豫ICP备17040950号-2

遗传算法解决TSP问题

文章目录
  1. 1. TSP问题
  2. 2. 设计思路
  3. 3. 对比实验
  4. 4. 源码分享

TSP问题

旅行商问题,即TSP问题(Travelling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

设计思路

1、随机生成N的位置(坐标),把坐标点绘制到页面上。
2、设置种群规模为M,每个个体生成1到N的随机序列。
3、计算每个个体的适应度(路径总长度)。
4、寻找出当前迭代的最优解,把最优解路线绘制到页面上。
5、交叉,变异,生成新的一代种群。
6、重复3-5,直到迭代次数到达指定次数。

对比实验

TSP问题的解法,还有回溯法、分支限界法、近似算法、动态规划法、蚁群算法等。
对比遗传算法和其他算法求解TSP问题的数据量、数据分布以及实验结果(求解时间等),找出遗传算法的优缺点,适用于数据量多少,数据分布是什么情况。

然而,工作量很大,暂时搁置,完成后也能写篇不错的论文了吧。

源码分享

https://github.com/voidking/TSP_MATLAB.git
https://github.com/voidking/GA4TSPProblem.git