分布式进化算法的性能测试与分析

针对分布式进化算法设计过程中由于缺乏对性能影响因素的分析而导致算法无法达到预期加速比的问题,提出一种全面的性能分析方法。根据分布式进化算法的组成结构,将影响分布式进化算法性能的因素分为进化操作开销、适应值计算开销和通信开销三个部分。首先研究进化算法在不同个体编码维数下进化操作开销的特性;其次,在进化操作开销相对固定的情况下,通过使用操作系统的延时函数控制适应值计算开销,通过改变个体编码维数控制通信开销;最后,应用控制变量方法,逐一测试各因素对算法加速比的影响。实验结果展现了三种因素的相互制约关系,给出了分布式进化算法获得更好加速比的条件。

Performance tests and analysis of distributed evolutionary algorithms

Due to the lack of performance analysis while designing a distributed Evolutionary Algorithm (dEA), the designed algorithm cannot reach the expected speedup. To solve this problem, a comprehensive performance analysis method was proposed. According to the components of dEAs, factors that influence the performance of dEAs can be divided into three parts, namely, evolutionary cost, fitness evaluation cost and communication cost. Firstly, the feature of evolutionary cost under different individual encoding lengths was studied. Then when the evolutionary cost was kept unchanged, the fitness evaluation cost was controlled by using the delay function of the operating system and the communication cost was controlled by changing the length of individual encoding. Finally, the effect of each factor was tested through control variable method. The experimental results reveal the constraint relation among the three factors and point out the necessary conditions for speeding up dEAs.