A Frequency-based Parent Selection for Reducing the Effect of Evaluation Time Bias in Asynchronous Parallel Multi-objective Evolutionary Algorithms

This paper proposes a new parent selection method for reducing the effect of evaluation time bias in asynchronous parallel evolutionary algorithms (APEAs). APEAs have the advantage of increasing computational efficiency even when the evaluation times of solutions differ. However, APEAs have a problem that their search direction is biased toward the search region with a short evaluation time. The proposed parent selection method considers the search frequency of solutions to reduce such an adverse influence of APEAs while maintaining their computational efficiency. We conduct experiments on toy problems that reproduce the evaluation time bias on multi-objective optimization problems to investigate the effectiveness of the proposed method. The experiments use NSGA-III, a well-known multi-objective evolutionary algorithm. In the experiments, we compare the proposed method with the synchronous and asynchronous methods. The experimental results reveal that the proposed method can reduce the effect of the evaluation time bias while reducing the computing time of the parallel NSGA-III.