Improving CPU utilization of interleaving generation parallel evolutionary algorithm with precedence evaluation of tentative solutions and their suspension

Abstract

This paper proposes a new mechanism to improve the CPU efficiency of parallel evolutionary algorithms (PEAs). The proposed method is based on interleaving generation evolutionary algorithm (IGEA) that was proposed in a previous study. Whereas PEA generates offspring after all individuals are evaluated, IGEA generates offspring of which all parents have been determined before other evaluations are completed. The proposed method introduced a precedence evaluation of tentative offspring and their suspension mechanism into IGEA. In particular, while IGEA generates offspring of which all parents have been determined, the proposed method tentatively generates offspring when one of two parents has been determined and then begins their evaluations. The evaluation of unnecessary offspring is suspended when the other parent of tentative offspring is determined. We compare the proposed method with the original IGEA and a simple PEA to investigate the effectiveness of the proposed method. This paper considers two replacement schemes of PEAs, $ (\lambda , \lambda ) $ -PEA and $ (\lambda +\lambda ) $ -PEA. The experimental results reveal that the proposed method has higher CPU utilization than the original IGEA and the simple PEA on both schemes.

Keywords

• evolutionary algorithm
• parallelization
• interleaving generations
• evaluation time difference
• computational efficiency