Asynchronously evolving solutions with excessively different evaluation time by reference-based evaluation
Tomohiro Harada, Keiki Takadama · 2014
The asynchronous evolution has an advantage when evolving solutions with excessively different evaluation time since the asynchronous evolution evolves each solution independently without waiting for other evaluations, unlike the synchronous evolution requires evaluations of all solutions at the same time. As a novel asynchronous evolution approach, this paper proposes Asynchronous Reference-based Evaluation (ARE) that asynchronously selects good parents by the tournament selection using reference solution in order to evolve solutions through a crossover of the good parents. To investigate the effectiveness of ARE in the case of evolving solutions with excessively different evaluation time, this paper applies ARE to Genetic Programming (GP), and compares GP using ARE (ARE-GP) with GP using (μ+λ) selection ((μ+λ)-GP) as the synchronous approach in particular situation where the evaluation time of individuals differs from each other. The intensive experiments have revealed the following implications: (1) ARE-GP greatly outperforms (μ+λ)-GP from the viewpoint of the elapsed unit time in the parallel computation environment, (2) ARE-GP can evolve individuals without decreasing the searching ability in the situation where the computing speed of each individual differs from each other and some individuals fail in their execution.