GA-遗传算法简介概述课件.ppt

《GA-遗传算法简介概述课件.ppt》由会员分享，可在线阅读，更多相关《GA-遗传算法简介概述课件.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、主要内容主要内容一、遗传算法概述一、遗传算法概述一、遗传算法概述一、遗传算法概述二、遗传算法的基本操作二、遗传算法的基本操作二、遗传算法的基本操作二、遗传算法的基本操作 三、遗传算法原理三、遗传算法原理三、遗传算法原理三、遗传算法原理四、遗传算法的应用四、遗传算法的应用四、遗传算法的应用四、遗传算法的应用现代智能优化算法遗传算法禁忌算法蚁群算法粒子群算法细菌算法混沌算法TSGAACOPSOBCCOA自由搜索算法FS1 1、遗传算法起源、遗传算法起源 遗传算法遗传算法遗传算法遗传算法(Genetic AlgorithmGenetic AlgorithmGenetic AlgorithmGenet

2、ic Algorithm,GA),GA),GA),GA)是由美国的是由美国的是由美国的是由美国的J.J.J.J.HollandHollandHollandHolland教授于教授于教授于教授于1975197519751975年在他的专著年在他的专著年在他的专著年在他的专著自然界和人工系统的自然界和人工系统的自然界和人工系统的自然界和人工系统的适应性适应性适应性适应性中首先提出的，它中首先提出的，它中首先提出的，它中首先提出的，它是一类借鉴生物界自然选择和是一类借鉴生物界自然选择和是一类借鉴生物界自然选择和是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。自然遗传机制的随机化搜索算法。自然

3、遗传机制的随机化搜索算法。自然遗传机制的随机化搜索算法。GAGAGAGA来源于达尔文的来源于达尔文的来源于达尔文的来源于达尔文的进化进化进化进化论论论论、魏茨曼的、魏茨曼的、魏茨曼的、魏茨曼的物种选择物种选择物种选择物种选择学说和孟德尔的学说和孟德尔的学说和孟德尔的学说和孟德尔的群体遗传群体遗传群体遗传群体遗传学说。其学说。其学说。其学说。其基本思想是模拟自然界遗传机制和生物进化论而形成的一基本思想是模拟自然界遗传机制和生物进化论而形成的一基本思想是模拟自然界遗传机制和生物进化论而形成的一基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程种过程种过程种过程搜索全局最优解搜索全局最优解搜索

4、全局最优解搜索全局最优解的算法。的算法。的算法。的算法。一、遗传算法概述一、遗传算法概述2 2、生物进化理论和遗传学基本知识、生物进化理论和遗传学基本知识 一、遗传算法概述一、遗传算法概述(1)(1)(1)(1)达尔文的自然选择说达尔文的自然选择说达尔文的自然选择说达尔文的自然选择说遗传（遗传（遗传（遗传（heredityheredityheredityheredity）：）：）：）：子代和父代具有相同或相似的性状，保证物种的稳定性子代和父代具有相同或相似的性状，保证物种的稳定性子代和父代具有相同或相似的性状，保证物种的稳定性子代和父代具有相同或相似的性状，保证物种的稳定性变异（变异（变异（变

5、异（variationvariationvariationvariation）：）：）：）：子代与父代子代与父代子代与父代子代与父代,子代不同个体之间总有差异，是生命多样性的根源子代不同个体之间总有差异，是生命多样性的根源子代不同个体之间总有差异，是生命多样性的根源子代不同个体之间总有差异，是生命多样性的根源生存斗争和适者生存：生存斗争和适者生存：生存斗争和适者生存：生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰具有适应性变异的个体被保留，不具适应性变异的个体被淘汰具有适应性变异的个体被保留，不具适应性变异的个体被淘汰具有适应性变异的个体被保留，不具适应性变异的个体

6、被淘汰一、遗传算法概述一、遗传算法概述2 2、生物进化理论和遗传学基本知识、生物进化理论和遗传学基本知识(2)(2)(2)(2)遗传学基本概念和术语遗传学基本概念和术语遗传学基本概念和术语遗传学基本概念和术语基因基因基因基因(gene)(gene)(gene)(gene)：染色体的一个片段染色体的一个片段染色体的一个片段染色体的一个片段染色体染色体染色体染色体(Chromosome)(Chromosome)(Chromosome)(Chromosome)：问题中个体的某种字符串形式的编码表示问题中个体的某种字符串形式的编码表示问题中个体的某种字符串形式的编码表示问题中个体的某种字符串形式的编码

7、表示种群种群种群种群(Population)(Population)(Population)(Population)：个体的集合个体的集合个体的集合个体的集合,该集合内的个体数称为种群的大小该集合内的个体数称为种群的大小该集合内的个体数称为种群的大小该集合内的个体数称为种群的大小基因型基因型基因型基因型(genetypegenetypegenetypegenetype)：基因组合的模型，染色体的内部表现基因组合的模型，染色体的内部表现基因组合的模型，染色体的内部表现基因组合的模型，染色体的内部表现表现型表现型表现型表现型(phenotype)(phenotype)(phenotype)(phe

8、notype)：染色体决定性状的外部表现染色体决定性状的外部表现染色体决定性状的外部表现染色体决定性状的外部表现1 1 11 1 11 1 11 1 1 1 1 1 1 1 1 11 1 11 1 11 1 1 1 1 11 1 11 1 11 1 1 0 0 0 0 1 1 11 1 11 1 11 1 1个体个体 染色体染色体 9 -10019 -1001一、遗传算法概述一、遗传算法概述2 2、生物进化理论和遗传学基本知识、生物进化理论和遗传学基本知识(2)(2)(2)(2)遗传学基本概念和术语遗传学基本概念和术语遗传学基本概念和术语遗传学基本概念和术语进化进化进化进化(evolution

9、)(evolution)(evolution)(evolution)：个体逐渐适应生存环境，不断改良品质的过程个体逐渐适应生存环境，不断改良品质的过程个体逐渐适应生存环境，不断改良品质的过程个体逐渐适应生存环境，不断改良品质的过程适应度适应度适应度适应度(fitness)(fitness)(fitness)(fitness)：反映个体性能的一个数量值反映个体性能的一个数量值反映个体性能的一个数量值反映个体性能的一个数量值编码编码编码编码(coding)(coding)(coding)(coding)：从表现型到基因型的映射从表现型到基因型的映射从表现型到基因型的映射从表现型到基因型的映射解码解

10、码解码解码(decoding)(decoding)(decoding)(decoding)：从基因型到表现性的映射从基因型到表现性的映射从基因型到表现性的映射从基因型到表现性的映射适应度函数适应度函数适应度函数适应度函数(fitness function):(fitness function):(fitness function):(fitness function):问题中的全体个体与其适应度之间的一个对应关系问题中的全体个体与其适应度之间的一个对应关系问题中的全体个体与其适应度之间的一个对应关系问题中的全体个体与其适应度之间的一个对应关系,一般是一一般是一一般是一一般是一个实值函数。该函数

11、就是遗传算法中指导搜索的评价函数。个实值函数。该函数就是遗传算法中指导搜索的评价函数。个实值函数。该函数就是遗传算法中指导搜索的评价函数。个实值函数。该函数就是遗传算法中指导搜索的评价函数。1 1 选择选择-复制复制(selection-reproduction)(selection-reproduction)二、遗传算法的基本操作二、遗传算法的基本操作 选择选择选择选择-复制指的就是以一定的概率从种群中选择若干个体并进行复制指的就是以一定的概率从种群中选择若干个体并进行复制指的就是以一定的概率从种群中选择若干个体并进行复制指的就是以一定的概率从种群中选择若干个体并进行复制的操作复制的操作复制

12、的操作复制的操作uu 轮盘赌选择（轮盘赌选择（轮盘赌选择（轮盘赌选择（roulette wheel selectionroulette wheel selectionroulette wheel selectionroulette wheel selection）uu 随机遍历抽样（随机遍历抽样（随机遍历抽样（随机遍历抽样（stochastic universal selectionstochastic universal selectionstochastic universal selectionstochastic universal selection）uu 局部选择（局部选择（局部选

13、择（局部选择（local selectionlocal selectionlocal selectionlocal selection）uu 截断选择（截断选择（截断选择（截断选择（truncation selectiontruncation selectiontruncation selectiontruncation selection）uu 锦标赛选择（锦标赛选择（锦标赛选择（锦标赛选择（tournament selectiontournament selectiontournament selectiontournament selection）选择概率选择概率选择概率选择概率P(xP

14、(xP(xP(xi i i i)的计算公式为的计算公式为的计算公式为的计算公式为:常用选择常用选择常用选择常用选择-复制方法：复制方法：复制方法：复制方法：按比例的适应按比例的适应按比例的适应按比例的适应度分配方法度分配方法度分配方法度分配方法1 1 选择选择-复制复制(selection-reproduction)(selection-reproduction)二、遗传算法的基本操作二、遗传算法的基本操作例：轮盘赌选择例：轮盘赌选择 解解 (1)(1)计算选择概率和累计概率计算选择概率和累计概率 个体个体染色体染色体适应度适应度选择概率选择概率累计概率累计概率1000110000080.08

15、69570.0869572010111100150.0543480.1413043000000010120.0217390.16304341001110100100.1086960.2717395101010101070.0760870.34782661110010110120.1304350.4782617100101101150.0543480.53260981100000001190.2065220.73913091001110100100.1086960.847826100001010011140.1521741.0000001 1 选择选择-复制复制(selection-reprod

16、uction)(selection-reproduction)二、遗传算法的基本操作二、遗传算法的基本操作个体个体染色体染色体适应度适应度选择概率选择概率累计概率累计概率1000110000080.0869570.0869572010111100150.0543480.1413043000000010120.0217390.16304341001110100100.1086960.2717395101010101070.0760870.34782661110010110120.1304350.4782617100101101150.0543480.53260981100000001190.20

17、65220.73913091001110100100.1086960.847826100001010011140.1521741.000000复制操作能从旧种群中选择出优秀者，但不能创造新的染色体！复制操作能从旧种群中选择出优秀者，但不能创造新的染色体！复制操作能从旧种群中选择出优秀者，但不能创造新的染色体！复制操作能从旧种群中选择出优秀者，但不能创造新的染色体！(2)(2)在在0-10-1之间产生一个随机数之间产生一个随机数 0.507893 60.507893 60.070221 10.070221 10.545929 80.545929 80.784567 90.784567 90.44

18、6930 60.446930 60.291198 50.291198 50.716340 80.716340 80.271901 4 0.271901 4 0.371435 60.371435 60.854641 100.854641 10淘淘汰汰2 2 交叉交叉(crossover)(crossover)基因重组基因重组二、遗传算法的基本操作二、遗传算法的基本操作交叉就是互换两个染色体某些位上的基因交叉就是互换两个染色体某些位上的基因交叉就是互换两个染色体某些位上的基因交叉就是互换两个染色体某些位上的基因 s s s s1 1 1 1=01000101,=01000101,=01000101

19、,=01000101,s s s s2 2 2 2=10011011=10011011=10011011=10011011 可以看做是原染色体可以看做是原染色体可以看做是原染色体可以看做是原染色体s s s s1 1 1 1和和和和s s s s2 2 2 2的子代染色体的子代染色体的子代染色体的子代染色体 例：设染色体例：设染色体例：设染色体例：设染色体s s s s1 1 1 1=01001011,s=01001011,s=01001011,s=01001011,s2 2 2 2=10010101,=10010101,=10010101,=10010101,交换其后交换其后交换其后交换其后

20、4 4 4 4位基因位基因位基因位基因,即即即即单点交叉单点交叉单点交叉单点交叉2 2 交叉交叉(crossover)(crossover)基因重组基因重组二、遗传算法的基本操作二、遗传算法的基本操作其它常用的交叉方法：其它常用的交叉方法：其它常用的交叉方法：其它常用的交叉方法：uu 多点交叉（多点交叉（多点交叉（多点交叉（multiple-point crossovermultiple-point crossovermultiple-point crossovermultiple-point crossover）uu 均匀交叉（均匀交叉（均匀交叉（均匀交叉（uniform crossover

21、uniform crossoveruniform crossoveruniform crossover）uu 部分匹配交叉（部分匹配交叉（部分匹配交叉（部分匹配交叉（Partially Matched CrossoverPartially Matched CrossoverPartially Matched CrossoverPartially Matched Crossover）uu 顺序交叉（顺序交叉（顺序交叉（顺序交叉（Ordered CrossoverOrdered CrossoverOrdered CrossoverOrdered Crossover）uu 循环交叉（循环交叉（循环交

22、叉（循环交叉（Cycle CrossoverCycle CrossoverCycle CrossoverCycle Crossover）交叉模拟了生物进化过程中的繁殖现象，通过两个染色体的交换组交叉模拟了生物进化过程中的繁殖现象，通过两个染色体的交换组交叉模拟了生物进化过程中的繁殖现象，通过两个染色体的交换组交叉模拟了生物进化过程中的繁殖现象，通过两个染色体的交换组合，来产生新的优良品种！合，来产生新的优良品种！合，来产生新的优良品种！合，来产生新的优良品种！3 3 变异变异(mutation)(mutation)变异就是改变染色体某个变异就是改变染色体某个变异就是改变染色体某个变异就是改变染

23、色体某个(些些些些)位上的基因位上的基因位上的基因位上的基因例如，设染色体例如，设染色体例如，设染色体例如，设染色体s s s s=11001101=11001101=11001101=11001101，将其第三位上的，将其第三位上的，将其第三位上的，将其第三位上的0 0 0 0变为变为变为变为1,1,1,1,即即即即 s s s s=11=11=11=110 0 0 001101 01101 01101 01101 111111111 1 1 101101=01101=01101=01101=s s s s。s s s s也可以看做是原染色体也可以看做是原染色体也可以看做是原染色体也可以看做

24、是原染色体s s s s的子代染色体的子代染色体的子代染色体的子代染色体 变异运算用来模拟生物在自然的遗传环境中由于变异运算用来模拟生物在自然的遗传环境中由于变异运算用来模拟生物在自然的遗传环境中由于变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素各种偶然因素各种偶然因素各种偶然因素引引引引起的基因突变起的基因突变起的基因突变起的基因突变.若只有选择和交叉，而没有变异，则无法在初始基因若只有选择和交叉，而没有变异，则无法在初始基因若只有选择和交叉，而没有变异，则无法在初始基因若只有选择和交叉，而没有变异，则无法在初始基因组合以外的空间进行搜索，使进化过程在早期就陷入局部解而进入终组合以外

25、的空间进行搜索，使进化过程在早期就陷入局部解而进入终组合以外的空间进行搜索，使进化过程在早期就陷入局部解而进入终组合以外的空间进行搜索，使进化过程在早期就陷入局部解而进入终止过程，从而影响解的质量止过程，从而影响解的质量止过程，从而影响解的质量止过程，从而影响解的质量!二、遗传算法的基本操作二、遗传算法的基本操作三、遗传算法的原理三、遗传算法的原理标准遗传算法流程框图标准遗传算法流程框图标准遗传算法流程框图标准遗传算法流程框图遗传算子遗传算子适者生存适者生存种群繁殖种群繁殖关键关键三、遗传算法的原理三、遗传算法的原理算法中的一些控制参数：算法中的一些控制参数：算法中的一些控制参数：算法中的一些

26、控制参数：种群规模：种群规模：种群规模：种群规模：最大换代数：最大换代数：最大换代数：最大换代数：交叉率交叉率交叉率交叉率(crossover rate)(crossover rate)(crossover rate)(crossover rate)：参加交叉运算的染色体个数占全体染色体总数的比例，记为参加交叉运算的染色体个数占全体染色体总数的比例，记为参加交叉运算的染色体个数占全体染色体总数的比例，记为参加交叉运算的染色体个数占全体染色体总数的比例，记为P P P Pc c c c 取值范围一般为取值范围一般为取值范围一般为取值范围一般为0.40.40.40.40.990.990.990.9

27、9 变异率变异率变异率变异率(mutation rate)(mutation rate)(mutation rate)(mutation rate)：发生变异的发生变异的发生变异的发生变异的基因位数所占全体染色体的基因总位数基因位数所占全体染色体的基因总位数基因位数所占全体染色体的基因总位数基因位数所占全体染色体的基因总位数的比例，记为的比例，记为的比例，记为的比例，记为P P P Pm m m m 取值范围一般为取值范围一般为取值范围一般为取值范围一般为0.00010.00010.00010.00010.10.10.10.1三、遗传算法的原理三、遗传算法的原理标准遗传算法标准遗传算法标准遗传

28、算法标准遗传算法(Standard genetic algorithm,SGA)(Standard genetic algorithm,SGA)(Standard genetic algorithm,SGA)(Standard genetic algorithm,SGA)Step1Step1Step1Step1 在搜索空间在搜索空间在搜索空间在搜索空间U U U U上定义一个适应度函上定义一个适应度函上定义一个适应度函上定义一个适应度函数数数数f(xf(xf(xf(x)，给定种群规模，给定种群规模，给定种群规模，给定种群规模N N N N，交叉率，交叉率，交叉率，交叉率PcPcPcPc和变异和

29、变异和变异和变异率率率率PmPmPmPm，代数，代数，代数，代数T T T T；Step2 Step2 Step2 Step2 随机产生随机产生随机产生随机产生U U U U中的中的中的中的N N N N个个体个个体个个体个个体s s s s1 1 1 1,s s s s2 2 2 2,s s s sN N N N，组成初始种群，组成初始种群，组成初始种群，组成初始种群S S S S=s s s s1 1 1 1,s s s s2 2 2 2,s s s sN N N N ，置代，置代，置代，置代数计数器数计数器数计数器数计数器t t t t=1=1=1=1；Step3 Step3 Step3

30、 Step3 计算计算计算计算S S S S中每个个体的适应度中每个个体的适应度中每个个体的适应度中每个个体的适应度f(xf(xf(xf(x)；Step4 Step4 Step4 Step4 若终止条件满足，则取若终止条件满足，则取若终止条件满足，则取若终止条件满足，则取S S S S中适应度最大的个体作为所求结果，算法中适应度最大的个体作为所求结果，算法中适应度最大的个体作为所求结果，算法中适应度最大的个体作为所求结果，算法结束。否则，转结束。否则，转结束。否则，转结束。否则，转Step5Step5Step5Step5；Step5Step5Step5Step5 按选择概率按选择概率按选择概率

31、按选择概率P(xP(xP(xP(xi i i i)所决定的选中机会，所决定的选中机会，所决定的选中机会，所决定的选中机会，每次从每次从每次从每次从S S S S中随机选定中随机选定中随机选定中随机选定1 1 1 1个个体并将其复制，共个个体并将其复制，共个个体并将其复制，共个个体并将其复制，共做做做做N N N N次，然后将复制所得的次，然后将复制所得的次，然后将复制所得的次，然后将复制所得的N N N N个染色体组成群个染色体组成群个染色体组成群个染色体组成群体体体体S S S S1 1 1 1；Step6Step6Step6Step6 按交叉率按交叉率按交叉率按交叉率PcPcPcPc所决定

32、的参加交叉的染所决定的参加交叉的染所决定的参加交叉的染所决定的参加交叉的染色体数色体数色体数色体数c c c c，从，从，从，从S S S S1 1 1 1中随机确定中随机确定中随机确定中随机确定c c c c个染色体，配对个染色体，配对个染色体，配对个染色体，配对进行交叉操作，并用产生的新染色体代替原进行交叉操作，并用产生的新染色体代替原进行交叉操作，并用产生的新染色体代替原进行交叉操作，并用产生的新染色体代替原染色体，得群体染色体，得群体染色体，得群体染色体，得群体S S S S2 2 2 2；Step7 Step7 Step7 Step7 按变异率按变异率按变异率按变异率PmPmPmPm

33、所决定的变异次数所决定的变异次数所决定的变异次数所决定的变异次数m m m m，从，从，从，从S S S S2 2 2 2中随机确定中随机确定中随机确定中随机确定m m m m个染色体，分别个染色体，分别个染色体，分别个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体进行变异操作，并用产生的新染色体代替原染色体，得群体进行变异操作，并用产生的新染色体代替原染色体，得群体进行变异操作，并用产生的新染色体代替原染色体，得群体S S S S3 3 3 3；Step8Step8Step8Step8 将群体将群体将群体将群体S S S S3 3 3 3作为新一代种群，即用作为新一代种群，

34、即用作为新一代种群，即用作为新一代种群，即用S S S S3 3 3 3代替代替代替代替S S S S，t=t+1t=t+1t=t+1t=t+1，转步，转步，转步，转步Step3Step3Step3Step3；三、遗传算法的原理三、遗传算法的原理标准遗传算法标准遗传算法标准遗传算法标准遗传算法(Standard genetic algorithm,SGA)(Standard genetic algorithm,SGA)(Standard genetic algorithm,SGA)(Standard genetic algorithm,SGA)四、遗传算法的应用四、遗传算法的应用1 1、遗传算

35、法的应用领域、遗传算法的应用领域（1 1 1 1）组合优化）组合优化）组合优化）组合优化 （2 2 2 2）函数优化）函数优化）函数优化）函数优化 （3 3 3 3）自动控制）自动控制）自动控制）自动控制 （4 4 4 4）生产调度）生产调度）生产调度）生产调度 （5 5 5 5）图像处理）图像处理）图像处理）图像处理 （6 6 6 6）机器学习）机器学习）机器学习）机器学习 （7 7 7 7）人工生命）人工生命）人工生命）人工生命 （8 8 8 8）数据挖掘）数据挖掘）数据挖掘）数据挖掘2 2、遗传算法的应用举例、遗传算法的应用举例四、遗传算法的应用四、遗传算法的应用例：例：求下列一元函数的

36、最大值求下列一元函数的最大值：x-1,2x-1,2x-1,2x-1,2，求解结果精确到，求解结果精确到，求解结果精确到，求解结果精确到6 6 6 6位小数。位小数。位小数。位小数。四、遗传算法的应用四、遗传算法的应用用微分法求解：用微分法求解：用微分法求解：用微分法求解：即：即：即：即：解有无解有无解有无解有无穷穷穷穷多个多个多个多个 (i=1,2,及及i=-1,-2,i=-1,-2,)是一个接近于是一个接近于0 0的实数递减序的实数递减序列列当当当当i i i i为奇数时为奇数时为奇数时为奇数时x x x xi i对应局部极大值点，对应局部极大值点，对应局部极大值点，对应局部极大值点，i i

37、 i i为偶数时为偶数时为偶数时为偶数时x x x xi i对应局部极小值对应局部极小值对应局部极小值对应局部极小值 x x1919即为区间即为区间即为区间即为区间-1,2-1,2-1,2-1,2内的最大值点内的最大值点内的最大值点内的最大值点此时，函数最大值此时，函数最大值此时，函数最大值此时，函数最大值f(xf(xf(xf(x1919）比）比）比）比f(1.85)=3.85f(1.85)=3.85f(1.85)=3.85f(1.85)=3.85稍大稍大稍大稍大四、遗传算法的应用四、遗传算法的应用用遗传算法求解：用遗传算法求解：分析：分析：由于区间长度为由于区间长度为3 3，求解结果精确到，

38、求解结果精确到6 6位小数，因此可将自变量位小数，因此可将自变量定义区间划分为定义区间划分为3 310106 6等份。又因为等份。又因为2 22121 3 310106 6 2 22222 ，所以本例的，所以本例的二进制编码长度至少需要二进制编码长度至少需要2222位，编码过程实质上是将区间位，编码过程实质上是将区间-1-1，22内对内对应的实数值转化为一个二进制串（应的实数值转化为一个二进制串（b b2121b b2020b b0 0）。）。求解过程：求解过程：(1)(1)编码编码表现型：表现型：x x基因型：基因型：二进制编码，串长二进制编码，串长2222位位几个术语几个术语 基因型：基因

39、型：1000101110110101000111 表现型：表现型：0.637197 编码解码个体（染色体）基因四、遗传算法的应用四、遗传算法的应用(2)(2)(2)(2)生成初始种群生成初始种群生成初始种群生成初始种群用遗传算法求解：用遗传算法求解：用遗传算法求解：用遗传算法求解：方式：随机生成长度为方式：随机生成长度为方式：随机生成长度为方式：随机生成长度为22222222的二进制制串的二进制制串的二进制制串的二进制制串数量：种群的大小数量：种群的大小数量：种群的大小数量：种群的大小(规模规模规模规模)，如，如，如，如30303030，50505050，1111010011100001011

40、000 1111010011100001011000 1111010011100001011000 1111010011100001011000 1100110011101010101110 1100110011101010101110 1100110011101010101110 1100110011101010101110 1010100011110010000100 1010100011110010000100 1010100011110010000100 1010100011110010000100 1011110010011100111001 10111100100111001110

41、01 1011110010011100111001 1011110010011100111001 0001100101001100000011 0001100101001100000011 0001100101001100000011 0001100101001100000011 0000011010010000000000 0000011010010000000000 0000011010010000000000 0000011010010000000000 四、遗传算法的应用四、遗传算法的应用(3)(3)(3)(3)计算适应度计算适应度计算适应度计算适应度用遗传算法求解：用遗传算法求解：用

42、遗传算法求解：用遗传算法求解：不同的问题有不同的适应度计算方法，本例直接用目标函数作不同的问题有不同的适应度计算方法，本例直接用目标函数作不同的问题有不同的适应度计算方法，本例直接用目标函数作不同的问题有不同的适应度计算方法，本例直接用目标函数作为适应度函数为适应度函数为适应度函数为适应度函数计算计算计算计算x x x x的函数值的函数值的函数值的函数值(适应度适应度适应度适应度)：将某个个体转化为将某个个体转化为将某个个体转化为将某个个体转化为-1,2-1,2-1,2-1,2区间的实数：区间的实数：区间的实数：区间的实数：s=x=0.637197s=x=0.637197s=x=0.63719

43、7s=x=0.637197(4)(4)(4)(4)遗传操作遗传操作遗传操作遗传操作选择：轮盘赌选择法选择：轮盘赌选择法选择：轮盘赌选择法选择：轮盘赌选择法交叉：单点交叉交叉：单点交叉交叉：单点交叉交叉：单点交叉变异：小概率变异变异：小概率变异变异：小概率变异变异：小概率变异四、遗传算法的应用四、遗传算法的应用用遗传算法求解：用遗传算法求解：用遗传算法求解：用遗传算法求解：(5)(5)(5)(5)模拟结果模拟结果模拟结果模拟结果设置的参数：设置的参数：设置的参数：设置的参数：种群大小种群大小种群大小种群大小50,50,50,50,交叉概率交叉概率交叉概率交叉概率0.750.750.750.75

44、变异概率变异概率变异概率变异概率0.05,0.05,0.05,0.05,最大代数最大代数最大代数最大代数200200200200 得到的最佳个体：得到的最佳个体：得到的最佳个体：得到的最佳个体：smaxsmaxsmaxsmax=xmaxxmaxxmaxxmax=1.8506=1.8506=1.8506=1.8506 f(xf(xf(xf(xmaxmaxmaxmax)=3.8503)=3.8503)=3.8503)=3.8503世代数世代数世代数世代数自变量自变量自变量自变量适应度适应度适应度适应度1 11.44951.44953.44943.44949 91.83951.83953.74123

45、.741217171.85121.85123.84993.849930301.85051.85053.85033.850350501.85061.85063.85033.850380801.85061.85063.85033.85031201201.85061.85063.85033.85032002001.85061.85063.85033.8503遗传算法的本质遗传算法的本质 遗传算法本质上是对染色体模式所进行遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交中的优良模式遗传到下一代种群中，利

46、用交叉算子进行模式重组，利用变异算子进行模叉算子进行模式重组，利用变异算子进行模式突变。通过这些遗传操作，模式逐步向较式突变。通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的最优解。好的方向进化，最终得到问题的最优解。小结小结1 1 1 1、遗传算法优点：、遗传算法优点：、遗传算法优点：、遗传算法优点：搜索过程不直接作用在变量上，而是对参数集进行了编码的个体上搜索过程不直接作用在变量上，而是对参数集进行了编码的个体上搜索过程不直接作用在变量上，而是对参数集进行了编码的个体上搜索过程不直接作用在变量上，而是对参数集进行了编码的个体上 搜索过程是迭代的过程，具有并行性搜索过程是迭代的过程

47、，具有并行性搜索过程是迭代的过程，具有并行性搜索过程是迭代的过程，具有并行性 利用概率转移规则，可在一个不确定的空间上寻优利用概率转移规则，可在一个不确定的空间上寻优利用概率转移规则，可在一个不确定的空间上寻优利用概率转移规则，可在一个不确定的空间上寻优 不是从一点出发沿一条线搜索，而是在整个空间上搜索，从而找到全局最优不是从一点出发沿一条线搜索，而是在整个空间上搜索，从而找到全局最优不是从一点出发沿一条线搜索，而是在整个空间上搜索，从而找到全局最优不是从一点出发沿一条线搜索，而是在整个空间上搜索，从而找到全局最优解解解解 对搜索空间无任何特殊要求对搜索空间无任何特殊要求对搜索空间无任何特殊要

48、求对搜索空间无任何特殊要求(连通，凸性连通，凸性连通，凸性连通，凸性)容错能力强容错能力强容错能力强容错能力强2 2 2 2、遗传算法存在的问题：、遗传算法存在的问题：、遗传算法存在的问题：、遗传算法存在的问题：编码问题：编码选择不当使编码问题：编码选择不当使编码问题：编码选择不当使编码问题：编码选择不当使GAGAGAGA很难收敛到最优解很难收敛到最优解很难收敛到最优解很难收敛到最优解 早熟收敛：群体过早失去多样性而收敛到局部最优解早熟收敛：群体过早失去多样性而收敛到局部最优解早熟收敛：群体过早失去多样性而收敛到局部最优解早熟收敛：群体过早失去多样性而收敛到局部最优解 进化时间长：进化过程中产

49、生大量数据，计算大、时间长进化时间长：进化过程中产生大量数据，计算大、时间长进化时间长：进化过程中产生大量数据，计算大、时间长进化时间长：进化过程中产生大量数据，计算大、时间长 参数选择问题：目前参数选择是根据经验来确定，缺乏理论依据参数选择问题：目前参数选择是根据经验来确定，缺乏理论依据参数选择问题：目前参数选择是根据经验来确定，缺乏理论依据参数选择问题：目前参数选择是根据经验来确定，缺乏理论依据 改变改变改变改变GAGAGAGA的组成成分（编码、适应度函数）的组成成分（编码、适应度函数）的组成成分（编码、适应度函数）的组成成分（编码、适应度函数）采用动态自适应技术（交叉率和变异率）采用动态自适应技术（交叉率和变异率）采用动态自适应技术（交叉率和变异率）采用动态自适应技术（交叉率和变异率）自适应自适应自适应自适应GAGAGAGA 采用非标准的遗传操作算子采用非标准的遗传操作算子采用非标准的遗传操作算子采用非标准的遗传操作算子 CHC CHC CHC CHC 结合其他技术，生成混合结合其他技术，生成混合结合其他技术，生成混合结合其他技术，生成混合GAGAGAGA 并行并行并行并行GAGAGAGA、小生境遗传算法等、小生境遗传算法等、小生境遗传算法等、小生境遗传算法等小结小结3 3 3 3、遗传算法改进方法：、遗传算法改进方法：、遗传算法改进方法：、遗传算法改进方法：