MATLAB实验报告-遗传算法解最短路径以与函数最小值问题

硕士生考查课程考试试卷考试科目：MATLAB教程考生姓名：考生学号：学院：专业：考生成绩：任课老师(签名)考试日期：20年月日午时至时《MATLAB教程》试题：A、利用MATLAB设计遗传算法程序，寻找下图11个端点的最短路径，其中没有连接的端点表示没有路径。要求设计遗传算法对该问题求解。abcdefghijk121683179467294211B、设计遗传算法求解f(x)极小值，具体表达式如下：321231(,,)5.125.12,1,2,3iiifxxxxxi要求必须使用m函数方式设计程序。C、利用MATLAB编程实现：三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行，随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货，但是如何乘船渡河的大权掌握在商人手中，商人们怎样才能安全渡河？D、结合自己的研究方向选择合适的问题，利用MATLAB进行实验。以上四题任选一题进行实验，并写出实验报告。选择题目：A一、问题分析（10分）1234567891011121683179467294211如图如示，将节点编号，依次为1.2.3.4.5.6.7.8.9.10.11，由图论知识，则可写出其带权邻接矩阵为：02815005005005005005005002065001500500500500500500860750015005005005005001500705005009500500500500500150050003500250050050050050015003045006500500500500500950040500500150050050050050025005000750095005005005005006500701250050050050050050015001045005005005005005005009240注：为避免计算时无穷大数吃掉小数，此处为令inf=500。问题要求求出任意两点间的最短路径，Floyd算法采用的是在两点间尝试插入顶点，比较距离长短的方法。我思考后认为，用遗传算法很难找到一个可以统一表示最短路径的函数，但是可以对每一对点分别计算，然后加入for循环，可将相互之间的所有情况解出。观察本题可发现，所有节点都是可双向行走，则可只计算i到j的路径与距离，然后将矩阵按主对角线翻折即可得到全部数据。二、实验原理与数学模型（20分）实现原理为遗传算法原理：按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，使得适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。数学模型如下：设图G由非空点集合12{,...}nVVVV与边集合12{,...}mEeee组成，其中121221(,)e,P,)(P,P),iiiiiiiiePPEP且若（则G为一个有向图；又设ie的值为ia，12{,...},mAaaa故G可表示为一个三元组{,,}GPEA则求最短路径的数学模型可以描述为：1min*..niiiiiAEstAAEE实验具体：第一：编码与初始化因采用自然编码，且产生的编码不能重复，于是我采用了randperm函数产生不重复的随机自然数。因解题方法是使用的是计算每一对点，则我们编码时将第一个节点单独放入，合并成完整编码。因为节点有11个，可采用一个1行11列的矩阵储存数据，同时，由于编号为数字，可直接使用数字编码表示路径的染色体。具体如下：采用等长可变染色体的方式，例如由2到9的路径，染色体编码可能为（2，5，1，8，4，6，9，3，10，7，11），超过9之后的编码，用来进行算子的运算，不具备实际意义。第二：计算适应度，因取最短路径值，即最小值，常用方法为C-F(x)或C/F(x)（C为一常数），此处采用前一种方式。于是，可进一步计算相对适应度。第三：选择与复制采用轮盘赌算法，产生一个随机值，比较它与累计相对适应度的关系，从而选择出优良个体进入下一代。第四：交叉。因编码是不重复的数字，所以采用传统的交叉方法，即上一行与下一行对位交叉，会产生无效路径，于是，采用了不同的交叉方法，具体如下：（1）在表示路径的染色体Tx与Ty中，随机选取两个基因座（不能为起点基因座）i与j,即将i个基因座与第j个基因座之间的各个基因座定义为交叉域，并将交叉的内容分别记忆为temp1与temp2。（2）根据交叉区域中的映射关系，在个体Tx中找出所有与temp2相同的元素，在个体Ty中找出所有与temp1相同的元素，全部置为0。（3）将个体Tx、Ty进行循环左移，遇到0就删除，直到编码串中交叉区域的左端不再有0：然后将所有空位集中到交叉区域，而将交叉区域内原有的基因依次向后移动。因0元素可能较多，在程序实现时，我是将非零元素提出，后面再合成。（4）将temp2插入到Tx的交叉区域，temp1插入到Ty的交叉区域。形成新的染色体[1]。第五：变异染色体编码为从1到11的无重复编码，所以不能采用一般的生成一个随机数替代的办法。此处采用交换变异法。即随机产生两个数，交换两个节点的顺序。例：[1,2,3,4,5,6,7,8,9,10,11],13,28pKK则新染色体编码为：[1,2,8,4,5,6,7,3,9,10,11]p三、实验过程记录（含基本步骤、程序代码及异常情况记录等）（60分）首先，写程序，修复Bug。然后，调试种群数量，遗传代数，交叉概率，变异概率等，不断运行程序，以达到较理想的状态。有一次异常情况：算出来的最短距离均为0，最短路径没有终点出现，经过分析发现，因为交叉处的代码较复杂，弄错了一点，导致新基因有部分为非法基因。最后采用提出非零数值组成向量，再合成新基因的方式解决。Matlab程序代码如下：clc;clear;%初始化参数%注：popsize=200,MaxGeneration=100,约跑2分钟。若不要求太精确，可减少循环次数。pointnumber=11;%节点个数Popsize=200;%种群规模，只能取偶数（因67行的循环）MaxGeneration=100;%最大代数Pc=0.8;Pm=0.3;%交叉概率与变异概率A=[028150505050505050206501505050505050860750150505050501507050509505050505015050035025050505050150304506505050505095040505015050505050250500750950505050506507012505050505050150104505050505050509240];%带权邻接矩阵。A(A==50)=500;%取值50过小而修正为500；Bestindividual=zeros(MaxGeneration,1);outdistance=zeros(11,11);outpath=cell(11,11);%用于存放11个点相互之间的最短路径%******生成初始种群******fora=1:pointnumber%起点的编号%a=1;tempvary=[1234567891011];tempvary(a)=[];%暂时剔除起点tempmatrix=a*ones(Popsize,1);%将起点单独放一矩阵path=zeros(Popsize,pointnumber-1);%声明矩阵大小，避免减慢速度fori=1:Popsizetemprand=randperm(pointnumber-1);path(i,:)=tempvary(temprand(1:end));%生成一系列剔除起点的随机路线endpath=[tempmatrixpath];%合成包括起点的完整路线[row,col]=size(path);forb=a:pointnumber%终点的编号%b=10;fork=1:1:MaxGenerationfori=1:rowposition2=find(path(i,:)==b);%找出终点在路线中的位置pathlong(i)=0;forj=1:position2-1pathlong(i)=pathlong(i)+A(path(i,j),path(i,j+1));endend%计算适应度Fitness=length(A)*max(max(A))-pathlong;%因要求最小值，采且常数减函数值构造适应度Fitness=Fitness./sum(Fitness);%******Step1:选择最优个体******Bestindividual(k)=min(pathlong);[Orderfi,Indexfi]=sort(Fitness);%按照适应度大小排序Bestfi=Orderfi(Popsize);%Oderfi中最后一个即是最大的适应度BestS=path(Indexfi(Popsize),:);%记录每一代中最优个体的路线%******Step2:选择与复制操作******temppath=path;roulette=cumsum(Fitness);fori=1:PopsizetempP=rand(1);forj=1:length(roulette)iftempProulette(j)break;endendpath(i,:)=temppath(j,:);end%************Step3:交叉操作************temppath2=path;fori=1:2:rowtempP2=rand(1);if(tempP2rand(1))temPm2=fix((rand(1)+0.2)*10);%因起点基因不能改变temPm3=fix((rand(1)+0.2)*10);%随机取出两个位置为2到11基因座temPm4=min(temPm2,temPm3);temPm5=max(temPm2,temPm3);temp1=path(i,temPm4:temPm5);%将两点之间的基因储存，方便交叉temp2=path(i+1,temPm4:temPm5);[cd]=find(ismember(path(i,:),temp2));path(i,d)=0;%找出i行在i+1行取出区域中的数，置为0[ef]=find(ismember(path(i+1,:),temp1));path(i+1,f)=0;%找出i+1行在i行取出区域中的数，置为0[gh]=find(path(i,:)~=0);v1=path(i,h);%取出i行的非零元素，成一向量[lm]=find(path(i+1,:)~=0);v2=path(i+1,m);%取出i+1行的非零元素，成一向量path(i,:)=[v1(1:temPm4-1)temp2v1(temPm4-1+size(temp1):end)];path(i+1,:)=[v2(1:temPm4-1)temp1v2(temPm4-1+size(temp2):end)];%基因交叉endendpath(Popsize,:)=BestS;%************Step4:变异操作**************fori=1:PopsizetempPm=rand(1);if(tempPmPm)temPm6=fix((rand(1)+0.2)*10);temPm7=fix((rand(1)+0.2)*10);%产生两个用于交换的随机数tempvessel=path(i,temPm6);%交换前用一临时容器存放数据path(i,temPm6)=path(i,temPm7);path(i,temPm7)=tempvessel;%变异交换endendpath(Popsize,:)=BestS;end[aabb]=find(BestS==b);%找出终点Bestpath=BestS(1:bb);%剔除后面无用的点，留下实际路线outdi