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

1、N Ne el ld de er r- -MMe ea ad d蜂蜂群群混混合合优优化化算算法法及及其其收收敛敛性性分分析析与与性性能能比比较较Good is good, but better carries it.精益求精，善益求善。INSTRUCTIONS FOR PREPARING AND TRANSFERRING FINAL PAPERS TO ECC0122Nelder-Mead蜂群混合优化算法及其收敛性分析与性能比较蜂群混合优化算法及其收敛性分析与性能比较杨晨光杨晨光1, 陈杰陈杰2, 涂绪彦涂绪彦21 中国船舶工业集团公司船舶系统工程部，北京，100362 北京理工大学信息科学技

2、术学院自动控制系，北京，100081INSTRUCTIONS FOR PREPARING AND TRANSFERRING FINAL PAPERS TO ECC0133关关键词键词： ：蜂群优化算法，Nelder-Mead方法，马尔科夫链，基于Nelder-Mead方法的蜂群优化算法，旅行商问题.摘要摘要蜂群优化算法是一种新的群智能优化算法，但具有收敛速度慢和计算过程复杂等不足。通过改变蜂群优化算法的结构，利用Nelder-Mead方法改善其局部搜索能力，提出一种新的优化算法。基于马尔科夫链理论，分析了所提出算法的收敛能力。通过解决旅行商问题进行仿真优化，对所提出的算法与其他优化算法进行比较

3、，仿真结果表明改进的蜂群优化算法具有更好的熟练能力和优化性能。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 Optimization (MBO) is a new swarm-intelligence method, but it

4、 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 characteristic of the proposed algorithm is proved by using t

5、he 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 show that the proposed algorithm has better convergenc

6、e 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 等人进行了改进。本文将进一步分析蜂群优化算法的计算能力，并结合Nelder-Mead方法对基本的蜂群优化算法进行了改进，并利用马尔科

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

8、理论马尔可夫链是一种无后效性的随机过程，下一时刻的状态只取决于当前时刻的状态和转移概率，而与过去时刻的状态无关。马尔可夫链被广泛应用于分析收敛性问题，例如通过遗传算法构造成一个马尔可夫过程来研究遗传算法的收敛性。定定义义16 ：已知方阵ijn nAa ,1,:0,( 0);i jnaAAij如果则称是正的* MERGEFORMAT (1) ,1,:0, ( 0);.i jnaAAij如果则称为非负的 0 and :0,; mAmAA 如果则为正则的 0 and 1, :1,1nAinaAijj 如果则是随机的。INSTRUCTIONS FOR PREPARING AND TRANSFERRIN

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

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

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

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

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

14、交叉算子、变异算子和启发式算子。交叉因子和变异因子与遗传算法中的定义相似，启发式因子由本文定义。交叉算子：通过基因重组产生更优的个体变异算子：以一定概率改变基因个体INSTRUCTIONS FOR PREPARING AND TRANSFERRING FINAL PAPERS TO ECC0155启发式算子：对一些新个体进行优化，进行局部搜索5 NMMBO算法收敛性分析算法收敛性分析本节将利用马尔科夫链链理论分析NMMBO算法的收敛性能。定义定义3 NMMBO的状态空间集合是：* 12, ,0,1 ,1,NiXxt tttiNMERGEFORMAT (5)式中，是二进制位簇。12,Nt tt在

15、集合上，定义适应度函数为，则X f x适应度集合为Y* ,Yy yf x x XMERGEFORMAT (6)则有：* ,0 xX y MERGEFORMAT (7)定义，则有如下有序集合gY* 1212,ggyyyyyyMERGEFORMAT (8)交叉因子、变异因子、启发因子会引起状态空间中的状态转移，所以利用三个转移矩阵、和来分CMH别表示它们的影响。定义NMMBO算法马尔可夫链的转移矩阵为，即Tr* TrC M HMERGEFORMAT (9)定理定理4 NMMBO是一个齐次有限马尔可夫过程。证明：NMMBO算法所有群体集合是有限的，则由构12,Mxxx12,Mxxx成的马尔可夫链是有

16、限的。构成状态空间集合中。如果，则在第X,ijX步，从状态转移到状态的概率仅仅依赖于状态tij而与时间无关。所以，NMMBO算法的马尔可夫链i是齐次的。所以，NMMBO是一个齐次有限马尔可夫过程。定理定理5 ：NMMBO算法中，交叉概率转移矩阵和启C发概率转移矩阵都是随机的。H证明 对于交叉概率转移矩阵，C，ijn nCc* 1,1,:01,:1nijijji jncandinc MERGEFORMAT (10)所以是随机的。C对于启发概率转移矩阵，Hijn nHh* 1,1,:01,:1nijijji jnhandinh MERGEFORMAT (11)所以是随机的。H定理定理6 NMMBO

17、算法中，变异概率转移矩阵是随M机且正的。证明 对于变异概率转移矩阵， ijn nMm* 1,1,:01,:1nijijji jnmandinm MERGEFORMAT (12)所以，是随机的。M因为变异过程对状态向量的每个元素都有影响，所以很容易得到，将变异为的概ixjx率大于零，。所以，到的转移概,ijx xXixjx率为正。因此，转移概率矩阵是正的。定理定理7 NMMBO算法的马尔可夫链是各态历经的Tr，具有有限分布函数. lim0, ,ijjttrttri jX证明 依据定理5、定理6和公式* MERGEFORMAT Error! Reference source not found.，

18、NMMBO算法的马尔可夫链是正的。又根据定理1，则定理7的结论即被证明。定定义义4 一代中的适应度是这袋中所有个体中适应度最大的值，即 121,2,.,maxKiiKfx xxfx* MERGEFORMAT (13)定义121212,iKKiKXx xxfx xxy x xxX，是由* MERGEFORMAT Error! iyReference source not found.定义的，即在集合中，所有个体的适iX应度都等于。iy定定义义5 对于任意一个初始代，是最大的适应度X(0)1y值，即INSTRUCTIONS FOR PREPARING AND TRANSFERRING FINAL

19、PAPERS TO ECC0166* 1limPr( ()1( )tf XytMERGEFORMAT (14)则这个算法具有全局收敛性。定理定理8 NMMBO收敛到全局最优解。证明 定义* iTXX iNMERGEFORMAT (15)根据定义4和定理4，是一个马尔可夫链。TX定义* ()iiP XP iXXMERGEFORMAT (16)在(12)中定义。则、。iX()0iP X1()1niiP X定义为状态到状态的概率(,)ijP XXiXjX，则* 11(,),(,)jiNNijninjniinjjninjP XXxXxXP xxMERGEFORMAT (17)由于NMMBO在每次迭代都

20、保留的最优个体，所以1111(,)(,)(,)(,)nnnnP XXP XXPP XXP XX21221100(,)(,)0(,)(,)nnnP XXP XXP XXP XX* MERGEFORMAT (18)对于定理3222121(,)0(,)1,(,)(,)(,)nnnnP XXP XXCTRP XXP XXP XX* MERGEFORMAT (19)* 1000limlim0kkkikikkkiCCPPT RCTRMERGEFORMAT (20)对于定理7和定理1，是稳定的随机矩P阵，所以，即1R* 211lim(,)1lim1lim(,)kkkknkP XXkRRP XX MERGEF

21、ORMAT (21)所以，在迭代步数足够多的情况下， 的状态都会转到。TX1X6 仿真仿真为了验证NMMBO的收敛性能，我们选择与基本MBO、IMBO和遗传算法和不应用Nelder-Mead进行比较。这里应用复杂测试函数和TSP问题作为优化问题。6.1 应用评价函数应用评价函数评价函数 1: Sphere 模型 * 21( ),100iiif xxxMERGEFORMAT (22)01020304050607080012345678stepvalue GAMBOIMBONMMBO图 2: NMMBO、IMBO、MBO和 GA对评价函数1的优化结果评价函数2: Schwefel问题1303011

22、( ),10iiiiif sxxx* MERGEFORMAT (23)05010015020025002468101214161820stepvalue GAMBOIMBONMMBO图 3: NMMBO、IMBO、MBO和 GA对评价函数2的优化结果评价函数 3: 广义 Rosenbrock 函数22211( )100()(1),30iiiiif xxxxx* MERGEFORMAT (24)INSTRUCTIONS FOR PREPARING AND TRANSFERRING FINAL PAPERS TO ECC017705010015020025002004006008001000120

23、0stepvalue GAMBOIMBONMMBO图 4: NMMBO、IMBO、MBO和GA对评价函数3的优化结果评价函数 4: Step 函数3021( )0.5,100iiif xxx* MERGEFORMAT (25)020406080100120140160180010203040506070stepvalue GAMBOIMBONMMBO图 5: NMMBO、IMBO、MBO和GA对评价函数4的优化结果评价函数 5: 广义Rastrigin函数21( )10 cos(2) 10 ,5.12iiiif xxxx* MERGEFORMAT (26)0501001502002500510

24、1520253035404550stepvalue GAMBOIMBONMMBO图 6: NMMBO、IMBO、MBO和GA对评价函数5的优化结果评价函数 6: Ackley 函数2111( )cos() 1,6004000iiiiixf xxxi* MERGEFORMAT (27)05010015005101520253035stepvalue GAMBOIMBONMMBO图 7: NMMBO、IMBO、MBO和 GA对评价函数6的优化结果6.2 旅行商问题旅行商问题旅行商（Traveling Salesman Problem -TSP）问题是一个典型的NP问题，已经成为测试优化算法有效性的

25、标准。为了说明问题，下面将对比标准遗传算法、原始蜂群算法和作者提出的改进蜂群优化算法，采用TSPLIB数据集。010020030040050060065707580859095100105110115stepdistance(km) GAMBOIMBONMMBO图8: NMMBO、IMBO、MBO和 GA对16个城市的TSP问题优化结果01002003004005006007000.70.80.911.11.21.3x 105stepdistance(km) GAMBOIMBONMMBO图9: NMMBO、IMBO、MBO和 GA对48个城市的TSP问题优化结果6.3 分析分析从以上结果可以看

26、出，无论是对于复杂的评价函数还是对于不同规模的TSP问题，NMMBO的计算性能都很稳定。具体而言，NMMBO不仅收敛，而且收敛速度快，尽管有的评价函数具有多个局部最优点，但是NMMBO都能给出较好的优化结果。INSTRUCTIONS FOR PREPARING AND TRANSFERRING FINAL PAPERS TO ECC0188NMMBO的性能不仅优于基本的蜂群优化算法和遗传算法，也优于不采用Nelder-Mead方法的IMBO算法。收敛速度快，尤其在初始阶段，尤其对于初始条件差于其他三种算法的时候，NMMBO仍能迅速收敛。对于MBO算法，从结果可见，有时MBO优于遗传算法，有时则

27、很差，性能表现并不稳定。由于其计算过程复杂和较差的局部搜索能力，所以MBO的性能并不是很好，有时长期维持在某个局部极值无法跳出。7 结论结论本文提出一种改进的蜂群优化算法，即基于Nelder-Mead方法的蜂群优化算法。基本蜂群优化算法参数多、计算量大，而NMMBO算法不仅通过随机生成一定数量的雄蜂与蜂后交配，避免了陷入局部极值，并且提高的计算速度；并且利用优化的局部搜索性能取得更好的优化能力。基于马尔科夫链理论，NMMBO算法的收敛性也得到了证明。仿真结果也验证了无论是优化TSP问题还是复杂的评价函数，NMMBO的优化性能都优于基本蜂群优化算法和遗传算法，并验证了采用Nelder-Mead方

28、法改进局部搜索能力的有效性。另一方面，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, GECCO200