遗传算法（1）

遗传算法（Genetic algorithm）

一群扇贝在海边生活繁衍，但海边的渔民会捕捞扇贝，而这些渔民的家族图腾是 POJO 的图标(或者其他任意一个图标都行)，所以渔民总是选择那些贝壳花纹长得比较不像 POJO 图标的扇贝，长此以往，扇贝的贝壳的花纹都会演化成很像 POJO 图标。

• 在一代代演化的过程中，父母扇贝的基因组合产生新扇贝，所以遗传算法会选择两个原有的扇贝，然后对这两个扇贝的染色体进行随机交叉形成新的扇贝
• 迭代演化也会造成基因突变，遗传算法让新产生扇贝的基因以较小的概率发生变异。也就是说，染色体的像素值随机改变
• 对扇贝像素值和 POJO 图标进行逐一评价，颜色相差得越大的显然表示越不像
• 这个评价的函数叫做“适应度函数”，它负责评价与 POJO 的相似程度

遗传交叉

遗传变异

遗传算法 (Genetic algorithm) 是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法首先依据某种方式（通常是随机）生成一组候选解，之后，候选解中的个体通过交叉和变异产生新的解群，再在这个解群中选取较优的个体产生新一代的候选解，重复此过程，直到满足某种收敛指标为止。

相关概念

种群（population）

就是组候选解的集合，遗传算法正是通过种群的迭代进化，实现了最优解或者近似最优解。

个体（individual）

一个个体对应一个解，也就是构成种群的基本单元。在遗传算法中，需要把一个解构造成染色体（chromosome）的形式，如同在扇贝例子中，通过染色体来表示一个扇贝花纹图案，这个过程也被称为编码。而当算法结束时，需要把最优的染色体还原成最优解，这个过程称为解码。

基因（gene）

染色体是由基因组成的，所以把组成遗传算法染色体（个体）的基本部分称为基因，基因的选择可以多种多样。比如在扇贝例子中，我们用像素作为基因，但实际上扇贝例子的原文是用不同的三角形块作为基因，通过不同三角形块的叠加形成 POJO 图案。在实际中，遗传算法广泛用到的一种基因是 0、1 比特，0、1 比特基因形成的染色体是一个二进制串。

交叉（crossover）

交叉是将两个父代个体的部分基因进行交换，从而形成两个新的个体。最简单的交叉如同扇贝例子，在染色体上寻找一个点，然后进行相互交叉，这种交叉称为单点交叉（one-point crossover）。除了单点交叉（交叉染色体中的一个点），交叉操作还包括：

• 多点交叉（Multi-point Crossover）：交叉染色体中的一段基因
• 均匀交叉（Uniform Crossover）：随机生成一个染色体编码，按照 0、1 比特交叉出新的染色体 1’ 和染色体 2’ ，例如当前基因是 0 就不交叉，是 1 就交叉
• 洗牌交叉（Shuffle Crossover）：染色体交叉之前将基因打乱，然后进行单点交叉，再复原至洗牌前原位置

变异（mutation）

按照一定的概率将个体中的基因值用其它基因值来替换，从而形成一个新的个体。如同自然界中生物的变异概率较小，在遗传算法中基因的变异概率也应该设置为较小。

选择（selection）

在目前的种群中（通常是上一代的种群和新生产的种群的结合）选择一定数量的较优个体，形成新的种群。选择是通过适应度函数 做出的，其中 为个体。 在轮盘赌中，需要计算每个个体的选择概率 ：

• 线性排序选择（Linear-rank selection）

通常 ， ,这种赋值使得

• 指数排序选择（Exponential-rank selection） 其中位于区间（0， 1）， 越小，最优个体被选择的概率就越大

• 锦标赛选择（Tournament selection）：在种群中随机选择 个样本，在这 个样本中，选择适应度函数最好的个体作为下一代的个体，之后将样本回放，重复采用和选择直到选出一定数目的个体。

具体算法

Algorithm 遗传算法

1. Input： 适应度函数 ，种群个体数目 ，个体编码长度 ，最大迭代次数 ，种群差异阈值 ，交叉概率 ，变异概率
2. Output： 最优解
3. 初始化： ，按照编码随机生成 的个体
4. repeat
5.   /* 选择流程 */
6.   在 中按照轮盘赌算法选择 个个体
7.   /* 单点交叉流程 */
8.   for i = 1 to n - 1 do
9.     if then
10.       随机选择一个交叉点：;
11.       对 和 在 点进行单点交叉
12.     end if
13.   end for
14.   /* 变异流程 */
15. for 中的每一个个体 do
16.     for j = 1 to m do
17.       if then
18.         对基因 从 处开始进行变异（如果是0，1基因编码，翻转即可）
19.       end if
20.     end for
21.   end for
22.  
23. until 或者
24. 选择 中的最优个体
25. return 对个体 进行解码

具体实例

求解函数的最大 / 最小值，要求精度小数点后 5 位

将区间 [ - 2 , 2 ] 划分 等份，因为
，所以编码的长度应该设置为 m = 19 比特，编码表示例如：011 0100 1110 1001 1010

注：会有部分编码超出表示，这部分超出的称为非法编码

旅行商问题

旅行商问题的个体定义是比较直观的，如有 10 个城市，将个城市从 1 到 10 进行编号，每个编号就是个体的基因，所以一个个体就是 1 到 10 的一个排序，代表了城市的访问顺序。例如：

个体 1 ：8 2 5 9 1 6 3 10 7 4
个体 2 ：4 8 7 2 5 1 10 3 6 9

单点交叉后可能出现非法解，即同一个个体有两个相同的数字，表意为去到相同的城市，就存在城市未达

解决办法：

• 部分匹配交叉（Partially Mapped Crossover）：保留交叉来的基因，通过改变原有未交叉部分的基因去适配
• 顺序交叉（Order Crossover）：记录交叉来的基因，取出原染色体的基因排列（从第二刀位置开始）并剔除交叉来的基因，剩余部分依次填空

4 8 7 | 2 5 1 10 | 3 6 9
排列应该是 3 6 9 4 8 7 2 5 1 10（剔除换来的）
剔除后填入
2 5 10 | 9 1 6 3 | 4 8 7
一般是从第二刀开始

变异：

• 选择染色体中的两个基因交换
• 截取一段内部重新排序