主题：【原创】试说遗传算法 1 -- 风满袖

遗传算法（Genetic Algorithm）是什么？它是一种算法，它借助了生物进化理论，用来针对那些不能使用数学分析方法来解决的问题，例如NP（Non-deterministic Polynomial time）问题。推销者（或旅游者）的最佳行程就是个简单的例子，一个推销者（旅游者）要从他家乡开始旅行经过N个城市来达到自己的目的（推销或旅游），然后再返回老家。请给出一条最近的路线。这个问题在城市数N不多的情况下（小于12）很好解决，排列组合然后比较。一旦城市数量多了以后排列组合将爆炸性的增长（排列组合数为 N+1!/2），计算时间也将同比例的增长。例如当N为100时，大约有（5*10的159次方） 个排列组合，以现今的计算机能力大约需要运算（10的143次方） 年。这种问题在计算机学科里面称为NP问题，此类问题的特点是，随着问题涉及面（例子中城市数N）的增加，其计算量将指数性或失控式地增长。

那么遗传算法又是如何解决这个问题的呢？我想先简单介绍一下达尔文（Charles Darwin）进化论和格利高利.孟德尔（Gregor Mendel）遗传定律。后者孟德尔被称为现代遗传之父，他通过对大量数据的手工分析，发现了遗传的基本规律。

其中对进化论我们很容易理解，其核心思想为

第一，“Survival of the fittest”（适者生存），“Struggle for life”（为了生存而斗争）；

第二， 生物的基本特征将会被遗传到下一代身上，但这遗传如何发生，达尔文也不知道。

第三， 每一代生物中都会有一些个体随机异变，将一些新特征带到这个生物中去；

第四， 每一代能幸存下来的生物普遍来说都是最适合外部环境的，所以一个物种只要给他足够的时间，它可以适应环境的变化。

由于达尔文无法解释亲本的特征如何遗传给后代，所以他面临了很多科学家和的异议。十九世纪五十年代到六十年代，格利高利.孟德尔 通过植物培育试验开始解决这个问题。但是直到二十世纪初，遗传原理开始形成时，他的研究成果才广为人知。孟德尔通过多年细致观察豌豆的繁殖得出了以下结论：

第一， 物种的遗传是在每一个细胞中以指令代码的形式进行的。

第二， 这些指令代码被储存在染色体中

第三， 染色体是由很多基因组成

第四， 每个基因控制了一个特殊的物种个性（例如眼睛的颜色等等），因此有机体的全貌由基因控制。

第五， 染色体都是成对出现。在遗传中，在新一代中每个染色体都是由一对父染色体产生（分别来自不同的个体），其中具有“统治性”特征的基因将取代不具有“统治性”的基因。

好，只能介绍这么多了，生物不是我的专业，说不了很多，以上可能也有错误之处，还请河里各位高手指正。不过这些对于初步理解遗传算法已经足够了，现在我们就可以来看看遗传算法到底是怎么回事了。

遗传算法的本质是一种优化算法，所谓“优化”也就是说没有最好，只有更好。它也没有具体公式，只有一些通用的操作步骤。照我的理解它其实是一种妥协，是一种在人类无能为力时的妥协。你不是不让我算出最短的路程？可以，那我就退而求其次，算出一个比较好的。反正能用就行。^_^ 那么如何取得较好的结果呢？这就需要参考进化论和遗传定律了，（我觉得每当人类无能为力的时候，自然界总能给我们启发和灵感。敬畏大自然！）

我们可以对他们的模型和工作原理进行分析。其模型的组成是：染色体，基因（每个基因有自己的值），还有外界环境的限制；其工作原理就是：选择――繁殖（突变）――再选择，其目的就是更适合外部环境。

在实际应用中，我们首先需要把实际问题模型化，比如推销者问题，我们可以把每一条不同的路线看成不同的染色体，每个需要经过的城市看成染色体中的每个基因，基因（也就是每个城市）的排列顺序决定了行程路线。在这个问题中外界条件限制就是：每个基因（城市）必须是不同的。这个模型在计算机中很好表达，可以简单的用一个一维数组来表示，数组中的每个值不能重复，同时每个数组的第一个值和最后一个值都是一样的（代表出发点）。

那么如何具体工作呢？

第一 我们要先人工给出一些第一代的值，在例子中就是一些不同路线，也就是给出一些符合要求的一维数组。同时还要给出一些参数，比如每代的数目有多少？繁殖几代？产生突变的概率？这些参数可以有效的控制计算时间和答案是否更优化。

第二 对这一代的每个个体进行评价，在例子中就是求出每一条路线的长短。

第三 选择一定数量相对优秀的物种进行下一代的繁殖。也就是旅行总距离能小于一定值的数组。如何产生新的下一代的方法具体我下面再介绍。

第四 在新一代中产生一些突变后代，比如把已经确定的新路线中的某个城市随机地用另一个城市取代掉，或者随机打乱其中的顺序。

第五 在新一代中选择优秀的个体，并把新一代取代老一代，也就是把新数组群拷贝到答案数组群中。

最后就是检测是否达到了中断繁殖的标准？比如：达到最大的繁殖代数，或者产生的新一代和老一代的值是一样的。如果达到了中断标准，就停止工作，给出最终答案。反之则继续循环。

现在说说如何繁殖后代，也就是如何产生新的路线？主要方法是Crossover（转换？抱歉，这术语翻译不好，请以英语为准）。

Crossover的工作原理是将染色体A中的一部分基因被染色体B中的一部分来取代，例如：

Crossover前染色体对中的基因排列：

染色体A：AGTATC

染色体B：CAGCAT

Crossover后染色体对中的基因排列：

染色体A：AGTCAT

染色体B：CAGATC

在例子中我们可以交换两个老路线中的一些城市来产生下一个新的路线。

Crossover也有很多种方法，比如：

1、OnePoint Crossover：随机产生一个数r（在本文例子中1<r<N），然后将两个染色体中从r点开始一直到结束范围内的所有基因进行交换，产生两个新的染色体。例如：

染色体A：AGTATC

染色体B：CAGCAT

然后随机选择一个一个数r（1<r<5），比如r=3。交换后：

染色体A：AGTCAT

染色体B：CAGATC

2、TwoPoint Crossover：随机产生两个数b和e，b代表开始，e代表结束。将染色体中位于b和e之间的基因进行交换。

3、N-Point Crossover：随机产生一个二进值的Vector，其二进值的数量和染色体中基因的数量相同。比如分别有五个基因的一对染色体，则随机产生一个有5个数的Vector：{0, 1, 1, 0, 1}。然后规定对相应在Vector中0位的基因进行交换，在这里就交换1位和4位的基因，其余的基因保持不变。

遗传算法的基本原理就是这样，繁殖新一代，选择，再繁殖。就像地球上所有生物一样，唯一不同的是在计算机上受到时间和计算能力的限制。我的理解，遗传算法的关键在于繁殖和突变，选择一个合适的方式进行繁殖和突变是整个算法的重点，但这也是最难的，因为没有一个通用的繁殖和突变方式适合所有的环境。人们必须自己在实践中积累经验然后进行总结得出合适自己的方式。

在应用中遗传算法适合于这类离散变量的优化问题，它可以在较短的时间里给出一个相对满意的答案。在现在全球化和生产程序逐步细化的环境下，不可知的变量和生产规模会越来越大，类似的NP问题将会越来越多的出现在供应，采购和生产等各个环节上。

比如现在生产和运输都讲究集中化，批量化，以求最低成本。但在销售时却讲究个性化，同样一辆汽车两个买主的要求可能完全不一样，这就是一对矛盾。如果讲究个性化销售你就很难降低成本，每人一个样啊；同样如果批量生产成本是低了，但产品千人一面，肯定销量不好。这类矛盾往往就是个NP问题，小产品还好点，象汽车之类的大件，这种问题就很严重了。还有在生产中，例如自动化制定所有工人的排班表，在工人人数少时没关系，很简单。但对上千上万人的工厂做一个公平合理的排班表（比如要满足不能让一个工人连续上两天夜班和上完夜班要休息等等各类条件），就会产生NP问题。遗传算法无疑为这类问题的计算机化处理提供了一个不错的方法。

但遗传算法的实际应用也有不足的地方，同样也是在繁殖和突变方式的选择。由于繁殖和突变方式的选择需要软件设计者有很多相关的实际经验，甚至是相关方面的专家，这样设计出来的软件才不会太离谱。而这类人才相对很少。同样由于通过遗传算法得不到一个最佳的答案，这类软件在目前只能起一个辅助决策的作用，最终结果还是需要人为修改、决定。

无论如何，遗传算法的出现使得NP问题有了初步解决的可能，接下来需要的工作就是慢慢改善，我觉得不久这类应用将会越来越多的出现在实际生活中。

终于写完了，虽然花了不少时间，不过知道自己水平有限，写得很一般，漏洞错误不少。不过我发这片东西的原意，第一就是想抛砖引玉，让高手指点。第二也正好整理一下自己的思路。呵呵。最后多谢各位捧场的朋友，能有耐心看完这几页干巴巴的东西。