实验六:遗传算法求解TSP问题实验讲解

4-7-8 5-4-8-7-3-1-9-0.65 28.0447 33.7003 30.9371 2-6-0 9-1-3-8-7-4-5-0.7 27.0935 32.0927 29.9502 0-6-2 0-5-4-8-7-3-1-0.75 28.0447 32.4488 30.3699 9-2-6 7-4-5-0-6-2-9-0.8 27.0935 32.1551 29.9382 1-3-8 5-0-6-2-9-1-3-0.85 27.0935 34.5399 30.3594 8-7-4 6-0-5-4-7-8-3-0.9 27.0935 32.6273 30.69 1-9-2 6-2-9-1-3-8-7-0.95 27.0935 32.4672 29.919 4-5-0 476 375 360 358 559 571 596 (注:红色表示非最优解)

在该情况下,交叉概率过低将使搜索陷入迟钝状态,得不到最优解。

(3)变异概率对算法结果的影响 实验次数:10 种群规模:25 最大迭代步数:100 交叉概率:0.85

实验结果:

表1-3

变异概率 最好适应度 最差适应平均适应度 度 最优解 0-6-2-1-9-3-8-70.001 29.4717 34.732 32.4911 -4-5 8-4-5-0-2-6-9-10.01 29.0446 34.6591 32.3714 -3-7 5-0-2-6-9-1-3-80.1 28.0934 34.011 30.9417 -7-4 6-0-5-4-7-8-3-10.15 27.0935 32.093 30.2568 -9-2 8-7-4-5-0-6-2-90.2 27.0935 32.2349 30.3144 -1-3 4-5-0-6-2-9-1-30.25 27.0935 32.718 30.1572 -8-7 0-5-4-7-8-3-1-90.3 27.0935 32.4488 30.2854 -2-6 1-3-8-7-4-5-0-60.35 27.0935 33.3167 30.7748 -2-9 2-0-5-4-8-7-3-10.4 0.45 29.0446 27.0935 34.3705 31.3041 31.374 -9-6 362 438 266 252 245 282 246 250 274 245 运行时间 29.6816 2-6-0-5-4-7-8-3-1-9 2-9-1-3-8-7-4-50.5 27.0935 32.3752 30.2211 -0-6 1-3-8-7-4-5-0-60.55 27.0935 33.3819 30.6623 -2-9 1-3-8-7-4-5-0-20.6 28.0934 33.2512 30.36 -6-9 3-1-9-2-6-0-5-40.65 27.0935 32.7491 30.0201 -7-8 1-3-8-7-4-0-5-60.7 28.7108 32.4238 30.785 -2-9 1-9-2-6-0-5-4-70.75 27.0935 31.8928 30.2451 -8-3 9-1-3-8-7-4-5-00.8 28.0934 31.6135 30.3471 -2-6 2-9-1-3-7-8-4-00.85 29.662 33.2392 31.1585 -5-6 0-5-4-8-7-3-1-90.9 28.0447 32.0387 30.4152 -2-6 9-1-3-7-8-4-5-00.95 28.0447 31.3036 30.0067 -6-2 436 396 314 327 475 432 434 417 492 431 又表1-3可知,当变异概率过大或过低都将导致无法得到最优解。

注:(2)(3)的实验数据与(1)的实验数据不同,详见附录。

六、不同变异策略和个体选择概率分配策略对算法结果的影响 (1)两点互换变异与插入变异的比较: ? 试验次数(CASNUM):10 ? 城市数(POINTCNT):10 ? 种群规模(POPSIZE):100

? 最大迭代步数(GENERATIONS):100 ? 交叉概率(PC):0.85 ? 变异概率(PM):0.15 ? 选择个体方法:轮盘赌选择 ? 交叉类型:PMX交叉

? 个体选择概率分配方法:适应度比例方法

a. 变异类型: 两点互换变异

表1-4两点互换变异程序结果

最好适应序号 度 最差适应度 平均适应度 最优解 6-2-0-5-4-7-8-3-1 2 28.0934 27.0935 30.4229 31.1417 29.0891 1-9 1199 1678 运行时间 28.9841 4-5-0-6-2-9-1-3-8-7 0-5-4-7-8-3-1-9-3 27.0935 30.4228 29.0604 2-6 1-3-8-7-4-5-0-6-4 27.0935 30.3703 28.8787 2-9 3-1-9-2-6-0-5-4-5 27.0935 31.0619 29.0755 7-8 2-6-0-5-4-7-8-3-6 27.0935 31.1589 29.3942 1-9 6-2-9-1-3-7-8-4-7 28.0447 31.0619 29.7648 5-0 4-5-0-2-6-9-1-3-8 29.0446 31.3475 29.8415 7-8 0-6-2-9-1-3-8-7-9 27.0935 30.6143 29.059 4-5 9-2-6-0-5-4-7-8-10 27.0935 30.5585 29.0811 3-1 0-5-4-7-8-3-1-9-11 27.0935 31.0171 29.4264 2-6 1-9-2-6-0-5-4-7-12 27.0935 31.3036 29.2414 8-3 0-6-2-9-1-3-8-7-13 27.0935 32.0255 29.0789 4-5 1517 1541 1517 1872 1940 1980 1772 1936 1885 1756 1940

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4