人工智能实验
实验六遗传算法求解TSP问题
一、实验目的
熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传求解函数优化问题，理解求解TSP问题的流程并测试主要参数对结果的影响。
二、实验内容
1、参考实验系统给出的遗传算法核心代码，用遗传算法求解TSP的优化问题，分析遗传算法求解不同规模TSP问题的算法性能。
2、对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。
3、增加1种变异策略和1种个体选择概率分配策略，比较求解同一TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。
4、上交源代码。
1
f人工智能实验
三、遗传算法求解TSP问题的流程图
开始初始化种群（随机产
生城市坐标）确定种群规模、迭代次数、个体选择方
式、交叉概率、变异概率等
计算染色体适应度值（城市之间的欧氏距离）
按某个选择概率选择个体YES
个体交叉
个体变异
P迭代总次数NO
输入适应度最高的解
结束
四、遗传算法求解不同规模的TSP问题的算法性能
（1）遗传算法执行方式说明：适应度值计算方法：当前路线的路径长度
2
f人工智能实验
个体选择概率分配方法：适应度比例方法选择个体方法：轮盘赌选择交叉类型：PMX交叉变异类型两点互换变异（2）实验模拟结果：
城市个数时间（ms）
5
16925
10
16630
15
18833
20
22596
25
24159
30
30289
35
35239
40
38608
45
40032
50
43757
55
47746
60
58143
65
59942
70
64361
75
71417
图11
（3）分析由图11可知，遗传算法执行时间随着TSP问题规模的增大而增大，并且大
致为线性增长。
五、不同参数下的计算结果对比
（1）种群规模对算法结果的影响
3
f人工智能实验
实验次数：10最大迭代步数100交叉概率：085变异概率：015
种群规模
表11适应度值
最优路径
10
25264
4587631092
20
263428
2910367584
30
251652
1367584290
50
251652
0136758429
80
251652
9013675842
100
251652
1092485763
150
251652
5842901367
200
251652
1367584290
250
251652
3109248576
300
251652
5842901367
如表11所示，显然最短路径为251652m最优路径为10913675842或
3109248576，注意到这是一圈，顺时针或者逆时针都可以。当种群规模为
10，20时，并没有找到最优解。
（2）交叉概率对算法结果的影响实验次数：15种群规模：25最大迭代步数100变异概率：015实验结果：
表12
交叉概率最好适应度最差适应度平均适应度
0001
280447
366567
326002
001
270935
349943
321495
01
280447
353033
319372
r