基于种子的多种群多策略并行PSO用于原子簇结构优化

朱静静 刘 静

(上海海事大学信息工程学院 上海 201306)

0 引 言

原子簇是由几个乃至上千个原子通过化学结合力组成的相对稳定的微观和亚微观的聚集体，它被广泛应用于电化学、催化反应、航天工业等领域，而具有稳定空间结构的原子簇能够更好地保持并发挥其优越的性能，因此研究原子簇的结构优化问题具有重大的现实意义。迄今为止，通过实验和理论方法只确定了少数种类原子簇的最优空间结构，随着计算机模拟技术和计算机硬件软件的飞速发展，通过理论方法来得到大多数原子簇的空间结构成为大势所趋。当今主流的理论确定原子簇空间结构的方法为从头预测法，该法直接从原子数目出发，首先建立一个表征原子簇的空间结构与其势能之间关系的函数，然后根据热物理理论，通过搜索算法找出原子簇势能最低时对应的空间结构即为该原子簇的最稳定结构。

目前常用于搜索原子簇最优结构的算法有:蒙特·卡洛(Monte-Carlo)[1]、模拟退火(SA)[2-3]、遗传算法(GA)[4-6]和粒子群算法(PSO)[7-8]等。其中粒子群算法是由Kennedy和Eberhart提出的一种基于鸟类觅食行为的启发式群智能优化算法[9-10],PSO具有无需繁杂的进化操作、易于实现、参数少等优点，但也具有易出现早熟陷入局部最优、精度较低等不足，为了改进PSO的性能，学者们从不同的切入点进行突破，包括局部版本的PSO[11-12]、协同演化PSO[13]、动态多种群粒子群算法(Dynamic Multi-Swarm Particle Swarm Optimizer，DMS-PSO)[14]、随机漂移粒子群算法(Random Drift Swarm Optimization，RDPSO)[15-16]和基于频繁覆盖策略的随机漂移粒子群算法(FC-RDPSO)[17]等。

本文提出了一种基于种子的多种群多策略并行粒子群算法(SS-MG-MS-PPSO)，且使用LJ函数测试该算法的运行效率。针对原子簇结构优化问题，随着原子数目的增加，单纯的PSO等算法的优化性能急剧衰减的原因有两点：1) 随着原子数目的不断增加导致原子簇的结构搜索空间持续膨胀，搜索到全局最优解的难度大大增加；2) 随着问题规模的增加，各个决策变量之间的耦合关系增强，搜索到的最优解很可能出现“前进两步，倒退一步”的现象，优化问题的复杂度大大增加。针对前者，种子策略(通过较少原子数目的原子簇最优结构信息来引导寻优方向)可以大大减小搜索空间体积从而加快算法的搜索进程，而多种群多策略机制则可以增加种群的多样性，显著提高算法的优化性能。针对后者，多种群多策略中加入的FC-RDPSO在每次迭代时只针对个别变量进行子空间的优化，然后将各搜索子空间的优化结果进行频繁的交叉、叠加，最终覆盖到整个搜索空间，从而降低问题的复杂度。

该算法首先通过种子策略初始化种群，然后将初始化的种群划分为多个子种群，各子群按照RDPSO和FC-RDPSO两种不同的规则进化，同时为了增强算法的全局和局部搜索能力，不同的子群设置的速度限制项不同，以充分发挥多种群独立进化的优势。在单独进化达到一定的迭代次数后，进行种群间的通信交流，最终得到原子簇的最优结构或近似最优结构。此外，通过并行化操作进一步提高算法的运行性能及效率。

在原子簇的势能函数上对SS-MG-MS-PPSO进行优化测试，并进行算法的有效性论证，分别对原子数为2～35的原子簇结构进行优化。分别将DMS-RDPSO、DMS-FC-RDPSO和MG-MS-PSO与SS-MG-MS-PPSO进行比较，实验结果表明，SS-MG-MS-PPSO对于原子数在2到35之间的原子能搜索到其最优或近似最优结构，且在各性能上均具有较大优势。

1 计算原理

从头预测法确定原子簇的最优结构主要有两个步骤：找到一个表征原子簇各原子的空间三维坐标与其势能之间关系的函数；通过搜索算法找到能量最低时对应的原子簇的空间结构即为该原子簇的最稳定结构。本文使用的能量函数是L-J势能函数，该函数能用来模拟两分子或两原子间的作用势能，原子簇中所有原子间的相互作用势能之和即为该原子簇所具有的能量，包含N个原子的原子簇的势能用公式表示如下：

(1)

式中：ε表示二聚体的势能阱深度；σ表示二聚体的核心距；rij为原子簇中任意两个原子i与原子j间的欧氏距离。

(2)

2 算法描述

2.1 动态多种群粒子群算法

动态多种群粒子群算法(DMS-PSO)结合了局部PSO和基本全局PSO的优点，首先产生多个有效的初始解形成初始种群，再将初始种群划分为多个小种群(子群)，各子群在局部PSO下独立进化后，重新组合形成新的种群，反复迭代、进化。这样的优化规律增加了种群的多样性，当迭代达到一定次数后，使用全局版本的PSO对所有粒子进行更新，得到最终的结果[18]。

2.2 随机漂移粒子群算法

随机漂移粒子群算法(RDPSO)的中心思想来源于磁场中金属导体内的自由电子存在两种形式的运动：无规则的随机热运动和定向漂移运动。这两种运动方式使得金属导体内的势能逐渐变小，这与PSO搜索优化问题全局最优解的过程如出一辙。自由电子所做的随机热运动相当于优化搜索过程中粒子的全局搜索，受磁场环境影响而产生的定向漂移运动则类似于粒子的局部搜索，这两种搜索方式相辅相成，使得优化问题的目标函数值不断地接近于全局最优解。

在RDPSO中，粒子速度更新公式由定向漂移运动项和随机热运动项构成，速度更新公式如下：

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

综合1)、2)两项，RDPSO中的粒子速度更新公式可表示如下：

(12)

该算法中的粒子位置更新公式为：

(13)

综上，RDPSO通过粒子的速度和位置的不断更新，逐步地逼近目标函数的最优值，具有较强的优化能力。

2.3 基于频繁覆盖集策略的随机漂移粒子群算法

为了进一步提高RDPSO搜索到全局最优解的概率，文献[17]提出将频繁覆盖策略引入到RDPSO中。即在每次的迭代过程中仅优化一部分随机选取的决策变量，而保持其余变量不变，由此构成一个个的搜索子空间，利用RDPSO搜索粒子在各个子空间上的最优位置。由于每次迭代过程中优化的决策变量是随机选取的，经过多次迭代后，这些子空间中的变量相互重叠、交叉或互异，能够覆盖到整个搜索空间，从而子优化算法RDPSO能够搜索到全局最优值。这样的策略大大减小了子空间搜索的难度，这也是高维度复杂优化问题的有效解决方案之一。

2.4 基于种子的多种群多策略并行粒子群算法

2.4.1种子策略

本文采用种子策略(Seed Strategy，SS)，即参考已求得的具有较少原子数的原子簇最优空间结构，初始化原子数相对多的团簇空间结构的初始解产生方式。假设已求得含有N个原子的原子簇W的稳定结构，设此时原子簇W中N个原子的空间坐标为(X1，X2，…,Xi，…,XN)，若此时需要求解含有N+1个原子的原子簇的最优结构,如果在W的基础上增加一个随机生成坐标的原子XN+1作为该原子簇的初始解W’，虽然W’未必是该原子簇的最优结构，但通常会比随机初始化N+1个原子的三维坐标得到的初始解要更接近于该原子簇的最优结构。

因此，本文在求解含有较多原子的原子簇最优结构时，选择使用种子策略来初始化初始解，而对于所含原子数较少的原子簇最优结构的求解，初始解的生产方式依据求解的难度来选择。

2.4.2多种群多策略机制

本文除了在初始解的生成方式上进行改进外，还将多种群动态寻优机制加入到搜索算法中。为了最大程度地加强优化算法的搜索能力，将粒子群划分为多个小种群，各小种群分别在拥有不同参数的RDPSO和FC-RDPSO下并行寻优。由于RDPSO具有较强的全局搜索能力而FC-RDPSO能在较少的计算时间内具有较快的收敛速度和更高的寻优精度，而不同的参数控制着算法全局搜索和局部搜索的能力，因此该机制能够在高维度的优化问题上发挥出其明显的寻优和效率优势。

2.4.3并行化原理

本文提出的基于种子的多种群多策略并行粒子群算法(SS-MG-MS-PPSO)以较高效率解决高维度的优化问题，利用多种群机制将初始化的种群分配给拥有不同搜索能力的子群，这些子群在随机漂移粒子群算法(RDPSO)和基于频繁覆盖策略的随机漂移粒子群算法(FC-RDPSO)两种不同的规则下并行进化，大大增加了种群的多样性。由于RDPSO具有较强的全局搜索能力，FC-RDPSO可以产生许多搜索子空间，子空间使用RDPSO进行并行优化，从而能够以更大的概率覆盖到整个搜索空间，RDPSO和FC-RDPSO相结合再配合速度限制项的变化，所以该算法能够在原子簇的结构优化方面表现出优越的性能。除了算法内部的多种群机制并行策略和FC-RDPSO中的搜索子空间的并行进化以外，本文在此基础上加入了外部的并行机制，即利用MATLAB并行工具箱(Parallel Computing Tool，PCT)将算法放到一个计算机集群上并行计算，这大大地加快了算法的计算效率。

SS-MG-MS-PPSO通过内部和外部的同步并行运算，增强该算法在寻优性能和求解效率上的优势。

2.4.4算法流程

将本文提出的SS-MG-MS-PPSO应用于包含n个原子的原子簇结构优化，其优化求解的步骤如下：

(1) 设定算法的最大迭代次数maxiter和种群中的粒子数popsize，在可行域内选用适当的初始化方式(随机初始化方式或种子策略)构造popsize个3行n列的向量作为初始种群pop，每一个3行n列的向量代表一个包含n个原子的原子簇初始空间结构，并初始化总迭代次数i=1。

(2) 将种群pop随机划分为s个包含粒子数目相等的子群。

(3) 设定子群单独进化的总次数R，初始化子群单独进化次数r=1。

(4) 每个子群都在具有不同搜索能力的FC-RDPSO或RDPSO算子下单独进化，每单独进化一次r=r+1，当r

(5) 将单独进化R次后的s个子群合并，组成新的pop种群，并使得i=i+1，当i

3 参数设置和实验环境

为了检验本文提出的SS-MG-MS-PPSO算法解决原子簇结构优化问题的性能,选择原子数在2到35之间原子簇的L-J势能函数作为测试函数,选择DMS-RDPSO、DMS-FC-RDPSO和MG-MS-PSO三个算法作为对比算法，验证算法的有效性。根据相关参考文献，采用的算法参数设置见表1。其中，popsize表示种群规模，s表示多种群机制下的子群数目，α和β分别表示RDPSO中的热敏系数和漂移系数，M表示在FC-RDPSO每次迭代过程中选择优化的决策变量个数。

表1 各算法的参数设置

特别地，本文提出多种群多策略，在得到初始化种群后将其平均划分为12个子群，每个子群设置不同的速度限制项，速度限制项是用来限制粒子的飞行速度，若粒子飞行速度过快，很可能直接飞过最优解位置，但若飞行速度过慢，会使得收敛速度变慢，因此设置合理的速度限制项很有必要。各算法中每6个子群为一组，每组子群速度限制项vmax设为0至1的不同分节点。

本文实验所用的计算机配置如下：Intel Core i5-6500 CPU，3.20 GHz，8 GB内存，Windows 10专业版，64位操作系统。

4 结果分析

本文提出的SS-MG-MS-PPSO及对比算法(DMS-RDPSO、DMS-FC-RDPSO和MG-MS-PSO)在原子数为2到35的原子簇结构优化测试的结果如表2所示(原子数不同的原子簇对应兰纳琼斯势能各指标的理想值参考文献[19])。原子个数不同的原子簇优化结果的优劣由三个指标来评判，分别是各算法在此测试函数上独立运行30次所得目标函数值的最优值(Opt)、平均值(Ave)和标准差(Sta)。

表2 各算法在原子簇的L-J势能函数上的测试结果

续表2

续表2

为了更加直观地比较DMS-RDPSO、DMS-FC-RDPSO、MG-MS-PSO和SS-MG-MS-PPSO的实验结果，本文将各算法优化原子簇结构的结果用折线图表示。图1表示各算法求得的原子簇最低能量值与理想能量值的差值曲线；图2表示各算法独立运行30次求得的原子簇平均能量值与理想能量值的差值曲线；图3表示各算法独立运行30次求得的原子簇能量值标准差变化曲线。

图1 各算法求得的原子簇最低能量值 与理想能量值的差值曲线

图2 各算法独立运行30次求得的原子簇平均 能量值与理想能量值的差值曲线

图3 各算法独立运行30次求得的原子簇 能量值标准差变化曲线

从表2中可看出：对于原子数N=2,3,4,5的原子簇，各算法皆可求得原子簇的稳定结构，且均达到理想效果；对于原子数N=6，…，16的原子簇，各算法均能求得其最优结构，但SS-MG-MS-PPSO有更高的稳定性；当原子数N=17,…,25时，另外三个算法在个别原子数上所能求得的最优值与理想最优值均已存在差距，均值、标准差与理想值差距也较大，而此时SS-MG-MS-PPSO能求得其最优结构且标准差也相对较小；当原子数N=26,…,31时，三个对比算法能求得的最优值与理想最优值之间存在较大差距，而SS-MG-MS-PPSO能求得的最优值与理想最优值差距较小，整体上保持着算法的稳定性；当原子数N=32,33时，SS-MG-MS-PPSO求得的最优结构与理想最优值有一定差距，但与其他三个算法相比，差距已经大大地缩小，且均值与方差也在一定的波动范围之内；当原子数N=34,35时，SS-MG-MS-PPSO求得的最优结构与理想最优值有差距，相对于DMS-FC-RDPSO和MG-MS-PSO而言，稍显逊色，但更稳定，原因可能是“种子策略”限制了原子簇结构的自由“生长”，使其极易陷入局部极优，所以相对其他算法不易跳出局部极优，更显稳定。从整体来看，当原子数N=2,3,...,33时，SS-MG-MS-PPSO明显优于其他三个算法，并且能以较高的效率求得原子簇的最优结构或近似最优结构。

从图1和图2也可以发现，SS-MG-MS-PPSO30次独立运行求得的最优值、平均值与理想值之间的差距明显小于三个对比算法。图3充分展现了SS-MG-MS-PPSO较其他算法都更为稳定。综上所述，本文提出的SS-MG-MS-PPSO在原子数为N=2,…,35的原子簇结构优化上，有着更高的寻优效率和更好的稳定性。

此外，本文算法使用的并行机制将串行运行仅25%的CPU利用率提高到了95%以上，运行时间显著减少，大大加快了算法的运行效率。

5 结 语

本文针对原子簇结构优化问题，提出了一种基于种子的多种群多策略并行粒子群算法(SS-MG-MS-PPSO)。该算法使用种子策略初始化种群，然后将种群划分为多个子群且各子群在不同的规则下单独进化，只需定期进行通信交流，通过发挥不同搜索策略的优势从而找到原子簇的最优结构或近似最优结构。实验结果表明，SS-MG-MS-PPSO对于原子数在2到35之间的原子簇搜索到其最优或近似最优结构，且相比其他算法更为稳定、高效，证明种子策略(SS)和多种群多策略并行进化机制可有效增强算法的搜索效率和能力，为原子簇的结构优化提供了一种新的解决思路。当然，该算法存在一定的缺陷，随着原子数的增加，该算法寻求原子簇最优结构的能力稍显力不从心，这也是该课题未来的主要研究方向。