广州大学人工智能原理实验一：知识的表示与推理实验 广州大学人工智能原理实验二：八数码问题 广州大学人工智能原理实验三：产生式系统推理 广州大学人工智能原理实验四：TSP问题的遗传算法实现 广州大学人工智能原理实验五：基于汉诺塔的问题规约图实现 五份实验报告下载链接🔗

本实验课程是计算机、智能、物联网等专业学生的一门专业课程，通过实验，帮助学生更好地掌握人工智能相关概念、技术、原理、应用等；通过实验提高学生编写实验报告、总结实验结果的能力；使学生对智能程序、智能算法等有比较深入的认识。要掌握的知识点如下： 1.掌握人工智能中涉及的相关概念、算法； 2.熟悉人工智能中的知识表示方法； 3.掌握问题表示、求解及编程实现； 4.熟悉和掌握遗传算法的基本概念和基本思想； 5.理解和掌握遗传算法的各个操作算子，能够用选定的编程语言设计简单的遗传优化系统； 6.通过实验培养学生利用遗传算法进行问题求解的基本技能。

1.实验前，复习《人工智能》课程中的有关内容。 2.准备好实验数据。 3.程序可以在多个同学交流下讨论完成，但是实验报告独立完成。 4.该按照自己完成的部分进行。

推荐使用C或C++（Visual studio等平台）（不限制语言使用，Java，matlab，Python等）。

以N个节点的TSP（旅行商问题）问题为例，应用遗传算法进行求解，求出问题的最优解。 1 旅行商问题 旅行商问题（Traveling Salesman Problem, TSP），又译为旅行推销员问题、货担郎问题，简称为TSP问题，是最基本的路线问题。假设有n个可直达的城市，一销售商从其中的某一城市出发，不重复地走完其余n-1个城市并回到原出发点，在所有可能的路径中求出路径长度最短的一条。 TSP问题是组合数学中一个古老而又困难的问题，也是一个典型的组合优化问题，现已归入NP完备问题类。NP问题用穷举法不能在有效时间内求解，所以只能使用启发式搜索。遗传算法是求解此类问题比较实用、有效的方法之一。 下面给出30个城市的位置信息：

最优路径为：1 2 3 4 6 5 7 8 9 10 11 12 13 14 15 16 17 19 18 20 21 22 23 24 25 28 26 27 29 30 其路径长度为：424.869292 也可取前10个城市的坐标进行测试：

表2 Oliver TSP问题的10个城市位置坐标

有人求得的最优路径为： 1 4 6 5 10 9 8 7 3 2 1 路径长度是166.541336 上述10个城市的求解中编号从0开始，把所有路径搜索完又返回到出发节点。

2 问题描述 应用遗传算法求解30/10个节点的TSP（旅行商问题）问题，求问题的最优解。

（1）要求求出问题最优解，若得不出最优解，请分析原因； 一、取前10个城市测试： 参数设置：

最优路径为： [ 1 2 3 7 8 9 10 5 6 4 1] 最优距离：166.54133557746266

二、取所有城市测试： 参数设置：

最优路径为： [13 12 11 10 9 8 7 5 6 4 3 2 1 30 29 27 26 28 25 24 23 22 21 20 18 19 17 16 15 14 13] 最优距离：424.8692923184516

（2）对实验中的几个算法控制参数进行仔细定义，并能通过实验选择参数的最佳值；

①　以所有城市测试为例，进行以下参数讨论； ②　每一条基因的定义为一条旅游路线，即每一条基因对应了30个城市数字下标，这30个数字每个都是有且只有一个； ③　选择种群：优胜劣汰，对低于平均适应度的染色体进行交叉和突变，高于平均适应度的进行保留； ④　交叉操作：选取两条父母染色体，对母亲染色体随机截取一段S，对父染色体在S上出现的数字剔除，然后拼接S，返回交叉后的染色体； ⑤　突变操作：对染色体进行随机截取一段，进行翻转操作； ⑥　种群进化：种群内每一根染色体都有可能进行交叉和突变，取决于交叉率和突变率。 ⑦　大的种群可以保证每一代里拥有的染色体更多，交叉和突变得到的新染色体更多，有助于跳出局部最优解，尽早获得全局最优解。 ⑧　为了快速得到实验结果，默认进化代数为500、种群大小为100，对交叉率和突变率进行消融实验

⑨　可以看到pc取0.4，pm取0.3时，可取得全局最优解。但实验初始化具有随机性，参数的选择仅具有一定参考意义。 ⑩　解决办法：采用随机初始化种子，固定随机数的产生，进行多组消融实验，因花费时间可能过多，这里不再一一展开。

（3）要求界面显示每次迭代求出的局部最优解和最终求出的全局最优解。

一、取前10个城市测试：

二、取所有城市测试：

（4）实验结果讨论。

①　本次实验，前十城市还是所有城市，都可以成功寻得全局最优值，完成了实验的基本要求。 ②　遗传算法的核心主要在于，种群淘汰、交叉与变异三个操作，因为这几个点的选择非常重要，所以要针对具体问题设计对应的操作，这样可以大大加快优化的时间。 ③　选择合适的操作之后，还要对参数进行设置，种群大小、交叉率、变异率，这三个参数可以直接影响是否能够跳出局部最优，寻得全局最优。 ④　在对于所有城市的求解过程中，可以发现全局最优解的获得往往要通过多次运行代码才能获得，因此对于该遗传算法应该仍有较大的优化空间。 ⑤　通过本次实验，可以发现一个种群存在着一些问题，就是每次保留的最优染色体都一直是由该种群产生的，很容易陷入局部最优解，或许可以采用多个种群解决这一问题。 ⑥　通过网上查阅，发现已经有人提出了多种群遗传算法MSGA，下面为多种群遗传算法流程简介图。