遗传算法应用课件.ppt

《遗传算法应用课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、遗传算法1.基本概念2.应用举例1基本概念遗传算法：模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存+检测”的迭代过程的搜索算法。本质特征：与传统的启发式优化搜索算法（爬山算法、模拟退火算法）相比，遗传算法的主要本质特征在于群体搜索策略和简单的遗传算子。1基本概念理论基础：主要以收敛性分析为主，即群体收敛到优化问题的全局最优解的概率。分类：从整体上讲，可分为给予随机过程的收敛性研究（随机模型理论）和基于模式理论的收敛性分析（进化动力学理论）1基本概念遗传算法的优点：以目标函数值作为搜索信息，提高了搜索效率；以决策

2、变量的编码作为运算对象，这种编码处理方式可以更方便的操作算子；使用自适应概率搜索技术，增加了搜索过程的灵活性。1基本概念遗传算法的构成要素：①参数编码（一般二进制）②初始群体的设定N③适应度函数④遗传算子（包括选择算子、交叉算子、突变算子）⑤基本遗传算法运行参数（N、T/Pc/Pm/Pr）1基本概念遗传算法的一般框架：①编码设置初始群体②对群体迭代的执行下面的两个步骤，直到满足停止准则：(i).计算群体中每个个体的适应值(ii).应用选择、交叉和突变算子产生下一代群体③把在任一代中出现的最好的个体串指定为遗传算法的执行结果，此结果可以表示问题的一个解（或近似解）算法流程图：2遗

3、传算法应用案例例：利用遗传算法求解区间[0,31]上二次函数y=x2的最大值。分析：原问题可转化为在区间[0,31]中搜索能使y取最大值的点x的问题。那么，[0,31]中的点x就是个体，函数值f(x)恰好就可以作为x的适应度，区间[0,31]就是一个（解）空间。这样，只要能给出个体x的适当染色体编码，该问题就可以用遗传算法来解决。解：设定种群规模，编码染色体，产生初始种群。将种群规模设定为4，用5位二进制数编码染色体，取下列个体组成初始种群S1；s1=13(01101),s2=24(11000)s3=8(01000)，s4=19(10011)定义适应度函数，取适应度函数：f(

4、x)=x2计算各代种群中的各个体的适应度，并对其染色体进行遗传操作，直到适应度最高的个体(即31（11111）)出现为止首先计算种群S1中各个体的适应度f(si):s1=13（01101）,s2=24(11000)s3=8（01000）,s4=19（10011）容易求得:f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361再计算种群S1中各个体的选择概率。选择概率的计算公式为:由此可求得:P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(

5、s4)=P(19)=0.31选择(用轮盘赌选择法)设从区间［0,1］中产生4个随机数如下:r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503于是，经选择得群体：s1’=11000（24）,s2’=01101（13）s3’=11000（24）,s4’=10011（19）交叉设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。并且设s1’与s2’配对，s3’与s4’配对。分别交换后两位基因，得新染色体si’’：s1’’=11001（25）,s2’’=01100（12）s3’’=11011（27）,s4’’=10000（16）突变设突变率

6、pm=0.001，这样，群体S1中共有5×4×0.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。于是，得到第二代种群S2：s1’’=11001（25）,s2’’=01100（12）s3’’=11011（27）,s4’’=10000（16）染色体情况（种群S2）：第二轮遗传运算：做选择运算，4个染色体都被选中，则得到群体：s1’=11001（25）,s2’=01100（12）s3’=11011（27）,s4’=10000（16）做交叉运算，让s1’与s2’，s3’与s4’分别交换后三位基因得：s1’’=11100（28）,s2’’=01001（9

7、）s3’’=11000（24）,s4’’=10011（19）这一轮仍然不会发生变异。于是，得第三代种群S3：s1=11100（28）,s2=01001（9）s3=11000（24）,s4=10011（19）染色体情况（种群S3）：第三轮遗传算法（种群S3）：做选择运算，结果为：s1’=11100（28）,s2’=11100（28）s3’=11000（24）,s4’=10011（19）做交叉运算，让s1’与s4’，s2’与s3’分别交换后两位基因得：s1’’=11111（31）,s