A runtime analysis of evolutionary algorithms for constrained optimization problems

Yuren Zhou, Jun He

Research output: Contribution to journalArticlepeer-review

Abstract

Although there are many evolutionary algorithms (EAs) for solving constrained optimization problems, there are few rigorous theoretical analyses. This paper presents a time complexity analysis of EAs for solving constrained optimization. It is shown when the penalty coefficient is chosen properly, direct comparison between pairs of solutions using penalty fitness function is equivalent to that using the criteria ldquosuperiority of feasible pointrdquo or ldquosuperiority of objective function value.rdquo This paper analyzes the role of penalty coefficients in EAs in terms of time complexity. The results show that in some examples, EAs benefit greatly from higher penalty coefficients, while in other examples, EAs benefit from lower penalty coefficients. This paper also investigates the runtime of EAs for solving the 0-1 knapsack problem and the results indicate that the mean first hitting times ranges from a polynomial-time to an exponential time when different penalty coefficients are used.
Original languageEnglish
Pages (from-to)608-619
Number of pages12
JournalIEEE Transactions on Evolutionary Computation
Volume11
Issue number5
DOIs
Publication statusPublished - Oct 2007

Fingerprint

Dive into the research topics of 'A runtime analysis of evolutionary algorithms for constrained optimization problems'. Together they form a unique fingerprint.

Cite this