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-13 23:27 | 显示全部楼层
本帖已被收录到知识树中,索引项:其他结构和算法
时隔多日,今天我的附件总算有点样子了,可以拿出手了。

关于“求解TSP”,本论坛标杆是灰袍法师,我无法超越,我只是对这个问题一直感兴趣,想在力所能及的范围内做个明白。

今天上传的附件有以下几个特点:

1.优化了顶楼所做的“C-W节约算法”。以225城市的数据为例,顶楼附件遍历225个基点城市大约需要152秒,现在约需89秒,主要做法是:

取消字典,改用n*n的二维数表存储城市间距离数据;

取消字符串连接、拆分的方法,改用数组存储,开辟规模(n-1)*(n+1)的数组,原来只需(n-1)*3;

改二维排序为一维排序,期间我曾考虑使用“快速排序”,但综合对比下来,居然“归并排序”更稳定高效,这让我感觉“归并排序”是个老实能干的人!也许有这样的原因:

快速排序本身不够稳定,如果选取的作为分治序列的基枢纽值过于偏向两极(最大和最小)的话,效率会降低的,坛子里大师们说过:快速排序的时间复杂度有从O(nln(n))退化为O(n^2)的可能;

另外,和我个人的处理有关,我是如何将二维数组根据一个key值排序的问题转化为一维排序的?其实是修改了排序返回值,只是返回原始键值所在数组的原序号,如此而已,改完我发现,快排里赋值、转存语句加的太多了,是会影响效率的;

CW算法的核心在于节约值从大到小排序,这个规模很大,(n-1)*(n-2)/2,如果要遍历n个基点城市,需要再乘上n,我实在感觉不到,提前计算并储存好这样的巨量“三维数表”是划得来的做法!因此,我感觉这个算法我的优化算是到了极点了吧,现在影响效率的就是反复排序,每改变一个基点城市,就要重新计算、排序巨量的节约值,不知是不是这个算法的硬伤,或者是我的智“伤”?顶楼附件就留着,以本楼为目前最佳,作为对比,见证曾经的“愚蠢”。


2.新增了“随机贪婪法”,一开始我做的是“分叉随机选择”,发现不如法师的效果好(同等循环下,当然和法师帖中1楼附件对比,17楼附件中应该全都绑定了“邻域搜索优化算法”,解的质量不在一个档次),便借鉴参考了一下(这是我唯一看了一个大概的法师的算法,蚂蚁算法、领域等核心部分没勇气也没信心,更没能力读懂,法师的代码就像是“英文阅读”一样,变量名长长的,是漂亮而优美的句子,真大师也)。“分叉选择”其实是等概率的,我也把概率变成了递减的,越近的城市被选择的概率越高,解的质量稍微有所提高,其实我更得意的是代码执行的效率,1173城市规模生成10000条随机路径仅需10秒,比法师的高了不老少(估计这也说明了法师的确是将每种基本算法都绑定了“邻域搜索优化”)。


3.新增了“交换优化算法”,恐怕这个硬是靠着我钻研、思考,反复尝试出来的算法,才是我自鸣得意的东西。内含三种优化:
交换1:其实就是法师的2_opt,只不过我觉得我用的是“路径环线遍历法”,法师的是“邻域搜索”,我的是单线的,法师的是发散的、闪电状的、树枝状的(呵呵,想象下),因此,有时在明明好多次优化为0的时候,法师的会突然冒出来几次,继续优化下去,而我的通常不会。

交换2:其实就是法师说的3_opt,法师称其做了三种基本情况,再加上逆转(本质是对称)、旋转,力求覆盖所有情况,而且貌似采用的仍然是“邻域搜索路径”,我水平低,依旧是“环线路径遍历”,但是我在对称、旋转之余,竟研制出了四种基本情况,收效还不错。但是尽管如此,综合起来,仍然比法师的差点,偶尔超越法师结果的,也多半是“随机旋转”所带来的偶然因素,许多时候法师的“邻域搜索优化”也会遇到这个问题。


必须声明的是:我是将法师的“邻域搜索优化”与我所谓的“交换优化”算法单独对比的,即把它们当作与蚂蚁、CW、随机贪婪法所并列的求解TSP的算法来对比的。我要说的是:这种优化算法秒掉CW、随机贪婪不在话下,而且效率很高,像目前我的CW,跑完2319城市一个基点,也需要约360秒,得到的结果(25万左右)远不如优化算法的(24万2左右),当然我没试过遍历完2319个基点城市的,您可以试试……别用我的算法……

交换3:这算是我的创新吧,我起名叫“截点邻域插入法”,当然我还试过“随机交换不定长两弧的优化方法”,单用都有效果,但后者的效果被交换1、2淹没怠尽,没有新的增益,第一个倒是可以与交换一二配合。因此,现在我就把附件拿出来了。

在“优化算法”对比上:我和法师的各有千秋,在有些数据上,比如:318-42029上,我可以优化出43307,法师的连开多次“3_opt FULL”,也只能达到43699,但这也不能完全说明情况,有些数据我的还是不如法师的,可能有“随机旋转”的偶然因素。不过,我还是那句话,至少我的理解在大多数情况下是正确的(我指这个路径变换优化方法,蚂蚁算法完全不懂)。反倒值得我炫耀的是我的代码太少了,交换优化总共152行,法师我认得的2_opt有148行,3_opt有384行,这就是差距啊……


最后声明,我这帖算是学习附件,解的质量无法超越法师的“蚂蚁算法+邻域搜索优化”,我只是换了种思路,唯愿在“邻域搜索优化”上与法师一争高下。

今天我就不上图了,大家试试,给个看法,有时一会好的,一会差的,折腾的我都快蛇精了……曾经我把225以CW4018解的基础上进一步优化出了3918的结果与最优解只差1点几,之后一直优化,结果反不如初也,痛苦啊(前面的旧版没保存),直到今天,终于又能做出来了,极大可能的,所有赶紧发了,不再折腾了。

三种方法求解TSP(CW、随机贪婪、交换优化)_aoe1981.zip (231.29 KB, 下载次数: 26)

(顶楼附件已无多大价值,以这个为准。)



评分

1

查看全部评分

TA的精华主题

TA的得分主题

发表于 2020-3-14 00:16 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
只能默默的支持大仙你,这种算法不懂,没研究,小花献上,附件存下来留念~

评分

1

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2020-3-15 22:14 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
天啦,天啦,我在tsp225 : 3916这一组数据上超越法师了,真是不敢相信:
超越法师第一图:225_3892.35.PNG

超越法师第二图:225_3892.35.PNG

详情容后慢慢道来,现在心情十分激动。

得出的数据如下(原样数据,绝无修改):

204        311.92        356.65
26        290.42        356.65
25        269.42        356.65
208        254.92        356.65
24        240.92        356.65
23        219.42        356.65
22        183.92        356.65
21        155.42        356.65
20        155.42        328.15
203        155.42        314.15
19        155.42        299.65
18        176.92        299.65
17        176.92        328.15
16        190.92        328.15
15        190.92        335.65
14        205.42        335.65
13        226.42        335.65
12        226.42        314.15
11        226.42        292.65
10        226.42        264.15
9        226.42        235.65
8        226.42        207.15
7        226.42        186.15
6        226.42        171.65
5        205.42        171.65
4        205.42        150.65
3        183.92        150.65
1        155.42        150.65
200        155.42        136.15
198        190.92        136.15
197        212.42        136.15
195        254.92        136.15
194        276.42        136.15
46        276.42        150.65
44        276.42        171.65
43        254.92        171.65
42        254.92        193.15
41        254.92        221.65
40        254.92        243.15
39        254.92        271.65
38        254.92        292.65
37        254.92        314.15
36        254.92        335.65
34        290.42        335.65
33        290.42        328.15
35        297.92        328.15
32        297.92        299.65
31        318.92        299.65
206        318.92        314.15
217        336.42        313.15
219        336.42        306.15
216        336.42        298.65
76        336.42        278.65
75        347.42        278.65
74        347.42        264.15
73        368.92        264.15
72        368.92        257.15
71        375.92        257.15
70        375.92        243.15
69        397.42        243.15
68        397.42        235.65
67        418.92        235.65
66        418.92        221.65
65        432.92        221.65
64        432.92        200.15
63        418.92        200.15
62        418.92        186.15
61        404.42        186.15
60        404.42        179.15
58        383.42        186.15
59        383.42        179.15
2        375.92        164.65
47        375.92        150.65
225        368.42        150.65
190        361.92        150.65
207        362.92        164.65
49        354.92        164.65
51        354.92        174.65
57        361.92        186.15
56        361.92        200.15
55        354.92        200.15
54        354.92        221.65
53        338.42        221.65
52        338.42        200.15
50        338.42        174.65
133        347.42        150.65
199        338.92        150.65
224        330.92        150.65
48        308.92        150.65
45        296.42        150.65
218        293.42        136.15
193        301.92        136.15
196        315.92        136.15
192        326.42        136.15
191        340.42        136.15
205        355.42        136.15
189        370.42        136.15
27        387.42        136.15
188        404.42        136.15
187        425.92        136.15
186        447.42        136.15
119        454.42        150.65
118        439.92        150.65
117        419.92        150.65
116        419.92        167.65
223        429.92        167.65
115        439.92        167.65
114        439.92        179.15
113        447.42        179.15
112        447.42        193.15
111        461.42        193.15
110        461.42        214.65
109        461.42        243.15
108        454.42        243.15
107        454.42        250.15
106        439.92        250.15
105        439.92        264.15
220        425.92        264.15
104        418.92        264.15
103        418.92        271.65
102        397.42        271.65
101        397.42        285.65
100        375.92        285.65
99        375.92        299.65
98        361.92        299.65
97        361.92        321.15
96        375.92        321.15
95        375.92        333.65
209        383.42        333.65
94        397.42        333.65
93        397.42        321.15
91        418.92        314.15
92        418.92        321.15
83        418.92        342.65
84        432.92        342.65
210        447.42        335.65
87        447.42        321.15
90        432.92        314.15
89        432.92        292.65
88        447.42        292.65
127        496.92        292.65
126        496.92        271.65
125        496.92        243.15
124        496.92        214.65
123        496.92        193.15
122        496.92        171.65
121        475.92        171.65
175        475.92        160.65
120        475.92        150.65
185        468.42        136.15
184        489.92        136.15
182        532.42        136.15
181        553.92        136.15
180        575.42        136.15
179        596.42        136.15
178        624.92        136.15
177        624.92        150.65
176        603.92        150.65
174        568.42        150.65
173        546.92        150.65
172        546.92        171.65
171        525.42        171.65
170        525.42        193.15
169        525.42        214.65
168        525.42        233.15
212        525.42        250.15
214        525.42        261.15
167        525.42        281.65
166        525.42        299.65
165        525.42        314.15
164        525.42        335.65
213        546.92        335.65
158        560.92        335.65
163        575.42        335.65
162        575.42        321.15
161        582.42        321.15
160        582.42        314.15
159        596.42        314.15
157        596.42        285.65
156        582.42        285.65
155        582.42        271.65
154        575.42        271.65
153        575.42        264.15
152        560.92        264.15
151        542.92        264.15
150        542.92        250.15
149        560.92        250.15
148        575.42        250.15
147        589.42        250.15
146        589.42        257.15
145        610.92        257.15
144        610.92        278.65
143        624.92        278.65
201        624.92        299.65
142        624.92        321.15
141        610.92        321.15
140        610.92        335.65
139        610.92        342.65
138        603.92        342.65
137        589.42        342.65
136        589.42        356.65
183        575.42        356.65
135        560.92        356.65
134        539.92        356.65
215        525.42        356.65
132        496.92        356.65
129        496.92        335.65
128        496.92        317.15
222        482.92        335.65
130        470.42        335.65
211        470.42        345.65
131        470.42        356.65
86        447.42        356.65
85        432.92        356.65
82        418.92        353.65
221        391.42        353.65
81        368.92        353.65
80        368.92        342.65
79        347.42        342.65
78        347.42        328.15
77        336.42        328.15
202        318.92        321.65
30        318.92        328.15
29        318.92        335.65
28        318.92        356.65
204        311.92        356.65



容后慢慢道来。

TA的精华主题

TA的得分主题

 楼主| 发表于 2020-3-15 23:47 | 显示全部楼层
本帖最后由 aoe1981 于 2020-3-16 07:52 编辑

最近,反复阅读了一些关于蚁群算法的文章,同时用法师的附件做了大量的测试,对蚁群算法积累了一些有益的经验,同时,也加深了对法师附件“有邻域搜索的各种蚁群算法”的理解。

蚁群算法是一种仿生算法,成功模拟了蚂蚁的群体智能。在算法开始之初(也就是第一代蚁群),其实遵循的是“随机贪婪法”,因为法师为了提高算法效率,只限定蚂蚁搜索最近25个邻域(通常设置为25个),随机贪婪法当中的“概率递减”策略是完全可以实现这一点的。但是“蚁群算法”强大的生命力在于:蚁群的迭代演化推进,下一代的蚁群会借鉴上一代的蚁群的“信息素”或者干脆就理解成是“寻路经验”,这使得它们的盲目性被降低了,指向性开始凸显,同时,由于“概率选择”依然存在于每一代蚁群当中,又保证了必要的“多样性”,使得算法在具有“收敛性”的同时,保有“全局性”。按理来说,只要“演化代数”足够大,最终是会十分逼近最优解或者找出最优解的。当然,您得不计时间代价,因为,大多数时候蚁群算法的时间效率并不高。

所以有上面的看法,是因为我做出了一个猜测并通过法师的附件得到了验证,那就是:“演化代数”是比“蚂蚁数”更为重要的参数!!!

设有100只蚂蚁,循环100代,则会生成10000条路径;如果极端设置成:a.10000只蚂蚁,演化1代;b.1只蚂蚁,演化10000代。则:b的结果绝对会优于a的结果。下面是我测试的其中一组数据:

法师称MMAS(最大最小蚁群)是性能最好的蚁群算法,在大规模TSP问题中确实如此,比如500城市左右。然而,在200左右及以内城市规模时,我却测试得出BWAS(最好最坏蚁群)的性能是最好的。因此,为了节约时间,我主要选用的是:
BWAS
att48 : 33522
全部不使用邻域搜索优化(法师附件共有5种搜索选项)
10000只蚂蚁,演化1代,用时1.12秒,得出:40524(相当于随机贪婪10000路径的结果);
1只蚂蚁,演化10000代,用时2.36秒,得出:36997;
10只蚂蚁,演化10000代,用时10.76秒,得出:33966;
10只蚂蚁,演化200000代,用时212.02秒,得出:33700;
10只蚂蚁,演化400000代,用时349.52秒,得出:33700;
……

相信,您通过测试法师17楼的最强附件也会认同我的这个结论的。

蚁群算法的收敛性勿庸置疑,是一种成功的算法,只是时间效率算是一种短板,许多改良我相信都是为了时间效率。

以上是第一部分。


在求解TSP问题上,现在我感觉(当然现在的我也不具代表性)综合效率最高的其实是“优化算法”,也就是法师所谓“邻域搜索优化算法”,我之所谓“交换优化算法”。虽然,这种优化算法一次性不大可能得到最优解或极优解,但是在很多情况下秒掉CW、随机贪婪、甚至蚁群算法(比如限定同等时间)是不在话下的。我试过,法师附件中的各种蚁群算法在不开邻域搜索的情况下,除非将循环代数设置很大,一般情况下的结果其实很一般。

但是,也不能过于夸大优化算法的作用,我现在还是坚持这一观点。优化算法有这样一些特点:
1.每次得到的结果不尽一样,有可能差别很大,这也和“优化算法”内部使用了随机旋转路径、对称变换路径有关;

2.同一组数据,初始状态不同时(此时可以关掉优化算法内部的随机旋转和对称,使之便于对比),优化得到的结果是不同的;

3.优化算法要说“稳定”,绝对不是指每次针对同一组数据得出同样距离的结果,而是得出有同样特点的路径,比如:这样的路径绝对没有交叉等,所以说,优化算法是“质的稳定、量的随机”。


以上是第二部分。


法师所说“强迫蚂蚁在好的路径上”,具体应该是这样做的,将每一代的每一个蚂蚁产生的路径做一次“邻域搜索优化”,于是原本假设100代才能收敛出的路径效果,说不定5、6代就可以收敛、优化出来了,因而提高了蚁群算法的效率。我所以这样判断有三点依据:

1.带邻域搜索的蚁群算法耗时明显增长;

2.设置参数为1只蚂蚁循环1代时,其效果等同于“单独执行邻域搜索优化算法”;

3.如果1只蚂蚁循环1代产生的优化次数分别是:2_opt  70次,3_opt  20次,则20只蚂蚁循环500代,产生的优化次数将约是:2_opt  70万次,3_opt  20万次,很明显,每一条路径背后都无一例外地执行了一次邻域搜索优化,这一点您可以通过法师的附件得以验证。


以上是第三部分。


根据我对优化算法的经验,如果基于好的一个结果状态,则会优化出好的结果。比如:TPS225之前我一直基于CW4018反复优化,极大概率可得3917点几,与最优解相差1点几。这使我突发奇想,如果将我做的“交换优化算法”和“随机贪婪法”绑定起来,将原本一次只能试一次的,变为一次可以试50、60次,甚至100、200次(请注意:不要贪心,一下子上成千上万次,那样会很耗时的,我的做法是先测试一次优化耗时,估计时长后再设置,否则,您也会像我一样,打开“任务管理器”强行结束excel的),然后沉淀最好结果。楼上的图就是在这种状况下做出来的,实在是令人激动。


为了稳妥起见,我又测试了许多组数据,大规模的数据还没测,太费时。我的交换优化中的参数“最远检测”、“最大交换”的最大设置值是城市数,像1173数据,两个全设置成1173,单跑一次优化就得几百秒(具体忘了),更别说来个一二百次,黄花菜都凉了!但是,就在刚才,我大量测试了300及以内规模的数据,不是每次都能像TSP225数据一样,刷新当时的纪录,许多仍然达不到,但令人可喜的是,均十分稳定的极为接近最优解,比如:pr299 : 48191,只设了100次随机路径,参数全开299、299、20(优化3中的邻域范围是不用设置太大的,法师一直设25),用时877秒,可以得到48373.8578260486的结果,这个大家可以试一下。我的第三个附件在下面:

求解TSP_随机贪婪绑定交换优化法_aoe1981.zip (352.6 KB, 下载次数: 17)


(该版本求解性能最强,但再无新的算法,只是将11楼附件中的两种算法结合起来使用,居然可以得到1+1>2的效果,几可与法师附件比肩)




现在,更加证明我所做的交换优化思路和方法是正确的。

我成功写出了2_opt,写出了4种基本情形的3_opt(比法师多一种情形,不算旋转和对称),还创新了“截点邻域插入法”,综合性能十分接近法师的“邻域搜索优化算法”效果,可能唯独的差别在于:法师采用“邻域搜索”路径,这是一种树状、闪电状、不定的、充满变化的路径,而我只是简单的使用了“环线路径遍历”法。我相信,如果有天法师来冒泡了,也看到我的做法了,将我的四种情形之一吸收进去,说不定效果会极大提升的。哈哈……


最后,我也是使用过“邻域”的,但是,我没想明白的是:当确定一个城市的第 j 个邻域城市序号后,有什么好的办法可以快速确定该邻域城市在当前变化路径中的“位置”?我采用的是“遍历匹配查找”,我很不喜欢这一点,无端使算法的时间复杂度提升O(n),当然,用字典应该更废,因为当前路径一直在变化……

还有很大的提升空间啊……现在想想,法师将“蚁群”和“邻域搜索优化”结合起来,是多么明智的做法!蚁群产生的是“会进化的随机路径”,毕竟不会完全等同于“随机贪婪法”的。我也认为,我的目前的做法,只是逼近了法师的效果,并在某些偶然的情况下超越了法师。

希望各位坛友指正。

评分

2

查看全部评分

TA的精华主题

TA的得分主题

发表于 2020-3-16 05:18 | 显示全部楼层

TA的精华主题

TA的得分主题

 楼主| 发表于 2020-3-16 09:31 | 显示全部楼层
EXCEL20022002 发表于 2020-3-16 05:18
致敬大师,致敬楼主,致敬大姐

感谢感谢……不知“大姐”是谁?
我的确在很多地方都使用过“香川经典数组洗牌法”,确实是工具性的基础贡献,女侠、大师等等都是EH的基石啊……

TA的精华主题

TA的得分主题

 楼主| 发表于 2020-3-18 20:43 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
本帖最后由 aoe1981 于 2020-4-11 23:47 编辑

增加了一个基本的蚁群算法(AS),附件现在如图:

225-3870.10.PNG


上图同时是我对数据:tsp225 : 3916刷出来的最新结果:3870.10,完整数据结果包含在本楼最新附件中,此时的环游图如下:

225-3870.10图.PNG


其实,我发现规模不大的数据,大概300以下的吧,我差不多是跑出了最优结果的,只是由于法师为了对接历史数据,采用了一些四舍五入计算的办法,一时间给我弄慒了,比如:att48 : 33522,我得到:33523.71

48-33523其实是最优解.PNG


其实就是最优解,见下图:

法师对照.PNG


一时间,煞是高兴。


先传最新附件如下:


五种方法求解TSP_aoe1981.zip (473.15 KB, 下载次数: 53)


(更新了蚁群算法,目前是接近MMAS(最大最小蚁群),该蚁群算法在不使用邻域搜索优化或交换优化的情况下,单独比较时,总体上比法师附件中的最强蚁群算法MMAS表现还要好!其他各楼层附件无需下载,只作为探索过程记载,以本楼层附件为最终附件20200322)

(近期更新附件详细理由见23、24楼,本次附件中不再保留tsp225所谓突破数据3870。因为还有:3859,不过这些都是由于对“舍入”误差处理方式不同而闹的一场乌龙)


(附件中增加“检测蚁群算法停滞并重置信息素”,使得蚁群算法的全局持续寻优能力得以强化,详情见53楼——20200327)

(继续更新了蚁群算法,效果略有进步,不太明显,但更合逻辑;增加了“插入法”,详情见下面的链接:

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

向原作者致敬,这种插入法(尤其“任意插入法”)效率高,可以用来构造初始解。
最新附件界面如下图:

最新界面.PNG
经反复测试,去掉了“邻近插入法”,改用“随机+任意插入法”,效率高,可以得到不错的解,最终界面如下:


最新界面1.PNG

400构造数据59秒.PNG


——20200411






其他版本无须下载,留作纪念,以本楼附件为准!!!


其他版本无须下载,留作纪念,以本楼附件为准!!!


其他版本无须下载,留作纪念,以本楼附件为准!!!



至于蚁群算法,到时再粗略谈一下。






TA的精华主题

TA的得分主题

 楼主| 发表于 2020-3-18 22:30 | 显示全部楼层
本帖最后由 aoe1981 于 2020-3-19 09:33 编辑

蚁群算法我感觉和随机贪婪法在本质思想上是一致的。

最简单、极致的贪婪法是:每次选择距离当前城市最近的可选城市。这样得到的结果很多情况下不是最优解,甚至连极优解都算不上,因为“局部贪婪”过火了。

好吧,降低一些贪婪度,将当前城市的下一步可选城市按距离从近到远排序,随机选择前 k 名中的一个城市,作为下一步城市,会发现可行解的花样多了,变化多了,产生较优解的可能性似乎高了。

然而效果仍不理想,我的进一步改进是:按从近到远“概率递减”,不再是一视同仁,概率平均。在大量随机试验的基础上,会发现效果好了一些。

我做“蚁群算法AS”,便是在上面的随机贪婪法的基础上改造的。

AS其实本质上仍然是一种概率选择、随机搜索的算法,只不过它建立了较之“简单概率递减”更为复杂的概率计算模式,该模式的启发点来源于蚁群仿生。

参数Q的意思是假定一只蚂蚁携带的可释放的信息素总量是一定的,我设置的值是10,也没有多大好的理由。如果这只随机探索路径的蚂蚁走的路程长,则所经过的路径信息素更为稀疏,路径短则浓度较高。我将Q除以它们各自的路径总长,这一点和各种资料介绍一致,不同的是,我在给路径中的每一段增加信息素时,是将 Q/L 再乘以每一段路径长度 di(i,j) 的,这样做,是为了避免产生负几十上百次方的极小数字,否则,偶尔是会出现“数据溢出”的。

后代蚂蚁在探路时,是会倾向于“信息素浓度”高的路径的,参数 a (阿尔法)其实是对信息素重要程度的一种人为控制,一般取1,如果取2或更高,则上代蚂蚁走过的路径会被更加推崇。这样会大大降低路径选择上的随机性、多样性,使得“早熟”(得到一个局部解)。

上代经验固然重要,下代也要勇于探索、创新。参数 b (贝塔),便是根据路径距离对蚂蚁的一种诱导,使其增大选择距当前城市距离较近的城市的可能,具体计算办法是:距离倒数的 b 次方,通常这是一个很小的值,如果 b 再取2、3、……,这个值会更小,这样做将极大地拉大“短路径”与“长路径”的差异,使得新生代蚂蚁在选择路径上,不再是完全依靠上代蚂蚁留下的信息素而绝大可能的一边倒,从而有了更多可能。

然而,不管是 a ,还是 b ,其实都和距离有关,都是为了调整概率。a 所调整的概率的着眼点是“路径整体”,具有全局观点,可以看成是长远利益(整体路径越短,信息素浓度越高);b 所调整的概率的着眼点是“当前可选路径段”,是局部观点,可以看成是眼前利益(倾向于选择当前最短路径段,这其实还是“贪婪法”附身啊)。有人曾说,蚁群算法与其说是一种“算法”,倒不如说是一种“哲学”,整个算法过程中不断体现、演绎了“长远利益与眼前利益的权衡、博弈、取舍、评判”。呵呵,我想还真是如此。

真实的自然环境中,或许蚂蚁从不着急,四处随机探索与发现食物后以最短路径运回巢穴,或许同样重要。可以发现,蚁群算法要收敛出一个漂亮的解,往往需要大量的蚂蚁和迭代次数,普通还真是等不了,计算机也累,以至于我写完了,也并没有多大的惊喜,虽然对比法师的AS,我甚至可以调得更优异一些,但始终感觉和我想象的不一样。我想将蚁群与我的“交换优化”绑定起来,然而,绑定我的“交换优化”,往往“随机路径”数不要超过100条,因为根本等不了,时间代价太大,这和蚁群动辙50只蚂蚁500代共25000条随机路径的情形相去甚远,根本不现实,顶多是个花架子。

其实,主要原因是:法师是通过“邻域搜索”改进蚁群算法效率的。邻域城市大多数情况下20个就够了,20名以内用蚁群的概率,20名开外用贪婪法的概率办法,再加上邻域搜索优化,促使蚂蚁尝试“没有交叉”、更好的路径,加速蚁群算法代际收敛。既提高了效率,又提升了解的质量。

我的“交换优化”的致命缺陷是:没有采用邻域搜索路径。所谓“环线遍历路径”,也能产生好的结果,比如我甚至可以将225不断刷新出新的纪录,但是当遇到更大数据规模时,便不得不将“最远检测”、“最大交换”调小,当然可以调得和“邻域范围”一样小,这时,效率也算是有了,但是“优化效果”却大大地差了,因为“遍历”肯定是会覆盖“邻域城市”的,然而限制后,“最有价值的、最值得交换尝试的邻域城市”却往往会鞭长莫及。事实上,“最优路径”的优化都是集中在“邻域范围”内的,恐怕90%以上如此。我的交换3也是这样的路径,关键的交换2却总是缺乏一些访问邻域城市后回访当前路径所在序号的好的办法,一直搁浅着。

哎,说真的,不要太拔高“蚁群算法”了,虽然我只做过基本版,但我想其他增强版的核心思想也不过如此。

借用法师断言:

“单独的蚁群是很废的,单独的邻域搜索也是很废的,两者相加就很牛逼!”

其实,很多情况下,单用“交换优化”或邻域搜索,其实综合效益比蚁群算法强。

TA的精华主题

TA的得分主题

发表于 2020-3-18 22:47 来自手机 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
好帖,好帖,好帖,重要事情说三遍!

评分

1

查看全部评分

TA的精华主题

TA的得分主题

发表于 2020-3-19 10:10 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
本帖最后由 duquancai 于 2020-3-19 10:14 编辑
duquancai 发表于 2020-3-18 22:47
好帖,好帖,好帖,重要事情说三遍!

不介意的话:python 代码https://blog.csdn.net/wyquin/article/details/88863424
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

1234

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

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

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

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

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

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