遗传算法解决TSP问题的matlab程序.docx
《遗传算法解决TSP问题的matlab程序.docx》由会员分享，可在线阅读，更多相关《遗传算法解决TSP问题的matlab程序.docx（31页珍藏版）》请在冰点文库上搜索。
遗传算法解决TSP问题的matlab程序
1.遗传算法解决TSP问题（附matlab源程序）
2.知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市
3.只能访问一次，最后又必须返回出发城市。
如何安排他对这些城市的访问次序，可使其
4.旅行路线的总长度最短？
5.用图论的术语来说，假设有一个图g=（v,e），其中v是顶点集，e是边集，设d=（dij）
6.是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶
7.点且每个顶点只通过一次的具有最短距离的回路。
8.这个问题可分为对称旅行商问题（dij=dji,,任意i,j=1,2,3，…,n）和非对称旅行商
9.问题（dij≠dji,,任意i,j=1,2,3，…,n）。
10.若对于城市v={v1,v2,v3,…,vn}的一个访问顺序为t=（t1,t2,t3,…,ti,…,tn）,其中
11.ti∈v（i=1,2,3,…,n），且记tn+1=t1，则旅行商问题的数学模型为：
12.minl=σd（t（i）,t（i+1））（i=1,…,n）
13.旅行商问题是一个典型的组合优化问题，并且是一个np难问题，其可能的路径数目
14.与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法
15.求其近似解。
16.遗传算法：
17.初始化过程：
用v1,v2,v3,…,vn代表所选n个城市。
定义整数pop-size作为染色体的个数
18.，并且随机产生pop-size个初始染色体，每个染色体为1到18的整数组成的随机序列。
19.适应度f的计算：
对种群中的每个染色体vi，计算其适应度，f=σd（t（i）,t（i+1））.
20.评价函数eval（vi）：
用来对种群中的每个染色体vi设定一个概率，以使该染色体被选中
21.的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被
22.选择产生后台的机会要大，设alpha∈（0,1），本文定义基于序的评价函数为eval（vi）=al
23.pha*（1-alpha）.^（i-1）。
[随机规划与模糊规划]
24.选择过程：
选择过程是以旋转赌轮pop-size次为基础，每次旋转都为新的种群选择一个
25.染色体。
赌轮是按每个染色体的适应度进行选择染色体的。
26.step1、对每个染色体vi,计算累计概率qi，q0=0;qi=σeval（vj）j=1,…,i;i=1,
27.…pop-size.
28.step2、从区间（0,pop-size）中产生一个随机数r；
29.step3、若qi-1step4、重复step2和step3共pop-size次，这样可以得到pop-size个复制的染色体。
30.grefenstette编码：
由于常规的交叉运算和变异运算会使种群中产生一些无实际意义的
31.染色体，本文采用grefenstette编码《遗传算法原理及应用》可以避免这种情况的出现
32.。
所谓的grefenstette编码就是用所选队员在未选（不含淘汰）队员中的位置，如：
33.815216107431114612951813171
34.对应：
35.81421386325734324221。
36.交叉过程：
本文采用常规单点交叉。
为确定交叉操作的父代，从到pop-size重复以下过
37.程：
从[0，1]中产生一个随机数r，如果r将所选的父代两两组队，随机产生一个位置进行交叉，如：
38.81421386325734324221
39.6123568563185633211
40.交叉后为：
41.81421386325185633211
42.6123568563734324221
43.变异过程：
本文采用均匀多点变异。
类似交叉操作中选择父代的过程，在r选择多个染色体vi作为父代。
对每一个选择的父代，随机选择多个位置，使其在每位置
44.按均匀变异（该变异点xk的取值范围为[ukmin,ukmax],产生一个[0，1]中随机数r，该点
45.变异为x'k=ukmin+r（ukmax-ukmin））操作。
如：
46.81421386325734324221
47.变异后：
48.814213106322734524121
49.反grefenstette编码：
交叉和变异都是在grefenstette编码之后进行的，为了循环操作
50.和返回最终结果，必须逆grefenstette编码过程，将编码恢复到自然编码。
51.循环操作：
判断是否满足设定的带数xzome，否，则跳入适应度f的计算；是，结束遗传
52.操作，跳出。
53.
54.
55.
56.matlab代码
57.
58.
59.
60.distTSP.txt
61.061848
62.701737
63.44045
64.201924022
65.881660
66.%GATSP.m
67.functiongatsp1（）
68.clear;
69.loaddistTSP.txt;
70.distance=distTSP;
71.N=5;
72.ngen=100;
73.ngpool=10;
74.%ngen=input（'#ofgenerationstoevolve='）;
75.%ngpool=input（'#ofchromosomsinthegenepool='）;%sizeofgenepool
76.gpool=zeros（ngpool,N+1）;%genepool
77.fori=1:
ngpool,%intializegenepool
78.gpool（i,:
）=[1randomize（[2:
N]'）'1];
79.forj=1:
i-1
80.whilegpool（i,:
）==gpool（j,:
）
81.gpool（i,:
）=[1randomize（[2:
N]'）'1];
82.end
83.end
84.end
85.
86.costmin=100000;
87.tourmin=zeros（1,N）;
88.cost=zeros（1,ngpool）;
89.increase=1;resultincrease=1;
90.fori=1:
ngpool,
91.cost（i）=sum（diag（distance（gpool（i,:
）',rshift（gpool（i,:
））'）））;
92.end
93.%recordcurrentbestsolution
94.[costmin,idx]=min（cost）;
95.tourmin=gpool（idx,:
）;
96.disp（[num2str（increase）'minmumtriplength='num2str（costmin）]）
97.
98.costminold2=200000;costminold1=150000;resultcost=100000;
99.tourminold2=zeros（1,N）;
100.tourminold1=zeros（1,N）;
101.resulttour=zeros（1,N）;
102.while（abs（costminold2-costminold1）;100）&（abs（costminold1-costmin）;100）&（increase;500）
103.
104.costminold2=costminold1;tourminold2=tourminold1;
105.costminold1=costmin;tourminold1=tourmin;
106.increase=increase+1;
107.ifresultcost>costmin
108.resultcost=costmin;
109.resulttour=tourmin;
110.resultincrease=increase-1;
111.end
112.fori=1:
ngpool,
113.cost（i）=sum（diag（distance（gpool（i,:
）',rshift（gpool（i,:
））'）））;
114.end
115.%recordcurrentbestsolution
116.[costmin,idx]=min（cost）;
117.tourmin=gpool（idx,:
）;
118.%==============
119.%copygensinthgpoolaccordingtotheprobilityratio
120.%>1.1copytwice
121.%>=0.9copyonce
122.%;0.9remove
123.[csort,ridx]=sort（cost）;
124.%sortfromsmalltobig.
125.csum=sum（csort）;
126.caverage=csum/ngpool;
127.cprobilities=caverage./csort;
128.copynumbers=0;removenumbers=0;
129.fori=1:
ngpool,
130.ifcprobilities（i）>1.1
131.copynumbers=copynumbers+1;
132.end
133.ifcprobilities（i）<0.9
134.removenumbers=removenumbers+1;
135.end
136.end
137.copygpool=min（copynumbers,removenumbers）;
138.fori=1:
copygpool
139.forj=ngpool:
-1:
2*i+2gpool（j,:
）=gpool（j-1,:
）;
140.end
141.gpool（2*i+1,:
）=gpool（i,:
）;
142.end
143.ifcopygpool==0
144.gpool（ngpool,:
）=gpool（1,:
）;
145.end
146.%=========
147.%whengenarationismorethan50,orthepatternsinacouplearetooclose,domutation
148.fori=1:
ngpool/2
149.%
150.sameidx=[gpool（2*i-1,:
）==gpool（2*i,:
）];
151.diffidx=find（sameidx==0）;
152.iflength（diffidx）<=2
153.gpool（2*i,:
）=[1randomize（[2:
12]'）'1];
154.end
155.end
156.%===========
157.%crossgensincouples
158.fori=1:
ngpool/2
159.[gpool（2*i-1,:
）,gpool（2*i,:
）]=crossgens（gpool（2*i-1,:
）,gpool（2*i,:
））;
160.end
161.
162.fori=1:
ngpool,
163.cost（i）=sum（diag（distance（gpool（i,:
）',rshift（gpool（i,:
））'）））;
164.end
165.%recordcurrentbestsolution
166.[costmin,idx]=min（cost）;
167.tourmin=gpool（idx,:
）;
168.disp（[num2str（increase）'minmumtriplength='num2str（costmin）]）
169.end
170.
171.disp（['costfunctionevaluation:
'int2str（increase）'times!
']）
172.disp（['n:
'int2str（resultincrease）]）
173.disp（['minmumtriplength='num2str（resultcost）]）
174.disp（'optimumtour='）
175.disp（num2str（resulttour））
176.%====================================================
177.functionB=randomize（A,rowcol）
178.%Usage:
B=randomize（A,rowcol）
179.%randomizerowordersorcolumnordersofAmatrix
180.%rowcol:
if=0oromitted,roworder（default）
181.%if=1,columnorder
182.
183.rand（'state',sum（100*clock））
184.ifnargin==1,
185.rowcol=0;
186.end
187.ifrowcol==0,
188.[m,n]=size（A）;
189.p=rand（m,1）;
190.[p1,I]=sort（p）;
191.B=A（I,:
）;
192.elseifrowcol==1,
193.Ap=A';
194.[m,n]=size（Ap）;
195.p=rand（m,1）;
196.[p1,I]=sort（p）;
197.B=Ap（I,:
）';
198.end
199.%=====================================================
200.functiony=rshift（x,dir）
201.%Usage:
y=rshift（x,dir）
202.%rotatexvectortoright（down）by1ifdir=0（default）
203.%orrotatextoleft（up）by1ifdir=1
204.ifnargin;2,dir=0;end
205.[m,n]=size（x）;
206.ifm>1,
207.ifn==1,
208.col=1;
209.elseifn>1,
210.error（'xmustbeavector!
break'）;
211.end%xisacolumnvectorelseifm==1,
212.ifn==1,y=x;
213.return
214.elseifn>1,
215.col=0;%xisarowvectorendend
216.ifdir==1,%rotateleftorup
217.ifcol==0,%rowvector,rotateleft
218.y=[x（2:
n）x
（1）];
219.elseifcol==1,
220.y=[x（2:
n）;x
（1）];%rotateup
221.end
222.elseifdir==0,%defaultrotaterightordown
223.ifcol==0,
224.y=[x（n）x（1:
n-1）];
225.elseifcol==1%columnvector
226.y=[x（n）;x（1:
n-1）];
227.end
228.end
229.%==================================================
230.function[L1,L2]=crossgens（X1,X2）
231.%Usage:
[L1,L2]=crossgens（X1,X2）
232.s=randomize（[2:
12]'）';
233.n1=min（s
（1）,s（11））;n2=max（s
（1）,s（11））;
234.X3=X1;X4=X2;
235.fori=n1:
n2,
236.forj=1:
13,
237.ifX2（i）==X3（j）,
238.X3（j）=0;
239.end
240.ifX1（i）==X4（j）,X4（j）=0;
241.end
242.end
243.end
244.j=13;k=13;
245.fori=12:
-1:
2,
246.ifX3（i）~=0,
247.j=j-1;
248.t=X3（j）;X3（j）=X3（i）;X3（i）=t;
249.end
250.ifX4（i）~=0,
251.k=k-1;
252.t=X4（k）;X4（k）=X4（i）;X4（i）=t;
253.end
254.end
255.fori=n1:
n2
256.X3（2+i-n1）=X2（i）;
257.X4（2+i-n1）=X1（i）;
258.end
259.L1=X3;L2=X4;
遗传算法程序matlab
1.遗传算法程序:
2.说明:
fga.m为遗传算法的主程序;采用二进制Gray编码,采用基于轮盘赌法的非线性排名选择,均匀交叉,变异操作,而且还引入了倒位操作!
3.
4.function[BestPop,Trace]=fga（FUN,LB,UB,eranum,popsize,pCross,pMutation,pInversion,options）
5.%[BestPop,Trace]=fmaxga（FUN,LB,UB,eranum,popsize,pcross,pmutation）
6.%Findsamaximumofafunctionofseveralvariables.
7.%fmaxgasolvesproblemsoftheform:
8.%maxF（X）subjectto:
LB<=X<=UB
9.%BestPop-最优的群体即为最优的染色体群
10.%Trace-最佳染色体所对应的目标函数值
11.%FUN-目标函数
12.%LB-自变量下限
13.%UB-自变量上限
14.%eranum-种群的代数,取100--1000（默认200）
15.%popsize-每一代种群的规模；此可取50--200（默认100）
16.%pcross-交叉概率,一般取0.5--0.85之间较好（默认0.8）
17.%pmutation-初始变异概率,一般取0.05-0.2之间较好（默认0.1）
18.%pInversion-倒位概率,一般取0.05－0.3之间较好（默认0.2）
19.%options-1*2矩阵,options
（1）=0二进制编码（默认0）,option
（1）~=0十进制编
20.%码,option
（2）设定求解精度（默认1e-4）
21.%
22.%------------------------------------------------------------------------
23.
24.T1=clock;
25.ifnargin<3,error（'FMAXGArequiresatleastthreeinputarguments'）;end
26.ifnargin==3,eranum=200;popsize=100;pCross=0.8;pMutation=0.1;pInversion=0.15;options=[01e-4];end
27.ifnargin==4,popsize=100;pCross=0.8;pMutation=0.1;pInversion=0.15;options=[01e-4];end
28.ifnargin==5,pCross=0.8;pMutation=0.1;pInversion=0.15;options=[01e-4];end
29.ifnargin==6,pMutation=0.1;pInversion=0.15;options=[01e-4];end
30.ifnargin==7,pInversion=0.15;options=[01e-4];end
31.iffind（（LB-UB）>0）
32.error（'数据输入错误,请重新输入（LB'）;
33.
'）;
34.end
35.s=sprintf（'程序运行需要约%.4f秒钟时间,请稍等......',（eranum*popsize/1000））;
36.disp（s）;
37.
38.globalmnNewPopchildren1children2VarNum
39.
40.bounds=[LB;UB]';bits=[];VarNum=size（bounds,1）;
41.precision=options
（2）;%由求解精度确定二进制编码长度
42.bits=ceil（log2（（bounds（:
2）-bounds（:
1））'./precision））;%由设定精度划分区间
43.[Pop]=InitPopGray（popsize,bits）;%初始化种群
44.[m,n]=size（Pop）;
45.NewPop=zeros（m,n）;
46.children1=zeros（1,n）;
47.children2=zeros（1,n）;
48.pm0=pMutation;
49.BestPop=zeros（
升级会员 