基于Nelder-Mead单纯形法的改进量子行为粒子群算法

郑伟博，张纪会

(青岛大学复杂性科学研究所，山东 青岛 266071)



基于Nelder-Mead单纯形法的改进量子行为粒子群算法

郑伟博，张纪会

(青岛大学复杂性科学研究所，山东 青岛 266071)

摘要:针对PSO算法搜索精度较低，并且在复杂多模态函数优化中，容易陷入局部极值的问题，提出了一种改进的量子行为粒子群优化算法。研究了该算法的基本原理、给出了算法流程并采用正交试验的方式获得了一套通用性较强的算法参数。并以CEC’13的28个测试函数作为测试集，采用Wilcoxon符号秩检验将NM-QPSO算法分别与PSO算法和QPSO算法的误差进行比较试验。试验表明：NM-QPSO算法在统计意义上优于传统的PSO算法和QPSO算法，并且在高维函数优化中，具有显著优势。

关键词：群体智能；粒子群优化算法；量子行为粒子群优化算法；Nelder Mead单纯形法

0引言

群体智能(Swarm Intelligence，SI)算法是模拟自然界生物的群体行为设计的随机优化算法。它通过简单个体的交互过程突显出智能行为，因此群体智能具有自组织性。Millonas[1]于1994年提出了群体智能的5个基本原则：距离原则，种群可以进行简单的空间和时间运算；质量原则，种群能够对环境中的质量因素做出反应；反应的多样性原则，种群的反应行为具有一定的多样性，不能太单一；稳定性原则，种群不应在每次环境改变时都改变自己的行为模式；适应性原则，种群应能在改变行为模式是值得的情况下改变其行为模式。目前群体智能研究主要包括蚁群算法和粒子群算法，并衍生出一系列的优化算法、聚类算法和多机器人协同合作系统等，它们都满足Millonas提出的群体智能基本原则。其中，蚁群优化算法和粒子群优化算法在求解实际问题中应用最为广泛。粒子群优化(Particle Swarm Optimization, PSO)算法由Kenney等[2]在1995年提出，其基本思想来源于对鸟群觅食行为的模拟，是一种典型的群体智能优化技术。在该算法中，寻优空间中的每一个个体被抽象为一个粒子，仅考虑其位置属性和速度属性。其运动的速度受自身和群体的历史最优位置的影响，并受到学习因子的协调，从而较好地协调粒子本身和种群之间的关系。PSO具有算法简单、搜索效率较高、通用性较强等优势。但它在高维空间搜索时效率较低而且容易出现早熟收敛。众多学者对此进行了研究。冯奇峰[3]提出将搜索区域分区，使用多个子种群并通过微粒间的距离来保持多样性，然而这类算法在有些情况下会有大量粒子做无用搜索，影响搜索效率。Gülcü和Kodaz H[4]提出一种新的并行学习策略PCLPSO，利用所有其它粒子的历史最优信息来更新粒子速度，并加入主从模式。该策略可以保持种群多样性，防止早熟收敛，可以提高PSO算法在多模态问题上的性能，但是该算法大大增加了粒子间的交互信息，进一步增加了计算的复杂度。张勇等[5]提出了一种结合Nelder-Mead单纯型法的PSO改进算法，该算法通过并行协同运行两种算法，以达到平衡全局和局部寻优能力的目的。Meng等[6]提出了一种采用交叉搜索的加速粒子群搜索算法。孙俊等[7—8]将量子理论中的概率云和观测行为引入PSO，提出了一种具有全局性的量子行为粒子群算法(Quantum-behaved Particle Swarm Optimization，QPSO)，在处理高维多模态优化中取得了较好的效果。在该算法中，取消了PSO算法中的速度属性，每个粒子的下一次位置依概率弥散在整个搜索域，其概率受自身和群体的历史最优位置影响，其具体位置的确定由一次观察操作来完成。QPSO算法有效地克服了PSO算法容易陷入局部极值的缺点，即使在所有粒子均收敛到一个较小的区域时，仍有可能在下次迭代时出现在搜索域的任何位置，并且在高维多模态优化中显著优于PSO算法。但是由于QPSO算法仍旧采用粒子本身做局部搜索，这就要求在搜索到全局最优点附近时，全部粒子需要收敛在一个极小的范围内进行搜索，这一特性导致难以有效平衡算法的全局和局部搜索能力这一对矛盾。近年来国内外学者还对QPSO进行了一系列改进研究，Liu等[9]提出了一种结合模拟退火和协同进化理论的QPSO改进算法。

Nelder-Mead 单纯形法(Nelder Mead Simplex, NM Simplex)是一个非常实用的直接搜索技术，同时也不要求目标函数连续和可导，具有极强的局部搜索能力，在多维无约束优化问题中应用非常广泛[10]。本文受此启发，希望在维持QPSO算法全局性的基础上，提高其局部搜索效率，因此对QPSO算法的群体历史最优点Pg在每次迭代时引入Nelder-Mead单纯形搜索，提出了一种具有Pg自优化功能的量子行为粒子群优化算法。使得这一算法既具有QPSO的全局性强的特点，又具有Nelder-Mead法精细的局部搜索能力。

1基于NM单纯形法的改进量子行为粒子群优化算法

1.1粒子群优化算法

PSO将每个个体抽象为粒子，并仅仅赋予该粒子两个属性，即第t次迭代的粒子位置X(t)和粒子速度V(t)。同时，每个粒子记忆其历史最优位置Pi(t)和群体历史最优位置Pg(t)。迭代公式见文献[11]。其惯性因子，通常设置为t的线性递减函数[12]，以在算法后期加速收敛。

1.2量子行为粒子群优化算法

2004年，孙俊等[13]将量子行为引入PSO算法，提出了量子行为粒子群优化算法。QPSO算法较PSO算法相比具有更强的随机性，因而具有更高的群体智能程度，可以有效地克服PSO算法早熟收敛的不足，并且在处理高维函数优化中具有明显优势。QPSO算法不再采用PSO算法中确定的速度-位置更新策略，取消了速度属性，引入量子思想，认为粒子可能出现在搜索空间中的任何位置，在某一位置出现的概率由一个分布函数决定。每一代粒子出现的具体位置由一次“观察”操作来确定，在算法实现上，利用Monte Carlo方法在第t次迭代递推第t+1次迭代时粒子的具体位置。算法流程见文献[13]。孙俊从理论上推导出当创新系数λ<1.782时，粒子收敛，同时做了试验验证[13]。但是在实际应用中，一般取值不大于1，取值大于1时会大大影响种群的收敛速度。

1.3Nelder-Mead单纯形搜索算法

Nelder和Mead[10]于1965年提出了一种用于优化多维无约束问题的搜索算法，被称作Nelder-Mead单纯形法。它通过取N维空间中的N+1个点构成一个多胞体，计算顶点评价值。然后对最差点进行反射、扩展、压缩等方法获得一个较好点，用它取代最差点，构成一个新的单纯形，或者通过向最好点收缩来形成新的单纯形，以逼近极小点。该算法具有收敛速度快，并有极强的局部搜索能力，在处理高维问题时，也可以以极小的时间成本搜索到局部最优点。而且与PSO算法一样，该算法并不要求被优化函数连续，可微和可导。

1.4基于Nelder-Mead单纯形法的Pg自优化QPSO算法

在高维多模态问题中，QPSO算法明显优于传统的PSO算法，但是收敛速度较低，而QPSO算法在局部的搜索主要依靠多个粒子在小范围里运动，这就要求种群必须最终收敛在群体历史最优点Pg附近进行搜索。虽然文献[14]中将λ设定为1～0.5递减取值，提高了收敛速度，但是其搜索效果仍旧不尽人意。并且通过分析QPSO迭代公式可知，当种群收敛在Pg附近进行搜索时，只有当u取接近于0时粒子才有可能出现在距Pg较远的位置，这样就使QPSO算法在进行精细搜索的时候较难兼顾全局性。为了克服这一问题，希望在种群粒子不收敛在一个较小的范围中时，算法仍旧拥有较好的局部搜索能力，以平衡局部搜索效果和全局性这一对矛盾，因此本文提出了基于Nelder-Mead单纯形法的改进QPSO算法。

NM-QPSO算法的核心思想是通过对QPSO算法的群体历史最优点Pg进行Nelder-Mead单纯形搜索，使Pg在不借助种群中任何粒子的情况下，自行进行优化，搜索当前Pg所在位置周围的局部最优解。考虑到NM单纯形法在搜索到全局最优解的吸引域时，其向极值点的搜索精度显著高于PSO和QPSO算法，但是初始解的选择会对NM单纯形法的优化效果造成较大影响。因此利用QPSO算法为NM单纯形法提供一个较好的初始解，从而更容易搜索到全局最优解的吸引域。而QPSO的全局性也极大地提高了整个系统在进入局部极值吸引域后，摆脱局部极值吸引的能力。

该算法的流程为：

步骤1：初始化每个粒子的当前位置Xi，并将当前位置Xi记录为自身历史最优位置Pi。初始化Ω矩阵，其中Ω为D×D矩阵，用于保存D个点的坐标，D为目标函数维数。

步骤2：计算每个粒子自身历史最优位置Pi的评价值，将最优评价值所对应的Pi记为种群历史最优位置Pg。

步骤3：将Pg和Ω矩阵对应的D个点构成一个D+1维多胞体，进行一次Nelder-Mead单纯形法优化。将得到的新单纯形中评价值最优的点作为Pg，其余D个点的坐标作为新的Ω矩阵。

步骤4：根据QPSO算法迭代公式，更新每个粒子的当前位置Xi，并计算Xi的评价值。

步骤5：对每个粒子，将当前位置Xi的评价值与自身历史最优位置Pi的评价值进行比较，若优于Pi的评价值，则令Pi=Xi。

步骤6：对每个粒子，将当前位置Xi的评价值与种群历史最优位置Pg的评价值进行比较，若优于Pg的评价值，则令Pg=Xi。

步骤7：检查终止条件，若未达到终止条件，返回Step3。

2NM-QPSO算法的控制参数选择

在NM-QPSO算法中，虽然可以采用Nelder-Mead单纯形法和QPSO算法相关文献的参数取值，但是这样取值并不能保证算法的效果。因此针对NM-QPSO算法的4个控制参数：α,β,γ,λ进行了取值试验。其中α为反射系数，β为压缩系数，γ为扩展系数，λ为创新系数。

为减少试验次数，同时不失一般性，设计了正交试验。控制参数的试验取值选取3个水平，分别为可选取值的最小值，中间值和最大值。如表1所示：

采用CEC’13的28个测试函数(参见文献[15])，分别对这4个控制参数进行L9(34)的正交试验，每组试验100次，取维数D=5，误差系数为0.1，最大迭代次数为100 000。超过最大迭代次数时认为该次试验未能找到全局最优位置，定义找到全局最优位置的试验次数占该组试验总次数的比例为达优率。

本试验中优先以达优率为评价标准，在达优率相同时，以每组试验迭代次数的平均数为评价标准。鉴于将λ设为1～0.5递减取值的参数设计在QPSO算法中取得了较好的效果，为了验证NM-QPSO算法固定创新系数的合理性，增加一组经由正交试验得到的通用控制参数与将λ设为1～0.5递减取值的对照试验，统计达优率以判断固定创新系数是否优于、差于递减取值，或者无明显差异。其中,符号“NA”表明二者无明显差异,即二者达优率差≤±5%，“+”表示固定创新系数“好”于递减取值，“-”表示“差”于递减取值。试验结果如表2。

其中，影响度为单个因素的极差与4个因素的极差和之比，其大小反映该因素的影响程度，值越大表明影响程度越高，影响最高的项已加粗表示。

通过统计表2可以得出，NM-QPSO算法通用程度较强的一套控制参数取值方案为：α=1.2,β=0.5,γ=1.5,λ=1。同时分析各函数特点可以看出，对于非常陡峭的函数和局部极值非常密集的函数，为了获得更快的收敛速度和在小范围内跳出局部极值的能力，往往需要取较小的创新系数；对于局部极值相隔较远的多峰函数，应取较大的创新系数以获得较高的全局搜索性能。同时，在优化大多数测试函数时，创新系数λ为主要的控制参数。

对比试验结果表明，取固定创新系数的通用控制参数在函数优化上7个优于5个差于创新系数递减取值的参数选择方案，分析对应函数可以看出在处理局部极值较少，且距离较大的函数时，取大的固定创新系数具有更好的全局性，而在处理局部极值较多，极值较为密集的函数时，创新系数递减取值优势在于可以在迭代后期将种群集中在更小的范围内，防止浪费搜索资源，但是这会削弱种群的全局搜索性能，总体上取通用控制参数效果更优。

3对比测试结果

本试验采用了CEC’13的28个测试函数，每个函数进行n=100次试验，测试5维迭代10 000次和20维迭代100 000次情况下的误差，对PSO算法，QPSO算法以及NM-QPSO算法分别进行了试验。经过对试验数据做K-S检验发现数据并不符合正态分布，不能进行t-检验，并且由于Wilcoxon符号秩检验较配对t-检验灵敏度更高[14]，因此执行显著性水平α=0.05的Wilcoxon符号秩检验以判断NM-QPSO算法是否显著优于、差于PSO和QPSO算法，或者在统计意义上无显著性差异。其中，显著性符号(Sig.符号)“NA”表明二者无显著差异，“+”表示NM-QPSO算法显著“好”，“-”表示NM-QPSO算法显著“差”。为保证公平，本试验采用本文第2节得出的NM-QPSO算法通用控制参数进行测试，PSO算法程序采用CEC’13官方测试程序，QPSO算法采用文献[16]中的参数选择。测试结果如表3～表6。

通过分析以上试验结果可以看出，NM-QPSO算法较另外两种算法在处理下降速度较快的单峰函数时具有显著优势，例如函数F2、F4这类非常陡峭的函数，这种结果是由于另外两种算法缺少精细搜索能力导致的，说明引入NM单纯形法这类局部精细搜索算法对这类函数的优化性能改进是显著有效的。

同时QPSO算法本身较PSO算法在处理全局最优解吸引域较小，局部极值的差也较小的多峰函数时，例如函数F8，F16等，具有显著优势。因为PSO算法在这类函数中，获取的全局历史最优解的吸引能力往往并不能很好地引导其他粒子找到全局最优解，而QPSO算法的全局性强在这类问题上的优势显著存在，同时NM单纯形法可以使粒子一进入吸引域就可以在极少的迭代次数中将群体最优解Pg固定到极值点附近。这说明NM-QPSO算法在处理这类函数时显著优于PSO算法。

但是诸如函数F17,F19这类有下降趋势，同时在全局最优解附近具有大量局部极值的函数，由于QPSO算法相对于PSO算法为了全局性牺牲了一部分精细搜索能力，而对于在全局最优解附近具有大量局部极值的函数，例如F17，在全局最优解附近[-1,1]D局部极值点个数随维度D的上升迅速增长，只要Pg没有进入全局最优解的吸引域，NM单纯形法的精细搜索所能提供的帮助就非常有限，只有在维数较高时才能显著提高QPSO算法在这类函数上的搜索效果，并且是显著差于PSO算法的。因此考虑到显著增加的计算量，NM-QPSO算法并不适用于这类函数。

如图1和图2，选取代表性的函数F2、F8、F16、F17为例，可以明显看出NM-QPSO在搜索速度上优于其他两种算法，即使在函数F17这类NM-QPSO算法并不擅长的函数优化中，其在高维搜索时仍旧占据一定优势。其中直线代表NM-QPSO，点线代表QPSO，虚线代表PSO。

最后，通过横向对比5维和20维测试结果可以得出，在被优化函数维数越高，NM-QPSO算法的效果越好。说明，引入NM单纯形法可以有效地提高QPSO算法的精细搜索能力，并且在QPSO算法优势较为明显的高维函数优化中，NM-QPSO算法更具有显著优势。

4结论

本文结合QPSO算法和NM单纯形法提出了一种基于Nelder-Mead单纯形法的Pg自优化QPSO算法，给出了NM-QPSO算法的算法流程，讨论了控制参数的选择，提出了一套通用性较强的参数选择方案，并利用测试函数对NM-QPSO算法和PSO、QPSO算法进行了对比试验，验证了NM-QPSO算法具有更好的搜索性能，今后的研究将进一步探讨Ω矩阵的取点策略，以及在具有某些特征的函数中在Pg因QPSO算法更新时，对Ω矩阵进行小范围重置等策略。并且今后将进一步研究NM-QPSO算法对无约束单目标多维优化问题的应用，并尝试求解多目标、带约束的多维优化问题。

参考文献:

[1]Millonas M M. Swarms, phase transitions, and collective intelligence[C]//Marks R J, Palaniswami M, Fogel D B. Computational Intelligence: A Dynamic System Perspective. Richmond, TX, USA: Institute of Electrical & Electronics Engineers(IEEE).1994: 137-151.

[2]Kennedy J. Particle swarm optimization[C]//International Conference on Neural Networks. Western Austalia, 1995: 1942-1948.

[3]冯奇峰,李言.改进粒子群优化算法在工程优化问题中的应用研究[J].仪器仪表学报,2006,26(9): 984-987.

Feng Qi Feng,Li Yan. Application of improved particle swarm optimization algorithm in engineering optimization problems[J].Chinese Journal of Scientific Instrument, 2006, 26(9):984-987.

[5]张勇,巩敦卫,张婉秋.一种基于单纯形法的改进微粒群优化算法及其收敛性分析,自动化学报,2009,35(3):289-298.

Zhang Yong, Gong Dun Wei, Zhang Wan Qiu.A simplex method based improved particle swarm optimization and analysis on its global convergence[J]. Acta Automatica Sinica,2009,35(3):289-298.

[6]Meng A, Li Z, Yin H, et al. Accelerating particle swarm optimization using crisscross search[J]. Information Sciences, 2016, 329: 52-72.

[7]Sun J, Feng B, Xu W B. Particle swarm optimization with particles having quantum behavior[C]//IEEE Proceedings of Congress on Evolutionary Computation, Portland, USA. 2004: 325-331.

[8]Sun J, Xu W B, Feng B, A global search strategy of quantum-behaved particle swarm optimization[C]// IEEE Proceedings of Cybernetics and Intelligent Systems, Singapore.2004: 111-116.

[9]Liu F, Zhou Z. An improved QPSO algorithm and its application in the high-dimensional complex problems[J]. Chemometrics and Intelligent Laboratory Systems, 2014, 132: 82-90.

[10] Nelder J A, Mead R. A simplex method for function minimization[J]. The computer journal, 1965, 7(4): 308-313.

[11] Shi Y, Eberhart R C. A modified particle swarm optimizer[C]// Proceedings of the IEEE Congress on Evolutionary Computation, Piscataway, N J. 1998: 69-73.

[12] Ma G, Zhou W, Chang X L. A novel particle swarm global optimization algorithm based on particle migration[J]. Applied Mathematics and Computation, 2012, 218(11): 6620-6626.

[13] 孙俊.量子行为粒子群优化算法研究[D].无锡:江南大学,2009.

Sun Jun. Research on quantum behaved particle swarm optimization algorithm[D].Wuxi: Jiangnan University,2009.

[14] Derrac J, García S, Molina D, et al. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms[J]. Swarm and Evolutionary Computation, 2011, 1(1): 3-18.

[15] Liang J J, Qu B Y, Suganthan P N, et al. Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization[R]. Singapore: Nanyang Technological University,2013.

[16] Pant M, Thangaraj R, Abraham A. A new quantum behaved particle swarm optimization[C]//The 10th annual conference on Genetic and evolutionary computation. Atlanta, GA, USA, 2008: 87-94.

(责任编辑耿金花)

A Improved Quantum Behaved Particle Swarm Optimization Algorithm Using Nelder and Mead′s Simplex Algorithm

ZHENG Weibo, ZHANG Jihui

(Institute of Complexity Science, Qingdao University, Qingdao 266071, China)

Abstract：PSO algorithm is poor in search accuracy and prone to fall into the local extremum when solving complex multimodal function optimization problem. So， we propose an improved quantum behaved particle swarm optimization algorithm. This paper studies the fundamentals and basic procedure of that algorithm, An orthogonal test for parameter selection is designed to select a set of reasonable control parameters. We use a suite of 28 test functions from CEC’13 as test set. NM-QPSO is compared with both of traditional PSO and QPSO by using the Wilcoxon Signed Ranks Test respectively. Tests show that the NM-QPSO algorithm has better performance than the traditional PSO and QPSO algorithms in statistical sense, and it has obvious advantages in the high-dimensional function optimization.

Key words：swarm intelligence； particle swarm optimization； nelder mead simplex method

文章编号：1672—3813(2016)02—0097—08;

DOI:10.13306/j.1672-3813.2016.02.012

收稿日期：2015-07-10；修回日期：2015-10-12

基金项目：山东省自然科学基金(ZR2010GM006)

作者简介：郑伟博(1989-)，男，山东潍坊人，硕士研究生，主要研究方向为物流系统工程，智能优化。 通信作者：张纪会(1969-)，男，山东青岛人，博士，教授，主要研究方向为物流系统工程，智能优化。

中图分类号：TP18

文献标识码：A