【数据结构与算法】用 Python 实现遗传算法（一）
这里，我们用遗传算法求一个函数的最大值。
$$f(x) = 10sin5x + 7cos4x, x\in[0, 10]$$
我们将求解过程分为以下几步：
-
将自变量 x 进行编码
取基因片段的长度为 10, 则 10 位二进制位可以表示的范围是 0 到 1023。基因与自变量转变的公式是 x = b2d(individual) * 10 / 1023。编码方式为随机从 0 和 1 中选择十次并放在一个列表中。 -
计算目标函数值
根据自变量与基因的转化关系式，求出每个个体的基因对应的自变量，然后将自变量代入函数 f(x)，求出每个个体的目标函数值。 -
适应度函数
适应度函数是用来评估个体适应环境的能力，是进行自然选择的依据。本题的适应度函数直接将目标函数值中的负值变成 0。因为我们求的是最大值，所以要使目标函数值是负数的个体不适应环境，使其繁殖后代的能力为 0。适应度函数的作用将在自然选择中体现。 -
选择
使用轮盘赌算法。其具体步骤：
假设种群中共 5 个个体，适应度函数计算出来的个体适应性列表是 fitvalue = [1 ,3, 0, 2, 4] ，totalvalue = 10 ， 如果将 fitvalue 画到圆盘上，值的大小表示在圆盘上的面积。在转动轮盘的过程中，单个模块的面积越大则被选中的概率越大。选择的方法是将 fitvalue 转化为累加的和 [1, 4, 4, 6, 10], fitvalue / totalvalue = [0.1, 0.4, 0.4, 0.6, 1.0]。然后产生 5 个 0-1 之间的随机数，将随机数从小到大排序，假如是 [0.05, 0.2, 0.7, 0.8, 0.9]，则将 0 号个体、1 号个体、4 号个体、4 号个体、4 号个体拷贝到新种群中。自然选择的结果使种群更符合条件了。 -
交叉
假设个体 a、b 的基因是
a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
b = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]
这两个个体发生基因交换的概率 pc = 0.6。如果要发生基因交换，则产生一个随机数 point 表示基因交换的位置，假设 point = 4，则：
a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
b = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]
交换后为：
a = [1, 0, 0, 0, 1, 0, 1, 1, 1, 1]
b = [0, 0, 0, 1, 0, 1, 1, 1, 0, 0] -
变异
遍历每一个个体，假设基因的每一位发生突变（0 变为 1，1 变为 0）的概率 pm 为 0.001。突变可以增加解空间
