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

研究生考试试卷考试科目：MATLAB教程候选人姓名：学生编号：学校：专业化：学生的成绩：(签名)老师考试日期：20年，从中午到中午MATLAB教程问题：用MATLAB设计遗传算法程序，找出下图中11个端点的最短路径，没有连接的端点表示没有路径。需要设计遗传算法来解决这个问题。b .设计遗传算法求解f(x)最小值，具体表达式如下：要求程序必须以m函数的方式设计。用MATLAB编程实现：三个商人各带一名随行人员乘船渡河，一艘船只能容纳两人，由他们自己承担，随行人员秘密约定，在河的两边，一旦随行人员的数量超过商人，他们就会杀人并渡河，但是如何乘船渡河的权力掌握在商人手中，商人如何能安全渡河？根据你的研究方向选择合适的问题，并用MATLAB进行实验。从上述四个问题中选择一个进行实验，并写实验报告。选择主题：a一、问题分析(10分)如图所示，节点编号依次为1.2.3.4.5.6.7.8.9.10.11。根据图论知识，其加权邻接矩阵可以写成如下：0 2 8 1 500 500 500 500 500 500 5002 0 6 500 1 500 500 500 500 500 5008 6 0 7 500 1 500 500 500 500 5001 500 7 0 500 500 9 500 500 500 500500 1 500 500 0 3 500 2 500 500 500500 500 1 500 3 0 4 500 6 500 500500 500 500 9 500 4 0 500 500 1 500500 500 500 500 2 500 500 0 7 500 9500 500 500 500 500 6 500 7 0 1 2500 500 500 500 500 500 1 500 1 0 4500 500 500 500 500 500 500 9 2 4 0注意：为了避免在计算中无限数吃十进制数，这里使用inf=500。这个问题需要找到任意两点之间的最短路径。Floyd算法使用尝试在两点之间插入顶点并比较距离的方法。经过思考，我认为用遗传算法很难找到一个能统一表示最短路径的函数，但可以对每一对点分别计算，然后加一个循环来解决它们之间的所有情况。看这个题目，我们可以发现所有的节点可以在两个方向上行走，所以我们只能计算从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分)首先，编写程序来修复错误。然后，调试种群数量、遗传代数、交叉概率、变异概率等。并不断运行程序以达到更好的状态。一旦出现异常情况：计算的最短距离都是0，最短路径没有终点。经过分析，发现因为交叉点的代码更复杂，而且有错误，一些新基因是非法基因。最后，通过提出非零值来形成载体和合成新基因来解决这个问题。Matlab程序代码如下：clc清除；%初始化参数%注意：popsize=200，MaxGeneration=100，运行大约2分钟。如果不要求太精确，循环次数可以减少。点数=11；节点数%Popsize=200%人口规模，只能取偶数(由于67行循环)MaxGeneration=100% max代数Pc=0.8。Pm=0.3。%交叉概率和变异概率a=0 2 8 1 50 50 50 50 50 50 50 50 502 0 6 50 1 50 50 50 50 50 508 6 0 7 50 1 50 50 50 50 501 50 7 0 50 50 9 50 50 50 5050 1 50 50 0 3 50 2 50 50 5050 50 1 50 3 0 4 50 6 50 5050 50 50 9 50 4 0 50 50 1 5050 50 50 50 2 50 50 0 7 50 950 50 50 50 50 6 50 7 0 1 250 50 50 50 50 50 1 50 1 0 450 50 50 50 50 50 50 9 2 4 0；%加权邻接矩阵。甲(甲=50)=500；50%的值太小，更正为500；最佳个体=零(最大生成，1)；外距离=零(11，11)；outpath=单元格(11，11)；%用于存储11点之间的最短路径% * * * * *生成初始群体* * * * * *对于a=点编号%起点编号% a=1；temp vary=1 2 3 4 5 6 7 8 9 10 11；temp vary(a)=；%暂时拒绝起点temp matrix=a * one(Popsi size，1)；%将起点单独放在矩阵中path=零(Popsize，point number-1)；%声明矩阵大小以避免变慢对于i=1:Popsizetemprand=randperm(点数-1)；路径(I，)=temp vary(temprand(1: end)；%生成一系列不包括起点的随机路线目标路径=tempmatrix路径；%合成完整路线，包括起点行，col=大小(路径)；对于b=点编号%端点编号% b=10对于k=1:1:最大发电量对于i=1:row位置2=查找（路径(I，)=b)；%找出终点在路线中的位置路径长(I)=0；对于j=位置2-1路径长(一)=路径长(路径(一、j)、路径(一、j . 1)；目标目标%计算适应度适合度=长度(一)*最大值（最大值(一)-路径长度；%因要求最小值，采且常数减函数值构造适应度健康=健康/sum(健身)；%*步骤1 :选择最优个体* * * * * * *最佳个体(k)=最小值（路径长度)；奥尔德菲，指数=排序（适合度)；%按照适应度大小