遗传算法实验报告泽

遗传算法实验报告岸」一、问题描述已知函数f(x)=x3-60x2+900x+100,X[0,35]，求函数的最大值。上图为函数f(x)=x3-60x2+900x+100在X[0,35]区间上的曲线图像。可以看出，该函数有多个极值点，如果使用其他的搜寻方法，很容易陷入局部最小点，而不能搜寻到真正的全局最小点，遗传算法具有通用、并行、稳健、简单与全局优化能力强等突出优点，适用于解决这种全局优化问题。二、方法原理遗传算法：遗传算法是借鉴生物界自然选择和群体进化机制形成的一种全局寻优算法。与传统的优化算法相比，遗传算法具有如下优点：不是从单个点，而是从多个点构成的群体开始搜索；在搜索最优解过程中，只需要由目标函数值转换得来的适应值信息，而不需要导数等其它辅助信息；搜索过程不易陷入局部最优点。目前，该算法已渗透到许多领域，并成为解决各领域复杂问题的有力工具。在遗传算法中，将问题空间中的决策变量通过一定编码方法表示成遗传空间的一个个体，它是一个基因型串结构数据；同时，将目标函数值转换成适应值，它用来评价个体的优劣，并作为遗传操作的依据。遗传操作包括三个算子：选择、交叉和变异。选择用来实施适者生存的原则，即把当前群体中的个体按与适应值成比例的概率复制到新的群体中，构成交配池(当前代与下一代之间的中间群体)。选择算子的作用效果是提高了群体的平均适应值。由于选择算子没有产生新个体，所以群体中最好个体的适应值不会因选择操作而有所改进。交叉算子可以产生新的个体，它首先使从交配池中的个体随机配对，然后将两两配对的个体按某种方式相互交换部分基因。变异是对个体的某一个或某一些基因值按某一较小概率进行改变。从产生新个体的能力方面来说，交叉算子是产生新个体的主要方法，它决定了遗传算法的全局搜索能力;而变异算子只是产生新个体的辅助方法，但也必不可少，因为它决定了遗传算法的局部搜索能力。交叉和变异相配合，共同完成对搜索空间的全局和局部搜索。三、 实现过程（1） 编码：使用二进制编码，随机产生一个初始种群。L表示编码长度，通常由对问题的求解精度决定，编码长度L越长，可期望的最优解的精度也就越高，过大的L会增大运算量。（2） 生成初始群体：种群规模表示每一代种群中所含个体数目。随机产生N个初始串结构数据，每个串结构数据成为一个个体，N个个体组成一个初始群体，N表示种群规模的大小。当N取值较小时，可提高遗传算法的运算速度，但却降低种群的多样性，容易引起遗传算法早熟，出现假收敛；而N当取值较大时，又会使得遗传算法效率降低。一般建议的取值范围是20—100。遗传算法以该群体作为初始迭代点；（3） 适应度检测：根据实际标准计算个体的适应度，评判个体的优劣，即该个体所代表的可行解的优劣。本例中适应度即为所求的目标函数；（4） 选择：从当前群体中选择优良（适应度高的）个体，使它们有机会被选中进入下一次迭代过程，舍弃适应度低的个体。本例中采用轮盘赌的选择方法，即个体被选择的几率与其适应度值大小成正比；（5） 交叉：遗传操作，根据设置的交叉概率对交配池中个体进行基因交叉操作，形成新一代的种群，新一代中间个体的信息来自父辈个体，体现了信息交换的原则。交叉概率控制着交叉操作的频率，由于交叉操作是遗传算法中产生新个体的主要方法，所以交叉概率通常应取较大值；但若过大的话，又可能破坏群体的优良模式。一般取0.4到0.99。（6） 变异：随机选择中间群体中的某个个体，以变异概率大小改变个体某位基因的值。变异为产生新个体提供了机会。变异概率也是影响新个体产生的一个因素，变异概率小，产生新个体少；变异概率太大，又会使遗传算法变成随机搜索。一般取变异概率为0.0001—0.1。（7） 终止进化代数。本例中规定遗传代数的收敛判据，根据设置好的进化代数，搜索到规定代数后自动停止。四、 具体代码（一）主函数function[xv,fv]=GA（fitness,a,b,NP,NG,pc,pm,eps）%待优化的目标函数:fitness%自变量下界:a%自变量上界:b%种群个体数:NP%最大进化代数:NG%杂交概率:pc%自变量概率:pm%自变量离散精度:eps%目标函数取最小值时的自变量值：xm%目标函数的最小值:fvL=ceil（log2（（b-a）/eps+1））; %根据离散精度，确定二进制编码需要的码长x=zeros（NP,L）;fori=1:NPx（i,:）=Initial（L）;%种群初始化fx(i)=fitness(Dec(a,b,x(i,:),L));%个体适应值endfork=1:NGsumfx=sum(fx); %所有个体适应值之和px=fx/sumfx; %所有个体适应值的平均值ppx=0;ppx(1)=px(1);fori=2:NP %用于轮盘赌策略的累加ppx(i)=ppx(i-1)+px(i);endfori=1:NPsita=rand();forn=1:NPifsita<=ppx(n)SelFather=n;%根据轮盘赌策略确定的父亲break;endendSelmother=floor(rand()*(NP-1))+1;%随机选择母亲posCut=floor(rand()*(L-2))+1; %随机选择交叉点r1=rand();ifr1<=pc %交叉nx(i,1:posCut)=x(SelFather,1:posCut);nx(i,(posCut+1):L)=x(Selmother,(posCut+1):L);r2=rand();ifr2<=pm %变异posMut=round(rand()*(L-1)+1);nx(i,posMut)=~nx(i,posMut);endelsenx(i,:)=x(SelFather,:);endendx=nx;fori=1:NPfx(i)=fitness(Dec(a,b,x(i,:),L));%子代适应值endendfv=-inf;fori=1:NPfitx=fitness(Dec(a,b,x(i,:),L));iffitx>fvfv=fitx; %取个体中的最好值作为最终结果xv=Dec(a,b,x(i,:),L);endend初始化代码functionresult=Initial(length) %初始化函数fori=1:lengthr=rand();result(i)=round(r);end编码functiony=Dec(a,b,x,L)%二进制编码转换为十进制编码base=2.”((LT):T:0);y=dot(base,x);y=a+y*(b-a)/(2”L-1);适应度函数functionF=fitness(x)F=x"3-60*x"2+900*x+100;运行结果在命令窗口输入：[xv,fv]=GA(@fitness,0,35,100,500,0.9,0.04,0.01)即可得出结果：xv=9.9744fv=4100五、结果分析运行结果显示，该函数在xv=10附近取得最大值，从函数图象可以看出，该运行结果基本正确。但是，本例中采用了赌轮选择法，选择算子随即操作，误差比较大，适应度最高的个体只是被选中的几率大，但也会出现适应度最高的个体不被选中的情况，从而出现适应度低的个体有由于机会被选中，被选中的个体将复制到下一代，从而造成误差。当运算目标函数阶次较低时(如本例)，采用适当的进化代数可以得到相对合理的结果，但当目标函数比较复杂时候，该算法不再有效。例如，将目标函数设置为F=x"4-5*x