实验十遗传算法与优化问题.pptx

《实验十遗传算法与优化问题.pptx》由会员分享，可在线阅读，更多相关《实验十遗传算法与优化问题.pptx（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、,#,实验十,遗传算法与优化问题,数学实验,问题背景和实验目的,遗传算法（,Genetic,Algorithm,，简称,GA,），,是模,拟达尔文的遗传选择和自然淘汰的生物进化过程的计算机算法，它由美国,Holland,教授,1975,年提出。,遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适合并行处理及应用范围广,等显著特点，奠定了它作为,21,世纪关键智能计算之一的地位。,本实验主要介绍遗传算法的基本理论，然后通过求解几个简单的函数最值问题，来说明如何利用遗传算法进行初步的优化计算。,遗传算法基本原理,基本思想：,基于模仿生物界遗传学的遗传过程，把问题的参数用,基因来表示，

2、把问题的解用染色体来表示代表（,在计算,机里用二进制码表示），,从而得到一个由具有不同染色体的个体组成的群体。,这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代，后代随机化地继承父代的最好特征，并也在生存环境的控制支配下继续这一过程。,群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优解。,遗传学相关概念,遗传学,遗传算法,数学,1,个,体,要处理的基本对象、结,构,也就是可行,解,2,群,体,个体的集,合,被选定的一组可行解,3,染色体 个体的表现形式,可行解的编码,4,基,因,染色体中的元,素,编码中的元素,5,基因位 某一基因在染

3、色体中的位置 元素在编码中的位置,6,适应值 个体对于环境的适应程度，可行解所对应的适应,或在环境压力下的生存能力 函数值,7,种,群,被选定的一组染色体或个,体,根据入选概率定出的一组可行解,8,选,择,从群体中选择优胜的个体,，,淘汰劣质个体的操,作,保留或复制适应值大的可行解，去掉小的,可行解,遗传学相关概念,遗传学,遗传算法,数学,9,交叉,一组染色体上对应基因段,的交换,根据交叉原则产生的,一组新解,10,交叉概率,染色体对应基因段交换的,概率（可能性大小,）,闭区间,0,1,上的一个,值，一般为,0.650.90,11,变异,染色体水平上基因变化,编码的某些元素被改,变,12,变异

4、概率,染色体上基因变化的概率,（可能性大小,）,开区间,(0,1),内的一个,值,一般为,0.0010.01,13,进化、,适者生存,个体进行优胜劣汰的进化,一代又一代地优化,，目标函数取到最大值，,最优的可行解,遗传算法的步骤,遗传算法计算优化的过程就如同生物学上生物遗,传进化的过程，主要有三个基本操作（或算子,）：,选择,（Selection）,交叉,（Crossover）,变异,（Mutation）,遗传算法的步骤,遗传算法基本步骤：,把问题的解表示成,“,染色体,”,，在算法中就是以二进制,编码的串，给出一群,“,染色体,”,，也就是假设的可行解,把这些可行解置于问题的,“,环境,”,

5、中，按适者生存的原则，,选取较适应环境的,“,染色体,”,进行复制，并通过交叉、变异过,程产生更适应环境的新一代,“,染色体,”,群,经过这样的一代一代地进化，最后就会收敛到最适应环,境的一个,“,染色体,”,上，它就是问题的最优解,遗传算法有很多种具体的不同实现过程，这里仅介绍标准遗传算法的主要步骤。,遗传算法具体步骤,选择编码策略，把参数集合（可行解集合）,转换染色,体结构空间；,定义适应函数，便于计算适应值；,确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数；,随机产生初始化群体；,计算群体中的个体或染色体解码后的适应值；,按照遗传策略，运用选择、

6、交叉和变异算子作用于群体，形成下一代群体；,判断群体性能是否满足某一指标，或者已完成预定的,迭代次数，不满足则返回第五步，或者修改遗传策略,再返回第六步,产生初始群体,是否满足终止条件,得到结果,是,结束程序,否,计算每个个体的适应值,以概率选择遗传算子,选择一个个体复制到新群体,选择两个个体进行交叉插入到新群体,选择一个个体进行变异插入到新群体,得到新群体,例,1.,设,f,(,x,)=,-,x,2,+,2,x,+0.5,，求,max,f,(,x,),x,-,1,2,。,遗传算法的实际应用,我们将通过这个简单的求最值问题来详细给出遗传算法,的整个过程。,编码和产生初始群体,首先需要确定编码的

7、策略，也就是说如何把,-1,2,区间内的数用计算机语言表示出来。编码就是从表现型到基因型的映射，编码时要注意以下三个原则：,完备性：问题空间中所有点（潜在解）都能成为,GA,编,码空间中的点（染色体位串）,的表现型；,健全性：,GA,编码空间中的染色体位串必须对应问题空,间中的某一潜在解；,非冗余性：染色体和潜在解必须一一对应,编码,我们采用二进制形式来解决编码问题，即将某个变量值代,表的个体表示为一个,0,1,二进制串。串的长度取决于求解的,精度，例如假设求解精度为保留六位小数，由于区间,-1,2,的长度为,3,，则必须将该区间分为,3,10,6,等分。因为,2,21,3,10,6,2,22

8、,，所以编码所用的二进制串至少需要,22,位。,二进制串（,b,21,b,20,b,19,b,1,b,0,）,与,a,b,内实数的一一映射：,二进制串,十进制数,a,b,内实数,b,21,b,20,b,19,b,1,b,0,编码,其对应的十进制数为：,转化到,-1,2,内的实数为：,例,.,二进制串,a=,产生初始群体,随机的产生一个初始群体。,pop1=,，,%,a1,，,%,a2,，,%,a3,%,a4,这里假设初始群体的个体数为,4,。,转化成,-1,2,之间的十进制数即为：,下面就需要解决每个染色体个体的适应值,pop1=,1.523032,0.574022,-0.697235,0.2

9、47238,适应函数,（,2,）,定义适应函数和适应值,由于目标函数,f,(,x,),在,-1,2,内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率打下基础。,定义适应函数：,为了便于计算，这里,的,F,min,采用了一个特定的输入,值,例：,如果取,F,min,=-1,，则,f,(,x,)=1,对应的适应值为,g,(,x,)=2,适应函数和适应值,上述随机产生的初始群体，取,F,min,=-1,，则,它们的目,标函数值和适应值分别为：,f(pop1)=,1.226437,1.31

10、8543,-1.380607,0.933350,g(pop1)=2.226437,2.318543,0,1.933350,选择标准,（,3,）,确定选择标准,用适应值比例来作为入选概率。,设给定的规模为,n,的群体,pop=,a,1,a,2,.,a,n,，个体,a,i,的适应值为,g,(,a,i,),，则其入选概率为,上述随机产生的初始群体，它们的入选概率分别为：,p(pop1)=g(pop1)/sum(g(pop1),=0.343675,0.357892,0,0.298433,产生种群,，,%,a1,，,%,a2,，,%,a2,%,a4,（,4,）,产生种群,将入选概率大的个体选入种群，淘汰

11、概率小的个体，并用概率最大的个体补入种群，得到与原群体大小同样的种群。,在上述随机产生的初始群体中，淘汰掉,a,3,，再加入,a,2,，得,到新的种群：,newpop1=,Matlab,程序参见附录,11,交叉,（,5,）,交叉,交叉也就是将一组染色体上对应基因段的交换得到新的染色体，然后得到新的染色体组，组成新的群体。,将前面得到的,newpop1,的四个个体两两配对，重复的,不配对，进行交叉（可以在任一位进行交叉,）：,新的群体,jchpop1,变异,（,6,）,变异,变异就是通过一个小概率改变染色体位串上的某个基因。,现把,jchpop1,中第,3,个个体中的第,9,位改变，就产生,了变

12、异，得到了新的群体,pop2,：,pop2=,然后重复上述的选择、交叉、变异，直到满足终止条件为止,终止条件,（,7,）,终止条件,遗传算法的终止条件有两类常见条件：,采用设定最大（遗传）,代数的方法，一般可设定为,50,代，,此时就可能得出最优解此种方法简单易行，但可能不是,很精确,（,Matlab,程序参见附录,1,）,根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因位相似程度来进行控制,遗传算法的收敛性,遗传算法通过对这些操作的适当设计和运行，可以实现兼顾全局搜索和局部搜索的所谓均衡搜索,均衡搜索的具体实现图示,遗传算法的收敛性,遗传算法虽然可以实现均衡的搜索，并且在许多复

13、杂问题的求解中往往能得到满意的结果，但是该算法的全局优化收敛性的理论分析尚待解决。目前普遍认为，标准遗传算法并不保证全局最优收敛。但是，在一定的约束条件下，遗传算法可以实现这一点。,定理,1,如果变异概率为 ，交叉概率为，同时采,用比例选择法,(,按个体适应度占群体适应度的比例进行复制,),，则标准遗传算法的变换矩阵,P,是基本的。,遗传算法的收敛性,定理,2,标准遗传算法（参数如定理,1,）,不能收敛至全局最优解。,标准遗传算法是不能收敛至全局最最优解，对标准遗传算法作一些改进，就能够保证其收敛性。,最佳个体保存方法,（,elitist,model,）,的思想是把群体中适应度最高的个体不进行

14、配对交叉而直接复制到下一代中。,设时刻,t,(,第,t,代,),时，群体中,a,*(,t,),为最佳个体，并设,A,(,t,+1,),为新一代群体，若,A,(,t,+1,),中不存在,a,*(,t,),，则把,a,*(,t,),作为,A,(,t,+1,),中的第,n,+1,个个体,(,其中，,n,为群体大小,),最佳个体保存方法,该方法的优点：确保进化过程中某一代的最优解不被交叉,和变异操作所破坏。,该方法的缺点：局部最优个体的遗传基因会急速增加而使进化有可能限于局部解，即该方法的全局搜索能力差，它更,适合单峰性质的搜索空间搜索，而不是多峰性质的空间搜索。,使用策略：与其他选择方法结合使用。,

15、最佳个体保存方法,定理,4,具有定理,1,所示参数，且在选择前保留当前最优解的遗传算法可收敛于全局最优解。,定理,3,具有定理,1,所示参数，且在选择后保留当前最优值的遗传算法最终能收敛到全局最优解。,实验举例,例,1.,设,f,(,x,)=,-,x,2,+,2,x,+0.5,，求,max,f,(,x,),x,-,1,2,。,解：,群体中包含六个染色体，每个染色体用,22,位码表示，,变异概率为,0.01,，变量区间为,-1,2,，取,F,min,=-2,，遗传,代数为,50,代，运用第一种终止条件（指定遗传代数）,的,Matlab,程序为,Count,Result,BestMember=,Genetic1(22,6,-x*x+2*x+0.5,-1,2,-2,0.01,50),教材,P,：练习,1,、,2,、,4,、,6,要求写入实验报告册,其它练习自己上机练习，不用写入报告,上机作业,