A genetic algorithm hybridisation scheme for effective use of parallel workers

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

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, Czech Republic
Duration: 13 Jul 201917 Jul 2019
https://gecco-2019.sigevo.org/index.html/HomePage

Publication series

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

Conference

ConferenceThe Genetic and Evolutionary Computation Conference 2019
Abbreviated titleGECCO 2019
CountryCzech Republic
CityPrague
Period13/07/1917/07/19
OtherGECCO is the largest selective conference in the field of Evolutionary Computation, and the main conference of the Special Interest Group on Genetic and Evolutionary Computation (SIGEVO) of the Association for Computing Machinery (ACM). GECCO implements a rigorous and selective reviewing process to identify important and technically sound papers to publish. The technical program is divided into thirteen tracks reflecting all aspects of our field and chaired by experts who make the decisions on accepted papers.
Internet address

Keywords

  • Genetic algorithms
  • Hybrid algorithms
  • Parallelisation

Cite this