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

aoe1981

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



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实现（年纪大了，对其他的编程语言不再那么激动了），以检验一下该算法的“质量”或“性能”。

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







先对比一下效果，以225座城市的数据为例（已知最优解3916）：

大师的MMAS算法，用时254.47秒，得到3919：





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


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






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





只得到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, 下载次数: 43)

2020-3-5 19:10 上传

点击文件名下载附件

（大师的附件，转载）

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

位于1楼：

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

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

2020-3-5 19:13 上传

点击文件名下载附件

（大师提供的数据，转载）

最后是我的学习附件：


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

2020-3-5 19:15 上传

点击文件名下载附件

承蒙大家多指教。


（最新附件在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楼。蚁群反成了本帖目前最值得自夸的东西，至于综合运用效果，大家评判。）

ivccav

恭喜葛优兄弟，研究越来越深刻了

yxbaju

看不懂,看不懂,还不够十个字

aoe1981

还有一点值得一提：

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的二维数表，要排序完成，也要耗费许多时间。每换一个基点城市，这个步骤都得重新做一遍，这恐怕也是程序效率不高的一个原因。但是这不是主要的，更慢的是字符串的连接、拆分，是更为要命的。


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

aoe1981

主楼一个介绍糊涂了：本帖附件的两大规模，程序运行效率的两座大山

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，图如下：



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



也不知道这两张图差在什么地方呢？（就当是一个找不同的游戏吧，哈哈）

FOB_FN_L

aoe1981 发表于 2020-3-5 23:36
主楼一个介绍糊涂了：本帖附件的两大规模，程序运行效率的两座大山

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

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

astupig

灰袍法师的算法研究确实是顶级的~ 我也拜读了很多法师的帖子，获益良多！
希望法师可以重出江湖~

aoe1981

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+旋转、对称变换”，但是不太清楚旋转、对称变化的时机和频率。故而我只做了“标准情况”，也就是这个图：




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

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

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

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

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

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

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






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

2.lin318        42029可以达到43031：





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







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





呵呵呵，还是法师会作法！！！

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

（不管还能不能再提高，升级版附件我后面是会发的）

aoe1981

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






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

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






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

aoe1981

下面的测试我用的是法师提供的测试数据中规模最大的一组：u2319        :        234256


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

法师的：





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

我的逐次优化如下：

初始数据l图：


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



第一轮优化图：



第二轮优化图：



第三轮优化图：



最终数据如下图：




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

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





这时的图看起来少了许多斜线：



牛！！！

再过一些日子就不折腾了，发了我依然幼稚的附件。