第5讲遗传算法2011

1遗传算法原理与应用赵鹏[e-mail]21.遗传算法起源遗传算法是由美国的J.Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。一、基本原理3群体变异子群婚配竞争种群淘汰的群体生物进化循环图4遗传算法的主要特征：进化发生在解的编码上，这些编码按生物学的术语称为染色体。由于对解进行了编码，优化问题的一切性质都通过编码来研究。编码和解码是遗传算法的一个主题。自然选择规律决定哪些染色体产生超过平均数的后代。遗传算法中，通过优化问题的目标而人为地构造适应函数以达到好的染色体产生超过平均数的后代。当染色体结合时，双亲的遗传基因的结合使得子女保持父母的特征。当染色体结合后，随机的变异会造成子代同父代的不同。5生物遗传概念在遗传算法中的对应关系生物遗传概念遗传算法中的作用适者生存在算法停止时，最优目标值的解有最大的可能被保留个体(individual)解染色体(chromosome)解的编码（字符串，向量等）基因(gene)解中每一分量的特征（如各分量的值）适应性(fitness)适应函数值群体(population)选定的一组解（其中解的个数为群体的规模）种群(reproduction)根据适应函数值选取的一组解交配(crossover)通过交配原则产生一组新解的过程变异(mutation)编码的某一个分量发生变化的过程6遗传算法主要处理步骤首先是对优化问题的解进行编码，称一个解的编码为一个染色体，组成编码的元素称为基因。编码的目的主要是用于优化问题解的表现形式和利于之后遗传算法中的计算。第二是适应函数的构造和应用。适应函数基本上依据优化问题的目标函数而定。当适应函数确定以后，自然选择规律是以适应函数值的大小决定的概率分布来确定哪些染色体适应生存，哪些被淘汰。生存下来的染色体组成种群，形成一个可以繁衍下一代的群体。第三是染色体的结合。双亲的遗传基因结合是通过编码之间的交配达到下一代的产生。新一代的产生是一个生殖过程，它产生了一个新解。最后是变异。新解产生过程中可能发生基因变异，变异使某些解的编码发生变化，使解有更大的遍历性。72、基本遗传算法基本遗传算法（SimpleGeneticAlgorithms，简称SGA，又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。基本遗传算法的组成（1）编码（产生初始种群）（2）适应度函数（3）遗传算子（选择、交叉、变异）（4）运行参数8函数优化示例求下列一元函数的最大值：x∈[-1,2]，求解结果精确到6位小数。0.2)10sin()(xxxfGA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。SGA使用二进制串进行编码。编码9SGA对于本例的编码由于区间长度为3，求解结果精确到6位小数，因此可将自变量定义区间划分为3×106等份。又因为2213×106222，所以本例的二进制编码长度至少需要22位，本例的编码过程实质上是将区间[-1，2]内对应的实数值转化为一个二进制串（b21b20…b0）。10几个术语基因型：1000101110110101000111表现型：0.637197编码解码个体（染色体）基因11初始种群SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。适应度函数遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。12选择算子遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。13轮盘赌选择示意s40.31s20.49s10.14s30.06●盘轮赌选择法14轮盘赌选择方法轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，个体i的适应度为Fi，则个体i被选中遗传到下一代群体的概率为：niiiiFFP1/15轮盘赌选择方法的实现步骤（1）计算群体中所有个体的适应度函数值（需要解码）；（2）利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；（3）采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。16交叉算子所谓交叉运算，是指对两个相互配对的染色体依据交叉概率Pc按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。SGA中交叉算子采用单点交叉算子。17单点交叉运算交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉点18变异算子所谓变异运算，是指依据变异概率Pm将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。SGA中变异算子采用基本位变异算子。19基本位变异算子基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。20基本位变异算子的执行过程变异前：000001110000000010000变异后：000001110001000010000变异点21运行参数（1）M：种群规模（2）T：遗传运算的终止进化代数（3）Pc：交叉概率（4）Pm：变异概率22SGA的框图初始种群24遗传算法应用举例利用遗传算法求解区间［0,31］上的二次函数y=x2的最大值。y=x231XY25分析原问题可转化为在区间［0,31］中搜索能使y取最大值的点a的问题。那么，［0,31］中的点x就是个体,函数值f(x)恰好就可以作为x的适应度，区间［0,31］就是一个(解)空间。这样,只要能给出个体x的适当染色体编码,该问题就可以用遗传算法来解决。26解(1)设定种群规模,编码染色体，产生初始种群。将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)(2)定义适应度函数,取适应度函数：f(x)=x227(3)计算各代种群中的各个体的适应度,并对其染色体进行遗传操作,直到适应度最高的个体(即31（11111）)出现为止。28首先计算种群S1中各个体s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)的适应度f(si)。容易求得f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=36129再计算种群S1中各个体的选择概率。NjjiixfxfxP1)()()(选择概率的计算公式为由此可求得P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.3130赌轮选择示意s40.31s20.49s10.14s30.06●赌轮选择法31在算法中赌轮选择法可用下面的子过程来模拟:①在［0,1］区间内产生一个均匀分布的随机数r。②若r≤q1,则染色体x1被选中。③若qk-1r≤qk(2≤k≤N),则染色体xk被选中。其中的qi称为染色体xi(i=1,2,…,n)的积累概率,其计算公式为ijjixPq1)(32选择-复制设从区间［0,1］中产生4个随机数如下:r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503染色体适应度选择概率积累概率选中次数s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.00133于是，经复制得群体：s1’=11000（24）,s2’=01101（13）s3’=11000（24）,s4’=10011（19）34交叉设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。设s1’与s2’配对，s3’与s4’配对。分别交换后两位基因，得新染色体：s1’’=11001（25）,s2’’=01100（12）s3’’=11011（27）,s4’’=10000（16）35变异设变异率pm=0.001。这样，群体S1中共有5×4×0.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。36于是，得到第二代种群S2：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）37第二代种群S2中各染色体的情况染色体适应度选择概率积累概率估计的选中次数s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.00138假设这一轮选择-复制操作中，种群S2中的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）这一轮仍然不会发生变异。39于是，得第三代种群S3：s1=11100（28）,s2=01001（9）s3=11000（24）,s4=10011（19）40第三代种群S3中各染色体的情况染色体适应度选择概率积累概率估计的选中次数s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.00141设这一轮的选择-复制结果为：s1’=11100（28）,s2’=11100（28）s3’=11000（24）,s4’=10011（19）做交叉运算，让s1’与s4’，s2’与s3’分别交换后两位基因，得s1’’=11111（31）,s2’’=11100（28）s3’’=11000（24）,s4’’=10000（16）这一轮仍然不会发生变异。42于是，得第四代种群S4：s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（16）43显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。44YYy=x28131924X第一代种群及其适应度y=x212162527XY第二代种群及其适应度y=x29192428XY第三代种群及其适应度y=x216242831X第四代种群及其适应度45遗传算法的描述Step1选择问题的一个编码；给出一个有N个染色体的初始群体pop(1),t:=1;S