主题：【原创】试说遗传算法 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”（为了生存而斗争）；

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

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

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

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

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

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

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

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

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

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