【29】【优化算法】遗传算法求最短路径

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【29】【优化算法】遗传算法求最短路径，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含8836字，纯文字阅读大概需要13分钟。

内容图文

界面设计

 

 

 

一、问题分析

如图如示，将节点编号，依次为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的路径与距离，然后将矩阵按主对角线翻折即可得到全部数据。

二、实验原理与数学模型

实现原理为遗传算法原理：

按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，使得适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。

数学模型如下：

 

 

实验具体：

第一：编码与初始化

因采用自然编码，且产生的编码不能重复，于是我采用了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到11的无重复编码，所以不能采用一般的生成一个随机数替代的办法。此处采用交换变异法。即随机产生两个数，交换两个节点的顺序。

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 tempP<roulette(j)                break;            end        end        path(i,:)=temppath(j,:);    end    %************ Step 3 : 交叉操作 ************    temppath2=path;    for i=1:2:row        tempP2=rand(1);                                 if(tempP2<rand(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(tempPm<Pm)            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;             %变异交换        end     end    path(Popsize,:)=BestS;end[aa bb]=find(BestS==b);                          %找出终点Bestpath=BestS(1:bb);                            %剔除后面无用的点，留下实际路线outdistance(a,b)=Bestindividual(k);              %将最短距离写入矩阵outpath{a,b}=Bestpath;                           %写入路径，因数据类型为矩阵，所以采用元胞数组储存endendfor i=1:pointnumber    for j=1:i        outdistance(i,j)=outdistance(j,i);       %实现距离的对称        outpath{i,j}=fliplr(outpath{j,i});       %实现路径的对称与翻转    endend    %*************** 结果输出 *****************outdistancecelldisp(outpath)%xlswrite('tempdata.xls', outpath)               %存入excel中进行操作

距离矩阵：a(i,j) i表示起点，j表示终点。

outdistance =

 

     0     2     7     1     3     6    10     5    12    11    14

     2     0     5     3     1     4     8     3    10     9    12

     7     5     0     7     4     1     5     6     7     6     9

     1     3     7     0     4     8     9     6    11    10    13

     3     1     4     4     0     3     7     2     9     8    11

     6     4     1     8     3     0     4     5     6     5     8

    10     8     5     9     7     4     0     9     2     1     4

     5     3     6     6     2     5     9     0     7     8     9

    12    10     7    11     9     6     2     7     0     1     2

    11     9     6    10     8     5     1     8     1     0     3

14    12     9    13    11     8     4     9     2     3     0

路径：b(i,j) i表示起点，j表示终点。

outpath:

 

注：完整代码或者代写添加QQ1575304183

内容总结

以上是互联网集市为您收集整理的【29】【优化算法】遗传算法求最短路径全部内容，希望文章能够帮你解决【29】【优化算法】遗传算法求最短路径所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---