计算机科学与技术专业

《人工智能》课程实验报告

实验编号：     1                       批阅人：

实验内容：

通过设计GA（遗传算法）求解下面所示图的最大割问题。补充：最大割问题即：即将一个无向图切成2个部分（子图），从而使得2个子图之间的边数最多。

实验要求：

（1） 写清问题编码方案，明确染色体表示

（2） 设计适应度函数

（3） 确定选择、交叉、变异算子的具体形式

（4） 确定进化终止条件，确保解的质量

（5） 程序要可视化进化情况、最优解和最佳适应度值

（6） 写明运行环境和开发平台，可记录实现过程中的反思、经验和教训，也可记录使用提高编程效率的技术

报告要求：

（1） 报告按照“学号+姓名+实验编号命名”，例如“01022020202张三实验1”；

（2） 报告要求图文并茂，对实验要求中的（1）~（4）要解释设计方案并给出充分的描述，提供算法代码截图和运行截图，对于实验要求（5）要给出代码截图和运行截图，避免只有图没有文字和只有文字没有图的情况；

（3） 独立完成设计实验，杜绝抄袭。一旦发现抄袭情况，抄袭者和被抄袭者的报告均做零分处理。

（4） 通过FTP在指定时间上传学院实验平台。

（5） 上述所有内容请保留，作为实验报告前部不要删除。

实验报告

一、 实验设计

Step1:设置种群大小，将染色体进行编码，并初始化种群

定义种群适应度函数

Step2: 使用轮盘赌的方式从种群中随机选择两个父代染色体

Step3: 杂交

对选取的父代进行杂交得到子代，其中杂交方法为若两个父代的同一节点在相同集合中，则保留；否则，对随机分配该节点至任意集合中。

Step4:  变异

设定遗传概率，在0.05的概率下，将子代的某个节点从一个集合移动到另一个集合中。

Step5: 种群更新

将通过轮盘赌方式挑选出的两个父代杂交得到的子代保留，并从种群中挑选出质量最差的个体出来，将此个体用子代个体替换掉。

Step6: 循环

循环执行以上5个步骤，每5个步骤为一代，一代一代向前进化，直到完成最优解

二、 开发环境

VS2019

三、 程序实现

（1） 以‘p’开头的总概栏，指明了总的点数和边数；以‘e’开头的两个点的标号，代表这两个点相连接。创建一个二维数组，两个标号分别为其下标，以布尔值或者标识值作为数组的存放值以判断两个点是否相连。另外完成种群初始化的过程。

（2） 确定选择、交叉、变异算子的具体形式

在Genetic_Crossover()中，对于父亲节点的选择，按优秀度进行轮盘选择的。对选取的父代进行杂交得到子代，其中杂交方法为若两个父代的同一节点在相同集合中，则保留；否则，对随机分配该节点至任意集合中。

子代变异：

将交叉后的子代的某个节点从一个集合移动到另一个集合中。

（3） 确定进化终止条件，确保解的质量

对种群进行更新，若得到的子代的被切割边数大于群体中最小的被切割边数，则用该子代取代。经过一次一次的种群更新，个体的解会向着最优解不断地靠近，最终最好的解到达并稳定在一个比较优秀的值

（4） 检验该解是否为当前最优解，并输出最后结果

实验代码截图：

运行截图：

四、 实验反思和分析

（1） 由于使用pycharm时，库函数的引用总是报错而且无法解决，所以最后采用了C++进行此次实验的编程

（2） 在进行无向图的最大割的解析时，一开始并不能理解所给出的无向图应该怎么切割，在网上查阅了最大割的相关问题后，明白了最大割问题的本质是将无向图的顶点划分至两个集合中，让两个集合中的顶点之间的关联边权重之和达到最大。