ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 效率神器,一键搞定繁琐工作
HR薪酬管理数字化实战 Excel 2021函数公式学习大典 Excel数据透视表实战秘技 打造核心竞争力的职场宝典
让更多数据处理,一键完成 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
用ChatGPT与VBA一键搞定Excel WPS表格从入门到精通 Excel VBA经典代码实践指南
楼主: 灰袍法师

[原创] 学习共享:高级蚁群算法求解1000以上城市的TSP问题(旅行商),附大量TSPLIB数据!

  [复制链接]

TA的精华主题

TA的得分主题

发表于 2013-7-3 13:01 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
本帖已被收录到知识树中,索引项:
imcjp 发表于 2013-7-2 00:33
你3opt里应该没调用2opt吧。所以3opt里包含2opt也是必要的。因为,换3个位置的结果,并不一定比换2个位置 ...

还有,这个算法没必要每次迭代都进行信息素挥发操作,因为这一步是O(N^2)的算法。只需要累积200次左右再进行一次信息素的挥发操作,可以使得算法中O(N^2)的操作次数大大减少。这样可以节省很多时间。
由于每只蚂蚁的搜索过程在优化过后是O(N)的,因此当数据一大,刚才的优化就会很明显。
PS:3opt算法优化后也是O(N)的,因为搜索邻域的数量为K。那么复杂度大致为N*K*K

TA的精华主题

TA的得分主题

发表于 2013-7-3 13:05 | 显示全部楼层
灰袍法师 发表于 2013-7-2 00:31
确实是代码有错误,正确的代码要把这里的第三行删掉
Sub regen_pheromone()
Dim u As Long, v As Long, ...

还有邻域搜索时也要优化才能保证是O(N)的复杂度,因为如果遍历donchecked数组的话,最差情况是O(N^2)。应该用链表保存可以被check的点。就不会有一大堆无用的循环了。

TA的精华主题

TA的得分主题

发表于 2013-7-3 13:08 | 显示全部楼层
灰袍法师 发表于 2013-7-2 00:31
确实是代码有错误,正确的代码要把这里的第三行删掉
Sub regen_pheromone()
Dim u As Long, v As Long, ...

我用1000个点测试过,无用循环(donchecked为true时跳过该点)达10W次。而有用循环就1200左右。虽然无用循环单次不占什么时间,但是数据一大,它占的时间将会远远大于有用循环。

点评

有道理,等我再看看。  发表于 2013-7-3 18:55

TA的精华主题

TA的得分主题

发表于 2013-8-10 16:55 | 显示全部楼层
为什么我用你的随机贪婪法最快。

点评

本来就是随机贪婪最快,不过求解精度最低。  发表于 2013-8-10 19:16

TA的精华主题

TA的得分主题

发表于 2013-8-12 21:42 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2013-8-13 12:45 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2013-8-13 16:01 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2013-8-18 07:55 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
zdqwy19 发表于 2013-8-10 16:55
为什么我用你的随机贪婪法最快。

谢谢点评,我想在cad中使用,连接点

TA的精华主题

TA的得分主题

发表于 2013-8-23 17:27 | 显示全部楼层
法师~如果只有城市间的距离,没有坐标。蚁群还能用不?有没个例子我参考一下?

点评

多读入一个距离矩阵,然后程序中“计算距离”的代码,全部改为“查找距离”的代码即可。改起来是比较烦。。。。。。  发表于 2013-8-23 19:20

TA的精华主题

TA的得分主题

发表于 2013-8-29 08:39 | 显示全部楼层
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2024-11-29 05:34 , Processed in 0.060931 second(s), 11 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

沪公网安备 31011702000001号 沪ICP备11019229号-2

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:李志群律师

快速回复 返回顶部 返回列表