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

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

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

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

那么如何具体工作呢？

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

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

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

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

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

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

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

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

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

染色体A：AGTATC

染色体B：CAGCAT

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

染色体A：AGTCAT

染色体B：CAGATC

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