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

aoe1981

duquancai 发表于 2020-3-19 10:10
不介意的话：python 代码https://blog.csdn.net/wyquin/article/details/88863424

python真火，没学过啊……

aoe1981

发现了一种构造数据的办法，以后但凡要检测一种TSP算法的性能便可轻易测试了，而不再需要大费周章，找一些公认的历史数据了。

这个构造办法就是：点子图。

点子图有个特点：每一小格都是正方形，边长为1，对角线长约1.41。

构造公式如下：
=RANDBETWEEN(1,30000)

=INT((ROW()-0.1)/50)+1       

=MOD(ROW()-1,50)+1




公式1中的随机大数序列(降低重复性)是为了乱序数据而设计.

且先来看一组:

(1)3*3


以上是乱序效果.


以上是优化效果,从图中可以看出,最优结果应该是:8+1.41=9.41,只有一条斜线,像这样的小规模数据我的附件可以做到.


(2)4*4





一乱一序,最优解是:16.

(3)5*5





最优解是25.41


(4)19*19







最优解应该是:361.41,我没再花时间跑,只得到:363.9,花了近200秒.

(5)20*20







这个又是"偶数点*偶数点",最优解应该是:400,我初步得到了:404.14,花了110秒左右.

这两组数据规模可以用来测试多数TSP算法性能.

(6)50*50

这一组的最优解是:2500







我把参数调为400*400,一次优化时长:1014秒,得到:2564.62的结果.按理说,上图中应该没有斜线的,这种最短路径,人脑也是可以轻松规划出来的,但计算机显然更费劲.我所想到的方法是:反复"凹"字路线,最后像一把梳子.


这些数据的最优解是确定的,可以验证算法性能.

aoe1981

貌似我折腾出了“最强蚁群算法”（当然是和法师的最强蚁群MMAS对比），我初步对比测试发现，竟然比法师的还要强（哈哈，我累计吹过这样的牛已不在少数，法师一直很大度的，不过这次，我似乎说的是实际情况）！

关于基本蚁群（AS）、精英蚁群（EAS）、最大最小蚁群（MMAS），我在代码中是这样区分的：




AS：保留a句，注释b句；
EAS：保留a句，保留b句；
MMAS：注释a句，保留b句。

但也是有点偷懒的做法，不过一切看效果说话。

a句是给每只蚂蚁留信息素，b句是给每一代中最佳的一只蚂蚁留信息素。MMAS中，普通蚂蚁不留信息素，只给每一代中最佳蚂蚁留信息素，为此，同时采用低蒸发率（0.02左右），且对信息素进行“最大、最小”的保护性限制，太低时，强制设置为最小值，太高时，强制设置为最大值。

我的做法中，只满足MMAS的以下几条：

1.普通蚂蚁不留信息素；

2.只给每一代最佳蚂蚁留信息素；

3.使用低蒸发率（<=0.1）。

但我并未使用“最大最小信息素限制”，一是我偷懒，一是和我的信息素添加方式有关，当然最主要的是，居然这样效果更好。

我的信息素添加规则前楼有所介绍，如下：

路径段（i,j）的信息素=信息素常数Q/每一代蚂蚁的最佳路径L*di(i,j)

给出一张图介绍下：




对于att48 : 33522这组数据，在蒸发率p=0.02时（蚂蚁数50，迭代500，a=1，b=4），极易得到最优值，相比法师的各种蚁群，可谓“一骑绝尘”。

在测试其他数据时，在蒸发率：0.02~0.1之间表现差异较大。

比如：tsp225：        3916数据

我的在蒸发率0.1时反而效果最好：




法师的各版本蚁群算法中，最强的MMAS的表现如下：

p=0.1



结果是4027。

p=0.02



结果是4248。

p=0.5




结果是4354。

难道真是我幸运的误打误撞出来的？

欢迎各位坛友指正，附件同步更新在17楼。
http://club.excelhome.net/forum. ... 35&pid=10269119

（哈哈，把楼层搞错了）

aoe1981

最近我研究TSP的思路是这样的：

1.先是作出了“交换优化”，并言总体性能堪比法师的“邻域搜索优化”，且偶有胜出。

2.试做了基本蚁群算法AS，由于不满足其求解质量，胡乱折腾了一个伪MMAS（最大最小蚁群算法），又言“最强蚁群”，因为许多组实测数据（从48城市、225、532、1173各种规模都有测试对比）支持，在单独使用蚁群（不开交换优化或邻域搜索优化算法的情况下）时，的确会得到较优结果。

3.其实我的目标也是顺着法师的思路，想把“蚁群”和“交换优化”结合起来。然而我似乎走岔道了。法师的可以产生“1+1>2”的效果，我的却是不敢做“1+1”，因为法师将邻域搜索做了4个版本：2_opt FAST（快的）、2_opt FULL（满的）、3_opt FAST、3_opt FULL，并且“邻域”的限定就是为了效率与解的质量的兼顾，我自始至终是没有顾及这一点的，我所采用的“优化策略”是“环线遍历”，十分耗时，如果降低参数，会失去对“邻域”城市的覆盖，致使优化质量下降。这就是我与大师的差距！！！


然而，我终究没有在这条道上死心，想走出一条有自己特色的道路，即使效果差点也不在乎，只要说得过去就行。


我忽生一个主意，既然每一代蚁群（比如说通常设置的50只）中，四处随机搜索路径后，路径最短，排名第一的“精英蚂蚁”的路径更有价值（体现在MMAS中给其他普通蚂蚁不留信息素，只给精英蚂蚁留信息素），我何不只针对精英蚂蚁的路径进行一番“交换优化”？这样的话，相比给每一代的每一只蚂蚁的路径做优化，然后对比，应该会提速m倍，如果m为50只蚂蚁，则会提速50倍，接下来，影响交换优化次数的变量就只剩下蚁群迭代次数T了。

为了进一步提高时间效率，我进一步将我的“交换2”（其实就是3_opt）阉割了，比如将“最远检测”、“最大交换”两个影响“交换2”效率的参数设为较小值20，与邻域范围相同，寄希望于蚁群的迭代可以弥补“优化阉割”后带来的损失。

这样做还是带来了一些效果：

（1）TSP225继续刷新：3859，我都不敢相信了，赶紧拿法师的附件重新计算，发现只相当于3919（距离最优解还差3），但是这一次画出了漂亮的“TSP”，话说，法师附件中，为了接轨早期取整数据的做法，还真是有点坑，舍入误差居然可以达到让人难以置信的57（3916-3859）！！！真是奇怪，因为我始终清醒地知道，自己的水平不是那种可以反复刷新“纪录”的人！如图：



重点是大家看看这次的时间：55秒，这是我更满意的。



上图为用法师附件检验，只相当于3919，开了好几次法师的“3_opt FULL”，也没有任何优化点。



这个图承载着我这一段的梦想。

之前宣称的3870，只相当于3927（的确，当时的图"TSP"依旧是难看的，这个应当成为当时的判断），如图：






（2）这次吓得我不轻，不敢再狂了，赶紧再试了试：lin318        42029

首先是“随机贪婪+全开优化”，50条随机路径并优化，耗时597秒（这就是我不敢将其与蚁群绑定的原因），得到：42771。




然后是“随机贪婪+阉割优化”，50条随机路径并优化，耗时17秒，得到：43579，足见，时间节省，质量下降。




重点是“蚁群+阉割优化”，50只蚂蚁，500代，相当于25000条随机路径，其中优化500条，如图：




耗时116秒，得到：42216，还算有点效果，虽然不十分令人满意。

对照法师附件，相当于：42203（这次又变小了，忽大忽小的，受不了）。




（3）再来一组猛的：pcb1173                56892，这组数据往往不是为了藏着掖着，而是实在太费时间了，抓狂啊：

首先是我的：100只蚂蚁、500代+阉割优化，完了又做了一次完整优化，耗时：1431+4=1435秒，得到：58826（偏离最优解更多了）。




赶紧又跑了一下法师的：50只蚂蚁、500代、MMAS、3_opt FAST，耗时：3114秒（我几乎后悔了，差点强行结束），得到：57212（法师真大师也）。





我真的很想多跑几次，要是借我一台超级计算机，可以短时间测试各种数据的话该有多好。


综合下来，我现在的做法可以拿得出手了，但总体还是比法师差着一截，重走法师当年走过的路，方知其中滋味。附件我会继续更新在17楼（貌似法师的最强附件也是在17楼，一开始是巧合，后来我便只守着这个楼层了）。

哈哈，致敬大师。

aoe1981

根据最新的处理策略（见24楼），对200左右规模的城市做了多次测试，90%以上可以轻松求得最优解（均以法师附件验证为准），个别情况下，如果改变蒸发率p的值，也就是寻找出合适的p值后也可以求得，或极其接近最优解，比如差1、差2之类，我使用过的p值有0.02、0.05、0.07、0.1……不同的数据似乎对不同的 p 值存在着不同的敏感性。下面是一组求解组图，算是这一段折腾的成果：

aoe1981

今天闲暇又测了一组数据：ali535 : 202339

得到：202324.80，经法师附件验证，相当于：202309

看来果真是刷新了纪录，方法是：50只蚂蚁500代300多秒加一次全开优化约10秒，图片中我又试了50只蚂蚁2000代，没有更进一步结果。

运行结果：



运行结果图：



法师附件验证图：





运行结果数据（只贴城市序号）：


406        429        473        452        472        475        282        195        9        13        402        126        104        403        296        17        264        208        15        485        515        464        182        276        364        431        375        511        295        531        70        400        474        262        481        207        47        388        226        510        20        368        21        1        101        362        16        18        122        68        396        189        76        512        65        314        275        337        492        305        205        343        113        327        324        505        170        293        203        345        212        154        175        338        290        408        369        377        259        112        99        160        495        385        129        114        81        354        414        234        83        90        491        140        179        55        366        453        166        58        202        384        171        6        344        321        196        258        297        284        67        111        174        286        280        272        210        271        534        458        437        107        356        329        372        273        91        28        419        25        172        270        332        167        116        192        465        127        319        93        89        533        460        335        355        214        87        215        358        75        2        462        62        184        199        371        14        131        320        498        477        54        466        266        265        162        395        469        279        94        509        209        301        530        412        277        493        401        494        507        193        413        30        397        529        455        88        191        340        501        118        185        416        389        490        391        497        315        155        487        220        483        200        435        53        480        278        317        133        405        461        136        470        50        115        479        147        445        51        95        249        514        198        206        352        32        459        85        216        263        463        323        331        228        359        128        506        98        373        454        450        449        36        217        409        232        231        176        27        40        261        348        22        145        57        482        24        31        102        292        35        158        250        52        10        204        311        46        236        11        423        143        33        233        307        432        64        187        42        478        3        253        420        153        41        159        468        79        441        168        39        304        246        84        150        421        242        471        177        251        110        142        535        407        73        503        390        289        322        219        103        245        489        360        218        440        378        436        347        370        221        499        353        417        392        247        339        19        80        135        123        467        108        306        308        12        379        163        326        161        237        443        252        294        77        124        318        438        328        486        146        532        387        300        239        342        169        244        72        105        183        351        288        291        194        197        428        78        287        325        334        148        238        132        56        254        188        100        60        346        241        157        260        484        380        281        130        267        285        8        4        349        374        74        415        190        119        71        156        350        442        404        456        411        201        508        426        92        45        488        229        34        410        336        180        96        418        430        283        274        213        502        121        82        298        106        422        393        61        504        186        398        29        448        433        376        248        38        137        255        109        299        44        134        394        399        447        446        310        476        424        211        7        309        313        312        341        367        303        141        500        37        66        333        223        427        144        152        496        361        59        23        151        5        173        383        451        256        425        257        269        444        439        222        26        181        524        434        526        516        69        525        227        330        363        302        316        457        117        365        230        139        138        125        164        165        521        120        386        528        225        97        519        518        523        240        520        63        86        49        235        357        268        178        382        43        224        513        149        381        48        517        522        527        243




对于网上可见的“用遗传算法轻松求取120个圆周坐标城市的最短环游路径”的例子，我生成了400个圆周坐标，发现该问题毫无难度，用CW、随机贪婪（将选择下一个最优城市概率提高到0.99以上）、蚁群、交换优化均可以轻松求得，这种数据不值得作为测试数据。如图：


优化前，随机乱序结果：




运行结果：





优化结果图：





我越来越感觉我的交换优化算法、蚁群算法还是很强大的。

FOB_FN_L

应用的方向在哪些方面呢，具体的实际可应用的地无意当中看到了个日本人写的个限定时间内能去更多的地方的一个例子，肯定没有你的弄的这么多了，

aoe1981

FOB_FN_L 发表于 2020-3-24 19:38
应用的方向在哪些方面呢，具体的实际可应用的地无意当中看到了个日本人写的个限定时间内能去更多的地方的一 ...

惭愧惭愧，我是没有考虑任何“应用”场景的，只是借这个TSP学习下算法……就这么多……谁知掉进了法师所言“军备竞赛”的无聊的坑里了……只是作为偶尔的消遣。

FOB_FN_L

aoe1981 发表于 2020-3-24 19:46
惭愧惭愧，我是没有考虑任何“应用”场景的，只是借这个TSP学习下算法……就这么多……谁知掉进了法师所 ...

研究算法确实是高深的方向，我反正是不懂~~~您自已有方向感就好，除非是在吃黄粮的地，要不就得考虑实际的应用的地呀，
附近是无意中下到的一个，远没有你研究的深

aoe1981

FOB_FN_L 发表于 2020-3-24 19:51
研究算法确实是高深的方向，我反正是不懂~~~您自已有方向感就好，除非是在吃黄粮的地，要不就得考虑实际 ...

附件当中英文太多，没怎么看懂……

观察下图：




虽然只有44个城市，但是人家研究的是更为一般的情况，A到B的距离与B到A的距离并不一定相等……我所做的算是对法师高帖的学习，是基于“对称矩阵”的，显然一般情况更有价值。