遗传算法求解TSP问题MATLAB实现
摘要：旅行商问题（TSP）是一个经典的优化组合问题，本文采用遗传算法来求解TSP问题，深入讨论了
遗传算法解决TSP问题的求解过程，并通过MATLAB对算法进行了实现，最后对实验结果进行分析，并与粒子群算法进行对比和分析。
关键字：TSP；遗传算法；粒子群算法
0引言
旅行商问题是一个经典的优化组合问题，它可以扩展到很多问题，如电路布线、输油管路铺设等，但是，由于TSP问题的可行解数目与城市数目N是成指数型增长的，是一个NP难问题，因而一般只能近似求解，遗传算法（GA）是求解该问题的较有效的方法之一，当然还有如粒子群算法，蚁群算法，神经网络算法等优化算法也可以进行求解。遗传算法是美国学者Holla
d根据自然界“物竞天择，适者生存”现象而提出的一种随机搜索算法，本文采用MATLAB来实现遗传算法解决TSP问题。
1旅行商问题
旅行商问题可以具体描述为：已知
个城市之间的相互距离，现有一个推销员从某一个城市出发，必须遍访这
个城市，并且每个城市只能访问一次，最后又必须返回到出发城市，如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短。用图论术语来表示，就是有一个图gve其中v是定点5，e是边集，设ddij是有顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的最短距离的回路。若对与城市vv1v2v3…v
的一个访问顺序为tt1t2t3…t
，其中ti∈vi12
且记t
1t1则旅行上问题的数学模型为式1：
mi
Idtiti1i1
（1）
2遗传算法与粒子群算法
21遗传算法遗传算法的基本原理是通过作用于染色体上的基因寻找好的染色体来求解问题，它需要
对算法所产生的每个染色体进行评价，并基于适应度值来选择染色体，使适应性好的染色体有更多的繁殖机会，在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种群；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗产操作后的个体集合形成下一代新的种群，对这个新的种群进行下一轮的进化。22遗传算法的过程遗传算法的基本过程是：1初始化群体。2计算群体上每个个体的适应度值3由个体适应度值所决定的某个规则选择将进入下一代个体。4按概率Pc进行交叉操作。5按概率Pm进行变异操作。6没有满足某种停止条件，则转第2步，否则进入第7步。
f7输出种群中适应度值最优的染色体作r