ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
HR薪酬管理数字化实战 Excel 2021函数公式学习大典 Excel数据透视表实战秘技 打造核心竞争力的职场宝典
300集Office 2010微视频教程 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
用ChatGPT与VBA一键搞定Excel WPS表格从入门到精通 Excel VBA经典代码实践指南
查看: 11323|回复: 64

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

[复制链接]

TA的精华主题

TA的得分主题

发表于 2020-3-5 19:15 | 显示全部楼层 |阅读模式
本帖已被收录到知识树中,索引项:其他结构和算法
本帖最后由 aoe1981 于 2020-4-11 16:37 编辑

TSP(旅行商问题)我一直惦记在心里。
早在2014年我发一个帖子,有点幼稚,大师这样回复我:

大师回复.PNG

http://club.excelhome.net/forum. ... 1118081&pid=7614127

原因是更早两年,大师的精华帖已然名震EH,我当时只是懒惰没有搜索,竟是不知:

学习共享:高级蚁群算法求解1000以上城市的TSP问题(旅行商),附大量TSPLIB数据!
http://club.excelhome.net/thread-825313-1-1.html
(出处: ExcelHome技术论坛)


后来拜读大师高帖,囫囵吞枣,稀里糊涂,没能理解其中精妙于万一。

近日偶然读到一个算法:叫做C-W节约算法,是启发式算法的一种,可以解决TSP,而且算理容易理解,便迫于用VBA实现(年纪大了,对其他的编程语言不再那么激动了),以检验一下该算法的“质量”或“性能”。

继“数独”后,又折腾几日,算是实现了,发个帖,一道表达对大师的怀念。



附件一角.PNG



先对比一下效果,以225座城市的数据为例(已知最优解3916):

大师的MMAS算法,用时254.47秒,得到3919:


大师的效果.PNG


绘出了漂亮的“TSP”,深度优化后的“高级蚁群算法”,使解的质量大幅提升!!!


大师的随机+贪婪算法,用时0.25秒,得到3990,我怎么更喜欢这个算法,不明其中原理,是不是用递归的办法,但每次用贪婪法加随机法择取其中若干条路径,而不是(n-1)条路径逐条测试?有工夫了我写个这样思路的,效果图如下:


大师随机贪婪.PNG



最后是我做的这个“C-W节约算法”:


附件效果.PNG


只得到4018的极限结果。为何说“极限”?是因为该算法所有可能我已穷尽,不可能更优,这是这个算法的“顶级质量”。

至于效率,如果遍历225个城市作为基点城市,是一定会得出4018解的,如果随机50个城市作基点城市,则是运气型的,有次我用35秒撞出了4018解。

这个效率不代表C-W算法的效率。我首先追求的是VBA实现,但苦于缺乏良好的数据结构的知识和技巧,算法中的实现技巧便只依赖于“大量的字符串的连接、拆分”来实现,这样使得我写的C-W节约算法效率低下。我一直渴望找到“占有空间不大、效率高”的数据结构,但实在黔驴技穷,找不出来。如果改用数组,避免字符串连接,则又会白白占用大量的空间,我没想好怎么避免。

C-W节约算法大约是这样的:任选一个城市作为基点城市,与其余n-1个城市作弧,共n-1条弧,作为初始路径距离(添加进路径组,该路径组逐渐递减、收敛为1条,即为最终结果),长度为2倍弧的总长,此时,显然不是一条环路。

接下来对其余除基点城市以外的(n-1)个城市两两作弧(我在附件中统统叫“边”,因为我们假设“A到B”和“B到A”是一样的,而且我们就以点到点的欧式距离而非实际距离为长度),一共可以作:(n-1)*(n-2)/2条弧,这些弧要全部录入进字典。如果是1000座城市,则要录入498501条边的信息,根据以往了解,超过100万时,字典效率会急剧下降,但我也只是听说。

然后,对每条弧计算“节约值”,指彼此连接后,与基点形成的环路比原来的两条弧的总长能减少多少距离。举例说:基点G,弧1:G-A-G,弧2:G-B-G,连成环路:G-A-B-G,看其“节约值”有多少。

算法的核心巧妙之处在于:将所有弧的节约值从大到小排序,然后逐次插入到“初始路径组”中,成功插入一条,原路径组就递减1条,(n-2)次后便收敛出最终结果。

至于“插入原则”,读到的资料中只淡淡地给出了两条:
1.弧两端不在同一条路径中;
2.弧两端都与基点相邻接。

然而,在我仔细研究中却发现,至少有四种具体情况要处理,当然这恐怕也和我的代码实现方式相关。算了,这部分就不谈了。我的附件代码、注释公开,各取其便吧。

下面是大师的最佳附件,便于大家对比,不算我偷盗哦!

位于17楼:

http://club.excelhome.net/forum. ... =825313&pid=5708537


各种版本的增强蚁群算法 3opt 加速技巧.zip (172.73 KB, 下载次数: 39)

(大师的附件,转载)

下面是大师提供的测试数据,大师的附件预留了3000行位置,寓意可以方便测试3000以内城市规模,我不敢造次,只预留了1200行。

位于1楼:

http://club.excelhome.net/thread-825313-1-1.html

TSPLIB数据.zip (113.09 KB, 下载次数: 25)

(大师提供的数据,转载)

最后是我的学习附件:


C-W节约算法_求解TSP_aoe1981.zip (105.01 KB, 下载次数: 28)


承蒙大家多指教。


(最新附件在11楼,这个附件可以下岗了  20200313)

最强附件在17楼:

http://club.excelhome.net/forum. ... 524335&pid=10269119

以17楼附件为准,其他留作纪念,无需下载。——20200327

以17楼附件为准,其他留作纪念,无需下载。——20200327

以17楼附件为准,其他留作纪念,无需下载。——20200327

折腾半月余,就此打住,仍有提升空间,留待猴年马月。所谓“最强”,只是吹嘘:

1.数据tsp225被我刷出了新的结果(3859,其实相当于3919,距离最优解3916只有3),事实上,200左右规模城市十分容易求得最优解;

2.我的“交换优化算法”性能可比法师的“邻域搜索优化算法”,很多情况下还会胜出,其余如各种蚁群算法、代码架构、代码效率,大师仍旧令我景仰;


3.我的伪MMAS(增加了自创的“算法停滞检测和信息素重置”的处理办法,效果十分好)收到了比法师的真MMAS(最大最小蚁群算法)更好的效果(单用蚁群算法,不用绑定优化算法时对比)。

罢了。
(增加了“插入法”,凑成了“五种”算法——20200411)

(帖中最强算法是:蚁群算法,前提是:单用比较,给足时间,只对比解的质量。其中蚁群糅合了:MMAS与BWAS,胡乱瞎折腾,收效甚好,调好参数,后楼所述400构造数据亦可得精确最优解400,200左右城市规模蚁群单用几乎可得最优解。最新附件仍在17楼。蚁群反成了本帖目前最值得自夸的东西,至于综合运用效果,大家评判。)

评分

12

查看全部评分

TA的精华主题

TA的得分主题

发表于 2020-3-5 19:23 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
恭喜葛优兄弟,研究越来越深刻了

评分

1

查看全部评分

TA的精华主题

TA的得分主题

发表于 2020-3-5 19:25 | 显示全部楼层

TA的精华主题

TA的得分主题

 楼主| 发表于 2020-3-5 19:34 | 显示全部楼层
本帖最后由 aoe1981 于 2020-3-5 19:37 编辑

还有一点值得一提:

C-W节约算法的核心巧妙之处在于,将(n-1)*(n-2)/2条弧的节约值从大到小排序。如果有1000座城市的规模,将有这样的498501条弧。我在附件中用一个m行3列的数组盛放弧的“节约值”,第1列为弧的起点,第2列为弧的终点,第3列为节约值。1000个城市规模时,m=498501。

我习惯于用“双循环排序”,尽管之前也学做过许多排序,但依旧会惯性使然。

结果这次确是不行了,我便搬来了我之前做的基于归并的二维数据多key排序,这是我当时自认为“最快的稳定排序”:


基于归并排序的稳定二维数据表多key排序学习
http://club.excelhome.net/thread-1502139-1-1.html
(出处: ExcelHome技术论坛)



然而,尽管如此,一个50万乘3的二维数表,要排序完成,也要耗费许多时间。每换一个基点城市,这个步骤都得重新做一遍,这恐怕也是程序效率不高的一个原因。但是这不是主要的,更慢的是字符串的连接、拆分,是更为要命的。


哈哈,还是那句话:实现了就行,这是第一步。

评分

1

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2020-3-5 23:36 | 显示全部楼层
主楼一个介绍糊涂了:本帖附件的两大规模,程序运行效率的两座大山

1.录入字典规模:n*(n-1)/2条边,这还是假定A到B和B到A一样的情况下,以1000个城市为例,需录入1000*999/2=499500条边;

2.排序数组规模(盛放弧的节约值):(n-1)*(n-2)/2行3列,以1000个城市为例,数组将有999*998/2=498501行。

主楼把二者搞混了。
另外,借着刷的这层楼,再对比一组数据:

ch130        :        6110


法师的MMAS用时93.39秒直接就是最优解6110,图如下:

6110.PNG

这组数据规模在我的附件可接受的范围内,我遍历完了130个基点城市,用时19.16秒,得到6299的结果,图如下:

6299.PNG

也不知道这两张图差在什么地方呢?(就当是一个找不同的游戏吧,哈哈)

评分

1

查看全部评分

TA的精华主题

TA的得分主题

发表于 2020-3-6 05:50 | 显示全部楼层
aoe1981 发表于 2020-3-5 23:36
主楼一个介绍糊涂了:本帖附件的两大规模,程序运行效率的两座大山

1.录入字典规模:n*(n-1)/2条边,这 ...

一个美术大师蛋生了,恭喜~~

评分

1

查看全部评分

TA的精华主题

TA的得分主题

发表于 2020-3-6 08:46 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
灰袍法师的算法研究确实是顶级的~ 我也拜读了很多法师的帖子,获益良多!
希望法师可以重出江湖~

评分

1

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2020-3-7 22:45 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
C-W算法的求解质量让我有点失望,同时,我写的C-W效率更是让人捉急,我一直想优化。

经过仔细对比研究法师早期和最强附件,一个在1楼,一个在17楼。当我对比1楼附件中的算法时,似乎找到了信心。

我又写出了我所理解的“随机贪婪法”,大意是:每次列出当前城市最接近的未到达城市,不一定完全贪婪,每次只选最近,而是根据允许的最大“分叉”选择数,随机取其中一条,由此生成个10、20条路径,沉淀其较优者。如果时间允许,可以尝试更多。由于我不再考虑“算法的通用性”,比如:城市间的连通限制、实际距离的输入……只考虑“n阶完全图”的假设,便可以较简单的实现这个“随机贪婪算法”,甚至不用字典,使得代码只有50多行。

但我对解的质量依然不满,“随机贪婪法”甚至不如C-W,如果要赛过解的质量,则会输掉时间。于是也便懒得发了。好在,比起法师1楼初步附件,确是一个水平。

“蚁群算法”我不懂,也算是一种启发式近似算法,它的性能其实也不是特别出众,CW的解的质量是可以穷尽其算法极限的,因为没有随机的一丝一毫成分,蚁群的结果却是“稳定中有弹性”的,但是二者其实算是同一个水平(此句我仅凭感觉)。

让蚁群算法如虎添翼的是:法师发明的“2_opt、3_opt邻域搜索优化算法”,这个算法纵使单独反复使用,直到不能优化任何一次时,其解的质量也是不错的。不单是让“蚁群算法”虎虎生威,就是让“随机贪婪算法”也倍增强悍。法师曾言:单独的蚁群是很废的,单独的邻域搜索也是很废的。这是拿二者合力后产生的优良结果对比的。其实我更加感觉“邻域搜索优化算法”的强悍,单用这个就秒杀CW和随机贪婪了!当然,在蚁群、CW、随机贪婪的基础上进行邻域搜索优化,效率会更高,算是“站在巨人的肩膀上”。

法师所以取名“邻域”,主要是为了效率的考虑(我90%以上确定,我没研究法师的代码,因为看不懂,但我看差不多了法师描述的算法,并有自己的理解和实践,所以这样说),法师的附件中也是"3_opt FULL"这样的选择,极端费时,1173个城市的那组数据已知最优解是56892,我用法师17楼最强附件开足火力,反复单用领域搜索,在“3_opt FAST”反复一次不能优化时最终得到59553的结果,最后又来了一次"3_opt FULL",用时3800多秒,优化到59483,这个结果许多能叫上名堂的算法也多半干瞪眼!所以我说:“邻域搜索”才是法师高帖的精妙所在,蚁群、遗传、退火啊的,总感觉有些被虚吹了一些,虽然我没做过这些算法,但从已知的结果来看,稀松平常。

法师所谓“邻域搜索优化”,我总感觉应该叫做“交换优化”!我想起了以前做过的“均衡分班”,随机交换、优化,效果竟是很神奇,最早的思想也是源自法师。我想法师的这些算法思想是一脉相承的,尤其当看到其法师附件中的“FULL”时,我更是信了这一点。所谓“邻域”,只是有针对性的尝试交换比较接近的城市,而不是“遍历”性的,但FULL就成遍历了(我90%以上这样猜),因此“邻域”一词是可以丢掉的,“搜索”也是普通,唯其实质是:“路径的交换优化”!

路径的交换并不简单,这比“均衡分班”难了不老少,每次成功的交换应该满足两方面条件(算是我的学习心得,一并和盘托出,向法师学习,同时也请众坛友指教):

1.交换后的路径总长度要比原来减少;
2.交换后的路径仍旧是一条“环路”,不能形成“两个环”或更多环。

我应该是仿做成功了“2_opt”,因为这个简单,主要在5楼介绍:

http://club.excelhome.net/forum. ... 313&pid=5644737


这个算法直观的作用是:消除“交叉路径”。缺点是:很快会限入停滞,不能自拔。

能够打破困局的是“3_opt”,可以让交换搜索绝处逢生,进而带动“2_opt”继续产生优化。这个主要在17楼介绍:

http://club.excelhome.net/forum. ... 313&pid=5708537


我算是仿写了三分之一的“3_opt”,法师将原本“3_opt”的多种情况,在旋转、对称变换的帮助下,简化成了三种情形,分别实现,看了让人害怕。我竟发现后两种情形居然等价于“2_opt+旋转、对称变换”,但是不太清楚旋转、对称变化的时机和频率。故而我只做了“标准情况”,也就是这个图:

标准情况.PNG


从我使用的情况来看,我应该是做成功了,没有出现运行错误,也能够在2_opt反得不能再优化时,进一步创造出优化机会,属于开拓型的算法。

但是…………………………………………………………

我做的功力弱多了……………………………………

我丢掉了“邻域”,以遍历为主,用参数控制交换探测的最远路径段数,控制最大交换路径段数,实现耗时可控。一次200秒优化100次,给人的感觉是不如每次4、5秒,优化10、20次的,多点几次而已。

我做的还是有点效果的,如果单独使用“交换优化”,也会秒掉我做的CW、随机贪婪法的,尤其当城市规模数大时,比如:1173城市时,是可以轻松优化到62000以内的(别忘了,上文说过,法师的单用邻域搜索可以达到极致的59483),这是我写的CW、贪婪所不能比拟的。当然在小规模数据比如200以内,由于“遍历基点城市”的耗时可以等待,CW会优异一些。

今天,我先不打算上最新附件了,因为这个附件我还不满意,只上一些图:

1.最优解3916的TSP225我达到了3931,图如下:

改进尚未成形附件一角225.PNG


改进效果225-3931.PNG

这个图不太漂亮,但确实短了,找不到交叉路径。

2.lin318        42029可以达到43031:

318.PNG

318-43031.PNG

3.这个att532        :        86729的试了多次只达到了90498,时间太长,没再全力测试:

532.PNG


532-90498.PNG


看看法师的单用“邻域搜索”的效果,轻松破9万,我没闯进去:

法师的.PNG



呵呵呵,还是法师会作法!!!

我得再学学,希望能克服恐惧的心情,哈哈。

(不管还能不能再提高,升级版附件我后面是会发的)



评分

1

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2020-3-8 13:19 | 显示全部楼层
现在,我感觉已经将法师的“2_opt、3_opt邻域搜索优化”已经仿写的差不多了,只是在细节处理上还欠点火候,在大框架上应该是对的。
225最优结果3916的,我可以得到3918了,差那么1点几,死活出不来,也说不定正是这一星半点,我和法师的附件便差着一大截:

225-3918.PNG


225图.PNG

虽然数字很接近了,但看着这个“TSP”的图,更丑了。

1173的最优结果56892我真得不敢想象,但是我仅用我的“交换优化算法”,居然达到了59673,就在上楼这个结果停留在62000以内,现在更优了。但是,同样和法师附件中单用“邻域搜索优化算法”的最佳结果59483,差着一星半点,说不定实际情况还真是一大截。这组数据使我感觉:也不要过分迷信“优化算法”的威力,法师将其与“蚁群算法”结合使用可以达到57000左右,两者结合才显强大。这组数据我不敢用CW遍历1173的基点城市,估计得跑一晚上,才可以出一个可以用来进一步“交换优化”的基础结果。如果只随机选择1、2个基点城市,得到的结果还破不了6万,完全不如我的“交换优化算法”,如果不要求特别精致的结果,这个交换优化算法简单可以无视CW、随机贪婪算法的存在了。图如下:

1173-59673.PNG


1173图.PNG

通过交换优化算法得到的结果虽然与最优结果还差一截,但是环游图绝对不存在“交叉”,这是其优异的地方。现在单用这个可控效率的算法,我都敢尝试3000左右规模的城市了,当然目标一是继续检测这个“交换优化算法”的性能,一是以可接受解为追求目标。趁着这股热劲,打算再磨一磨。

评分

1

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2020-3-8 22:25 | 显示全部楼层
下面的测试我用的是法师提供的测试数据中规模最大的一组:u2319        :        234256


首是单独使用我的“交换优化”和法师的“邻域搜索优化”的对比:

法师的:


2319法师.PNG


请注意:我在反复点击“邻域搜索优化3_opt FAST”直至不能优化时,又全开了一遍3_opt FULL,耗时很长,得到242804的结果。

我的逐次优化如下:

初始数据l图:
初始数据.PNG

随机贪婪1条路径后得到的图:

2319随机贪婪图.PNG

第一轮优化图:

2319第一轮优化.PNG

第二轮优化图:

2319第二轮优化.PNG

第三轮优化图:

2319第三轮优化.PNG

最终数据如下图:

效果参数.PNG


得到了240826的结果,我采用的是小步慢走多次优化的策略,法师也说过,3_opt本身是O(n^3)的,我没有采取邻域的交换策略,是遍历性质的,这样的规模根本不敢将“最远检测”和“最大交换”同时设置为2319,那样的话实在等不了。我得到这样的结果只证明了:我仿写的交换优化代码效果上是对的。

接下来是我用法师的MMAS逼近最优结果234256,我的各种算法综合起来也是没有希望破24万的,因为我的基础算法CW、随机贪婪并不强大。法师在将“蚁群”和“邻域搜索”的结合上自有高招,单从代码规模来看我的就是小儿科,我写的“交换优化”代码也就150多行。下面是法题的牛逼结果,运行了9004秒得到:235503


法师235503.PNG


这时的图看起来少了许多斜线:
法师的235503图.PNG


牛!!!

再过一些日子就不折腾了,发了我依然幼稚的附件。
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

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

GMT+8, 2024-3-29 22:52 , Processed in 0.066830 second(s), 11 queries , Gzip On, Redis On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

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

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

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