蚁群算法介绍(带简单模拟实验)
上传者:郭景梅|上传时间: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月月考生物试卷
网友关注
- 男鸡宝宝取名 带杰字的男孩名字精选
- 安全常识
- 中国特色幼儿教育市场前瞻与投资战略规划分析
- 浅议情感管理在幼儿园管理中的运用
- 101班安全教育主题班会
- 幼儿园留样要求
- 伟大的“母亲”张文卓
- 黄草坝小学一(3)班防溺水安全教育主题班会记录
- 小学中华经典诵读美文推荐篇目
- 义务教育阶段教学常规环节要求
- 汉语拼音的书写格式
- 邮票齿孔的故事
- 古诗词过级之新定五百首诗词(-全)
- 小学古诗
- 行为习惯养成教育活动记录
- 03.29 幼儿园不学拼音、识字,上小学就会“掉队”?
- 幼儿园安全管理培训 郭丽
- 六一儿童节幼儿园小学趣味俏皮Word
- 小班家长半日活动
- 小学生必背古诗词100首
- 自拼(中)练习2答案
- 03.29 孩子太磨蹭?因为你总是催催催!
- 幼儿园春季安全宣传教育计划
- 宝宝辅食大全
- 23.古诗词三首
- 消防安全小常识
- 幼儿园安全小常识
- 柳塘镇打坝小学图书室管理制度
- 游览动物园
- 幼儿园毕业典礼家长发言稿
网友关注视频
- 化学九年级下册全册同步 人教版 第18集 常见的酸和碱(二)
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 4
- 外研版英语三起6年级下册(14版)Module3 Unit1
- 第4章 幂函数、指数函数和对数函数(下)_六 指数方程和对数方程_4.7 简单的指数方程_第一课时(沪教版高一下册)_T1566237
- 七年级英语下册 上海牛津版 Unit9
- 沪教版牛津小学英语(深圳用) 五年级下册 Unit 10
- 外研版英语七年级下册module1unit3名词性物主代词讲解
- 【获奖】科粤版初三九年级化学下册第七章7.3浓稀的表示
- 第五单元 民族艺术的瑰宝_16. 形形色色的民族乐器_第一课时(岭南版六年级上册)_T1406126
- 沪教版牛津小学英语(深圳用) 六年级下册 Unit 7
- 冀教版小学数学二年级下册第二单元《有余数除法的竖式计算》
- 沪教版牛津小学英语(深圳用) 五年级下册 Unit 12
- 沪教版八年级下次数学练习册21.4(2)无理方程P19
- 北师大版数学 四年级下册 第三单元 第二节 小数点搬家
- 飞翔英语—冀教版(三起)英语三年级下册Lesson 2 Cats and Dogs
- 沪教版八年级下册数学练习册21.3(2)分式方程P15
- 沪教版八年级下册数学练习册一次函数复习题B组(P11)
- 沪教版牛津小学英语(深圳用) 五年级下册 Unit 7
- 冀教版英语五年级下册第二课课程解读
- 冀教版小学数学二年级下册第二周第2课时《我们的测量》宝丰街小学庞志荣
- 北师大版小学数学四年级下册第15课小数乘小数一
- 冀教版小学数学二年级下册第二单元《余数和除数的关系》
- 七年级英语下册 上海牛津版 Unit5
- 冀教版英语四年级下册第二课
- 外研版英语三起6年级下册(14版)Module3 Unit2
- 苏科版八年级数学下册7.2《统计图的选用》
- 《小学数学二年级下册》第二单元测试题讲解
- 冀教版小学英语五年级下册lesson2教学视频(2)
- 《空中课堂》二年级下册 数学第一单元第1课时
- 第19课 我喜欢的鸟_第一课时(二等奖)(人美杨永善版二年级下册)_T644386
精品推荐
- 2016-2017学年高一语文人教版必修一+模块学业水平检测试题(含答案)
- 广西钦州市高新区2017届高三11月月考政治试卷
- 浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
- 浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
- 辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
- 广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
- 广西钦州市钦州港区2017届高三11月月考政治试卷
- 广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
- 广西钦州市高新区2016-2017学年高二11月月考政治试卷
- 广西钦州市高新区2016-2017学年高一11月月考政治试卷
分类导航
- 互联网
- 电脑基础知识
- 计算机软件及应用
- 计算机硬件及网络
- 计算机应用/办公自动化
- .NET
- 数据结构与算法
- Java
- SEO
- C/C++资料
- linux/Unix相关
- 手机开发
- UML理论/建模
- 并行计算/云计算
- 嵌入式开发
- windows相关
- 软件工程
- 管理信息系统
- 开发文档
- 图形图像
- 网络与通信
- 网络信息安全
- 电子支付
- Labview
- matlab
- 网络资源
- Python
- Delphi/Perl
- 评测
- Flash/Flex
- CSS/Script
- 计算机原理
- PHP资料
- 数据挖掘与模式识别
- Web服务
- 数据库
- Visual Basic
- 电子商务
- 服务器
- 搜索引擎优化
- 存储
- 架构
- 行业软件
- 人工智能
- 计算机辅助设计
- 多媒体
- 软件测试
- 计算机硬件与维护
- 网站策划/UE
- 网页设计/UI
- 网吧管理