A new approach for analyzing average time complexity of population-based evolutionary algorithms on unimodal problems

Tianshi CHEN, Jun HE, Guangzhong SUN, Guoliang CHEN, Xin YAO

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

58 Citations (Scopus)

Abstract

In the past decades, many theoretical results related to the time complexity of evolutionary algorithms (EAs) on different problems are obtained. However, there is not any general and easy-to-apply approach designed particularly for populationbased EAs on unimodal problems. In this paper, we first generalize the concept of the takeover time to EAs with mutation, then we utilize the generalized takeover time to obtain the mean first hitting time of EAs and, thus, propose a general approach for analyzing EAs on unimodal problems. As examples, we consider the so-called (N + N) EAs and we show that, on two well-known unimodal problems, LEADINGONES and ONEMAX, the EAs with the bitwise mutation and two commonly used selection schemes both need O(n ln n + n2/N) and O(n ln ln n + n ln n/N) generations to find the global optimum, respectively. Except for the new results above, our approach can also be applied directly for obtaining results for some population-based EAs on some other unimodal problems. Moreover, we also discuss when the general approach is valid to provide us tight bounds of the mean first hitting times and when our approach should be combined with problem-specific knowledge to get the tight bounds. It is the first time a general idea for analyzing population-based EAs on unimodal problems is discussed theoretically. © 2009 IEEE.
Original languageEnglish
Pages (from-to)1092-1106
Number of pages15
JournalIEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
Volume39
Issue number5
Early online date24 Mar 2009
DOIs
Publication statusPublished - Oct 2009
Externally publishedYes

Bibliographical note

This work was supported in part by the National Natural Science Foundation of China under Grants 60533020 and U0835002, by the Fund for Foreign Scholars in University Research and Teaching Programs under Grant B07033, by the Fund for International Joint Research Program of Anhui Science and Technology Department under Grant 08080703016, and by an Engineering and Physical Science Research Council Grant in U.K. under Grant EP/C520696/1. This paper was recommended by Associate Editor H. Takagi.

Keywords

  • Drift analysis, evolutionary algorithms (EAs)
  • First hitting time
  • Takeover time
  • Unimodal problems

Fingerprint

Dive into the research topics of 'A new approach for analyzing average time complexity of population-based evolutionary algorithms on unimodal problems'. Together they form a unique fingerprint.

Cite this