From an Individual to a Population: An Analysis of the First Hitting Time of Population-based Evolutionary Algorithms

H...............H

Show simple item record

dc.contributor.author He, Jun
dc.contributor.author Yao, Xin
dc.date.accessioned 2008-12-18T11:30:05Z
dc.date.available 2008-12-18T11:30:05Z
dc.date.issued 2008-12-18
dc.identifier.citation He , J & Yao , X 2008 , ' From an Individual to a Population: An Analysis of the First Hitting Time of Population-based Evolutionary Algorithms ' IEEE Transactions on Evolutionary Computation , pp. 495-511 . en
dc.identifier.other PURE: 105601
dc.identifier.other dspace: 2160/1777
dc.identifier.uri http://hdl.handle.net/2160/1777
dc.description He, J., Yao, X., From an Individual to a Population: An Analysis of the First Hitting Time of Population-based Evolutionary Algorithms, IEEE Transactions on Evolutionary Computation, 6(5) pp.495-511 en
dc.description.abstract Almost all analyses of time complexity of evolutionary algorithms (EAs) have been conducted for (1 + 1) EAs only. Theoretical results on the average computation time of population-based EAs are few. However, the vast majority of applications of EAs use a population size that is greater than one. The use of population has been regarded as one of the key features of EAs. It is important to understand in depth what the real utility of population is in terms of the time complexity of EAs, when EAs are applied to combinatorial optimization problems. This paper compares (1 + 1) EAs and (N + N) EAs theoretically by deriving their first hitting time on the same problems. It is shown that a population can have a drastic impact on an EA's average computation time, changing an exponential time to a polynomial time (in the input size) in some cases. It is also shown that the first hitting probability can be improved by introducing a population. However, the results presented in this paper do not imply that population-based EAs will always be better than (1 + 1) EAs for all possible problems. en
dc.format.extent 17 en
dc.language.iso eng
dc.relation.ispartof IEEE Transactions on Evolutionary Computation en
dc.title From an Individual to a Population: An Analysis of the First Hitting Time of Population-based Evolutionary Algorithms en
dc.type Text en
dc.type.publicationtype Article (Journal) en
dc.contributor.institution Department of Computer Science en
dc.description.status Peer reviewed en


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Cadair


Advanced Search

Browse

My Account