A runtime analysis of evolutionary algorithms for constrained optimization problems

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

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 "superiority of feasible point" or "superiority of objective function value." 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.

Details

Original languageEnglish
Pages (from-to)608-619
Number of pages12
JournalIEEE Transactions on Evolutionary Computation
Volume11
Issue number5
Publication statusPublished - 1 Oct 2007

Keywords

  • evolutionary algorithms (EAs), 0-1 knapsack problems, constrained optimization problem, time complexity