没有合适的资源?快使用搜索试试~ 我知道了~
蚁群算法的基本原理.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 64 浏览量
2021-10-10
15:17:40
上传
评论
收藏 304KB DOC 举报
温馨提示
试读
11页
蚁群算法的基本原理.doc
资源推荐
资源详情
资源评论
.
2.1 蚁群算法的根本原理
蚁群优化算法是模拟蚂蚁觅食的原理,设计出的一种群集智能算法。蚂蚁
在觅食过程中能够在其经过的路径上留下一种称之为信息素的物质,并在觅食
过程中能够感知这种物质的强度,并指导自己行动方向,它们总是朝着该物质
强度高的方向移动,因此大量蚂蚁组成的集体觅食就表现为一种对信息素的正
反应现象。某一条路径越短,路径上经过的蚂蚁越多,其信息素遗留的也就越
多,信息素的浓度也就越高,蚂蚁选择这条路径的几率也就越高,由此构成的
正反应过程,从而逐渐的逼近最优路径,找到最优路径。
蚂蚁在觅食过程时,是以信息素作为媒介而间接进展信息交流,当蚂蚁从
食物源走到蚁穴,或者从蚁穴走到食物源时,都会在经过的路径上释放信息素,
从而形成了一条含有信息素的路径,蚂蚁可以感觉出路径上信息素浓度的大小,
并且以较高的概率选择信息素浓度较高的路径。
人工蚂蚁的搜索主要包括三种智能行为:
〔〕蚂蚁的记忆行为。一只蚂蚁搜索过的路径在下次搜索时就不再被该蚂蚁
选择,因此在蚁群算法中建立禁忌表进展模拟。
〔〕蚂蚁利用信息素进展相互通信。蚂蚁在所选择的路径上会释放一种信息
素的物质,当其他蚂蚁进展路径选择时,会根据路径上的信息素浓度进展选择,
这样信息素就成为蚂蚁之间进展通信的媒介。
〔〕蚂蚁的集群活动。通过一只蚂蚁的运动很难到达事物源,但整个蚁群进
展搜索就完全不同。当某些路径上通过的蚂蚁越来越多时,路径上留下的信息
素数量也就越多,导致信息素强度增大,蚂蚁选择该路径的概率随之增加,从
而进一步增加该路径的信息素强度,而通过的蚂蚁比拟少的路径上的信息素会
随着时间的推移而挥发,从而变得越来越少。蚂蚁系统
蚂蚁系统是最早的蚁群算法。其搜索过程大致如下:
在初始时刻, 只蚂蚁随机放置于城市中,各条路径上的信息素初始值相
等,设为: 为信息素初始值,可设 , 是由最近邻启发式
方法构造的路径长度。其次,蚂蚁 ,按照随机比例规那么选择下
一步要转移的城市,其选择概率为:
1 / 11
.
其中, 为边 上的信息素, 为从城市 转移到城市 的启发式
因子, 为蚂蚁 下一步被允许访问的城市集合。
为了不让蚂蚁选择已经访问过的城市,采用禁忌表 来记录蚂蚁 当前
所走过的城市。经过 时刻,所有蚂蚁都完成一次周游,计算每只蚂蚁所走过的
路径长度,并保存最短的路径长度,同时,更新各边上的信息素。首先是信息
素挥发,其次是蚂蚁在它们所经过的边上释放信息素,其公式如下:
,其中 为信息素挥发系数,且 。
,其中 是第 只蚂蚁向它经过的边释放的信息素,定义
为: 〔〕
根据〔〕可知,蚂蚁构建的路径长度 越小,那么路径上各条边就会
获得更多的信息素,那么在以后的迭代中就更有可能被其他的蚂蚁选择。
蚂蚁完成一次循环后,清空禁忌表,重新回到初始城市,准备下一次周游。
大量的仿真实验发现,蚂蚁系统在解决小规模 问题时性能尚可,能较
快的发现最优解,但随着测试问题规模的扩大, 算法的性能下降的比拟严重,
容易出现停滞现象。因此,出现了大量的针对其缺点的改良算法。
精英蚂蚁系统
精英蚂蚁系统
是对根本 算法的第一次改良,它首先由 等人
中提出,它的设计思想是对算法每次循环之后给予最优路径额外的信息素量。
找出这个解的蚂蚁称为精英蚂蚁。
将这条最优路径记为 〔〕。针对路径 的额外强化
是通过向 中的每一条边增加 大小的信息素得到的,其中 是一个参数,
它定义了给予路径 的权值大小, 代表了 的长度。这样相应的信息素的
更新公式如式〔〕:
〔〕
其中, 的定义方法跟以前的一样, 的定义那么如式〔〕:
2 / 11
.
〔〕
等人的文章列举的计算结果说明,使用精英策略并选取一个适当的 值
将使得 算法不但可以得到更好的解,而且能够在更少的迭代次数下得到一
些更好的解。
最大-最小蚂蚁系统
最大最小蚂蚁系统〔
〕是到目前为止解决 问题最好的
算法方案之一。 算法是在 算法的根底之上,主要作了如下的改
良:〔〕为防止算法过早收敛于局部最优解,将各条路径可能的外激素浓度
限制于 ,超出这个围的值被强制设为 或者是 ,可以有效地防
止某条路径上的信息量远大于其余路径,防止所有蚂蚁都集中到同一条路径上;
〔〕强调对最优解的利用。每次迭代完毕后,只有最优解所属路径上的信息
被更新,从而更好地利用了历史信息;〔〕信息素的初始值被设定为其取值
围的上界。在算法的初始时刻, 取较小的值时,算法有更好的发现较好解的
能力。所有蚂蚁完成一次迭代后,按〔〕式对路径上的信息作全局更新:
〔〕
〔〕
允许更新的路径可以是全局最优解,或本次迭代的最优解。实践证明逐渐
增加全局最优解的使用频率,会使该算法获得较好的性能。
基于排序的蚁群算法
基于排序的蚂蚁系统〔
〕
是对 算法的一种改良。其改良思想是:
在 每 次 迭 代 完 成 后 , 蚂 蚁 所 经 路 径 将 按 从 小 到 大 的 顺 序 排 列 , 即
。算法根据路径长度赋予不同的权重,路径长度越短权重
越大。全局最优解的权重为 w,第 r 个最优解的权重为 ,那么
的信息素更新规那么为:
〔!〕
蚁群系统
3 / 11
剩余10页未读,继续阅读
资源评论
yunxidzh
- 粉丝: 60
- 资源: 30万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功