发布时间 : 星期三 文章进化粒子群算法在TSP中的应用更新完毕开始阅读6b5bbe4b2b160b4e767fcf0e
第21页
第4章 一种改进的求解TSP混合粒子群优化算法
本章结合遗传算法、蚁群算法和模拟退火算法的思想,用混合粒子群算法[1]来求解著名的旅行商问题.。与模拟退火算法、标准遗传算法进行比较，24 种混合粒子群算法的效果都比较好，而且简单有效，收敛速度快，结果也比较优，对于目前仍没有较好解法的组合优化问题, 通过此算法修改很容易解决。
4.1 混合粒子群算法的概述
混合粒子群算法的本质是利用本身信息、个体极值信息和全局极值信息3个信息，指导例子下一步迭代位置，对于TSP问题，其当前位置是基本路径，若按基本粒子群算法，其速度难以表达，故采用遗传算法的思想解决。
vk?1?c0vk?c1(pbestk?xk)?c2(gbestk?xk) （ 4-1）
xk?1?xk?vk?1 （4-2）
式（4-1）、（4-2）为基本粒子群优化算法的粒子速度和位置更新公式。在混合粒子群算法当中，式（4-1）中的c0vk项可看作遗传算法的变异操作，
c1(pbestk?xk)?c2(gbestk?xk)项可看作遗传算法的交叉操作，使当前解与个体极值和
全局极值分别作交叉操作，产生的解为新的位置。变异操作和交叉操作后，新的解可能比原来的解要坏，接受准则是采用模拟退火算法的思想，允许目标函数有限范围内变坏，为简化计算并不按概率取舍，直接按ΔE 4.2 变异操作 这里假设有n个城市，由路径C0变异到另一条路径C1，常用的有以下几种策略： 1） 变异策略A：在第1~n个访问的城市中随机选取第j1次和第j2次访问的 城市，在路径C0中交换第j1次和第j2次访问的城市，其余不变，此时路径为C1。 2） 变异策略B：在第1~n个访问的城市中随机选取第j1次访问的城市，在 路径C0中交换第j1次和第j+1次访问的城市，其余不变，此时路径为C1。 3） 变异策略C：在第1~n个访问的城市中随机选取第j1次和第j2次访问的 城市，在路径C0中第j1次到第j2次访问的城市之间的子路径以反方向插入，其余不变，此时路径为C1。 4） 变异策略D：在第1~n个访问的城市中随机选取第j1次和第j2次访问的 第22页 城市，假设j1 5） 变异策略E：上述策略未利用城市间距离大小的信息，变异策略E将利用 点的邻接关系，依据蚁群算法的思想，距离近的邻接点以较大的概率被选为下一个访问点，所以在局部调整时依据此思想。设d（i，j）表示城市i 与城市 j 的距离，在第1~n个城市中随机选取城市i1，离城市i1最远的城市的距离为： dmax?maxd(i1,j) （4-3） j为了排除下一个访问点为其本身，令d（i1，i1）=dmax，则下一个访问点为城市j的概率为： pj?dmax?d(i1,j)n （4-4） ?(dk?1max?d(i1,j))假设以公式（4-3）的概率选择城市j1，在路径C0中将城市j1安排在i1之后，其余不变，此时路径为C1。 6） 变异策略F：在第1~n个城市中随机选取城市i1，为了使路径总长度之和 达到最小，优先解决薄弱环节，这里采用路径中相邻城市间距离大的两个城市以较大的概率被选取，在它们之间插入其他城市。采用l（n）数组记录路径C0相邻城市之间的距离，具体数据如下： l(k)?d[c(k),c(k?1)]k?1,2,?,n?1; （4-5） l(n)?d[c(n),c(1)] （4-6） 选取城市 i 的概率为： pi?l(i)/(?l(k)) （4-7） k?1n按式（4-7）选取城市i1，后面方法同策略变异E，按式（4-4）选取城市j1，在路径C0中将城市j1安排在i1之后，其余不变，此时路径为C1。 4.3 交叉操作 交叉的方法很多, 下面几种方法最常用： 1） 交叉策略A：在第2个串中随机选择一个交叉区域；将old2 的交叉区域 加到old1 前面（或后面），删除old1中已在old2交叉区中出现过的城市。 2） 交叉策略B：在第2个串中随机选择一个交叉区域；将old2 的交叉区域 第23页 加到old1对应的位置，删除old1中已在old2交叉区中出现过的城市。 3） 交叉策略C：在第2个串中随机选择一个交叉区域；将old2 的交叉区域 加到old1的随机位置，删除old1中已在old2交叉区中出现过的城市。 4） 交叉策略D：在第2个串中随机选择一个交叉区域，如交叉区域为：6，5， 4，3； 找非交叉区域城市离交叉区域两端城市6和城市3最近的城市，若城市8，3最近，则将old2 的交叉区域加到old1 的城市8的位置（有可能逆转），删除old1中已在old2交叉区中出现过的城市。 4.4 混合粒子群算法 解TSP 的混合粒子群算法如下： 设定粒子数m，规定迭代次数N_max，随机产生m个初始解（初始路径）C0； 根据当前位置计算适应值（各路径的长度）ltsp0，设置当前适应值为个体极值plbest，当前位置为个体极值位置pcbest，根据各个粒子的个体极值plbest，找出全局极值glbest和全局极值位置gcbest； While（迭代次数 第j 个粒子路径C0（j）与交叉得到C1'(j)； C1'(j)与pcbest 交叉得到C1''(j)； 对C1''(j)产生变异得到C1（j）； 根据当前位置计算适应值 ltsp1； 计算两个位置所引起的适应值的变化量ΔE；若ΔE 数变坏的范围），ΔE≤0，接受新值；否则，拒绝，第 j 个粒子路径C1（j）仍然为C0（j）；如果ltsp1（j） End For 根据各个粒子的个体极值plbest, 找出全局极值glbest 和全局极值位置 gcbest; C0←C1； End While 最后输出全局极值 glbest 和全局极值位置gcbest； 混合粒子群算法的时间复杂性可估算如下：以交叉时间花费最多，内循环需要作O（2m）交叉操作，外循环执行N_max次，所以时间复杂度约为O（2mN_max）。 其流程图如图4-1所示 第24页 种群初始化评估个体适应值ltsp1Yltsp1(j) 图4-1 混合粒子群算法流程图 4.5 算法测试 每种算法对burma14进行10次仿真结果如下（burma14最优解为30.8785）： ● 交叉策略A变异策略A：