Parallel Evolutionary Algorithm with Interleaving Generations

0477041 - ÚI 2018 RIV US eng C - Conference Paper (international conference)
Pilát, M. - Neruda, Roman
Parallel Evolutionary Algorithm with Interleaving Generations.
GECCO 2017. Proceedings of the 2017 Genetic and Evolutionary Computation Conference. New York: ACM, 2017, s. 865-872. ISBN 978-1-4503-4920-8.
[GECCO 2017. Genetic and Evolutionary Computation Conference. Berlin (DE), 15.07.2017-19.07.2017]
R&D Projects: GA ČR GA15-19877S
Institutional support: RVO:67985807
Keywords : evolutionary algorithms * parallelization * evaluation-time bias * complex optimization * interleaving generations
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

We present a parallel evolutionary algorithm with interleaving generations. The algorithm uses a careful analysis of genetic operators and selection in order to evaluate individuals from following generations while the current generation is still not completely evaluated. This brings significant advantages in cases where each fitness evaluation takes different amount of time, the evaluations are performed in parallel, and a traditional generational evolutionary algorithm has to wait for all evaluations to finish. The proposed algorithm provides better utilization of computational resources in these cases. Moreover, the algorithm is functionally equivalent to the generational evolutionary algorithm, and thus it does not have any evaluation time bias, which is often present in asynchronous evolutionary algorithms. The proposed algorithm is tested in a series of simple experiments and its effectiveness is compared to the effectiveness of the generational evolutionary algorithm in terms of CPU utilization.
Permanent Link: http://hdl.handle.net/11104/0273439