| The Centre of Excellence for Research in Computational Intelligence and Applications (2008) | |||||||||||||||
Abstract | |||||||||||||||
| This paper compares three different evolutionary algorithms for solving the node covering problem: EA-I relies on the definition of the problem only without using any domain knowledge, while EA-II and EA-III employ extra heuristic knowledge for the problem. It is proven in theory all three evolutionary algorithms can find the optimal solution in a finite computation time, find a feasible solution efficiently, but none of them can find the optimal solution efficiently for all instances of the problem. Through experiments, it is found that all three evolutionary algorithms can find a feasible solution efficiently, and evolutionary algorithms with extra heuristic knowledge can find good approximation solutions; but none of them can find the optimal solution to the first instance efficiently. It is shown in this paper that heuristic knowledge is helpful for evolutionary algorithms to find good approximation solutions, but for some instances, it contributes little to finding the optimal solution. I. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||