When hillclimbers beat genetic algorithms in multimodal optimization

Lobo, F.J.; Bazargani, Mosab

Publication

When hillclimbers beat genetic algorithms in multimodal optimization

2015-04-26Journal article

dc.contributor.author	Lobo, F.J.
dc.contributor.author	Bazargani, Mosab
dc.date.accessioned	2023-03-15T11:08:46Z
dc.date.available	2023-03-15T11:08:46Z
dc.date.issued	2015-04-26
dc.description.abstract	This paper investigates the performance of multistart next ascent hillclimbing and well-known evolutionary algorithms incorporating diversity preservation techniques on instances of the multimodal problem generator. This generator induces a class of problems in the bitstringdomain which is interesting to study from a theoretical perspective in the context of multimodal optimization, as it is a generalization of the classical OneMax and TwoMax functions for an arbitrary number of peaks. An average-case runtime analysis for multistart next ascent hill-climbing is presented for uniformly distributed equal-height instances of this class of problems. It is shown empirically that conventional niching and mating restriction techniques incorporated in an evolutionary algorithm are not sufficient to make them competitive with the hillclimbing strategy. We conjecture the reason for this behaviour is the lack of structure in the space of local optima on instances of this problem class, which makes an optimization algorithm unable to exploit information from one optimum to infer where another optimum might be. When no such structure exist, it seems that the best strategy for discovering all optima is a brute-force one. Overall, our study gives insights with respect to the adequacy of hillclimbers and evolutionary algorithms for multimodal optimization, depending on properties of the fitness landscape.	pt_PT
dc.description.version	info:eu-repo/semantics/publishedVersion	pt_PT
dc.identifier.doi	10.1162/evco_a_00312	pt_PT
dc.identifier.eissn	1530-9304
dc.identifier.uri	http://hdl.handle.net/10400.1/19254
dc.language.iso	eng	pt_PT
dc.peerreviewed	yes	pt_PT
dc.publisher	MIT Press	pt_PT
dc.relation	Center for Environmental and Sustainability Research
dc.rights.uri	http://creativecommons.org/licenses/by/4.0/	pt_PT
dc.subject	Multimodal optimization	pt_PT
dc.subject	Niching	pt_PT
dc.subject	Multimodal problem generator	pt_PT
dc.subject	Hill-climbing	pt_PT
dc.subject	Evolutionary algorithms	pt_PT
dc.title	When hillclimbers beat genetic algorithms in multimodal optimization	pt_PT
dc.type	journal article
dspace.entity.type	Publication
oaire.awardTitle	Center for Environmental and Sustainability Research
oaire.awardURI	info:eu-repo/grantAgreement/FCT/6817 - DCRRNI ID/UIDB%2F04085%2F2020/PT
oaire.citation.endPage	559	pt_PT
oaire.citation.issue	4	pt_PT
oaire.citation.startPage	535	pt_PT
oaire.citation.title	Evolutionary Computation	pt_PT
oaire.citation.volume	30	pt_PT
oaire.fundingStream	6817 - DCRRNI ID
person.familyName	Lobo
person.givenName	Francisco José
person.identifier.orcid	0000-0002-3294-7202
person.identifier.rid	J-9836-2012
person.identifier.scopus-author-id	7007134816
project.funder.identifier	http://doi.org/10.13039/501100001871
project.funder.name	Fundação para a Ciência e a Tecnologia
rcaap.rights	openAccess	pt_PT
rcaap.type	article	pt_PT
relation.isAuthorOfPublication	6f1a2a3e-5d33-44c1-8382-e82064c6ed67
relation.isAuthorOfPublication.latestForDiscovery	6f1a2a3e-5d33-44c1-8382-e82064c6ed67
relation.isProjectOfPublication	84911521-6e52-41f6-abed-98015910a175
relation.isProjectOfPublication.latestForDiscovery	84911521-6e52-41f6-abed-98015910a175