A Comparative Study of Three Evolutionary Algorithms Incorporating Different Amounts of Domain Knowledge for Node Covering Problem

Research output: Contribution to journalArticle

Standard

Harvard

APA

Vancouver

Author

Bibtex

@article{18d66340992a4583a364e90716320db6,
title = "A Comparative Study of Three Evolutionary Algorithms Incorporating Different Amounts of Domain Knowledge for Node Covering Problem",
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.",
keywords = "performance analysis, optimization methods, algorithm design, heuristic knowledge",
author = "Jun He and Xin Yao and Jin Li",
year = "2005",
month = may,
day = "1",
doi = "10.1109/TSMCC.2004.841903",
language = "English",
volume = "35",
pages = "266--271",
journal = "IEEE Transactions on Systems, Man and Cybernetics, Part C",
issn = "1094-6977",
publisher = "Institute of Electrical and Electronics Engineers (IEEE)",
number = "2",

}

RIS

TY - JOUR

T1 - A Comparative Study of Three Evolutionary Algorithms Incorporating Different Amounts of Domain Knowledge for Node Covering Problem

AU - He, Jun

AU - Yao, Xin

AU - Li, Jin

PY - 2005/5/1

Y1 - 2005/5/1

N2 - 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.

AB - 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.

KW - performance analysis

KW - optimization methods

KW - algorithm design

KW - heuristic knowledge

UR - http://www.scopus.com/inward/record.url?scp=18544379627&partnerID=8YFLogxK

U2 - 10.1109/TSMCC.2004.841903

DO - 10.1109/TSMCC.2004.841903

M3 - Article

VL - 35

SP - 266

EP - 271

JO - IEEE Transactions on Systems, Man and Cybernetics, Part C

JF - IEEE Transactions on Systems, Man and Cybernetics, Part C

SN - 1094-6977

IS - 2

ER -