本人写这样一篇文章的目的在于提供一张学习遗传算法的地图。实现的主要工具是MATLAB和其自带的全局优化工具箱 Global Optimization Toolbox。无论读者是来自工程、科学或者其他任何领域，希望看完文章之后都能实现自己的遗传算法！欢迎留言交流。
如何通俗易懂地解释遗传算法？有什么例子？www.zhihu.com知乎上也有相关的问题，可以看下前两个高赞回答对于养成直觉上的理解很有帮助。
遗传算法 (Genetic Algorithm) 是一种基于自然选择启发式的随机并行搜索优化方法。该算法特殊之处在于其借鉴了进化生物学中的很多概念，其中包括遗传、突变、自然选择和杂交等。抽象的来说，我们将会学到怎么模拟一个人工种群的进化过程。相比基于梯度的传统优化方法，遗传算法可以解决不连续、不可微的目标函数的优化问题。尤其擅长解决时间表安排 (例如为一个大学安排不冲突的课表)， 在下一篇文章中我们将会看到一个具体的例子和代码。
1.1 遗传算法流水线 (pipeline)
0）预处理：编码优化问题。
1）随机初始化一定数量的初始种群，种群中每一个个体(提前编码成二进制形式)代表优化问题的一个候选解。从生物学意义上来说，我们可以认为个体代表染色体或者基因片段。
2）通过遗传算子(genetic operator)进化至下一代种群。算子的主要构成：
3）满足终止条件(stopping criteria)后，选出迭代进化的种群中最优个体。
以上部分参考了MATLAB的GA官方文档：
How the Genetic Algorithm Worksww2.mathworks.cn1.2 可调节参数
关于调参的细节请参见官方文档：
Genetic Algorithmww2.mathworks.cn接下来我们通过一个具体的优化例子，来进一步认识以上提及的概念：
求解函数
画出函数图像和：
*注释：在遗传算法优化中，我们默认求的是最大值问题
*注释：我们这个例子中
2.1 编码和解码 (code and decode)
遗传算法的第一步是对优化问题进行编码，映射到一个方便基因进化的码空间。主要存在实数编码和二进制编码两种方式。在这个例子中，我们采用传统上偏向的二进制编码。其具有稳定性高、种群多样性(diversity)等优点，但需要的存储空间较大而且解码过程不易理解。
假设我们求解的精度为小数点后四位，即
类似的，解码过程就是一个逆向的从码空间映射到解空间的过程。对于二进制编码，每个二进制基因串都可以翻译成一个十进制的实数值。这个我们都很熟悉，
请注意这里是从左至右进行转码的。然后再把这个十进制实数映射到相应的区间，我们知道
通过对区间编码过程的观察，我们构造以下映射并验证其合理性：
接着完成我们前面选定个体的解码过程，
2.2 初始化种群
接着我们随机生成一定数量的个体。如果知道种群的实际分布，当然可以按照此分布提高初始种群的质量。初始种群的数量很重要，如果初始种群数量过多，算法会占用大量系统资源；如果初始种群数量过少，算法很可能忽略掉最优解。
function假设初始种群大小 n = 5，染色体长度 m = 16。得到以下码空间内部的初始种群矩阵：
2.3 适应度函数
接下来我们解码到解空间中，并评分得到每个个体的原始适应成绩 (raw fitness score)。
function如果我们给前面初始的种群
其中第4个染色体的表现似乎最好，不如直接选为精英个体(elite)保留到下一代，就不给他脱单的机会了：）。。。接着我们可视化一下这些初始个体：
*注释：遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优。如果一个优化问题没有确切的适应度函数表征个体好坏的问题，算法会失去进化导向。
2.4 (可选) 原始适应成绩的缩放(scaling)和排序(rank)
缩放的目的在于让选择机制更好的运行。如果缩放后的期望值范围太大，表现最好的个体可能繁衍过快，与很多其他个体交换基因从而导致种群的基因库里充斥着这个单一个体的基因，损失多样性。这种现象被称之为早熟，算法会快速收敛到局部最优解而非全局最优解。在相反的情况下，如果缩放后的期望值变化范围很小，每个个体能繁衍后代的几率都差不多。这会导致算法收敛的很慢。。。排序是将种群中的个体按照适应度从小到大进行排列。
[2.5 选择机制
接着我们来看一下常用的轮盘赌博（Roulette Wheel Selection）选择法。根据上面5个染色体的例子，他们作为一个种群的原始总评分为:
每个染色体被选择的概率是：
比方说个体一被选中的概率就是
那么算法上，具体要怎么做才能让第一个个体被选中的概率正好等于
function*注释：这里只选了一个精英个体，读者不妨试试选择多个精英个体会产生怎么样的影响。
在上面这个轮盘赌博算法中，我默认了精英选择机制。也就是说，把这一代的最优解自动保留到下一代。然后在剩下的基因库里选择父代和母代，接着我们前面的例子：
细心的读者会发现，我们没有让每代的精英在他所在的时代繁衍的机会。但这不意味着在下一代，他没机会脱单。也就是说只要你足够优秀老牛吃嫩草是完全可能的。。。我们接着来看看这一个初始种群是怎么通过遗传算子进化到下一代的。
2.6 变异(mutation)和交叉操作(crossover)
选定好父代和母代之后，进入交配过程。一般的遗传算法都有一个交配概率
然后交配点在4个基因位，产生的孩子便会是
function还是回到我们前面的例子，设定
再下一步是突变，通过突变产生新的“子”个体。一般遗传算法都有一个固定的突变常数
function*注释：这里我们每次只允许一个基因点变异其实是限制了遗传多样性的。
设定突变概率
接着我们可视化一下第二代种群的适应程度：
可以看出，种群的累计适应度是按照我们给出的进化方向上升了的。但是由于我们初始种群数量太小，基因库同化趋势比较明显（3个个体都集中在同一处）。我们可以大胆预测，就算进化迭代20次以后依然很难达到全局最大值。不妨验证一下：
不出所料。这是个典型的例子：由于种群多样性的不足，使得我们无法跳出局部最大值。可以尝试的解决方案就是增大初始种群数量。
2.7 遗传算法主体程序
在搭建完以上的所有轮子之后，我们来看看算法的主体部分
function调参过后，运行多次遗传算法取结果最大值如下：
那么在搭建完我们自己的遗传算法（破铜烂铁轮子）之后，我们来看看官方的工具箱（军火库）该怎么使用。先从同样的例子开始讲解：
3.1 工具箱入门
求解函数
optimtool我们先打开优化工具箱，来到以下界面。选项是真的多。。不愧是MATLAB军火库。
*注释：默认GA工具箱找的全局最小值，所以我们最大值问题得通过取负号变换取得。
填写适应度函数 (Fitness function)以及上下限
3.2 可视化选项
我们选择可视化最优适应度
3.3 算子选项
往往现实当中遇到的实际问题不会像我们的例子这么简单，经常是带有约束条件的。那我们接下来具体看看第二个例子：
读者若有多余的时间不妨尝试挑战以下问题：