遗传算法2011课件.pptx

会计学1遗传算法遗传算法2011课件课件21.1.1.1.遗传算法起源遗传算法起源遗传算法起源遗传算法起源 n n 遗传算法是由美国的遗传算法是由美国的J.HollandJ.Holland教授于教授于19751975年在他的专年在他的专著著自然界和人工系统的适应性自然界和人工系统的适应性中首先提出的，它是一类中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。借鉴生物界自然选择和自然遗传机制的随机化搜索算法。一一、基本原理、基本原理 第1页/共70页3生物进化循环图生物进化循环图第2页/共70页4生物遗传概念在遗传算法中的对应关系生物遗传概念在遗传算法中的对应关系生物遗传概念遗传算法中的作用适者生存在算法停止时，最优目标值的解有最大的可能被保留个体(individual)解染色体(chromosome)解的编码（字符串，向量等）基因(gene)解中每一分量的特征（如各分量的值）适应性(fitness)适应函数值群体(population)选定的一组解（其中解的个数为群体的规模）种群(reproduction)根据适应函数值选取的一组解交配(crossover)通过交配原则产生一组新解的过程变异(mutation)编码的某一个分量发生变化的过程第3页/共70页5遗传算法的主要特征：遗传算法的主要特征：进化发生在解的编码上，这些编码按生物学的术语称为染色体。由于对解进行了编码，优化问题的一切性质都通过编码来研究。编码和解码是遗传算法的一个主题。自然选择规律决定哪些染色体产生超过平均数的后代。遗传算法中，通过优化问题的目标而人为地构造适应函数以达到好的染色体产生超过平均数的后代。当染色体结合时，双亲的遗传基因的结合使得子女保持父母的特征。当染色体结合后，随机的变异会造成子代同父代的不同。第4页/共70页6遗传算法主要处理步骤遗传算法主要处理步骤 首先是对优化问题的解进行编码，称一个解的编码为一个染色体，组成编码的元素称为基因。编码的目的主要是用于优化问题解的表现形式和利于之后遗传算法中的计算。第二是适应函数的构造和应用。适应函数基本上依据优化问题的目标函数而定。当适应函数确定以后，自然选择规律是以适应函数值的大小决定的概率分布来确定哪些染色体适应生存，哪些被淘汰。生存下来的染色体组成种群，形成一个可以繁衍下一代的群体。第三是染色体的结合。双亲的遗传基因结合是通过编码之间的交配达到下一代的产生。新一代的产生是一个生殖过程，它产生了一个新解。最后是变异。新解产生过程中可能发生基因变异，变异使某些解的编码发生变化，使解有更大的遍历性。第5页/共70页72 2 2 2、基本遗传算法、基本遗传算法、基本遗传算法、基本遗传算法n n 基本遗传算法（基本遗传算法（Simple Genetic AlgorithmsSimple Genetic Algorithms，简称，简称SGASGA，又称简单遗传算法或标准遗传算法），是由，又称简单遗传算法或标准遗传算法），是由GoldbergGoldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。容易理解，是其它一些遗传算法的雏形和基础。基本遗传算法的组成（1）编码（产生初始种群）（2）适应度函数（3）遗传算子（选择、交叉、变异）（4）运行参数第6页/共70页8函数优化示例函数优化示例函数优化示例函数优化示例 n n求下列一元函数的最大值求下列一元函数的最大值：x-1,2 x-1,2 ，求解结果精确到，求解结果精确到6 6位小数。位小数。GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。SGA使用二进制串进行编码。编码 第7页/共70页9SGASGASGASGA对于本例的编码对于本例的编码对于本例的编码对于本例的编码 n n 由于区间长度为由于区间长度为3 3，求解结果精确到，求解结果精确到6 6位小数，因此位小数，因此可将自变量定义区间划分为可将自变量定义区间划分为3 310106 6等份。又因为等份。又因为2 22121 310 3106 6 2 22222 ，所以本例的二进制编码长度至少，所以本例的二进制编码长度至少需要需要需要需要22222222位位位位，本例的，本例的编码过程实质上是将区间编码过程实质上是将区间-1-1，22内对应的实数值转化为一个内对应的实数值转化为一个二进制串（二进制串（b21b20b21b20b0b0）。）。第8页/共70页10几个术语几个术语几个术语几个术语 n n基因型：1000101110110101000111 表现型：0.637197 编码解码个体（染色体）基因第9页/共70页11n n初始种群初始种群n n SGASGA采用随机方法生成若干个个体的集合，该集合称为初采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中始种群。初始种群中个体的数量称为种群规模个体的数量称为种群规模。n n 适应度函数适应度函数 n n 遗传算法对一个个体（遗传算法对一个个体（解）的好坏用适应度函数值来评解）的好坏用适应度函数值来评价，价，适应度函数值越大，解的质量越好。适应度函数是遗传适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。的设计应结合求解问题本身的要求而定。第10页/共70页12选择算子选择算子选择算子选择算子n n 遗传算法使用选择运算来实现对群体中的个体进行优遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。遗传到下一代群体。SGASGA中选择算子采用中选择算子采用轮盘赌选择方法轮盘赌选择方法。第11页/共70页13轮盘赌选择示意s40.31s20.49s10.14s30.06轮盘赌选择法第12页/共70页14轮盘赌选择方法轮盘赌选择方法轮盘赌选择方法轮盘赌选择方法n n 轮盘赌选择又称轮盘赌选择又称比例选择算子比例选择算子，它的基本思想是：各，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体个个体被选中的概率与其适应度函数值大小成正比。设群体大小为大小为n n，个体，个体i i 的适应度为的适应度为 F Fi i，则个体，则个体i i 被选中遗传到下被选中遗传到下一代群体的概率为：一代群体的概率为：第13页/共70页15轮盘赌选择方法的实现步骤轮盘赌选择方法的实现步骤轮盘赌选择方法的实现步骤轮盘赌选择方法的实现步骤n n（1 1）计算群体中所有个体的适应度函数值（需要解码）；计算群体中所有个体的适应度函数值（需要解码）；n n（2 2）利用比例选择算子的公式，计算每个个体被选中利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；遗传到下一代群体的概率；n n（3 3）采用模拟赌盘操作（即生成采用模拟赌盘操作（即生成0 0到到1 1之间的随机数与之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。个个体是否遗传到下一代群体中。第14页/共70页16交叉算子交叉算子交叉算子交叉算子 n n 所谓交叉运算，是指对两个相互配对的染色体依据所谓交叉运算，是指对两个相互配对的染色体依据交叉概率交叉概率 P Pc c 按某种方式按某种方式相互交换其部分基因相互交换其部分基因，从而形成两，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。主要方法。SGASGA中交叉算子采用单点交叉算子。中交叉算子采用单点交叉算子。第15页/共70页17单点交叉运算单点交叉运算单点交叉运算单点交叉运算 n n交叉前：n n00000|01110000000010000n n11100|00000111111000101n n交叉后：n n00000|00000111111000101n n11100|01110000000010000交叉点交叉点第16页/共70页18变异算子变异算子变异算子变异算子 n n 所谓变异运算，是指依据变异概率所谓变异运算，是指依据变异概率 P Pm m 将个体编码将个体编码串中的串中的某些基因值用其它基因值来替换某些基因值用其它基因值来替换，从而形成一个新，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。间的全局搜索和局部搜索。SGASGA中变异算子采用基本位变中变异算子采用基本位变异算子。异算子。第17页/共70页19基本位变异算子基本位变异算子基本位变异算子基本位变异算子 n n 基本位变异算子是指对个体编码串基本位变异算子是指对个体编码串随机指定的某一随机指定的某一位或某几位基因作变异运算位或某几位基因作变异运算。对于基本遗传算法中用二进制。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为座上的原有基因值为0 0，则变异操作将其变为，则变异操作将其变为1 1；反之，若原；反之，若原有基因值为有基因值为1 1，则变异操作将其变为，则变异操作将其变为0 0。第18页/共70页20基本位变异算子的执行过程基本位变异算子的执行过程基本位变异算子的执行过程基本位变异算子的执行过程 n n变异前：n n000001110000000010000n n变异后：n n000001110001000010000变异点变异点第19页/共70页21运行参数运行参数运行参数运行参数 n n（1 1）M M ：种群规模种群规模 n n（2 2）T T ：遗传运算的终止进化代数遗传运算的终止进化代数 n n（3 3）P Pc c ：交叉概率交叉概率 n n（4 4）P Pm m：变异概率变异概率 第20页/共70页初始种群初始种群第21页/共70页23遗传算法应用举例 利用遗传算法求解区间0,31上的二次函数y=x2的最大值。y=x2 31 XY第22页/共70页24n n 分析分析 n n 原问题可转化为在区间原问题可转化为在区间0,310,31中搜中搜索能使索能使y y取最大值的点取最大值的点a a的问题。那么，的问题。那么，0,0,3131 中的点中的点x x就是个体就是个体,函数值函数值f f(x x)恰好就可以恰好就可以作为作为x x的适应度，区间的适应度，区间0,310,31就是一个就是一个(解解)空间空间 。这样。这样,只要能给出个体只要能给出个体x x的适当染色体的适当染色体编码编码,该问题就可以用遗传算法来解决。该问题就可以用遗传算法来解决。第23页/共70页25解(1)设定种群规模,编码染色体，产生初始种群。将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)(2)定义适应度函数,取适应度函数：f(x)=x2 第24页/共70页26(3)计算各代种群中的各个体的适应度,并对其染色体进行遗传操作,直到适应度最高的个体(即31（11111）)出现为止。第25页/共70页27n n 首先计算种群首先计算种群S S1 1中各个体中各个体n n s s1 1=13(01101),=13(01101),s s2 2=24(11000)=24(11000)n n s s3 3=8(01000),=8(01000),s s4 4=19(10011)=19(10011)n n的适应度的适应度f f(s si i)。n n 容易求得容易求得n n f f(s s1 1)=)=f f(13)=13(13)=132 2=169=169n n f f(s s2 2)=)=f f(24)=24(24)=242 2=576=576n n f f(s s3 3)=)=f f(8)=8(8)=82 2=64=64n n f f(s s4 4)=)=f f(19)=19(19)=192 2=361=361第26页/共70页28n n再计算种群再计算种群S S1 1中各个体的选择概率。中各个体的选择概率。选择概率的计算公式为 由此可求得 P(s1)=P(13)=0.14 P(s2)=P(24)=0.49 P(s3)=P(8)=0.06 P(s4)=P(19)=0.31第27页/共70页29 赌轮选择示意s40.31s20.49s10.14s30.06 赌轮选择法第28页/共70页30在算法中赌轮选择法可用下面的子过程来模拟:在0,1区间内产生一个均匀分布的随机数r。若rq1,则染色体x1被选中。若qk-1rqk(2kN),则染色体xk被选中。其中的qi称为染色体xi(i=1,2,n)的积积累累概概率率,其计算公式为 第29页/共70页31选择-复制 设从区间0,1中产生4个随机数如下:r1=0.450126,r2=0.110347 r3=0.572496,r4=0.98503 染色体 适应度选择概率积累概率选中次数选中次数s1=01101 169 0.14 0.14 1s2=11000 576 0.49 0.63 2s3=01000 64 0.06 0.69 0s4=10011 361 0.31 1.00 1第30页/共70页32于是，经复制得群体：s1=11000（24）,s2=01101（13）s3=11000（24）,s4=10011（19）第31页/共70页33交叉 设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。设s1与s2配对，s3与s4配对。分别交换后两位基因，得新染色体：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）第32页/共70页34变异 设变异率pm=0.001。这样，群体S1中共有 540.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。第33页/共70页35n n 于是，得到第二代种群于是，得到第二代种群S S2 2：n n s s1 1=11001=11001（2525）,s s2 2=01100=01100（1212）n n s s3 3=11011=11011（2727）,s s4 4=10000=10000（1616）第34页/共70页36 第二代种群第二代种群S2中各染色体的情况中各染色体的情况 染色体 适应度选择概率积累概率 估计的估计的选中次数选中次数s1=11001 625 0.36 0.36 1s2=01100 144 0.08 0.44 1s3=11011 729 0.41 0.85 1s4=10000 256 0.15 1.00 1第35页/共70页37 假设这一轮选择-复制操作中，种群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）这一轮仍然不会发生变异。第36页/共70页38于是，得第三代种群S3：s1=11100（28）,s2=01001（9）s3=11000（24）,s4=10011（19）第37页/共70页39 第三代种群第三代种群S3中各染色体的情况中各染色体的情况 染色体 适应度选择概率积累概率 估计的估计的选中次数选中次数s1=11100 784 0.44 0.44 2s2=01001 81 0.04 0.48 0s3=11000 576 0.32 0.80 1s4=10011 361 0.20 1.00 1第38页/共70页40 设这一轮的选择-复制结果为：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）这一轮仍然不会发生变异。第39页/共70页41 于是，得第四代种群S4：s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（16）第40页/共70页42 显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。第41页/共70页43YYy=x2 8 13 19 24 X第一代种群及其适应度y=x2 12 16 25 27 XY第二代种群及其适应度y=x2 9 19 24 28 XY第三代种群及其适应度y=x2 16 24 28 31 X第四代种群及其适应度第42页/共70页44遗传算法的描述遗传算法的描述遗传算法的描述遗传算法的描述n nStep1Step1 选择问题的一个编码；给出一个有选择问题的一个编码；给出一个有N N个染色体的初始群体个染色体的初始群体pop(1),t:=1;pop(1),t:=1;n nStep2Step2 对群体对群体pop(t)pop(t)中的每一个染色体中的每一个染色体poppopi i(t)(t)计算它的适应函数计算它的适应函数 f fi i=fitness(pop=fitness(popi i(t);(t);n nStep3Step3 若停止规则满足，则算法停止；否则，计算概率若停止规则满足，则算法停止；否则，计算概率n n P Pi i=f=fi i/f/fi i,i=1,2,N,i=1,2,Nn n并以概率从并以概率从pop(t)pop(t)中随机选一些染色体构成一个新的种群中随机选一些染色体构成一个新的种群n nNewpop(t+1)=pop(t)|j=1,2,N;Newpop(t+1)=pop(t)|j=1,2,N;n nStep4Step4 通过交配，交配概率为通过交配，交配概率为p pc c，得到一个有，得到一个有N N个染色体的个染色体的crosspop(t+1);crosspop(t+1);n nStep5Step5 以较小概率以较小概率p pm m，使得一个染色体的基因发生变异，形成，使得一个染色体的基因发生变异，形成mutpop(t+1);t:=t+1mutpop(t+1);t:=t+1,一个新的体群一个新的体群pop(t)=mutpop(t);pop(t)=mutpop(t);返回返回step2.step2.第43页/共70页453 3 3 3、遗传算法的特点、遗传算法的特点、遗传算法的特点、遗传算法的特点 n n（1 1）群体搜索，易于并行化处理；）群体搜索，易于并行化处理；n n（2 2）不是盲目穷举，而是启发式搜索；）不是盲目穷举，而是启发式搜索；n n（3 3）适应度函数不受连续、可微等条件的约束，适用范）适应度函数不受连续、可微等条件的约束，适用范围很广。围很广。第44页/共70页46二二、理论基础、理论基础n n1 1、遗传算法的数学基础、遗传算法的数学基础 n n2 2、遗传算法的收敛性分析、遗传算法的收敛性分析 n n3 3、遗传算法的改进、遗传算法的改进 第45页/共70页471 1 1 1、遗传算法的数学基础、遗传算法的数学基础、遗传算法的数学基础、遗传算法的数学基础n n（1 1）模式定理）模式定理 n n（2 2）积木块假设）积木块假设 模式是指种群个体基因串中的相似样板，它用来描述基因串中某些特征位相同的结构。在二进制编码中，模式是基于三个字符集(0,1,*)的字符串，符号*代表任意字符，即 0 或者 1。模式示例：10*1模式模式第46页/共70页48两个定义两个定义两个定义两个定义n n定义定义1 1：模式：模式 H H 中中确定位置的个数确定位置的个数称为模式称为模式 H H 的的阶阶，记，记作作O(H)O(H)。例如。例如O(10*1)=3 O(10*1)=3。n n定义定义2 2：模式：模式 H H 中中第一个确定位置和最后一个确定位置第一个确定位置和最后一个确定位置之间的距离之间的距离称为模式称为模式 H H 的定义的定义距距，记作，记作(H)(H)。例如。例如(10*1)=4(10*1)=4。模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。模式的阶和定义距的含义第47页/共70页49模式定理模式定理模式定理模式定理n n 模式定理：具有模式定理：具有低阶、短定义距低阶、短定义距以及以及平均适应度高于平均适应度高于种群平均适应度的模式在子代中种群平均适应度的模式在子代中呈指数增长呈指数增长。n n 模式定理保证了模式定理保证了较优的模式（遗传算法的较优解）的数较优的模式（遗传算法的较优解）的数目呈指数增长目呈指数增长，为解释遗传算法机理提供了数学基础。，为解释遗传算法机理提供了数学基础。从模式定理可看出，有高平均适应度、短定义距、低阶的模式，在连续的后代里获得至少以指数增长的串数目，这主要是因为选择使最好的模式有更多的复制，交叉算子不容易破坏高频率出现的、短定义距的模式，而一般突变概率又相当小，因而它对这些重要的模式几乎没有影响。第48页/共70页50积木块假设积木块假设积木块假设积木块假设 n n 积木块假设：遗传算法通过短定义距、低阶以及高平均积木块假设：遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），在遗传操作下相互结合，最终接适应度的模式（积木块），在遗传操作下相互结合，最终接近全局最优解。近全局最优解。n n 模式定理保证了较优模式的样本数呈指数增长，从而使模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在；而积木块假设则指遗传算法找到全局最优解的可能性存在；而积木块假设则指出了在遗传算子的作用下，能生成全局最优解。出了在遗传算子的作用下，能生成全局最优解。定理 若参数满足：变异概率0pm1,交配概率0pc 1,则简单遗传算法不收敛于全局最优解。第49页/共70页512 2 2 2、遗传算法的收敛性分析、遗传算法的收敛性分析、遗传算法的收敛性分析、遗传算法的收敛性分析n n 遗传算法要实现全局收敛，首先要求任意初始种群经遗传算法要实现全局收敛，首先要求任意初始种群经有有限步都限步都能到达全局最优解，其次算法必须由保优操作来能到达全局最优解，其次算法必须由保优操作来防止防止最优解的遗失最优解的遗失。与算法收敛性有关的因素主要包括种群规模、。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率。选择操作、交叉概率和变异概率。定理 如果改进简单遗传算法按交配、变异、种群选取之后更新当前最优染色体的进化循环过程，则收敛于全局最优解。改进遗传算法：进化的每一代中，记录前面各代最优解并存放在群体的第一位，这个染色体不参与遗传运算。第50页/共70页52种群规模对收敛性的影响种群规模对收敛性的影响种群规模对收敛性的影响种群规模对收敛性的影响n n 通常，种群太小则不能提供足够的采样点，以致算法通常，种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，尽管可以增加优化信息，阻止早熟收性能很差；种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。为收敛速度缓慢。选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率1收敛于全局最优解。选择操作对收敛性的影响第51页/共70页53交叉概率对收敛性的影响交叉概率对收敛性的影响交叉概率对收敛性的影响交叉概率对收敛性的影响n n 交叉操作用于个体对，产生新的个体，实质上是在解空交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很快，间中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，交叉操会造成高适应度值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。作很少进行，从而会使搜索停滞不前，造成算法的不收敛。变异概率对收敛性的影响 变异操作是对种群模式的扰动，有利于增加种群的多样性。但是，变异概率太小则很难产生新模式，变异概率太大则会使遗传算法成为随机搜索算法。第52页/共70页54遗传算法的本质遗传算法的本质遗传算法的本质遗传算法的本质 n n 遗传算法本质上是对染色体模式所进行的一系列运遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。通过这些遗传操作，模式逐步向较好的方向进化，式突变。通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的最优解。最终得到问题的最优解。第53页/共70页55GAGAGAGA的局限性的局限性的局限性的局限性n n 在于在于 GAGA在进化搜索过程中，在进化搜索过程中，每代总要维持一定规模的群体，每代总要维持一定规模的群体，若若群体规模太小，含有的信息量也少群体规模太小，含有的信息量也少，不能使算法得到充分发挥，不能使算法得到充分发挥，若若群体规模大，包含的信息量也大群体规模大，包含的信息量也大，但计算次数会激剧增加，因，但计算次数会激剧增加，因而限制了算法的使用。而限制了算法的使用。n n GAGA的另一个不足之处是的另一个不足之处是“早熟早熟”。造成这种成熟前收敛的。造成这种成熟前收敛的原因，一方面是原因，一方面是 GAGA中最重要的遗传算子中最重要的遗传算子交叉算子使群体中交叉算子使群体中的染色体具有的染色体具有局部相似性局部相似性，父代染色体的，父代染色体的信息交换量小信息交换量小，从而使，从而使搜索停滞不前；另一方面是搜索停滞不前；另一方面是变异概率又太小变异概率又太小，以至于不能使搜索，以至于不能使搜索转向其它的解空间进行搜索。转向其它的解空间进行搜索。n n GAGA的爬山能力差，也是由于变异概率低造成的。的爬山能力差，也是由于变异概率低造成的。第54页/共70页563 3 3 3、遗传算法的改进、遗传算法的改进、遗传算法的改进、遗传算法的改进n n 遗传欺骗问题：在遗传算法进化过程中，有时会产生遗传欺骗问题：在遗传算法进化过程中，有时会产生一些超常的个体，这些个体因竞争力太突出而控制了选择运一些超常的个体，这些个体因竞争力太突出而控制了选择运算过程，从而影响算法的全局优化性能，导致算法获得某个算过程，从而影响算法的全局优化性能，导致算法获得某个局部最优解。局部最优解。第55页/共70页57遗传算法的改进途径遗传算法的改进途径遗传算法的改进途径遗传算法的改进途径n n（1 1）对编码方式的改进）对编码方式的改进 n n（2 2）对遗传算子的改进）对遗传算子的改进n n（3 3）对控制参数的改进）对控制参数的改进 n n（4 4）对执行策略的改进）对执行策略的改进 第56页/共70页58对编码方式的改进对编码方式的改进对编码方式的改进对编码方式的改进n n 二二进进制制编编码码优优点点在在于于编编码码、解解码码操操作作简简单单，交交叉叉、变变异异等等操操作作便便于于实实现现，缺缺点点在在于于精精度度要要求求较较高高时时，个个体体编编码码串串较较长长，使使算算法法的的搜搜索索空空间间急急剧剧扩扩大大，遗遗传传算算法法的的性性能能降降低低。格格雷雷编编码码克克服服了了二二进进制制编编码码的的不不连连续续问问题题，浮浮点点数数编编码码改改善善了遗传算法的计算复杂性了遗传算法的计算复杂性 。第57页/共70页59TSPTSPTSPTSP问题的基本遗传算法问题的基本遗传算法问题的基本遗传算法问题的基本遗传算法n n(1)(1)编码编码n n 自然数编码，自然数编码，i i1 1i i2 2i i3 3iin nn n(2)(2)适应度函数适应度函数n n f fi i ：巡回路长度的倒数：巡回路长度的倒数n n(3)(3)选择操作选择操作n n 繁殖池；繁殖池；赌轮选择赌轮选择 n n(4)(4)杂交算子杂交算子n n 例，基于位置的杂交例，基于位置的杂交n n 父代父代1 1：1 2 3 4 5 6 7 8 9 101 2 3 4 5 6 7 8 9 10n n 父代父代2 2：5 9 2 4 6 1 10 7 3 85 9 2 4 6 1 10 7 3 8n n 所选位置所选位置 *n n 子代子代1 1：1 9 2 3 6 4 5 7 8 101 9 2 3 6 4 5 7 8 10n n 子代子代2 2：9 2 3 4 5 6 1 8 10 7 9 2 3 4 5 6 1 8 10 7 n n(5)(5)变异算子变异算子n n 例，基于位置的变异、基于次序的变异、打乱变异例，基于位置的变异、基于次序的变异、打乱变异第58页/共70页60对遗传算子的改进对遗传算子的改进对遗传算子的改进对遗传算子的改进n n排序选择 n n均匀交叉 n n逆序变异（1 1）对群体中的所有个体按对群体中的所有个体按其适应度大小进行降序排序；其适应度大小进行降序排序；（2 2）根据具体求解问题，设根据具体求解问题，设计一个概率分配表，将各个概计一个概率分配表，将各个概率值按上述排列次序分配给各率值按上述排列次序分配给各个个体；个个体；（3 3）以各个个体所分配到的以各个个体所分配到的概率值作为其遗传到下一代的概率值作为其遗传到下一代的概率，基于这些概率用赌盘选概率，基于这些概率用赌盘选择法来产生下一代群体。择法来产生下一代群体。第59页/共70页61对遗传算子对遗传算子对遗传算子对遗传算子 的改进的改进的改进的改进n n排序选择 n n均匀交叉 n n逆序变异（1 1）随机产生一个与个体随机产生一个与个体编码长度相同的二进制屏蔽编码长度相同的二进制屏蔽字字P=WP=W1 1W W2 2W Wn n ；（2 2）按下列规则从按下列规则从A A、B B两两个父代个体中产生两个新个个父代个体中产生两个新个体体X X、Y Y：若：若W Wi i=0=0，则，则X X的第的第i i个基因继承个基因继承A A的对应基因，的对应基因，Y Y的第的第i i个基因继承个基因继承B B的对应基的对应基因；若因；若W Wi i=1=1，则，则A A、B B的第的第i i个基因相互交换，从而生成个基因相互交换，从而生成X X、Y Y的第的第i i个基因。个基因。第60页/共70页62对遗传算子的改进对遗传算子的改进对遗传算子的改进对遗传算子的改进n n排序选择 n n均匀交叉 n n逆序变异变异前：变异前：3 4 8|7 9 6 5|2 13 4 8|7 9 6 5|2 1变异后：变异后：3 4 8|5 6 9 7|2 13 4 8|5 6 9 7|2 1第61页/共70页63对控制参数的改进对控制参数的改进对控制参数的改进对控制参数的改进n n Schaffer Schaffer建议的最优参数范围是：建议的最优参数范围是：n n M=20-100M=20-100，n n T=100-500T=100-500，n n P Pc c=0.4-0.9=0.4-0.9，n n P Pm m=0.001-0.01=0.001-0.01。n n 第62页/共70页64对控制参数的改进对控制参数的改进对控制参数的改进对控制参数的改进n n SrinvivasSrinvivas等人提出自适应遗传算法，即等人提出自适应遗传算法，即P PC C和和P Pm m能够随能够随适应度自动改变，当种群的各个个体适应度自动改变，当种群的各个个体适应度趋于一致或趋于适应度趋于一致或趋于局部最优时，使二者增加，而当种群适应度比较分散时，使局部最优时，使二者增加，而当种群适应度比较分散时，使二者减小二者减小，同时对适应值高于群体平均适应值的个体，采用，同时对适应值高于群体平均适应值的个体，采用较低的较低的P PC C和和P Pm m，使性能优良的个体进入下一代，而低于平均，使性能优良的个体进入下一代，而低于平均适应值的个体，采用较高的适应值的个体，采用较高的P PC C和和P Pm m，使性能较差的个体被淘，使性能较差的个体被淘汰汰 。第63页/共70页651 1 1 1、遗传算法的应用领域、遗传算法的应用领域、遗传算法的应用领域、遗传算法的应用领域n n（1 1）组合优化）组合优化 （2 2）函数优化）函数优化 n n（3 3）自动控制）自动控制 （4 4）生产调度）生产调度 n n（5 5）图像处理）图像处理 （6 6）机器学习）机器学习 n n（7 7）人工生命）人工生命 （8 8）数据挖掘）数据挖掘 第64页/共70页66遗传算法应用于组合优化遗传算法应用于组合优化遗传算法应用于组合优化遗传算法应用于组合优化n n 随着问题规模的增大，组合优化问题的搜索空间也急随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在计算机上用枚举法很难甚至不可能求出其剧扩大，有时在计算机上用枚举法很难甚至不可能求出其最优解。实践证明，遗传算法已经在求解旅行商问题、背最优解。实践证明，遗传算法已经在求解旅行商问题、背包问题、装箱问题、布局优化、网络路由等具有包问题、装箱问题、布局优化、网络路由等具有NPNP难度的难度的组合优化问题上取得了成功的应用。组合优化问题上取得了成功的应用。第65页/共70页三、实现技术三、实现技术n n1.1.群体的规模群体的规模群体的规模群体的规模n n 群体规模群体规模取个体编码长度的线性倍数取个体编码长度的线性倍数是实际应用经常采是实际应用经常采用的方法；用的方法；n n 当多个进化代没有改变解的性能可以扩大群体的数量；当多个进化代没有改变解的性能可以扩大群体的数量；反之，可以减少群体的数量。反之，可以减少群体的数量。n n2.2.初始群体的选取初始群体的选取初始群体的选取初始群体的选取n n 随机选取随机选取n n 采用启发式算法或经验选择一些优良的种子采用启发式算法或经验选择一些优良的种子n n “没有免费的午餐没有免费的午餐”67第66页/共70页三、实现技术三、实现技术n n3.3.终止规则终止规则终止规则终止规则n n 1)1)给定最大的遗传代数；给定最大的遗传代数；n n 2)2)与目标值的差距与目标值的差距n n 3)3)自适应：当若干代