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 language | English |
---|---|
Title of host publication | GECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference |
Subtitle of host publication | 2019 Genetic and Evolutionary Computation Conference, GECCO 2019; Prague; Czech Republic; 13 July 2019 through 17 July 2019 |
Place of Publication | New York NY USA |
Publisher | Association for Computing Machinery (ACM) |
Pages | 745-752 |
Number of pages | 8 |
ISBN (Electronic) | 9781450361118 |
DOIs | |
Publication status | Published - 13 Jul 2019 |
Externally published | Yes |
Event | The Genetic and Evolutionary Computation Conference 2019 - Prague, Czechia Duration: 13 Jul 2019 → 17 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
Name | GECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference |
---|
Conference
Conference | The Genetic and Evolutionary Computation Conference 2019 |
---|---|
Abbreviated title | GECCO 2019 |
Country/Territory | Czechia |
City | Prague |
Period | 13/07/19 → 17/07/19 |
Internet address |
Keywords
- Genetic algorithms
- Hybrid algorithms
- Parallelisation