自然计算报告

自然计算报告学院专业学号学生姓名授课老师遗传算法实验报告一、问题描述已知函数求函数的最大值及所对应的x1和x2的值。二、方法原理遗传算法：遗传算法是借鉴生物界自然选择和群体进化机制形成的一种全局寻优算法。与传统的优化算法相比，遗传算法具有如下优点：不是从单个点，而是从多个点构成的群体开始搜索；在搜索最优解过程中，只需要由目标函数值转换得来的适应值信息，而不需要导数等其它辅助信息；搜索过程不易陷入局部最优点。目前，该算法已渗透到许多领域，并成为解决各领域复杂问题的有力工具。在遗传算法中，将问题空间中的决策变量通过一定编码方法表示成遗传空间的一个个体，它是一个基因型串结构数据；同时，将目标函数值转换成适应值，它用来评价个体的优劣，并作为遗传操作的依据。遗传操作包括三个算子：选择、交叉和变异。选择用来实施适者生存的原则，即把当前群体中的个体按与适应值成比例的概率复制到新的群体中，构成交配池（当前代与下一代之间的中间群体）。选择算子的作用效果是提高了群体的平均适应值。由于选择算子没有产生新个体，所以群体中最好个体的适应值不会因选择操作而有所改进。交叉算子可以产生新的个体，它首先使从交配池中的个体随机配对，然后将两两配对的个体按某种方式相互交换部分基因。变异是对个体的某一个或某一些基因值按某一较小概率进行改变。从产生新个体的能力方面来说，交叉算子是产生新个体的主要方法，它决定了遗传算法的全局搜索能力；而变异算子只是产生新个体的辅助方法，但也必不可少，因为它决定了遗传算法的局部搜索能力。交叉和变异相配合，共同完成对搜索空间的全局和局部搜索。二、实现过程（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[pop,m]=geneformax%遗传算法%求解f(x1,x2)=21.5+x1*sin(4*pi*x1)+x2*sin(20*pi*x2)最大值%-3.0=x1=12.14.1=x2=5.8clc;clear%种群初始化N=100;%种群规模设定为100pop=[-3+15.1*rand(N,1)4.1+1.7*rand(N,1)];%第一列为染色体1对应自变量x1第二类为染色体2对应自变量x2rep=0;whilerep100value=21.5+pop(:,1).*sin(4*pi*pop(:,1))+pop(:,2).*sin(20*pi*pop(:,2));%计算种群的适应度%选择fori=1:90parents(i)=selectparents(value);end%交叉初始化子代fori=1:45temp=pop(parents(2*i-1),:)-pop(parents(2*i),:);child(2*i-1,:)=pop(parents(2*i),:)+1/3*temp;child(2*i,:)=pop(parents(2*i),:)+2/3*temp;end[v,ind]=sort(value,'descend');pop=[pop(ind(1:10),:);child];%变异对子代中适应度较大的值进行变异fori=6:10ifrand0.5pop(i,1)=pop(i,1)+rand(1)*0.05*sign(-0.5+rand(1));pop(i,2)=pop(i,2)+rand(1)*0.005*sign(-0.5+rand(1));endendrep=rep+1;m=max(value);figure(1);holdonplot(rep,m,'ko');end%选择函数使用轮盘法则functionselect=selectparents(value)r=rand(1);total=0;whiletotalsum(value)*rselect=ceil(100*rand(1));total=total+value(select);endendend%%%变异%有可能找到最大值，同时不能忽略的是，也有可能失去最优解%可以在保持种群个体中有足够多的最优解时，四、运行结果