| A new approach for analyzing average time complexity of population-based evolutionary algorithms on unimodal problems. | |
| | |
MedLine Citation:
|
PMID: 19336324 Owner: NLM Status: MEDLINE |
Abstract/OtherAbstract:
|
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 population-based 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 + n(2)/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. |
| | |
Authors:
|
Tianshi Chen; Jun He; Guangzhong Sun; Guoliang Chen; Xin Yao |
Related Documents
:
|
7722434 - Proof construction: adolescent development from inductive to deductive problem-solving ... 17217524 - Maximum common subgraph: some upper bound and lower bound results. 20076194 - Two approaches to the star mapping problem for space vehicle attitude determination. 2308534 - Adolescents & aids. three michigan physicians reach out to educate youth about aids/hiv. 856534 - Cumulative radiation effect. part vii: computer calculations and applications in clinic... 7722434 - Proof construction: adolescent development from inductive to deductive problem-solving ... |
Publication Detail:
|
Type: Journal Article; Research Support, Non-U.S. Gov't Date: 2009-03-24 |
Journal Detail:
|
Title: IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society Volume: 39 ISSN: 1941-0492 ISO Abbreviation: IEEE Trans Syst Man Cybern B Cybern Publication Date: 2009 Oct |
Date Detail:
|
Created Date: 2009-05-28 Completed Date: 2009-07-24 Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 9890044 Medline TA: IEEE Trans Syst Man Cybern B Cybern Country: United States |
Other Details:
|
Languages: eng Pagination: 1092-106 Citation Subset: IM |
Affiliation:
|
Department of Computer Science and Technology, Nature Inspired Computation and Applications Laboratory, University of Science and Technology of China, Hefei, China. |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
Algorithms* Artificial Intelligence* Computer Simulation Models, Genetic* Models, Theoretical* Pattern Recognition, Automated / methods* |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: L(2)- L(infinity) Control of Nonlinear Fuzzy ItO Stochastic Delay Systems via Dynamic Output Feedbac...
Next Document: AMPSO: A New Particle Swarm Method for Nearest Neighborhood Classification.