The impact of migration topology on the runtime of island models in dynamic optimization

Andrei Lissovoi, Carsten Witt

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

We introduce a simplified island model with behavior similar to the λ (1+1) islands optimizing the Maze fitness function, and investigate the effects of the migration topology on the ability of the simplified island model to track the optimum of a dynamic fitness function. More specifically, we prove that there exist choices of model parameters for which using a unidirectional ring as the migration topology allows the model to track the oscillating optimum through n Mazelike phases with high probability, while using a complete graph as the migration topology results in the island model losing track of the optimum with overwhelming probability. Additionally, we prove that if migration occurs only rarely, denser migration topologies may be advantageous. This serves to illustrate that while a less-dense migration topology may be useful when optimizing dynamic functions with oscillating behavior, and requires less problem-specific knowledge to determine when migration may be allowed to occur, care must be taken to ensure that a sufficient amount of migration occurs during the optimization process.
Original languageEnglish
Title of host publicationProceedings of the Genetic and Evolutionary Computation Conference (GECCO '16)
PublisherAssociation for Computing Machinery
Publication date2016
Pages1155-1162
ISBN (Print)978-1-4503-4206-3
DOIs
Publication statusPublished - 2016
EventGenetic and Evolutionary Computation Conference (GECCO 2016) - Denver, Colorado, United States
Duration: 20 Jul 201624 Jul 2016
Conference number: 25
http://gecco-2016.sigevo.org/index.html/HomePage#&panel1-1

Conference

ConferenceGenetic and Evolutionary Computation Conference (GECCO 2016)
Number25
CountryUnited States
CityDenver, Colorado
Period20/07/201624/07/2016
Internet address

Cite this

Lissovoi, A., & Witt, C. (2016). The impact of migration topology on the runtime of island models in dynamic optimization. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '16) (pp. 1155-1162). Association for Computing Machinery. https://doi.org/10.1145/2908812.2908843