多模态优化粒子群算法的研究

黄 琨

多模态优化粒子群算法的研究

黄 琨1,2

（1.广西大学计算机与电子信息学院，广西 南宁 530004；2.广西农业职业技术学院，广西 南宁 530007）

基本粒子群算法直接用于求解多模态函数优化问题会存在不少问题，文章详述了这些可能出现的问题并分析了引起这些问题的原因，然后针对这些不足提出2项改进措施。这2项措施主要是为了在理论上保证找到所有极值点。最后通过对4个不同规模，不同特征的多模态函数进行测试，实验结果证明这2项措施是有效的。

多模态；粒子群算法；迁徙

粒子群算法［1］最开始是J. Kennedy和R. C. Eberhart等为了图形化、形象化的模拟鸟群似乎没有规律、飞行轨迹难以预测的捕食昆虫的活动而设计的演化计算算法。由粒子群算法的位置以及速度更新原理可知［2］，该算法简单明了，收敛迅速而且精度也高，是非线性连续问题的有效求解方法。粒子群算法常用于神经网络的训练，模拟简化的大脑模型，这要求它必须快速而高效。目前运用较多的领域还有计算机视觉、计算机辅助设计等等。我们在工作、学习和日常生活中碰到的许多问题都可能是多模态问题，而目前运用粒子群算法解决多模态问题的研究并不多，粒子群算法由于本身的设计特性，在求解多模态问题时常常会遇到一些困难，比如难以找出所有极值点。本文将会对这些问题进行分析，并提出一些改进措施，最后通过实验测试验证措施的有效性。

1　问题提出

笔者从公式（1）和（2）可以看出，粒子位置的更新变化会受到粒子自己曾经发现的最佳位置和所有粒子曾经发现的最佳位置的影响，至于受影响的程度，跟学习因子C1和C2有关，除此之外还与权重因子、加速度有关。如果一个粒子的适应度是以粒子的函数值作为直接或者间接的参考的话，那么我们推测，在多峰寻优问题中，采用这种适应度评价策略的粒子群算法极有可能无法符合多峰寻优的要求，无法发现所有的极值点，容易陷入局部极值区域而无法跳出。经过对多个不同特性的多峰函数的测试，笔者发现这一猜想是正确的。针对这一问题，在保证粒子群算法执行原理不变的情况下，笔者需要找到一种新的适应度评价策略。

粒子算法在执行时，除了粒子本身会记录一个自身曾经发现的最佳位置之外，算法本身也会记录一个所有粒子所发现的最佳位置。对于多峰函数极值点存在多个的情况，采用基本粒子群算法的只记录当前最佳位置的方法行不通，我们需要寻求新的解决方案。

2　多峰函数优化的改进思想

对于不同的多峰寻优问题， 其极值点可能有多个，并且对应的目标函数值有可能是不同的。本文研究如何利用粒子群算法找到规定区域内的某种极值，比如要么找的是峰值，要么找谷值。有些多峰函数的一些点，尽管同是极值，但是其函数值有可能是不同的，当存在某个极值点比别的极值点的函数值都大或者都小时，粒子在搜索时极可能都朝这个点移动，这会导致算法无法找到别的极值点。针对多峰函数的多极值以及极值点的特征［3］，只需要判别哪些是极值点，哪些是非极值点，只要是极值点，都是最佳的位置点。本文改进粒子群算法的适应度评估策略参考了文献［4］中遗传算法适应度值的设计思想，并针对粒子群算法做了相应改进，其设计思想是：

笔者假设粒子的位置坐标是X=（x1，x2，…，xm），这是一个m维坐标。笔者用F（x）表示多峰函数某个位置对应的函数值。由数学知识，知道极值点出现在函数的驻点，驻点是导数为零的点，驻点有一个特征，那就是它对应的函数值要比它周边邻域的点的函数值都要大或者都要小，比周边邻域更大的点，称它为峰点，反之，则称为谷点。

由数学中偏导数Fitnessi的理论知识，驻点的偏导数是0，而且越是邻近驻点的点，其各个自变量的偏导数越趋于0，那么公式（4）中，Fitnessi的值越趋于1，而离驻点远的点，其偏导数的绝对值通常都比较大，Fitnessi也就会比较小。由于我们设置了一个随机因子，这个因子能放大靠近驻点的点之间的差异。这种适应度评价方法忽视了不同极值点之间的函数差异，对所有极值点一视同仁，这在理论上为粒子群算法找出所有极值点提供了保证。

在上文介绍的粒子群算法基本原理中，粒子更新位置受粒子自己发现的sj，i（t）和群体中的gj，i（t）的影响。在多峰寻优问题中，极值点有多个，那么需要处理好gj，i（t）与多个极值点之间的关系。根据基本粒子群的原理，gj，i（t）只有一个，而多峰寻优问题则存在多个最优值的问题。对于这个问题，本文的处理策略是将寻找到的符合一定条件的不同优良粒子通过一个库存储这些粒子的相关信息，也就是说gj，i（t）可能不是一个粒子，而可能是多个。在参考gj，i（t）执行于粒子位置更新时，我们随机抽取一个新粒子执行更新，粒子更新后，如果发现同属一个坡或者一个谷的粒子更加优越时，则替换自身，接着才与整个群体优良库中的粒子执行比较替换，其原则依旧是同坡、同谷更优秀的则替换，否则不做修改。2个粒子是否同峰、同谷，主要依据粒子间的欧氏距离判定。

3　改进粒子群算法执行流程

本文从2个方面对粒子群算法进行了改进，改进的粒子群算法执行流程有5点内容，其具体内容的描述如下：

（1）算法参数的设置：粒子数目SIZE，算法迭代停止次数Tmax，这与所研究问题的搜索空间大小有关；学习因子C1和C2、惯性权重因子W以及位置更新的加速度V的取值范围。由于在具体的算法实现上，优良粒子群体空间是自动增长的，这里无需设置。

（2）初始化：根据第1步中设置后的参数建立粒子，通常就是指点的位置坐标，并评价粒子的适应度，然后进行对比记录sj，i（t）和gj，i（t）。

（3）粒子位置的更新：参考公式（6）、（7），根据粒子数目循环执行，如果更新后的粒子同属一个峰、或者一个谷而且更加优越，则替换自身，并与优良库中的粒子执行相似的比较。如果找到的粒子是不同峰或者不同谷的，则不对自身修改，而直接与优良库粒子执行比较，如果是同峰或者同谷，如果比库中的粒子更加优秀，则替换。如果不同峰或者不同谷，达到了记录要求，则将它加入库中，否则不作修改。

（4）判断：如果达到最大迭代次数Tmax，则停止算法的执行，否则返回从第3步骤重复执行。

（5）算法停止。

4　实验测试

算法的软件运行环境是matlab 2014a，硬件运行环境是：Intel i5-4210U处理器、8GB内存。

本节选取4个特征各异、寻优难易程度各不相同的多峰值函数进行算法性能的测试，主要检验算法的2个指标。（1）可否发现全部的极值点。极值点有峰值点和谷值点两种类型，考虑到函数寻优往往是求极小值，或者极大值，因此，在某一次的实验中，笔者只寻找极大值，或者极小值。（2）算法的可行、稳定性。通过多次实验，观察是不是每次实验都能找到所有极值点。这4个函数的实验参数设置是粒子数量SIZE=20，迭代搜索次数Tmax= 2000，学习因子C1、C2随机取值于［0，2］之间，惯性权重因子W随机取值于［0，1］之间，而加速度V的取值范围与一致。

实验选取的标准测试函数有以下4个：

函数1：

函数4：

函数1、2、3来自文献［5］，而函数4来自文献［6］，表1是本文IMBF-PSO改进粒子群算法对这四个标准测试函数的测试结果概览，而表2是本文算法对这4个函数的测试结果与文献［5］中的HABC算法、文献［6］的Non-EA算法的测试结果对比。

表1　实验测试结果总览

由表1可以看出，在维度都是30维的情况下，算法均能在指定搜索次数内找到所有指定精度的极值点，而搜索时间也相对较少，当然了，时间运行时间除了与算法本身有关之外，还与电脑的软硬件条件有关，这里仅做参考。

表2　测试结果对比

由表2的实验结果来看，除了函数2在精度上比起文献［5］的HABC算法略有不及之外，其余3个函数测试结果在稳定性、精度都要稍微好一些。综合上述实验测试结果分析，表明本文算法具有比较好的稳定性以及寻优精度，改进措施能够使算法达到多模态函数的优化要求。

5　结束语

从论文对4个特征不同的多峰函数的测试结果来看，本文改进了的粒子群算法在保持基本粒子群算法实现简单、搜索收敛速度快，数值精度高的优点之外，还克服了基本粒子群算法运用于求解多模态问题时存在的无法找到多个极值的困难。这4个多峰函数均能在较高维数的情况下，找到所有极值。当函数的维度逐步增高时，IMBF-PSO算法的搜索成功率可能会随着寻优函数极值点数量的增多和维度升高而下降，说明算法仍有一定的不足，需要进一步的改进。

［1］ 胡旺，李志蜀.一种更简化而高效的粒子群优化算法［J］.软件学报，2007，18（4）：861-868.

［2］ 付荣，居鹤华.基于粒子群优化的时间最优机械臂轨迹规划算法［J］.信息与控制，2011，40（6）：802-808.

［3］ 胡旺，李志蜀.一种更简化而高效的粒子群优化算法［J］.软件学报，2007，18（4）：861-868.

［4］ 刘洪杰，王秀峰.多峰搜索的自适应遗传算法［J］.控制理论与应用，2004，4（21）：303-310.

［5］ 林志毅，王玲玲.求解高维函数优化问题的混合蜂群算法［J］.计算机科学，2013，3（40）：279-281.

［6］ 赵新超.基于非均匀变异的进化算法对高维多峰函数的收敛性分析［J］.系统科学与数学，2010，30（2）：218-224.

The research of multimodal optimization PSO algorithm

There are some problems if basic PSO algorithm is used to solve multimodal function optimization problem directly. This article describes the possible problems and analyzes the causes， then puts forward 2 improved measures for these problems. The 2 measures are mainly to make certain to find all extreme points. Finally we take a test for four multimodal functions in different size and characteristics. The experimental results prove that the two measures are effective.

Uti-modal； PSO； migration

TP302

A

1008-1151（2016）02-0029-03

2016-01-10

黄琨（1985－），男，广西都安人，广西大学计算机与电子信息学院在职研究生，广西农业职业技术学院助教，研究方向为计算机科学与技术。