Genetic Algorithm (GA) 遗传算法
遗传算法是对达尔文生物进化的自然选择以及遗传学原理的生物进化过程的计算模型
GA
Created 2021.02.10 by William Yu; Last modified: 2021.02.10-V1.0.0
Contact: windmillyucong@163.com
Copyleft! 2021 William Yu. Some rights reserved.
References
- https://www.jianshu.com/p/ae5157c26af9
- https://zhuanlan.zhihu.com/p/136393730
- NS-GA https://www.sciencedirect.com/science/article/pii/S1877705811022466
Basic Concept
Words & Sentence
基因与染色体
- 染色体：一条染色体是问题的一个可行的解决方案，每个个体具有一条染色体
- 基因：一个解决方案有很多元素构成，每个元素即 染色体的一个基因
- 个体：染色体的载体，可以理解为等同于染色体(因为每个个体只具有一条染色体) 即一种可行的解决方案
- 种群：个体的集合，即可行的解决方案集合
编码与解码
- 解决方案 -> 基因编码 的过程为编码
- 基因编码 -> 解决方案 的过程为解码
- 编码方式
- 二进制编码
- 实数编码
适应度函数
- 函数输入：某染色体
- 函数输出：该染色体的适应度
- 淘汰适应度较低的染色体
- 保留适应度较高的染色体
- 适应度函数是遗传算法进化的动力，相当于“自然选择”的标准
进化
- 进化有3个步骤：选择、交叉、变异
- 每一次进化迭代，产生N条染色体，N即种群容量，是个定值
选择 Selection
- 上一代种群中选择多对较优个体，一对个体为一对父母
- 究竟选择几对呢？
- 怎么选？
- 轮盘赌： 对当前群体中的所有染色体计算适应度，某个体被选中的概率与个体的适应度成正比
- 轮盘赌具有随机性，可能会丢掉较好个体，所以增加精英机制：复制
复制
- 每次进化中，为了保留上一代的优良染色体，将上一代中适应度最高的几条染色体原封不动复制给下一代。类似于，适应度高的个体多活几年
交叉 Crossover
- 父 + 母的染色体，生成子代的染色体
- 一对父母产生几个子代呢？ 一个或多个应该都行吧
- 交叉概率 cross_rate
- 交叉方法
- 单点交叉
- 按照交叉概率 cross_rate，生成随机数x，选父染色体的前百分之x，母染色体的后百分之x，拼成子染色体
- 其他交叉方法
- 单点交叉
变异 Mutation
- 不引入变异，算法容易收敛到局部最优解
- 变异概率 mutate_rate
- 单点变异：在交叉生成一条新的染色体后，在染色体上面随机选择若干个基因，然后随机修改该基因的值
- 其他变异方法
算法模型
Input
参数
- 种群大小 N
- 染色体基因数
- 交叉概率
- 变异概率
- 精英选择比例
- 收敛条件
- 迭代次数
- 精度要求
方法
- 适应度函数
- 交叉方法
- 变异方法
Process
- init
- 随机初始化N条染色体
- 计算当前种群中每个个体各自的适应度
- 精英保留
- 根据适应度轮盘赌选择多对父母
- 父母交叉产生子代
- 新产生的子代变异
- 检查是否满足收敛条件
- 满足，算法结束，由子代最优基本解码解决方案
- 不满足，重复步骤2,3,4,5,6
整体上分析，遗传算法其实相当于
- 在一个可行解空间内，随机尝试N次，
- 在N次结果中较优的那些解附近，再随机尝试总计N次，
- 以上步骤重复，很简单的逻辑
Code
// todo(congyu)
Contact
Feel free to contact me windmillyucong@163.com anytime for anything.
