基于Python实现的遗传算法求最大割问题 实验报告+使用说明+源码
计算机科学与技术专业
《人工智能》课程实验报告
实验编号： 1 批阅人：
报告整洁和分析（20%）
算法设计（40%）
算法实现（40%）
总成绩
实验内容：
通过设计GA（遗传算法）求解下面所示图的最大割问题。补充：最大割问题即：即将一个无向图切成2个部分（子图），从而使得2个子图之间的边数最多。
实验要求：
（1） 写清问题编码方案，明确染色体表示
（2） 设计适应度函数
（3） 确定选择、交叉、变异算子的具体形式
（4） 确定进化终止条件，确保解的质量
（5） 程序要可视化进化情况、最优解和最佳适应度值
（6） 写明运行环境和开发平台，可记录实现过程中的反思、经验和教训，也可记录使用提高编程效率的技术
报告要求：
（1） 报告按照“学号+姓名+实验编号命名”，例如“01022020202张三实验1”；
（2） 报告要求图文并茂，对实验要求中的（1）~（4）要解释设计方案并给出充分的描述，提供算法代码截图和运行截图，对于实验要求（5）要给出代码截图和运行截图，避免只有图没有文字和只有文字没有图的情况；
（3） 独立完成设计实验，杜绝抄袭。一旦发现抄袭情况，抄袭者和被抄袭者的报告均做零分处理。
（4） 通过FTP在指定时间上传学院实验平台。
（5） 上述所有内容请保留，作为实验报告前部不要删除。
目录
实验报告
一、 实验设计
1. 参数编码：可以采用位串编码、实数编码、多参数级联编码等
2. 设定初始群体：
1. 启发 / 非启发给定一组解作为初始群体
2. 确定初始群体的规模
3. 设定适应度函数：将目标函数映射为适应度函数，可以进行尺度变换来保证非负、归一等特性
4. 设定遗传操作：
1. 选择：从当前群体选出一系列优良个体，让他们产生后代个体，一般采用蒙特卡洛法，即按适 应度占比分配概率
2. 交叉：两个个体的基因进行交叉重组来获得新个体
3. 变异：随机变动个体串基因座上的某些基因
5. 设定控制参数：例如变异概率、交叉程度、迭代上限等
二、 开发环境
Python版本：Python 3及以上
所需要的依赖包：
matplotlib
numpy
mpl_toolkits
可采用的软件：PyCharm
