手机

教育资源为主的文档平台


当前位置: 查字典文档网> 所有文档分类> 科技> 自然科学> 蚁群算法介绍(带简单模拟实验)

蚁群算法介绍(带简单模拟实验)

上传者:郭景梅
|
上传时间:2016-09-05
|
次下载

蚁群算法介绍(带简单模拟实验)

这个模拟实验比较简单,并没有对信息素、路径选择等做优化,主要是方便大家查看简单的蚂蚁系统能够带来一个什么样的效果,详细说明见后文。

什么是蚁群算法

按百度百科的话来说,蚁群算法(ant colony optimization, ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质,并且现在已用于我们生活的方方面面。

基本原理

蚂蚁在运动过程中,会留下一种称为信息素的东西,并且会随着移动的距离,播散的信息素越来越少,所以往往在家或者食物的周围,信息素的浓度是最强的,而蚂蚁自身会根据信息素去选择方向,当然信息素越浓,被选择的概率也就越大,并且信息素本身具有一定的挥发作用。 蚂蚁的运动过程可以简单归纳如下:

当周围没有信息素指引时,蚂蚁的运动具有一定的惯性,并有一定的概率选择其他方向

当周围有信息素的指引时,按照信息素的浓度强度概率性的选择运动方向

找食物时,蚂蚁留下家相关的A信息素,找家时,蚂蚁留下食物相关的B信息素,并随着移动距离的增加,洒播的信息素越来越少

随着时间推移,信息素会自行挥发

一个简单的例子,如果现在有两条通往食物的路径,一条较长路径A,一条较短路径B,虽然刚开始A,B路径上都有蚂蚁,又因为B比A短,蚂蚁通过B花费的时间较短,随着时间的推移和信息素的挥发,逐渐的B上的信息素浓度会强于A,这时候因为B的浓度比A强,越来越多多蚂蚁会选择B,而这时候B上的浓度只会越来越强。如果蚂蚁一开始只在A上呢,注意蚂蚁的移动具有一定小概率的随机性,所以当一部分蚂蚁找到B时,随着时间的推移,蚂蚁会收敛到B上,从而可以跳出局部最优。

实验

上面的描述可能不是很形象,现在我们来模拟做个小实验,实验地址Demo,源码已放在 Github

简单蚁群实验环境:

满足上面4点基本规则,信息素散播规则按照屏幕斜线距离/蚂蚁移动距离,移动距离在找到食物或者家清0(言外之意式,蚂蚁最多能够移动斜线这么远的距离,这个公式比较简单)

超过一定的移动步数未找到食物或窝的蚂蚁进行重置

选择方向的计算公式采用单元格浓度/8个方向单元格浓度总和,用轮盘赌进行概率选择

信息素在每次迭代时,进行统一挥发一个常量值

现在我们来看看蚂蚁是否能够找到最近的食物。

1.首先我们放置一个较远的食物A,图中的绿色为食物,白色为蚂蚁,暗蓝色为家相关的信息素,颜色深浅代表浓度。

 

注意:我们上面采用的信息素洒播规则,会让家相关的信息素浓度围绕着家呈梯形分布,这样蚂蚁在回家时,能够根据浓度找到家,食物相关信息素也一样。感兴趣的朋友可以在源码里修改信息素显示参数,显示食物相关的信息素分布图。

2.过一会儿,我们发现蚂蚁都聚集在这条路径上,然后我们放一个离得很近的食物B

 

3.最后我们会发现这条路径上的蚂蚁越来越多,再过一会儿,A路径上基本没有什么蚂蚁了。

 

你有可能问,那障碍是干嘛用的,我当时只是想干一件小时候经常干的事情,如

1.一群蚂蚁找到了食物

 

2.我拦住了他们的去路

 

3.最后他们还是找到了食物,坏笑

 

最后

如果你亲自动手做实验,你会发现,当蚂蚁在一条路径上觅食很久时,你再放置一个近的食物基本没啥效果,你也可以理解为当一只蚂蚁找到一条路径时,过了很久的时间,大多数蚂蚁都选择了这条路径,就在这时候,突然有一只蚂蚁找到了较近的食物,但因为时间过得太久,两条路径上浓度相差太大(浓度越大,被选择的概率就越大),整个系统基本已经停滞了,陷入了局部最优。所以简单的蚂蚁系统是存在一些问题的,如:

搜索到一定程度,会出现停滞状态,陷入局部最优的情况

盲目的随机搜索,搜索时间较长

而影响蚂蚁是否能够找到好的最优解,依赖这几个关键因素:

信息素怎么洒播(比如维持在一个特地范围的值等)

信息素怎么挥发(除了全局挥发,可以让蚂蚁自身进行局部挥发等手段)

通过怎样的方式让蚂蚁选择运动方向,减少盲目性和不必要性(给蚂蚁一点点智能和经验)

给蚂蚁和环境一定的记忆能力能够帮助减少搜索空间

如果你感兴趣,可以去看看诸如最大最小蚁群算法、排序蚁群算法、基于遗传算法的蚁群算法等一系列在基本蚁群系统上的优化和改进,他们对于信息素的使用、蚂蚁方向选择等都有一套成熟的数学模型和经验优化参数。

版权声明:此文档由查字典文档网用户提供,如用于商业用途请与作者联系,查字典文档网保持最终解释权!

下载文档

热门试卷

2016年四川省内江市中考化学试卷
广西钦州市高新区2017届高三11月月考政治试卷
浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
广西钦州市钦州港区2017届高三11月月考政治试卷
广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
广西钦州市高新区2016-2017学年高二11月月考政治试卷
广西钦州市高新区2016-2017学年高一11月月考政治试卷
山东省滨州市三校2017届第一学期阶段测试初三英语试题
四川省成都七中2017届高三一诊模拟考试文科综合试卷
2017届普通高等学校招生全国统一考试模拟试题(附答案)
重庆市永川中学高2017级上期12月月考语文试题
江西宜春三中2017届高三第一学期第二次月考文科综合试题
内蒙古赤峰二中2017届高三上学期第三次月考英语试题
2017年六年级(上)数学期末考试卷
2017人教版小学英语三年级上期末笔试题
江苏省常州西藏民族中学2016-2017学年九年级思想品德第一学期第二次阶段测试试卷
重庆市九龙坡区七校2016-2017学年上期八年级素质测查(二)语文学科试题卷
江苏省无锡市钱桥中学2016年12月八年级语文阶段性测试卷
江苏省无锡市钱桥中学2016-2017学年七年级英语12月阶段检测试卷
山东省邹城市第八中学2016-2017学年八年级12月物理第4章试题(无答案)
【人教版】河北省2015-2016学年度九年级上期末语文试题卷(附答案)
四川省简阳市阳安中学2016年12月高二月考英语试卷
四川省成都龙泉中学高三上学期2016年12月月考试题文科综合能力测试
安徽省滁州中学2016—2017学年度第一学期12月月考​高三英语试卷
山东省武城县第二中学2016.12高一年级上学期第二次月考历史试题(必修一第四、五单元)
福建省四地六校联考2016-2017学年上学期第三次月考高三化学试卷
甘肃省武威第二十三中学2016—2017学年度八年级第一学期12月月考生物试卷

网友关注

2016年安徽公务员考试申论真题答案(B卷)
2016安徽公务员考试面试热点模拟题:提速降费
安徽省考面试每日一练模拟题05.05(结构化面试)
2016安徽公务员面试热点模拟题:教师资格打破“终身制”
安徽省考面试每日一练模拟题答案05.26(结构化面试)
安徽省考面试:面试每日一练结构化面试模拟题05.04
安徽省考面试每日一练模拟题答案6.3(结构化面试)
安徽省考面试每日一练模拟题答案05.31(结构化面试)
安徽省考面试每日一练模拟题答案05.06(结构化面试)
2016安徽公务员考试行测真题-常识判断
2016安徽公务员面试热点模拟题:个人信息泄露频发
安徽省考面试每日一练模拟题6.1(结构化面试)
2015年安徽公务员行测真题-资料分析
安徽省考面试:面试每日一练结构化面试模拟题05.03
安徽省考面试每日一练模拟题6.3(结构化面试)
安徽省考面试每日一练模拟题6.2(结构化面试)
安徽省考面试每日一练模拟题答案05.27(结构化面试)
2016安徽公务员面试模拟题:号贩子的猖獗是谁之过
2016安徽公务员面试热点模拟题:全面放开二孩制度
安徽省考面试每日一练模拟题答案6.1(结构化面试)
2016安徽公务员面试模拟题:玩手机算缺课
安徽省考面试每日一练模拟题答案6.2(结构化面试)
2015年安徽公务员行测真题-判断推理
2016安徽公务员考试行测真题-言语理解
安徽省考面试每日一练模拟题05.26(结构化面试)
2016安徽公务员面试热点模拟题:各行各业的“翻船体”
安徽省考面试每日一练模拟题答案05.05(结构化面试)
2016安徽公务员考试行测真题-资料分析
2016安徽公务员面试热点模拟题:假奶粉如何消除
2016年安徽公务员考试申论真题答案(A卷)

网友关注视频

三年级英语单词记忆下册(沪教版)第一二单元复习
第五单元 民族艺术的瑰宝_15. 多姿多彩的民族服饰_第二课时(市一等奖)(岭南版六年级上册)_T129830
沪教版牛津小学英语(深圳用) 五年级下册 Unit 10
外研版英语七年级下册module3 unit1第二课时
七年级英语下册 上海牛津版 Unit9
冀教版英语四年级下册第二课
北师大版小学数学四年级下册第15课小数乘小数一
30.3 由不共线三点的坐标确定二次函数_第一课时(市一等奖)(冀教版九年级下册)_T144342
【部编】人教版语文七年级下册《逢入京使》优质课教学视频+PPT课件+教案,安徽省
二年级下册数学第三课 搭一搭⚖⚖
苏科版数学八年级下册9.2《中心对称和中心对称图形》
冀教版英语三年级下册第二课
北师大版数学四年级下册3.4包装
每天日常投篮练习第一天森哥打卡上脚 Nike PG 2 如何调整运球跳投手感?
【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案,天津市
沪教版牛津小学英语(深圳用) 四年级下册 Unit 2
沪教版牛津小学英语(深圳用) 四年级下册 Unit 7
沪教版牛津小学英语(深圳用) 六年级下册 Unit 7
沪教版牛津小学英语(深圳用) 五年级下册 Unit 12
19 爱护鸟类_第一课时(二等奖)(桂美版二年级下册)_T3763925
8 随形想象_第一课时(二等奖)(沪教版二年级上册)_T3786594
六年级英语下册上海牛津版教材讲解 U1单词
青岛版教材五年级下册第四单元(走进军营——方向与位置)用数对确定位置(一等奖)
沪教版牛津小学英语(深圳用) 四年级下册 Unit 12
8.对剪花样_第一课时(二等奖)(冀美版二年级上册)_T515402
沪教版牛津小学英语(深圳用) 四年级下册 Unit 4
小学英语单词
沪教版牛津小学英语(深圳用) 四年级下册 Unit 3
【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案,广东省
冀教版小学数学二年级下册第二周第2课时《我们的测量》宝丰街小学庞志荣.mp4