遗传算法求解TSP问题实验报告

遗传算法求解TSP问题实验报告(总

5页)

--本页仅作为文档封面，使用时请直接删除即可-- --内页可以根据需求调整合适字体及大小--

人工智能实验报告 实验六 遗传算法实验II

一、实验目的：

熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传求解函数优化问题，理解求解TSP问题的流程并测试主要参数对结果的影响。

二、实验原理：

旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中着名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。

遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程。它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体。这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代。后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解。要求利用遗传算法求解TSP问题的最短路径。

三、实验内容：

1、参考实验系统给出的遗传算法核心代码，用遗传算法求解TSP的优化问题，分析遗

传算法求解不同规模TSP问题的算法性能。

2、对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。 3、增加1种变异策略和1种个体选择概率分配策略，比较求解同一TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。 4、上交源代码。

2

四、实验报告要求：

1、画出遗传算法求解TSP问题的流程图。

开始初始化种群（随机产生城市坐标）确定种群规模、迭代次数、个体选择方式、交叉概率、变异概率等计算染色体适应度值（城市之间的欧氏距离）YES按某个选择概率选择个体个体交叉个体变异P<迭代总次数NO输入适应度最高的解结束

3

2、 分析遗传算法求解不同规模的TSP问题的算法性能。

规模越大，算法的性能越差，所用时间越长。

3、对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。

（1） 种群规模对算法结果的影响 x y 0 3 2 3 4 7 8 8 4 4 9 9 2 2 实验次数：10 最大迭代步数:100 交叉概率： 变异概率：

种群规模 平均适应度值 最优路径 10 4-5-8-7-6-3-1-0-9-2 20 2-9--4 30 -2-9-0 50 0--2-9 80 9-0--2 100 -7-6-3 150 5-8-4-2-9-0-1-3-6-7 200 -2-9-0 250 3--7-6 300 5-8-4-2-9-0-1-3-6-7

如表所示，显然最短路径为,最优路径为-5-8-4-2或3--7-6，注意到这是一圈，顺时针或者逆时针都可以。当种群规模为10，20时，并没有找到最优解。因此并不是种群规模越小越好。

（2） 交叉概率对算法结果的影响 x y 9 3 1 4 7 8 3 4 1 3 9 2 1 实验次数：15 种群规模：25 最大迭代步数:100 变异概率： 实验结果：

4

交叉概率 最好适应度 最差适应度 平均适应度 最优解 9-2-6-0-5-4-8-7-3-1 7-8-3- 7-3--8 0-5-4-8-7-3-1-9-2-6 3--7-8 -6-2-9 8-3--7 9--6-2 -6-2-9 8-3--7 5-0-2-6-9-1-3-8-7-4 -7-8-3 3--7-8 5-4-8-7-3-1-9-2-6-0 9--6-2 0-5-4-8-7-3-1-9-2-6 7-4-5-0-6-2-9-1-3-8 5-0-6-2-9-1-3-8-7-4 6-0-5-4-7-8-3-1-9-2 6-2-9- （注:红色表示非最优解） 在该情况下，交叉概率过低将使搜索陷入迟钝状态，得不到最优解。

（3） 变异概率对算法结果的影响 x y 9 3 1 4 7 8 3 4 1 3 9 2 1 实验次数：10 种群规模：25 最大迭代步数:100 交叉概率： 实验结果： 变异概率 最好适应度 最差适应度 平均适应度 最优解 0-6-2- 8-4-5-0-2-6-9-1-3-7 5-0-2-6-9-1-3-8-7-4 6-0-5-4-7-8-3-1-9-2 8-7-4-5-0-6-2-9-1-3 4-5-0-6-2-9-1-3-8-7 0-5-4-7-8-3-1-9-2-6 -6-2-9 5

2-0-5-4-8-7-3-1-9-6 2-6-0-5-4-7-8-3-1-9 2-9--6 -6-2-9 -2-6-9 3--7-8 -6-2-9 -7-8-3 9--2-6 2-9--6 0-5-4-8-7-3-1-9-2-6 9--6-2 从该表可知，当变异概率过大或过低都将导致无法得到最优解。

4、增加1种变异策略和1种个体选择概率分配策略，比较求解同一TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。

不同变异策略和不同个体选择分配策略几乎不影响算法运行的时间，但会影响适应度。

五、实验心得与体会

通过本实验，更加深入体会了参数设置对算法结果的影响。同一个算法，参数值不同，获得的结果可能会完全不同。 同时通过本次实验，使自己对遗传算法有了更进一步的了解。遗传算法是一种智能优化算法，它能较好的近似求解TSP问题，在问题规模比较大的时候，遗传算法的优势就明显体现出来，当然不能完全保证能得到最优解。

6