MATLAB课程遗传算法实验报告及源代码

硕士生考查课程考试试卷考试科目：MATLAB教程考生姓名：张宜龙考生学号：2130120033学院：管理学院专业：管理科学与工程考生成绩：任课老师(签名)考试日期：年月日午时至时《MATLAB教程》试题：A、利用MATLAB设计遗传算法程序，寻找下图11个端点的最短路径，其中没有连接的端点表示没有路径。要求设计遗传算法对该问题求解。B、设计遗传算法求解f(x)极小值，具体表达式如下：要求必须使用m函数方式设计程序。C、利用MATLAB编程实现：三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行，随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货，但是如何乘船渡河的大权掌握在商人手中，商人们怎样才能安全渡河？D、结合自己的研究方向选择合适的问题，利用MATLAB进行实验。以上四题任选一题进行实验，并写出实验报告。选择题目：B、设计遗传算法求解f(x)极小值，具体表达式如下：要求必须使用m函数方式设计程序。一、问题分析（10分）这是一个简单的三元函数求最小值的函数优化问题，可以利用遗传算法来指导性搜索最小值。实验要求必须以matlab为工具，利用遗传算法对问题进行求解。在本实验中，要求我们用M函数自行设计遗传算法，通过遗传算法基本原理，选择、交叉、变异等操作进行指导性邻域搜索，得到最优解。实验原理与数学模型（20分）（1）试验原理：用遗传算法求解函数优化问题，遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。其采纳了自然进化模型，从代表问题可能潜在解集的一个种群开始，种群由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体；初始种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的解：在每一代，概据问题域中个体的适应度大小挑选个体；并借助遗传算子进行组合交叉和主客观变异，产生出代表新的解集的种群。这一过程循环执行，直到满足优化准则为止。最后，末代个体经解码，生成近似最优解。基于种群进化机制的遗传算法如同自然界进化一样，后生代种群比前生代更加适应于环境，通过逐代进化，逼近最优解。遗传算法是一种现代智能算法，实际上它的功能十分强大，能够用于求解一些难以用常规数学手段进行求解的问题，尤其适用于求解多目标、多约束，且目标函数形式非常复杂的优化问题。但是遗传算法也有一些缺点，最为关键的一点，即没有任何理论能够证明遗传算法一定能够找到最优解，算法主要是根据概率论的思想来寻找最优解。因此，遗传算法所得到的解只是一个近似解，而不一定是最优解。（2）数学模型对于求解该问题遗传算法的构造过程：（1）确定决策变量和约束条件；（2）建立优化模型；（3）确定编码方法：用2个实数分别表示两个决策变量，分别将的定义域离散化为从离散点-5.12到离散点5.12的Size个实数。（4）确定个体评价方法：个体的适应度直接取为对应的目标函数值，即设计遗传算子：选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变异算子（6）确定遗传算法的运行参数：群体大小M=500，终止进化代数G=200，交叉概率Pc=0.90，采用自适应变异概率即变异概率与适应度有关，适应度越小，变异概率越大。简化数学模型：基本遗传算法可定义为一个7元组：GA＝(M,F,s,c,m,pc,pm)M——群体大小；F——个体适应度评价函数；s——选择操作算于；c——交叉操作算子：m——变异操作算于；pc——交叉概率；pm——变异概率；三、实验过程记录（含基本步骤、程序代码及异常情况记录等）（60分）=================================================================基本步骤：第一步：确定决策变量及各种约束条件，即确定出个体的表现型X和问题的解空间；第二步：建立优化模型，即确定出目标函数的类型及数学描述形式或量化方法；第三步：确定表示可行解的染色体编码方法，即确定出个体的基因型x及遗传算法的搜索空间；第四步：确定解码方法，即确定出由个体基因型x到个体表现型X的对应关系或转换方法；第五步：确定个体适应度的量化评价方法，即确定出由目标函数值到个体适应度的转换规则；第六步：设计遗传算子，即确定选择运算、交叉运算、变异运算等遗传算子的具体操作方法。第七步：确定遗传算法的有关运行参数，即M,G,Pc,Pm等参数。=================================================================程序代码：程序1：主程序%%程序源代码%%主程序：用遗传算法求解函数优化问题。函数名称存储为main.m%%清空环境clcclear%%遗传算法参数maxgen=30;%进化代数sizepop=100;%种群规模pcross=[0.6];%交叉概率pmutation=[0.01];%变异概率lenchrom=[111];%变量字串长度bound=[-5.125.12;-5.125.12;-5.125.12];%变量范围%%个体初始化individuals=struct('fitness',zeros(1,sizepop),'chrom',[]);%个体avgfitness=[];%种群平均适应度bestfitness=[];%种群最佳适应度bestchrom=[];%适应度最好染色体%初始化种群fori=1:sizepopindividuals.chrom(i,:)=Code(lenchrom,bound);%随机产生个体x=individuals.chrom(i,:);individuals.fitness(i)=fun(x);%个体适应度end%找最好的染色体[bestfitnessbestindex]=min(individuals.fitness);bestchrom=individuals.chrom(bestindex,:);%最好的染色体avgfitness=sum(individuals.fitness)/sizepop;%染色体的平均适应度%记录每一代进化中最好的适应度和平均适应度trace=[];%%进化开始fori=1:maxgen%选择操作individuals=Select(individuals,sizepop);avgfitness=sum(individuals.fitness)/sizepop;%交叉操作individuals.chrom=Cross(pcross,lenchrom,individuals.chrom,sizepop,bound);%变异操作individuals.chrom=Mutation(pmutation,lenchrom,individuals.chrom,sizepop,[imaxgen],bound);%计算适应度forj=1:sizepopx=individuals.chrom(j,:);individuals.fitness(j)=fun(x);end%找到最小和最大适应度的染色体及它们在种群中的位置[newbestfitness,newbestindex]=min(individuals.fitness);[worestfitness,worestindex]=max(individuals.fitness);%代替上一次进化中最好的染色体ifbestfitness>newbestfitnessbestfitness=newbestfitness;bestchrom=individuals.chrom(newbestindex,:);endindividuals.chrom(worestindex,:)=bestchrom;individuals.fitness(worestindex)=bestfitness;avgfitness=sum(individuals.fitness)/sizepop;trace=[trace;avgfitnessbestfitness];%记录每一代进化中最好的适应度%和平均适应度end%进化结束%%结果显示figure[rc]=size(trace);plot([1:r]',trace(:,1),'r-',[1:r]',trace(:,2),'b-');title(['函数值曲线''终止代数＝'num2str(maxgen)],'fontsize',12);xlabel('进化代数','fontsize',12);ylabel('函数值','fontsize',12);legend('各代平均值','各代最佳值','fontsize',12);%窗口显示bestfitnessbestpop=xgridon=================================================================程序2：将编码编码成染色体%子程序：编码操作，函数名称存储为code.mfunctionret=Code(lenchrom,bound)%本函数将变量编码成染色体，用于随机初始化一个种群%lenchrominput:染色体长度%boundinput:变量的取值范围%retoutput:染色体的编码值flag=0;whileflag==0pick=rand(1,length(lenchrom));ret=bound(:,1)'+(bound(:,2)-bound(:,1))'.*pick;%线性插值flag=test(lenchrom,bound,ret);%检验染色体的可行性end=================================================================程序3：测试操作%子程序：测试操作，函数名称存储为test.mfunctionflag=test(lenchrom,bound,code)%lenchrominput:染色体长度%boundinput:变量的取值范围%codeoutput:染色体的编码值flag=1;[n,m]=size(code);fori=1:nifcode(i)<bound(i,1)||code(i)>bound(i,2)flag=0;endend=================================================================程序4：对每一代种群进行选择%子程序：选择操作，函数名称存储为Select.mfunctionret=Select(individuals,sizepop)%本函数对每一代种群中的染色体进行选择，以进行后面的交叉和变异%individualsinput:种群信息%sizepopinput:种群规模%optsinput:选择方法的选择%retoutput:经过选择后的种群individuals.fitness=1./(individuals.fitness);sumfitness=sum(individuals.fitness);sumf=individuals.fitness./sumfitness;index=[];fori=1:sizepop%转sizepop次轮盘pick=rand;whilepick==0pick=rand;endforj=1:sizepoppick=pick-sumf(j);ifpick<0index=[indexj];break;%寻找落入的区间，此次转轮盘选中了染色体i；%注意：在转sizepop次轮盘的过程中，有可能会重复选择某些染色体。endendindividuals.chrom=individuals.chrom(index,:);individuals.fitness=individuals.fitness(index);ret=individuals;=================================================================程序5：变异%子程序：变异操作，函数名称存储为Mutation.mfunctionret=Mutation(pmutation,lenchrom,chrom,sizepop,pop,bound)%本函数完成变异操作%pcorssinput:变异概率%lenchrominput:染色体长度%chrominput:染色体群%sizepopinput:种群规模%popinput:当前种群的进化代数和最大的进化代数信息%retoutput:变异后的染色体fori=1:sizepop%随机选择一个染色体进行变异pick=rand;whilepick==0pick=rand;endindex=ceil(pick*sizepop);%变异概率决定该轮循环是否进行变异pick=rand;ifpick>pmutationcontinue;endflag=0;whileflag==0%变异位置pick=rand;whilepick==0pick=rand;endpos=ceil(pick*sum(lenchrom));%随机选择了染色体变异的位置，即选择了第pos个变量进行变异v=chrom(i,pos);v1=v-bound(pos,1);v2=bound(pos,2)-v;pick=rand;%变异开始ifpick>0.5delta=v2*(1-pick^((1-pop(1)/pop(2))^2));chrom(i,pos)=v+delta;elsedelta=v1*(1-pick^((1-pop(1)/pop(2))^2));chrom(i,pos)=v-delta;end%变异结束flag=test(lenchrom,bound,chrom(i,:));%检验染色体的可行性endendret=chrom;=================================================================程序6：交叉%子程序：新种群交叉操作，函数名称存储为cross.mfunctionret=Cross(pcross,lenchrom,chrom,sizepop,bound)%本函数完成交叉操作%pcorssinput:交叉概率%lenchrominput:染色体的长度%chrominput:染色体群%sizepopinput:种群规模%retoutput:交叉后的染色体fori=1:sizepop%随机选择两个染色体进行交叉pick=rand(1,2);whileprod(pick)==0pick=rand(1,2);endindex=ceil(pick.*sizepop);%交叉概率决定是否进行交叉pick=rand;whilepick==0pick=rand;endifpick>pcrosscontinue;endflag=0;whileflag==0%随机选择交叉位置pick=rand;whilepick==0pick=rand;endpos=ceil(pick.*sum(lenchrom));%随机选择进行交叉的位置，即选择第几个变量进行交叉，注意：两个染色体交叉的位置相同pick=rand;%交叉开始v1=chrom(index(1),pos);v2=chrom(index(2),pos);chrom(index(1),pos)=pick*v2+(1-pick)*v1;chrom(index(2),pos)=pick*v1+(1-pick)*v2;%交叉结束flag1=test(lenchrom,bound,chrom(index(1),:));%检验染色体1的可行性flag2=test(lenchrom,bound,chrom(index(2),:));%检验染色体2的可行性ifflag1*flag2==0flag=0;elseflag=1;end%如果两个染色体不是都可行，则重新交叉endendret=chrom;=================================================================程序7：目标函数%子程序：目标函数，函数名称存储为fun.mfunctiony=fun(x)y=x(1)^2+x(2)^2+x(3)^2;=================================================================异常情况记录：在运用matlab编写程序进行运算时，遇到了一些问题，如下：（1）经常出现警告提示：Warning:Ignoringextralegendentries.>Inlegendat294Inmainat72Inrunat57（2）由于本实验包括7个程序，每个程序当中都有许多的变量名。由于程序中有些变量的名字特别长，因此在引用时总会因为输出其中某一个字母而在运行时出错。这当然可以通过修改得以更正，不过也提醒我以后在对变量名进行命名时不要使用过长的变量名。（3）本实验在编写过程中遇到的最大一个问题是，在编写完程序，进行运算时，matlab很久都没有反应，然后在下方的窗口中一直显示“busy”。刚开始我以为是由于遗传代数过多、染色体长度太长导致运行时间过久。于是我等了一会，可是过了很久结果还是没有运行出来。我强制关掉程序，仔细的检查了代码，并没有发现错误，可再次运行时还是出现同样的问题，运算不出结果。最后我设置了一些断点，也就是去掉一些分号，让中间结果输出到命令窗口。运行后发现命令窗口中一直在不停的输出中间结果。按“Ctrl+c”暂停之后，我知道程序中可能出现了死循环。于是在有循环的语句中去找错误，结果发现主程序中的counter=counter+1这一条语句没有写进去，致使循环无法结束。问题最终得以解决。由于粗心我花了好大功夫去寻找错误，这是一个教训，也是一次收获，下次再遇到这种情况我不会再犯类似的错误了。=================================================================四、实验结果与总结（10分）=================================================================试验结果：一：在初始设置为如下情况时：maxgen=30;%进化代数sizepop=100;%种群规模pcross=[0.6];%交叉概率pmutation=[0.01];%变异概率lenchrom=[111];%变量字串长度运行程序5次结果为：（1）bestfitness=7.9536e-004bestpop=0.0043-0.0282-0.0074（2）bestfitness=0.0059bestpop=-0.02660.04140.0656（3）bestfitness=2.0056e-005bestpop=-0.0002-0.00040.0046（4）bestfitness=8.0669e-004bestpop=0.01160.0251-0.0072（5）bestfitness=0.0019bestpop=0.0512-0.00750.0210根据以上5次运行，不难发现每次运行结果都不同，这是由于遗传算法本质上是一种启发式的随机搜索算法。然后对参数进行调整，使进一步优化结果。=================================================================二：修改参数设置，优化算法：maxgen=5000;%进化代数sizepop=120;%种群规模pcross=[0.001];%交叉概率pmutation=[0.1];%变异概率lenchrom=[111];%变量字串长度bound=[-5.125.12;-5.125.12;-5.125.12];%变量范围（1）bestfitness=0.0161bestpop=-0.0013-0.0011-0.1270（2）bestfitness=0.0697bestpop=0.00000.00000.2641（3）bestfitness=0.0316bestpop=-0.0004-0.00000.1779（4）bestfitness=0.0967bestpop=-0.0010-0.00050.3109（5）bestfitness=0.0374bestpop=-0.0000-0.00030.1934从上面的结果发现，将进化代数调整到5000次，得到的结果还没有得到实质性的优化，所以把焦点放到交叉概率和变异概率，进一步修改。=================================================================三：修改参数设置，优化算法：maxgen=120;%进化代数sizepo