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.
翻译:研究平行进化算法(PEAs)是为了通过使用平行计算来缩短进化算法的执行时间。一个非同步的PEA(APEA)是PEA(APEA)的一个计划,它通过在解决方案评价完成后,在没有计算节点的交替时间的情况下,立即产生新的解决方案来提高计算效率。然而,由于APEA为缩短评价时间的解决方案提供了更多的搜索机会,解决方案的评价时间偏向对搜索工作产生了负面影响。为克服这一缺陷,本文件建议了一个新的家长选择方法,以减少在APEA中评价时间偏差的影响。拟议方法考虑了解决方案的搜索频率,并选择了母解决方案,这样,不管评价时间的偏差,人口搜索进展是统一的。本文对模拟评价时间偏差的多目标优化问题进行了实验。实验使用NSGA-III,这是众所周知的多目标演进算法,并将拟议方法与常规同步/同步平行平行法进行比较。实验结果显示,拟议的方法可以减少评价时间偏差的影响,同时减少平行的NSGA-III的计算时间。