当代学生稿件信息
新型PSO-ABC混合算法在高维问题中的应用
田苗, 王斌,朱伟玺
(1.上海大学管理学院, 上海 201800；
2.上海复兴科技有限公司, 上海 201800；
3.华能澜沧江水电股份有限公司, 云南昆明 650200)
摘要：针对现实中的高维复杂约束优化问题，本文充分结合改进粒子群和人工蜂群算法的优点，提出了一种新型混合优化算法。首先，从三个方面对传统粒子群进行性能改进：(1)引进禁忌表运行模式；(2)加入领域随机化机制；(3)采用轮盘赌迭代原则。然后，提出新型混合优化算法，该算法采用改进 PSO高效的有序搜索方式迭代确定初始蜜源，由探索蜂带领对应数量的跟随蜂，在蜜源附近的领域内，按照改进 PSO的有序搜索方式寻找新的蜜源，根据新蜜源的适应度更新蜜源。最后，利用四个标准测试函数仿真显示： 新型混合优化算法能有效改善寻优性能，更加有效地处理复杂高维问题。
关键词：改进PSO-ABC；人工蜂群；改进粒子群；高维优化
中图分类号：TP301 文献标志码：A
0. 引言
复杂约束优化问题在实际工程应用中是一大难题[1]，此类问题本质上即为对带有约束条件的函数进行优化求解。但这些函数是典型的复杂函数，通常具有高维、大规模、非线性及不可微等特征。在目前的研究中，经典优化方法和智能优化算法是求解此类约束优化问题的主要方法。经典优化方法获得的解大多为局部最优解，求解的结果通常受初值设置影响，且需要梯度信息。而智能优化算法不仅搜索效率高、鲁棒性强，且能以较大概率搜索到全局最优解，相比之下，智能优化算法是求解复杂约束优化问题的更好选择。其中，人工蜂群优化算法( artificial bee colony，简称ABC)和粒子群优化( particle swarm optimizer，简称PSO)算法是常用的群体智能优化算法，在求解全局优化问题方面表现出明显的优势[2-5]。
近年来，也有一些学者融合PSO和ABC算法的优势形成混合优化算法，如：文献[6]提出的混合优化算法，即在粒子群算法的迭代过程中，采用蜂群算法在优秀解领域内进一步进行随机搜索，然后更新蜜源，并返回PSO算法。文献[7]提出的PSOABC混合优化算法，将总体划分为两个子种群，其中之一采用PSO算法进化而来，另一个子种群采用ABC算法进化而来，利用信息共享机制实现双种群协同进化。可以发现，这几种PSO与ABC的混合算法虽在一定程度上提升了算法的性能，但由于其搜索方式的随机性，随着维度的不断增加，搜索领域的不断扩大，寻优能力急剧下降，因此不适用于高维问题。
针对现实中无法尽快收敛，寻得最优解的高维问题，因而本文提出了一种新型PSO-ABC混合优化算法，与上述混合算法主要不同的点是：(1)首先从三个方面对PSO算法进行改进，再结合ABC算法的优点提出混合算法，对比基于传统PSO算法的混合算法，整体性能更优； (2)改进PSO和ABC的结合具有层次性和全局性，在算法进行寻优和不断迭代的整体过程中，不仅具有PSO算法高效的全局搜索能力，同时具有ABC算法的全局收敛特点，发挥了PSO的群体效应和ABC的个体特性。从而，从本质上大大提升了混合算法的性能。
1.ABC算法
ABC算法中，人工蜂群包含3种类型，分别称为探索蜂、跟随蜂和侦察蜂发，蜂群在解空间内采用随机搜索方式寻找蜜源，每个蜜源的位置即代表所求解问题的一个潜在解，同时，每个蜜源只能对应一只引领蜂进行搜索。
对于全局优化问题，令：
(1)
设搜索空间为D维，
表示第i个蜜源所在的空间位置。
ABC算法的具体步骤[8-9]如下：
初始化蜜源，根据公式(2)产生M个点作为蜜源初始位置
，并设
为算法的最大允许迭代次数，limit为算法限定的可循环次数。
(2)
其中，
、
分别表示变量的下限和上限，随机数
[0,1]。
每个蜜源
对应一只引领蜂，根据公式(3)在原蜜源周围搜索寻找新的蜜源，设产生的新蜜源为
。
(3)
其中，并且
，
；随机数
[-1,1]。
计算
的适应度值，根据贪婪选择原则，选择适应度高的蜜源。
根据公式(4)，计算可得引领蜂搜索的新蜜源被跟随蜂选择为搜索对象的概率。
(4)
其中，
表示第
个蜜源的适应度值，
表示蜜源的个数。
跟随蜂继续按照引领蜂的搜索方式，在蜜源周围寻找新的蜜源，并根据贪婪选择原则，保留适应值更优的蜜源。
判断蜜源
是否满足被放弃的条件。如果
，选择放弃第i个蜜源，并且对应于此蜜源的探索蜂全部将变为侦查蜂。
侦查蜂将在搜索空间内随机生成一个新位置以更新原蜜源信息。
判断算法是否满足迭代终止条件，计算迭代总次数
，若
成立，则迭代结束，并记录保留的最佳蜜源位置，否则返回
。
2.改进PSO算法
2.1 传统PSO算法
传统PSO算法[10]：在拥有
个搜索粒子的N维目标搜索空间中，设第
个搜索粒子所处的位置表示为
，速度表示为
，每个搜索粒子根据迭代原则寻找最优解，且在迭代过程中，搜索粒子参考两个“极值”来更新自己的速度和位置，一个称为个体极值，设为
，代表搜索粒子本身在限定搜索时间内所寻得的最优解；另一个极值称为整个领域的最优极值，设为
，代表该搜索粒子所在的领域内所有粒子在限定时间内所寻得的最优解。根据以下式(5)(6)(7)，更新第
个搜索粒子的速度和位置信息：
(5)
(6)
(7)
式中
表示[0,1]之间的随机数，
和
被称为学习因子，其设置对算法中搜索粒子向全局最优粒子和个体最优的粒子方向飞行的最大步长具有重要调节作用，若设置合理，不仅可以提高算法收敛性，而且可以避免算法陷入局部最优解。
表示算法设定的粒子在每一维搜索时的最大速度限制。其值设置的合理性对算法有重要影响，当
较小时，保证了粒子群优化算法的局部搜索能力，当
较大时，保证了粒子种群高效率的全局搜索能力。
、
分别表示惯性权重的初始值和终值，
表示算法设定的最大允许迭代次数，
表示当前的累计迭代次数。
2.2 PSO改进策略
基于传统PSO原理介绍，可知PSO算法有很多优点[11]，如具有很强的全局搜索速度能力，当局部最优解较少时，可行域能快速收敛等。但也存在不足之处，如在搜索过程中，粒子之间的依赖性强，易陷入局部最优解，进化后期的搜索效率低。
鉴于PSO算法的不足，提出以下三个方面的性能改进策略：
（1）引进禁忌表运行模式。此模式描述为：若某个粒子迭代多次后，却没有发生位置的变化，此时对于寻找更优解已失去意义，便放弃该粒子，并将其信息记录在禁忌表中。然后用一个随机生成粒子替代已放弃的粒子，进行下一步寻优。进而避免了陷入局部最优解。
（2）加入领域随机化机制。当求解高维问题时，几乎无法直接寻找粒子所在区域的局部最优解，优化性能急剧下降。针对该问题，随机的选择随机数量的粒子组合为一个小领域，从而将该领域随机化。然后从随机组合的小领域中找出最优秀解，继续下一步迭代，如此，极大地提高了寻优效率。
（3）采用轮盘赌迭代原则。即在算法迭代的过程中，从整体样本中选出一定比例的优秀粒子时，采用轮盘赌原则进行选择。如此，较优秀的粒子被选择的概率也会相应增大，进而改进了算法的收敛性能。
改进的PSO算法的详细流程图见图1。
图1 改进的PSO算法的流程图
3. 改进PSO-ABC算法设计
高维复杂优化问题即超过100维度的函数优化问题，问题的复杂程度随搜索空间维数的不断扩大而呈指数级增长，需要耗费大量的计算代价，一般方法难以有效解决。其中，粒子群优化算法虽前期具有高效的全局搜索能力，但其后期的寻优效果大大下降，随着维度的增加，其缺陷表现越突出，因此不适用于高维问题的求解；人工蜂群算法由于其前期随机的搜索方式，在高维问题下寻优时存在高度的盲目性，因此也不适用。为此，如何利用有限的粒子群体，最大化提升粒子个体的寻优能力，是求解高维问题的关键。
基于上述分析，充分结合改进PSO算法的群体效应和ABC算法的个体特性，得改进PSO-ABC混合优化算法的核心思想：首先，采用改进PSO高效的有序搜索方式，迭代一定次数后得若干优秀粒子，作为初始蜜源；然后，为每个蜜源分配一个探索蜂，并根据蜜源的质量确定所需的跟随蜂数量，由探索蜂带领对应数量的跟随蜂，在蜜源所在的领域内，按照改进PSO的有序搜索方式寻找新的蜜源信息；最后，对新蜜源的适应度进行评价，并根据贪婪选择原则对蜜源位置进行更新。其中，如果搜索次数已经到达设定的最大限制搜索次数limit后，仍然没有搜索到更优的蜜源信息，便将该蜜源舍弃，其信息存储在禁忌表中，同时该蜜源领域内的原探索蜂变为侦查蜂，并由侦查蜂以随机搜索方式，生成一个空间点作为新蜜源的位置。如此循环，直到满足迭代终止条件。
改进PSO-ABC新型混合优化算法的详细步骤如下：
参数设定：分别设置群体规模N，最大迭代次数
，限定的循环次数limit，学习因子
和
，惯性权重的初始值
和终值
。
初始化种群：设定探索蜂、跟随蜂和侦察蜂的数量，并根据公式(2)构建M个初始种群
。
确立初始蜜源：采用改进PSO算法高效的全局搜索方式，迭代一定次数后得若干优秀解
，作为初始蜜源。
跟随：根据式(8)确定蜜源
所需的跟随蜂的个数。
(8)
其中，
表示第
个蜜源的适应度评价值，N表示蜜源的个数，
表示总跟随蜂个数。
局部搜索：引领蜂带领确定数量的跟随蜂，在各个蜜源
对应的领域内，按照改进PSO的有序搜索方式寻找新的蜜源。
蜜源更新：分别计算新蜜源与当前蜜源的适应度值，并按照贪婪选择原则，选择适应度值更优的蜜源。
蜜源淘汰：判断蜜源
是否满足被放弃的条件。按照式(9)计算第i个蜜源的历史搜索次数，若
，则舍弃第i个蜜源，并且第i个蜜源附近的探索蜂变为侦查蜂。
(9)
其中，
代表该蜜源附近探索蜂的个数，
代表小粒子群的迭代次数。
蜜源更新：侦查蜂将在定义的解空间内，通过随机搜索方式产生一个新位置，对原蜜源进行更新。
终止条件判断：计算迭代总次数，若满足
，则迭代结束，并记录保留的最佳蜜源位置，否则返回
。
改进PSO-ABC混合优化算法的详细流程图见图2。
图2 混合优化算法的流程图
4. 算法性能测试分析
为了测试新型混合算法的运行效率，利用四个标准的测试函数[12-15]，对改进PSO-ABC混合算法与ABC算法和改进的PSO算法分别进行仿真实验，并对各实验结果进行对比分析。
Sphere函数是一个连续、对称的球面单峰函数，由于其易于寻找全局最优解，一般用于测试算法的寻优精度。Rosenbrock函数是一个典型的复杂优化问题的函数，由于变量之间具有较大的干扰性，搜索的信息较少，几乎找不到全局最优点。一般而言，该函数主要用于测试算法的执行能力和收敛速度。Rastrigin函数是复杂的非线性多峰函数，其众多局部极值点的存在，使算法很难搜索到全局最优解，因此该函数在测试算法避免局部最优的能力方面非常有效。Griewank函数是一个非线性的复杂多模态函数，由于存在大量的局部极小点，很难搜索到全局最优解。可用于测试算法的全局寻优能力和避免早熟的能力。
四个测试函数的详细信息见表1。
表1 四个标准的测试函数
|
函数 |
函数表达式 |
搜索空间 |
理论全局最优解 |
|
Sphere |
|
[-100,100] |
0 |
|
Rosenbrock |
|
[-100,100] |
0 |
|
Rastrigin |
|
[-100,100] |
0 |
|
Griewank |
|
[-100,100] |
0 |
在相同迭代次数下，通过对比四个测试函数适应度值的仿真结果，对三种算法的性能进行评价，其中平均适应度值和方差适应度值主要用于算法的寻优精度和鲁棒性评价。
算法参数设置如下： ABC算法中，蜜蜂数量分别设为跟随蜂50只、探索蜂10只和引领蜂3只，迭代次数为4000次。在改进PSO-ABC算法中，前期PSO粒子种群规模为100，最大允许迭代次数为2000，
，惯性权重
，后期PSO-ABC算法中，跟随蜂50只、探索蜂10只和引领蜂3只，最大迭代次数为2000次。不同维度函数测试下，维数分别设置为50、100、1000。
为避免随机性对测试结果的影响，每个算法都独立进行10次仿真实验，并分析它们的统计特征，计算得到各测试函数在不同维度下的各适应度值如表2、3、4所示，其中1000维下函数的进化代数曲线如图3—图6所示。
表2 测试函数的仿真结果比较 (50维)
|
函数 |
算法 |
平均值 |
方差 |
最优值 |
最差值 |
|
|
ABC |
0.0473 |
2.5222e-05 |
0.0379 |
0.0525 |
|
改进PSO |
1.3478e+02 |
6.7068e+01 |
1.2322e+02 |
1.4644e+02 |
|
|
改进PSO-ABC |
0.0356 |
1.1517e-06 |
0.0344 |
0.0377 |
|
|
|
ABC |
1.9494e+03 |
5.7071e+02 |
1.9133e+03 |
1.9869e+03 |
|
改进PSO |
1.0861e+05 |
4.0740e+08 |
6.6425e+04 |
1.2639e+05 |
|
|
改进PSO-ABC |
1.7421e+03 |
1.2052e+04 |
1.5684e+03 |
1.9294e+03 |
|
|
|
ABC |
1.1352e+04 |
1.6713e+05 |
1.0899e+04 |
1.2024e+04 |
|
改进PSO |
5.2500e+02 |
2.5765e+03 |
4.3151e+02 |
5.8723e+02 |
|
|
改进PSO-ABC |
2.4942e+02 |
1.3180e+03 |
1.9810e+02 |
3.1106e+02 |
|
|
|
ABC |
1.7269 |
0.1175 |
0.9686 |
1.9405 |
|
改进PSO |
1.1090 |
0.0284 |
1.0289 |
1.4856 |
|
|
改进PSO-ABC |
0.3368 |
0.0085 |
0.1317 |
0.3928 |
表3 测试函数的仿真结果比较 (100维)
|
函数 |
算法 |
平均值 |
方差 |
|
