1234

ExcelHome技术论坛

用户名  找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

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

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

[复制链接]

TA的精华主题

TA的得分主题

发表于 2020-3-26 18:19 | 显示全部楼层
本帖已被收录到知识树中,索引项:其他结构和算法
zopey 发表于 2020-3-26 17:50
一代更比一代强,就不叫遗传了。这样的种族 称霸全宇宙也不是事。

呵呵,应该是改进才是,改进到不能再优秀的便是人类精英了。

TA的精华主题

TA的得分主题

 楼主| 发表于 2020-3-27 11:34 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
我已经发现了我的“伪MMAS”蚁群算法的缺点:容易早熟。表现出来就是,再大的蚁群迭代次数,对最优解毫无改观,最优解总是出现在比较靠前的位置,这样的蚁群算法缺乏一种“持续性全局寻优的能力”,不能令人满意。


法师的MMAS不会出现这种情况。如果迭代500代,可能我的结果比法师的强,但只要法师的将迭代次数扩大,比如3000代,则我的结果不会更优,法师的结果却愈来愈强,这使我不得不重新思考。


法师所以做到这一点,是因为采取了:检测算法停滞并重置信息素的办法。


我的附件中也检测过算法是否陷入停滞,但我的愿意是为了“提前退出程序”,避免无谓浪费时间。法师却不是这么想,一旦算法进入停滞,便开始“重置信息素”,这就是我的缺点所在,我也应当加入“信息素重置”,但是,该怎样重置了?


看了看法师在14楼的介绍:

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


法师重置办法.PNG


发现并不能为我所用,我的“伪MMAS”有其特点,必须另寻出路。


什么是“信息素重置”?

是要回到初始状态,每条路径段都只有平均的“信息素初始量”吗?不是,这样相当于算法中途结束,再从头来过一遍,而前面多代蚂蚁搜寻的结果(反映在信息素中),前功尽弃了。

那么应当达到什么样的“重置效果”?我想可以概括为“保持现有信息素差异排名,但是缩小差距,削峰填谷”。


怎么做?我想到了一种现实生活中所谓“缩小收入差距”的办法,就是工资不变,在工资之外一次性发放等额奖金或补助的办法。这样原来收入高的依然高,收入低的依然低,但是彼此间相对差异缩小了。生活总是给予我们启发!!!


该一次性加多少了?我取当前信息素的平均值,这个是动态变化的。


就这样一个小小的改动,让我的“伪MMAS”插上了飞翔的翅膀,效果好极了!!!

以“pr299        :        48191”为例,检测单用蚁群(不开优化)的效果,取30只蚂蚁,迭代3000代:

首先是法师的(我反复测试取了最佳的,蒸发率0.1,当然应该再多试试,但我想我做的够多了,大家再公平试试),得到:49646

法师299-49646.PNG



然后是我的,我也反复对比试了下,在蒸发率0.07的时候出现了最好结果:48562(已经与最优结果很接近啦,要知道这是没开“交换优化”的效果啊,法师曾评价MMAS:“这个复杂的信息素规则,得到非常好的结果,即使不用邻域搜索,MMAS都可以直接求解出200以内规模的最优解!
非常强悍!”我现在真是信了!!!)

299-48562.PNG


我的这一版的附件依然会更新在17楼,其他各楼的附件都是可以删除的,留下只为当时发帖的完整,大家不必下载。


值得注意的是:法师虽未言明具体重置信息素的办法,但就其表达来看,规则还是够复杂,但令人出乎意料的是,法师的运行效率比我高,许多参数我都调一样了,就连领域范围25也是一样的,大师在代码架构上功力非凡,让人敬仰。


TA的精华主题

TA的得分主题

 楼主| 发表于 2020-3-27 15:41 | 显示全部楼层
现在,我又要情不自禁地吹嘘了:我的伪MMAS蚁群算法在加入了“算法停滞检测并重置信息素”的处理办法,终于修炼成“最强”蚁群算法了!!!(哪怕这种吹牛被事后打脸,至少也成为我当时持续不断改进的动力)

以att532 : 86729为例:

我单用、单用、单用蚁群,30只蚂蚁,30000代,耗时2149秒,在蒸发率0.04(测了两次,这个效果更好)下,得到:87962


532-87962.PNG



下面是法师的:

蒸发率0.02(MMAS的推荐蒸发率),耗时2419秒,得到:92385。(其实,在法师的附件中,很多时候这个0.02的推荐蒸发率并不好)

法师532-92385.png


变为和我一样0.04,耗时:2082秒,得到:90118。(总体法师的效率高一些,可能上面0.02时,重置信息素的次数多了,故而更慢)

法师532-90118.PNG


小规模数据容易测:以tsp225 : 3916为例:

我的:30只蚂蚁,3000代,蒸发率0.04(这个参数很敏感,需多调几次,这次我沿用0.04跑了一次),耗时:66秒,得到:3877。(天啦,没开优化啊,没开优化啊,没开优化啊)

225-3876.PNG


法师的我测了蒸发率0.02、0.1,不太好,最好的反而是0.5,耗时:57秒,得到:3928。(法师当时说MMAS强悍,应该是从这儿来的)

法师225-3928.PNG



哈哈,我十分满意目前所做的“算法停滞时信息素重置”的办法,法师对这一点没有详谈,貌似是将信息素过小的边强制调整为信息素最大值的0.7,这是我猜的。


我举个例子,详细谈谈我的信息素重置的处理办法。


重置目标(最最重要!!!):“保持现有信息素差异排名,但是缩小差距,削峰填谷”。


设 i 城市的可连接城市有3个,3条路径上的信息素现有量为:20,50,30。

则3条路径信息素占比依次为:0.2、0.5、0.3。

求取信息素平均值:(20+50+30)/3=33.3

追加平均值得:53.3、83.3、63.3,信息素总量为:200。

新的占比为:0.2665、0.4165、0.3165。

新旧对比便会发现:“保持差异排名,缩小差距,削峰填谷”的特点。


当然,不排除或有更好的信息素重置办法。

我已经排除的有:加信息素初始量、迭代后半段周期加入随机扰动、重置轮盘为“均等轮盘”(此时信息素并不重置,但不再依据信息素做选择,而是像算法刚开始一样随机选择一轮)。这些效果都不怎么样,当然,我也没再深究。


值得注意的是:我是采用了法师的默认参数,每100次检测停滞并重置信息素,改为每50次、每200次会有什么效果,目前还没有测试,太费时间了。


哈哈哈哈。

评分

1

查看全部评分

TA的精华主题

TA的得分主题

发表于 2020-3-27 23:42 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-3-28 12:15 编辑

设置变异率为0.01,遗传代数10000,结果如图。路径为(197        167        168        201        166        165        131        130        104        129        132        103        133        135        136        138        162        163        137        134        164        202        199        200        228        203        229        231        230        233        232        277        276        275        279        278        281        282        283        280        284        285        286        219        221        220        224        223        226        225        227        299        206        205        204        207        208        210        209        222        212        213        218        216        217        287        288        289        291        290        292        293        295        294        297        296        298        215        214        156        155        154        153        152        151        150        149        147        148        145        146        144        93        92        1        4        3        2        6        5        7        8        9        10        11        12        13        14        88        90        91        89        141        142        143        157        158        159        160        211        161        140        139        97        96        95        98        99        100        101        102        76        78        77        75        80        79        82        81        84        83        87        94        86        85        16        15        17        19        20        18        21        23        22        24        25        26        27        28        29        72        73        74        71        69        70        67        68        105        64        65        107        62        63        66        33        34        30        31        32        35        36        38        37        42        40        43        41        45        46        44        47        48        49        50        51        52        53        54        56        55        116        114        115        117        119        120        118        122        121        125        124        126        127        123        113        111        112        58        57        39        60        59        61        110        106        108        109        128        174        173        171        172        177        175        176        178        179        189        187        253        252        255        261        260        254        256        186        185        180        181        182        183        184        257        258        259        262        264        263        266        265        267        268        248        249        244        245        251        250        188        190        192        191        169        170        195        194        196        193        247        246        270        269        271        239        243        242        240        241        237        236        238        272        273        274        235        234        198)
123.png

评分

1

查看全部评分

TA的精华主题

TA的得分主题

发表于 2020-3-28 08:12 | 显示全部楼层
本帖最后由 FOB_FN_L 于 2020-3-28 08:13 编辑

两位美术大师开始画画了,具体实例应用在哪些案例上呢,就剩两朵花了,你俩一人一朵~~均分

评分

1

查看全部评分

TA的精华主题

TA的得分主题

发表于 2020-3-28 08:17 | 显示全部楼层
能否应用在   “全文内容搜索“   这个方向上,现在的EXCEL的VBA,如能在”全文内容搜索“上提速,那将是重大的一个突破~~

TA的精华主题

TA的得分主题

 楼主| 发表于 2020-3-28 09:29 | 显示全部楼层
FOB_FN_L 发表于 2020-3-28 08:17
能否应用在   “全文内容搜索“   这个方向上,现在的EXCEL的VBA,如能在”全文内容搜索“上提速,那将是重 ...

文本搜索不是有“正则表达式”吗?

对这方面没研究过,不知道问题的焦点在什么地方。

TA的精华主题

TA的得分主题

 楼主| 发表于 2020-4-11 22:39 | 显示全部楼层
把求解TSP的算法推进为5种了,分别是:CW节约、随机贪婪、任意插入、蚁群、交换优化。

当然,还有许多近似算法,比如:利用“最小生成树”实现的“2近似度算法”、利用“最小生成树”和“最小匹配”实现的“1.5近似算法”、凸包塌陷法等,没有再行尝试。前两个或许名字就暴露了它们的解的精度一般,凸包塌陷我却是看到了一个实例,居然还不如CW,当然,有可能凸包的运行效率高,CW是很慢的。

在我的五种算法中,单独使用,蚁群最强,给足时间,耐心调好“蚁群的参数组合”(令人头疼的是,这个“参数组合”本身也是一个寻优的过程,我给出的400城市构造数据,最优解400的,居然对蒸发率0.15最为敏感,80只蚂蚁,3000代循环,用时282秒,一下可得最优解400。阿尔法a取1就可以,贝塔b取4就可以,我反复测试好了,一般不用变,唯独对蚂蚁数、蒸发率、迭代次数反复测试恰当组合就好),200左右城市可以轻松逼近最优解。这算是我最为自鸣得意的吧。在1173城市(最优解56892)数据中,我单用蚁群,1173只蚂蚁、3000代、0.2蒸发率(奇怪的是:大规模数据居然对略高的蒸发率敏感,故而,我重新建议我的蚁群算法蒸发率“不大于0.2”),用时10500秒左右,跑出了58800左右的结果,当时忘了截图,只是证明了一件事:对于大规模数据,只要给足时间,测试出最佳适应参数组合,蚁群算法的收敛性依旧存在。

我的蚁群算法是“杂牌军”,糅合了MMAS(最大最小蚁群)和BWAS(最好最差蚁群)。

1.MMAS:是因为只对每一代的最佳蚂蚁留信息素;

2.BWAS:是因为对“后代”差于“前代”的最佳蚂蚁采取适度惩罚策略,将其信息素按“最佳路径长度”占“当代最佳路径长度”比例的平方进行降低,只有当代最侍蚂蚁找到同等或更优路径时,才按比例“1”保留信息素;

3.信息素重置策略:当前路径段信息素*0.25+全局信息素平均值*0.75,通过两个系数:0.25、0.75,控制重置的力度,同时又保证信息素总体水平不至反复增加,该重置策略几经对比,比“法师”的重置办法效果显著。

以上做法2,在1、3的基础上的改进不太明显,似乎只是为了合乎逻辑,不过,在反复测试中,没有出现退化,“比例的平方”事实上,使得信息素的添加更为动态,且多了一种调节手段,总体应该是略有进步的(由于蚁群仍属“随机搜索”的本质,很难精确评判)

“百尺竿头,更进一步”,更为难能可贵。全网少有“LKH”算法的原理介绍,在瞎搜中找到了“插入法”:

https://blog.csdn.net/onezeros/article/details/5600094?locationNum=5&fps=1

本来做了两个版本的插入法:任意插入法、近邻插入法,前者的时间复杂度是O(n^2),后者的时间复杂度是O(n^2*ln(n))或O(n^3)(可能和我的具体实现有关,我更多地感觉“近邻插入法”的时间复杂度是O(n^3)),便是要命的是:居然“近邻插入法”得到的解的质量远不如“任意插入法”,我便将其抛弃了,其实所谓“近邻”,是吸收了“贪婪”的思想,一贪婪就坏事了。我在“任意插入法”中,也轻度使用了“贪婪法”,即最初选择的两个城市,第二个城市是第一个城市的第一邻域城市,后来我在测试“随机+完全任意插入法”时,发现连这第一步贪婪都扔掉,会取得极好的结果,便果断只保留了一种“随机+任意插入法”,几组效果图如下,完全单用“插入法”:

随机 任意插入法.PNG

上面48城市的可以轻巧的得到最优解(33523),请注意:之前用法师的MMAS迭代40万代(不开邻域搜索)都只能得到33700)

随机 任意插入法2.PNG


1173城市规模的可以轻松得到6万4千多的结果,从其时间效率上,将其与“交换优化”次第使用,可能更经济实惠。我想这种结果往往是蚁群、遗传、CW、随机贪婪在同等时间内所不可能达到的。

相信,这个TSP问题仍然还有许多神奇而有效的办法是我所不知道的。

TA的精华主题

TA的得分主题

 楼主| 发表于 2020-4-16 20:00 | 显示全部楼层
最近看到一篇名为:《凸包工作集TSP算法》的论文,被其中贴出的效果数据折服,研究两天,成功实现了其算法,我根据我对算法的理解起名为:“凸包子集逐层递归塌陷算法”。

一听名字,确实是“高大上”的感觉,其算法的复杂程度,算是我自写“递归”以来遇到的最为困难的,好歹算是绕了出来。

这个算法的大意是:

先生成外层凸包子集,然后把内部剩余点分类到工作集中;

所谓“工作集”是指外层凸包子集中的每一条边,如果有8个外层凸包顶点,就有8条凸边,也就有8个工作集;

根据内部剩余点距离“工作集”的远近,对内部剩余点进行分类归集,形成了若干个小的点集,个数等于凸包顶点数,若初始凸包子集有8个顶点,则初始点集经过本轮归集后被划分为8个子点集;

对每个小的点集如法炮制,直到工作集只有两个点为至;


依次读出有序工作集的头元素,即形成一条合法路径,为结果。(这里的“有序”很要命,涉及到“生成凸包顶点”的顺时针、逆时针选择等,否则,连结果的正确性都保证不了……天啦,我算是绕出来了)

了解了这个算法的大概流程后,我是十分激动的。在实现过程中,更进一步体会到了论文中看似“不起眼的概念”,实则大有用处,总算是成功了。

我是对这么“复杂高级”的算法抱有极大信心的,因为还真不是一般人所能想到的,再看看其宣称的运行结果:

00.PNG


确实很牛,一个确定性的近似算法,能达到这样的结果,逆天了!!!

虽然数据中似乎告诉我们算法中仍有“大量随机”的影子,我也寻蛛丝马迹,将“归集内部点”的步骤由确定的“选择距离最近的”变为“轮盘赌选择”,以使算法的生成结果抖动起来,便于沉淀更优结果,然而,依然挡不住这伪装起来的算法的“垃圾本性”!可怜我的两天时间,我气的都不想发布了!!!

唯独的好处:圆周坐标一次生成最优结果(呵呵,全是外层凸包点集,其他算法也很轻松,网络视频中模拟圆周坐标的全是耍把戏的)。

11.png


但是换作“格子图”,凸包就“惨死”了……

20*20:

33.png

19*19:

22.png


典型的“凸包塌陷”结果。

至于其他诸如:将初始点集生成“洋葱结构”(即一圈一圈的凸包由外到内,如下图),然后“逐层由外向内或由内向外塌陷”,其效果比之这个“工作集”还是强的,但终归不如我的“随机+任意插入”,再也没能让人眼前一亮。即使只将外层凸包点集相对位置固定,内部剩余点集随机顺序插入,这种结果,也只和我的“随机+任意插入”旗鼓相当,没有明显差异。

44.png


凸包层(洋葱结构)


“随机+任意插入”效率高,短时内可以得到普通较优解。但是对于100以内的城市规模,居然可以轻巧得到精确最优解,这就是当初让我眼前一亮的原因!现在,想更进一步,不曾想却误入歧途。大家有类似想法就免了吧。

发点有用的:

  1. Public Function YWLunPan(arr#()) As Long '一维通用轮盘(输入一维数组,输出某一选中下标,数组元素值应当不小于0)
  2.     Dim xb&, sb&, cd&, i&, j&, arr_sum#, qd&, arr_sum_rnd#
  3.     xb = LBound(arr())
  4.     sb = UBound(arr())
  5.     cd = sb - xb + 1
  6.     arr_sum = 0
  7.     For i = xb To sb
  8.         arr_sum = arr_sum + arr(i)
  9.     Next i
  10.     Randomize
  11.     qd = Int(Rnd() * cd) + xb
  12.     arr_sum_rnd = arr_sum * Rnd()
  13.     For i = qd To qd + cd - 1
  14.         j = (i - 1) Mod cd + 1
  15.         arr_sum_rnd = arr_sum_rnd - arr(j)
  16.         If arr_sum_rnd < 0 Then YWLunPan = j: Exit For
  17.     Next i
  18. End Function
复制代码



那个伪学术的“垃圾算法”就不要再出来现眼了。

评分

2

查看全部评分

TA的精华主题

TA的得分主题

发表于 2020-4-16 22:49 | 显示全部楼层
aoe1981 发表于 2020-4-16 20:00
最近看到一篇名为:《凸包工作集TSP算法》的论文,被其中贴出的效果数据折服,研究两天,成功实现了其算法 ...

有个好玩的,你老人家可以突破一下,词云,知道吧,网上做得好的都是PY和JAVA写的,VBA的也有能人写出来过,但美感还是有点不足~~~突破一下呗

评分

1

查看全部评分

您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

1234

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

GMT+8, 2025-2-24 20:22 , Processed in 0.031164 second(s), 8 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

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

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

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