3.5　实验：实现遗传算法

3.5.1　实验目的

（1）了解遗传算法的基本原理。

（2）学会利用遗传算法优化实际问题。

3.5.2　实验要求

（1）了解遗传算法的实现步骤。

（2）使用Python实现遗传算法。

（3）将算法应用于求解函数最大值。

3.5.3　实验原理

遗传算法（GA）是由美国Holland教授最早提出的一种基于自然界的“适者生存，优胜劣汰”基本法则的智能搜索算法。该法则很好地诠释了生物进化的自然选择过程。遗传算法也是借鉴该基本法则，通过基于种群的思想，将问题的解通过编码的方式转化为种群中的个体，并让这些个体不断地通过选择、交叉和变异算子模拟生物的进化过程，然后利用“优胜劣汰”法则选择种群中适应性较强的个体构成子种群，最后让子种群重复类似的进化过程，直到找到问题的最优解或到达一定的进化（运算）时间。

GA的基本步骤如下。

步骤1：种群初始化，选择一种编码方案，然后在解空间内通过随机生成的方式初始化一定数量的个体构成GA的种群。

步骤2：评估种群，利用启发式算法对种群中的个体（矩形件的排样顺序）生成排样图并依此计算个体的适应度（利用率），然后保存当前种群中的最优个体作为搜索到的最优解。

步骤3：选择操作，根据种群中个体适应度的大小，通过轮盘法或期望值方法，将适应度高的个体从当前种群中选择出来。

步骤4：交叉操作，将步骤3选择的个体，用一定的概率阈值Pc控制是否利用单点交叉、多点交叉或其他交叉方式生成新的交叉个体。

步骤5：变异操作，用一定的概率阈值Pm控制是否对个体的部分基因执行单点变异或多点变异。

步骤6：终止判断，若满足终止条件，则终止算法；否则，返回步骤2。

3.5.4　实验步骤

用GA求y = 10×sin（5x） + 7×cos（4x）的最大值，步骤如下。

（1）初始化种群，采用10位二进制进行编码代表x的值，产生n个个体，代码如下。

（2）对染色体解码，也就是将二进制转化为十进制，并计算适应度，在这个问题中也就是函数值的大小，代码如下。

（3）对于值为负数的个体进行淘汰，代码如下。

（4）找出当前种群的最优解，也就是最大值，保存在list中，代码如下。

（5）计算每个个体被选中的概率，这里是用个体的函数除以种群全体值得到的，然后利用轮盘法进行选择，代码如下。

（6）进行交叉和变异操作，代码如下。

（7）编写主函数，定义所需变量，得到结果，代码如下。

（8）输出结果显示。

图3-22所示为种群进化代数（0～500）与每代最优个体适应度的关系。