《遗传算法理解》由会员分享，可在线阅读，更多相关《遗传算法理解（15页珍藏版）》请在金锄头文库上搜索。
1、一、遗传算法的结构二、遗传算法的基本原理三、遗传算法的收敛性四、遗传算法的性能五、遗传算法展望第四节 遗传算法遗传算法是仿真生物遗传学和自然选择机理，通过人工方式所构造的一类搜索算法，从 某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。霍兰德（ Holland ）于 1975 年在他的著作Adaptation in Natural and Artificial Systems首次提出遗传算法，并主要由 他和他的学生发展起来的。生物种群的生存过程普遍遵循达尔文进化准则，群体中的个体根据对环境的适应能力而 被大自然所选择或淘汰。进化过程的结果反映在个体的结构上，其染色体包含若干基因，相 应
2、的表现型和基因型的联系体现了个体的外部特性与内部机理间逻辑关系。通过个体之间的 交叉、变异来适应大自然环境。生物染色体用数学方式或计算机方式来体现就是一串数码， 仍叫染色体，有时也叫个体；适应能力是对应着一个染色体的一个数值来衡量；染色体的选 择或淘汰则按所面对的问题是求最大还是最小来进行。遗传算法自从 1975年提出以来，在国际上已经形成了一个比较活跃的研究领域，已召开 了多次比较重要的国际会议和创办了很多相关的国际刊物。遗传算法已用于求解带有应用前景的一些问题，例如遗传程序设计、函数优化、排序问 题、人工神经网络、分类系统、计算机图像处理和机器人运动规划等。一、遗传算法的结构霍兰德（Hol
3、land ）的遗传算法通常被称为“简单遗传算法”简称SGA ），我们以此作为 讨论主要对象，加上适应的改进，分析遗传算法的结构和机理。我们首先介绍主要的概念。我们在讲解中会结合如下的货郎担问题（Travelling Salesman Problem，简记为TSP）：设有n个城市，城市i和城市j之间的距离为d （i, j） i, j=1, ，n。TSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短。1. 编码与译码许多应用问题结构很复杂，但可以化为简单的位串形式编码表示，我们将问题结构变换 为位串形式编码表示的过程叫编码；而相反将位串形式编码表示变换为原问题结构的过程叫 译码或解
4、码。 ，有时也叫个体。对TSP可以按一条回路城市的次序进行编码，比如码串134567829表示从城市1开始， 依次是城市3, 4, 5, 6, 7, 8, 2, 9,最后回到城市1。一般情况是从城市w1开始，依次经 过城市w2,wn,最后回到城市w1,我们就有如下编码表示：w1 w2 wn由于是回路，记wn+1=w1。它其实是1, n的一个循环排列。要注意w1,w2, , wn 是互不相同的。2. 适应度函数乞日（WjRj+J为了体现染色体的适应能力,引入了对问题中的每一个染色体都能进行度量的函数,叫 适应度函数。通过适应度函数来决定染色体的优、劣程度,它体现了自然进化中的优利劣汰 原则。对优
5、化问题，适应度函数就是目标函数。TSP的目标是路径总长度为最短，路径总长 度的倒数就可以为TSP的适应度函数：1请注意其中 wn+1=w1。适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距,一个染色体与 问题的最优解染色体之间的差距小,则对应的适应度函数值之差就小,否则就大。适应度函 数的取值大小与求解问题对象的意义有很大的关系。3. 遗传操作简单遗传算法的遗传操作主要有三种：选择(selection )、交叉(crossover)、变异 (mutation)。改进的遗传算法大量扩充了遗传操作，以达到更高的效率。选择操作也叫复制操作,根据个体的适应度函数值所度量的优、劣程度决定它
6、在下一代 是被淘汰还是被遗传。一般地说,选择将使适应度较大(优良)个体有较大的存在机会,而 适应度较小(低劣)的个体继续存在的机会也较小。简单遗传算法采用赌轮选择机制，令 乞匚表示群体的适应度值之总和，有表示种群中第i个染色体的适应度值，它产生后代的能 力正好为其适应度值所占份额。交叉操作的简单方式是将被选择出的两个个体P1和P2作为父母个体，将两者的部分码 值进行交换。假设有如下八位长的二个体：产生一个在1到7之间的随机数c,假如现在产生的是3,将P1和P2的低三位交换：P1 的高五位与P2的低三位组成数串10001001，这就是P1和P2的一个后代Q1个体；P2的高 五位与P1的低三位组成
7、数串11011110，这就是P1和P2的一个后代Q2个体。其交换过程如 下图所示：图 5-4-1 交叉示意图让我们来讨论TSP的交叉操作作为较复杂的例子，举例如下：以下标作为交叉位置的编号，设已选择了如下两个染色体：w1 w2 wnz1 z2 zn随机产生一个1和n-1之间的数k,将此二染色体中前k个城市作交换，得到：z1 z2 zk wk+1 wk+2 wnw1 w2 wk zk+1 zk+2 zn但这两个可能不是合法的染色体，因为可能有重复的数码，要进行如下的合法化处理：首先 对 z1 z2zk wk+1 wk+2wn 进行改造。将 z1 z2zk 和 wk+1 wk+2wn 中的数字进行
8、比较，如果在wk+1 wk+2wn中出现了 z1 z2zk的数字，就在wk+1wk+2wn中删除这些数字，剩下来的总数串就没有n个了，也就是说不是1，n的 一个全排列，其中缺少的数字是w1 w2wk中的某些数字，因此按w1 w2wk的顺序将缺少的数字取出来补到z1 z2zk wk+1 wk+2wn的后面。如此繁杂的过程可以简化如下，首先将w1 w2wk加到z1 z2zk wk+1 wk+2wn后面，得到：z1 z2 zk wk+1 wk+2 wn w1 w2 wk从这个数串的wk+1 wk+2wn中删除wk+1 wk+2wn已出现在z1 z2zk中的数字，接着从w1 w2wk部分中删除已出现在
9、z1 z2zk wk+1 wk+2wn中的那些数字 ，得到的是一个合法的染色体。同样对另一个不合法染色体进行类似合法化。变异操作的简单方式是改变数码串的某个位置上的数码。我们先以最简单的二进制编码 表示方式来说明，二进制编码表示的每一个位置的数码只有0与1这两个可能，比如有如下二 进制编码表示：1：01:C111其码长为8,随机产生一个1至8之间的数k,假如现在k=5,对从右往左的第5位进行变异操作，将原来的0变为1，得到如下数码串（红色的数字1是被变异操作后出现的）：二进制编码表示时的简单变异操作是将0与1互换：0变异为1, 1变异为0。现在对TSP的变异操作作简单介绍，随机产生一个1至n之
10、间的数k,决定对回路中的 第k个城市的代码wk作变异操作，又产生一个1至n之间的数w,替代wk,并将wk加到尾 部,得到： （也就是说在哪里变异和变异成多少都是随机的）w1 w2 wk-1 w wk+1 wn wk你发现这个串有n+1个数码，注意数w其实在此串中出现重复了，必须删除与数w相重 复的,得到合法的染色体。4. 控制参数并不是所有被选择了的染色体都要进行交叉操作和变异操作,而是以一定的概率进行, 一般在程序设计中交叉发生的概率要比变异发生的概率选取得大若干个数量级,交叉概率取 0.6至 0.95之间的值；变异概率取0.001至0.01之间的值。种群的染色体总数叫种群规模,它对算法的效
11、率有明显的影响,规模太小不得于进化, 而规模太大将导致程序运行时间长。对不同的问题可能有各自适合的种群规模,通常种群规 模为 30至100。另一个控制参数是个体的长度,有定长和变长两种。它对算法的性能也有影响。二、遗传算法的基本原理遗传算法类似于自然进化，通过作用于染色体上的基因寻找好的染色体来求解问题。与 自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染 色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗 传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始群体；通 过适应度函数给每个个体一个数值评价，淘汰低适
12、应度的个体，选择高适应度的个体参加遗 传操作，经过遗传操作后的个体集合形成下一代新的种群。对这个新种群进行下一轮进化。 这就是遗传算法的基本原理。下面就是遗传算法思想，也是简单遗传算法的求解步骤如下：（1）初始化群体；（2）计算群体上每个个体的适应度值；（3）按由个体适应度值所决定的某个规则选择将进入下一代的个体；（4）按概率Pc进行交叉操作；（5）按概率Pc进行突变操作；（ 6） 没有满足某种停止条件，则转第（ 2）步，否则进入（ 7）。（7） 输出种群中适应度值最优的 染色体作为问题 的满意解或最优解。程序的停止条件最简单的有如下二种：完成了预先给定的进化代数则停止；种群中的最 优个体在连
13、续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。根据遗传算法思想可以画出如图5-4-2所示的简单遗传算法框图：A赧件经束输工差含度值 最优的牛休变异操作汁算总应度值选擇操作C）柳始化种辭选择操作 I交黒操作图 5-4-2简单遗传算法框图 一般遗传算法的主要步骤如下：（1）随机产生一个由确定长度的特征字符串组成的初始群体。（2）对该字符串群体迭代地执行下面的步骤和步骤直到满足停止准则为止：a计算群体中每个个体字符串的适应值；b应用复制、交叉和变异等遗传算子产生下一代群体。（3）把在后代中 出现的最好的个体字符串指字为遗传算法的执行结果，这个结果可以 表示问题的一个解也可将遗传算法的一
14、般结构表示为如下形式：Procedure： Genetic Algorithmsbegint 、- 0 ；initialize P( t)；evaluate P（r）；while（not termination condition）dobeginrecombine P（t） to yield C（t）；evaluate C（t）；select P（t+1）from P（t） and C（t）t 冬-t + 1 ;endend遗传算法求解举例 为了便于理解，下面通过一个简单的例子来说明遗传算法的主要内容及其运行步骤 例5.1用遗传算法求解函数f （s） = si-sin （1 On唸）+1.0的
15、最大值，其中盘匡卜习。首先用高等数学的方法求解。先求得函数的导数令其为0：f = sm fl0jix）+10nxcos （10兀芷）二 0变换得到：tan （10兀盜）二-IOju;很明显，以上方程无数解：其中Ei表示趋向于0的递减实数序列。当i为奇数时，珥勒)；当i为偶数时，珥蓋筈19间-1 2中，当达到了它的极大值37 =+ E19 =LS5 + Eb)时，f (x)最大，它仅比为极小值。在区fQ.851.85-sinl8n + - +1.0= 2.85稍大。面构造一个遗传算法来求解上面的问题。把遗传算法归纳为5个基本组成部分：(1) 方案表示(最优解是个数值，而不是平时所熟悉的数码组合，但是数值可以通过转 化成二进制的形式变成数码组合的形式，值得借鉴。)用一个二进制矢量表示一个染色体，由染色体来代表变量x的实数值，每个染色体的每- 位二进制数称为遗传因子。矢量的长度取决于所要求的精度，在此取小数点后6位数。由
