计算机科学与技术专业

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

实验编号：     1                       批阅人：

实验内容：

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

实验要求：

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

（2） 设计适应度函数

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

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

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

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

报告要求：

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

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

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

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

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

目录

4. 设定遗传操作：

2.1 控制参数

2.2 编码规则

2.3 选择初始群体

2.4 适应度函数

实验报告

一、 实验设计

1. 参数编码：可以采用位串编码、实数编码、多参数级联编码等

2. 设定初始群体：

1. 启发 / 非启发给定一组解作为初始群体

2. 确定初始群体的规模

3. 设定适应度函数：将目标函数映射为适应度函数，可以进行尺度变换来保证非负、归一等特性

4. 设定遗传操作：

1. 选择：从当前群体选出一系列优良个体，让他们产生后代个体，一般采用蒙特卡洛法，即按适 应度占比分配概率

2. 交叉：两个个体的基因进行交叉重组来获得新个体

3. 变异：随机变动个体串基因座上的某些基因

5. 设定控制参数：例如变异概率、交叉程度、迭代上限等

二、 开发环境

Python版本：Python 3及以上

所需要的依赖包：

matplotlib

numpy

mpl_toolkits

可采用的软件：PyCharm