遗传算法实例参考.pptx

一、遗传算法的基本知识遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。1975年遗传算法美国J.Holland教授具有内在的隐并行性和更好的全局寻优能力；直接对结构对象进行操作，不存在求导和函数连续性的限定采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。第1页/共39页遗传算法的组成遗传算法可定义为一个 8 员组：SGA=(C,E,P0,M,T)C 个体的编码方法；E 个体适应度评价函数；P0 初始群体；M 群体大小；选择算子；交叉算子；变异算子；T 遗传运算终止条件。第2页/共39页遗传算法思想初始化群体；计算群体上每个个体的适应度值；按由个体适应度值所决定的某个规则选择将进入下一代的个体；按概率Pc进行交叉操作；按概率Pm进行突变操作；没有满足某种停止条件，则转第(2)步，否则进入(7)。输出种群中适应度值最优的染色体作为问题的满意解或最优解。第3页/共39页遗传算法的优点（1）遗传对所解的优化问题没有太多的数学要求，遗传算法可以处理任意形式的目标函数和约束，无论是线性的还是非线性的，离散的还是连续，甚至混合的搜索空间。（2）进化算子的各态历经性使得遗传算法能够非常有效的进行概率意义下的全局搜索，而传统的优化方法是通过邻近点比较而转移到较好的点，从而达到收敛的局部搜索过程。（3）遗传算法对于各种特殊问题可以提供极大的灵活性来混合构造领域独立的启发式，从而保证算法的有效性。第4页/共39页遗传算法性能分析指标（1）在线性性能评估在线性能表示为：其中：T 是进化代数；是第t代的平均适应度函数；表示到T代为止所有适应度函数值的平均性能。在线指标用于说明算法的在线性能。第5页/共39页（2）离线性性能评估 离线性能表示为：其中是第t代最好的个体的适应度函数值；表示至第T代每次最好的适应度函数值的平均。离线指标用于说明算法的收敛性。第6页/共39页二、实例讲解目标分配问题描述为：m个地空导弹火力单元对n 批空袭目标进行目标分配。每批空袭用一个火力单元实施射击。假设进行目标分配之前，各批目标的威胁程度与各火力单元对各批目标的射击有利程度已经经过评估和排序。注：空袭批次可能因机型的不同，袭击方向的不同，袭击方式的不同，而不同。火力单元可能因导弹类型的不同，分布方位的不同，预警时间的不同，而不同。这些不同，导致了各批目标的威胁程度与各火力单元对各批目标的射击有利程度的不同。第7页/共39页第 j 批目标的威胁程度评估值为wj，第 i 个火力单元对第 j 批目标射击有利程度估计值为pij，令各火力单元对各批目标进行拦击的效益值为cij=wjpij，其中cij表示对某批目标进行拦击我方获益大小程度。目标分配的目的是满足目标分配的基本原则，追求总体效益最佳，即求：染色体采用十进制编码，每个基因表示为火力点的编号。染色体的长度由按目标批次编号顺序排列的火力单元分配编号组成，表示一种可能的分配方案。第8页/共39页射击有利程度估计值（对每个定点测量后确定的）p=.87.52.11.78.72.69.94.72.36.28.27.74.24.78.45;.87.52.11.78.72.69.94.72.36.28.27.74.24.78.45;.87.52.11.78.72.69.94.72.36.28.27.74.24.78.45;.87.52.11.78.72.69.94.72.36.28.27.74.24.78.45;.87.52.11.78.72.69.94.72.36.28.27.74.24.78.45;.87.52.11.78.72.69.94.72.36.28.27.74.24.78.45;.62.87.70.22.80.42.43.90.13.95.18.19.12.61.35;.48.20.42.16.43.58.69.03.34.72.15.24.29.30.75;威胁程度评估值 w=.47.97.76.62.48.77.33.74.54.65.43.35.63.66.57;第9页/共39页计算过程BaseV=crtbase(15,8);%创建初始矩阵Chrom=crtbp(NIND,BaseV)+ones(NIND,15);%初始种群ObjV=targetalloc(Chrom);%计算初始种群函数值while FitnV=ranking(-ObjV);%分配适应度值 SelCh=select(sus,Chrom,FitnV,GGAP);%选择 SelCh=recombin(xovsp,SelCh,0.7);%重组，交叉 f=rep(1;8,1,15);%复制矩阵 SelCh=mutbga(SelCh,f);%变异 SelCh=fix(SelCh);%fix(2.8)=2.0 ObjVSel=targetalloc(SelCh);%计算子代目标函数值 Chrom ObjV=reins(Chrom,SelCh,1,1,ObjV,ObjVSel);%重插入end第10页/共39页经过遗传迭代后，目标分配方案如下：（可能的一种方案）目标编号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15分配结果 1 7 7 1 7 1 1 7 2 7 1 3 8 1 8与此方案对应的总收益为6.4719注：最大遗传代数为MAXGEN=400，方能比较稳定地得到总收益值为6.4719。对于设计者而言，应该有一个估计的总收益值，如6.4。当计算结果大于估计值时就基本达到了目的，但并不一定是最优解。第11页/共39页三、函数讲解crtbase：创建长度为Lind的向量BaseV=crtbase(Lind,Base)如果Lind是向量，BaseV的长度为Lind的总长；如果Base也是一个长为Lind的向量，则BaseV是一组由Lind和基本字符Base的元素决定长度的基本字符组组成。当描述染色体结果的基因为基本字符时，最后一选项是有用的。举例：创建2个基数为6的基本字符0，1，2，3，4，5和3个基数为9的基本字符0，1，2，3，4，5，6，7，8的基本字符向量。BaseV=crtbase(2 3,6 9)BaseV=6 6 9 9 9第12页/共39页crtbp：创建一元素为随机数的种群矩阵Chrom,Lind,BaseV=crtbp(Nind,Lind)Chrom,Lind,BaseV=crtbp(Nind,BaseV)Chrom,Lind,BaseV=crtbp(Nind,Lind,Base)Chrom：染色体矩阵；Lind：长度；BaseV：基本字符。举例：创建一个长度为4有3个个体的种群Chrom,Lind,BaseV=crtbp(3,4,BaseV)得到：Chrom=0 0 1 0;1 0 1 1;0 1 0 1Lind=4;BaseV=2 2 2 2;第13页/共39页targetalloc：计算子代目标函数值并返回。ObjV=targetalloc(Chrom);首先生成初始种群：chrom=crtbp(NIND,BaseV)+ones(NIND,15);然后按火力点编号分配pij值：for i=1:m for j=1:15 chrom(i,j)=p(chrom(i,j),j);endend再计算目标值：eval=chrom*w;第15页/共39页ranking：基于排序的适应度分配。按照个体的目标值ObjV由小到大的顺序对它们进行排序，并返回一包含对应个体适应度值FitnV的列向量FitnV=ranking(ObjV)FitnV=ranking(ObjV,RFun)FitnV=ranking(ObjV,RFun,SUBPOP)举例：考虑具有10个体的种群，其当前目标值如下：ObjV=1 2 3 4 5 10 9 8 7 6。使用线性排序和压差为2，估算适应度值FitnV=ranking(ObjV)FitnV=2.00 1.7778 1.5556 1.3333 1.1111 0 0.2222 0.4444 0.6667 0.8889举例：使用RFun中的值估算适应度值RFun=3 5 7 10 14 18 25 30 40 50FitnV=ranking(ObjV,RFun)FitnV=50 40 30 25 3 5 7 10 14FitnV表明了每个个体被选择的预期概率。第16页/共39页select：（高级函数）从种群Chrom中选择个体返回到SelCh中。SelCh=select(SEL_F,Chrom,FitnV)SelCh=select(SEL_F,Chrom,FitnV,GGAP)SelCh=select(SEL_F,Chrom,FitnV,GGAP,SUBPOP)举例：chrom=1 11 21;2 12 22;3 13 23;4 14 24FitnV=1.2,0.3,0.9,0.7SelCh=select(sus,chrom,FitnV)SelCh=1 11 21;3 13 23;3 13 23;4 14 24概率最小的被淘汰了2 12 220.3sus：随机遍历抽样。按FitnV的值选择个体。第17页/共39页recombin：完成种群Chrom中个体的重组，在新种群NewChrom中返回重组后的个体。Chrom和NewChrom中的一行对应一个个体。NewChrom=recombin(REC_F,Chrom)NewChrom=recombin(REC_F,Chrom,RecOpt)NewChrom=recombin(REC_F,Chrom,RecOpt,SUBPOP)低级重组函数：xovsp单点交叉。Recdis离散重组。算法说明：recombin检测输入参数的一致性并调用低级重组函数。如果recombin调用时具有多个种群，则对每个子种群分别调用低级重组函数。举例：P81第18页/共39页rep：矩阵复制。Syntax:MatOut=rep(MatIn,REPN);Example:MatIn=1 2 3 REPN=1 2:MatOut=1 2 3 1 2 3 REPN=2 1:MatOut=1 2 3;1 2 3 REPN=3 2:MatOut=1 2 3 1 2 3;1 2 3 1 2 3;1 2 3 1 2 3第19页/共39页mutbga：对实值种群OldChrom，使用给定的概率，变异每一个变量，返回变异后的种群NewChrom。NewChrom=mutbga(OldChrom,FieldDR)NewChrom=mutbga(OldChrom,FieldDR,MutOpt)FieldDR是一个矩阵，包含每个变量的边界。MutOpt是一个可选向量，具有两个参数的最大值。举例：OldChrom=40.2381-17.1766 28.9530 15.3883;82.0642 13.2639 13.3596-9.0916;52.4396 25.6410 15.2014-2.5435FieldDR=-100-50-30-20;100 50 30 20mutbag产生一中间任务表MutMx，决定变异的变量，并为加入的delta所标识。如：MutMx=0 0 0 1;0 0-1 0;0 0-1-1delta=0.2500 0.2500 0.2500 0.2500;0.0001 0.0001 0.0001 0.0001;0.2505 0.2505 0.2505 0.2505NewChrom=mutbga(OldChrom,FieldDR,1/4 1.0)NewChrom=40.2381 -17.1766 28.9530 15.3849 94.5657 7.0131 13.3596 -9.0916 52.4030 25.6410 15.2014 -2.5435第20页/共39页fix：Round towards zero.FIX(X)rounds the elements of X to the nearest integers towards zero.Examp：fix(1.1)=1,fix(3.8)=8fix(1.3 2.6 4.9;2 4.4 6.9)ans=1 2 4 2 4 6第21页/共39页reins：完成插入子代到当前种群，用子代代替父代并返回结果种群，子代包含在矩阵SelCh中，父代在矩阵Chrom中，Chrom和SelCh中每一行对应一个个体。Chrom=reins(Chrom,SelCh)Chrom=reins(Chrom,SelCh,SUBPOP)Chrom=reins(Chrom,SelCh,SUBPOP,InsOpt,ObjVCh)Chrom=reins(Chrom,SelCh,SUBPOP,InsOpt,ObjVCh,ObjVSel)举例：ObjVCh=21;22;23;24;25;26;ObjVSel=31;32;Chrom=reins(Chrom,SelCh,1,1,ObjVCh);父代种群Chrom的目标值向量为ObjVCh，子代SelCh目标值向量为ObjVSel，基于适应度插入所有子代代替最不适应的父代个体。即：用31和32的个体代替25和26的个体。第22页/共39页四、改进的遗传算法问题：适应度值标定方式多种多样，不简洁、通用；早熟现象最难处理的关键问题；收敛较慢。七种改进的遗传算法分层遗传算法；自适应遗传算法；基于小生境技术的遗传算法；并行遗传算法；混合遗传算法：遗传算法与最速下降法相结合的混合遗传算法；遗传算法与模拟退火法相结合的混合遗传算法。第23页/共39页改进的遗传算法一在初始群体中，对所有个体按其适应度大小进行排序，然后计算个体的支持度和置信度；按一定的比例复制（将当前种群中适应度最高的两个个体结构完整地复制到待配种群中）；按个体所处的位置确定其变异概率并变异：按优良个体复制4份，劣质个体不复制的原则复制个体；从复制组中随机选择两个个体，对这两个个体进行多次交叉，从所得的结果中选择一个最优个体存入新群种；若满足结束条件，则停止；不然，跳转第1步，直至找到所有符合条件的规则。该算法的优点：进化过程中，子代总是保留了父代中最好的个体，保证了全局最优解。第24页/共39页改进的遗传算法二划分寻优空间设计空间退化寻优空间的移动第25页/共39页改进的遗传算法三交叉和变异算子的改进和协调采用：进化过程分为渐进和突变；动态变异；正交设计或均匀设计方法设计新的交叉和变异算子。采用与局部搜索算法相结合的混合遗传算法，解决局部搜索能力差的问题。采用有条件的替代父代的方法，解决单一的群体更新方式难以兼顾多样性和收敛性的问题。收敛速度慢的解决方法：产生好的初始群体；小生境技术；移民技术；自适应算子；与局部搜索结合的混合遗传算法；参数编码的动态模糊控制；进行未成熟收敛判断。第26页/共39页改进的遗传算法四适应度值的标定群体多样化第27页/共39页五、多目标优化中的遗传算法多目标优化的概念解决含有多目标和多约束的优化问题称为多目标优化问题。在实际应用中，工程优化问题大多数是多目标优化问题，有时需要使多个目标在给定区域上都可能地达到最优的问题，目标之间一般都是相互冲突的。例如投资问题，一般我们都是希望所投入的资金量最少，风险最小，并且所获得的收益最大。这种多于一个的数值目标的最优问题就是多目标优化问题。最优解和Pareto最优解。第28页/共39页多目标优化问题的遗传算法权重系数变换法并列选择法排列选择法共享函数法混合法第29页/共39页权重系数变换法对于一个多目标优化问题，若给其每个子目标函数 f(xi)(i=1,2,n)赋予权重wi，其中wi为相应的f(xi)在多目标优化问题中的重要程度，则各个子目标函数f(xi)的线性加权和表示为若将u作为多目标优化问题的评价函数，则多目标优化问题就可以转化为单目标优化问题，即可以利用单目标优化的遗传函数求解多目标优化问题。第30页/共39页并列选择法并列选择法的基本思想是，先将群体中的全部个体按子目标函数的数目均等地划分为一些子群体，对每个子群体分配一个子目标函数，各个子目标函数在相应的子群体中独立地进行选择运算，各自选择出一些适应度高的个体组成一个新的子群体，然后再将所有这些新生成的子群体合并成一个完整的群体，在这个群体中进行交叉和变异运算，从而生成下一代的完整群体，如此不断地进行“分割-并列选择-合并”操作，最终可求出多目标优化问题的Pareto最优解。第31页/共39页排列选择法排列选择法的基本思想是，基于Pareto最优个体，对群体中的各个个体进行排序，依据这个排列次序来进行进化过程中的选择运算，从而使得排在前面的Pareto最优个体将有更多的机会遗传到下一代群体中。如此这样经过一定代数的循环之后，最终就可求出多目标最优化问题的Pareto最优解。第32页/共39页共享函数法求解多目标最优化问题时，一般希望所得到的解能够尽可能地分散在整个Pareto最优解集合内，而不是集中在其Pareto最优解集合内的某一个较小的区域上。为达到这个要求，可以利用小生境遗传算法的技术来求解多目标最优化问题，这种方法称为共享函数法，它将共享函数的概念引入到求解多目标最优化问题的遗传算法中。小生境数的计算方法定义为：式中s(d)为共享函数，d(X,Y)为个体X,Y之间的海明距离。第33页/共39页混合法混合法的基本思想是，选择算子的主体使用并列选择法，然后通过引入保留最佳个体和共享函数的思想来弥补只使用并列选择法的不足之处。算法的主要过程为：并列选择过程 保留Pareto最优个体过程 共享函数处理过程第34页/共39页六、思考与学习药物配方研究中的最优组合方案算法设计：C 个体的编码方法：基因，染色体 E 个体适应度评价函数；P0 初始群体；T 遗传运算终止条件 （操作设计）M 群体大小；选择算子；交叉算子；（控制参数设定）变异算子；第35页/共39页浓度mg/L钉螺死亡率/%24h48h72h96h20253020253020253020253010.0012324638909660100100821001005.0010183826809432100100641001002.508121614488616100100401001001.2541216103276142610040681000.6252810830481216921636980.3125266482482042826100清水0200400062218不同浓度、温度、时间生物碱杀螺结果 第36页/共39页七、参考文献MATLAB 6.5 遗传算法工具箱及应用雷英杰主编MATLAB 6.5 应用接口编程飞思科技产品研发中心第38页/共39页感谢您的观看！第39页/共39页