《Java遗传算法编程》笔记

之前读完了《Java遗传算法编程》。感觉上这本书并不是很注重程序的设计及效率问题，但确实将遗传算法讲解清晰了。这里就记录一些不是很熟悉的概念。

一、选择

1.1 竞标赛

从种群中随机选取一定量的个体，选择其中适应度较高的个体。锦标赛作用在于，个体适应度越高，被选中进行杂交的几率越大。

锦标赛规模过大影响效率，且更容易抽中适应度较高的个体，导致多样性下降。而过小的规模会减小选择压力，减慢算法进展。

二、交叉

2.1 均匀交叉

每个基因都均有50%的概率来自双亲的其中一方。

2.2 单点交叉

在基因组中随机选取一个位置，这个位置之前所有基因和之后的所有基因分别来自两个亲代对应位置的基因。

常用于指令由多个基因编码的情况。以此使指令不被改变修改。

缺陷

1. 单点交叉造成无法杂交出亲代的某些基因组合（如00100和10001使用单点交叉无法产生10101）。当然，这点可以由变异补充。
2. 子代左侧基因有来自亲代1的偏向，右侧基因有来自亲代2的偏向。采用两点交叉可以解决这个问题。

2.3 两点交叉

在基因组中随机选取一个开始位置和一个结束位置。开始位置往右到结束位置取亲代1对应位置上的基因；结束位置往右到开始位置取亲代2对应位置上的基因。

三、优化

3.1 自适应遗传算法

基于算法，自动调整各种参数，以改进遗传算法性能。

例如，通常我们希望保留最佳个体，减少表现不好的个体。但一段时间后，种群开始收敛，个体开始靠近搜索空间中单个点。个体差异比较细微，搜索进程可能受阻。这种情况下应当略微提升变异率。

\(p_{m} = \left\{\begin{matrix}(f_{max} – f_{i}) / (f_{max} – f_{avg}) * m, f_{i} > f_{avg}
\\ m, f_{i} \leq f_{avg}
\end{matrix}\right.\)

获取种群最佳适应度，求出它与当前个体适应度的差。然后找到种群最佳适应度和种群平均适应度的差。将两个差相除，就可以用这个值缩放变异率了。（初始化自适应变异率时，所用的变异率为最大可能的变异率）

3.2 模拟退火

模拟退火有助于控制算法的收敛速度，以免算法在搜索空间的一个区域收敛太快。

温度（temperature）初始化为1，设置一个退化率（coolingRate）。每个世代执行一次退火操作（temperature *= 1 – coolingRate）。变异时，变异率乘温度得到此时的变异率。

四、其他

4.1 硬约束 & 软约束

硬约束决定解是否有效，软约束决定解的品质。具体做法可以是，破坏硬约束扣去100分，满足任何一个软约束增加1分、2分和三分（分数取决于软约束重要性）。使得软约束无法弥补硬约束的扣除。

最后附上书中源代码 https://github.com/apress/genetic-algorithms-in-java-basics