【老生谈算法】matlab实现遗传算法求解TSP问题.doc资源-CSDN文库

版权申诉

5星 · 超过95%的资源 94 浏览量 2023-06-09 21:05:07 上传评论收藏 320KB DOC 举报

资源推荐

资源详情

资源评论

遗传算法求解 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. 输出种群中适应度值最优的染色体作为问题的满意解或最优界。

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余7页未读，立即下载

内容反馈

版权申诉

2201_75292798

2023-06-20

资源使用价值高，内容详实，给了我很多新想法，感谢大佬分享~

阿里matlab建模师

粉丝: 3202
资源: 2782

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip