第5章-遗传算法.pptx

《第5章-遗传算法.pptx》由会员分享，可在线阅读，更多相关《第5章-遗传算法.pptx（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、智能优化算法智能优化算法又称现代启发式算法，是一种具有全局优化性能、通用性强且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。遗传算法属于智能优化算法之一。第1页/共59页常用的智能优化算法 遗传算法 模拟退火算法禁忌搜索算法粒子群算法蚁群算法第2页/共59页智能优化算法的特点从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。求解的过程通常是一个迭代的过程，即不是一步就完成。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。第3页/共59页遗传算法概述 美国J.Holland教授于19

2、75年在专著自然界和人工系统的适应性中首先提出。借鉴生物界自然选择和自然遗传机制的随机化搜索算法。模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象。第4页/共59页遗传算法概述 在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。基本遗传算法（Simple Genetic Algorithms，GA)又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。第5页/共5

3、9页基本遗传算法的组成（1）编码（产生初始种群）（2）适应度函数（3）遗传算子（选择、交叉、变异）（4）运行参数第6页/共59页 编码 遗传算法（GA）通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。基本遗传算法（SGA）使用二进制串进行编码。1000101110110101000111 染色体基因第7页/共59页 编码示例 求下列一元函数的最大值：其中x-1,2，求解结果精确到6位小数。第8页/共59页 一个问题 对于x-1,2，结果精确到6位小数，（1）二进制编码要求取多少位？（2）十进制实数与二进制编码之间应满足怎样的

4、数学关系？第9页/共59页 编码示例的分析 区间长度为3，求解结果精确到6位小数，因此可将自变量定义区间划分为3106等份。又因为221 3106 222，所以二进制编码长度至少需要22位。编码过程实质是将区间-1，2内对应的实数值转化为一个二进制串（b21b20b19b18b1b0）。101010111111101011000第10页/共59页 一个问题 对于x-1,2，结果精确到6位小数，十进制实数与二进制编码之间应满足怎样的数学关系？第11页/共59页 编码(二进制)与实数(十进制)的转换(1000101110110101000111)2第12页/共59页 编码与实数的转换(100010

5、1110110101000111)20.637197第13页/共59页第14页/共59页基因型与表现型 基因型：1000101110110101000111 表现型：表现型：0.637197 编码解码个体（染色体）1000101110110101000111基因第15页/共59页初始种群 基本遗传算法（SGA）采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。第16页/共59页 适应度函数 遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解

6、问题本身的要求而定。第17页/共59页选择算子遗传算法使用选择运算对个体进行优胜劣汰操作。适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是从父代群体中选取一些个体，遗传到下一代群体。基本遗传算法（SGA）中选择算子采用轮盘赌选择方法。第18页/共59页一等奖一等奖二等奖二等奖二等奖二等奖三等奖三等奖三等奖三等奖四等奖四等奖四等奖四等奖轮盘赌选择方法轮盘赌选择方法第19页/共59页轮盘赌选择方法轮盘赌选择又称比例选择算子，其基本思想是：各个个体被选中的概率与其适应度函数值成正比。设群体大小为N，个体xi 的适应度为 f(xi)，则个体x

7、i的选择概率为：第20页/共59页轮盘赌选择法可用如下过程模拟来实现：(1)在0,1内产生一个均匀分布的随机数r。(2)若rq1,则染色体x1被选中。(3)若qk-1rqk(2kN),则染色体xk被选中。其中的qi称为染色体xi(i=1,2,n)的积累概率,其计算公式为 轮盘赌选择方法第21页/共59页积累概率实例：轮盘赌选择方法0 0.14 0.63 0.69 1 q1 q2 q3 q4 0.14 0.49 0.06 0.31积累概率概率第22页/共59页轮盘赌选择方法轮盘赌选择方法的实现步骤:（1）计算群体中所有个体的适应度值；（2）计算每个个体的选择概率；（3）计算积累概率；（4）采用模

8、拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。第23页/共59页轮盘赌选择方法例如，有染色体 s1=13(01101)s2=24(11000)s3=8 (01000)s4=19(10011)假定适应度为f(s)=s2，则 f(s1)=f(13)=132=169 f(s2)=f(24)=242=576 f(s3)=f(8)=82=64 f(s4)=f(19)=192=361第24页/共59页染色体的选择概率为第25页/共59页染色体的累计概率为第26页/共59页s40.31s20.49s10.14S30.060 0.14 0.

9、63 0.69 1 q1 q2 q3 q4 0.14 0.49 0.06 0.31第27页/共59页 例如，从区间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第28页/共59页交叉算子 交叉运算，是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交

10、换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。基本遗传算法（SGA）中交叉算子采用单点交叉算子。第29页/共59页单点交叉运算 交叉前：01000|0111000000001000011100|00000111111000101交叉后：01000|00000111111000101 （孩子1）11100|01110000000010000 （孩子2）交叉点交叉点第30页/共59页变异算子 变异运算，是指改变个体编码串中的某些基因值，从而形成新的个体。变异运算是产生新个体的辅助方法，决定遗传算法的局部搜索能力

11、，保持种群多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。基本遗传算法（SGA）中变异算子采用基本位变异算子。第31页/共59页变异算子 基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则将其变为1；反之，若原有基因值为1，则将其变为0。第32页/共59页基本位变异示例变异前：000001110000000010000变异后：000001110001000010000变异点变异点第33页/共59页运行参数（1）M ：种群规模（2）T ：遗传运算的终止进化代数（

12、3）Pc ：交叉概率（4）Pm：变异概率 第34页/共59页基本遗传算法的框图 产生初始群体产生初始群体满足停止准则？满足停止准则？是是输出结果输出结果计算适应度值计算适应度值比例选择运算比例选择运算单点交叉运算单点交叉运算基本位变异运算基本位变异运算否否产生新一代群体产生新一代群体执行执行M/2M/2次次第35页/共59页已已已已知知知知x x为为为为整整整整数数数数，利利利利用用用用遗遗遗遗传传传传算算算算法法法法求求求求解解解解区区区区间间间间0,0,3131上的二次函数上的二次函数上的二次函数上的二次函数y=xy=x2 2的最大值。的最大值。的最大值。的最大值。y=x2 31 XY遗传

13、算法的应用举例第36页/共59页 分析 原问题可转化为在区间0,31中搜索能使 y 取最大值的点 a 的问题。个体：0,31 中的任意点x 适应度：函数值f(x)=x2 解空间：区间0,31 这样,只要能给出个体x的适当染色体编码,该问题就可以用遗传算法来解决。第37页/共59页解解(1)设设定定种种群群规规模模,编编码码染染色色体体，产产生生初初始始种种群。群。将将种种群群规规模模设设定定为为4；用用5位位二二进进制制数数编编码码染染色体；取下列个体组成初始种群色体；取下列个体组成初始种群S1 s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)

14、(2)定义适应度函数定义适应度函数,取适应度函数取适应度函数 f(x)=x2 第38页/共59页(3)计计算算各各代代种种群群中中的的各各个个体体的的适适应应度度,并并对对其其染染色色体体进进行行遗遗传传操操作作,直直到到适适应应度度最最高高的的个个体，即体，即31（11111）出现为止。）出现为止。第39页/共59页首先计算种群S1中各个体 s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)的适应度f(si),容易求得 f(s1)=f(13)=132=169 f(s2)=f(24)=242=576 f(s3)=f(8)=82=64 f(s4)=

15、f(19)=192=361第40页/共59页再计算种群S1中各个体的选择概率。由此可求得 P(s1)=P(13)=0.14 P(s2)=P(24)=0.49 P(s3)=P(8)=0.06 P(s4)=P(19)=0.31第41页/共59页再计算种群S1中各个体的积累概率第42页/共59页0 0.14 0.63 0.69 1 q1 q2 q3 q4 0.14 0.49 0.06 0.31种群S1中各个体的积累概率第43页/共59页选择-复制：设从区间设从区间0,1中产生中产生4个随机数个随机数:r1=0.450126,r2=0.110347 r3=0.572496,r4=0.98503 染色体

16、染色体 适应度适应度选择概率选择概率积累概率积累概率选中次数选中次数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第44页/共59页于是，经复制得群体：于是，经复制得群体：s1=11000（24）,s2=01101（13）s3=11000（24）,s4=10011（19）被选中两次被选中两次第45页/共59页交叉 设设交交叉叉率率pc=100%，即即S1中中的的全全体体染染色色体体都都参加交叉运算。参加交叉运算。设设s1与与s2配对，配对，s3与与s4

17、配对。配对。s1=11000（24）,s2=01101（13）s3=11000（24）,s4=10011（19）分别交换分别交换后两位基因后两位基因，得新染色体：，得新染色体：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）第46页/共59页变异 设变异率设变异率pm=0.001。这样，群体这样，群体S1中共有中共有 540.001=0.02位基因可以变异。位基因可以变异。0.02位位显显然然不不足足1位位，所所以以本本轮轮遗遗传传操操作作不不做变异。做变异。第47页/共59页于是，得到第二代种群于是，得到第二代种群S2：s1=11001（2

18、5）,s2=01100（12）s3=11011（27）,s4=10000（16）第48页/共59页 第二代种群S2中各染色体的情况 染色体染色体 适应度适应度选择概率选择概率积累概率积累概率 估计估计选中次数选中次数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 1第49页/共59页 假设这一轮选择假设这一轮选择-复制操作中，种群复制操作中，种群S2中的中的4个个染色体都被选中，则得到群体：染色体都被选中，则得到群体：s1=11001（25）,s2=01

19、100（12）s3=11011（27）,s4=10000（16）做交叉运算，让做交叉运算，让s1与与s2，s3与与s4 分别交换分别交换后三位后三位基因，得基因，得 s1=11100（28）,s2=01001（9）s3=11000（24）,s4=10011（19）这一轮仍然不会发生变异。这一轮仍然不会发生变异。第50页/共59页于是，得第三代种群于是，得第三代种群S3：s1=11100（28）,s2=01001（9）s3=11000（24）,s4=10011（19）第51页/共59页 第三代种群第三代种群S3中各染色体的情况中各染色体的情况 染色体染色体 适应度适应度选择概率选择概率 积累概率

20、积累概率 估计的估计的选中次数选中次数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第52页/共59页 设这一轮的选择设这一轮的选择设这一轮的选择设这一轮的选择-复制结果为：复制结果为：复制结果为：复制结果为：s1=11100（28）,s2=11100（28）s3=11000（24）,s4=10011（19）做交叉运算做交叉运算做交叉运算做交叉运算，让让让让s1与与与与s4，s2与与与与s3 分别交分别交分别交分别交换换换换后两位基因后两位基因后两位基

21、因后两位基因，得，得，得，得 s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（16）这一轮仍然不会发生变异。这一轮仍然不会发生变异。这一轮仍然不会发生变异。这一轮仍然不会发生变异。被选中两次被选中两次第53页/共59页 于是，得第四代种群于是，得第四代种群S4：s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（16）出现了最出现了最优解！优解！第54页/共59页 显显然然，在在这这一一代代种种群群中中已已经经出出现现了了适适应应度度最最高高的的染染色色体体s1=11111。于于是是，遗遗传传操操作作终终止

22、止，将将染染色体（色体（11111）作为最终结果输出。作为最终结果输出。然后，将染色体然后，将染色体“11111”解码为表现型，解码为表现型，即得所求的即得所求的最优解：最优解：31。将将31代入函数代入函数y=x2中，即得原问题的解，即中，即得原问题的解，即函数函数y=x2的最大值为的最大值为961。第55页/共59页YYy=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第四代种群及其适应度第56页/共59页刚刚产生四代种群及其适应度。你知道这四代种群之间有何发展规律吗？四代种群的发展规律就是适应度的整体水平越来越好，直到最优解出现！第57页/共59页第58页/共59页感谢您的观看！第59页/共59页