【TSP问题】基于模拟退火结合遗传算法求解旅行商问题matlab源码.pdf
需积分: 5 144 浏览量
2021-09-24
13:00:18
上传
评论
收藏 822KB PDF 举报
【TSP问题】基于模拟退火结合遗传算法求解旅行商问题matlab
源码
1 算法介绍
1.1 TSP介绍
“旅行商问题”(Traveling Salesman Problem,TSP)可简单描述为：一位销售商从n个城市中的某一城市出
发，不重复地走完其余n-1个城市并回到原出发点，在所有可能路径中求出路径长度最短的一条。
旅行商的路线可以看作是对n城市所设计的一个环形，或者是对一列n个城市的排列。由于对n个城市所有
可能的遍历数目可达(n-1)!个，因此解决这个问题需要O(n!)的计算时间。而由美国密执根大学的Holland教
授发展起来的遗传算法，是一种求解问题的高效并行全局搜索方法，能够解决复杂的全局优化问题，解决
TSP问题也成为遗传算法界的一个目标。
1.2 遗传算法求解tsp模型
巡回旅行商问题(TSP)是一个组合优化方面的问题，已经成为测试组合优化新算法的标准问题。应用遗传算
法解决 TSP 问题，首先对访问城市序列进行排列组合的方法编码，这保证了每个城市经过且只经过一次。
接着生成初始种群，并计算适应度函数，即计算遍历所有城市的距离。然后用最优保存法确定选择算子，
以保证优秀个体直接复制到下一代。采用有序交叉和倒置变异法确定交叉算子和变异算子。
算法流程
评论0