  Parallel evolutionary algorithms (PEAs) have been studied for reducing the
execution time of evolutionary algorithms by utilizing parallel computing. An
asynchronous PEA (APEA) is a scheme of PEAs that increases computational
efficiency by generating a new solution immediately after a solution evaluation
completes without the idling time of computing nodes. However, because APEA
gives more search opportunities to solutions with shorter evaluation times, the
evaluation time bias of solutions negatively affects the search performance. To
overcome this drawback, this paper proposes a new parent selection method to
reduce the effect of evaluation time bias in APEAs. The proposed method
considers the search frequency of solutions and selects the parent solutions so
that the search progress in the population is uniform regardless of the
evaluation time bias. This paper conducts experiments on multi-objective
optimization problems that simulate the evaluation time bias. The experiments
use NSGA-III, a well-known multi-objective evolutionary algorithm, and compare
the proposed method with the conventional synchronous/asynchronous
parallelization. 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.
