高级推理――GA

人工智能（ArtificialIntelligence，AI）刘春阳机器人与智能接口研究所Tel：51963500第4章基于遗传算法的随机优化搜索第4章基于遗传算法的随机优化搜索4.14.2基本遗传算法4.3遗传算法应用举例4.4遗传算法的特点与优势习题四第4章基于遗传算法的随机优化搜索4.1基本概念1.适应度(fitness)就是借鉴生物个体对环境的适应程度,而对所求解问题中的对象设计的一种表征优劣的测度。适应度函数(fitnessfunction)就是问题中的全体对象与其适应度之间的一个对应关系,即对象集合到适应度集合的一个映射。它一般是定义在论域空间上的一个实数值函数。第4章基于遗传算法的随机优化搜索2.染色体及其编码遗传算法以生物细胞中的染色体(chromosome)代表问题中的个体对象。而一个染色体可以看作是由若干基因组成的位串,所以需要将问题中的个体对象编码为某种位串的形式。这样,原个体对象也就相当于生命科学中所称的生物体的表现型(phenotype),而其编码即“染色体”也就相当于生物体的基因型(genotype)。遗传算法中染色体一般用字符串表示,而基因也就是字符串中的一个个字符。例如,假设数字9是某问题中的个体对象,则我们就可以用它的二进制数串1001作为它的染色体编码。第4章基于遗传算法的随机优化搜索3.种群种群(population)就是模拟生物种群而由若干个染色体组成的群体,它一般是整个论域空间的一个很小的子集。遗传算法就是通过在种群上实施所称的遗传操作,使其不断更新换代而实现对整个论域空间的搜索。第4章基于遗传算法的随机优化搜索4.遗传操作遗传算法中有三种关于染色体的运算:选择-复制、交叉和变异,这三种运算被称为遗传操作或遗传算子(geneticoperator)。第4章基于遗传算法的随机优化搜索选择-复制选择-复制(selectionreproduction)操作是模拟生物界优胜劣汰的自然选择法则的一种染色体运算,就是从种群中选择适应度较高的染色体进行复制,以生成下一代种群。选择-复制的通常做法是,对于一个规模为N的种群S,按每个染色体xi∈S的选择概率P(xi)所决定的选中机会,分N次从S中随机选定N个染色体,并进行复制。这里的选择概率P(xi)的计算公式为NjjiixfxfxP1)()()((4-1)第4章基于遗传算法的随机优化搜索其中,f为适应度函数,f(xi)为xi的适应度。可以看出,染色体xi被选中的概率就是其适应度f(xi)所占种群中全体染色体适应度之和的比例。显然,按照这种选择概率定义,适应度越高的染色体被随机选定的概率就越大,被选中的次数也就越多,从而被复制的次数也就越多。相反,适应度越低的染色体被选中的次数也就越少,从而被复制的次数也就越少。如果把复制看做染色体的一次换代的话,则这就意味着适应度越高的染色体其后代也就越多,适应度越低的染色体其后代也就越少,甚至被淘汰。这正吻合了优胜劣汰的自然选择法则。第4章基于遗传算法的随机优化搜索图4-1赌轮选择示例第4章基于遗传算法的随机优化搜索上述按概率选择的方法可用一种称为赌轮的原理来实现。即做一个单位圆,然后按各个染色体的选择概率将圆面划分为相应的扇形区域(如图4-1所示)。这样,每次选择时先转动轮盘,当轮盘静止时,上方的指针所正对着的扇区即为选中的扇区,从而相应的染色体即为所选定的染色体。例如,假设种群S中有4个染色体:s1,s2,s3,s4,其选择概率依次为:0.11,0.45,0.29,0.15,则它们在轮盘上所占的份额如图4－1中的各扇形区域所示。第4章基于遗传算法的随机优化搜索在算法中赌轮选择法可用下面的子过程来模拟:①在［0,1］区间内产生一个均匀分布的伪随机数r。②若r≤q1,则染色体x1被选中。③若qk-1r≤qk(2≤k≤N),则染色体xk被选中。其中的qi称为染色体xi(i=1,2,…,n)的积累概率,其计算公式为ijjixPq1)(第4章基于遗传算法的随机优化搜索一个染色体xi被选中的次数,也可以用下面的期望值e(xi)来确定。fxfNxfxfNxfxfNxPxeiNjjiNjjiii)(/)()()()()()(11(4-2)其中f为种群S中全体染色体的平均适应度。第4章基于遗传算法的随机优化搜索交叉交叉(crossover)亦称交换、交配或杂交,就是互换两个染色体某些位上的基因。例如,设染色体s1=01001011,s2=10010101,交换其后4位基因,即则得新串s1′=01000101,s2′=10011011。s1′和s2′可以看做是原染色体s1和s2的子代染色体。变异变异(mutation)亦称突变,就是改变染色体某个(些)位上的基因。例如,把染色体s=11001101的第三位上的0变为1,则得到新染色体s′=11101101。第4章基于遗传算法的随机优化搜索4.2基本遗传算法简单来讲,遗传算法就是对种群中的染色体反复做三种遗传操作,使其朝着适应度增高的方向不断更新换代,直至出现了适应度满足目标条件的染色体为止。遗传算法的基本框架如图4-2所示。在算法的具体步骤中,还需给出若干控制参数,如种群规模、最大换代数、交叉率和变异率等等。——种群规模就是种群的大小,用染色体的个数表示。——最大换代数就是算法中种群更新换代的上限,它也是算法终止的一个条件。第4章基于遗传算法的随机优化搜索——交叉率[WTBZ](crossoverrate)就是参加交叉运算的染色体个数占全体染色体总数的比例，记为Pc,取值范围一般为0.4～0.99。由于生物繁殖时染色体的交叉是按一定的概率发生的,因此参加交叉操作的染色体也有一定的比例,而交叉率也就是交叉概率。——变异率(mutationrate)是指发生变异的基因位数所占全体染色体的基因总位数的比例，记为Pm，取值范围一般为0.0001～0.1。由于在生物的繁衍进化过程中,变异也是按一定的概率发生的,而且发生概率一般很小,因此变异率也就是变异概率。第4章基于遗传算法的随机优化搜索基本遗传算法：步1在论域空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T；步2随机产生U中的N个染色体s1,s2,…,sN，组成初始种群S={s1,s2,…,sN}，置代数计数器t=1；步3计算S中每个染色体的适应度f()；步4若终止条件满足，则取S中适应度最大的染色体作为所求结果，算法结束。步5按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个染色体并将其复制，共做N次，然后将复制所得的N个染色体组成群体S1；第4章基于遗传算法的随机优化搜索步6按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；步7按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；步8将群体S3作为新一代种群，即用S3代替S，t=t+1，转步3；第4章基于遗传算法的随机优化搜索需要说明的是,遗传算法的具体表述在各个文献中并不太一致,本书给出的这一表述,只是遗传算法的基本步骤,所以我们称其为基本遗传算法。该算法描述与所称的简单遗传算法(SimpleGeneticAlgorithm，SGA)基本一致。简单遗传算法是D.J.Goldberg总结出的一种统一的最基本的遗传算法。在简单遗传算法的基础上,现在已派生出遗传算法的许多变形,可以说已形成了一个遗传算法家族。在应用遗传算法解决实际问题时,还需给出结构模式的表示方案、适应度的计算方法、终止条件等。表示方案通常是把问题的搜索空间的每一个可能的点,编码为一个看做染色体的字符串,字符通常采用二进制数0、1。适应度的计算方法一般根据实际问题而定。第4章基于遗传算法的随机优化搜索4.3遗传算法应用举例例4.1利用遗传算法求解区间［0,31］上的二次函数y=x2的最大值。分析可以看出,只要能在区间［0,31］中找到函数值最大的点a,则函数y=x2的最大值也就可以求得。于是,原问题转化为在区间［0,31］中寻找能使y取最大值的点a的问题。显然,对于这个问题,任一点x∈［0,31］都是可能解,而函数值f(x)=x2也就是衡量x能否为最佳解的一种测度。那么,用遗传算法的眼光来看,区间［0,31］就是一个(解)空间,x就是其中的个体对象,函数值f(x)恰好就可以作为x的适应度。这样,只要能给出个体x的适当染色体编码,该问题就可以用遗传算法来解决。第4章基于遗传算法的随机优化搜索解(1)定义适应度函数,编码染色体。由上面的分析,函数f(x)=x2就可作为空间U上的适应度函数。显然y=x2是一个单调增函数,其取最大值的点x=31是个整数。另一方面,5位二进制数也刚好能表示区间［0,31］中的全部整数。所以,我们就仅取［0,31］中的整数来作为参加进化的个体,并且用5位二进制数作为个体x的基因型编码,即染色体。(2)设定种群规模,产生初始种群。我们将种群规模设定为4,取染色体s1=01101(13),s2=11000(24),s3=01000(8),s4=10011(19)组成初始种群S1。第4章基于遗传算法的随机优化搜索(3)计算各代种群中的各染色体的适应度,并进行遗传操作,直到适应度最高的染色体(该问题中显然为“11111”=31)出现为止。计算S1中各染色体的适应度、选择概率、积累概率等并列于表4.1中。第4章基于遗传算法的随机优化搜索表4.1第一代种群S1中各染色体的情况染色体适应度选择概率积累概率估计被选中次数s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001第4章基于遗传算法的随机优化搜索选择-复制设从区间［0,1］中产生4个随机数如下:r1=0.450126,r2=0.110347,r3=0.572496,r4=0.98503按赌轮选择法，染色体s1,s2,s3,s4的被选中次数依次为：1,2,0,1。于是，经复制得群体：s1’=11000（24）,s2’=01101（13）,s3’=11000（24）,s4’=10011（19）可以看出，在第一轮选择中适应度最高的染色体s2被选中两次，因而被复制两次；而适应度最低的染色体s3一次也没有选中而遭淘汰。第4章基于遗传算法的随机优化搜索交叉设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。设s1’与s2’配对，s2’与s4’配对。分别交换后两位基因，得新染色体：s1’’=11001（25）,s2’’=01100（12）,s3’’=11011（27）,s4’’=10000（16）变异设变异率pm=0.001。这样，群体S1中共有540.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。现在，我们得到了第二代种群S2：s1=11001（25）,s2=01100（12）,s3=11011（27）,s4=10000（16）第4章基于遗传算法的随机优化搜索表4.2第二代种群S2中各染色体的情况染色体适应度选择概率积累概率估计被选中次数s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.001第4章基于遗传算法的随机优化搜索假设这一轮选择-复制操作中，种群S2中的4个染色体都被选中（因为选择概率毕竟只是一种几率，所以4个染色体恰好都被选中的情况是存在的），我们得到群体：s1’=11001（25）,s2’=01100（12）,s3’=11011（27）,s4’=10000（16）然后，做交叉运算，让s1’与s2’，s3’与s4’分别交换后三位基因，得s1’’=11100（28）,s2’’=01001（9）,s3’’=11000（24）,s4’’=10011（19）这一轮仍然不会发生