参考博客：https://zhuanlan.zhihu.com/p/43546261
遗传算法（Genetic Algorithm, GA）起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，借鉴了达尔文的进化论和孟德尔的遗传学说。
其本质是一种高效、并行、全局搜索的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最佳解。
相关术语：
基因(genotype)性状染色体的内部表现表现型(phenotype)染色体决定的性状的外部表现，或者说，根据基因型形成的个体的外部表现进化(evolution)种群逐渐适应生存环境，品质不断得到改良。生物的进化是以种群的形式进行的适应度(fitness)度量某个物种对于生存环境的适应程度选择(selection)以一定的概率从种群中选择若干个个体。一般，选择过程是一种基于适应度的优胜劣汰的过程复制(reproduction)细胞分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新细胞就继承了旧细胞的基因交叉(crossover)两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交变异(mutation)复制时可能（很小的概率）产生某些复制差错，变异产生新的染色体，表现出新的性状编码(coding)DNA中遗传信息在一个长链上按一定的模式排列。遗传编码可看作从表现型到基因型的映射解码(decoding)基因型到表现型的映射个体（individual）指染色体带有特征的实体种群（population）个体的集合，该集合内个体数称为种群的大小遗传算法是从代表问题可能潜在的解集的一个种群(population)开始的，而一个种群则由经过基因(gene)编码的一定数目的个体(individual)组成。因此，第一步需要实现从表现型到基因型的映射即编码工作。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代(generation)演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度 (fitness)大小选择个体，借助于自然遗传学的遗传算子(genetic operators)进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样，后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码(decoding)，可以作为问题近似最优解。
遗传算法的概念模拟物竞天择的生物进化过程，通过维护一个潜在解的群体执行了多方向的搜索，并支持这些方向上的信息构成和交换。是以面为单位的搜索，比以点为单位的搜索，更能发现全局最优解。
比喻说明：在遗传算法中，有很多袋鼠，它们降落到喜玛拉雅山脉的任意地方。这些袋鼠并不知道它们的任务是寻找珠穆朗玛峰。但每过几年，就在一些海拔高度较低的地方射杀一些袋鼠，并希望存活下来的袋鼠是多产的，在它们所处的地方生儿育女。就这样经过许多年，这些袋鼠们竟然都不自觉地聚拢到了一个个的山峰上，可是在所有的袋鼠中，只有聚拢到珠穆朗玛峰的袋鼠被带回了美丽的澳洲。
遗传算法的理解遗传算法的实现过程实际上就像自然界的进化过程那样。首先寻找一种对问题潜在解进行“数字化”编码的方案。（建立表现型和基因型的映射关系）然后用随机数初始化一个种群（那么第一批袋鼠就被随意地分散在山脉上），种群里面的个体就是这些数字化的编码。接下来，通过适当的解码过程之后（得到袋鼠的位置坐标），用适应性函数对每一个基因个体作一次适应度评估（袋鼠爬得越高，越是受我们的喜爱，所以适应度相应越高）。用选择函数按照某种规定择优选择（我们要每隔一段时间，在山上射杀一些所在海拔较低的袋鼠，以保证袋鼠总体数目持平）。让个体基因变异（让袋鼠随机地跳一跳）。然后产生子代（希望存活下来的袋鼠是多产的，并在那里生儿育女）。遗传算法并不保证你能获得问题的最优解，但是使用遗传算法的最大优点在于你不必去了解和操心如何去“找”最优解。（你不必去指导袋鼠向那边跳，跳多远）而只要简单的“否定”一些表现不好的个体就行了。（把那些总是爱走下坡路的袋鼠射杀，这就是遗传算法的精粹）
遗传算法的基本特征：
智能式搜索：依据适应度（目标函数）进行只能搜索 渐进式优化：利用复制、交换、突变等操作，使下一代结果优于上一代 全局最优解：采用交换和突变操作产生新个体，使得搜索得到的优化结果逼近全局最优解黑箱式结构：根据问题的特性进行编码（输入）和确定适应度（输出），具有只考虑输入与输出关系的黑箱式就够，并不深究输入与输出关系的原因 通用性强：不要求明确的数学表达式，只需要一些简单的原则要求，可应用于解决离散问题、函数关系不明确的复杂问题 并行式运算：每次迭代计算都是对群体中所有个体同时进行运算，是并行式运算方式，搜索速度快 遗传算法基本过程 初始化：设置最大迭代进化次数T，随机生成M个个体作为初始种群P(0);个体评价：计算当前种群P(t)中的个体适应度；选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁衍子孙。根据各个个体的适应度值，按照一定的规则或方法从上一代群体中选择出一些优良的个体遗传到下一代种群中。选择的依据是适应性强的个体为下一代贡献一个或多个后代的概率大；交叉：遗传算法中的核心部分,通过交叉操作可以得到新一代个体，新个体组合了父辈个体的特性。将群体中的各个个体随机搭配成对，对每一个个体，以交叉概率交换它们之间的部分染色体；变异：在个体基因的基础上进行变动，模拟自然界的基因突变，其变异结果的好坏不定,对种群中的每一个个体，以变异概率改变某一个或多个基因座上的基因值为其他的等位基因。同生物界中一样， 变异发生的概率很低，变异为新个体的产生提供了机会；终止条件：若迭代次数达到预先设定的T，将迭代过程中具有最优适应度的个体作为问题的解输出。遗传算法的三个基本核心操作:选择(Selection)、交叉(Crossover)和变异(Mutation)。
遗传算法具体步骤分析背包问题：
itemweightsurvival pointssleeping bag1515rope37pocket knife210torch55bottle98glucose2017 3.1 初始化（编码）遗传算法的核心是个体之间的组合交叉变异部分。个体之间的组合交叉变异方式众多，不同的交叉变异方式将对算法的效率产生巨大的影响。
这里我们用遗传算法来解决这个背包问题。第一步是定义我们的总体。总体中包含了个体，每个个体都有一套自己的染色体。
我们知道，染色体可表达为二进制数串，在这个问题中，1 代表接下来位置的基因存在，0 意味着丢失。（译者注：作者这里借用染色体、基因来解决前面的背包问题，所以特定位置上的基因代表了上方背包问题表格中的物品，比如第一个位置上是 Sleeping Bag，那么此时反映在染色体的『基因』位置就是该染色体的第一个『基因』。）
如图，红色方框代表基因（Gene） 绿色方框代表染色体（Chromosome） 紫色方框代表总体人口；
现在，我们将图中的 4 条染色体看作我们的总体初始值。
3.2 编码补充 二进制编码二进制编码由二进制符号0和1所组成的二值符号集。它有以下一些优点： 1. 编码、解码操作简单易行 2. 交叉、变异等遗传操作便于实现 3. 合最小字符集编码原则 4. 利用模式定理对算法进行理论分析。
二进制编码的缺点是：对于一些连续函数的优化问题，由于其随机性使得其局部搜索能力较差，如对于一些高精度的问题，当解迫近于最优解后，由于其变异后表现型变化很大，不连续，所以会远离最优解，达不到稳定。
格雷码格雷码编码是其连续的两个整数所对应的编码之间只有一个码位是不同的，其余码位完全相同。
二进制码转为格雷码：异或运算：同则为0，异则为1。公式如下：
由格雷码转二进制的转换公式为：
优点：增强遗传算法的局部搜索能力，便于对连续函数进行局部空间搜索。使用非常广泛。
浮点编码法二进制编码虽然简单直观，但明显地。但是存在着连续函数离散化时的映射误差。个体长度较短时，可能达不到精度要求，而个体编码长度较长时，虽然能提高精度，但增加了解码的难度，使遗传算法的搜索空间急剧扩大。
所谓浮点法，是指个体的每个基因值用某一范围内的一个浮点数来表示。编码长度等于决策变量的个数。 在浮点数编码方法中，必须保证基因值在给定的区间限制范围内，遗传算法中所使用的交叉、变异等遗传算子也必须保证其运算结果所产生的新个体的基因值也在这个区间限制范围内。
优点：
适用于在遗传算法中表示范围较大的数 适用于精度要求较高的遗传算法 便于较大空间的遗传搜索 改善了遗传算法的计算复杂性，提高了运算交率 便于遗传算法与经典优化方法的混合使用 便于设计针对问题的专门知识的知识型遗传算子 便于处理复杂的决策变量约束条件 符号编码法符号编码法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集如｛A,B,C…｝。
优点：
符合有意义积术块编码原则 便于在遗传算法中利用所求解问题的专门知识 便于遗传算法与相关近似算法之间的混合使用。 3.3 适应度函数适应度函数一般使用目标函数；表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。
计算前两条染色体的适应度分数，对于本问题，适应度分数越高意味着适应性更强， 对 A1 染色体 [100110]、 A2 染色体 [001110]计算结果如下：
itemweightsurvival pointssleeping bag1515torch55bottle98total2923 itemweightsurvival pointspocket knife210torch55bottle98total1623对于这个问题，我们认为，当染色体包含