沉迷遗传算法无法自拔

Nero_Claudius · 2018-08-13 10:45:01 · 个人记录

前言

作为近似算法，遗传算法极其有效的避免了考场打不出正解的尴尬，提供了快速的骗分方法。

本文主要整理了遗传算法的一些相关内容，如有错误欢迎指正。

（另注：本文参考了网上的部分博客，但是内容全部为原创）

基本概念

基因型(genotype)：你生成的个体的编码。
表现型(phenotype)：个体解码之后得到的信息。
进化(evolution)：这个过程通过一些规则选择最优的进行繁殖。
适应度(fitness)：衡量一个个体的优秀程度。规则与具体题目相关。
选择(selection)：这个过程通过一些规则把OK的留下来。
复制(reproduction)：繁殖的时候个体的一部分会原封不动的进入新个体。
交叉(crossover)：相当于杂交，两个个体的部分混在一起产生新个体。
变异(mutation)：以一个很小的概率改变个体某一位上的值。
编码(coding)：就是表现型到基因型的转换规则。
解码(decoding)：上面的反过来。
个体（individual）：这个可以忽略，都是废话。
种群（population）：一群个体。

初始化

要开始进行整个算法核心，你首先需要一整个种群。

种群由随机生成的个体组成，当然数量不能太少（要不然随便一会儿就没人了），当然也不能太多（会炸）。

个体的生成方式较多，最显然的是二进制编码，当然也有三进制编码四进制编码（其实说白了因题而异）。

还有一种现在比较常用的是浮点数编码，就是对于每个基因值用某一范围内的一个浮点数来表示。

对于对精度需求较高的题目，二进制编码较浮点数编码弱很多。

其他还有很多乱七八糟的编码，就不一一介绍了。

选择

选择算法有很多优化，思路都挺好理解的。

轮盘赌选择（Roulette Wheel Selection）：根据适应度得到每个元素被选中的概率，随机选择。
随机竞争选择（Stochastic Tournament）：就是每次用上面的随机挑两个，然后适应度大的获胜。
最佳保留选择：也被叫做“精英主义选择”，就是把最佳的个体原封不动传到下一代。
无回放随机选择（也叫期望值选择Excepted Value Selection）：类似轮盘赌，但是不以适应度作为选择标准，而以（下一轮中的）生存指数作为选择标准:
- （1）计算每个个体在下一代群体中的生存指数。
- （2）若某一个体被选中参与交叉运算，则它在下一代中的生存指数减去0.5，若某一个体未被选中参与交叉运算，则它在下一代中的生存指数减去1.0。
- （3）随着选择过程的进行，若某一个体的生存指数小于0（铁定扑街）时，则该个体就不再有机会被选中。
确定式选择：和上面的类似，但是没有随机化过程。具体操作过程如下：
- （1）计算群体中各个个体在下一代群体中的期望指数。
- （2）用生存指数的整数部分确定各个对应个体在下一代群体中的生存数目。
- （3）用生存指数的小数部分对个体进行降序排列，顺序取前M个个体加入到下一代群体中。至此可完全确定出下一代群体中M个个体。
无回放余数随机选择：算一下平均适应度，然后大于平均值的都OK。
均匀排序：类似轮盘赌，但根据适应度排序来随机选择。
最佳保存策略：类似精英主义选择，用每一次的精英去替换交叉和突变中最不佳的个体。
随机联赛选择：每次随机选好几个个体，把其中适应度最高的遗传下去。
排挤选择：法如其名，子代替代相似的父代。

特殊策略

由于仍然可能得到局部最优解，所以可以选择添加优化来尽量规避。

灭绝：为了避免得到的是局部最优解，可以设定如果在第n轮前都没有得到比现行解更优的解，那就灭绝现在的最优解；如果再次达到现在的最优解则不灭绝。

交叉

单点交叉（One-point Crossover）：在个体的编码随机设置一个交叉点，然后再该点相互交换两个个体的部分染色体。
两点交叉（Two-point Crossover）：在个体的编码随机设置两个交叉点，然后再进行部分基因交换。
多点交叉（Multi-point Crossover）：参考两点交叉，替换为多点即可。
均匀交叉（也称一致交叉，Uniform Crossover）：两个个体的编码的每一个对应位都均匀随机地选择换位与否。
算术交叉（Arithmetic Crossover）：不再单纯的交换，而是通过计算直接得出新的子代（据说一般适用于浮点数编码）。

突变

基本位变异（Simple Mutation）：对于个体编码的每一个值，随机判断是否变异。
均匀变异（Uniform Mutation）：求出一个平均值，然后以较小的几率将其与当前位互换。（特别适用于在算法的初级运行阶段）
边界变异（Boundary Mutation）：随机取上界或下界替换当前位。
非均匀变异：乱搞操作，随便动一动编码，然后就OjbK了。

常数

这里以【开心的金明】为例，测试各种常数配置的结果：

1. 全部函数选取最简单：

TEST1
种群大小：1000
循环次数：100000
交叉概率：0.3
突变概率：0.01
分数：20

TEST2
种群大小：10000
循环次数：1000
交叉概率：0.3
突变概率：0.1
分数：60

TEST3
种群大小：10000
循环次数：1000
交叉概率：0.7
突变概率：0.1
分数：40

TEST4
种群大小：10000
循环次数：1000
交叉概率：0.5
突变概率：0.1
分数：30

TEST5
种群大小：10000
循环次数：1000
交叉概率：1
突变概率：0.1
分数：30

TEST6
种群大小：10000
循环次数：1000
交叉概率：0.1
突变概率：0.1
分数：40

TEST7
种群大小：10000
循环次数：1000
交叉概率：0.3
突变概率：0.07
分数：30

TEST8
种群大小：10000
循环次数：1000
交叉概率：0.3
突变概率：0.05
分数：40

TEST9
种群大小：10000
循环次数：1000
交叉概率：0.3
突变概率：0.3
分数：50

TEST10
种群大小：10000
循环次数：1000
交叉概率：0.3
突变概率：0.9
分数：40

2. 增加用进废退，淘汰末尾子代：

TEST1
种群大小：10000
循环次数：1000
交叉概率：0.3
突变概率：0.1
分数：40

TEST2
种群大小：100
循环次数：100000
交叉概率：0.3
突变概率：0.1
分数：30

TEST3
种群大小：10
循环次数：1000000
交叉概率：0.3
突变概率：0.1
分数：0

TEST4
种群大小：100000
循环次数：100
交叉概率：0.3
突变概率：0.1
分数：60

TEST4
种群大小：100000
循环次数：100
交叉概率：0.3
突变概率：0.15
分数：60

TEST5
种群大小：10000
循环次数：1000
交叉概率：0.3
突变概率：0.15
分数：40

2. 增加灭绝，每100代如果当前最优解未出现过，消灭当前最优解：

资料来源：

超详细的遗传算法