遗传算法实例(参考)

遗传算法基础及应用实例湖南师范大学数学与计算机科学学院刘刚湖南师范大学计算机专业研究生课程一、遗传算法的基本知识•遗传算法（GeneticAlgorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。1975年遗传算法美国J.Holland教授具有内在的隐并行性和更好的全局寻优能力；直接对结构对象进行操作，不存在求导和函数连续性的限定采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的组成遗传算法可定义为一个8员组：SGA=(C,E,P0,M,Φ,Γ,Ψ,T)C——个体的编码方法；E——个体适应度评价函数；P0——初始群体；M——群体大小；Φ——选择算子；Γ——交叉算子；Ψ——变异算子；T——遗传运算终止条件。遗传算法思想•初始化群体；•计算群体上每个个体的适应度值；•按由个体适应度值所决定的某个规则选择将进入下一代的个体；•按概率Pc进行交叉操作；•按概率Pm进行突变操作；•没有满足某种停止条件，则转第(2)步，否则进入(7)。•输出种群中适应度值最优的染色体作为问题的满意解或最优解。遗传算法的优点•（1）遗传对所解的优化问题没有太多的数学要求，遗传算法可以处理任意形式的目标函数和约束，无论是线性的还是非线性的，离散的还是连续，甚至混合的搜索空间。•（2）进化算子的各态历经性使得遗传算法能够非常有效的进行概率意义下的全局搜索，而传统的优化方法是通过邻近点比较而转移到较好的点，从而达到收敛的局部搜索过程。•（3）遗传算法对于各种特殊问题可以提供极大的灵活性来混合构造领域独立的启发式，从而保证算法的有效性。遗传算法性能分析指标•（1）在线性性能评估在线性能表示为：TteetfTsX1)(1)(其中：T是进化代数；是第t代的平均适应度函数；表示到T代为止所有适应度函数值的平均性能。)(tfe在线指标用于说明算法的在线性能。)(sXe•（2）离线性性能评估离线性能表示为：TtetfTsXe1**)(1)(其中)(*tfe是第t代最好的个体的适应度函数值；)(*sXe表示至第T代每次最好的适应度函数值的平均。离线指标用于说明算法的收敛性。二、实例讲解•目标分配问题描述为：m个地空导弹火力单元对n批空袭目标进行目标分配。每批空袭用一个火力单元实施射击。•假设进行目标分配之前，各批目标的威胁程度与各火力单元对各批目标的射击有利程度已经经过评估和排序。•注：空袭批次可能因机型的不同，袭击方向的不同，袭击方式的不同，而不同。火力单元可能因导弹类型的不同，分布方位的不同，预警时间的不同，而不同。这些不同，导致了各批目标的威胁程度与各火力单元对各批目标的射击有利程度的不同。•第j批目标的威胁程度评估值为wj，第i个火力单元对第j批目标射击有利程度估计值为pij，令各火力单元对各批目标进行拦击的效益值为cij=wj×pij，其中cij表示对某批目标进行拦击我方获益大小程度。目标分配的目的是满足目标分配的基本原则，追求总体效益最佳，即求：•染色体采用十进制编码，每个基因表示为火力点的编号。染色体的长度由按目标批次编号顺序排列的火力单元分配编号组成，表示一种可能的分配方案。)max(1njijc•射击有利程度估计值（对每个定点测量后确定的）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];计算过程•BaseV=crtbase(15,8);%创建初始矩阵Chrom=crtbp(NIND,BaseV)+ones(NIND,15);%初始种群ObjV=targetalloc(Chrom);%计算初始种群函数值whileFitnV=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.0ObjVSel=targetalloc(SelCh);%计算子代目标函数值[ChromObjV]=reins(Chrom,SelCh,1,1,ObjV,ObjVSel);%重插入end•经过遗传迭代后，目标分配方案如下：（可能的一种方案）目标编号123456789101112131415分配结果177171172713818•与此方案对应的总收益为6.4719•注：最大遗传代数为MAXGEN=400，方能比较稳定地得到总收益值为6.4719。对于设计者而言，应该有一个估计的总收益值，如＞6.4。当计算结果大于估计值时就基本达到了目的，但并不一定是最优解。三、函数讲解•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([23],[69])BaseV=[66999]•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=[0010;1011;0101]Lind=4;BaseV=[2222];•targetalloc：计算子代目标函数值并返回。•ObjV=targetalloc(Chrom);首先生成初始种群：chrom=crtbp(NIND,BaseV)+ones(NIND,15);然后按火力点编号分配pij值：fori=1:mforj=1:15chrom(i,j)=p(chrom(i,j),j);endend再计算目标值：eval=chrom*w';•ranking：基于排序的适应度分配。按照个体的目标值ObjV由小到大的顺序对它们进行排序，并返回一包含对应个体适应度值FitnV的列向量FitnV=ranking(ObjV)FitnV=ranking(ObjV,RFun)FitnV=ranking(ObjV,RFun,SUBPOP)•举例：考虑具有10个体的种群，其当前目标值如下：ObjV=[12345109876]‘。使用线性排序和压差为2，估算适应度值FitnV=ranking(ObjV)FitnV=[2.001.77781.55561.33331.111100.22220.44440.66670.8889]’•举例：使用RFun中的值估算适应度值RFun=[35710141825304050]’FitnV=ranking(ObjV,RFun)FitnV=[504030253571014]’•FitnV表明了每个个体被选择的预期概率。•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=[11121;21222;31323;41424]FitnV=[1.2,0.3,0.9,0.7]‘SelCh=select('sus',chrom,FitnV)SelCh=[11121;31323;31323;41424]•概率最小的被淘汰了——[21222]0.3•sus：随机遍历抽样。按FitnV的值选择个体。•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•rep：矩阵复制。Syntax:MatOut=rep(MatIn,REPN);•Example:•MatIn=[123]•REPN=[12]:MatOut=[123123]•REPN=[21]:MatOut=[123;•123]•REPN=[32]:MatOut=[123123;•123123;•123123]•mutbga：对实值种群OldChrom，使用给定的概率，变异每一个变量，返回变异后的种群NewChrom。NewChrom=mutbga(OldChrom,FieldDR)NewChrom=mutbga(OldChrom,FieldDR,MutOpt)FieldDR是一个矩阵，包含每个变量的边界。MutOpt是一个可选向量，具有两个参数的最大值。•举例：OldChrom=[40.2381-17.176628.953015.3883;82.064213.263913.3596-9.0916;52.439625.641015.2014-2.5435]FieldDR=[-100-50-30-20;100503020]mutbag产生一中间任务表MutMx，决定变异的变量，并为加入的delta所标识。如：MutMx=[0001;00-10;00-1-1]delta=[0.25000.25000.25000.2500;0.00010.00010.00010.0001;0.25050.25050.25050.2505]NewChrom=mutbga(OldChrom,FieldDR,[1/41.0])NewChrom=[40.2381-17.176628.953015.384994.56577.013113.3596-9.091652.403025.641015.2014-2.5435]•fix：Roundtowardszero.FIX(X)roundstheelementsofXtothenearestintegerstowardszero.•Examp：fix(1.1)=1,fix(3.8)=8fix([1.