概述
遗传算法是什么？以下是某个知乎牛人的解释，个人觉得很有趣，遂引用之：
我想让机器人Bob画出我的梦中情人（最优解）。Bob当然不知道我梦中情人长啥样。
Bob很无奈，只能一张张试。先画一张，问我像不像？我说不像，Bob就重新画一张。直到我觉得像。
然而Bob又不会画画，只会填格子。于是Bob准备了一张1000*1000的格子纸，每个格子可以填黑色或者白色。那么总共有2^1000000种画法。如果我能坚持到宇宙毁灭N次，那可以每张都看，然后找到那个最像的。显然我没这个耐心。
于是我只让Bob画10万张，画不出来我就砸了它。
Bob很紧张，开始想办法，终于想到了遗传算法。
第一轮，Bob随机画了1万张（初始种群）。这1万张里面，肯定各种乱七八糟，有像星空的，像猪的，像石头的，等等。然后Bob让我挑最像的。妈蛋，我强忍怒火，挑出来一堆猪、猴、狗，好歹是哺乳动物。
Bob拿着我挑的“猪猴狗们”，如获至宝，开始第二轮，将这些画各种交叉变异一下。比如把一幅画的耳朵跟另一幅的鼻子换一下，或者再随机改个眼睛。然后又生成了1万张图让我挑。我挑出来一堆猴子猩猩，好歹是灵长类动物。
如此反复好多轮后，挑出来的开始像人了，虽然有男人、女人、小孩。
慢慢地，开始有美女了。再慢慢地，就越来越像了。
在画了10万张图后，终于找到一张还不错的。虽然不是梦中情人，但也很不错呐（次优解）。
这就是遗传算法。
作者：赵志强
链接：https://www.zhihu.com/question/23293449/answer/120102627
遗传算法（GA，Genetic Algorithm），顾名思义，应该跟遗传学有关的。没错，遗传算法是模拟种群优胜劣汰的进化机制而提出的一种启发式算法，是一种高效、并行、全局搜索的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最佳解。
种群 生物的进化是以集团的形式共同进行的, 这样的一个团体称为种群，组成种群的单个生物称为个体, 每个个体对生存环境都有不同的适应能力, 这种适应能力称为个体的适应度(Fitness)。
优胜劣汰 按照达尔文的进化论, 那些具有较强适应环境变化能力的生物个体具有更高的生存能力, 容易存话下来, 并有较多的机会产生后代；相反, 具有较低生存能力的个体则被淘汰, 或者产生后代的机会越来越少, 直至消亡。达尔文把这一过程和现象叫做“自然选择, 适者生存”。
进化 种群在其延续生存的过程中，逐渐适应生存环境，品质不断得到改良，这种现象称为进化。
启发式算法 一个基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个，该可行解与最优解的偏离程度一般不能被预计。模拟退火、鱼群算法、粒子群算法等也属于启发式算法。
遗传算法原理
种群和适应性函数
种群和适应性函数是遗传算法的两个输入，其中：
种群代表“基因”，是对问题的解的一种编码方案，可以是二进制编码，浮点数编码或者其他类型的编码。种群的每一个个体都初始化为不同的基因型。
适应性函数代表“大自然”，可以理解为评价函数，用来评价个体对环境的适应程度。
遗传算法基本流程
遗传算法的基本流程可以用下图表示：
GA基本流程
GA基本运算过程：
a)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。
b)个体评价：计算群体P(t)中各个个体的适应度。
c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。
d)交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。
e)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。
f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。
以上为遗传算法的基本流程，实际应用时还会有很多额外的“规则”以确保进化方向最优、增大随机性，比如“精英策略”、“多点交叉”、“多点变异”等等。详见下图：
GA详解
遗传算法应用
组合优化问题
旅行商问题，即TSP（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
TSP示意图（https://www.jqr.com/article/000390）
这里有完整的实现过程和代码
TSP是一个典型的组合优化问题。此外， 背包问题、装箱问题、图形划分问题等也属于组合优化问题，也是遗传算法较为成功的应用领域。
此外，GA也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。
函数优化问题
函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。
比如：求解函数 f(x) = x + 10sin(5x) + 7cos(4x) 在区间[0,9]的最大值。(https://www.zhihu.com/question/23293449)
image.png
这个函数看上去是如此奇怪，如果让我们去求它的最大值，完全不知道如何下手，但是不管一个函数的形状多么奇怪，遗传算法都能在很短的时间内找到它在一个区间内的(近似)最大值。
这里有完整的实现过程和代码
车间调度问题
车间调度问题是一个典型的NP-Hard问题，遗传算法作为一种经典的智能算法广泛用于车间调度中，很多学者都致力于用遗传算法解决车间调度问题，现今也取得了十分丰硕的成果。从最初的传统车间调度（JSP）问题到柔性作业车间调度问题（FJSP），遗传算法都有优异的表现，在很多算例中都得到了最优或近优解。
其他应用
用遗传算法作画，有兴趣可以玩玩(https://alteredqualia.com/visualization/evolve/)，上传一张图片，GA自己学习用三角形组合出原图。
综上所述，遗传算法似乎擅长解决目标未知或难以描述、但却知道怎么评估的一类问题。
网友评论