对遗传算法的解读

当无法穷举遍历出所有的解集时，智能算法就登场了。

好像术语太多了，举个例子吧。六度空间理论说，你和任何一个陌生人，只要通过六个人就可以认识。比如，你认识A，A认识B，B认识C，等等，最多中间通过六个朋友，你就可以找到那位陌生人。这个神奇的理论是Stanley Milgram在1967年提出的，现在我们讨论如何实现它。假定我们掌握了所有的人际关系网络，现在突然想看看，自己能通过最少几个人，可以认识到奥巴马呢？已经可以想见，这几乎无法穷举，人口基数太大了，而且每个人的社会关系都有至少几百人，整个关系网想穷举不可能，即使能穷举出所有的网络关系，那么在这段时间内还不断的有人死亡有人出生呢。但只有找出所有的社会关系，才能知道"最少"通过几个人可以认识到奥巴马，可是其实我们想知道的只是，如何能在几小时或者几天内，以尽量少的中间人数量找到这条关系路径。需要的是时效的平衡，智能算法就是用于解决类似的问题。

复杂的问题，海量的数据，或者对求解时间上的限制，常常会使人们不得不选择一种智能算法去求解近似最优解，像模拟退火、神经网络、蚁群算法、粒子群算法、遗传算法等。简单的了解了下这几种常见的求近似最优解的智能算法后，我对遗传算法最感兴趣，回顾下最近对它的一些学习和理解。

顾名思义，遗传算法的灵感来自于达尔文的进化论。物竞天择，适者生存，遗传算法就是基于这个思想来设计的，所以，它一定是通过模拟一个种群的进化往下进行，这样，遗传算法的关注点就不是个体了，最关心的就是种族的进化方向。抽象来说，就是在部分解空间中，不断进化取得更加优秀的解空间，从而找到近似最优解。

可能不太好理解，还是用上面的例子来说明吧。现在还是要找到你和奥巴马之间的最近关系网络，首先都认识到，获得所有你到奥巴马的关系网络是不现实的，偶尔知道一个，比如通过一千个中间人才能认识到。甚至获取一个这样的关系一下也想不到，没关系，那我们也找出一个“不完整的”解空间吧作为种族的第一代吧。比如你认识的所有人，或者你所在学校或者公司对美国有好友的人，或者奥巴马的所有中国朋友，第一代种族当然越有用，经过N代后的进化越优。在第一代向后进化时，我们使之向好的方向进化下去，最终可能会有许多你需要的关系网络，你从中找出最好的即可。

说到这里，就涉及到了，什么才是好的进化方向呢？怎么解读“物竞天择，适者生存”？首先是“天择”，天就是算法设计者了，你要选择出某一代解空间里，最接近最优解的那部分。所以，对每个个体进行评价，根据评价结果来排名是必不可少的。每个个体怎样成长不需要关注，但是一个好的评价函数会直接影响算法的效率。比如继续上面这个例子，如果把你的所有好友中随机取出100个，按照谁最可能认识奥巴马来设计一个评价函数，比如，有海外经历的、有博士学位以上的、有从政经历的返回较高分，分别评价每位好友后排名。那么这个解空间里，了解了每个个体的适应度，你才能继续选择。

再看“物竞”，就是每个个体之间，如何进化出下一代。比如，每双父母会有一个儿子，那么这个儿子所有的染色体中，一部分来自于父亲，其余的来自于母亲，应用到算法中就是，对于这一代中没有淘汰的解中间，随机抽取两个解，把每个解的染色体中任何组合后产生一个儿子。又有些抽像了，再举上面的例子，我们先看有完整解空间的情况。抽出两个解，你->A->B->C->奥巴马，你->E->B->G->F->奥巴马，那么交叉后，可能得到的下一代为：你->E->B->C->奥巴马。如果还没有得到完整的解空间，比如你的两个适应度最高的好友A，B，他们的各自好友中，取出有交集或者最有可能有交集的一位最为下一代。这一步叫做交叉选择，对特定问题，好的交叉方法很重要，如果想设计更加通用的遗传算法，则可能希望把解空间的个体分解为染色体越发的简单，交叉也是如此。

只是交叉选择还会存在风险，因为你的评价函数未必是没有偏差的。完全有可能你认识解空间中一个解要被淘汰了，或者两个解中取下一代时，按照正常的交叉选择会导致，更有可能的最优解没有被进化到。比如，你的关系网络里有一个朋友的乡下二大爷，曾经救过奥巴马老婆一命，正常的评价函数里，直接把二大爷淘汰了，无论如何进化这条二大爷->奥巴马老婆->奥巴马的关系网络都见不到了。这样，变异就出现了。变异就是，未必按照目前考虑完善的进化法则进行，就像蚁群算法中，总有几个蚂蚁并不按照当前已知的最优路线行进，它们是探险者。所以，在交叉选择时，就要有变异，甚至直接把相对适应度低的关系拿上来进化。

最后看“适者生存”，如果你有了上面的解空间适应度排名，以及如何交叉选择，如何变异，那么你就可以决定，排名前多少名的解有资格进行交叉选择，排名最靠后的多少解，直接淘汰，可以不按照适应度和交叉函数产生多少个变异解，以及可以直接从上代解中间保留下多少排名最靠前的解。这些是经验数据，因为一个解空间，或者一个种族不能过大，过大的话运算量太大，时效性上不可接受，比如现有的PC机二十年计算出来时小奥却已经驾鹤了那就没有任何价值了。所以限制了解空间的大小后，比如，每代只考虑100个关系，从排名前80的关系中去产生交叉选择后代等等。

进化到什么时候结束呢？可以设定为最多计算一周时间，或者最多进化100万代，或者找到最少通过四个人就认识奥巴马了就停止。这样完整的遗传算法就呈现在大家眼前了。遗传算法的好处就是关注点在解空间上，对解的个体特征不必太关注，通用性高。并且在没有得到所需要的满足自己的解时，任何时刻都可以得到比初始时更好的解。到问题的规模无法控制时，这个特性太重要了。而且遗传算法利于并行求解，这也是个非常重要的特性，对分布式计算很有意义。其实，单CPU计算机都是串行执行命令，它的运算速度远大于毫秒级的人脑，但是人脑的并行计算却在很多场合中更有效，人工神经网络这个算法也由此产生，能够并行运算确实是很重要的。

现在还有多种群竞争遗传算法，就是初始解空间不只一个，产生后代时每个种群互相影响。具体问题具体分析吧。

总之，遗传算法就是由初始解空间，适应度的评价，选择哪些个体，如何交叉选择，如何变异，如何停止算法的执行这些要素组成。很多复杂问题都能被它解决。最近我玩QQ七雄争霸，对里面的战略战用python+tkinter简单的模拟了下，用遗传算法计算出较好的阵形。比如，骑兵的特点是攻击力强，血少，移动快，弓箭手射程远，攻击力低，枪兵射程近，血厚，等等。在兵力固定时，通过遗传算法不断的进化，只是通过变幻阵形往往得出相同的战场规则下，结果非常优秀的阵形。比如，我选择80%的种子产生50%的子孙，40%的阵形直接保存，10%的阵形变异，同等兵力时，可以只死一半兵全灭敌人。