找回密码
 注册
关于网站域名变更的通知
查看: 472|回复: 1
打印 上一主题 下一主题

基于matlab遗传算法求最短路径

[复制链接]

该用户从未签到

跳转到指定楼层
1#
发表于 2021-3-12 18:09 | 只看该作者 |只看大图 回帖奖励 |倒序浏览 |阅读模式

EDA365欢迎您登录!

您需要 登录 才可以下载或查看,没有帐号?注册

x

6 W. X% }( S8 Y& N0 e1 d一、简介, k. H' N8 z, B
# N' g' G. U! a! {8 g7 h: Q5 q' S
# a2 c$ g  }) k7 u  L) v6 W" v3 c
一、问题分析3 r$ Z: k+ Z+ P

3 B# L6 f' W/ p* q7 n& \如图如示,将节点编号,依次为1.2.3.4.5.6.7.8.9.10.11,由图论知识,则可写出其带权邻接矩阵为:
) L4 E, m( p; \
) F6 ]4 p$ e  B7 k
  • 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; w1 p* f+ ^: e3 n1 X( d  n

3 o% n: B( F: h2 [( [
5 s2 A: ~! G3 G" g; j# }500 1 500 500 0 3 500 2 500 500 500
$ L4 U4 M6 u, E
6 b$ L' Z4 L/ u/ M500 500 1 500 3 0 4 500 6 500 500
/ q9 G4 }4 U* c4 i0 h9 @; A1 C' I
500 500 500 9 500 4 0 500 500 1 500
0 G4 \$ Y$ |/ e
6 L: F. W4 y, o7 K" ]500 500 500 500 2 500 500 0 7 500 9: p8 H- x9 v; {# }1 Q# u" p
3 u2 @1 a+ F/ @) U1 n- e
500 500 500 500 500 6 500 7 0 1 2+ N( g# l8 `2 Q) b5 T- _

- H+ }3 X( H0 X$ `) @$ a500 500 500 500 500 500 1 500 1 0 49 ?3 `# f6 @# j' W4 @$ K

# K% A/ a4 I' g6 D/ O; I8 k500 500 500 500 500 500 500 9 2 4 0- X& l* C4 t6 f; ]# T

4 k' y& I& m  g/ Z注:为避免计算时无穷大数吃掉小数,此处为令inf=500。# Y0 b  ^- A: `! {" y- K% P
/ [: v/ v& S4 y0 _
6 j" p! y0 v6 }! U9 V
问题要求求出任意两点间的最短路径,Floyd算法采用的是在两点间尝试插入顶点,比较距离长短的方法。我思考后认为,用遗传算法很难找到一个可以统一表示最短路径的函数,但是可以对每一对点分别计算,然后加入for循环,可将相互之间的所有情况解出。观察本题可发现,所有节点都是可双向行走,则可只计算i到j的路径与距离,然后将矩阵按主对角线翻折即可得到全部数据。6 m! ]  T+ |$ a; K

+ Z% g/ r5 T5 X8 J' r+ ]& a) f& v1 s1 D5 E8 [5 q/ e
! U, I9 B9 Z; h" @" m: h- E8 C
二、实验原理与数学模型
) f8 R* Z, G6 I) ~* C, S* O  M! j9 c7 B' {( G" ^. M# J; `
实现原理为遗传算法原理:/ j( \0 m& y' ^7 G( v
) Z8 s( H0 D3 J- C) J# n
按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选,使得适应度高的个体被保留下来,组成新的群体,新的群体既继承了上一代的信息,又优于上一代。这样周而复始,群体中个体适应度不断提高,直到满足一定的条件。
+ w2 G, x" G# y) }- U5 q: q4 F! x0 M# f7 x" W* L& h# I4 E9 V7 M1 w
数学模型如下:
  d/ z" S4 h4 D. f: s
( q2 v; v0 s% Y' S" j 6 b" f, C( c6 l0 r& W

  f% @8 l4 Z; S+ u; y3 J0 r) h+ b" [
实验具体:3 e. G" Y- C/ x9 J: K& i" H8 s
! S7 a& X! R. d8 c0 F
第一:编码与初始化
0 f. \9 o1 D4 [; @. m
$ D3 x& \1 t2 O9 r9 w: G因采用自然编码,且产生的编码不能重复,于是我采用了randperm函数产生不重复的随机自然数。因解题方法是使用的是计算每一对点,则我们编码时将第一个节点单独放入,合并成完整编码。9 d% m! h' J8 c$ F1 X; Q
/ V4 X1 ^' E. c' e! H* a; m5 |( X% N" n
因为节点有11个,可采用一个1行11列的矩阵储存数据,同时,由于编号为数字,可直接使用数字编码表示路径的染色体。具体如下:* Z" I; ^% @" ~8 x* F* i
  r; L& Y  l! O5 j+ P6 e( T
采用等长可变染色体的方式,例如由2到9的路径,染色体编码可能为(2,5,1,8,4,6,9,3,10,7,11),超过9之后的编码,用来进行算子的运算,不具备实际意义。
/ @6 Q/ Z8 d( K2 o/ |
: N! a! k& _) O) l5 @第二:计算适应度,因取最短路径值,即最小值,常用方法为C-F(x)或C/F(x)(C为一常数),此处采用前一种方式。于是,可进一步计算相对适应度。
: J( k# A$ C/ B$ U( [; C2 l5 H  A8 t/ d8 d# k& `
第三:选择与复制
1 K! d0 b1 b# a( O8 p* I! E; m  b4 O) y% z  g/ _" m2 P& n
采用轮盘赌算法,产生一个随机值,比较它与累计相对适应度的关系,从而选择出优良个体进入下一代。" @; |7 u+ E" U: _. q, c; P$ t

6 n/ A- y9 V# B. W$ u  K8 J7 l第四:交叉。9 \4 t% c  F' H% l% Z3 Z' v7 i. y

4 d9 w5 {0 p. k: x$ p* s  m6 {, I% G1 l7 X因编码是不重复的数字,所以采用传统的交叉方法,即上一行与下一行对位交叉,会产生无效路径,于是,采用了不同的交叉方法,具体如下:
9 X0 f9 L- q' ~
5 c# q* Q2 [* r(1)在表示路径的染色体Tx 和Ty中,随机选取两个基因座(不能为起点基因座)i和j, 即将i个基因座和第j个基因座之间的各个基因座定义为交叉域,并将交叉的内容分别记忆为temp1和temp2。8 K" c: Z) n' }( N/ ~1 q
2 q6 i0 `7 L$ W7 ?! u
(2)根据交叉区域中的映射关系,在个体Tx中找出所有与temp2相同的元素,在个体Ty中找出所有与temp1相同的元素,全部置为0。+ b; T* I% ]1 a0 }7 I

/ \- j" w8 j# Q: A8 j+ G% q(3)将个体Tx、Ty进行循环左移,遇到0就删除,直到编码串中交叉区域的左端不再有0:然后将所有空位集中到交叉区域,而将交叉区域内原有的基因依次向后移动。因0元素可能较多,在程序实现时,我是将非零元素提出,后面再合成。; V. [$ u; H/ d+ B
; `. ?5 v% p" k
(4)将temp2插入到Tx的交叉区域,temp1插入到Ty的交叉区域。形成新的染色体。7 x. O% r1 S# v1 P# J2 F& ?" _  C

* Y) ?" g$ O" q$ Y) C% G# I第五:变异
: ?  w' f# J7 i0 K( Q3 ^  I' {, j) A+ L, L" |; A0 M; Z
染色体编码为从1到11的无重复编码,所以不能采用一般的生成一个随机数替代的办法。此处采用交换变异法。即随机产生两个数,交换两个节点的顺序。3 e4 Z# _. S0 @6 ]% s1 X6 @# }! }

( d4 u" t8 C; o0 R
* b, i5 T; M0 Z2 w5 R) x' R& D/ F9 O$ Q, W" K& {
二、源代码
3 w1 I' [# Y% b, X5 d
  • 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));      %生成一系列剔除起点的随机路线
  • end
  • path=[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;                           %写入路径,因数据类型为矩阵,所以采用元胞数组储存
  • end
  • end
  • for i=1:pointnumber
  •     for j=1:i
  •         outdistance(i,j)=outdistance(j,i);       %实现距离的对称
  •         outpath{i,j}=fliplr(outpath{j,i});       %实现路径的对称与翻转
  •     end
  • end
  •     %*************** 结果输出 *****************
  • outdistance
  • celldisp(outpath)
  • %xlswrite('tempdata.xls', outpath)               %存入excel中进行操作
    ! ~* M: Z$ X6 e( l1 |/ G

; z5 @( y( O! u3 K# y% N* a2 _! n" E0 T
三、运行结果. J! `& J/ f* }) u
  @& Y0 n- l! h; O+ v+ w# k
距离矩阵:a(i,j) i表示起点,j表示终点。2 y5 |/ r4 _  L: `, |
7 [! J$ _/ C4 y  \& n2 F, Z1 l
outdistance =/ r" C6 Z/ D' E; F- }9 M; d) v# H

% t6 |7 M# ]- y
  • 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
    3 h. a" l3 g* @. R
9 F' G/ t+ R1 p
9 K4 H& W, ^# i3 Q/ ~  i
14 12 9 13 11 8 4 9 2 3 0
1 n0 G9 F4 Q: D8 p) d! N, ]
- h- ]1 e8 a( {' T7 [2 c路径:b(i,j) i表示起点,j表示终点。
. @$ H( [2 ~2 Y( c
. N4 ~( z$ s0 P9 e( boutpath:  \6 ?# U& b! |7 w

% e! {7 |" Q7 B4 H' ?! V' O   T& t7 L' n0 V$ F5 D3 C8 f9 f- V

2 _# y# L! Y" S: ^' d, W& l  b2 O
7 H& T3 o) E; r$ c5 d) p5 f. R9 E3 a) c9 D/ S# \

该用户从未签到

2#
发表于 2021-3-12 18:28 | 只看该作者
基于matlab遗传算法求最短路径
您需要登录后才可以回帖 登录 | 注册

本版积分规则

关闭

推荐内容上一条 /1 下一条

EDA365公众号

关于我们|手机版|EDA365电子论坛网 ( 粤ICP备18020198号-1 )

GMT+8, 2025-10-6 15:07 , Processed in 0.156250 second(s), 26 queries , Gzip On.

深圳市墨知创新科技有限公司

地址:深圳市南山区科技生态园2栋A座805 电话:19926409050

快速回复 返回顶部 返回列表