遗传算法初窥
初窥遗传算法编程
随着1950年 阿兰 图灵的一篇“Computing Machinery and Intelligence”（计算机器和智能）论文提出，在最近的20年 AI似乎成了一个当前最火的研究话题。虽然离完全可以复制人类智能的机器还很远，但这其中也出现了一批已经卓有成效的应用；苹果公司的Siri，谷歌和特斯拉的自动驾驶汽车等。我更愿意把后者称其为弱AI。弱AI更专注于某一方面，这也意味着它只需要更少的算法以及算力，在更短的时间就可以取得成果。
遗传算法
遗传算法或者说进化计算可以说是机器学习子集，遗产算法通常不是用来解决单一的或者说特定问题的最好方法；任何一个问题，几乎都会存在最优解。它是一个类似于瑞士军刀的多用途工具，好比你只是需要拧紧50个螺丝那么你会毫不犹豫的选择螺丝刀，但是你的任务如果是拧几个螺丝然后还要去砍柴，接着在开一瓶汽水奖励自己刚刚的劳动成果，那瑞士军刀无疑是最好的选择。 另外一个原因：相比于复杂的神经网络算法需要高深的数学它明显更适合我这样的初学者。
早期人工智能系统大部分采用生物学类比方式来作为指导人工智能的开发基石。20世纪50年代，科学家首次建立以达尔文的生物进化论思想为基础的进化算子理论。进化算子三个核心的概念 选择、交叉（生物繁殖的模拟）、变异（在遗产信息中添加新的基因组过程）。在这三种操作作用下使遗传算法能够出现进化新的解成为了可能。
进化计算的优势
一般的静态决策问题我们可以通过计算机来解决，但是随着可能的输入和输出的增加，这些问题的复杂度会以指数上升最后达到用人力来编写代码难以解决的困境。这时进化计算就有了用武之地了。有很多时候我们不知道如何解决一个问题或者说我们不知道这个问题的最优解是什么的时候。比较经典的例子：NASA（美国航空航天局），他们需要设计一个为了满足2006年的太空任务所有要求的天线，但是他们不知道该如何进行设计。他们写了一个遗传算法，进化出一个天线设计，满足所有具体的设计约束，如信号质量、尺寸、重要等。进化计算具备快速的适应性；对于需要大量搜索，来找到最够好的解或许是一个非常不错的方法。问题的特征值大概如下：
问题难以写代码解决
不知道如何解决
快速变化的问题
是否可以接收足够好的解
生物进化
进化论
因为遗传算法的指导思想就是达尔文的生物进化论，所以在我们开始探究遗传算法前我们有必要对生物进化的基础知识有必要的了解。
DNA：生物体的所有不同性状由他们编码构成
染色体：生物体的基因被分组放在染色体中，一套完整的染色体组成一个生物体的基因组。（染色体通常在遗传算法中被称为候选解）
交叉：两个相同的物种结合产生的后代，通常从第一亲代得到50%的DNA并从第二亲代获取另外50%的DNA。
变异：在交叉的过程中后代可能偶尔会携带不属于亲代的DNA，我们称之为变异。
进化：如果后代对于外部环境的适应足够好，那么他们会继续进行繁殖。如果未能适应外部环境则最终被淘汰。最终生存下来的个体适应性越来越强；这就是适者生存。
遗传算法中的重要概念
种群：变异和交叉的遗传操作应用的候选解集合
候选解：问题的可能解
基因：构建染色体的基础块。经典基因编码方式 0或1
染色体：基因串，它定义了一个特定的候选解。经典二进制编码染色体方式：01011110....
变异：基因随机改变的过程，用来创建新的性状（生物的多样性）
交叉：创建新的候选解诀方案的过程，也可以称之为重组
选择：从众多候选解中繁殖下一代解的技术
适应度：评估候选解适合给定问题的程度
搜索空间距离：在用二进制遗传表示时；如101于111将0翻转成1就能转化成111所以他们之间的搜索空间距离为1，其他依次类推。空间距离越近表示他们之间的特征值越相似。在许多搜索算法中也应用这一种以空间距离策略来优化搜索结果。
适应度景观
二维适应景观图，横轴一般表示我们需要优化的值，纵轴表示适应度值
简单连续二维适应度景观图：
简单连续二维适应度景观图，一般针对现实情况适应情况较少，可以解决优化解较少的情况。对于复杂的情况，构成搜索空间的解一般会超过亿级，我们如果通过解决每个解那时间复杂度太高（我们可以换算下1亿个解，每个解的计算耗费1秒 那么它的耗时超过3年）。现实情况我们面对的情况往往更复杂：我们可能只能看到我们搜索空间的一部分。也就是非连续二维适应度景观图
对于这种情况采用遗传算法和进化算法可以非常有效的提高我们获取可行或者接近最佳解的速度。当然前提是我们可以接受最接近解这一方案才行。
遗传算法在进行搜索空间搜索时引入了种群的概念，但是需要两个假设的前提：
两个适应度不错的解可以进行组合，可以形成一个更加强壮的后代。这里其实隐含了两个操作；选择交叉（繁殖下一代的过程），形成更强壮一代（引入了精英模式 elitism）对于精英模式后文我进行说明
为了解决下一代在搜索空间中跨出一步来进行解优化，需要在遗传算法中引入变异算子。（具体的概念请看上文中提到的概念）
我们以登山算法为例：通过gif图我们可以看到种群最终到达某个峰顶
通过上图其实我们可以发现一个问题：局部最优问题，产生这个问题的原因是我们看不到整个适应度景观，正是由于这个原因我们的优化算法往往不知不觉进入了局部最优的死胡同。
解决局部最优问题，有很多中方式。在遗传算法中我们一般采用：让种群在搜索空间区域进行大面积的随机取样
其实我们上文提到的变异算子，本质上也可以在一定程度上优化局部最优问题。为什么说是一定程度，因为这需要我们的变异算子可以容许我们的解从一个位置跳到搜索空间的另外一个位置。如何调试变异算子的大小则需要我们耐心的进行调试运算了。变异算子过大会影响我们的种群规模评分适应度值的准确性；过小则算法可能需要过长的时间在搜索空间移动。
基因表示方式
基于二进制基因表示：优点：足够简单，对于交叉变异等操作友好。缺点：基因的变异对于编码值的改变带有不确定性。
使用浮点数表示：暂未研究
基于数表示：暂未研究
遗传算法终止条件
到达世代的最大数目
超过运算时间
发现满足条件解
到达稳定阶段
遗传算法搜素过程
算法开始，初始化种群（一般是随机）
为种群中的个体分配一个适应度值，并进行评估
评估完成后，检查是否到达终止条件
如果终止条件不满足，种群经过一个选择阶段。基于适应度评分。个体的适应度越高被选择的机会越大
针对选择的个体进行交叉和变异操纵，并生成下一代新个体
返回评估阶段。（一个循环称为一个世代）
如果条件满足则退出。并返回结果
遗传算法的实现
关于本文中提到的几个用例是根据 Burak kanber 书中所用的案例来进行。但是我会对其进行改进以及详细说明。
问题1:全一问题，发现全部由1构成的字符串，比如对于长度为5的字符串，最优解是 11111。
问题是一个足够简单的问题，我们有很多种方式来解决。但是我认为做为一个入门者来看。足够简单的问题如何运用遗传算法的知识来解决这个问题，对于后面解决复杂的问题是至关重要的。
