A genetic algorithm hybridisation scheme for effective use of parallel workers

Simon Bowly

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearch

1 Citation (Scopus)

Abstract

Genetic algorithms are simple to accelerate by evaluating the fitness of individuals in parallel. However, when fitness evaluation is expensive and time to evaluate each individual is highly variable, workers can be left idle while waiting for long-running tasks to complete. This paper proposes a local search hybridisation scheme which guarantees 100% utilisation of parallel workers. Separate work queues are maintained for individuals produced by genetic crossover and local search neighbourhood operators, and a priority rule determines which queue should be used to distribute work at each step. Hill-climbing local search and a conventional genetic algorithm can both be derived as special cases of the algorithm. The general case balances allocation of computing time between progressing the genetic algorithm and improving individuals through local search. Through evaluation on a simulated expensive optimisation problem we show that the search performance of the algorithm in terms of number of function evaluations does not vary significantly with the number of workers used, while still achieving linear speedup through parallelisation. Comparisons with an asynchronous genetic algorithm show that this method of using idle worker capacity for local search can improve performance when the computation budget is limited.

Original languageEnglish
Title of host publicationGECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference
Subtitle of host publication2019 Genetic and Evolutionary Computation Conference, GECCO 2019; Prague; Czech Republic; 13 July 2019 through 17 July 2019
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Pages745-752
Number of pages8
ISBN (Electronic)9781450361118
DOIs
Publication statusPublished - 13 Jul 2019
Externally publishedYes
EventThe Genetic and Evolutionary Computation Conference 2019 - Prague, Czechia
Duration: 13 Jul 201917 Jul 2019
Conference number: 21st
https://gecco-2019.sigevo.org/index.html/HomePage
https://dl.acm.org/doi/proceedings/10.1145/3321707 (Proceedings)

Publication series

NameGECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference

Conference

ConferenceThe Genetic and Evolutionary Computation Conference 2019
Abbreviated titleGECCO 2019
Country/TerritoryCzechia
CityPrague
Period13/07/1917/07/19
Internet address

Keywords

  • Genetic algorithms
  • Hybrid algorithms
  • Parallelisation

Cite this