|
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# \
|
|