致敬淡出的大师:五种算法(CW节约、随机贪婪、插入、蚁群、交换优化)求解TSP旅行商问题

FOB_FN_L

aoe1981 发表于 2020-3-24 20:29
附件当中英文太多，没怎么看懂……

观察下图：

我也没看懂，那个原作者和您老人家差不多，那作者也还有个数独的例子的，

Simonflying

高人，厉害了。mark下，留着以后学习

aoe1981

FOB_FN_L 发表于 2020-3-24 20:34
我也没看懂，那个原作者和您老人家差不多，那作者也还有个数独的例子的，

不过，这些所谓“一般情况”，我目前能想到的有两种：

1.某两个城市之间不连通的：可以人为设置这两个城市之间的距离为一个巨大数，比如9e+307；

2.由A到B和由B到A距离不同时，放弃根据城市坐标计算“欧氏对称距离”的办法，直接读取事先录入好的二维距离矩阵，比如您提供的附件中的44*44的二维表格中的数据。

然后，哈哈，程序就可以通用了。

FOB_FN_L

aoe1981 发表于 2020-3-24 20:56
不过，这些所谓“一般情况”，我目前能想到的有两种：

1.某两个城市之间不连通的：可以人为设置这两个 ...

这我就不知道了，您老人家慢慢研究~~这个虽是打着旅行的TITLE，但在我看来，实际应用还真不在旅行上，因为我以前也总出差，实际应用中，旅行上用这个还真玩不转~~~

FOB_FN_L

想起个事，您的那数独的应该写成个手机上的小应用，有些公司拿数独当作面试题考那些会计或出纳的岗位的人，

aoe1981

FOB_FN_L 发表于 2020-3-24 22:12
想起个事，您的那数独的应该写成个手机上的小应用，有些公司拿数独当作面试题考那些会计或出纳的岗位的人，

我不懂那些语言，手机上类似应用很多啊，我都试玩了好几款。

aimisiyou

tsp问题网上好像是说遗传算法最好吧，100以内的小规模我用lisp实现了，没有优化，运行10分钟以内。设置N_d=3000，得到pr76的较好解108155.6347。

aimisiyou

蚂蚁算法的鲁棒性很强，原理根据不同路径上的信息素变化，蚂蚁越来越趋向于走信息素高的边，这也容易导致陷入局部最优解。如果前期加快收敛，后期放缓收敛，更利于搜到全局最优路径。例如如果当次循环中最长路径高出最短路径10%，更新所有边的信息素就按经过改该条边上所有蚂蚁路径的倒数和（如某条边上有蚂蚁1和蚂蚁2经过，该边上的信息素更新=0.1*该边原来信息素+0.9*（1/L1+1/L2）。如果当次循环中最长路径比最短路径不超过10%，更新所有边的信息素就按经过该条边上所有蚂蚁路径的倒数和的平均值（如某条边上有蚂蚁1、蚂蚁2和蚂蚁3经过，该表边上的信息素更新=0.1*该边原来的信息素+0.9*（（1/L1+1/L2+1/L3）/3），这样就实现前期加速收敛，后期放缓收敛，尽量减少陷入局部最值。
之前仅用单纯的蚁群算法算出的结果质量很差，就放弃了蚁群算法。

aoe1981

aimisiyou 发表于 2020-3-25 15:00
tsp问题网上好像是说遗传算法最好吧，100以内的小规模我用lisp实现了，没有优化，运行10分钟以内。设置N_d= ...

我只能得到：108159.44，资料中给出的最优解是：108159，我和法师的结果一样：



开了阉割优化，不开的话，我的蚁群40只蚂蚁500代最好可以到108343左右。



这个图为了占满地方，没有设计成横轴与纵轴同单位刻度的，看起来上下方向拉伸了。




这是法师的，和我的结果一样。


结果是（城市序号）：

46        45        44        48        47        69        68        70        67        50        49        51        66        65        71        72        73        64        63        62        61        41        60        59        58        57        56        55        52        53        54        42        43        28        27        26        20        19        31        30        29        32        33        35        34        40        39        38        36        37        18        17        16        15        74        14        13        12        11        10        9        8        7        6        5        4        3        2        75        76        1        23        22        21        25        24



数据源：

http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/pr76.tsp


兄台厉害啊。

aoe1981

aimisiyou 发表于 2020-3-25 15:00
tsp问题网上好像是说遗传算法最好吧，100以内的小规模我用lisp实现了，没有优化，运行10分钟以内。设置N_d= ...

其实我做的交换优化算法可以应用于遗传算法的“变异”演化的，这样变异出来的都是优良个体，但是我一直没想好：如何让“交叉”出来的个体一定或大概率超过其父代的基因？


遗传算法的关键之处我以为是：如何根据父代基因交叉生成优异的下代基因，只有实现一代更比一代强，才会让算法收敛，防止退化或原地打转。


所以，目前没有动手去写。