用遗传算法求解中国34个省会TSP问题
一、 TSP问题的描述
旅行商问题（TSP）可以具体描述为：已知n个城市之间的相互距离，现有一个推销员从某一个城市出发，必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回到出发城市，如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短。
现给出中国34个省会数据，要求基于此数据使用遗传算法解决该TSP问题。
中国34省会位置
city =
1.西藏  2.云南  3.四川王刚儿子  4.青海  5.宁夏  6.四个一健康管理是什么意思甘肃  7.内蒙古  8.黑龙江 9.吉林 
10.辽宁  11.北京 12天津  13.河北 14.山东  15.河南  16.好听但不出名的歌山西 17.陕西 18.安徽  19.江苏   
20.上海  21.浙江  22.江西 23.湖北 24.湖南  25.贵州 26.广西27.广东    28.福建 29.海南 30.澳门 31.香港 32.台湾 33.重庆 34.新疆                       
像素坐标如下：
Columns 1 through 11 
  100  187  201  187  221  202  258  352  346  336  290
  211  265  214  158  142  165  121    66    85  106  127
Columns 12 through 22 
  297  278  296  274  265  239  302  316  334  325  293
  135  147  158  177  148  182  203  199  206  215  233
Columns 23 through 33 
  280  271  221  233  275  322  250  277  286  342  220
  216  238  253  287  285  254  315  293  290  263  226
  Column 34 104 77
二、遗传算法的介绍
2.1 遗传算法
遗传算法的基本原理是通过作用于染体上的基因寻好的染体来求解问题，它需要对算法所产生的每个染体进行评价，并基于适应度值来选择染体，使适应性好的染体有更多的繁殖机会，在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即
染体，形成初始种；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗产操作后的个体集合形成下一代新的种，对这个新的种进行下一轮的进化。
2.2 遗传算法的过程
遗传算法的基本过程是：
1. 初始化体。
2. 计算体上每个个体的适应度值
3. 由个体适应度值所决定的某个规则选择将进入下一代个体。
4. 按概率Pc进行交叉操作。
5. 按概率Pm进行变异操作。
6. 没有满足某种停止条件，则转第2步，否则进入第7步。
7. 输出种中适应度值最优的染体作为问题的满意解或最优界。
停止条件有两种：一是完成了预先给定的进化代数则停止；二是种中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。遗传算法过程图如图2
沈星照片大全
图2  遗传算法过程框图
小彬彬离婚
三、 遗传算法解决TSP问题的Matlab程序实现
3.1 程序初始化
程序首先读入34个省会城市坐标，计算任意两个城市的距离：
设置遗传算法控制参数。
clear all;clc;clf; 
load(‘testdata.mat’);
nlen=length(x1);
xy=[x1;y1]';
n = 500;  %种数目
C = 5000;  %进化迭代次数
m=2;      %适应度归一化淘汰加速指数，取值不宜太大
alpha=0.8;  %李婷宜个人资料淘汰保护指数，范围0~1，为1时关闭保护