Genetic Algorithm
1. 基本操作
选择、交叉、变异
1.1 选择
-
群体规模 \(N\)
-
\(N\) 个染色体的适应值为 \(F(x_i)\)
-
每个染色体被选中的概率为：所有染色体的适应值之和分之单个染色体的适应值
显然，适应值越大，被选中概率越大
区分适应值与指标值
适应值 \(F(x_i)\) 是算法中用来评估染色体的，指标值 \(f(x_i)\) 是实际问题中需要优化的指标、结果。
适应值可以直接取指标值，也可以取其它的。
1.1.1 随机 - 轮盘赌
模拟轮盘赌的算法
1.1.2 “确定性”法
不用随机数，按照概率选取 \(N\) 个染色体的方法：
-
期望值 \(e(x_i) = p(x_i) N\) ，但是这个数不一定是整数
-
先选择整数部分，向下取整；一共： \(\sum\lfloor e(x_i) \rfloor\)
-
如何选取剩下的 \(N - \sum_{i=1}^N\lfloor e(x_i) \rfloor\) ？
对 \(e_i - \lfloor e(x_i) \rfloor\) 从大到小排序，依次选出。相当于优先选整数部分与期望值差得多的。
1.2 交叉
双亲的两个染色体，交叉产生新的染色体。
二进制编码交叉：随机产生交叉位，然后两边互换。以下是双亲双子法：
1.3 变异
发生在染色体二进制编码的某一位上；0、1互换。
2. 算法框架
给定群体规模 \(N\) ，交叉概率 \(p_c\) （较大），变异概率 \(p_m\) （较小）。
进化：迭代以下流程：
- （初始）群体 ← 随机生成 \(N\) 个染色体
- 对每一染色体计算适应值；根据当前适应值，决定是否继续。
- 种群 ← 计算概率 \(p(x_i)\) ，选择 \(N\) 个染色体
- 交叉得到新染色体
- 随机两两配对
- 随机交叉点位置
- 配对染色体之间交叉互换
- 新群体 ← 未交叉的染色体 + 交叉得到的新染色体
- 变异：变异概率 \(p_m\) 对染色体（逐位）变异
整个进化过程中，适应值最大的染色体作为最终的最优解。
3. 相关技巧
3.1 评价
如何监视算法的变化趋势？
3.1.1 当前最好法
观察整个进化过程中最好解的变化。
3.1.2 在线比较法
计算当前代中所有染色体的指标值的平均值：
3.1.3 离线比较法
计算进化过程中每代最好解的指标值的平均值：
3.2 适应函数
但在有些情况下，指标函数在最大值附近的变化可能会非常小，以至于适应值非常接近，很难区分出那个染色体占优。
找新的适应函数，其与问题的指标函数具有相同的变化趋势，但变化的速度更快。
3.2.1 非线性加速
3.2.2 线性加速
3.3 整数编码
考虑旅行商问题，可以这样二进制编码：
但这样的二进制编码空间是很稀疏的。
为了解决二进制编码空间稀疏的问题，考虑使用整数编码方案。
对于整数编码，交叉、变异方式有：
3.3.1 交叉
3.3.1.1 常规交叉
子代前一半继承对应的父代，后一半是前一半未出现的数字，按交叉的父代的顺序排列。
3.3.1.2 次序交叉
P1: 1 2 3 4 5 6 7 8 9 10
P2: 5 9 2 4 6 1 10 7 3 8
Select: * * * *
P2': ? 9 ? 4 6 1 10 7 ? ?
C1: 2 9 3 4 6 1 10 7 5 8
生成子代1的过程：
- 随机选取一些位置，对应「亲代1」中的子数字序列 \(s_1\)
- 在「亲代2」中删掉 \(s_1\) 中的数字，留空
- 在「亲代2」上一步的留空中填入 \(s_1\)
本质上，就是把「亲代2」中 \(s_1\) 里的那些数字按照「亲代1」中的顺序重排。
3.3.1.3 映射交叉
在双亲的对应位置上选取「映射对」，选取几个映射对，构成一套映射关系。
据此映射关系，替换亲代中的数字，产生两个子代。
3.3.2 变异
3.3.2.1 位置变异
随机产生两个变异位，将第二个变异位上的基因移动到第一变异位之前。
3.3.2.2 次序变异
随机产生两个变异位，交换之。
3.3.2.3 打乱变异
随机选取染色体上的一段，然后打乱在该段内的基因次序。