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

《Nelder-Mead蜂群混合优化算法及其收敛性分析与性能比较.doc》由会员分享，可在线阅读，更多相关《Nelder-Mead蜂群混合优化算法及其收敛性分析与性能比较.doc（5页珍藏版）》请在三一文库上搜索。

1、1 Nelder-Mead 蜂群混合优化算法及其收敛性分析与性能比较蜂群混合优化算法及其收敛性分析与性能比较 杨晨光杨晨光 1, 陈杰 陈杰 2, 涂绪彦 涂绪彦 2 1 中国船舶工业集团公司船舶系统工程部，北京，10036 2 北京理工大学信息科学技术学院自动控制系，北京，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). Abstract Marriag

3、e in Honey Bees Optimization (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 glo

4、bal convergence characteristic 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 (G

5、A), simulation results show 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

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

7、研究成果，它模拟了 蜂群的繁育过程，包括以下主要步骤：多个雄蜂通过竞 争获得与蜂后交配的机会；强壮的雄蜂将会有较大的概 率胜出；未能交配的雄蜂将被蜂群淘汰；幼蜂将由工蜂 来照顾。 3 马尔科夫链理论马尔科夫链理论 马尔可夫链是一种无后效性的随机过程，下一时刻 的状态只取决于当前时刻的状态和转移概率，而与过去 时刻的状态无关。马尔可夫链被广泛应用于分析收敛性 问题，例如通过遗传算法构造成一个马尔可夫过程来研 究遗传算法的收敛性。 定义定义 16 ：已知方阵 ij n n Aa ,1,:0,( 0);i jnaAA ij 如果则称是正的 * MERGEFORMAT (1) ,1,:0, ( 0);

8、.i jnaAA ij 如果则称为非负的 0 and :0,; m AmAA 如果则为正则的 0 and 1, :1, 1 n AinaA ij j 如果则是随机的。 定义定义 26 如果状态空间是有限集，即，且SSn 一步转移概率与时间 无关，即 pt ij t * , ijij i jSu vpupv MERGEFORMAT (2) 2 则称这样的马尔可夫链为齐次有限马尔可夫链。式中， 为在时刻 ，由状态到状态的一步转移概 pt ij ti Sj S 率。 定理定理 16齐次有限马尔可夫链，其转移概率矩阵为 ，如果 () ij Pp * MERGEFORMAT (3):0 m mP 则称此

9、马尔可夫链是遍历的，且极限分布 是该齐次有限马尔可夫链的平稳 lim, , ijj t ptp i jS 分布。 定理定理26 设是可约化随机矩阵。是阶随机PCm 正矩阵，则0,0RT * 1 0 0 0 limlim 0 k k k ik ik kk i C C PP T RCTR MERGEFORMAT (4) 4 基于基于 Nelder-Mead 方法的蜂群优化算法方法的蜂群优化算法 蜂群优化算法优于遗传算法的重要特点是它在每次 迭代都进行局部搜索。但是，MBO 选择的是简单、随 机的局部搜索算法，例如工蜂即启发式搜索应用的是 Random Walk、Random New1等算法，它们效

10、率较低， 性能较差，可以考虑应用较好的局部搜索算法代替它们 扮演工蜂角色，从而增进算法性能。 Nelder-Mead 方法是一种非线性优化算法，由 Nelder 和 Mead8提出。该方法使用直接搜索策略，其 特点是对初始值并不敏感，不受限于目标函数是否连续 或可微。所以，我们将利用 Nelder-Mead 方法来替代基 本蜂群优化算法中的工蜂进行局部搜索。 在作者的相关工作中，已对如何提高 MBO 的收敛 速度进行了分析，并提出了一种改进算法（Improved Marriage in Honey Bees Optimization IMBO）。作为本 文改进算法的基础，这里简单介绍一下。 在

11、 MBO 算法中，雄蜂与蜂后交配的概率是一个退 火函数1，不仅计算过程复杂，而且用于计算的元素 也需要由其他复杂的计算过程得来。所以，整个过程计 算量很大。另一方面，我们发现，MBO 需要足够的迭 代次数来达到优化结果，但是 MBO 中如能量、速度都 不能保证这一点。随着迭代次数的增加，蜂后的飞行速 度越小，鉴于蜂后与雄蜂适应度差异带有随机性，其交 配概率，越到后期就越小。这会使得算法后期跳出局部 极值的能力越来越小，很容易陷入局部极值点。所以， 基于基本的 MBO 算法，我们采用如下方法简化计算过 程，即每步按比例随机生成雄蜂，限制迭代条件，与有 限数量的蜂后进行交配。 这里，我们利用前述的

12、两个方面策略，对基本蜂群 优化算法进行改进，提出基于 Nelder-Mead 方法的蜂群 优化算法（algorithm of Nelder-Mead Marriage in Honey Bees Optimization -NMMBO）。 NMMBO 计算过程如下： 定义 Q: 蜂后数量 D: 雄蜂数量 M: 受精囊大小 用启发式算法随机初始化工蜂 随机初始化蜂后基因类型 应用 Nelder-Mead 方法改进蜂后基因类型 如果循环条件不被满足时 (例如循环次数小于最大循环次数，或没有 得到满意解) 循环蜂后 循环受精囊 随机产生雄蜂 雄蜂和蜂后交叉变异，产生受精卵 受精卵基因变异 用 Nel

13、der-Meade 作为工蜂进行启发式搜索 如果新生成的幼蜂优于最差的蜂后， 用新生成的幼蜂替代最差的蜂后； 按照适应度刷新蜂后列表。 图 1: 基于 Nelder-Mead 方法的蜂群优化算法计算流程 在图 1 中，NMMBO 比 MBO 算法的计算过程简单， 参数个数减少，避免了复杂的概率计算，从而提高了整 体的计算速度。 在 NMMBO 中，本文定义了三个算子，即交叉算子、 变异算子和启发式算子。交叉因子和变异因子与遗传算 法中的定义相似，启发式因子由本文定义。 交叉算子：通过基因重组产生更优的个体 变异算子：以一定概率改变基因个体 启发式算子：对一些新个体进行优化，进行局部搜 索 5

14、NMMBO 算法收敛性分析算法收敛性分析 本节将利用马尔科夫链链理论分析 NMMBO 算法 的收敛性能。 定义定义 3 NMMBO 的状态空间集合是： * 12 , ,0,1 ,1, Ni Xxt tttiN MERGEFORMAT (5) 式中，是二进制位簇。 12 , N t tt 在集合上，定义适应度函数为，则适应度X f x 集合为Y * ,Yy yf x x X MERGEFORMAT (6) 则有： * MERGEFORMAT (7),0xX y 定义，则有如下有序集合gY * 1212 , gg yyyyyy MERGEFORMAT (8) 交叉因子、变异因子、启发因子会引起状态

15、空间中 的状态转移，所以利用三个转移矩阵、和来分CMH 别表示它们的影响。定义NMMBO算法马尔可夫链的转 移矩阵为，即Tr * MERGEFORMAT TrC M H (9) 定理定理4 NMMBO是一个齐次有限马尔可夫过程。 3 证明：NMMBO算法所有群体集合 是有限的，则由构成的 12 , M xxx 12 , M xxx 马尔可夫链是有限的。 构成状态空间集合中。如果，则在第X , ij X 步，从状态转移到状态的概率仅仅依赖于状态t i j 而与时间无关。所以，NMMBO 算法的马尔可夫链 i 是齐次的。所以，NMMBO 是一个齐次有限马尔可夫 过程。 定理定理5 ：NMMBO算法

16、中，交叉概率转移矩阵 和启发概率转移矩阵都是随机的。CH 证明 对于交叉概率转移矩阵，C ij n n Cc * 1 ,1,:01,:1 n ijij j i jncandinc MERGEFORMAT (10) 所以是随机的。C 对于启发概率转移矩阵，H ij n n Hh * 1 ,1,:01,:1 n ijij j i jnhandinh MERGEFORMAT (11) 所以是随机的。H 定理定理6 NMMBO算法中，变异概率转移矩阵是M 随机且正的。 证明 对于变异概率转移矩阵， ij n n Mm * 1 ,1,:01,:1 n ijij j i jnmandinm MERGEFO

17、RMAT (12) 所以，是随机的。M 因为变异过程对状态向量的每个元素都有影响， 所以很容易得到，将变异为的概率大于零， i x j x 。所以，到的转移概率为正。因此，, ij x xX i x j x 转移概率矩阵是正的。 定理定理7 NMMBO算法的马尔可夫链是各态历经Tr 的，具有有限分布函数. lim0, , ijj t trttri jX 证明 依据定理 5、定理 6 和公式* MERGEFORMAT 错误！未找到引用源。错误！未找到引用源。，NMMBO 算法的马尔可夫链是正的。又根据定理 1，则定理 7 的 结论即被证明。 定义定义4 一代中的适应度是这袋中所有个体中适应 度最

18、大的值，即 12 1,2,., ,max Ki iK fx xxfx * MERGEFORMAT (13) 定义， 121212 , iKKiK Xx xxfx xxy x xxX 是由* MERGEFORMAT 错误！未找到引用源。错误！未找到引用源。定 i y 义的，即在集合中，所有个体的适应度都等于。 i X i y 定义定义5 对于任意一个初始代，是最大的适X(0) 1 y 应度值，即 * 1 limPr( ()1( ) t f Xyt MERGEFORMAT (14) 则这个算法具有全局收敛性。 定理定理8 NMMBO收敛到全局最优解。 证明 定义 * i TXX iN MERGEF

19、ORMAT (15) 根据定义 4 和定理 4，是一个马尔可夫链。定义TX * () ii P XP iXX MERGEFORMAT (16) 在(12)中定义。则、。 iX ()0 i P X 1 ()1 n i i P X 定义为状态到状态的概率，则(,) ij P XX i X j X * 11 (,),(,) j i N N ijninjniinjj ninj P XXxXxXP xx MERGEFORMAT (17) 由于 NMMBO 在每次迭代都保留的最优个体，所以 111 1 (,)(,) (,)(,) n nnn P XXP XX P P XXP XX 2122 1 100 (

20、,)(,) 0 (,)(,) nnn P XXP XX P XXP XX * MERGEFORMAT (18) 对于定理 3 2221 21 (,)0(,) 1, (,)(,)(,) nnnn P XXP XX CTR P XXP XXP XX * MERGEFORMAT (19) * 1 0 0 0 limlim 0 k k k ikik kk i C C PP T RCTR MERGEFORMAT (20) 对于定理 7 和定理 1，是稳定的随机矩阵，P 所以，即1R 4 * 21 1 lim(,) 1 lim 1 lim(,) k k k k n k P XX k RR P XX MER

21、GEFORMAT (21) 所以，在迭代步数足够多的情况下， 的状态都会转TX 到。 1 X 6 仿真仿真 为了验证 NMMBO 的收敛性能，我们选择与基本 MBO、IMBO 和遗传算法和不应用 Nelder-Mead 进行比 较。这里应用复杂测试函数和 TSP 问题作为优化问题。 6.1 应用评价函数应用评价函数 评价函数 1: Sphere 模型 * 2 1 ( ),100 ii i f xxx MERGEFORMAT (22) 01020304050607080 0 1 2 3 4 5 6 7 8 step value GA MBO IMBO NMMBO 图 2: NMMBO、IMBO、

22、MBO 和 GA 对评价函数 1 的 优化结果 评价函数 2: Schwefel 问题 1 3030 11 ( ),10 iii ii f sxxx * MERGEFORMAT (23) 050100150200250 0 2 4 6 8 10 12 14 16 18 20 step value GA MBO IMBO NMMBO 图 3: NMMBO、IMBO、MBO 和 GA 对评价函数 2 的 优化结果 评价函数 3: 广义 Rosenbrock 函数 222 1 1 ( )100()(1),30 iiii i f xxxxx * MERGEFORMAT (24) 05010015020

23、0250 0 200 400 600 800 1000 1200 step value GA MBO IMBO NMMBO 图 4: NMMBO、IMBO、MBO 和 GA 对评价函数 3 的 优化结果 评价函数 4: Step 函数 30 2 1 ( )0.5,100 ii i f xxx * MERGEFORMAT (25) 020406080100120140160180 0 10 20 30 40 50 60 70 step value GA MBO IMBO NMMBO 图 5: NMMBO、IMBO、MBO 和 GA 对评价函数 4 的 优化结果 评价函数 5: 广义 Rastri

24、gin 函数 2 1 ( )10 cos(2) 10 ,5.12 iii i f xxxx * MERGEFORMAT (26) 050100150200250 0 5 10 15 20 25 30 35 40 45 50 step value GA MBO IMBO NMMBO 图 6: NMMBO、IMBO、MBO 和 GA 对评价函数 5 的 优化结果 评价函数 6: Ackley 函数 2 11 1 ( )cos() 1,600 4000 i ii ii x f xxx i * MERGEFORMAT (27) 5 050100150 0 5 10 15 20 25 30 35 ste

25、p value GA MBO IMBO NMMBO 图 7: NMMBO、IMBO、MBO 和 GA 对评价函数 6 的 优化结果 6.2 旅行商问题旅行商问题 旅行商（Traveling Salesman Problem -TSP）问题是 一个典型的 NP 问题，已经成为测试优化算法有效性的 标准。为了说明问题，下面将对比标准遗传算法、原始 蜂群算法和作者提出的改进蜂群优化算法，采用 TSPLIB 数据集。 0100200300400500600 65 70 75 80 85 90 95 100 105 110 115 step distance(km) GA MBO IMBO NMMBO

26、图 8: NMMBO、IMBO、MBO 和 GA 对 16 个城市的 TSP 问题优化结果 0100200300400500600700 0.7 0.8 0.9 1 1.1 1.2 1.3x 10 5 step distance(km) GA MBO IMBO NMMBO 图 9: NMMBO、IMBO、MBO 和 GA 对 48 个城市的 TSP 问题优化结果 6.3 分析分析 从以上结果可以看出，无论是对于复杂的评价函数 还是对于不同规模的 TSP 问题，NMMBO 的计算性能 都很稳定。具体而言，NMMBO 不仅收敛，而且收敛 速度快，尽管有的评价函数具有多个局部最优点，但是 NMMBO

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

28、O 算法不仅通过随机生成一定数量的雄蜂与蜂 后交配，避免了陷入局部极值，并且提高的计算速度； 并且利用优化的局部搜索性能取得更好的优化能力。基 于马尔科夫链理论，NMMBO 算法的收敛性也得到了 证明。仿真结果也验证了无论是优化 TSP 问题还是复 杂的评价函数，NMMBO 的优化性能都优于基本蜂群 优化算法和遗传算法，并验证了采用 Nelder-Mead 方法 改进局部搜索能力的有效性。 另一方面，NMMBO 算法还有很多可以深入研究 的地方，作者将在今后的工作中继续讨论。 参考文献参考文献 1H.A. Abbass, “Marriage in Honey Bees Optimization

29、 (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

30、, (2001). 3Jason Teo and H.A. Abbass, “An annealing approach to the mating-flight trajectories in the marriage in honey bees optimization algorithm”, Technical Report CS04/01, University of New South Wales, (2001). 4Omid Bozorg Haddad, Abbas Afshar and Miguel A. Marino, “Honey-bees mating optimizati

31、on (HBMO) algorithm: a new heuristic approach for water resources optimization”, Water Resources Management, 20, pp. 661-680, (2006). 5Hyeong Soo Chang, “Converging marriage in honey- bees optimization and application to stochastic dynamic programming”, Journal of Global Optimization, 35, pp. 423-44

32、1, (2006). 6G. Rudolph, “Convergence analysis of canonical genetic algorithms”, IEEE Transaction Neural Networks. 5(1), pp. 96-101, (1994). 7J.C. Lagarias, J.A. Reeds, M.H. Wright and P.E. Wright, “Convergence properties of the Nelder-Mead simplex method in low dimensions”, SIAM Journal of Optimization, 9(1), pp. 112-147, (1998).