交互学习的粒子群优化算法

秦全德，李丽，程适，李荣钧

(1.深圳大学管理学院，广东 深圳518060;2.英利利物浦大学电气电子工程系，英国利物浦L69 3GJ;3.西交利物浦大学电气电子工程系，江苏苏州215123;4.华南理工大学工商管理学院，广东广州510640)

粒子群优化(particle swarm optimization，PSO)算法是一种基于种群搜索的随机优化技术，其模拟了鸟群觅食过程中的迁徙和群集行为[1].PSO算法具有概念简单、控制参数少、收敛速度快和易于编程实现的优点[2]，自提出以来受到广大学者的关注.但PSO算法同其他的随机搜索方法类似，在求解复杂多峰函数时，容易陷入局部最优[3].为了提高算法性能，较多学者提出了基于不同思想的改进算法，可以简单归纳为以下几类:1)调节算法的参数[4-5];2)群体拓扑结构的改进[6-7];3)与其他优化算法混合[8-9];4)嵌入生物行为机制[10-11];5)设计新的学习策略[12-13].

在基本PSO算法中，粒子通过向个体最优位置和群体最优位置学习并不断调整其飞行速度和所在位置，从而实现在搜索空间寻优.这样的学习策略使得群体内的信息交流速度快，但由于学习方向的单一性，容易产生“趋同”现象，在算法性能上表现为迭代后期搜索缓慢甚至停滞，容易陷入局部最优[14].因此，设计新的粒子学习策略是提高PSO算法性能的一个重要途径.目前，国内外学者已经在这方面开展了一些研究.Liang等提出了广泛学习的PSO算法，其每个粒子根据学习概率来决定向自身个体最优位置还是其他的个体最优位置进行学习[12].实验结果表明，采用广泛学习策略能够探索更大的搜索空间，保持了群体多样性，算法在搜索过程中不容易陷入局部最优，适合于多峰函数的求解.根据多精英比单精英更能够引导群体学习的社会现象，Huang等提出了基于榜样学习的改进PSO算法[13].文献[15]引入了超球坐标的方式来更新粒子速度，设计了一种集成学习PSO算法.Wang等提出了一种自适应学习的PSO算法，该算法依据搜索的进程进行调整学习概率，在具有不同优点的4种学习策略中进行自适应选择[16].Peram等提出了适应度值－距离－比例的PSO算法，此算法中每个粒子的每一维根据适应度值－距离－比例原则确定一个新的学习对象[17].

人类社会中不同群体之间存在资源和特质的差异性，个体不但会吸收所在群体的经验，而且还会同其他群体进行信息交流.因此，人类社会的学习行为可以发生在个体与个体、个体与群体以及群体与群体之间.启发于人类社会的学习行为特点，本文提出了一种由2个种群组成的交互学习的粒子群优化算法(interactive learning particle swarm optimization，ILPSO).当2个种群中最佳的全局最优位置在连续一定的迭代次数内没有改善时，开始实施交互学习策略.交互学习的策略使得粒子学习的方向具有了多样性，为算法摆脱局部最优提供了新的额外动力.仿真实验结果表明，ILPSO在搜索的过程中能够较好地保持群体的多样性，具有较好的全局寻优能力，是一种求解复杂问题的有效方法.

1 粒子群优化算法框架

PSO算法中的每个粒子视为问题的一个可行解.在D维的搜索空间中，粒子i在t次迭代时的状态属性由位置向量和速度向量进行描述其中 ld和 ud分别为搜索空间的下限和上限，d=1，2，…，D，vmin和 vmax是由用户设定的粒子飞行的最小和最大速度.粒子的好坏由一个事先设定的适应度函数来确定.在算法的迭代过程中，每一个粒子通过向个体最优位置和群体最优位置进行学习，按照式(1)和式(2)更新飞行速度和位置，从而在搜索空间内寻优.

式中:tmax和t分别表示最大迭代次数和当前的迭代次数，ωs和ωe分别表示算法初始和停止时的惯性权重.文献[4]的研究结果表明当 ωs=0.9，ωe=0.4时，算法具有较好的性能.将文献[4]这种惯性权重按照式(3)递减的PSO算法称为标准粒子群优化算法(SPSO).

2 交互学习的粒子群优化算法

2.1 交互学习策略

在ILPSO中，粒子分成Swarm1和Swarm22个种群.算法初始运行时，2个种群均按照式(1)更新速度.Swarm1中粒子i在t次迭代的位置向量、速度向量、个体最优位置和群体最优位置分别记为将上述 4 个向量的下标“1”改成“2”就代表Swarm2相对应的向量.设的适应度表示为表示 t次迭代时 2 个种群中最佳的全局最优位置，其适应度表示为在连续的k次迭代中如果没有改善时，即，表明算法陷入了局部最优，2个种群开始实施交互学习策略，其主要步骤如下:

1)确定学习种群和被学习种群.启动交互学习策略时，其中一个种群将仍然维持原有的方式进行寻优，称之为被学习种群;改变原有的学习方式的种群称为学习种群.根据的值，采用模拟退火的方法确定Swarm1和Swarm2作为被学习种群的概率.这样的方式使得群体最优位置相对较差的种群将以一定的概率作为被学习种群，从而增加了算法的全局搜索能力.用ps表示Swarm1被选择作为被学习种群的概率，依据模拟退火算法的原理易有式(4):

式中:T表示模拟退火的温度.依据ps的大小，采用轮盘赌的抽样方法确定学习种群和被学习种群.抽取在[0，1]均匀分布的随机数，小于 ps时，Swarm1为被学习种群，反之Swarm2将作为被学习种群.

2)确定学习种群中每个粒子向被学习种群学习的概率.在ILPSO中，根据学习种群中单个粒子适应度值的排序来决定学习概率的大小.学习种群中适应度好的粒子向被学习种群学习的概率相对较小，以尽量维持目前良好的搜索形态;反之学习种群中适应度值较差的粒子，学习概率较大.依据经验公式(5)确定学习种群中粒子i向被学习种群的学习概率 pci.

式中:orderi表示按粒子i在学习种群内适应度的排序;m表示学习种群的规模.

3)更新每个种群的速度和位置.被学习种群的粒子按照式(1)更新速度;在学习种群中，如果产生的随机数小于pci，粒子i同时向个体最优位置、群体最优位置和被学习种群的群体最优位置学习更新速度;反之仍然根据式(1)更新速度.当Swarm1是学习种群时，向Swarm2学习的粒子速度按照式(6)更新.而当Swarm2是学习种群时，向Swarm1学习的粒子速度按照式(7)更新.

式中:rij(i=1，2，j=1，2，3)表示在[0，1]内均匀分布的随机数.

2.2 变异算子

如果Swarm1和Swarm2的群体最优位置的适应度值相差较大时，式(4)会给算法带来较大的选择压力，不利于全局搜索.基于这样的考虑，本文采用在任意一个种群中随机选择一个粒子在任一维上的速度按式(8)发生变异:

式中:vmax表示粒子飞行的最大速度，r3和r4表示均匀分布在[0，1]的随机数.由于只选择一个种群中的一个粒子一维的速度发生变异，因此几乎不会破坏群体的结构.但每一个种群、每一个粒子和其每一维速度从统计意义上来说是以同样的概率被选择发生变异.

2.3 ILPSO 主要步骤

ILPSO的主要步骤如下:

1)置t=0;初始化2个种群粒子的位置和速度，并设定相应的参数;

2)计算粒子适应度值，确定个体最优位置和群体最优位置;

4)确定学习种群和被学习种群;

5)计算学习种群中每个粒子向被学习种群学习的概率;

6)更新2个种群的粒子速度和位置;

7)执行变异算子;

8)t=t+1;计算粒子适应度，更新每个粒子的个体最优位置和群体最优位置;

9)判断程序终止条件是否满足，若满足则算法终止，输出最优解，否则转到3).

3 仿真实验

3.1 测试函数

本文选取了11个常用的测试函数进行仿真实验.其中基本测试函数包括f1、f22个单峰函数和f3、f64个多峰函数，f7、f8和 f9、f11分别是偏移测试函数和旋转测试函数.基本测试函数的局部极值点多沿着平行的坐标轴，且全局最优位于原点，不能较好地反映现实中优化问题的复杂性.Suganthan等对基本测试函数进行了偏移和旋转[18].f7、f8是将基本测试函数f2和f3的全局最优点随机移动到每一维具有不同数值的新位置，并且加上了一个偏置值O.本文依据文献[18]的方法进行偏移.旋转测试函数f9～f11是通过将一个正交矩阵左乘f2、f3和f5而得到的，其各个变量之间变得都不可分.其中正交矩阵的产生采用Salomon在1996年提出的方法[19].表1给出了每个函数的名称、数学表达式、搜索范围和最优值.

表1 测试函数及其参数设置Table 1 Benchmark function and their settings

3.2 实验参数设置

将ILPSO 同 SPSO、PSOPC、FDR-PSO 和 HPSOTVAC的性能进行比较.为公平起见，各种比较算法的粒子数量设置为 60，在 ILPSO中 Swarm1和Swarm2的粒子数量分别设置为30.SPSO、PSOPC、FDR-PSO、HPSO-TVAC和ILPSO的详细参数根据文献[4、10、17、20]进行设置，具体见表 2，其中 Range表示搜索范围的大小.式(4)中初始温度T0和退温方式根据文献[21]提出的如式(9)、(10)确定:

式中:λ称为退温速率，本文取λ=0.9.

表2 参数设置Table 2 Parameter settings of involved algorithms

3.3 实验结果与分析

将ILPSO和其他的4种PSO算法在11个测试函数上分别独立运行25次，最大迭代次数为6 000次.比较的5种PSO算法的实验结果(平均值和标准差)如表3，其中最好的实验结果加粗表示.图1描述了比较的5种PSO算法求解f1～f3，f5～f10平均最优值的变化曲线.

表3 各种算法的测试结果比较Table 3 Comparisons of experimental results

对于f1，ILPSO的求解结果都优于其他4种算法.在对“香蕉函数”f2的优化中，相较于 SPSO、PSOPC和 FDR-PSO，ILPSO和 HPSO-TVAC在搜索过程中没有陷入局部最优.虽然ILPSO实验结果的平均值稍差于 HPSO-TVAC，但标准差较小，表明ILPSO具有较好的鲁棒性.对于具有大量局部最优点的复杂多峰函数f3和f6，ILPSO体现了很好的优化效果，在搜索过程中一直没有陷入局部最优，说明了交互学习策略能够摆脱局部最优的有效性.比较的各算法在求解函数f4的性能差别不大，都搜索到比较满意的结果.在求解 f5中，SPSO、PSO-FDR和HPSO-TVAC的搜索精度只能达到 10－2数量级，PSOPC的搜索精度为10－3数量级，而ILPSO的搜索精度达到了10－4数量级且标准差最小.对于偏移测试函数f7和f8，ILPSO求解结果的平均值和标准差都明显好于其他算法.将函数的坐标轴进行旋转后，求解的难度将会提高.ILPSO对旋转测试函数f9～f11的实验结果仍表现出了好的搜索精度和鲁棒性，表明了其具有很好的适应性.综上分析，ILPSO在对基本测试函数、偏移测试函数和旋转测试函数的求解中都表现了搜索精度高和鲁棒性好的特点，特别对复杂的函数，其优秀的搜索性能更加突出.

在ILPSO中，由于交互学习策略的作用，每个粒子群体的多样性得到维护，从而提高了全局搜索能力，不容易陷入局部最优.根据“没有免费午餐定理”，在维护粒子群体多样性的同时也带来了收敛速度相对不够快的成本.从图1中可以看出，ILPSO的收敛速度虽然快于SPSO和HPSO-TVAC，但在一些测试函数的优化上比PSOPC和FDR-PSO的收敛速度稍慢.

图1 各种算法实验结果的平均最优值变化Fig.1 The convergence curve of invdved algorithms

4 结束语

在分析基本PSO算法学习策略缺陷的基础上，启发于人类社会学习的特点，本文提出了一种交互学习的PSO算法——ILPSO.交互学习策略中学习种群和被学习种群在搜索的过程中能够相互转换，且改善了粒子学习方向“单一性”的缺陷，保证了群体的多样性，从而提高了算法的全局搜索能力.多个测试函数的实验结果表明ILPSO具有较高的搜索精度和鲁棒性，特别在求解复杂的问题中，体现的优化性能更加突出.如何在保证ILPSO搜索精度和鲁棒性的同时，并进一步提高收敛速度，以及将ILPSO应用到实际问题的求解中是未来研究的重点.

[1]EBERHART R C，KENNEDY J.Particle swarm optimiza-tion[C]//IEEE International Conference on Neural Networks.Perth，Australia，1995:1942-1948.

[2]KENNEDY J，EBERHART R C.Empirical study of particle swarm optimization[C]//Proc of Congress on Evolutionary Computation.Washington，DC，USA，1999:1945-1949.

[3]ANGELINE P J.Evolutionary optimization versus particle swarm optimization and philosophy and performance difference[C]//Proc of 7th Annual Conference on Evolutionary Programming.San Diego，USA，1998:601-610.

[4]SHI Y，EBERHART R C.A modified particle swarm optimizer[C]//IEEE Congress on Evolutionary Computation Anchorage.AK，NJ，1998:69-73.

[5]FAN S K S，LIANG Y C，ZAHARA E.Hybrid simplex search and particle swarm optimization for the global optimization of multimodal functions[J].Engineering Optimization，2004，36:401-418.

[6]SUGANTHAN P N.Particle swarm optimizer with neighborhood operator[C]//Proc of the IEEE Congress of Evolutionary Computation.Washington DC，USA，1999:1958-1961.

[7]杨雪榕，梁加红，陈凌，等.多邻域改进粒子群算法[J].系统工程与电子技术，2010，32(11):2453-2458.YANG Xuerong，LIANG Jiahong，CHEN Ling，et al.Multineighbourhood improved particle swarm optimization algorithm[J].Systems Engineering and Electronics，2010，32(11):2453-2558.

[8]杨帆，胡春平，颜学峰.基于蚁群系统的参数自适应粒子群算法及其应用[J].控制理论与应用，2010，27(11):1479-1488.YANG Fan，HU Chunping，YAN Xuefeng.Particle swarm optimization algorithm of self-adaptive parameter based on ant system and its application[J].Control Theory ＆ Applications，2010，27(11):1479-1488.

[9]ZHANG W J，XIE X F.DEPSO:hybrid particle swarm with differential evolution operator[C]//Proc of IEEE International Conference on System，Man and Cybernetic.Washington DC，USA，2003:3816-3821.

[10]HE S，WU Q H，WEN J Y，et al.A particle swarm optimizer with passive congregation[J].BioSystems，2004，78:135-147.

[11]秦全德，李荣钧.基于生物寄生行为的双种群粒子群算法[J].控制与决策，2011，26(4):548-552.QIN Quande，LI Rongjun.Two-population particle swarm optimization algorithm based bio-parasitic behaviour[J].Control and Decision，2011，26(4):548-552.

[12]LIANG J J，QIN K，SUGANTHAN P N.Comprehensive learning particle swarm optimization for global optimization of multimodal functions[J].IEEE Transactions on Evolutionary Computation，2006，6(3):281-295.

[13]HUANG H，QIN H，HAO Z F，et al.Exampled-based learning swarm optimization for continuous optimization[J].Information Sciences，2011，182(1):125-138.

[14]CLERC M，KENNEDY J.The particle swarm:explosion，stability，and convergence in multi dimensional complex space[J].IEEE Transactions on Evolutionary Computation，2002，6:58-73.

[15]SABAT S L，UDGATA S K.Integrated learning particle swarm optimizer for global optimization[J].Applied Soft Computing，2011，11(1):574-584.

[16]WANG Y，LI B，WEISE T，et al.Self-adaptive learning based particle swarm optimization[J].Information Sciences，2011，182(20):4515-4538.

[17]PERAM T，VEERAMACHANENI K，MOHAN C K.Fitness-distance-ratio based particle swarm optimization[C]//Proc of the Swarm Intelligence Symposium.Indianapolis，USA，2003:174-181.

[18]SUGANTHAN P N，HANSEN N，LIANG J J，et al.Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization[R/OL].http://www.ntu.edu.sg/home/EPNSugan.

[19]SALOMON R.Reevaluating genetic algorithm performance under coordinate rotation of benchmark functions[J].Biosystems，1996，39:263-278.

[20]RATNAWEERA A，HALGAMUGE S K，WATSON H C.Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients[J].IEEE Transactions on Evolutionary Computation，2004，8(3):240-255.

[21]王凌，李令莱，郑大钟.非线性系统参数估计的一类有效搜索策略[J].自动化学报，2003，29:953-958.WANG Ling，LI Lingtai，ZHENG Dazhong.A class of effective search strategies for parameter estimation of nonlinear systems[J].Acta Automatica Sinica，2003，29:953-958.