小袋鼠你往哪儿跳

第二章 小袋鼠你往哪儿跳－－遗传算法 基础及其本质 有很多袋鼠，它们降落到喜玛拉雅山脉的任意地方。这些袋鼠并不知道它们的任务是寻 找珠穆朗玛峰。但每过几年，就在一些海拔高度较低的地方射杀一些袋鼠，并希望存活下来 的袋鼠是多产的，在它们所处的地方生儿育女。 想了很久，应该用一个怎么样的例子带领大家走进遗传算法的神奇世界呢？遗传算法的 有趣应用很多，诸如寻路问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ，8 数码问题，囚犯困境，动作控制，找圆心问题（这是一个 国外网友的建议：在一个不规则的多边形中，寻找一个包含在该多边形内的最大圆圈的圆 心。），TSP 问题（在以后的章节里面将做详细介绍。），生产调度问题，人工生命模拟等。 直到最后看到一个非常有趣的比喻，觉得由此引出的袋鼠跳问题（暂且这么叫它吧），既有 趣直观又直达遗传算法的本质，确实非常适合作为初学者入门的例子。这一章将告诉读者， 我们怎么让袋鼠跳到珠穆朗玛峰上去(如果它没有过早被冻坏的话)。 问题的提出与解决方案 让我们先来考虑考虑下面这个问题的解决办法。 已知一元函数： [ ]( ) sin(10 ) 2.0 1,2f x x x xπ= ⋅ + ∈ − 现在要求在既定的区间内找出函数的最大值。函数图像如图 2-1 所示。 图 2-1 极大值、最大值、局部最优解、全局最优解 在解决上面提出的问题之前我们有必要先澄清几个以后将常常会碰到的概念：极大值、 最大值、局部最优解、全局最优解。学过高中数学的人都知道极大值在一个小邻域里面左边 的函数值递增，右边的函数值递减，在图 2.1 里面的表现就是一个“山峰”。当然，在图上 有很多个“山峰”，所以这个函数有很多个极大值。而对于一个函数来说，最大值就是在所 有极大值当中，最大的那个。所以极大值具有局部性，而最大值则具有全局性。 因为遗传算法中每一条染色体，对应着遗传算法的一个解决方案，一般我们用适应性函 数（fitness function）来衡量这个解决方案的优劣。所以从一个基因组到其解的适应度形 成一个映射。所以也可以把遗传算法的过程看作是一个在多元函数里面求最优解的过程。在 这个多维曲面里面也有数不清的“山峰”，而这些最优解所对应的就是局部最优解。而其中 也会有一个“山峰”的海拔最高的，那么这个就是全局最优解。而遗传算法的任务就是尽量 爬到最高峰，而不是陷落在一些小山峰。（另外，值得注意的是遗传算法不一定要找“最高 的山峰”，如果问题的适应度评价越小越好的话，那么全局最优解就是函数的最小值，对应 的，遗传算法所要找的就是“最深的谷底”）如果至今你还不太理解的话，那么你先往下看。 本章的示例程序将会非常形象的表现出这个情景。 “袋鼠跳”问题 既然我们把函数曲线理解成一个一个山峰和山谷组成的山脉。那么我们可以设想所得到 的每一个解就是一只袋鼠，我们希望它们不断的向着更高处跳去，直到跳到最高的山峰（尽 管袋鼠本身不见得愿意那么做）。所以求最大值的过程就转化成一个“袋鼠跳”的过程。下 面介绍介绍“袋鼠跳”的几种方式。 爬山法、模拟退火和遗传算法 解决寻找最大值问题的几种常见的算法： 1. 爬山法（最速上升爬山法）： 从搜索空间中随机产生邻近的点，从中选择对应解最优的个体，替换原来的个体，不断 重复上述过程。因为只对“邻近”的点作比较，所以目光比较“短浅”，常常只能收敛到离 开初始位置比较近的局部最优解上面。对于存在很多局部最优点的问题，通过一个简单的迭 代找出全局最优解的机会非常渺茫。（在爬山法中，袋鼠最有希望到达最靠近它出发点的山 顶，但不能保证该山顶是珠穆朗玛峰，或者是一个非常高的山峰。因为一路上它只顾上坡， 没有下坡。） 2. 模拟退火： 这个 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 来自金属热加工过程的启发。在金属热加工过程中，当金属的温度超过它的 熔点（Melting Point）时，原子就会激烈地随机运动。与所有的其它的物理系统相类似，原 子的这种运动趋向于寻找其能量的极小状态。在这个能量的变迁过程中，开始时。温度非常 高，使得原子具有很高的能量。随着温度不断降低，金属逐渐冷却，金属中的原子的能量就 越来越小，最后达到所有可能的最低点。利用模拟退火的时候，让算法从较大的跳跃开始， 使到它有足够的“能量”逃离可能“路过”的局部最优解而不至于限制在其中，当它停在全 局最优解附近的时候，逐渐的减小跳跃量，以便使其“落脚”到全局最优解上。（在模拟退 火中，袋鼠喝醉了，而且随机地大跳跃了很长时间。运气好的话，它从一个山峰跳过山谷， 到了另外一个更高的山峰上。但最后，它渐渐清醒了并朝着它所在的峰顶跳去。） 3. 遗传算法： 模拟物竞天择的生物进化过程，通过维护一个潜在解的群体执行了多方向的搜索，并支 持这些方向上的信息构成和交换。以面为单位的搜索，比以点为单位的搜索，更能发现全局 最优解。（在遗传算法中，有很多袋鼠，它们降落到喜玛拉雅山脉的任意地方。这些袋鼠并 不知道它们的任务是寻找珠穆朗玛峰。但每过几年，就在一些海拔高度较低的地方射杀一些 袋鼠，并希望存活下来的袋鼠是多产的，在它们所处的地方生儿育女。）（后来，一个叫天 行健的网游给我想了一个更恰切的故事：从前，有一大群袋鼠，它们被莫名其妙的零散地遗 弃于喜马拉雅山脉。于是只好在那里艰苦的生活。海拔低的地方弥漫着一种无色无味的毒气， 海拔越高毒气越稀薄。可是可怜的袋鼠们对此全然不觉，还是习惯于活蹦乱跳。于是，不断 有袋鼠死于海拔较低的地方，而越是在海拔高的袋鼠越是能活得更久，也越有机会生儿育女。 就这样经过许多年，这些袋鼠们竟然都不自觉地聚拢到了一个个的山峰上，可是在所有的袋 鼠中，只有聚拢到珠穆朗玛峰的袋鼠被带回了美丽的澳洲。 ） 下面主要介绍介绍遗传算法实现的过程。 遗传算法的实现过程 遗传算法的实现过程实际上就像自然界的进化过程那样。首先寻找一种对问题潜在解进 行“数字化”编码的方案。（建立表现型和基因型的映射关系。）然后用随机数初始化一个 种群（那么第一批袋鼠就被随意地分散在山脉上。），种群里面的个体就是这些数字化的编 码。接下来，通过适当的解码过程之后，（得到袋鼠的位置坐标。）用适应性函数对每一个 基因个体作一次适应度评估。（袋鼠爬得越高，越是受我们的喜爱，所以适应度相应越高。） 用选择函数按照某种规定择优选择。（我们要每隔一段时间，在山上射杀一些所在海拔较低 的袋鼠，以保证袋鼠总体数目持平。）让个体基因交叉变异。（让袋鼠随机地跳一跳）然后 产生子代。（希望存活下来的袋鼠是多产的，并在那里生儿育女。）遗传算法并不保证你能 获得问题的最优解，但是使用遗传算法的最大优点在于你不必去了解和操心如何去“找”最 优解。（你不必去指导袋鼠向那边跳，跳多远。）而只要简单的“否定”一些表现不好的个 体就行了。（把那些总是爱走下坡路的袋鼠射杀。）以后你会慢慢理解这句话，这是遗传算 法的精粹！ 题外话： 这里想提一提一个非主流的进化论观点：拉马克主义的进化论。 法国学者拉马克（Jean-Baptiste de Lamarck,1744～1891）的进化论观点表述在他的 《动物学哲学》（1809）一书中。该书提出生物自身存在一种是结构更加复杂化的“内驱力”， 这种内驱力是与生俱来的，在动物中表现为“动物体新器官的产生来自它不断感觉到的新需 要。”不过具体的生物能否变化，向什么方向变化，则要受环境的影响。拉马克称其环境机 制为“获得性遗传”，这一机制分为两个阶段：一是动物器官的用与不用（即“用进废退”： 在环境的作用下，某一器官越用越发达，不使用就会退化，甚至消失。）；二是在环境作用 下，动物用与不用导致的后天变异通过繁殖传给后代（即“获得性遗传”）。 德国动物学家魏斯曼（August Weismann,1834～1914）对获得性遗传提出坚决的质疑。 他用老鼠做了一个著名的“去尾实验”，他切去老鼠的尾巴，并使之适应了短尾的生活。用 这样的老鼠进行繁殖，下一代老鼠再切去尾巴，一连切了 22 代老鼠的尾巴，第 23 代老鼠仍 然长出正常的尾巴。由此魏斯曼认为后天后天获得性不能遗传。（择自《怀疑----科学探索 的起点》） 我举出这个例子，一方面希望初学者能够更加了解正统的进化论思想，能够分辨进化论 与伪进化论的区别。另一方面想让读者知道的是，遗传算法虽然是一种仿生的算法，但我们 不需要局限于仿生本身。大自然是非常智慧的，但不代表某些细节上人不能比她更智慧。另 外，具体地说，大自然要解决的问题，毕竟不是我们要解决的问题，所以解决方法上的偏差 是非常正常和在所难免的。（下一章，读者就会看到一些非仿生而有效的算法改进。）譬如 上面这个“获得性遗传”我们先不管它在自然界存不存在，但是对于遗传算法的本身，有非 常大的利用价值。即变异不一定发生在产生子代的过程中，而且变异方向不一定是随机性的。 变异可以发生在适应性评估的过程当中，而且可以是有方向性的。（当然，进一步的研究有 待进行。） 所以我们总结出遗传算法的一般步骤： 开始循环直至找到满意的解。 1.评估每条染色体所对应个体的适应度。 2.遵照适应度越高，选择概率越大的原则，从种群中选择两个个体作为父方和母方。 3.抽取父母双方的染色体，进行交叉，产生子代。 4.对子代的染色体进行变异。 5.重复 2，3，4 步骤，直到新种群的产生。 结束循环。 接下来，我们将详细地剖析遗传算法过程的每一个细节。 编制袋鼠的染色体----基因的编码方式 通过前一章的学习，读者已经了解到人类染色体的编码符号集，由 4 种碱基的两种配合 组成。共有 4 种情况，相当于 2 bit 的信息量。这是人类基因的编码方式，那么我们使用遗 传算法的时候编码又该如何处理呢？ 受到人类染色体结构的启发，我们可以设想一下，假设目前只有“0”，“1”两种碱基， 我们也用一条链条把他们有序的串连在一起，因为每一个单位都能表现出 1 bit 的信息量， 所以一条足够长的染色体就能为我们勾勒出一个个体的所有特征。这就是二进制编码法，染 色体大致如下： 010010011011011110111110 上面的编码方式虽然简单直观，但明显地，当个体特征比较复杂的时候，需要大量的编 码才能精确地描述，相应的解码过程（类似于生物学中的 DNA 翻译过程，就是把基因型映射 到表现型的过程。）将过份繁复，为改善遗传算法的计算复杂性、提高运算效率，提出了浮 点数编码。染色体大致如下： 1.2 – 3.3 – 2.0 – 5.4 – 2.7 – 4.3 那么我们如何利用这两种编码方式来为袋鼠的染色体编码呢？因为编码的目的是建立 表现型到基因型的映射关系，而表现型一般就被理解为个体的特征。比如人的基因型是 46 条染色体所描述的（总长度两米的纸条？），却能解码成一个个眼，耳，口，鼻等特征各不 相同的活生生的人。所以我们要想为“袋鼠”的染色体编码，我们必须先来考虑“袋鼠”的 “个体特征”是什么。也许有的人会说，袋鼠的特征很多，比如性别，身长，体重，也许它 喜欢吃什么也能算作其中一个特征。但具体在解决这个问题的情况下，我们应该进一步思考： 无论这只袋鼠是长短，肥瘦，只要它在低海拔就会被射杀，同时也没有规定身长的袋鼠能跳 得远一些，身短的袋鼠跳得近一些。当然它爱吃什么就更不相关了。我们由始至终都只关心 一件事情：袋鼠在哪里。因为只要我们知道袋鼠在那里，我们就能做两件必须去做的事情： （1）通过查阅喜玛拉雅山脉的地图来得知袋鼠所在的海拔高度（通过自变量求函数值。） 以判断我们有没必要把它射杀。 （2）知道袋鼠跳一跳后去到哪个新位置。 如果我们一时无法准确的判断哪些“个体特征”是必要的，哪些是非必要的，我们常常 可以用到这样一种思维方式：比如你认为袋鼠的爱吃什么东西非常必要，那么你就想一想， 有两只袋鼠，它们其它的个体特征完全同等的情况下，一只爱吃草，另外一只爱吃果。你会 马上发现，这不会对它们的命运有丝毫的影响，它们应该有同等的概率被射杀！只因它们处 于同一个地方。（值得一提的是，如果你的基因编码 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 中包含了袋鼠爱吃什么的信息，这 其实不会影响到袋鼠的进化的过程，而那只攀到珠穆朗玛峰的袋鼠吃什么也完全是随机的， 但是它所在的位置却是非常确定的。） 以上是对遗传算法编码过程中经常经历的思维过程，必须把具体问题抽象成数学模型， 突出主要矛盾，舍弃次要矛盾。只有这样才能简洁而有效的解决问题。希望初学者仔细琢磨。 既然确定了袋鼠的位置作为个体特征，具体来说位置就是横坐标。那么接下来，我们就 要建立表现型到基因型的映射关系。就是说如何用编码来表现出袋鼠所在的横坐标。由于横 坐标是一个实数，所以说透了我们就是要对这个实数编码。回顾我们上面所介绍的两种编码 方式，读者最先想到的应该就是，对于二进制编码方式来说，编码会比较复杂，而对于浮点 数编码方式来说，则会比较简洁。恩，正如你所想的，用浮点数编码，仅仅需要一个浮点数 而已。而下面则介绍如何建立二进制编码到一个实数的映射。 明显地，一定长度的二进制编码序列，只能表示一定精度的浮点数。譬如我们要求解精 确到六位小数，由于区间长度为 2 – (-1) = 3 ,为了保证精度要求，至少把区间[-1,2]分 为 3 × 106等份。又因为 21 6 222097152 2 3 10 2 4194304= < × < = 所以编码的二进制串至少需要 22 位。 把一个二进制串 转化位区间0 20 21(b b b" ) [ ]1,2− 里面对应的实数值通过下面两个步骤。 （1）将一个二进制串 代表的二进制数转化为 10 进制数0 20 21(b b b" ) x′： 21 0 20 21 2 10 0 ( ) ( 2 )ii i b b b b x = ′= ⋅ =∑" （2） x′对应区间[ ]1,2− 内的实数： 22 2 ( 1)0.1 2 1 x x − −′= − + ⋅ − 例如一个二进制串<1000101110110101000111>表示实数值 0.637197。 2 22 (1000101110110101000111) 2288967 30.1 2288967 0.637197 2 1 x x ′ = = = − + ⋅ =− 二进制串<0000000000000000000000>和<1111111111111111111111>则分别表示区间的 两个端点值-1 和 2。 由于往下章节的示例程序几乎都只用到浮点数编码，所以这个“袋鼠跳”问题的解决方 案也是采用浮点数编码的。往下的程序示例（包括装载基因的类，突变函数）都是针对浮点 数编码的。（对于二进制编码这里只作简单的介绍，不过这个“袋鼠跳”完全可以用二进制 编码来解决的，而且更有效一些。所以读者可以自己尝试用二进制编码来解决。） 小知识：vector（容器）的使用。 在具体写代码的过程中，读者将会频繁用到 vector 这种数据结构，所以大家必须先对 它有所了解。 std::vector 是 STL（standard template library）库里面的现成的模板类。它用起来 就像动态数组。利用 vector（容器）我们可以方便而且高效的对容器里面的元素进行操作。 示例如下： //添加头文件，并使用 std 名空间。 #include using namespace std; //定义一个 vector,<>内的是这个 vector 所装载的类型。 vector MyVector; //为 vector 后面添加一个整型元素 0。 MyVector.push_back(0); //把 vector 的第一个元素的值赋给变量 a。值得注意的是如果 vector 的长度只有 1，而你 //去访问它的下一个元素的话，编译和运行都不会报错，它会返回一个随机值给你，所以使 //用的时候一定要注意这个潜伏的 BUG。 int a = MyVector[0]; //把 vector 里面的元素全部清空。 MyVector.clear(); //返回 vector 里面的元素的个数。 MyVector.size() 呵呵，如果你没用过这个模板类，请完全不必介意，因为现在为止，你已经学会了在本 书里面将用到的所有功能。 另外，我也顺便提一提，为什么我用 vector 而不用其它数据结构比如数组，来承载一 条基因，还有后面我们将会学到的神经网络中的权值向量。诚然，用数组作为基因或者权值 向量的载体，速度会快一些。但是我用 vector 主要出于下面几个考虑。首先，vector 的使 用比较方便，方便得到其大小，也方便添加和访问元素，还有排序。其次，使用 vector 也 便于代码的维护与及重用（在这本书的学习过程中，学习者将会逐步建立起遗传算法和人工 神经网络的引擎，通过对代码少量的修改就能用于解决新的问题。）。另外，我还希望在研 究更前缘的应用方向――通过遗传算法动态改变神经网络的拓扑结构的时候，大家仍然可以 通过少量的修改后继续利用这些代码。（因为动态地改变神经网络的拓扑结构非常需要不限 定大小的容器。） 我们定义一个类作为袋鼠基因的载体。（细心的人会提出这样的疑问：为什么我用浮点 数的容器来储藏袋鼠的基因呢？袋鼠的基因不是只用一个浮点数来表示就行吗？恩，没错， 事实上对于这个实例，我们只需要用上一个浮点数就行了。我们这里用上容器是为了方便以 后利用这些代码处理那些编码需要一串浮点数的问题。） class CGenome { public: //定义装载基因的容器（事实上从英文解释来看，Weights 是权值的意思，这用来表示 //基因的确有点名不符实，呵呵。这主要是因为这些代码来自于 GA-ANN 引擎，所以在 //它里面基因实质就是神经网络的权值，所以习惯性的把它引入过来就只好这样了。） vector vecWeights; // dFitness 用于存储对该基因的适应性评估。 double dFitness; //类的无参数初始化参数。 CGenome():dFitness(0){} //类的带参数初始化参数。 CGenome(vector w, double f): vecWeights(w), dFitness(f){} }; 好了，目前为止我们把袋鼠的染色体给研究透了，让我们继续跟进袋鼠的进化旅程。 物竞天择－－适应性评分与及选择函数。 1.物竞――适应度函数（fitness function） 自然界生物竞争过程往往包含两个方面：生物相互间的搏斗与及生物与客观环境的搏斗 过程。但在我们这个实例里面，你可以想象到，袋鼠相互之间是非常友好的，它们并不需要 互相搏斗以争取生存的权利。它们的生死存亡更多是取决于你的判断。因为你要衡量哪只袋 鼠该杀，哪只袋鼠不该杀，所以你必须制定一个衡量的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 。而对于这个问题，这个衡量的 标准比较容易制定：袋鼠所在的海拔高度。（因为你单纯地希望袋鼠爬得越高越好。）所以 我们直接用袋鼠的海拔高度作为它们的适应性评分。即适应度函数直接返回函数值就行了。 2.天择――选择函数（selection） 自然界中，越适应的个体就越有可能繁殖后代。但是也不能说适应度越高的就肯定后代 越多，只能是从概率上来说更多。（毕竟有些所处海拔高度较低的袋鼠很幸运，逃过了你的 眼睛。）那么我们怎么来建立这种概率关系呢？下面我们介绍一种常用的选择方法――轮盘 赌（Roulette Wheel Selection）选择法。假设种群数目 ,某个个体 其适应度为n i if ,则其 被选中的概率为： 1 i i n i i fP f = = ∑ 比如我们有 5 条染色体，他们所对应的适应度评分分别为：5，7，10，13，15。 所以累计总适应度为： 1 5 7 10 13 15 50 n i i F f = = = + + + + =∑ 所以各个个体被选中的概率分别为： 1 1 2 2 3 3 4 4 5 5 5100% 100% 10% 50 7100% 100% 14% 50 10100% 100% 20% 50 13100% 100% 26% 50 15100% 100% 30% 50 fP F fP F fP F fP F fP F = × = × = = × = × = = × = × = = × = × = = × = × = 呵呵，有人会问为什么我们把它叫成轮盘赌选择法啊？其实你只要看看图 2-2 的轮盘就 会明白了。这个轮盘是按照各个个体的适应度比例进行分块的。你可以想象一下，我们转动 轮盘，轮盘停下来的时候，指针会随机地指向某一个个体所代表的区域，那么非常幸运地， 这个个体被选中了。（很明显，适应度评分越高的个体被选中的概率越大。） 图 2-2 那么接下来我们看看如何用代码去实现轮盘赌。 //轮盘赌函数 CGenome GetChromoRoulette() { //产生一个 0 到人口总适应性评分总和之间的随机数. //中 m_dTotalFitness 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 了整个种群的适应性分数总和) double Slice = (RandFloat()) * m_dTotalFitness; //这个基因将承载转盘所选出来的那个个体. CGenome TheChosenOne; //累计适应性分数的和. double FitnessSoFar = 0; //遍历总人口里面的每一条染色体。 for (int i=0; i= Slice) { TheChosenOne = m_vecPop[i]; break; } } //返回转盘选出来的个体基因 return TheChosenOne; } 遗传变异――基因重组（交叉）与基因突变。 应该说这两个步骤就是使到子代不同于父代的根本原因（注意，我没有说是子代优于父 代的原因，只有经过自然的选择后，才会出现子代优于父代的倾向。）。对于这两种遗传操 作，二进制编码和浮点型编码在处理上有很大的差异，其中二进制编码的遗传操作过程，比 较类似于自然界里面的过程，下面将分开讲述。 1.基因重组/交叉(recombination/crossover) （1）二进制编码 回顾上一章介绍的基因交叉过程：同源染色体联会的过程中，非姐妹染色单体（分别来 自父母双方）之间常常发生交叉，并且相互交换一部分染色体，如图 2-3。事实上，二进制 编码的基因交换过程也非常类似这个过程――随机把其中几个位于同一位置的编码进行交 换，产生新的个体，如图 2-4 所示。 图 2-3 图 2-4 （2）浮点数编码 如果一条基因中含有多个浮点数编码，那么也可以用跟上面类似的方法进行基因交叉， 不同的是进行交叉的基本单位不是二进制码，而是浮点数。而如果对于单个浮点数的基因交 叉，就有其它不同的重组方式了，比如中间重组： [ ]( ) θ θ ∈子代编码值＝父代编码在值＋ 母方编码值－父方编码值 其中 0,1 这样只要随机产生θ 就能得到介于父代基因编码值和母代基因编码值之间的值作为子代基 因编码的值。 考虑到“袋鼠跳”问题的具体情况――袋鼠的个体特征仅仅表现为它所处的位置。可以 想象，同一个位置的袋鼠的基因是完全相同的，而两条相同的基因进行交叉后，相当于什么 都没有做，所以我们不打算在这个例子里面使用交叉这一个遗传操作步骤。（当然硬要这个 操作步骤也不是不行的，你可以把两只异地的袋鼠捉到一起，让它们交配，然后产生子代， 再把它们送到它们应该到的地方。） 题外话： 性的起源 生命进化中另一个主要的重大进展是伴随着两性的发育――两个生物个体间遗传物质 的交换而来的。正是这种交换提供了自然选择可以发生作用的变异水平。 性可能起源于在某种同类相食中。一个生物吞噬了另一个生物。含有双倍遗传物质的吞 噬后生物为了解救自己而一分为二。这时，一种单倍遗传物质与双倍遗传物质的单位持续相 互交换替的模式就会产生。直至到达一个各项规则都适合于双倍系统的环境。在这个系统中， 从双倍体到单倍体的分裂只发生在性细胞或配子形成中，然后来自不同母体的配子结合成一 个新的个体而恢复正常的双倍体系统。由于两性的出现，使进化的步伐加快了。（择自《吉 尼斯－百科全书》1999 年版） 由于基因交叉和两性有莫大的关联，所以我们可以从这个角度去深入了解基因交叉。性 别的出现是在生物已经进化得相对复杂的时候。那个时候生物的基因基本形成了一种功能分 块的架构。而自然界的基因交叉过程又一般不是单个基因，或者随便几个基因的交叉，而是 一块基因，往往是表现某种个体性状的那块基因，所以从宏观上看，基因交叉的表现是性状 的分离（孟德尔在实验中总结出来的规律。）。而性状又往往表现相对独立的个体特征。比 如豌豆的高茎和矮茎，圆滑和皱缩。（参照第一章对孟德尔实验的介绍。）这些都是相对独 立的特征，它们之间可以自由组合互相搭配。这时候，交叉过程将起到从宏观上调整基因块 之间搭配的作用。经过物竞天择的过程，最后就能得到相对较好的特征组合方式，从而产生 更优的个体。我想这才是基因交叉的意义所在吧。所以对于很多问题，使用基因交叉操作的 效果不太明显，往往只能充当跳出局部最优解，相当于大变异的功能。真正意义上的基因交 叉应该使用在大规模参数的进化过程当中，它将承担起对基因块进行组合优化的职责，从更 宏观的角度去优化个体。对于交叉操作以后还将进行更具体的探讨。 2.基因突变(Mutation) （1）二进制编码 同样回顾一下上一章所介绍的基因突变过程：基因突变是染色体的某一个位点上基因的 改变。基因突变使一个基因变成它的等位基因，并且通常会引起一定的表现型变化。恩，正 如上面所说，二进制编码的遗传操作过程和生物学中的过程非常相类似，基因串上的 “0” 或“1”有一定几率变成与之相反的“1”或“0”。例如下面这串二进制编码： 101101001011001 经过基因突变后，可能变成以下这串新的编码： 001101011011001 （2）浮点型编码 浮点型编码的基因突变过程一般是对原来的浮点数增加或者减少一个小随机数。比如原 来的浮点数串如下： 1.2, 3.4, 5.1, 6.0, 4.5 变异后，可能得到如下的浮点数串： 1.3, 3.1, 4.9, 6.3, 4.4 当然，这个小随机数也有大小之分，我们一般管它叫“步长”。（想想“袋鼠跳”问题， 袋鼠跳的长短就是这个步长。）一般来说步长越大，开始时进化的速度会比较快，但是后来 比较难收敛到精确的点上。而小步长却能较精确的收敛到一个点上。所以很多时候为了加快 遗传算法的进化速度，而又能保证后期能够比较精确地收敛到最优解上面，会采取动态改变 步长的方法。其实这个过程与前面介绍的模拟退火过程比较相类似，读者可以做简单的回顾。 下面是针对浮点型编码的基因突变函数的写法： //基因突变函数 void Mutate(vector &chromo) { //遵循预定的突变概率,对基因进行突变 for (int i=0; i g_RightPoint) { chromo[i] = g_LeftPoint; } //以上代码非基因变异的一般性代码只是用来保证基因编码的可行性。 } } } 值得一提的是遗传算法中基因突变的特点和上一章提到的生物学中的基因突变的特点 非常相类似，这里回顾一下： 1.基因突变是随机发生的，且突变频率很低。（不过某些应用中需要高概率的变异） 2.大多数基因变异对生物本身是有害的。 3.基因突变是不定向的。 题外话： 染色体变异 基因突变是染色休的某一个位点上基因的改变，这种改变在光学显微镜下是无法直接观 察到的。而染色休变异（chromosomal variations）是可以用显微镜直接观察到的，如染色 体结构的改变、染色体数目的增减等。 1.染色体结构的变异 人类的许多遗传病是由染色体结构改变引起的。例如，猫叫综合征是人的第 5 号染色体 部分缺失引起的遗传病，因为患病儿童哭声轻，音调高，很像猫叫而得名。猫叫综合症患者 的生长发育迟缓，而且存在严重的智力障碍。 在自然条件或人为因素的影响下，染色体发生的结构变异主要有以下 4 种类型。（如图 组 2-5） （1）染色体某一段缺失引起变异。 （2）染色体中增加某一片段引起变异。 （3）染色体某一片段移接到另一条非同源染色体上引起变异。 （4）染色体中某一片段位置颠倒也可引起变异。 上述染色体结构的改变，都会使排列在染色体上的基因的数目和排列顺序发生改变，从 而导致性状的变异。大多数染色体结构变异对生物体是不利的，有的甚至导致生物体死亡。 2. 染色体数目的变异 一般来说，每一种生物的染染色体数目都是稳定的，但是，在某些特定的环境条件下生 物体的染色体数目会发生改变，从而产生可遗传变异。染色体数目的变异可以分为两类：一 类是细胞内的个别染色体增加或减少，另一类是细胞内的染色体数目以染色体组的形式成倍 地增加或减少。（择自《高中生物课本》） 读者应该察觉到我们用在遗传算法上的基因突变也没有包括染色体的变异过程。因为一 般来说这种大规模的变异对原来的个体的基因序列破坏性比较大。所以一般来说很难得到一 个适应度高的个体。但是染色体变异，特别是染色体数目的突变使到生物从简单进化到复杂 成为了可能，这也是非常具有意义的。 1.染色体某一段缺失引起变异。 2.染色体中增加某一片段引起变异。 3.染色体某一片段移接到另一条非同源染 色体上引起变异。 4.染色体中某一片段位置颠倒也可引起 变异。 图组 2-5 好了，到此为止，基因编码，基因适应度评估，基因选择，基因变异都一一实现了，剩 下来的就是把这些遗传过程的“零件”装配起来了。先让我们定义一个遗传算法的类：CGenAlg 遗传算法引擎――CGenAlg class CGenAlg { public: //这个容器将储存每一个个体的染色体 vector m_vecPop; //人口(种群)数量 int m_iPopSize; //每一条染色体的基因的总数目 int m_iChromoLength; //所有个体对应的适应性评分的总和 double m_dTotalFitness; //在所有个体当中最适应的个体的适应性评分 double m_dBestFitness; //所有个体的适应性评分的平均值 double m_dAverageFitness; //在所有个体当中最不适应的个体的适应性评分 double m_dWorstFitness; //最适应的个体在 m_vecPop 容器里面的索引号 int m_iFittestGenome; //基因突变的概率,一般介于 0.05 和 0.3 之间 double m_dMutationRate; //基因交叉的概率一般设为 0.7 double m_dCrossoverRate; //代数的记数器 int m_cGeneration; //构造函数 CGenAlg(); //初始化 m_dTotalFitness, m_dBestFitness, m_dWorstFitness, m_dAverageFitness 等变量 void Reset(); //初始化函数 void init(int popsize, double MutRate, double CrossRate, int GenLenght); //计算 m_dTotalFitness, m_dBestFitness, m_dWorstFitness, m_dAverageFitness 等变量 void CalculateBestWorstAvTot(); //轮盘赌选择函数 CGenome GetChromoRoulette(); //基因变异函数 void Mutate(vector &chromo); //这函数产生新一代基因 void Epoch(vector &vecNewPop); }; 其中 Reset()函数，init()函数和 CalculateBestWorstAvTot()函数都比较简单，读者查看示 例程序的代码就能明白了。而下面分别介绍 init 函数和 Epoch 函数。 类的初始化函数――init 函数 init 函数主要充当 CGenAlg 类的初始化工作，把一些成员变量都变成可供重新开始遗 传算法的状态。（为什么我不在构造函数里面做这些工作呢？因为我的程序里面 CGenAlg 类是 View 类的成员变量，只会构造一次，所以需要另外的初始化函数。）下面是 init 函数 的代码： void CGenAlg::init(int popsize, double MutRate, double CrossRate, int GenLenght) { m_iPopSize = popsize; m_dMutationRate = MutRate; m_dCrossoverRate = CrossRate; m_iChromoLength = GenLenght; m_dTotalFitness = 0; m_cGeneration = 0; m_iFittestGenome = 0; m_dBestFitness = 0; m_dWorstFitness = 99999999; m_dAverageFitness = 0; //清空种群容器，以初始化 m_vecPop.clear(); for (int i=0; i &vecNewPop) { //用类的成员变量来储存父代的基因组(在此之前 m_vecPop 储存的是不带估值的所有基 因组) m_vecPop = vecNewPop; //初始化相关变量 Reset(); //为相关变量赋值 CalculateBestWorstAvTot(); //清空装载新种群的容器 vecNewPop.clear(); //产生新一代的所有基因组 while (vecNewPop.size() < m_iPopSize) { //转盘随机抽出两个基因 CGenome mum = GetChromoRoulette(); CGenome dad = GetChromoRoulette(); //创建两个子代基因组 vector baby1, baby2; //先把他们分别设置成父方和母方的基因 baby1 = mum.vecWeights; baby2 = dad.vecWeights; //使子代基因发生基因突变 Mutate(baby1); Mutate(baby2); //把两个子代基因组放到新的基因组容器里面 vecNewPop.push_back( CGenome(baby1, 0) ); vecNewPop.push_back( CGenome(baby2, 0) ); }//子代产生完毕 //如果你设置的人口总数非单数的话,就会出现报错 if(vecNewPop.size() != m_iPopSize) { AfxMessageBox("你的人口数目不是单数!!!"); return; } } 呵呵，现在我们可以为袋鼠传宗接代了。（细心的读者会发现，上面每次处理两个基因 个体其实是没必要的，恩，那也是为了以后能够使用交叉函数而准备的，因为交叉函数需要 两个相异的个体参与。）接下来，我们要把命令袋鼠跳正式开始的函数（大家注意，这个函 数非 CGenAlg 类的成员函数，而是 CSearchMaxView 类的成员函数，因为这个命令并非 CGenAlg 类自发的，而是由你“通知”CSearchMaxView 类，然后再由 CSearchMaxView 类 通知 CGenAlg 类的。）也一并实现： 上帝的一声令下――OnStartGenAlg 函数 下面将列出 OnStartGenAlg 函数的主要代码（为了不要太占版面，只列出那些关键性的 代码及其解释。），读者要注意里面的适应度评价是怎么实现的。 void CSearchMaxView::OnStartGenAlg() { //产生随机数 srand( (unsigned)time( NULL ) ); //初始化遗传算法引擎 GenAlg.init(g_popsize, g_dMutationRate, g_dCrossoverRate, g_numGen); //清空种群容器 m_population.clear(); //种群容器装进经过随机初始化的种群 m_population = GenAlg.m_vecPop; //定义两个容器，以装进函数的输入与及输出（我们这个函数是单输入单输出的，但是 以后往往不会那么简单，所以我们这里先做好这样的准备。） vector input, output; input.push_back(0); for(int Generation = 0;Generation <= g_Generation;Generation++) { //里面是对每一条染色体进行操作 for(int i=0;i让袋鼠们开始跳吧，开始遗传算法的过程。其中蓝 色的线条是函数曲线（恩，那就是喜玛拉雅山脉。其中最高的波峰，就是珠穆朗玛峰。）绿 色的点是一只只袋鼠。上方的黑色曲线图表是对每一代最优的个体的适应性评分的统计图 表。下方的黑色曲线图表是对每一代所有个体的平均适应性评分的统计图表。（如果你认为 它们阻碍了你的视线，你可以在参数设置里面取消掉。）如图 2-7 所示。另外还可以用键盘 的上下左右键来控制视窗的移动，加减键控制函数曲线的放缩。 图 2-7 刚开始的时候，袋鼠分布得比较分散它们遍布了各个山岭，有的在高峰上，有的在深谷 里。（如图 2-8） 图 2-8 经过了几代的进化后，一些海拔高度比较低的都被我们射杀了，而海拔较高的袋鼠却不 断的生儿育女。（如图 2-9） 图 2-9 最后整个袋鼠种群就只出现在最高峰上面（最优解上）。（如图 2-10） 图 2-10 当然，袋鼠不是每一次都能跳到珠穆朗玛峰的，如图 2-11 所示。（就是说不是每次都 能收敛到最优解）也许它们跳到了某一个山峰，就自大的认为它们已经“会当凌绝顶”了。 （当然，事实上是因为不管它们向前还是向后跳都只能得到更小的适应度，所以不等它们跳 过山谷，再跳到旁边更高的山峰，就被我们射杀了。）所以，我们为了使到袋鼠每次都尽可 能的攀到珠穆朗玛峰，而不是留恋在某一个低一些的山峰，我们有两个改进的办法，其一是 初始人口数目更多一些，以使最好有一些袋鼠一开始就降落到最高峰的附近，但是这种方法 对于搜索空间非常大的问题往往是无能为力的。我们常常采用的方法是使袋鼠有一定的概率 跳一个很大的步长，以使袋鼠有可能跳过一个山谷到更高的山峰去。这些改进的方法留给读 者自己去实现。 图 2-11 另外，如果把变异的机率调得比较高，那么就会出现袋鼠跳得比较活跃的局面，但是很 可能丢失了最优解；而如果变异的机率比较低的话，袋鼠跳得不太活跃，找到最优解的速度 就会慢一些，这也留给读者自己去体验。 作为一个寻找大值的程序，这个的效率还很低。我希望留给初学者更多改进的空间，大 家不必受限于现有的方法，大可以发挥丰富的想象力，自己想办法去提高程序的效率，然后 自己去实现它，让事实去验证你的想法是否真的能提高效率，抑或刚好相反。恩，在这个过 程当中，大家不知不觉地走进了遗传算法的圣殿了，胜于一切繁复公式的摆设和教条式的讲 解。 总结与及扩充 经过本章的学习，我想读者应该能基本上把握遗传算法的基本步骤与及隐约的看到了她 的本质。当然同时还会带着许多许多的疑问和不解。好的，不必急躁，让我们在以后的章节 中慢慢领会。下面我们回顾一下前面所学过的内容，同时也做一些扩充。（为了适应学习新 知识的客观规律，我对知识点的介绍所遵循的原则是：先对理论作简单的介绍，目的是让读 者对新鲜理论有一个感性的认识。然后用实际的例子实现理论并且在实践中加深对理论的理 解。最后对理论作更为深入系统的总结与及扩充。） 对编码方式的回顾与扩充 1．二进制编码 二进制编码的编码符号集由 0 和 1组成，因此染色体是一个二进制符号串，其优点在于 编码、解码操作简单，交叉、变异等遗传操作便于实现，对于全局搜索能力有一定的优势; 其缺点在于，