[Github源码链接](https://github.com/Code-Bullet/Google-Chrome-Dino-Game-AI)
什么是遗传算法？
遗传算法的由来
Species to survive, is not the most strong, is not the most intelligent， but those who make a rapid response to change.
物尽天择，适者生存。
查尔斯达尔文在一百多年前提出的“生物进化论”，他证明生物的起源是在遗传、变异、生存斗争和自然选择中，从简单到复杂、从低等到高等不断地发展变化而来的。
达尔文的进化论给美国的科学家霍兰德留下了深刻的印象，他从计算机角度思考了这个问题，也就是遗传算法的由来。
遗传算法也便继承了“进化论”的思想，将需要解决的问题模拟成一个生物进化的过程，通过复制、交叉、突变等操作产生下一代的解，并逐步淘汰适应度(Fitness)低的解，经过N代自然选择后，会进化出适应度函数值很高的个体。
定义：
遗传算法（Genetic Algorithm, GA）起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最佳解。
相关术语
| 相关术语 | 解释 |
|---|---|
| 基因型(genotype) | 性状染色体的内部表现 |
| 表现型(phenotype) | 染色体决定的性状的外部表现，或者说，根据基因型形成的个体的外部表现 |
| 进化(evolution) | 种群逐渐适应生存环境，品质不断得到改良。生物的进化是以种群的形式进行的 |
| 适应度(fitness) | 度量某个物种对于生存环境的适应程度 |
| 选择(selection) | 以一定的概率从种群中选择若干个个体。一般，选择过程是一种基于适应度的优胜劣汰的过程 |
| 复制(reproduction) | 细胞分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。 |
| 交叉(crossover) | 两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交 |
| 变异(mutation) | 复制时可能（很小的概率）产生某些复制差错，变异产生新的染色体，表现出新的性状 |
| 编码(coding) | DNA中遗传信息在一个长链上按一定的模式排列。遗传编码可看作从表现型到基因型的映射 |
| 解码(decoding) | 基因型到表现型的映射 |
| 个体（individual） | 指染色体带有特征的实体 |
| 种群（population） | 个体的集合，该集合内个体数称为种群的大小 |
遗传算法的应用
遗传算法的有趣应用很多，诸如寻路问题，8数码问题，囚犯困境，动作控制，找圆心问题（在一个不规则的多边形中，寻找一个包含在该多边形内的最大圆圈的圆心），TSP问题，生产调度，模式识别，神经网络，自适应控制等。
一个简单的例子
求解函数 f(x) = x + 10*sin(5*x) + 7*cos(4*x) 在区间[0,9]的最大值
那么如何通过遗传算法找到这个函数的最大值呢？
事实上，不管一个函数的形状多么奇怪，遗传算法都能在很短的时间内找到它在一个区间内的(近似)最大值。
👉具体分析
遗传算法思想
GA的组成：
- 编码(产生初始种群)👉创造染色体
- 个体👉种群
- 适应度函数
- 遗传算子(选择、交叉、变异)
- 运行参数
- 种群大小
- 染色体长度
- 最大迭代次数
- 交叉概率
- 变异概率
- 是否选择精英操作
GA算法特点
遗传算法的优点
- 群体搜索，易于并行化处理；
- 不是盲目穷举，而是启发式搜索；
- 适应度函数不受连续、可微等条件的约束，适用范围很广。
- 容易实现。一旦有了一个遗传算法的程序，如果想解决一个新的问题，只需针对新的问题重新进行基因编码就行；如果编码方法也相同，那只需要改变一下适应度函数就可以了。
遗传算法的缺点
- 全局搜索能力不强,很容易陷入局部最优解跳不出来；(可结合SA进行改进,因为SA在理率上是100%得到全局最优的,但搜索代价高)
将遗传算法用于解决各种实际问题后，人们发现遣传算法也会由于各种原因过早向目标函数的局部最优解收敛，从而很难找到全局最优解。其中有些是由于目标函数的特性造成的，例如函数具有欺骗性，不满足构造模块假说等等；另外一些则是由于算法设计不当。为此，不断有人对遗传算法提出各种各样的改进方案。例如：针对原先的定长二进制编码方案；提出了动态编码、实数编码等改进方案；针对按比例的选择机制，提出了竞争选择、按续挑选等改进方案；针对原先的一点交算子，提出了两点交、多点交、均匀交等算子；针对原先遗传算法各控制参数在进化过程中不变的情况，提出了退化遗传算法、自适应遗传算法等。另外，针对不同问题还出现了分布式遗传算法、并行遗传算法等等。