A comparative study of three evolutionary algorithms incorporating different amounts of domain knowledge for node covering problem

Jun HE, Xin YAO, Jin LI

Research output: Journal PublicationsJournal Article (refereed)peer-review

32 Citations (Scopus)

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. In theory, it is proven that all three algorithms can find an optimal solution in finite generations and 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 observed that all three algorithms can find a feasible solution efficiently, and the algorithms with extra heuristic knowledge can find better approximation solutions, but none of them can find the optimal solution to the first instance efficiently. This paper shows that heuristic knowledge is helpful for evolutionary algorithms to find good approximation solutions, but it contributes little to search for the optimal solution in some instances. © 2005 IEEE.
Original languageEnglish
Pages (from-to)266-271
Number of pages6
JournalIEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews
Volume35
Issue number2
Early online date25 Apr 2005
DOIs
Publication statusPublished - May 2005
Externally publishedYes

Bibliographical note

This work was supported in part by the Engineering and Physical Sciences Research Council under Grant GR/S63847/01, in part by the State Key Lab of Software Engineering at Wuhan University, and in part by the National Natural Science Foundation under Grant 60443003. This paper was recommended by Guest Editor Y. Jin.

Keywords

  • Algorithm design
  • Heuristic knowledge
  • Optimization methods
  • Performance analysis

Fingerprint

Dive into the research topics of 'A comparative study of three evolutionary algorithms incorporating different amounts of domain knowledge for node covering problem'. Together they form a unique fingerprint.

Cite this