实验六:遗传算法求解TSP问题实验讲解 下载本文

0-6-2-9-1-3-8-7-14 27.0935 31.516 28.8906 4-5 6-0-5-4-7-8-3-1-15 27.0935 30.4228 29.0226 9-2 0-6-2-9-1-3-8-7-16 27.0935 30.4081 28.9081 4-5 7-8-3-1-9-2-6-0-17 27.0935 30.4081 29.3316 5-4 1-3-8-7-4-5-0-6-18 27.0935 30.0203 28.5243 2-9 2-9-1-3-7-8-4-5-19 28.0447 31.1404 29.567 0-6 7-4-5-0-6-2-9-1-20 平均值

b. 变异类型: 插入变异

表1-5插入变异程序结果

最好适应序号 度 最差适平均适应度 应度 最优解 运行时间 27.3361 30.8782 29.1877 1657 27.0935 31.1417 29.5359 3-8 1311 1609 1601 1522 1853 1377 1345 31.47528.8451 27.0935 3 3 28.9162 27.0935 29.662 29.6633 27.0935 1 28.902 8 2-6-0-5-4-7-8-3-1-9 5-0-6-2-9-1-3-8-7-4 1-9-2-6-0-5-4-7-8-3 4-5-0-6-2-9-1-3-7-8 2-6-0-5-4-7-8-3-1-9 2-6-0-5-4-7-8-3-1-9 3-1-9-2-6-0-5-4-81222 1245 1164 1637 1355 1388 30.52429.5114 28.0447 1 9 31.05729.4685 27.0935 5 2 28.5546 27.0935 29.662 30.8207 28.0447 5 29.748 6 -7 1-9-2-6-0-5-4-7-8-3 0-6-2-9-1-3-8-7-4-5 5-0-6-2-9-1-3-8-71148 30.52429.3908 27.0935 1 7 28.6879 27.0935 30.423 30.40810 27.0935 1 28.72 29.32811 12 27.0935 27.0935 31.374 2 8 1742 2064 -4 4-5-0-6-2-9-1-3-8-7 1-3-8-7-4-5-0-6-21518 1240 1204 30.523 28.5544 30.82029.05013 27.0935 5 8 -9 0-6-2-9-1-3-8-7-4-5 0-5-4-7-8-3-1-9-2-6 4-5-0-6-2-9-1-3-8-7 5-0-6-2-9-1-3-8-7-4 6-0-5-4-7-8-3-1-9-2 4-5-0-6-2-9-1-3-8-7 2-6-0-5-4-7-8-3-1-9 3-1-9-2-6-0-5-4-7-8 1234 1507 1601 1485 1282 1483 1532 1734 31.11729.59014 27.0935 7 5 29.19015 27.0935 30.523 4 30.40828.80616 27.0935 1 1 31.76329.45917 27.0935 9 1 31.15829.16118 27.0935 9 4 30.40828.59719 27.0935 1 4 30.61428.80320 27.0935 3 6 30.64629.064平均值 27.18862 分析:

两点互换变异20次模拟中,4次得到非最优解;而插入变异只有

5 3 1439 2次;插入变异的最好适应度平均值比两点互换变异小0.14755,最

差适应度平均值和总的适应度平均值都比两点互换下,并且在Release下,运行时间前者比后者快218.3ms。可见在该条件下(交叉概率,变异概率,种群规模等),插入变异比两点互换变异的算法效果要好。

(2)个体选择分配策略 ? 试验次数(CASNUM):10 ? 城市数(POINTCNT):10 ? 种群规模(POPSIZE):100

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

a. 个体选择概率分配方法:适应度比例方法 同表1-4

b. 个体选择概率分配方法:非线性排序方式

表1-6非线性排序方式程序结果

序号 最好适最差适平均适应最优解 运行时应度 应度 度 1-9-2-6-0-5-4-7-间 1 27.0935 32.1721 30.0904 8-3 4-5-0-6-2-9-1-3-824 2 28.0447 31.297 29.9979 7-8 2-0-5-4-7-8-3-1-865 3 28.0934 32.1683 30.5601 9-6 3-1-9-2-6-0-5-4-895 4 27.0935 32.0973 30.3472 7-8 4-5-0-6-2-9-1-3-1067 5 27.0935 31.516 29.8531 8-7 5-0-6-2-9-1-3-8-887 6 27.0935 31.408 29.4637 7-4 3-1-9-2-6-0-5-4-727 7 27.0935 31.3742 29.9476 7-8 0-5-4-7-8-1-3-9-651 8 29.5231 31.8009 30.5543 2-6 0-5-4-7-8-3-1-9-901 9 27.0935 32.7147 30.391 2-6 9-3-1-8-7-4-5-0-749 10 29.5231 31.5688 30.2385 6-2 3-7-8-4-5-0-6-2-840 11 28.0447 31.7639 30.2617 9-1 1044