![MATLAB实验报告-遗传算法解最短路径以及函数最小值问题_第1页](http://file1.renrendoc.com/fileroot_temp2/2020-4/27/5e79974f-609b-4b95-9c9f-1776c1020a0a/5e79974f-609b-4b95-9c9f-1776c1020a0a1.gif)
![MATLAB实验报告-遗传算法解最短路径以及函数最小值问题_第2页](http://file1.renrendoc.com/fileroot_temp2/2020-4/27/5e79974f-609b-4b95-9c9f-1776c1020a0a/5e79974f-609b-4b95-9c9f-1776c1020a0a2.gif)
![MATLAB实验报告-遗传算法解最短路径以及函数最小值问题_第3页](http://file1.renrendoc.com/fileroot_temp2/2020-4/27/5e79974f-609b-4b95-9c9f-1776c1020a0a/5e79974f-609b-4b95-9c9f-1776c1020a0a3.gif)
![MATLAB实验报告-遗传算法解最短路径以及函数最小值问题_第4页](http://file1.renrendoc.com/fileroot_temp2/2020-4/27/5e79974f-609b-4b95-9c9f-1776c1020a0a/5e79974f-609b-4b95-9c9f-1776c1020a0a4.gif)
![MATLAB实验报告-遗传算法解最短路径以及函数最小值问题_第5页](http://file1.renrendoc.com/fileroot_temp2/2020-4/27/5e79974f-609b-4b95-9c9f-1776c1020a0a/5e79974f-609b-4b95-9c9f-1776c1020a0a5.gif)
已阅读5页,还剩6页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
精品文档硕士生考查课程考试试卷考试科目: MATLAB教程 考生姓名: 考生学号: 学 院: 专 业: 考 生 成 绩: 任课老师 (签名) 考试日期:20 年 月 日 午 时至 时11欢迎下载11欢迎下载11欢迎下载。MATLAB教程试题:A、利用MATLAB设计遗传算法程序,寻找下图11个端点的最短路径,其中没有连接的端点表示没有路径。要求设计遗传算法对该问题求解。B、设计遗传算法求解f(x)极小值,具体表达式如下:要求必须使用m函数方式设计程序。C、利用MATLAB编程实现:三名商人各带一个随从乘船渡河,一只小船只能容纳二人,由他们自己划行,随从们密约,在河的任一岸,一旦随从的人数比商人多,就杀人越货,但是如何乘船渡河的大权掌握在商人手中,商人们怎样才能安全渡河?D、结合自己的研究方向选择合适的问题,利用MATLAB进行实验。以上四题任选一题进行实验,并写出实验报告。选择题目: A 一、问题分析(10分)如图如示,将节点编号,依次为1.2.3.4.5.6.7.8.9.10.11,由图论知识,则可写出其带权邻接矩阵为: 0 2 8 1 500 500 500 500 500 500 500 2 0 6 500 1 500 500 500 500 500 500 8 6 0 7 500 1 500 500 500 500 500 1 500 7 0 500 500 9 500 500 500 500 500 1 500 500 0 3 500 2 500 500 500 500 500 1 500 3 0 4 500 6 500 500 500 500 500 9 500 4 0 500 500 1 500 500 500 500 500 2 500 500 0 7 500 9 500 500 500 500 500 6 500 7 0 1 2 500 500 500 500 500 500 1 500 1 0 4 500 500 500 500 500 500 500 9 2 4 0注:为避免计算时无穷大数吃掉小数,此处为令inf=500。问题要求求出任意两点间的最短路径,Floyd算法采用的是在两点间尝试插入顶点,比较距离长短的方法。我思考后认为,用遗传算法很难找到一个可以统一表示最短路径的函数,但是可以对每一对点分别计算,然后加入for循环,可将相互之间的所有情况解出。观察本题可发现,所有节点都是可双向行走,则可只计算i到j的路径与距离,然后将矩阵按主对角线翻折即可得到全部数据。二、实验原理与数学模型(20分)实现原理为遗传算法原理:按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选,使得适应度高的个体被保留下来,组成新的群体,新的群体既继承了上一代的信息,又优于上一代。这样周而复始,群体中个体适应度不断提高,直到满足一定的条件。数学模型如下: 设图 由非空点集合 和边集合 组成,其中 又设 的值为 , 故 可表示为一个三元组则求最短路径的数学模型可以描述为:实验具体:第一:编码与初始化因采用自然编码,且产生的编码不能重复,于是我采用了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的无重复编码,所以不能采用一般的生成一个随机数替代的办法。此处采用交换变异法。即随机产生两个数,交换两个节点的顺序。例: 则新染色体编码为:三、实验过程记录(含基本步骤、程序代码及异常情况记录等)(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=0 2 8 1 50 50 50 50 50 50 50 2 0 6 50 1 50 50 50 50 50 50 8 6 0 7 50 1 50 50 50 50 50 1 50 7 0 50 50 9 50 50 50 50 50 1 50 50 0 3 50 2 50 50 50 50 50 1 50 3 0 4 50 6 50 50 50 50 50 9 50 4 0 50 50 1 50 50 50 50 50 2 50 50 0 7 50 9 50 50 50 50 50 6 50 7 0 1 2 50 50 50 50 50 50 1 50 1 0 4 50 50 50 50 50 50 50 9 2 4 0; %带权邻接矩阵。A(A=50)=500; %取值50过小而修正为500;Bestindividual=zeros(MaxGeneration,1);outdistance=zeros(11,11);outpath=cell(11,11); %用于存放11个点相互之间的最短路径%* 生成初始种群 *for a=1:pointnumber %起点的编号%a=1; tempvary=1 2 3 4 5 6 7 8 9 10 11;tempvary(a)=; %暂时剔除起点tempmatrix=a*ones(Popsize,1); %将起点单独放一矩阵path=zeros(Popsize,pointnumber-1); %声明矩阵大小,避免减慢速度for i=1:Popsize temprand=randperm(pointnumber-1); path(i,:)=tempvary(temprand(1:end); %生成一系列剔除起点的随机路线endpath=tempmatrix path; %合成包括起点的完整路线row,col=size(path);for b=a:pointnumber %终点的编号%b=10;for k=1:1:MaxGeneration for i=1:row position2=find(path(i,:)=b); %找出终点在路线中的位置 pathlong(i)=0; for j=1:position2-1 pathlong(i)=pathlong(i)+A(path(i,j),path(i,j+1); end end %计算适应度 Fitness=length(A)*max(max(A)-pathlong; %因要求最小值,采且常数减函数值构造适应度 Fitness=Fitness./sum(Fitness); %* Step 1 : 选择最优个体 * Bestindividual(k)=min(pathlong); Orderfi,Indexfi=sort(Fitness); %按照适应度大小排序 Bestfi=Orderfi(Popsize); %Oderfi中最后一个即是最大的适应度 BestS=path(Indexfi(Popsize),:); %记录每一代中最优个体的路线 %* Step 2 : 选择与复制操作* temppath=path; roulette=cumsum(Fitness); for i=1:Popsize tempP=rand(1); for j=1:length(roulette) if tempProulette(j) break; end end path(i,:)=temppath(j,:); end %* Step 3 : 交叉操作 * temppath2=path; for i=1:2:row tempP2=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); c d=find(ismember(path(i,:),temp2); path(i,d)=0; %找出i行在i+1行取出区域中的数,置为0 e f=find(ismember(path(i+1,:),temp1); path(i+1,f)=0; %找出i+1行在i行取出区域中的数,置为0 g h=find(path(i,:)=0); v1=path(i,h); %取出i行的非零元素,成一向量 l m=find(path(i+1,:)=0); v2=path(i+1,m); %取出i+1行的非零元素,成一向量 path(i,:)=v1(1:temPm4-1) temp2 v1(temPm4-1+size(temp1):end); path(i+1,:)=v2(1:temPm4-1) temp1 v2(temPm4-1+size(temp2):end); %基因交叉 end end path(Popsize,:)=BestS; %* Step 4: 变异操作 * for i=1:Popsize tempPm=rand(1); if(tempPmtemp %交叉条件 TempE(i,n:end)=E(i+1,n:end); TempE(i+1,n:end)=E(i,n:end); end end TempE(Size,:)=BestS; %最优个体保留E=TempE; %种群替换 %* Step 4: 变异操作 * %pm=0.001; %pm=0.001-1:1:Size*(0.001)/Size; %自适应变异概率%pm=0.0; %没有变异pm=0.1; %较大的变异概率 for i=1:1:Size for j=1:1:2*CodeL temp=rand; if pmtemp %变异条件 if TempE
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 人教版阅读与思考海伦-秦九韶公式
- 组织胚胎学全部题库
- 《李凭箜篌引》统编版高中语文选择性必修中册+
- 白兰鸽教案课件设计
- 阿尔及利亚石油工业行业市场前景及投资研究报告-外文版培训课件2024.7temu
- 爸爸的胡子美术教案
- 苏州市吴江区桃源镇社区工作者招聘考试试题及答案2024
- 肇庆市四会市威整镇社区工作者招聘考试试题及答案2024
- 菏泽市成武县伯乐集镇社区工作者招聘考试试题及答案2024
- 聊城市临清市松林镇社区工作者招聘考试试题及答案2024
- 中国乒乓球长盛不衰的原因探究
- 县卫生健康局有关开展医疗机构安全风险排查整改工作情况报告
- 幼儿简单迷宫图(整理打印)(共7页)
- 六年级语文(部编)上册词语表拼音
- 北师大七年级上册数学教学工作计划(1)
- 关于婚检率低的问题整改报告 (2)
- 双馈电机原理
- 校长个人专业发展规划(3年
- 初中家委会工作计划5篇
- 供应商QSA QPA评审表(电池)
- 2022最新小学一年级上数学期末试卷
评论
0/150
提交评论