参考博客：https://zhuanlan.zhihu.com/p/43546261

遗传算法（Genetic Algorithm, GA）起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，借鉴了达尔文的进化论和孟德尔的遗传学说。

其本质是一种高效、并行、全局搜索的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最佳解。

相关术语：

遗传算法是从代表问题可能潜在的解集的一个种群(population)开始的，而一个种群则由经过基因(gene)编码的一定数目的个体(individual)组成。因此，第一步需要实现从表现型到基因型的映射即编码工作。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代(generation)演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度 (fitness)大小选择个体，借助于自然遗传学的遗传算子(genetic operators)进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样，后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码(decoding)，可以作为问题近似最优解。

模拟物竞天择的生物进化过程，通过维护一个潜在解的群体执行了多方向的搜索，并支持这些方向上的信息构成和交换。是以面为单位的搜索，比以点为单位的搜索，更能发现全局最优解。

比喻说明：在遗传算法中，有很多袋鼠，它们降落到喜玛拉雅山脉的任意地方。这些袋鼠并不知道它们的任务是寻找珠穆朗玛峰。但每过几年，就在一些海拔高度较低的地方射杀一些袋鼠，并希望存活下来的袋鼠是多产的，在它们所处的地方生儿育女。就这样经过许多年，这些袋鼠们竟然都不自觉地聚拢到了一个个的山峰上，可是在所有的袋鼠中，只有聚拢到珠穆朗玛峰的袋鼠被带回了美丽的澳洲。

遗传算法的实现过程实际上就像自然界的进化过程那样。首先寻找一种对问题潜在解进行“数字化”编码的方案。（建立表现型和基因型的映射关系）然后用随机数初始化一个种群（那么第一批袋鼠就被随意地分散在山脉上），种群里面的个体就是这些数字化的编码。接下来，通过适当的解码过程之后（得到袋鼠的位置坐标），用适应性函数对每一个基因个体作一次适应度评估（袋鼠爬得越高，越是受我们的喜爱，所以适应度相应越高）。用选择函数按照某种规定择优选择（我们要每隔一段时间，在山上射杀一些所在海拔较低的袋鼠，以保证袋鼠总体数目持平）。让个体基因变异（让袋鼠随机地跳一跳）。然后产生子代（希望存活下来的袋鼠是多产的，并在那里生儿育女）。遗传算法并不保证你能获得问题的最优解，但是使用遗传算法的最大优点在于你不必去了解和操心如何去“找”最优解。（你不必去指导袋鼠向那边跳，跳多远）而只要简单的“否定”一些表现不好的个体就行了。（把那些总是爱走下坡路的袋鼠射杀，这就是遗传算法的精粹）

遗传算法的基本特征：

遗传算法的三个基本核心操作:选择(Selection)、交叉(Crossover)和变异(Mutation)。

背包问题：

遗传算法的核心是个体之间的组合交叉变异部分。个体之间的组合交叉变异方式众多，不同的交叉变异方式将对算法的效率产生巨大的影响。

这里我们用遗传算法来解决这个背包问题。第一步是定义我们的总体。总体中包含了个体，每个个体都有一套自己的染色体。

我们知道，染色体可表达为二进制数串，在这个问题中，1 代表接下来位置的基因存在，0 意味着丢失。（译者注：作者这里借用染色体、基因来解决前面的背包问题，所以特定位置上的基因代表了上方背包问题表格中的物品，比如第一个位置上是 Sleeping Bag，那么此时反映在染色体的『基因』位置就是该染色体的第一个『基因』。）

如图，红色方框代表基因（Gene） 绿色方框代表染色体（Chromosome） 紫色方框代表总体人口；

现在，我们将图中的 4 条染色体看作我们的总体初始值。

二进制编码由二进制符号0和1所组成的二值符号集。它有以下一些优点： 1. 编码、解码操作简单易行 2. 交叉、变异等遗传操作便于实现 3. 合最小字符集编码原则 4. 利用模式定理对算法进行理论分析。

二进制编码的缺点是：对于一些连续函数的优化问题，由于其随机性使得其局部搜索能力较差，如对于一些高精度的问题，当解迫近于最优解后，由于其变异后表现型变化很大，不连续，所以会远离最优解，达不到稳定。

格雷码编码是其连续的两个整数所对应的编码之间只有一个码位是不同的，其余码位完全相同。

二进制码转为格雷码：异或运算：同则为0，异则为1。公式如下：

由格雷码转二进制的转换公式为：

优点：增强遗传算法的局部搜索能力，便于对连续函数进行局部空间搜索。使用非常广泛。

二进制编码虽然简单直观，但明显地。但是存在着连续函数离散化时的映射误差。个体长度较短时，可能达不到精度要求，而个体编码长度较长时，虽然能提高精度，但增加了解码的难度，使遗传算法的搜索空间急剧扩大。

所谓浮点法，是指个体的每个基因值用某一范围内的一个浮点数来表示。编码长度等于决策变量的个数。 在浮点数编码方法中，必须保证基因值在给定的区间限制范围内，遗传算法中所使用的交叉、变异等遗传算子也必须保证其运算结果所产生的新个体的基因值也在这个区间限制范围内。

优点：

符号编码法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集如｛A,B,C…｝。

优点：

适应度函数一般使用目标函数；表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。

计算前两条染色体的适应度分数，对于本问题，适应度分数越高意味着适应性更强， 对 A1 染色体 [100110]、 A2 染色体 [001110]计算结果如下：

对于这个问题，我们认为，当染色体包含更多生存分数时，也就意味着它的适应性更强。因此，由图可知，染色体 1 适应性强于染色体 2。

接下来我们就是要选择要进行“交配”的染色体了，我们的目的是为了产生优良的下一代，因此选择“交配”的染色体自然也是要优良的。因此我们应该选择生存点数较高的C4染色体和C1染色体，对吧。这样想没错，但是这样的话在几代后染色体之间的相互差异就减少，失去多样性了。因此，我们一般会往里面假如一些随机性。让选择也具有一些随机性。那怎么加入呢？一般是采用「轮盘赌选择法」（Roulette Wheel Selection method）。

解释： 　　假设有一个轮盘，我们把它分割成n份(n表示总体中染色体的个数)，每条染色体在轮盘上的占用面积跟它的适应值成正比。以前面的例子来看，应如下图：

现在，将这个轮盘进行旋转，当停下来的时候，指针指中的那片区域所代表的染色体即为第一个亲本，重复操作得到第二个亲本。选中这两个亲本进行“交配”产生下一代。

选择

根据交叉点的个数可分为单点交叉和多点交叉。

单点交叉：交叉最基本的形式，随机选择一个交叉点，将交叉点前后的染色体部分进行染色体间的交叉对调从而产生新后代，如下图：

多点交叉：选择两个交叉点，将交叉点之间的染色体部分进行对调从而产生后代，如下图：

遗传算法与传统优化算法的区别

在生物学中，在后代的生长过程中，它们体内的基因会发生一些变化，使得它们与父母不同，这个过程我们称为变异。变异是导致子一代的性状与亲一代不一样的原因。也就是说，正是因为变异，才导致种群存在多样性。

一般的，我们定义变异为染色体上发生的随机变化。如下图：

变异完成后，我们就得到了新的个体，完成一次进化。整个过程如下图（图来源：http://www.jade-cheng.com/au/coalhmm/optimization/）：

这样就算完成了一次进化，接着我们由要用适应度函数去对这些新的后代进行判定，如果后代的适应度值够大，则将其替代掉总体中那些适应度值较低的染色体（保证种群的个数不变）。接着不断重复选择-交叉-变异这几个步骤，直至达到进化次数。

交叉操作中随机产生交叉点，在此，使用Logistics混沌序列确定交叉点位置。即取一个（0，1）区间上的随机数作为初值，然后利用x(n)=4*x(n-1)（1-x(n-1)）迭代产生一个（0，1）区间的混沌值，保存以上混沌值作为产生下一代交叉项的混沌迭代初值，再把这个值分别乘以100再加上2，最后取整作为交叉点，得到整个混沌序列，互换交叉点的基因，形成新的子代，仅仅更换部分点基因，没有连成片段，改动较小，这样可以避免遗传算法在组合优化应用中产生的寻优抖振问题。

待补

MATLAB内嵌遗传算法工具箱: gadst