A genetic algorithm hybridisation scheme for effective use of parallel workers

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.