蚁群算法(独辟蹊径的进化算法)

1. 算法背景——蚁群的自组织行为特征

高度结构化的组织——虽然蚂蚁的个体行为极其简单,但由个体组成的蚁群却构成高度结构化的社会组织,蚂蚁社会的成员有分工,有相互的通信和信息传递。

自然优化——蚁群在觅食过程中,在没有任何提示下总能找到从蚁巢到食物源之间的最短路径;当经过的路线上出现障碍物时,还能迅速找到新的最优路径。

信息正反馈——蚂蚁在寻找食物时,在其经过的路径上释放信息素(外激素)。蚂蚁基本没有视觉,但能在小范围内察觉同类散发的信息素的轨迹,由此来决定何去何从,并倾向于朝着信息素强度高的方向移动。

自催化行为——某条路径上走过的蚂蚁越多,留下的信息素也越多(随时间蒸发一部分),后来蚂蚁选择该路径的概率也越高

2. 算法基本思想:

(1)根据具体问题设置多只蚂蚁,分头并行搜索。

(2)每只蚂蚁完成一次周游后,在行进的路上释放信息素,信息素量与解的质量成正比。

(3)蚂蚁路径的选择根据信息素强度大小(初始信息素量设为相等),同时考虑两点之间的距离,采用随机的局部搜索策略。这使得距离较短的边,其上的信息素量较大,后来的蚂蚁选择该边的概率也较大。

(4)每只蚂蚁只能走合法路线(经过每个城市1次且仅1次),为此设置禁忌表来控制。

(5)所有蚂蚁都搜索完一次就是迭代一次,每迭代一次就对所有的边做一次信息素更新,原来的蚂蚁死掉,新的蚂蚁进行新一轮搜索。

(6)更新信息素包括原有信息素的蒸发和经过的路径上信息素的增加。

(7)达到预定的迭代步数,或出现停滞现象(所有蚂蚁都选择同样的路径,解不再变化),则算法结束,以当前最优解作为问题的最优解。

3. 信息素及转移概率的计算:

4. 算法步骤

算法流程图如下:

5. 举例分析

我们假设5个城市的TSP问题,然由于某种原因,城市道路均是单行道,即A->B和B->A的距离不相同,也就是说这是一个不对称的TSP问题。现在城市距离信息如下表:

设置参数:

m=5,α=1,β=1,ρ=0.5,τ_ij(0)=2。

第一次迭代第一只蚂蚁:

第一次迭代第二只蚂蚁

一次迭代第三只蚂蚁:

第一次迭代第四只蚂蚁:

第一次迭代第五只蚂蚁:

第一次迭代完成,更新信息素矩阵,信息素挥发系数为0.5。

第一代蚂蚁全部累死,重新随机生成第二代蚂蚁进行迭代。

第二次迭代第一只蚂蚁:

第二次迭代第二只蚂蚁:

第二次迭代第三只蚂蚁:

第二次迭代第四只蚂蚁:

第二次迭代第五只蚂蚁:

至此,我们已经发现在第二次迭代的时候,五只蚂蚁走的是同一条路,所以算法收敛结束。 最优路径A->E->D->C->B->A, 最有路径的距离为9.

6. 算法特点:

是一种基于多主体的智能算法,不是单个蚂蚁行动,而是多个蚂蚁同时搜索,具有分布式的协同优化机制。

本质上属于随机搜索算法(概率算法),具有概率搜索的特征。

是一种全局搜索算法,能够有效地避免局部最优。

免责声明:本文系网络转载。版权归原作者所有。如涉及版权,请联系删除!

原文发布于微信公众号 - 智能算法(AI_Algorithm)

原文发表时间:2017-04-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏marsggbo

[转载] 机器学习数据集统计系列一

作者:宋天龙 链接:https://www.zhihu.com/question/63383992/answer/222718972 来源:知乎

1302
来自专栏PaddlePaddle

GITCHAT系列2:个性化推荐

大家好,我是来自PaddlePaddle开源社区的李钊(@livc),目前是一名大三学生。我曾经在手机百度实习,参与推荐算法和反作弊的研发工作,目前是IDL的一...

4078
来自专栏数据科学与人工智能

【算法】推荐算法--协同过滤

协同过滤推荐(Collaborative Filtering recommendation)是在信息过滤和信息系统中正迅速成为一项很受欢迎的技术。与传统的基于内...

1341
来自专栏机器学习人工学weekly

机器学习人工学weekly-2018/1/21

1. Google Brain发布2017年总结贴,感觉今年vision方面已经没什么进展了,AutoML还是优先级最高的 链接:https://rese...

3797
来自专栏北京马哥教育

27个机器学习图表,帮你作弊一般飞速成长!

今天分享一篇机器学习的文章。翻了一半,发现Linux中国已经翻译过了。。。干脆搬过来,还有一个姊妹篇《My Curated List of AI and Mac...

3638
来自专栏ATYUN订阅号

NVIDIA新研究:AI只通过噪点图像的训练就可以修复照片

如果在低光照下拍摄的照片,噪音和伪影可以自动消除,那将会如何;如果你的照片库中有颗粒状或像素化的图像呢,你会想要修复它们吗?现在一种基于深度学习的方法已经学会...

1143
来自专栏PPV课数据科学社区

基础篇:从 0 到 1 掌握 Python 机器学习(附资源)

Python 可以说是现在最流行的机器学习语言,而且你也能在网上找到大量的资源。你现在也在考虑从 Python 入门机器学习吗?本教程或许能帮你成功上手,从 0...

4948
来自专栏人工智能头条

杨鹏谈世纪佳缘推荐算法:基于Spark GraphX,弃GBDT和LR用FM

2754
来自专栏新智元

【IEEE Spectrum】神经网络视觉分类算法的意外弱点

【新智元导读】以往的对抗攻击需要进行复杂的数据处理,但最近华盛顿大学、密歇根大学、石溪大学和加州大学伯克利分校的一组研究人员发表了一篇文章,表明在物理世界中进行...

33713
来自专栏新智元

CVPR 18论文“无法重现”?中国作者再度澄清获网友一边倒支持

而对于机器学习的研究来说,由于各种超参数对结果影响很大,并且论文里不太可能把所有实现的细节都说清楚,公布代码就成了保证复现的重要途径。

1212

扫码关注云+社区