遗传算法简介课件

上传人:夏** 文档编号:578904822 上传时间:2024-08-25 格式:PPT 页数:34 大小:1.21MB
返回 下载 相关 举报
遗传算法简介课件_第1页
第1页 / 共34页
遗传算法简介课件_第2页
第2页 / 共34页
遗传算法简介课件_第3页
第3页 / 共34页
遗传算法简介课件_第4页
第4页 / 共34页
遗传算法简介课件_第5页
第5页 / 共34页
点击查看更多>>
资源描述

《遗传算法简介课件》由会员分享,可在线阅读,更多相关《遗传算法简介课件(34页珍藏版)》请在金锄头文库上搜索。

1、Your company sloganYour company slogan遗传算法简介 主讲人:蔡慧君小组成员:贺鹏飞指导老师:许桢英Your company sloganYour company slogan 基本概念基本概念1 1 基本遗传算法基本遗传算法2 2 遗传算法应用举例遗传算法应用举例3 3 遗传算法的特点和优势遗传算法的特点和优势4 4Your company sloganYour company slogan 1. 基本概念 1.1 1.1 个体与种群个体与种群 个体就是模拟生物个体而对问题中的对象 (一般就是问题的解)的一种称呼,一个个 体也就是搜索空间中的一个点。 种群

2、(population)就是模拟生物种群而由若 干个体组成的群体, 它一般是整个搜索空间 的一个很小的子集。Your company sloganYour company slogan 1.21.2 适应度与适应度函数适应度与适应度函数 适应度(fitness)就是借鉴生物个体对环境的 适应程度,而对问题中的个体对象所设计的表 征其优劣的一种测度。 适应度函数(fitness function)就是问题中的 全体个体与其适应度之间的一个对应关系。 它一般是一个实值函数。该函数就是遗传算 法中指导搜索的评价函数。 Your company sloganYour company slogan1.3

3、1.3染色体与基因染色体与基因染色体(chromosome)就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因(gene)。 例如: 个体 染色体 9 - 1001 (2,5,6)- 010 101 110Your company sloganYour company slogan1.4 1.4 遗传操作遗传操作亦称遗传算子(genetic operator),就是关于染色体的运算。遗传算法中有三种遗传操作: 选择-复制(selection-reproduction) 交叉(crossover,亦称交换、交配或杂交) 变异(mutation,亦称突变) Your compan

4、y sloganYour company slogan选择-复制通常做法是:对于一个规模为N的种群S,按每个染色体xiS的选择概率P(xi)所决定的选中机会, 分N次从S中随机选定N个染色体, 并进行复制。 这里的选择概率P(xi)的计算公式为Your company sloganYour company slogan交叉 就是互换两个染色体某些位上的基因。 s1=01000101, s2=10011011 可以看做是原染色体s1和s2的子代染色体。 例如, 设染色体 s1=01001011, s2=10010101, 交换其后4位基因, 即Your company sloganYour co

5、mpany slogan 变异变异 就是改变染色体某个就是改变染色体某个( (些些) )位上的基因。位上的基因。 例如例如, , 设染色体设染色体 s s=11001101=11001101将其第三位上的将其第三位上的0 0变为变为1, 1, 即即 s s=11=110 001101 01101 11111 101101= 01101= s s 。 s s 也可以看做是原染色体也可以看做是原染色体s s的子代染色体。的子代染色体。Your company sloganYour company slogan2 基本遗传算法 遗传算法基本流程框图生成初始种群计算适应度选择-复制交叉变异生成新一代种

6、群 终止 ?结束YNYour company sloganYour company slogan 基本遗传算法步1 在搜索空间U上定义一个适应度函数f(x),给定种群规模N,交叉率Pc和变异率Pm,代数T; 步2 随机产生U中的N个个体s1, s2, , sN,组成初始种群S=s1, s2, , sN,置代数计数器t=1; 步3 计算S中每个个体的适应度f(x) ;步4 若终止条件满足,则取S中适应度最大的个体作为所求结果,算法结束。Your company sloganYour company slogan 步步5 5 按选择概率按选择概率P P( (x xi i) )所决定的选中机会,所决

7、定的选中机会,每次从每次从S S中随机选定中随机选定1 1个个个体并将其染色体复制,共做个体并将其染色体复制,共做N N次次,然后将复制所得的,然后将复制所得的N N个染色个染色体组成群体体组成群体S S1 1; 步步6 6 按交叉率按交叉率P Pc c所决定的参加交叉的染色体数所决定的参加交叉的染色体数c c,从,从S S1 1中随机中随机确定确定c c个染色体,配对进行交叉操作,并用产生的新染色体代替原个染色体,配对进行交叉操作,并用产生的新染色体代替原染色体,得群体染色体,得群体S S2 2; 步步7 7 按变异率按变异率P Pmm所决定的变异次数所决定的变异次数mm,从,从S S2 2

8、中随机确定中随机确定mm个染个染色体,分别进行变异操作,并用产生的新染色体代替原染色体,色体,分别进行变异操作,并用产生的新染色体代替原染色体,得群体得群体S S3 3; 步步8 8 将群体将群体S S3 3作为新一代种群,即用作为新一代种群,即用S S3 3代替代替S S,t = t+1t = t+1,转步,转步3 3; Your company sloganYour company slogan3. 遗传算法应用举例 例例4.1 利用遗传算法求解区间0,31上的二次函数y=x2的最大值。y=x2 31 XYYour company sloganYour company slogan 分析分

9、析 原问题可转化为在区间原问题可转化为在区间0, 310, 31中搜索能使中搜索能使y y取最大值的点取最大值的点a a的问题。那么,的问题。那么,0, 310, 31 中的中的点点x x就是个体就是个体, , 函数值函数值f f( (x x) )恰好就可以作为恰好就可以作为x x的适的适应度,区间应度,区间0, 310, 31就是一个就是一个( (解解) )空间空间 。这样。这样, , 只要能给出个体只要能给出个体x x的适当染色体编码的适当染色体编码, , 该问题就该问题就可以用遗传算法来解决。可以用遗传算法来解决。Your company sloganYour company sloga

10、n解(1) 设定种群规模,编码染色体,产生初始种群。 将种群规模设定为4;用5位二进制数编码染色体;取下列个体组成初始种群S1: s1= 13 (01101), s2= 24 (11000) s3= 8 (01000), s4= 19 (10011) (2) 定义适应度函数, 取适应度函数:f (x)=x2 (3) 计算各代种群中的各个体的适应度, 并对其染色体 进 行 遗 传 操 作 ,直 到 适 应 度 最 高 的 个 体 (即31(11111))出现为止。 Your company sloganYour company slogan首先计算种群首先计算种群S S1 1中各个体中各个体 s

11、 s1 1= 13(01101), = 13(01101), s s2 2= 24(11000)= 24(11000) s s3 3= 8(01000), = 8(01000), s s4 4= 19(10011)= 19(10011)的适应度的适应度f f ( (s si i) ) 。 容易求得容易求得 f f ( (s s1 1) = ) = f f(13) = 13(13) = 132 2 = 169= 169 f f ( (s s2 2) = ) = f f(24) = 24(24) = 242 2 = 576= 576 f f ( (s s3 3) = ) = f f(8) = 8(

12、8) = 82 2 = 64= 64 f f ( (s s4 4) = ) = f f(19) = 19(19) = 192 2 = 361= 361Your company sloganYour company slogan再计算种群再计算种群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.31Your company sloganYour company slogan 赌轮选择示意s40.31s20

13、.49s10.14s30.06 赌轮选择法Your company sloganYour company slogan在算法中赌轮选择法可用下面的子过程来模拟: 在0, 1区间内产生一个均匀分布的随机数r。 若rq1,则染色体x1被选中。 若qk-1rqk(2kN), 则染色体xk被选中。 其中的qi称为染色体xi (i=1, 2, , n)的积积累累概概率率, 其计算公式为 Your company sloganYour company slogan 选择-复制 设从区间0, 1中产生4个随机数如下: r1 = 0.450126, r2 = 0.110347 r3 = 0.572496, r

14、4 = 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 1Your company sloganYour company slogan于是,经复制得群体:s1 =11000(24), s2 =01101(13) s3 =11000(24), s4 =10011(19)交叉 设交叉率pc=100%,即S1中的全体染色体都参加交叉运算。 设s1与s2配对,s3与s4配对。分别交换后两位基因,得新染色体: s

15、1=11001(25), s2=01100(12) s3=11011(27), s4=10000(16)Your company sloganYour company slogan变异 设变异率pm=0.001。 这样,群体S1中共有 540.001=0.02位基因可以变异。 0.02位显然不足1位,所以本轮遗传操作不做变异。于是,得到第二代种群S2: s1=11001(25), s2=01100(12) s3=11011(27), s4=10000(16)Your company sloganYour company slogan 第二代种群第二代种群S2中各染色体的情况中各染色体的情况 染

16、色体 适应度选择概率积累概率 估计的选中次数s1=11001 625 0.36 0.36 1s2=01100 144 0.08 0.44 0s3=11011 729 0.41 0.85 2s4=10000 256 0.15 1.00 1Your company sloganYour company slogan 假设这一轮选择-复制操作中,种群S2中的4个染色体都被选中个染色体都被选中,则得到群体: s1=11001(25), s2= 01100(12) s3=11011(27), s4= 10000(16) 做交叉运算,让s1与s2,s3与s4 分别交换后三位基因,得 s1 =11100(2

17、8), s2 = 01001(9) s3 =11000(24), s4 = 10011(19) 这一轮仍然不会发生变异。 于是,得第三代种群S3: s1=11100(28), s2=01001(9) s3=11000(24), s4=10011(19) Your company sloganYour company slogan 第三代种群第三代种群S3中各染色体的情况中各染色体的情况 染色体 适应度选择概率积累概率 估计的选中次数s1=11100 784 0.44 0.44 2s2=01001 81 0.04 0.48 0s3=11000 576 0.32 0.80 1s4=10011 36

18、1 0.20 1.00 1Your company sloganYour company slogan 设这一轮的选择-复制结果为: 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) 这一轮仍然不会发生变异。于是,得第四代种群S4: s1=11111(31), s2=11100(28) s3=11000(24), s4=10000(16) Your company sl

19、oganYour company slogan 显然,在这一代种群中已经出现了适应度最高的染色体s1=11111。于是,遗传操作终止,将染色体“11111”作为最终结果输出。然后,将染色体“11111”解码为表现型,即得所求的最优解:31。 将31代入函数y=x2中,即得原问题的解,即函数y=x2的最大值为961。 Your company sloganYour company sloganYYy=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

20、X第四代种群及其适应度Your company sloganYour company slogan4 遗传算法的特点与优势 遗传算法的主要特点 遗传算法一般是直接在解空间搜索, 而不像图搜索那样一般是在问题空间搜索, 最后才找到解。 遗传算法的搜索随机地始于搜索空间的一个点集, 而不像图搜索那样固定地始于搜索空间的初始节点或终止节点, 所以遗传算法是一种随机搜索算法。 Your company sloganYour company slogan 遗传算法总是在寻找优解遗传算法总是在寻找优解, , 而不像图搜而不像图搜索那样并非总是要求优解索那样并非总是要求优解, , 而一般是设法尽快而一般是设

21、法尽快找到解找到解, , 所以遗传算法又是一种优化搜索算法。所以遗传算法又是一种优化搜索算法。 遗传算法的搜索过程是从空间的一个点遗传算法的搜索过程是从空间的一个点集集( (种群种群) )到另一个点集到另一个点集( (种群种群) )的搜索的搜索, ,而不像图而不像图搜索那样一般是从空间的一个点到另一个点地搜索那样一般是从空间的一个点到另一个点地搜索。搜索。 因而它实际是一种并行搜索因而它实际是一种并行搜索, , 适合大规适合大规模并行计算模并行计算, ,而且这种种群到种群的搜索有能力而且这种种群到种群的搜索有能力跳出局部最优解。跳出局部最优解。Your company sloganYour c

22、ompany slogan遗传算法的适应性强, 除需知适应度函数外, 几乎不需要其他的先验知识。 遗传算法长于全局搜索, 它不受搜索空间的限制性假设的约束,不要求连续性, 能以很大的概率从离散的、多极值的、 含有噪声的高维问题中找到全局最优解。 Your company sloganYour company slogan遗传算法的应用遗传算法的应用遗传算法在人工智能的众多领域便得到了广泛应用。遗传算法在人工智能的众多领域便得到了广泛应用。例如,机器学习、聚类、控制(如煤气管道控制)、例如,机器学习、聚类、控制(如煤气管道控制)、规划(如生产任务规划)、设计(如通信网络设计、规划(如生产任务规划

23、)、设计(如通信网络设计、布局设计)、调度(如作业车间调度、机器调度、运布局设计)、调度(如作业车间调度、机器调度、运输问题)、配置(机器配置、分配问题)、组合优化输问题)、配置(机器配置、分配问题)、组合优化(如(如TSPTSP、背包问题)、函数的最大值以及图像处理和、背包问题)、函数的最大值以及图像处理和信号处理等等。信号处理等等。另一方面,人们又将遗传算法与其他智能算法和技术另一方面,人们又将遗传算法与其他智能算法和技术相结合,使其问题求解能力得到进一步扩展和提高。相结合,使其问题求解能力得到进一步扩展和提高。例如,将遗传算法与模糊技术、神经网络相结合,已例如,将遗传算法与模糊技术、神经网络相结合,已取得了不少成果。取得了不少成果。 Your company sloganYour company slogan对遗传算法的进一步研究将涉及到模式定理和隐性、并行性等内容。有兴趣的同学可参阅有关专著。Your company sloganYour company slogan

展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 建筑/环境 > 施工组织

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号