正在加载图片...
.796 北京科技大学学报 2006年第8期 出局部最优后到寻找全局最优又要化费大量的时 最短的环游路径T中=T山；否则，L中，T中保持 间.因此引入LK变异算子，充分利用LK算法超 不变 强的局部搜索能力，在收敛到一定代数时，选择一 Step7以式(6)和式(7)更新信息素浓度， 定数量的解进行变异，从而进一步缩短解路线的 Step8判断是否出现停滞：若出现停滞，则 长度，以加快蚁群算法的收敛速度， 增大Qo或me;否则，转到Step9. 2.4ASSS算法一般步骤 Step9判断是否满足迭代终止条件：若nc Step1初始化：从m只蚂蚁中随机选择m <ncmax,tabu[k]复位，转到Step2,否则转到Step 个蚂蚁组成侦察子群S,ms=int[m/h],h∈[l, 10. m]然后确定Q0,Q1的初值，其余初始化与 Step 10输出最优解 MMAS算法相同(a,B,P,D,最大迭代次数 3 实验结果及效果分析 ncmx,禁忌表tabu[k],Tma,Tmin) Step2开始迭代：迭代次数nc十1. 由于TSP问题曾被许多文献用于检验蚁群 Step3蚂蚁环游： 算法，而且TSP问题又可以推广到许多组合优化 (1)根据迭代进程，确定ms,Qo,Q1的值； 领域，因此从TSPLIB库中选取中等规模的三个 (2)随机实验获得Q; TSP实例进行测试，来检验本文的改进算法，分 (3)蚂蚁k以式(4)和式(1)计算的转移概 别为eil51,kroal00和dl98,后面的数字为城 率，从当前城市i转移到下一个城市 市数. (4)循环进行(1)一(3)，直到所有的蚂蚁都 除非特别注明，以下实验默认参数设置为： 完成环游. a=1,B=5,p=0.9,0=1,m=20.Tmx和 Step4计算本代最短的环游长度Lb及对 tmm的值采用文献[7]中的公式动态计算，迭代次 应的最短路径T. 数为城市数的2倍 Step5LK变异运算：根据事先设定的开始 3.1Qo,Q1和m的影响 变异界限值，若满足则继续，否则转到Step7. 因Q0,Q1和m。组合实验数据较多，在此只 设允许最大交换边数为kmr,LK最大循环 能列出部分实验结果，实验中Q0,Q1和m,确定 次数为n“,选择T并按一定比例接收其他解 规则为：1ncma/5次迭代，Q0,Q1和me不变； 组成变异集C,从C中依次选择各解作为变异初 ncm/5~ncmx次选代，Q0=Q0-0.2,Q1= 始路径To(其长度为L0)·LK变异运算伪代码 Q1一0.2：若出现停滞则Q0=2Q0,m,=2m,否 如下： 则保持原值，为了检验侦察子群对算法的影响， for (j=0;j<nj) 本实验不使用LK变异算子，信息素更新与 被选用过的边集合X=NULL; MMAS一样选用Sb,每个实例独立运算10次取 for(k=l;k<kmax;k十+) 平均值，结果见表1，黑体数字表示每个实例最 {选择边：随机选择xk=(t2k-1,t2k)∈ 好解. T且足X与y%=(t2k,t2k+1)足T,把xk记录到 从表1中可以看出，Q0=0.3,Q1=0.9, Y; m=int[m/4]组合和Q0=0.25,Q1=0.95, 替换边：用y1,…,y来代替x1,…,xk me=int[m/2]组合较好，这是因为若Q0,ms取 得到新的路径TLk及其长度LLK; 值较大，则随机性太强，不利于算法收敛；反过来， 评价解：if（LLk<L0){To=TLK,L0= 若Q0,m,取值太小，侦察子群的作用表现不明 LLK,终止变异} 显，算法容易陷入局部最优 为了与MMAS和AS算法对比，表2给出了 MMAS和AS算法实验结果，该结果是分别采用 当C中所有解都完成变异后，重新计算本代 文献[7]和[2的算法，每个实例独立运算10次的 最短的环游长度L及对应的最短路径T山 平均值。对照表1和表2可以看出，表1中的解 Step6把Lb与历史循环中最短环游长度 大部分好于表2，这说明引入侦察子群后的蚁群 L中相比较：若Lb<L中，则L中=Lb,历史循环中 算法具有更好的全局搜索能力，出局部最优后到寻找全局最优又要化费大量的时 间．因此引入 LK 变异算子充分利用 LK 算法超 强的局部搜索能力在收敛到一定代数时选择一 定数量的解进行变异从而进一步缩短解路线的 长度以加快蚁群算法的收敛速度． 2∙4 ASSS 算法一般步骤 Step1 初始化：从 m 只蚂蚁中随机选择 ms 个蚂蚁组成侦察子群 Sms＝int ［ m／h ］h∈［1 m］然后确定 Q0Q1 的初值其余初始化与 MMAS 算法相同（αβρw最大迭代次数 ncmax禁忌表 tabu［ k］τmaxτmin）． Step2 开始迭代：迭代次数 nc＋1． Step3 蚂蚁环游： （1） 根据迭代进程确定 msQ0Q1 的值； （2） 随机实验获得 Q； （3） 蚂蚁 k 以式（4）和式（1）计算的转移概 率从当前城市 i 转移到下一个城市 j； （4） 循环进行（1）～（3）直到所有的蚂蚁都 完成环游． Step4 计算本代最短的环游长度 L ib及对 应的最短路径 T ib． Step5 LK 变异运算：根据事先设定的开始 变异界限值若满足则继续否则转到 Step7． 设允许最大交换边数为 kmaxLK 最大循环 次数为 n LK max选择 T ib并按一定比例接收其他解 组成变异集 C从 C 中依次选择各解作为变异初 始路径 T0（其长度为 L0）．LK 变异运算伪代码 如下： for （ j＝0；j＜ n LK max；j＋＋） ｛被选用过的边集合 X＝NULL； for （ k＝1；k＜kmax；k＋＋） ｛选择边：随机选择 xk＝（ t2k—1t2k）∈ T 且∈／X 与 yk ＝（ t2kt2k＋1）∈／T把 xk 记录到 X； 替换边：用 y1…yk 来代替 x1…xk 得到新的路径 TLK及其长度 L LK； 评价解：if （ L LK＜ L0）｛T0＝ TLKL0＝ L LK终止变异｝ ｝ ｝ 当 C 中所有解都完成变异后重新计算本代 最短的环游长度 L ib及对应的最短路径 T ib． Step6 把 L ib与历史循环中最短环游长度 L gb相比较：若 L ib＜ L gb则 L gb＝ L ib历史循环中 最短的环游路径 T gb＝ T ib；否则L gbT gb 保持 不变． Step7 以式（6）和式（7）更新信息素浓度． Step8 判断是否出现停滞：若出现停滞则 增大 Q0 或 ms；否则转到 Step9． Step9 判断是否满足迭代终止条件：若 nc ＜ncmaxtabu［ k］复位转到 Step2否则转到 Step 10． Step10 输出最优解． 3 实验结果及效果分析 由于 TSP 问题曾被许多文献用于检验蚁群 算法而且 TSP 问题又可以推广到许多组合优化 领域因此从 TSPLIB 库中选取中等规模的三个 TSP 实例进行测试来检验本文的改进算法分 别为 eil51kroa100 和 d198后面的 数 字 为 城 市数． 除非特别注明以下实验默认参数设置为： α＝1β＝5ρ＝0∙9w ＝1m ＝20．τmax 和 τmin的值采用文献［7］中的公式动态计算迭代次 数为城市数的2倍． 3∙1 Q0Q1 和 ms 的影响 因 Q0Q1 和 ms 组合实验数据较多在此只 能列出部分实验结果．实验中 Q0Q1 和 ms 确定 规则为：1～ncmax／5次迭代Q0Q1 和 ms 不变； ncmax／5～ ncmax 次 迭 代Q0 ＝ Q0—0∙2Q1 ＝ Q1—0∙2；若出现停滞则 Q0＝2Q0ms＝2ms否 则保持原值．为了检验侦察子群对算法的影响 本实验不使 用 LK 变 异 算 子信 息 素 更 新 与 MMAS 一样选用 S ib每个实例独立运算10次取 平均值结果见表1黑体数字表示每个实例最 好解． 从表 1 中可以看出Q0＝0∙3Q1＝0∙9 ms＝int ［ m／4］ 组 合 和 Q0＝0∙25Q1＝0∙95 ms＝int ［ m／2］组合较好．这是因为若 Q0ms 取 值较大则随机性太强不利于算法收敛；反过来 若 Q0ms 取值太小侦察子群的作用表现不明 显算法容易陷入局部最优． 为了与 MMAS 和 AS 算法对比表2给出了 MMAS 和 AS 算法实验结果该结果是分别采用 文献［7］和［2］的算法每个实例独立运算10次的 平均值．对照表1和表2可以看出表1中的解 大部分好于表2这说明引入侦察子群后的蚁群 算法具有更好的全局搜索能力． ·796· 北 京 科 技 大 学 学 报 2006年第8期