蚁群算法求旅行商问题

aimisiyou · 发表于 2019-1-20 11:39:18

本帖最后由 newer 于 2019-1-20 14:16 编辑

51个城市的数据，连续运行了五次，每次运行约三分钟，最好的结果是438.7465。

Lisphk · 发表于 2019-1-20 14:01:05

aimisiyou 发表于 2019-1-20 11:39
51个城市的数据，连续运行了五次，每次运行约三分钟，最好的结果是438.7465。

应该避免出现交叉吧？

aimisiyou · 发表于 2019-1-20 14:24:11

恩，存在交叉的肯定不是最短路径。将438.7465图形进行调整，得到431.9931的好结果。

newer · 发表于 2019-1-20 14:29:07

aimisiyou 发表于 2019-1-20 14:24
恩，存在交叉的肯定不是最短路径。将438.7465图形进行调整，得到431.9931的好结果。

手工调的，还是程序做的？程序能每次都做出不交叉的图形吗？

aimisiyou · 发表于 2019-1-20 14:42:10

newer 发表于 2019-1-20 14:29
手工调的，还是程序做的？程序能每次都做出不交叉的图形吗？

手工调的。出现交叉情况应该是陷入局部最值了，现在考虑的就是怎样尽量避免陷入局部最值。如果加速收敛，很容易陷入局部最值，如果收敛缓慢，虽然有利于搜到全局最优值，但运行时间又太长。矛盾的地方。

newer · 发表于 2019-1-20 14:55:10

本帖最后由 newer 于 2019-1-20 15:00 编辑

aimisiyou 发表于 2019-1-20 14:42
手工调的。出现交叉情况应该是陷入局部最值了，现在考虑的就是怎样尽量避免陷入局部最值。如果加速收敛， ...

看看你贴的那些图形，基本上都是从外面一层层往里面连的，
所以，建议，是不是你考虑下上面LOVEARX的，
1、先用凸包，一层层找点，先快速的找大的，因为你蚂蚁了很长时间，最后还是要走凸包的路径，时间没必要耗费，
2、每层连接的地方和一层内具体连的时候，在用你的蚁群算法，

这样综合起来，效率能最高。现在一些具体的实际的应用，比如导航，肯定不会让用户等上好多分钟的，这样的话就没人用了，市场就给你淘汰了。他们肯定不是纯的随机算法的。肯定要有优化在里面。

aimisiyou · 发表于 2019-1-20 15:01:39

newer 发表于 2019-1-20 14:55
看看你贴的那些图形，基本上都是从外面一层层往里面连的，
所以，建议，是不是你考虑下上面LOVEARX的， ...

不是从外往里面连的，只是按边上信息素浓度高的路径连在一起，起始点蚂蚁随机落在各个点上，然后按转移概率选择路径，过程是随机的。不过我也觉得蚂蚁起始点落在凸包顶点集上对运算结果会更好。

newer · 发表于 2019-1-20 15:04:12

本帖最后由 newer 于 2019-1-20 15:06 编辑

aimisiyou 发表于 2019-1-20 15:01
不是从外往里面连的，只是按边上信息素浓度高的路径连在一起，起始点蚂蚁随机落在各个点上，然后按转移概 ...

那你就试试把凸包加进去考虑，写写代码测试下
很多时候，并不是最短路径就是最优的，还要考虑时间、图形是否好看等其他因素，我们要的是相对的最优解。

xinrstar · 发表于 2019-1-20 16:55:23

留记号

aimisiyou · 发表于 2019-1-20 22:02:44

本帖最后由 aimisiyou 于 2019-1-21 07:57 编辑

本来想着怎么优化蚁群算法的，在纸上胡乱画了下，顿时就打消了。这不就是指派问题吗？！！！令Pii的距离为无穷大，也就是在距离矩阵上每行每列上只取一个，使得总和最小？好像有些限制，如不能出现关于斜对角对称的选项，如选了P13，就不能存在P31。有点类似八皇后问题。

aimisiyou · 发表于 2019-1-21 00:03:22

本帖最后由 aimisiyou 于 2019-1-21 01:15 编辑

来模拟个半自动法，先生成点集的最小生成树，然后按照尽量延长主线路的方法（尽量让更多的边留在最小生成树上）最终形成回路（语言不好描述。1、若增加一天边后形成回路，则减去原来中的一条边，两者差值尽量小；2、优先处理主线上分支较少的区域，保证增边与减边的差值最小；对于度数比较多的点，处理的情形要多些。）

aimisiyou · 发表于 2019-1-21 00:52:14

对于分支较多且分支长度较长的情形就不好处理了。

aimisiyou · 发表于 2019-1-21 12:51:56

根据最小生成树定义，若将其中一条边断开，过该边上一点补上一条不在原支撑树上的边（仍保持全点联通），显然是个非减过程。

aimisiyou · 发表于 2019-1-21 14:52:30

本帖最后由 aimisiyou 于 2019-1-21 14:59 编辑

似乎之前的感觉是错误的，应该从短路径可能性多的节点开始搜索。蚁群算法应该将起始点落在最小生成树上度数较多的节点上，因为通过它的路径更多，若放在后面搜素，会因前面信息素更新累积导致通过该点的边的信息素对比悬殊，也就扼杀了过其他边的路径（可能比目前路径更短），陷入局部最值。

aimisiyou · 发表于 2019-1-21 21:51:39

可以先根据最小支撑树找出里面度数大于2的节点，初始时将蚂蚁随机洒落在这些节点上开始寻找最短路径。

账号		自动登录	找回密码
密码			立即注册

[研讨] 蚁群算法求旅行商问题

点评

点评

点评

点评

点评