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.min l=σ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-1 step4、重复step2和step3共pop-size次，这样可以得到pop-size个复制的染色体。
30.grefenstette编码：由于常规的交叉运算和变异运算会使种群中产生一些无实际意义的
31.染色体，本文采用grefenstette编码《遗传算法原理及应用》可以避免这种情况的出现
32.。所谓的grefenstette编码就是用所选队员在未选（不含淘汰）队员中的位置，如：
33.8 15 2 16 10 7 4 3 11 14 6 12 9 5 18 13 17 1
34.对应：
35.8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1。
36.交叉过程：本文采用常规单点交叉。为确定交叉操作的父代，从到pop-size重复以下过
37.程：从[0，1]中产生一个随机数r，如果r 将所选的父代两两组队，随机产生一个位置进行交叉，如：
38.8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1
39. 6 12 3 5 6 8 5 6 3 1 8 5 6 3 3 2 1 1
40.交叉后为：
41.8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 1
42. 6 12 3 5 6 8 5 6 3 7 3 4 3 2 4 2 2 1
43.变异过程：本文采用均匀多点变异。类似交叉操作中选择父代的过程，在r 选择多个染色体vi作为父代。对每一个
选择的父代，随机选择多个位置，使其在每位置
44.按均匀变异（该变异点xk的取值范围为[ukmin,ukmax],产生一个[0，1]中随机数r，该点
45.变异为x'k=ukmin+r(ukmax-ukmin)）操作。如：
46.8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1
47.变异后：
48.8 14 2 13 10 6 3 2 2 7 3 4 5 2 4 1 2 1
49.反grefenstette编码：交叉和变异都是在grefenstette编码之后进行的，为了循环操作
50.和返回最终结果，必须逆grefenstette编码过程，将编码恢复到自然编码。
51.循环操作：判断是否满足设定的带数xzome，否，则跳入适应度f的计算；是，结束遗传
52.操作，跳出。
53.
54.
55.
56.matlab 代码
57.
58.
59.
60.distTSP.txt
61.0 6 18 4 8
62.7 0 17 3 7
63. 4 4 0 4 5
64.20 19 24 0 22
65.8 8 16 6 0
66.%GATSP.m
67.function gatsp1()
68.clear;
69.load distTSP.txt;
70.distance=distTSP;
71.N=5;
72.ngen=100;
73.ngpool=10;
74.%ngen=input('# of generations to evolve = ');
75.%ngpool=input('# of chromosoms in the gene pool = '); % size of genepool
76.gpool=zeros(ngpool,N+1); % gene pool
77.for i=1:ngpool, % intialize gene pool
78.gpool(i,:)=[1 randomize([2:N]')' 1];
79.for j=1:i-1
80.while gpool(i,:)==gpool(j,:)
81.gpool(i,:)=[1 randomize([2:N]')' 1];
82.end
83.end
84.end
85.
86.costmin=100000;
87.tourmin=zeros(1,N);
