【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 问题,首先对访问城市序列进行排列组合的方法编码,这保证了每个城市经过且只经过一
次。接着生成初始种群,并计算适应度函数,即计算遍历所有城市的距离。然后用最优保存法确定选择
算子,以保证优秀个体直接复制到下一代。采用有序交叉和倒置变异法确定交叉算子和变异算子。
算法流程