ga算法（用进化论解决算法问题）

说起生物进化论，几乎每个人都耳熟能详：例如物竞天择、适者生存、优胜劣汰等等。生物进化论是近两百年前英国科学家查尔斯·达尔文（Charles Darwin）提出的，虽然从提出开始就饱受争议，但并不妨碍其成为当代生物学的核心思想之一。你知道吗，这个理论不仅可用于生物学领域，还可以用来构建计算机算法呢！

遗传算法（Genetic Algorithm，GA）是计算数学中用于解决最优化问题的搜索算法，是进化算法的一种。进化算法最初就是借鉴了达尔文进化论中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。

遗传算法由密歇根大学的约翰·霍兰德（John Holland）于二十世纪六十年代率先提出。在二十世纪八十年代中期之前，对于遗传算法的研究还仅仅限于理论方面，直到在匹兹堡召开了第一届世界遗传算法大会。随着计算机计算能力的发展和实际应用需求的增多，越来越多种类的遗传算法出现并被用于许多领域中。财富杂志500强企业中大多数都用它进行时间表安排、数据分析、未来趋势预测、预算、以及解决很多其他商业智能中的组合优化问题。日本新干线N700系列车型独特的空气动力造型车鼻，就是遗传算法计算出来的结果。

遗传算法通常的实现方式，就是用程序来模拟生物种群进化的过程。对于一个求最优解的问题，我们可以把一定数量的候选解（称为个体）抽象地表示为染色体，使种群向更好的解来进化。大家知道，使用算法解决问题的时候，解通常都是用数据或者字符串等表示的，而这个数据或字符串对应到生物中就是某个个体的“染色体”。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中评价其在整个种群的适应度，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的种群，该种群在算法的下一次迭代中成为当前种群。其具体的计算步骤如下：

编码：将问题空间转换为遗传空间；生成初始种群：随机生成P个染色体；种群适应度计算：按照确定的适应度函数，计算各个染色体的适应度；选择：根据染色体适应度，按照选择算子进行染色体的选择；交叉：按照交叉概率对被选择的染色体进行交叉操作，形成下一代种群；突变：按照突变概率对下一代种群中的个体进行突变操作；返回第3步继续迭代，直到满足终止条件。

看到这里你也许会问：这里说的算法，好像就是高中课本上讲的生物遗传学呀？没错，遗传算法就是这样模拟生物遗传过程的，下面让我们看一些具体例子吧。

0/1背包问题

背包问题是一个典型的优化组合问题：有一个容量固定的背包，已知n个物品的体积及其价值，我们该选择哪些物品装入背包使得在其容量约束限制之内所装物品的价值最大？比如：背包容量限制为9，有4个物品的体积为{2,3,4,5}，其价值则分别是{3,4,5,7}。

背包问题在计算理论中属于NP-完全问题，传统的算法是动态规划法，可求出最优总价值为12，其时间复杂度对于输入是指数级的。而如果用贪心算法，计算物品性价比依次为{1.5,1.33,1.25,1.4}，依次选择物品1和4，总价值只能达到10，这并非最优解。

现在我们试用遗传算法求解这个问题：

1. 编码

将待求解的各量表示成长度为n的二进制串。例如：1010代表一个解，它表示将第1、3号物体放入背包中，其它的物体则不放入。

2. 生成初始种群

本例中，群体规模的大小取为4，即群体由4个个体组成，每个个体可通过随机的方法产生。例如：

a1 = [1, 1, 1, 1]

a2 = [1, 0, 1, 0]

a3 = [1, 0, 0, 1]

a4 = [1, 0, 0, 0]

3. 种群适应度计算

对每个个体，计算所有物体的体积totalSize，所有物体的价值totalValue，以及个体适应度fit。若所有物体的体积小于背包容量C，fit就是totalValue，否则应进行惩罚，fit应减去alpha∗(totalSize−C) ，这里我们取alpha=2，得到如下结果：

a1 = [1, 1, 1, 1], totalSize = 14, totalValue = 19, fit = 9

a2 = [1, 0, 1, 0], totalSize = 6, totalValue = 8, fit = 8

a3 = [1, 0, 0, 1], totalSize = 7, totalValue = 10, fit = 10

a4 = [1, 0, 0, 0], totalSize = 2, totalValue = 3, fit = 3

4. 选择

根据染色体适应度，我们可以采用轮盘赌进行染色体的选择，即与适应度成正比的概率来确定每个个体复制到下一代群体中的数量。具体操作过程如下：

先计算出群体中所有个体的适应度的总和。然后用每个个体适应度除以总和，结果就是个体被遗传到下一代群体中的概率。每个概率值组成一个区间，全部概率值之和为1。最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个区间内来确定各个个体被选中的次数。

在本例中，适应度总和为30，p(a1)=30.00%，p(a2)=26.66%，p(a3)=33.33%，p(a4)=10.00%。因此区间1为[0,0.3]，区间2为[0.3,0.5666]，区间3为[0.5666,0.9]，区间4为[0.9,1]。 经过4次选择，a1被选1次，a2被选2次，a3被选1次， a4落选：

b1 = [1, 0, 1, 0], totalSize = 6, totalValue = 8, fitValue = 8

b2 = [1, 0, 0, 1], totalSize = 7, totalValue = 10, fitValue = 10

b3 = [1, 0, 1, 0], totalSize = 6, totalValue = 8, fitValue = 8

b4 = [1, 1, 1, 1], totalSize = 14, totalValue = 19, fitValue = 9

经过选择，我们淘汰了适应度最差的个体a4。

5. 交叉

采用单点交叉的方法，先对群体进行随机配对，其次随机设置交叉点位置，最后再相互交换配对染色体之间的部分基因。

在本例中， b1与b4在第3位后交叉，生成后代：

c1 = [1, 0, 1, 1], totalSize = 11, totalValue = 15, fitValue = 11

c2 = [1, 1, 1, 0], totalSize = 9, totalValue = 12, fitValue = 12

b2与b3在第2位后交叉，生成后代：

c3 = [1, 0, 1, 0], totalSize = 6, totalValue = 8, fitValue = 8

c4 = [1, 0, 0, 1], totalSize = 7, totalValue = 10, fitValue = 10

我们可以看出，经过交叉，后代的适应值相比前代有所提高。

6. 突变

我们采用基本位变异的方法来进行变异运算，首先确定出各个个体的基因变异位置，然后依照某一概率将变异点的原有基因值取反。

本例中，c1的第1位发生突变：

c1 = [0, 0, 1, 1], totalSize = 9, totalValue = 12, fitValue = 12

c2 = [1, 1, 1, 0], totalSize = 9, totalValue = 12, fitValue = 12

c3 = [1, 0, 1, 0], totalSize = 6, totalValue = 8, fitValue = 8

c4 = [1, 0, 0, 1], totalSize = 7, totalValue = 10, fitValue = 10

若突变之后最大的适应值个体已经符合期望的价值则停止，否则返回第3步继续迭代。可以看出我们已经找到了2个最优解c1与c2。

八皇后问题

八皇后问题是算法学中一个古老而著名的问题，由国际象棋棋手马克斯·贝瑟尔（Max Bezzel）于1848年提出：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

下图就是八皇后问题的一个解：

以往我们解决八皇后问题都是采用穷举法或者回溯法，然而即使采用回溯法，需要搜索的空间仍然很大。这里我们试用遗传算法解决这个问题：

1. 编码

染色体的长度取决于皇后的个数，本例中染色体长度即为8。染色体中每个基因所处的位置表示其在棋盘上的行号，基因值表示其所在的列号。例如，上图可以表示为染色体53607142，表示第0行皇后放在第5列，第1行皇后放在第3列，第2行皇后放在第6列，第3行皇后放在第0列，以此类推。八皇后问题中的任意两个皇后不能出现在同列，因此染色体中的基因取值（0~7）不可重复。

2. 生成初始种群

随机生成8个初始染色体，他们的染色体中的基因取值各不相同，也就是满足所有皇后都不处于同行同列，但是可能并不满足对角线上是否出现互攻。

3. 种群适应度计算

在对某一染色体上某两个皇后的位置进行比较的时候，可以求其行号之差的绝对值与列号之差的绝对值， 若相等则说明互攻成立。

设某一染色体的互攻次数用N表示，其初始值等于0；将第0行皇后与第1~7行皇后进行比较，每出现一次互攻则N的值加1；将第1行皇后与第2~7行皇后进行比较，每出现一次互攻则N的值加1；以此类推。 如果染色体的N值为0则表示未发生互攻，表示已找到一个可行解。如果N不为0，一般说来适应度越大则N的值越小，也就是说适应度与N成反比。在这里对染色体的N求倒数就得到其适应度。例如，所有皇后都排在对角线上时，染色体01234567的N为7+6+5+4+3+2+1=28，其适应度仅为0.0357。

4. 选择

我们同样采用轮盘赌进行染色体的选择。

5. 交叉

我们采用单点交叉的方法，先对群体进行随机配对，对于每一对染色体，首先随机选取两点截取一段基因，例如：染色体01|24|3675和12|30|4576交换基因后变为01|30|3675和12|24|4576，这样生成的两条染色体并不合法，因此要对中间段外的基因进行交换，从而生成合法的染色体：41|30|2675与13|24|0576，交叉完成。

6. 突变

按照突变概率对下一代种群中的个体进行突变操作，这里对突变个体的染色体随机选择两个基因进行互换，例如对第1和6进行互换： 突变之前的染色体是72061453，突变之后变为42061753（这其实就是一个最优解）。

7. 继续迭代

返回第3步继续迭代，直到取得N为0的解。

采用随机的穷举法或者回溯法得到八皇后问题的一个解，需要几千次甚至上万次的迭代，而采用遗传算法，只需要百余次甚至数十次的迭代就能找到，厉害吧！

遗传算法特点

最后，让我们归纳一下遗传算法在解决优化问题过程中的一些特点：

遗传算法在适应度函数选择不当的情况下有可能收敛于局部最优，而不能达到全局最优。如同爬山一样，有时你爬到了一座山的最高点，但周围也许还有更高的山可以爬。初始种群的数量很重要，如果初始种群数量过多，算法会占用大量系统资源；如果初始种群数量过少，算法很可能忽略掉最优解。

对于每个解，一般根据实际情况进行编码，这样有利于编写突变函数和适应度函数。在编码过的遗传算法中，每次变异的编码长度以及变异率也影响到遗传算法的效率。如果变异代码长度过长，变异的多样性会受到限制；如果变异代码过短，变异的效率会非常低下，选择适当的变异长度是提高效率的关键。对于动态数据，用遗传算法求最优解比较困难，因为染色体种群很可能过早地收敛，而对以后变化了的数据不再产生变化。对于这个问题，学者提出了一些方法增加基因的多样性，从而防止过早的收敛。其中一种是所谓触发式超级变异，就是当染色体群体的质量下降（彼此的区别减少）时增加变异概率；另一种叫随机外来染色体，是偶尔加入一些全新的随机生成的染色体个体，从而增加染色体多样性。

​

选择过程很重要，但交叉和变异的重要性存在争议。一种观点认为交叉比变异更重要，因为变异仅仅是保证不丢失某些可能的解；而另一种观点则认为交叉过程的作用只不过是在种群中推广变异过程所造成的更新，对于初期的种群来说，交叉几乎等效于一个非常大的变异率，而这么大的变异很可能影响进化过程。遗传算法很快就能找到良好的解，即使解空间很复杂。然而遗传算法并不一定总是最好的优化策略，优化问题要具体情况具体分析。所以在使用遗传算法的同时，也可以尝试其他算法，互相补充，甚至根本不用遗传算法。

遗传算法不能解决那些“大海捞针”的问题，所谓“大海捞针”问题就是没有一个确切的适应度函数表征个体好坏的问题，使得算法的进化失去导向。对于任何一个具体的优化问题，调节遗传算法的参数可能会有利于更好更快收敛，这些参数包括个体数目、交叉率、变异率以及适应度函数。例如太大的变异率会导致丢失最优解，而过小的变异率会导致算法过早的收敛于局部最优点。

参考文献

维基百科.Banzhaf, Wolfgang; Nordin, Peter; Keller, Robert; Francone, Frank: Genetic Programming – An Introduction.周明; 孙树栋. 遗传算法原理及应用.Alsuwaiyel M H. Algorithms: Design Techniques and Analysis.

我们会每周推送商业智能、数据分析资讯、技术干货和程序员日常生活，欢迎关注我们的头条&知乎公众号“微策略中国”或微信公众号“微策略 商业智能"。本期公众号有奖互动话题：除了本文里介绍的例子，你还知道遗传算法其他的应用吗？欢迎大家积极留言~~