Nelder-Mead蜂群混合优化算法及其收敛性分析与性能比较

1、1Nelder-Mead 蜂群混合优化算法及其收敛性分析与性能比较蜂群混合优化算法及其收敛性分析与性能比较杨晨光杨晨光1, 陈杰陈杰2, 涂绪彦涂绪彦21 中国船舶工业集团公司船舶系统工程部，北京，100362 北京理工大学信息科学技术学院自动控制系，北京，100081关键词关键词：蜂群优化算法，Nelder-Mead 方法，马尔科夫链，基于 Nelder-Mead 方法的蜂群优化算法，旅行商问题.摘要摘要蜂群优化算法是一种新的群智能优化算法，但具有收敛速度慢和计算过程复杂等不足。通过改变蜂群优化算法的结构，利用 Nelder-Mead 方法改善其局部搜索能力，提出一种新的优化算法。基于马尔科

2、夫链理论，分析了所提出算法的收敛能力。通过解决旅行商问题进行仿真优化，对所提出的算法与其他优化算法进行比较，仿真结果表明改进的蜂群优化算法具有更好的熟练能力和优化性能。Keywords: Marriage in honey bees optimization (MBO), Nelder-Mead Method, Markov chain, Nelder-Mead Marriage in Honey Bees Optimization (NMMBO), Traveling Salesman Problem (TSP).AbstractMarriage in Honey Bees Optimiza

3、tion (MBO) is a new swarm-intelligence method, but it has the shortcomings of low speed and complex computation process. By changing the structure of MBO and utilizing the Nelder-Mead method to perform the local characteristic, we propose a new optimization algorithm. The global convergence characte

4、ristic of the proposed algorithm is proved by using the Markov Chain theory. And then some simulations are done on Traveling Salesman Problem (TSP) and several public evaluation functions. Comparing the proposed algorithm with MBO, Improved MBO (IMBO) and Genetic Algorithm (GA), simulation results s

5、how that the proposed algorithm has better convergence performance.1 引言引言群智能是一个新兴热门研究领域，重点关注群居动物的社会习性，抽象出模型，用于解决优化问题。近年来，基于蜂群繁育过程所提出的蜂群优化算法引起了注意。蜂群优化算法（Marriage in Honey Bees Optimization -MBO）由 Jason Teo 和 Hussein A. Abbass1,2所提出，并由 Jason Teo、 Hussein A. Abbass 3 和 Omid Bozorg Haddad 4,5 等人进行了改进。本文

6、将进一步分析蜂群优化算法的计算能力，并结合Nelder-Mead 方法对基本的蜂群优化算法进行了改进，并利用马尔科夫理论分析收敛性。下文中，将首先对蜂群优化算法和马尔科夫链理论进行介绍，然后对蜂群优化算法进行分析，提出改进的蜂群优化算法，并进行仿真比较。2 蜂群优化算法蜂群优化算法蜂群的行为特点不仅与遗传能力有关，还与生态环境、生理环境及外界条件，以及这些因素的相互影响有关1,2，表现出很强的社会性行为，例如合作、交流等，已引起了学者们的广泛兴趣，近年来，有越来越多的研究围绕此而展开。蜂群优化算法就是其中的一项研究成果，它模拟了蜂群的繁育过程，包括以下主要步骤：多个雄蜂通过竞争获得与蜂后交配的

7、机会；强壮的雄蜂将会有较大的概率胜出；未能交配的雄蜂将被蜂群淘汰；幼蜂将由工蜂来照顾。3 马尔科夫链理论马尔科夫链理论马尔可夫链是一种无后效性的随机过程，下一时刻的状态只取决于当前时刻的状态和转移概率，而与过去时刻的状态无关。马尔可夫链被广泛应用于分析收敛性问题，例如通过遗传算法构造成一个马尔可夫过程来研究遗传算法的收敛性。定义定义 16 ：已知方阵ijn nAa ,1,:0,( 0);i jnaAAij如果则称是正的* MERGEFORMAT (1) ,1,:0, ( 0);.i jnaAAij如果则称为非负的 0 and :0,; mAmAA 如果则为正则的 0 and 1, :1,1nA

8、inaAijj 如果则是随机的。定义定义 26 如果状态空间是有限集，即，且SSn一步转移概率与时间 无关，即 ptijt* ,ijiji jSu vpupvMERGEFORMAT (2)2则称这样的马尔可夫链为齐次有限马尔可夫链。式中，为在时刻 ，由状态到状态的一步转移概 ptijti Sj S率。定理定理 16齐次有限马尔可夫链，其转移概率矩阵为，如果()ijPp* MERGEFORMAT (3):0mmP则称此马尔可夫链是遍历的，且极限分布是该齐次有限马尔可夫链的平稳 lim, ,ijjtptp i jS分布。定理定理26 设是可约化随机矩阵。是阶随机PCm正矩阵，则0,0RT* 100

9、0limlim0kkkik ikkkiCCPPT RCTRMERGEFORMAT (4)4 基于基于 Nelder-Mead 方法的蜂群优化算法方法的蜂群优化算法 蜂群优化算法优于遗传算法的重要特点是它在每次迭代都进行局部搜索。但是，MBO 选择的是简单、随机的局部搜索算法，例如工蜂即启发式搜索应用的是Random Walk、Random New1等算法，它们效率较低，性能较差，可以考虑应用较好的局部搜索算法代替它们扮演工蜂角色，从而增进算法性能。Nelder-Mead 方法是一种非线性优化算法，由Nelder 和 Mead8提出。该方法使用直接搜索策略，其特点是对初始值并不敏感，不受限于目标

10、函数是否连续或可微。所以，我们将利用 Nelder-Mead 方法来替代基本蜂群优化算法中的工蜂进行局部搜索。在作者的相关工作中，已对如何提高 MBO 的收敛速度进行了分析，并提出了一种改进算法（Improved Marriage in Honey Bees Optimization IMBO）。作为本文改进算法的基础，这里简单介绍一下。在 MBO 算法中，雄蜂与蜂后交配的概率是一个退火函数1，不仅计算过程复杂，而且用于计算的元素也需要由其他复杂的计算过程得来。所以，整个过程计算量很大。另一方面，我们发现，MBO 需要足够的迭代次数来达到优化结果，但是 MBO 中如能量、速度都不能保证这一点。

11、随着迭代次数的增加，蜂后的飞行速度越小，鉴于蜂后与雄蜂适应度差异带有随机性，其交配概率，越到后期就越小。这会使得算法后期跳出局部极值的能力越来越小，很容易陷入局部极值点。所以，基于基本的 MBO 算法，我们采用如下方法简化计算过程，即每步按比例随机生成雄蜂，限制迭代条件，与有限数量的蜂后进行交配。这里，我们利用前述的两个方面策略，对基本蜂群优化算法进行改进，提出基于 Nelder-Mead 方法的蜂群优化算法（algorithm of Nelder-Mead Marriage in Honey Bees Optimization -NMMBO）。NMMBO 计算过程如下：定义 Q: 蜂后数量D

12、: 雄蜂数量M: 受精囊大小用启发式算法随机初始化工蜂随机初始化蜂后基因类型应用 Nelder-Mead 方法改进蜂后基因类型 如果循环条件不被满足时 (例如循环次数小于最大循环次数，或没有得到满意解)循环蜂后循环受精囊随机产生雄蜂雄蜂和蜂后交叉变异，产生受精卵受精卵基因变异用 Nelder-Meade 作为工蜂进行启发式搜索如果新生成的幼蜂优于最差的蜂后， 用新生成的幼蜂替代最差的蜂后； 按照适应度刷新蜂后列表。图 1: 基于 Nelder-Mead 方法的蜂群优化算法计算流程在图 1 中，NMMBO 比 MBO 算法的计算过程简单，参数个数减少，避免了复杂的概率计算，从而提高了整体的计算速

13、度。在 NMMBO 中，本文定义了三个算子，即交叉算子、变异算子和启发式算子。交叉因子和变异因子与遗传算法中的定义相似，启发式因子由本文定义。交叉算子：通过基因重组产生更优的个体变异算子：以一定概率改变基因个体启发式算子：对一些新个体进行优化，进行局部搜索5 NMMBO 算法收敛性分析算法收敛性分析本节将利用马尔科夫链链理论分析 NMMBO 算法的收敛性能。定义定义 3 NMMBO 的状态空间集合是：* 12, ,0,1 ,1,NiXxt tttiNMERGEFORMAT (5)式中，是二进制位簇。12,Nt tt在集合上，定义适应度函数为，则适应度X f x集合为Y* ,Yy yf x x

14、XMERGEFORMAT (6)则有：* MERGEFORMAT (7),0 xX y 定义，则有如下有序集合gY* 1212,ggyyyyyyMERGEFORMAT (8)交叉因子、变异因子、启发因子会引起状态空间中的状态转移，所以利用三个转移矩阵、和来分CMH别表示它们的影响。定义NMMBO算法马尔可夫链的转移矩阵为，即Tr* MERGEFORMAT TrC M H(9)定理定理4 NMMBO是一个齐次有限马尔可夫过程。3证明：NMMBO算法所有群体集合是有限的，则由构成的12,Mxxx12,Mxxx马尔可夫链是有限的。构成状态空间集合中。如果，则在第X,ijX步，从状态转移到状态的概率仅

15、仅依赖于状态tij而与时间无关。所以，NMMBO 算法的马尔可夫链i是齐次的。所以，NMMBO 是一个齐次有限马尔可夫过程。定理定理5 ：NMMBO算法中，交叉概率转移矩阵和启发概率转移矩阵都是随机的。CH证明 对于交叉概率转移矩阵，Cijn nCc* 1,1,:01,:1nijijji jncandinc MERGEFORMAT (10)所以是随机的。C对于启发概率转移矩阵，Hijn nHh* 1,1,:01,:1nijijji jnhandinh MERGEFORMAT (11)所以是随机的。H定理定理6 NMMBO算法中，变异概率转移矩阵是M随机且正的。证明 对于变异概率转移矩阵， ij

16、n nMm* 1,1,:01,:1nijijji jnmandinm MERGEFORMAT (12)所以，是随机的。M因为变异过程对状态向量的每个元素都有影响，所以很容易得到，将变异为的概率大于零，ixjx。所以，到的转移概率为正。因此，,ijx xXixjx转移概率矩阵是正的。定理定理7 NMMBO算法的马尔可夫链是各态历经Tr的，具有有限分布函数. lim0, ,ijjttrttri jX证明 依据定理 5、定理 6 和公式* MERGEFORMAT 错误！未找到引用源。错误！未找到引用源。，NMMBO算法的马尔可夫链是正的。又根据定理 1，则定理 7 的结论即被证明。定义定义4 一代中

17、的适应度是这袋中所有个体中适应度最大的值，即 121,2,.,maxKiiKfx xxfx* MERGEFORMAT (13)定义，121212,iKKiKXx xxfx xxy x xxX是由* MERGEFORMAT 错误！未找到引用源。错误！未找到引用源。定iy义的，即在集合中，所有个体的适应度都等于。iXiy定义定义5 对于任意一个初始代，是最大的适X(0)1y应度值，即* 1limPr( ()1( )tf XytMERGEFORMAT (14)则这个算法具有全局收敛性。定理定理8 NMMBO收敛到全局最优解。证明 定义* iTXX iNMERGEFORMAT (15)根据定义 4 和

18、定理 4，是一个马尔可夫链。定义TX* ()iiP XP iXXMERGEFORMAT (16)在(12)中定义。则、。iX()0iP X1()1niiP X定义为状态到状态的概率，则(,)ijP XXiXjX* 11(,),(,)jiNNijninjniinjjninjP XXxXxXP xxMERGEFORMAT (17)由于 NMMBO 在每次迭代都保留的最优个体，所以1111(,)(,)(,)(,)nnnnP XXP XXPP XXP XX21221100(,)(,)0(,)(,)nnnP XXP XXP XXP XX* MERGEFORMAT (18)对于定理 3222121(,)0

19、(,)1,(,)(,)(,)nnnnP XXP XXCTRP XXP XXP XX* MERGEFORMAT (19)* 1000limlim0kkkikikkkiCCPPT RCTRMERGEFORMAT (20)对于定理 7 和定理 1，是稳定的随机矩阵，P所以，即1R4* 211lim(,)1lim1lim(,)kkkknkP XXkRRP XX MERGEFORMAT (21)所以，在迭代步数足够多的情况下， 的状态都会转TX到。1X6 仿真仿真为了验证 NMMBO 的收敛性能，我们选择与基本MBO、IMBO 和遗传算法和不应用 Nelder-Mead 进行比较。这里应用复杂测试函数和

20、 TSP 问题作为优化问题。6.1 应用评价函数应用评价函数评价函数 1: Sphere 模型 * 21( ),100iiif xxxMERGEFORMAT (22)01020304050607080012345678stepvalue GAMBOIMBONMMBO图 2: NMMBO、IMBO、MBO 和 GA 对评价函数 1 的优化结果评价函数 2: Schwefel 问题 1303011( ),10iiiiif sxxx* MERGEFORMAT (23)05010015020025002468101214161820stepvalue GAMBOIMBONMMBO图 3: NMMBO、

21、IMBO、MBO 和 GA 对评价函数 2 的优化结果评价函数 3: 广义 Rosenbrock 函数22211( )100()(1),30iiiiif xxxxx* MERGEFORMAT (24)050100150200250020040060080010001200stepvalue GAMBOIMBONMMBO图 4: NMMBO、IMBO、MBO 和 GA 对评价函数 3 的优化结果评价函数 4: Step 函数3021( )0.5,100iiif xxx* MERGEFORMAT (25)020406080100120140160180010203040506070stepvalu

22、e GAMBOIMBONMMBO图 5: NMMBO、IMBO、MBO 和 GA 对评价函数 4 的优化结果评价函数 5: 广义 Rastrigin 函数21( )10 cos(2) 10 ,5.12iiiif xxxx* MERGEFORMAT (26)05010015020025005101520253035404550stepvalue GAMBOIMBONMMBO图 6: NMMBO、IMBO、MBO 和 GA 对评价函数 5 的优化结果评价函数 6: Ackley 函数2111( )cos() 1,6004000iiiiixf xxxi* MERGEFORMAT (27)505010

23、015005101520253035stepvalue GAMBOIMBONMMBO图 7: NMMBO、IMBO、MBO 和 GA 对评价函数 6 的优化结果6.2 旅行商问题旅行商问题旅行商（Traveling Salesman Problem -TSP）问题是一个典型的 NP 问题，已经成为测试优化算法有效性的标准。为了说明问题，下面将对比标准遗传算法、原始蜂群算法和作者提出的改进蜂群优化算法，采用TSPLIB 数据集。010020030040050060065707580859095100105110115stepdistance(km) GAMBOIMBONMMBO图 8: NMMB

24、O、IMBO、MBO 和 GA 对 16 个城市的TSP 问题优化结果01002003004005006007000.70.80.911.11.21.3x 105stepdistance(km) GAMBOIMBONMMBO图 9: NMMBO、IMBO、MBO 和 GA 对 48 个城市的TSP 问题优化结果6.3 分析分析从以上结果可以看出，无论是对于复杂的评价函数还是对于不同规模的 TSP 问题，NMMBO 的计算性能都很稳定。具体而言，NMMBO 不仅收敛，而且收敛速度快，尽管有的评价函数具有多个局部最优点，但是NMMBO 都能给出较好的优化结果。NMMBO 的性能不仅优于基本的蜂群优

25、化算法和遗传算法，也优于不采用 Nelder-Mead 方法的 IMBO 算法。收敛速度快，尤其在初始阶段，尤其对于初始条件差于其他三种算法的时候，NMMBO 仍能迅速收敛。对于 MBO 算法，从结果可见，有时 MBO 优于遗传算法，有时则很差，性能表现并不稳定。由于其计算过程复杂和较差的局部搜索能力，所以 MBO 的性能并不是很好，有时长期维持在某个局部极值无法跳出。7 结论结论本文提出一种改进的蜂群优化算法，即基于Nelder-Mead 方法的蜂群优化算法。基本蜂群优化算法参数多、计算量大，而NMMBO 算法不仅通过随机生成一定数量的雄蜂与蜂后交配，避免了陷入局部极值，并且提高的计算速度；

26、并且利用优化的局部搜索性能取得更好的优化能力。基于马尔科夫链理论，NMMBO 算法的收敛性也得到了证明。仿真结果也验证了无论是优化 TSP 问题还是复杂的评价函数，NMMBO 的优化性能都优于基本蜂群优化算法和遗传算法，并验证了采用 Nelder-Mead 方法改进局部搜索能力的有效性。另一方面，NMMBO 算法还有很多可以深入研究的地方，作者将在今后的工作中继续讨论。参考文献参考文献1H.A. Abbass, “Marriage in Honey Bees Optimization (MBO): a haplometrosis polygynous swarming approach”, Congress on Evolutionary Computation, CEC2001, Korea, pp. 207-214, (2001).2H.A. Abbass, “A single queen single worker honey-bees approach to 3-SAT”, Proceedings of the Genetic and Evolutionary Computation Conference, GECCO2001, USA, pp.807-814, (2001).3Jason Teo and H.A.