IEEE Trans Cybern. 2021 Oct;51(10):4848-4859. doi: 10.1109/TCYB.2020.3028070. Epub 2021 Oct 12.
Due to the population-based and iterative-based characteristics of evolutionary computation (EC) algorithms, parallel techniques have been widely used to speed up the EC algorithms. However, the parallelism usually performs in the population level where multiple populations (or subpopulations) run in parallel or in the individual level where the individuals are distributed to multiple resources. That is, different populations or different individuals can be executed simultaneously to reduce running time. However, the research into generation-level parallelism for EC algorithms has seldom been reported. In this article, we propose a new paradigm of the parallel EC algorithm by making the first attempt to parallelize the algorithm in the generation level. This idea is inspired by the industrial pipeline technique. Specifically, a kind of EC algorithm called local version particle swarm optimization (PSO) is adopted to implement a pipeline-based parallel PSO (PPPSO, i.e., PSO). Due to the generation-level parallelism in PSO, when some particles still perform their evolutionary operations in the current generation, some other particles can simultaneously go to the next generation to carry out the new evolutionary operations, or even go to further next generation(s). The experimental results show that the problem-solving ability of PSO is not affected while the evolutionary speed has been substantially accelerated in a significant fashion. Therefore, generation-level parallelism is possible in EC algorithms and may have significant potential applications in time-consumption optimization problems.
由于进化计算 (EC) 算法具有基于群体和基于迭代的特点，因此已经广泛使用并行技术来加速 EC 算法。然而，并行性通常在群体级别上执行，其中多个群体（或子群体）并行运行，或者在个体级别上执行，其中个体分布到多个资源上。也就是说，可以同时执行不同的群体或不同的个体，以减少运行时间。但是，针对 EC 算法的生成级并行性的研究很少有报道。在本文中，我们通过首次尝试在生成级并行化算法，提出了一种新的并行 EC 算法范例。这个想法是受工业流水线技术的启发。具体来说，采用一种称为局部版本粒子群优化 (PSO) 的 EC 算法来实现基于流水线的并行 PSO (PPPSO，即 PSO)。由于 PSO 中的生成级并行性，当一些粒子仍在当前代中执行其进化操作时，其他一些粒子可以同时进入下一代执行新的进化操作，甚至进入进一步的下一代。实验结果表明，PSO 的求解能力不受影响，而进化速度却得到了显著加速。因此，EC 算法中可能存在生成级并行性，并且在时间消耗优化问题中可能具有重要的潜在应用。
