蚁群算法吧 关注:1,045贴子:3,591

****** 如何学习蚁群算法 ******

[1]

蚁群算法是一个比较优秀的智能算法,现在也比较火热,研究的人越来越多,

在基本蚁群算法的基础上,经过改进和完善,衍生出许多版本。



学习蚁群算法,首先要从基本蚁群算法着手,万变不离其宗,

只要搞清楚了基本蚁群算法,其他改进的蚁群算法,看一下很快就会明白是怎么回事了。



学习蚁群算法首先要搞清除蚁群算法的原理,原理很简单,就是模拟蚂蚁寻找食物的行为,这个并不难理解。

其次要搞清楚怎么把这个过程用代码实现出来,这个才是关键。这只有一个办法,那就是阅读别人的代码,

这需要具有一定的编程基础,要是对编程一窍不通或者是初学,那阅读和理解起来会费劲一些。

其实基本蚁群算法的实现代码并不多,全部代码加起来也就200多行,这其中还包括注释行和空行,

真正的代码部分少于200行,如果看一遍不懂就看两遍。我想只要用心看上10遍,肯定可以看明白。

不要觉得蚁群算法的代码很复杂,其实很简单,看的时候动脑筋想一下就可以了。


福利不只是穿多穿少,还要有迷人的微笑! 这么文艺有点不习惯,福利贴你懂的!
  • 商业推广
[2]

现在网上关于蚁群算法的文档很多,看了一些,有些文档写的真烂,请容许我用烂这个词来形容那些文档。

实在是写得太差了,根本就没有写明白是怎么回事,完全就是糊弄,为了文章而文章。

很多资料就4、5张纸,开篇无一例外千篇一律的介绍一下基本蚁群算法的渊源,

再加上篇首标题和说明,1张多纸没了,最后面1张无一例外千篇一律的是参考的文献,

然后倒数第2张是自己的试验数据结果比较,真正的内容就剩下1、2张纸

里面罗列了一些公式,无非就是选择策略,更新信息素原则,有些还是抄别人的。

但是就是这么点东西也讲得不清不楚,公式里的每个符号没有说明是什么含义,应该如何取值,

有的文档下面倒是有一些公式里符号的说明,但是这个符号你在公式里愣是找不到。

靠,真是服了写文档和审阅文档的人了,这样的文章居然也可以发表在什么刊物和学报上!!!

简直是浪费自己和别人的时间.



为了搞清楚最大最小蚁群算法里最大和最小信息素是怎么计算的,

我看了好几篇文档,然后又下载了别人的一个源代码,综合比较起来看,才弄明白。

里面有个对Pbest开n次方的地方,几个文档里都没有说明n是什么,

开始猜测是迭代次数,后来觉得不对(n=2的话,除数为0了).

那很有可能是城市数量,但是无法确认,看了别人的代码又自己编了代码测试才确认。

并且里面有个文档对于最小信息素的计算公式还是错误的,真受不了了。

还有就是参数rou,有的文档是定义成信息素挥发参数,有的文档是定义成信息素残留参数,

不同人写的代码里定义也不统一,看的时候一定要注意!

[3]

会了蚁群算法后并不是万事大吉了,还要用它来解决实际问题。

各个行业和应用方面的问题千差万别,关键是把这些问题转化为类似tsp的问题,

这个没什么好方法,可以参考别人的方法,如果没有可参考的那就发挥自己的聪明才智吧,

毕竟我们除了学习之外还得创造点什么吧,呵呵。


[4]

题外话

优化蚁群算法的代码,提高运行速度

<1>尽量不要用pow函数,这个函数的效率很低,会大大降低运行速度,

如果alpha和beta参数都是整数,那么可以用乘法代替,你会发现程序运行速度会急剧提升。

例如beta=2.0

那pow(x,beta)和 x*x的运行结果是一样的,但是后者的速度要远高于前者。

<2>如果alpha和beta是小数,比如beta=1.5

那么就用查表法来提高速度,pow运算主要是运用在蚂蚁选择下一城市计算概率时。

这是会重复对城市间的距离的倒数进行pow运算,这样速度会很慢。

可以提前建立一个二维数组,计算城市间距离的时候顺便把城市间距离倒数的beta次幂也计算好,

到时直接拿来用就可以,速度可以提升很多。


啰嗦了这么多,希望对于想要学习蚁群算法和正在学习蚁群算法的同仁有所帮助。


快试试吧,
可以对自己使用挽尊卡咯~
顶一下


谢谢楼主~~~顶一下~~~


我的直接并行了...还是慢.....


谢谢楼主


MARK


楼主、;你太强悍了,我的问题你看到了,想请你编代码?sanjinzhi@163.com


你对最大最小蚁群算法好熟啊,能不能介绍一些资料啊?我查了很多,但是都没说清楚信息素上下限的更新方式,有的给了公式又没有解释,能不能帮帮忙?


看到你对网上那些蚁群算法的文档的评价,很佩服!能否把你的资料和源代码(最好是delphi,如果没有其他也行),邮箱:renping288@163.com,非常感谢!


楼主说的都是实话,看来蚁群算法还有很大的发展空间,大家一起努力吧


感谢lz的分享,小弟接触蚁群优化算法没多久,有以下几个问题想请教,望lz赐教:
1.MMAS信息素上下界如何设置?因为在网上看到了很多个不同的版本,故有此疑问,目前我的设定方法是上界是挥发系数乘以当前最优路径长度再取倒数,下界是上界除以城市数量的2倍。不知道是否正确。
2.关于ACS寻找下一城市的时候,有两种情况,其一是按照先验规则寻路,其二是按照随机概率寻路。我的疑问是按照先验规则寻路的时候的计算公式应该是怎样的,下图是Dorigo在《Ant colony optimization》一文中相关部分的截图
但在有些地方(而且是不只一次)看到的版本中在tau处有一个alpha次方,不知道此处是否应该有此次幂?


1.MMAS信息素上下界如何设置?

原版最大最小蚁群算法的论文里的计算公式如下:

最大信息素Tmax,你的计算方法是正确的。

最小信息素Tmin计算方法:

先对Pbest开n次方,假设结果是a。

Tmin=(Tmax*(1-a))/((n/2-1)*a)

Pbest=0.05,我看论文里的意思好像是蚂蚁一次搜索找到最优解的概率。
n 是城市数量


2.关于ACS寻找下一城市的时候,有两种情况........................

先验规则寻路和随机概率寻路的计算公式是一样的,只是选择的时候有区别。

先验规则是用贪心选择,选概率最大的。

随机概率是用轮盘选择。



顶楼主,楼主是个大牛啊,让我不得不顶了!


第一次来贴吧,看了蚁群算法吧里楼主的几个帖子,觉得这是个好地方,楼主是个好人!请多指教!


我也正在学习蚁群算法,能不能向你请教,如果方便,可以把最大最小蚂蚁系统的算法代码传给我!我的邮箱ming-zh@163.com ,深度感谢!


楼主有没有C#关于蚁群算法的程序啊。
我有点编程基础,但是对算法不理解,书上说的也都是大概,没有例子。
还有就是我要求一个函数的最小值,怎么用蚁群算法解决?


资料和代码都在下面邮箱的收件箱里
邮箱:ant_algorithm@163.com
密码:antalgorithmorithm


我想请问一下如何把蚁群算法和云计算中资源调度结合起来呀???


楼主太对了!膜拜
千万不要用pow
速度回减慢5倍左右

我运行1000个数据
有100只蚂蚁够么?



这是用C做的蚁群
数据量930个
循环次数1000
历时10分钟,蚂蚁数量50
和最优解相差很多。
如何设置最优参数?





城市数量是900多个,那蚂蚁数量也需要500,600左右吧,如果解不理想,你可以考虑使用最大最小蚁群算法或者蚁群系统试一下,基本蚁群算法求解的结果还是不太理想的。


楼主,很奇怪
我用的是ACS,蚁群系统
我看蚁群优化那本书上面说蚂蚁不一定要多,但似乎要大于sqrt(城市数),我试验了10次
用50只蚂蚁比100只蚂蚁收敛速度快,结果更优
这是为什么?
而且楼主你知道,笔记本+500只蚂蚁+将近1000的城市,那等到何年何月......
现在蚂蚁数目真心不知道怎么设置


理论上蚂蚁数量应该是越多越好,但是太多的话会降低运行速度。
我看到的资料蚂蚁数量应该是是城市数量的2/3,实际上设置成多少好像也没有理论上的依据。
你可以找个小规模的问题尝试一下,分别设置成城市数量的1/10 ,2/10………… 10/10,然后多运行几次,看设置成多少结果比较好,

其实像其他参数alpha,beta,rou也没有理论依据设置成多少是最好的,只能是自己根据问题组合尝试一下


受教了,非常感谢!


我勒个去,谁把公邮密码给改了


为兴趣而生,贴吧更懂你。