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

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

[复制链接]

该用户从未签到

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

EDA365欢迎您登录!

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

x

: b$ B8 o& G5 z" P/ q一、简介7 `; i$ G6 @; J
8 ^6 |  C6 ^0 T

7 e7 r) X9 z# y( E1 U+ F) x& @一、问题分析, y, C; g( W$ u8 g
+ C7 d+ K- q4 {& E' l0 h! a
如图如示,将节点编号,依次为1.2.3.4.5.6.7.8.9.10.11,由图论知识,则可写出其带权邻接矩阵为:$ I4 N) n; i6 n. q

0 W0 O/ B) C0 J0 G9 h5 q' f
  • 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
    ) v9 ]( _# M# L# j; `  J$ I* x

  L  Q: z' b5 P- s% w/ f! D7 E& s& F2 G7 w# }5 V% q3 T
500 1 500 500 0 3 500 2 500 500 500% c/ f* N4 L4 `
) P7 e/ b' o. L6 ~( g. M# a
500 500 1 500 3 0 4 500 6 500 5001 V) m3 \( [8 g# x

8 S+ l8 W6 s& j: k# e: @500 500 500 9 500 4 0 500 500 1 5008 a3 \$ c. _1 r- j  b

3 q  M$ H- V# w- O500 500 500 500 2 500 500 0 7 500 9- [2 O" j9 }: U8 F
" X& e# A; a* ?8 D! O8 j* Y% K
500 500 500 500 500 6 500 7 0 1 2
. D7 j1 ^. X6 d: W9 n3 {: g. j) ]: N! X' w5 f1 o
500 500 500 500 500 500 1 500 1 0 4
  c- F9 W* ~+ K* Y7 t/ L! t- T- }& o
500 500 500 500 500 500 500 9 2 4 0
( n& P- N( L3 F
( a. i1 e1 t- n- U" A& @5 y0 b注:为避免计算时无穷大数吃掉小数,此处为令inf=500。
) r. n. @: @# c/ g4 [- O0 R% i% H( q- N4 W" w# _( z

- q2 W3 S3 }" x# t9 t0 ~, J' s# j问题要求求出任意两点间的最短路径,Floyd算法采用的是在两点间尝试插入顶点,比较距离长短的方法。我思考后认为,用遗传算法很难找到一个可以统一表示最短路径的函数,但是可以对每一对点分别计算,然后加入for循环,可将相互之间的所有情况解出。观察本题可发现,所有节点都是可双向行走,则可只计算i到j的路径与距离,然后将矩阵按主对角线翻折即可得到全部数据。9 l- \) i; ~" k3 A: Y9 w

# Z; H; |4 O0 U# h+ O" n
( T5 ^9 H, {6 g. f; V4 \, z
3 X7 t2 H4 }2 d6 e1 t二、实验原理与数学模型. C  P, F  o& O, E

! J, {1 J; Z3 h; {9 |实现原理为遗传算法原理:
  T& p- o3 w+ K; t: ~* y! Z5 V
: {* S7 r0 w# L% J9 |+ W4 l按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选,使得适应度高的个体被保留下来,组成新的群体,新的群体既继承了上一代的信息,又优于上一代。这样周而复始,群体中个体适应度不断提高,直到满足一定的条件。
& l* o: P$ G$ r& h
8 j8 y( k0 N/ q7 K数学模型如下:& J5 ^6 t+ n  n0 d  u/ x. Y0 [
+ u1 k1 x4 ~: H8 E/ r* Z& `

; H- S4 g7 |2 G. {& k$ O+ K2 D7 k, @; x# C" g5 d

8 r8 l) l$ F4 U$ g实验具体:8 H4 U# e1 r0 C
3 m* ~, u2 ^( I3 P0 p; R8 o
第一:编码与初始化
6 |+ m) s3 v4 I, g: S
) J3 U7 G" \5 E! Z( k2 q因采用自然编码,且产生的编码不能重复,于是我采用了randperm函数产生不重复的随机自然数。因解题方法是使用的是计算每一对点,则我们编码时将第一个节点单独放入,合并成完整编码。
% v% z* E- F* N" a% E7 q. q* S. O4 H. f0 e1 e6 H
因为节点有11个,可采用一个1行11列的矩阵储存数据,同时,由于编号为数字,可直接使用数字编码表示路径的染色体。具体如下:
% @, E; B1 v  Z, m" G/ P
* Z9 V9 m: \4 T采用等长可变染色体的方式,例如由2到9的路径,染色体编码可能为(2,5,1,8,4,6,9,3,10,7,11),超过9之后的编码,用来进行算子的运算,不具备实际意义。3 T0 D  Z! M7 |# d

1 s9 z: n3 V: N7 r4 q第二:计算适应度,因取最短路径值,即最小值,常用方法为C-F(x)或C/F(x)(C为一常数),此处采用前一种方式。于是,可进一步计算相对适应度。- @9 v" w2 u; U4 I4 w/ Z4 S4 {
: t- [4 c; T7 J5 R! r
第三:选择与复制" |! e  m6 q% v( K# e0 S
! h5 w! h4 v% t  R& R8 ^- U1 {
采用轮盘赌算法,产生一个随机值,比较它与累计相对适应度的关系,从而选择出优良个体进入下一代。
: B; R9 U3 f& O  F
1 w2 u4 l) B/ b第四:交叉。% n' P; u) V# h) {0 g2 Z& M

9 h3 v8 _- I% y- m" b. {因编码是不重复的数字,所以采用传统的交叉方法,即上一行与下一行对位交叉,会产生无效路径,于是,采用了不同的交叉方法,具体如下:
+ j+ R" R9 y% [  I% H" `! L- w+ q' `7 Q- i3 k; q. c+ t4 V
(1)在表示路径的染色体Tx 和Ty中,随机选取两个基因座(不能为起点基因座)i和j, 即将i个基因座和第j个基因座之间的各个基因座定义为交叉域,并将交叉的内容分别记忆为temp1和temp2。
/ y+ ~4 }: F. N: B1 V. e& B9 M9 \4 S! h9 ~+ X' \: N5 C! v- b3 m$ B
(2)根据交叉区域中的映射关系,在个体Tx中找出所有与temp2相同的元素,在个体Ty中找出所有与temp1相同的元素,全部置为0。
5 l* |- l; [: j$ Y+ a5 Q5 l
5 @6 E7 l+ s7 _(3)将个体Tx、Ty进行循环左移,遇到0就删除,直到编码串中交叉区域的左端不再有0:然后将所有空位集中到交叉区域,而将交叉区域内原有的基因依次向后移动。因0元素可能较多,在程序实现时,我是将非零元素提出,后面再合成。
/ A. U, {$ p; ]3 I" s  u
: X# d* l- s/ G& |, O(4)将temp2插入到Tx的交叉区域,temp1插入到Ty的交叉区域。形成新的染色体。
1 c8 W; g' S# _6 g( b8 g2 I. y9 V# b+ G% \
第五:变异+ T* f6 \+ e- @; ]9 @& s& C( t
; G  Z& X  g* v& x, f5 E
染色体编码为从1到11的无重复编码,所以不能采用一般的生成一个随机数替代的办法。此处采用交换变异法。即随机产生两个数,交换两个节点的顺序。2 @) S4 B4 y' e7 q' \) Q: q
4 e# z$ U2 I" ^. n- M
" I+ O  c" I7 H  t$ L2 k8 i1 _1 q
' [- n( W" t' J' n/ X* D
二、源代码3 f+ u4 X: C/ L( W2 n2 z' ]& E* ^# ?
  • 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中进行操作
    ; N3 X9 x8 [1 q) w
, ^# W/ t9 S' t$ t" `0 o: h
; ~; B9 f5 S3 Z. t4 V: u
三、运行结果
  f3 g. @: s3 @
4 R- v$ Q  K; ]距离矩阵:a(i,j) i表示起点,j表示终点。
4 Z" a+ e( a8 ^8 z! u% K0 f* S  [
! m' _) Z/ s' l, ~8 t( O7 s4 R# Doutdistance =) v" H. u, t& S  E, J

* V! I6 o2 ?. J5 Z, z$ ^2 }
  • 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     31 F, d% z8 V1 j1 ~

0 U4 `; y8 F* u  ]) O2 t- S8 s( i' W$ Z/ L
14 12 9 13 11 8 4 9 2 3 0
: ~) g& Y& ~9 f' F1 [, I! E5 E- M# T  s
路径:b(i,j) i表示起点,j表示终点。* i! R6 p3 H& D! K/ d

8 O7 c' {& r4 ]6 j1 routpath:
6 q) D/ R1 q, C* E, d$ |0 c- a
5 h$ K6 s) Z  ?' F. `, r- c
, ?0 U* M# U! [3 x8 T. Y
1 R. u, L% r. v3 N3 O
" m& ]0 C6 o) N7 U1 o) {! t8 Z, G3 c4 e, Z! I  {

该用户从未签到

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

本版积分规则

关闭

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

EDA365公众号

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

GMT+8, 2025-10-31 04:56 , Processed in 0.140625 second(s), 26 queries , Gzip On.

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

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

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