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