基于种群关系的多种群粒子群协同优化算法

引用本文

刘悦, 杨桦, 王青正. 基于种群关系的多种群粒子群协同优化算法. 计算机系统应用, 2021, 30(10): 148-155.http://www.c-s-a.org.cn/1003-3254/7941.html

Liu Y, Yang H, Wang QZ. Multi-Swarm Particle Swarm Optimization Based on Population Relation. Computer Systems and Applications, 2021, 30(10): 148-155(in Chinese).http://www.c-s-a.org.cn/1003-3254/7941.html

基于种群关系的多种群粒子群协同优化算法

刘悦¹, 杨桦¹, 王青正²

1. 开封大学信息工程学院, 开封 475004;
2. 上海交通大学电子信息与电气工程学院, 上海 200240

收稿日期：2020-09-19; 修改日期：2020-10-21; 采用时间：2020-11-12

基金项目：国家自然科学基金(61702185); 河南省高等学校重点科研项目(19B520014); 河南省高等学校青年骨干教师培养计划(2017GGJS270)

通讯作者：杨桦, E-mail: 852278078@qq.com.

摘要：传统粒子群优化算法容易陷入局部最优解, 搜索效率不高, 针对此问题, 提出了一种基于种群关系和斥力因子的多种群粒子群优化算法SRB-PSO (Swarm-Relation-Based PSO). 根据当前搜索结果定义种群之间统治、对等和被统治3种关系, 通过引入斥力因子来保证种群间搜索的多样性, 并通过统治和被统治关系提高算法的搜索效率, 从而在改善算法的全局搜索性能的同时提高解的质量. 将算法与其他几种主流粒子群优化改进算法在标准测试集上进行对比, 实验结果证明了SRB-PSO算法能较好地保持粒子多样性, 全局搜索能力强, 在解决多峰函数时的性能优于其他几种主流粒子群优化改进算法.

关键词: 粒子群优化多种群种群关系斥力因子多峰问题

Multi-Swarm Particle Swarm Optimization Based on Population Relation

LIU Yue¹, YANG Hua¹, WANG Qing-Zheng²

1. College of Information Engineering, Kaifeng University, Kaifeng 475004, China;
2. School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China

Foundation item: National Natural Science Foundation of China (61702185); Key Scientific Research Program of the Institutions of Higher Education in Henan Province (19B520014); Training Plan for Young Backbone Teachers in the Institutions of Higher Education in Henan Province (2017GGJS270)

Abstract: Traditional Particle Swarm Optimization (PSO) is likely to converge to local optima when applied to multimodal problems, with low search efficiency. In this study, a novel multi-swarm PSO algorithm based on swarm relations and repulsion factors is proposed, called Swarm-Relation-Based PSO (SRB-PSO). Three swarm relations, including dominance, equivalence, and weakness, are defined according to the search results. The search diversity is guaranteed by introducing repulsion factors among equivalent populations and the search efficiency is increased by dominance and weakness relations. Thus, the global search ability of the algorithm is enhanced and the solution quality is improved. The new algorithm and several other versions of PSO are compared on a set of benchmark functions. The results show that the algorithm proposed in this study can well maintain the particle diversity and has outstanding global search ability. The proposed algorithm outperforms the other algorithms when solving multimodal problems.

Key words: Particle Swarm Optimization (PSO) multi-swarm swarm relation repulsion factor multimodal problem

粒子群优化算法(Particle Swarm Optimization, PSO)是1995年 Kennedy和Eberhart提出的一种随机搜索算法^[1], 它模仿鸟群和鱼群的群体觅食行为, 通过种群中个体之间的协同进化在解空间内搜索最优解. 种群中的每一个粒子被视为独立个体, 粒子通过自身的历史位置信息以及整个种群的位置信息来对当前的速度和位置进行相应地调整. 粒子群优化算法具有操作简单, 收敛速度快的优点, 因此受到国内外学者的广泛关注. 由于PSO的操作不关心优化函数是否具有可微、连续等性质, 所以应用PSO解决实际问题时更容易建模, 具有很强的实用性, 例如农业、电力系统、自动控制、车辆制造^[2-5], 但是粒子群优化算法在解决复杂多峰问题时, 容易陷入局部最优解.

目前, 学者们采用多种改进方式来提高算法的全局搜索能力, 主要包括: (1) 改进拓扑结构. 如Eberhart和Kennedy在文献[6]中提出了局部版本的粒子群优化算法, 提出了环形拓扑结构, 保证了搜索过程中粒子的多样性. 靳雁霞等在文献[7]中, 提出环状全互联结构, 通过自适应逃逸机制, 防止算法陷入局部最优. 焦重阳等在文献[8]中, 提出混合拓扑结构, 结合全局与局部寻优, 将PSO应用于软件测试, 大大提高测试效果; (2) 算法参数的改进. Shi和Eberhart在文献[9]中为PSO的公式引入了惯性参数, 详细分析了PSO速度公式的意义, 从而在求解不同问题时可通过调整惯性参数来调节算法收敛速度和全局搜索能力, 改善了算法的性能. 董红斌等在文献[10]中, 通过粒子最大适应值和最小适应值的指数函数来动态调整算法中的惯性权重, 有利于算法跳出局部最优. (3) 自适应PSO. 如Gong 和Zhang在文献[11]中提出了自适应拓扑结构的改进, 使算法在不同阶段自适应地调整拓扑结构, 显著地提升了算法的精度. 曹玉莲等在文献[12]中, 提出基于拟熵的自适应局部搜索策略, 融合具有高效收敛性的传统局部搜索策略, 提出混合自适应粒子群算法, 提高算法性能. (4) 多种群. Geng 和 Zhu在文献[13]中提出了使用3个种群协同搜索的算法, 其中一个种群按照PSO搜索, 第2个种群搜索最优位置附近, 而第3个种群用于增强多样性. Yan等在文献[14]中使用多个子种群, 并用一个种群来优化PSO的参数. Liang在文献[15]中介绍了一种动态多种群PSO算法(DMSPSO), 通过重组策略使粒子归属的种群动态变化, 增强了算法的性能. 胡成玉等在文献[16]中, 提出了基于斥力势场的多粒子群算法. 但是上述算法未明确定义种群关系和种群交互策略, 寻优能力有限, 并且未与其他主流粒子群改进算法进行对比. 曾辉等在文献[17]中, 将自适应与多种群结合, 提出自适应多种群粒子群搜索方法, 但是该方法未对种群关系进行定义, 文中探测与开采的平衡十分依赖于调参, 搜索速度与精度的平衡未在实验结果中明确说明.

本文从种群关系和斥力因子的角度出发, 提出一种新的多种群粒子群优化算法SRB-PSO (Swarm-Relation-Based PSO), 使用多个种群分别按照PSO算法独立地搜索, 依据种群粒子的适应值判定两个种群间的关系, 定义了“统治”、“对等”和“被统治”3种关系, 算法根据种群间关系自适应采取种群间影响策略: (1) 通过在对等种群间使用斥力因子来维持不同种群在不同区域搜索, 从而增强了搜索的多样性, 有助于跳出局部最优值, 避免过早收敛; (2) 通过使被统治种群向统治它的种群收敛, 相比单纯的多种群算法, 提高了搜索的效率, 加快了收敛速度. 由于每个种群在独立搜索时仍然依照PSO算法进行搜索, 其他针对各种场景下单种群PSO算法的改进方法可以直接应用在各个种群上, 因此SRB-PSO算法具有良好的可扩展性. 本文最后通过实验将SRB-PSO与全局版本PSO和局部版本PSO对比, 结果表明, SRB-PSO在求解多峰问题时性能最优, 且求解单峰问题时优于局部版本的PSO.

1 全局和局部粒子群优化算法 1.1 全局版本的PSO

粒子群优化算法使用一定数量的粒子在搜索空间中飞行, 每个粒子具有各自的速度, 并会记录各自的历史最优位置pbest以及整个种群的最优位置gbest. 每次迭代将计算粒子适应值, 更新最优位置, 然后按照式(1)更新粒子的速度, 并根据式(2)更新粒子的位置. 持续迭代直到满足终止条件, 终止条件可以是评估次数达到上限、迭代次数达到规定次数、最优解已满足需求. 算法的流程图如图1所示.

具体公式为:

$ \begin{split} {v_{id}} =& {v_{id}} + {c_1}\times{{rand{\rm{1}}}}()\times(pbes{t_{id}} - {x_{id}}) \\ & + {c_2}\times{{rand{\rm{2}}}}()\times(gbes{t_d} - {x_{id}}) \end{split} $

(1)

$ {x_{id}} = {x_{id}} + {v_{id}} $

(2)

式(1)是更新粒子速度的公式, $ {v}_{id} $ 表示粒子 ${i}$ 的速度在 ${d}$ 维的分量, $ {pbest}_{id} $ 表示粒子 ${i}$ 的历史最优位置的 ${d}$ 维坐标, $ {x}_{id} $ 表示粒子 ${i}$ 的当前位置的 ${d}$ 维坐标, $ {gbest}_{d} $ 表示群体最优位置的 ${d}$ 维坐标, $ {c}_{1} $ 、 $ {c}_{2} $ 是常数, ${r}{a}{n}{d}{\rm{1}}()$ 和 ${r}{a}{n}{d}{\rm{2}}()$ 是随机数函数, 产生0至1的随机数. 式中第2项体现了粒子根据自身经验对搜索状态的调整, 第3项体现了种群最优粒子对粒子搜索状态的引导. 式(2)表示依据速度更新粒子位置的公式.

算法通过设定最大速度来限定粒子的速度范围, 它限制粒子在空间飞行的最大速度. 如果最大速度太大, 粒子更容易越过最优解, 降低了算法的搜索精度, 如果最大速度太小, 粒子不能进行更广泛的探索, 容易陷入局部最优解. 通常最大速度是根据求解空间大小乘以常数系数设定的, 当粒子更新后的速度大小超过最大速度时, 速度大小被设定为最大速度. 此外, 式(2)得到的粒子的新位置可能会超出搜索空间, 当粒子位置在某维度上超出边界时, 粒子在该维度的坐标被置为边界值.

图 1 粒子群优化算法的流程

文献[6]中为粒子群优化的速度公式引入了新的参数w, 速度更新公式对应修改为式(3).

$\begin{split} {v_{id}} =& {\rm{ }}w\times {v_{id}} + {c_1}\times {{rand{\rm{1}}}}()\times (pbes{t_{id}} - {x_{id}}) \\ & + {c_2}\times {{rand{\rm{2}}}}()\times (gbes{t_d} - {x_{id}}) \\ \end{split} $

(3)

文献[6]中指出, 粒子群优化算法的速度公式既体现了搜索空间中更广泛的区域, 又体现了向已知较优区域收敛以获得最优值, 参数的选取体现了对这两方面的权衡. 不同问题对扩展搜索空间和收敛能力的权衡通常是不同的, 因此, 相比式(1), 式(3)引入了惯性参数 ${w}$ , 从而提供了更多的权衡空间, 通过选取恰当的参数 ${w}$ , 算法的性能将会大幅改善, 这一改进策略已被广泛使用.

1.2 局部版本的PSO

Eberhart和Kennedy在文献[6]中详细介绍并测试了两个版本的粒子群优化算法, 分别为全局版本和局部版本的PSO. 全局版本即前文所述的算法, 粒子的速度受自身经验的调整和群体最优粒子的引导; 而局部版本中粒子的速度则受自身经验的调整和拓扑邻域最优粒子的引导. 这两种版本的算法的区别在于, 粒子间信息交互的拓扑结构不同. 全局版本中, 所有粒子构成一个完全图, 因此每个粒子都能获悉整个种群所经过的最优位置并受其引导, 而在局部版本中, 粒子并不能获悉整个种群所经过的最优位置, 而只能获悉它的邻域粒子所经过的最优位置, 比如, 1个粒子只有2个邻居, 则所有粒子构成一个环形的拓扑结构.

从局部版本使用的拓扑结构分析, 每个粒子仅能获知其邻域粒子经过的最优位置, 因此多数粒子并不会很快向全种群最优位置收敛, 而是在不同区域进行了相对独立的搜索, 从而保持了粒子的多样性. 全局版本的PSO具有更快的收敛速度, 相比之下, 使用环形拓扑结构的局部版本PSO尽管收敛速度慢, 却拥有更强的全局搜索能力, 更加不易陷入局部最优解.

2 基于种群关系的SRB-PSO算法

尽管环形拓扑结构PSO相比传统PSO在全局搜索能力方面有了很大的改观, 但也存在着以下缺陷: 如果一些粒子在探索适应值很差的空间, 由于使用了环形拓扑结构, 粒子之间相对比较独立, 这些粒子在向好的区域收敛之前, 将在这个很差的空间进行大量的探索, 而这些探索是无意义的, 浪费了计算资源. 对于单峰问题, 环形拓扑结构使收敛速度慢了很多, 在相同计算量的情况下, 相比传统PSO, 算法的精度将会大幅下降; 此外, 环形拓扑结构带来的全局搜索能力增强也是有限的, 对很多带有大量局部最优的复杂多峰问题仍会陷入局部最优解.

针对以上缺陷, 本文提出了一种新的算法SRB-PSO, 使用多个种群, 分别按照PSO算法搜索, 并且在种群之间引入斥力因子, 从而使不同种群进行相对独立的搜索, 以获得更强的全局搜索能力, 同时使用一定的收敛机制, 以使算法的收敛速度得到保证. SRB-PSO算法的流程图如图2所示. 下文将分别就各关键操作进行详细介绍与分析, 最后给出整体的流程综述.

图 2 引入斥力因子的多种群PSO流程图

2.1 初始化种群

SRB-PSO中使用多个种群, 令不同种群进行相对独立的搜索. 如使用n个种群进行搜索, 通过将求解空间的随机某个维度等分为n段, 从而对应将求解空间划分为n个子空间, 在每个子空间中分别初始化一个种群. 这样的设定使不同种群从初始化时开始, 就具有很强的独立性.

2.2 SRB-PSO的4个阶段

SRB-PSO的种群间交互是影响算法性能的重要因素. 在算法的不同阶段有不同的需求, 种群间影响的施加频率是不同的. 在算法的前中期, 每个种群比较独立地进行搜索, 从而种群间的影响是不施加的或是低频施加的; 在算法中后期, 种群之间的交互将被高频施加, 以通过种群间的交互取得更好的结果; 在算法末期, 所有种群合并为一个种群收敛, 以提高算法的精度. 算法据此分为4个阶段, 分别为: 独立搜索期、弱影响期、强影响期和收敛期.

(1) 独立搜索期: 应用于算法运行的初期, 在这个阶段, 各个种群进行完全独立的搜索, 即各个种群的粒子都依据自身经过的最优位置、本种群经过的最优位置, 来调整自己的速度, 不同种群之间在这个阶段没有任何的交互, 即任何一个种群都觉察不到其他种群的存在, 而是各自按照传统PSO进行搜索. 由于各个种群初始化在求解空间的不同子空间, 因此各个种群之间的搜索具有很强的独立性, 具有较强的全局搜索能力. 这个阶段结束后, 每个种群都会获得初步的搜索结果.

(2) 弱影响期: 这个阶段种群间的影响在算法迭代中被间歇地施加, 依据不同种群的求解现状, 引入外种群的影响来帮助种群进化. 每隔一定的迭代次数, 就会依据当前各个种群的搜索状态, 对每个种群施加来自外种群的影响, 具体操作是该种群的每个粒子的速度会受到外种群粒子的影响. 影响策略共有3种, 分别是: 向外种群收敛、受到外种群排斥和不受外种群影响, 这些策略的设定是基于收敛速度和全局搜索两方面考虑的, 具体的策略选择在下文将被详细介绍. 值得强调的是, 在弱影响期, 种群间的影响是被间歇地施加的, 在两次施加之间, 种群的搜索行为仍然是完全独立的.

(3) 强影响期: 在算法运行的中后期, 种群间的影响将被施加到每次迭代. 在这个阶段, 一个种群的粒子在每次迭代中, 都同时受到所属种群和其他种群的影响, 具体影响策略与弱影响期相同, 区别在于每次迭代都施加种群间影响.

(4) 收敛期: 在算法运行的末期, 所有种群通过合并, 形成一个种群, 执行单种群的搜索算法, 综合之前所有的结果, 最终使得算法逐渐收敛, 得到最优结果.

2.3 种群间影响策略

在算法的弱影响期和强影响期, 种群之间通过交互从而提高搜索性能. 但最优种群, 即历史最优位置所在的种群, 并不会受到其他种群的影响, 因为通常其他种群的影响会对最优种群产生干扰, 影响最优种群的收敛速度.

施加某个种群受到的外种群的影响时, 首先会评估该种群与外种群的相对关系, 以使用不同的影响策略. 影响策略的伪代码如算法1所示. 在这个算法中, 种群与外种群的相对关系被定义为3种: 统治、对等和被统治. 评估基于两个参量, average-fitness与gbest-fitness, 前者是种群所有粒子的当前适应值的平均值, 后者则是该种群的历史最优适应值. 评估规则如表1所示.

算法1. 种群间影响策略伪代码

开始

对于种群A中的每个粒子 $\scriptstyle {{{i}}}$ :

if A的搜索最优值 $\scriptstyle {gbest_{{{A}}}}$ 与平均值 $\scriptstyle {average_{{{A}}}}$ 均优于种群B的 $\scriptstyle {gbest_{{B}}}$ 与 $\scriptstyle {average_{{{B}}}}$ , then

do nothing

else if B的搜索最优值 $\scriptstyle {gbest_{{{B}}}}$ 与平均值 $\scriptstyle {average_{{{B}}}}$ 均优于A的 $\scriptstyle {gbest_{{{A}}}}$ 与 $\scriptstyle {average_{{{A}}}}$ , then

$\scriptstyle {gbest_{{{A}}}}={gbest_{{{B}}}}$

$\scriptstyle {pbest_{{{A}}}}_{i}={pbest_{{{B}}}}_{i}$

else

根据式(4)更新速度

结束

表 1 种群间关系评估表

根据评估规则, 种群间的3种关系定义如下: 种群统治外种群, 当且仅当种群的average-fitness与gbest-fitness均优于外种群; 种群与外种群对等, 当且仅当种群的average-fitness与gbest-fitness中, 一项优于外种群而另一项差于外种群; 种群被外种群统治, 当且仅当种群的average-fitness与gbest-fitness都比外种群差. 确认了种群与外种群的关系后, 依据关系分别施加以下策略:

(1) 种群统治外种群, 则该种群不受外种群影响. 当种群统治外种群时, 认为该种群正探索的区域远好于外种群的区域, 因此不会受到外种群的影响.

(2) 种群与外种群对等, 则该种群的粒子受到外种群gbest位置的排斥, 且这个斥力反比于粒子与外种群gbest的距离, 以A、B分别表示种群与外种群, i表示粒子, d表示维度, 种群粒子的速度公式变更为式(4).

$ \begin{split} {v_{Aid}} =& {\rm{ }}w\times {v_{Aid}} + {c_1}\times {{rand{\rm{1}}}}()\times (pbes{t_{Aid}} - {x_{Aid}}) \\ & + {c_2}\times {{rand{\rm{2}}}}()\times (gbes{t_{Ad}} - {x_{Aid}}){\rm{ }} \\ & - {c_3}/(gbes{t_{Bd}} - {x_{Aid}})\times {{Decreasing}} () \end{split} $

(4)

${c}_{\rm{3}}$ 是算法引入的新参数—斥力因子, 它影响种群间斥力的大小, ${{Decreasing}} ()$ 是一个二次衰减函数, 随迭代次数增加由1衰减至0. 这种策略的意义在于, 当种群与外种群具有相仿的搜索结果时, 种群的粒子将受到外种群的斥力, 且斥力大小反比于粒子与外种群gbest位置的距离, 从而保持与外种群在相对独立的区域搜索, 增强算法的全局搜索能力, 避免所有种群都向某个局部最优收敛. 衰减函数的引入使种群间斥力在算法前中期时很大, 作用明显, 随迭代次数增加其作用逐渐减弱, 以使不同种群在进行独立搜索的同时兼顾收敛性能. 此外, 施加种群间影响后, 算法检查新的速度大小是否超出最大速度, 如果超出, 则将速度大小置为最大速度, 从而保证搜索的精度.

(3) 种群被外种群统治, 则该种群放弃当前的搜索区域, 向外种群收敛. 具体的实现是将每个粒子的 ${pbest}$ 位置依次对应改为外种群每个粒子的 ${pbest}$ 位置, 将该种群的 ${gbest}$ 位置改为外种群的 ${gbest}$ 位置.

当种群被外种群统治时, 认为种群正搜索的空间明显差于外种群正搜索的空间, 因此放弃种群正搜索的区域, 向外种群区域转移. 这个策略节约了搜索资源, 可以提高算法的收敛速度.

2.4 算法综述

算法使用多个种群, 在解空间的等分子空间进行分别初始化. 首先在独立搜索期, 每个种群进行完全独立的搜索. 接着在弱影响期和强影响期, 种群将被施加外种群间的影响, 算法定义了统治、对等、被统治3种种群间关系. 被统治的种群将放弃当前搜索区域, 转而向统治它的种群收敛; 对等的种群则会互相产生斥力, 从而保持在相对独立的空间搜索. 但最优种群并不会受到外种群的影响, 以避免其他种群干扰最优种群的收敛, 同时可以避免这种情况: 两个种群都围绕着最优解收敛却因互斥都无法进一步靠近最优解. 斥力将随迭代次数增加而减弱, 且在算法末期所有粒子将被整合为一个种群, 这样的操作大大提高了算法的收敛速度. 接下来本文将通过实验测试算法性能.

3 实验分析 3.1 测试函数与参数设定

为验证性能, 将SRB-PSO与全局版本以及局部版本的PSO进行对比. 实验使用文献[4]中的12个测试函数, 如表2所示, 函数维度D取30. 其中f₁至f₄是单峰函数, f₅是阶梯函数, f₆是带噪音的四次函数, f₇至f₁₂是有大量局部最优解的多峰函数. 将评估次数设定为300 000, 分别使用3种算法对这13个测试函数求最小值, 每个算法独立运行30次, 记录并对比30次运行的最优结果、平均结果与方差.

为确保比较的公平性, 3种算法使用的基本参数相同, 分别为: 惯性参数w=0.55, c₁=c₂=2, 速度上限为解空间一维长度的0.04倍. 全局版本与局部版本的PSO种群规模均为60, 迭代5000次. 新算法总粒子数也为60, 迭代5000次, 但使用5个种群, 每个种群的规模为12, 此外, 如前文所述, SRB-PSO在此基础上引入了种群关系和斥力因子, 分为4个执行阶段, 实验中取斥力因子c₃=0.001, 前1000次迭代为独立搜索期, 第1001–3000次迭代为弱影响期, 弱影响期内每50次迭代施加一次种群间影响, 第3001–4500次迭代为强影响期, 最后500次迭代为收敛期.

表 2 测试函数

测试函数	定义域	最小值	名称
${f_2}(x) = \displaystyle\sum\nolimits_{i = 1}^D {\|{x_i}\|} + \prod\nolimits_{i = 1}^D {\|{x_i}\|} $	[−10, 10]^D	0	Schwefel 2.22
${f_3}(x) = {\displaystyle\sum\nolimits_{i = 1}^D {\left( {\displaystyle\sum\nolimits_{i = 1}^i { {x_i} } } \right)} ^2}$	[−100, 100]^D	0	Schwefel 1.2
${f_4}(x) = {\max _i}(\|{x_i}\|,1 \le i \le D)$	[−100, 100]^D	0	Schwefel 2.21
${f_5}(x) = \displaystyle\sum\nolimits_{i = 1}^{D - 1} {\left[ {100{{\left( {{x_{i + 1}} - {x_i}^2} \right)}^2} + {{({x_i} - 1)}^2}} \right]}$	[−30, 30]^D	0	Rosenbrock
${f_6}(x) = \displaystyle\sum\nolimits_{i = 1}^D {(\left\lfloor {{x_i} + 0.5} \right\rfloor } {)^2}$	[−100, 100]^D	0	Step
${f_7}(x) = \displaystyle\sum\nolimits_{i = 1}^D {i{x^4} + random[0,1)} $	[−1.28,1.28]^D	0	Noise
${f_8}(x) = \displaystyle\sum\nolimits_{i = 1}^D { - {x_i}\sin (\sqrt {{x_i}} )} $	[−500, 500]^D	−12569.5	Schwefel 2.26
${f_9}(x) = \displaystyle\sum\nolimits_{i = 1}^D {\left[ {{x_i}^2 - 10\cos (2\pi {x_i}) + 10} \right]}$	[−5.12, 5.12]^D	0	Rastrigin
$\begin{array}{*{20}{l} }{ {f_{10} }(x) = - 20\exp \left( { - 0.2\sqrt {1/D\displaystyle\sum\nolimits_{i = 1}^D { {x_i}^2} } } \right)}\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{ - \exp \left( {1/D\displaystyle\sum\nolimits_{i = 1}^D {\cos 2\pi {x_i} } } \right) + 20 + e}\end{array}$	[−32, 32]^D	0	Ackley
${f_{11}}(x) = 1/4000\displaystyle\sum\nolimits_{i = 1}^D {{x_i}^2} - \prod\nolimits_{i = 1}^D {\cos ({x_i}/\sqrt i )} + 1$	[−600, 600]^D	0	Griewank
$\begin{array}{*{20}{l} }{ {f_{12} }(x) = \dfrac{\pi }{D}\left\{ {10{ {\sin }^2}(\pi {y_1}) + \displaystyle\sum\nolimits_{i = 1}^{D - 1} { { {({y_i} - 1)}^2}[1 + 10{ {\sin }^2}(\pi {y_{i + 1} })]} } \right.}\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\left. { + { {({y_D} - 1)}^2} } \right\} + \displaystyle\sum\nolimits_{i = 1}^D {u({x_i},a,k,m)} }\end{array}$	[−50, 50]^D	0	Generalized Penalized Function
$\begin{array}{*{20}{l} }{ {f_{13} }(x) = \dfrac{1}{ {10} }\left\{ { { {\sin }^2}(3\pi {x_1}) + \displaystyle\sum\nolimits_{i = 1}^{D - 1} { { {({x_i} - 1)}^2}[1 + { {\sin }^2}(3\pi {x_{i + 1} })]} } \right.}\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\left. { + { {({x_D} - 1)}^2}\left[ {1 + { {\sin }^2}(2\pi {x_D})} \right]} \right\} + \displaystyle\sum\nolimits_{i = 1}^D {u({x_i},a,k,m)} }\end{array}$	[−50, 50]^D	0	Generalized Penalized Function

表 2 测试函数

3.2 测试结果与分析

算法每次运行后计算算法所得最小值与函数理论最小值的误差, 针对每个测试函数, 统计30次运行的平均误差、最小误差、方差. 小的平均值意味着算法的求解精度更高, 稳定性更好, 小的方差进一步体现了算法的稳定性. 结果在表3中列出, 加粗表明该算法的该项结果是3种算法中最优的, 斜体表示该算法的该项结果强于另两种算法中的一种.

表 3 3种算法的平均值、最佳值与方差结果

函数	PSO			LPSO			SRB-PSO
函数	平均	最佳	方差	平均	最佳	方差	平均	最佳	方差
f₁	2.07E−40	1.04E−44	4.79E−79	2.73E−18	2.32E−19	4.80E−36	3.99E−21	2.28E−26	1.61E−40
f₂	1.76E−03	1.75E−04	3.06E−06	2.09E+00	7.84E−01	6.61E−01	1.19E−01	1.27E−02	8.67E−03
f₃	1.09E−02	1.70E−03	4.18E−05	5.84E−01	3.86E−01	1.55E−02	1.65E−01	5.45E−02	8.09E−03
f₄	3.51E+01	1.11E+01	5.88E+02	1.56E+01	1.33E−01	4.91E+01	1.64E+01	6.86E+00	2.71E+01
f₅	0.00E+00	0.00E+00	0.00E+00	0.00E+00	0.00E+00	0.00E+00	0.00E+00	0.00E+00	0.00E+00
f₆	1.33E−03	7.81E−04	1.52E−07	4.42E−03	2.64E−03	1.23E−06	1.45E−03	3.48E−04	3.93E−07
f₇	6.15E+03	4.54E+03	5.65E+05	4.95E+03	3.52E+03	4.03E+05	4.80E+03	3.34E+03	2.70E+05
f₈	3.23E+01	1.99E+01	9.28E+01	4.06E+01	2.49E+01	6.44E+01	2.82E+01	1.69E+01	3.27E+01
f₉	7.67E−15	4.00E−15	2.16E−30	4.45E−14	2.18E−14	2.58E−28	1.42E−14	7.55E−15	1.54E−29
f₁₀	9.19E−03	0.00E+00	1.20E−04	0.00E+00	0.00E+00	0.00E+00	9.04E−04	0.00E+00	8.16E−06
f₁₁	8.30E−02	1.57E−32	2.41E−02	1.73E−28	3.84E−30	8.81E−56	7.06E−32	1.57E−32	5.89E−62
f₁₂	2.56E−03	1.35E−32	2.23E−05	2.77E−27	9.99E−29	1.24E−53	3.70E−32	1.35E−32	9.22E−64

表 3 3种算法的平均值、最佳值与方差结果

算法对f₁至f₆的结果体现算法对单峰问题的求解性能, 对f₇至f₁₂的结果体现算法对多峰问题的求解性能. 表3结果表明, 传统PSO在求解单峰问题时性能最优, SRB-PSO在求解多峰问题时性能最优. 为进一步分析实验结果, 针对每个函数的实验结果作箱线图, 箱线图能够更直观地表现算法的精度和稳定性. 首先分析3种算法对单峰问题的求解性能, 3种算法求解f₁至f₆的结果在图3中以箱线图表示.

图3表明, 对于单峰问题, 3种算法中, 传统的全局版本PSO有最优的精度和稳定性, 这与理论分析是一致的, 因为局部版本的PSO和新算法都一定程度上牺牲了收敛速度来提升全局搜索能力. 还可以发现, 新算法的精度与稳定性明显强于局部版本的PSO. 这表明新算法比局部版本的PSO拥有更强的对单峰问题的优化能力. 其中误差范围表示算法的稳定性, 可以看出新算法误差范围在大多数测试案例中都表现出了更高的稳定性, 而对于多峰问题, 考虑表3结果中的f₇至f₁₂, 传统全局PSO的性能显然落后于局部版本PSO和新算法. 对于多峰问题求解的实验结果在图4中进一步以箱线图表示.

图 3 3种算法求解单峰问题结果的箱线图

图 4 3种算法求解多峰问题结果的箱线图

图4表明, 相比传统PSO, 新算法与局部版本的PSO对多峰问题都有很高的求解精度和稳定性. 表3数据显示, 新算法在f₈, f₉, f₁₀, f₁₂, f₁₃上的性能都优于局部版本PSO, 仅在f₁₁上稍有落后. 综合来看, 新算法对于多峰问题的求解性能最优. 同时新算法在问题求解的稳定性上, 在所有案例当中都最高, 可以看出新算法对于多峰问题求解有非常好的稳定性.

以上实验结果可总结为: 传统PSO对求解单峰问题有最优的性能, 但在求解多峰问题时误差较大; 局部版本的PSO求解单峰问题的精度最差, 但求解多峰问题的性能较强; 新算法求解多峰问题的性能最优, 且新算法求解单峰问题的性能明显优于局部版本的PSO.

4 结论与展望

粒子群优化算法是一种操作简单、收敛速度快的智能优化算法, 通过对算法进行一定的改进, 可以提高算法在求解多峰问题时的性能. 本文提出一种多种群粒子群优化算法SRB-PSO, 并引入斥力因子来保证不同种群的个体之间搜索全局最优解时的相对独立性, 从而加强了算法中期的全局搜索能力. 文章通过实验对算法性能进行了系统性地对比与分析. 实验结果表明, 相对于全局版本以及局部版本的粒子群优化算法而言, 本文提出的多种群粒子群优化算法在解决多峰问题时具有更高的求解精度. 因此算法在全局搜索能力上优于传统的粒子群优化算法.

参考文献

[1]	Kennedy J, Eberhart R. Particle swarm optimization. IEEE International Conference on Neural Networks. Perth: IEEE, 1995. 1942–1948.
[2]	徐艳蕾, 朱炽阳, 李陈孝, 等. 基于颜色系数反向粒子群模型的田间作物分割方法. 农业工程学报, 2018, 34(3): 173-179. DOI:10.11975/j.issn.1002-6819.2018.03.023
[3]	唐佳, 王丹, 贾宏杰, 等. 基于元模型辅助粒子群算法的主动配电网最优经济运行. 电力系统自动化, 2018, 42(4): 95-103. DOI:10.7500/AEPS20170630006
[4]	杨帆, 周丽红. 基于改进粒子群优化的四杆机构运动轨迹误差研究. 组合机床与自动化加工技术, 2018(2): 5-8.
[5]	安宗权, 王匀. 基于改进粒子群算法的车辆被动悬架优化与仿真研究. 现代制造工程, 2018(1): 63-68.
[6]	Eberhart R, Kennedy J. A new optimizer using particle swarm theory. Proceedings of the Sixth International Symposium on Micro Machine and Human Science. Nagoya: IEEE, 1995. 39–43.
[7]	靳雁霞, 张鑫, 薛丹. 具有自适应逃逸的环状全互连结构粒子群算法. 微电子学与计算机, 2018, 35(2): 1-5, 10.
[8]	焦重阳, 周清雷, 张文宁. 混合拓扑结构的粒子群算法及其在测试数据生成中的应用研究. 计算机科学, 2017, 44(12): 249-254. DOI:10.11896/j.issn.1002-137X.2017.12.045
[9]	Shi Y, Eberhart R. A modified particle swarm optimizer. The 1998 IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence. Anchorage: IEEE, 1998. 69–73.
[10]	董红斌, 李冬锦, 张小平. 一种动态调整惯性权重的粒子群优化算法. 计算机科学, 2018, 45(2): 98-102. DOI:10.11896/j.issn.1002-137X.2018.02.017
[11]	Gong YJ, Zhang J. Small-world particle swarm optimization with topology adaptation. Proceeding of the Fifteenth Annual Conference on Genetic and Evolutionary Computation. Lille: Association for Computing Machinery, 2013. 25–32. [doi: 10.1145/2463372.2463381]
[12]	曹玉莲, 李文锋, 张煜. 基于拟熵自适应启动局部搜索策略的混合粒子群算法. 电子学报, 2018, 46(1): 110-117. DOI:10.3969/j.issn.0372-2112.2018.01.016
[13]	Geng ZQ, Zhu QX. Multi-swarm PSO and its application in operational optimization of ethylene cracking furnace. 7th World Congress on Intelligent Control and Automation. Chongqing: IEEE, 2008. 103–106.
[14]	Yan YY, Hu YY, Guo BL. Parameters-optimized multi-subswarms particle swarm optimization. 2011 International Conference of Soft Computing and Pattern Recognition (SoCPaR). Dalian: IEEE, 2011. 301–305.
[15]	Liang JJ, Suganthan PN. Dynamic multi-swarm particle swarm optimizer. Proceedings 2005 IEEE Swarm Intelligence Symposium. Pasadena: IEEE, 2005. 124–129.
[16]	胡成玉, 吴湘宁, 王永骥. 斥力势场下的多粒子群协同动态优化算法及其应用. 小型微型计算机系统, 2011, 32(7): 1325-1330.
[17]	曾辉, 王倩, 夏学文, 等. 基于自适应多种群的粒子群优化算法. 计算机工程与应用, 2018, 54(10): 59-65. DOI:10.3778/j.issn.1002-8331.1711-0048