智能优化算法之蚁群算法
创始人
2024-06-01 23:05:46
0次

1、蚁群算法概述

  • 蚁群算法(Ant Colony Algorithm, ACA) 由Marco Dorigo于1992年在他的博士论文中首次提出, 该算法模拟了自然界中蚂蚁的觅食行为。
  •  蚂蚁在寻找食物源时, 会在其经过的路径上释放一种信息素, 并能够感知其它蚂蚁释放的信息素。 信息素浓度的大小表征路径的远近, 信息素浓度越高, 表示对应的路径距离越短。
  • 通常, 蚂蚁会以较大的概率优先选择信息素浓度较高的路径, 并释放一定量的信息素, 以增强该条路径上的信息素浓度, 这样, 会形成一个正反馈。 最终, 蚂蚁能够找到一条从巢穴到食物源的最佳路径, 即距离最短.
  • 路径上的信息素浓度会随着时间的推进而逐渐衰减。

 2、蚁群算法基本思路
 

        将蚁群算法应用于解决优化问题, 其基本思路为: 用蚂蚁的行走路径表示待优化问题的可行解, 整个蚂蚁群体的所有路径构成待优化问题的解空间。 路径较短的蚂蚁释放的信息素量较多,随着时间的推进, 较短的路径上累积的信息素浓度逐渐增高, 选择该路径的蚂蚁个数也愈来愈多。 最终, 整个蚂蚁会在正反馈的作用下集中到最佳的路径上, 此时对应的便是待优化问题的最优解。


 3、蚁群算法的核心基本流程

         不失一般性,设整个蚂蚁群体中蚂蚁的数量为m,城市的数量为n,城市i与城市j之间的相互距离为d_{ij}(i,j=1,2,...n),t时刻城市i与城市j连接路径上的信息素浓度为\tau _{ij}(t)。初始时刻,各个城市间连接路径上的信息素浓度相同,不妨设为\tau _{ij}(t)=\tau _{0}。
        蚂蚁k(k=1,2,...m)根据各个城市间连接路径上的信息素浓度决定其下一个访问城市,设P_{ij}^{k}(t)表示t时刻蚂蚁k从城市i转移到城市j的概率,其计算公式如下:

 其中,

\eta _{ij}(t)为启发函数, 

\eta _{ij}(t)=\frac{1}{d_{ij}}

表示蚂蚁从城市i转移到城市j的期望程度s_{allow_{k}} (k=1,2,...n)为蚂蚁k待访问城市的集合。开始时allow_{k}中有(n-1)个元素,即包括除了蚂蚁k出发城市的其它所有城市。随着时间的推进,allow_{k}中的元素不断减少,直至为空,即表示所有的城市均访问完毕。

\alpha为信息素重要因子,值越大,表示信息素浓度在转移中的作用越大,

\beta为启发函数重要因子,值越大,表示启发函数在转移中的作用越大。即蚂蚁会以较大的概率转移到距离短的城市。

        在蚂蚁释放信息素的同时,各个城市间连接路径上的信息素逐渐消失,设参数\rho(0<\rho<1)表示信息素的挥发程度。因此,当所有蚂蚁完成一次循环后,各个城市间连接路径上的信息素浓度需进行实时更新,具体公式如下:   

     其中,\Delta \tau _{ij}^{k}表示第k只蚂蚁在城市i与城市j连接路径上释放的信息素浓度,\Delta \tau ij表示所有蚂蚁在城市i与城市j连接路径上释放的信息素浓度之和。

 

3.1.1、信息素浓度更新模型

1.ant cycle system 模型

         ant cycle system模型中,\Delta \tau _{ij}^{k}的计算公式如下所示。

 其中,Q为常数,表示蚂蚁循环一次所释放的信息素总量;Lk为第k只蚂蚁经过路径的长度。

2.ant quantity system 模型

        ant quantity system模型中,\Delta \tau _{ij}^{k}的计算公式如下所示。

 3.ant density system 模型

        ant density system模型中,\Delta \tau _{ij}^{k}的计算公式如下所示。

 4、核心算法流程

(1)初始化参数
        在计算之初,需对相关的参数进行初始化,如蚁群规模(蚂蚁数量)m、信息素重要程度因子\alpha、启发函数重要程度因子\beta、信息素挥发因子\rho、信息素释放总量Q、最大迭代次iter-max、迭代次数初值iter=1。

(2)构建解空间
        将各个蚂蚁随机的置于不同出发点,对每个蚂蚁k(k=1,2,..m),计算其下一个待访问的城市,直到所有蚂蚁访问完所有的城市。

(3)更新信息素
        计算各个蚂蚁经过的路径长度L_{k}(1,2,...m),记录当前迭代次数中的最优解(最短路径)。同时对各个城市连接路径上的信息素浓度进行更新。

(4)判断是否终止
        若iter,清空蚂蚁经过路径的记录表,并返回步骤(2);否则,终止计算,输出最优解。

5、 蚁群算法的特点

  1.  采用正反馈机制, 使得搜索过程不断收敛, 最终逼近于最优解;
  2. 每个个体可以通过释放信息素来改变周围的环境, 且每个个体能够感知周围环境的实时变化,个体间通过环境进行间接地通讯;
  3. 搜索过程采用分布式计算方式, 多个个体同时进行并行计算, 大大提高了算法的计算能力和运行效率;
  4. 启发式的概率搜索方式, 不容易陷入局部最优, 易于寻找到全局最优解。
     

 

相关内容

热门资讯

存储芯片巨头的好日子何时结束 ... 摩根士丹利最新报告指出,旧存储芯片行业的前景被低估。曾经因供需失衡而获得高额利润的旧存储芯片现在正处...
国足开场2分钟落后 邵佳一眉头... 点击加载图片直播吧11月17日讯 国足开场2分钟丢球,0-1落后巴林,镜头给到眉头紧锁的邵佳一。国字...
小米:相关内容纯属虚构,警惕虚... 小米旗下微博账号“小米辟谣”于11月17日发布声明,指出近期有不法分子冒充“小米汽车”发送诈骗短信,...
最差密码榜单公布 123456... 网络安全公司 NordPass 发布了《2026 年最常用密码 Top 200》报告,指出“1234...
2岁孩子生命最后11天依然努力... 25岁的妈妈将患有罕见病的儿子兜兜送进了长沙的“雏菊之家”安宁病房。她陪伴儿子度过了最后11天,并每...
13岁少年被控杀害5岁男童案 ... 一名13岁少年因妹妹被邻居5岁男童撒沙而心生怨恨,将男童带至桥上推下水致其溺亡。此案引起了媒体的广泛...
全球顶尖科学家加速回流中国 风... 全球顶尖科学家纷纷选择离开美国,转向中国任职。2026年初,莱斯大学90后斯隆奖得主汪淏田全职加盟同...
APEC工商领导人峰会今天聚焦... 11月17日,来自亚太经合组织21个经济体及英国、法国、德国、瑞士等13个域外经济体的2000多位政...
雷军APEC发言 具身智能潜力... 11月17日,小米CEO雷军在2026年APEC工商领导人峰会上表示,具身智能机器人的潜力超过汽车,...
俄罗斯记者惊呼在深圳谁还用现金... 11月17日,今日俄罗斯国际通讯社记者德米特里·加夫里洛夫在接受采访时分享了他的深圳体验。他提到,刚...
雷军:智能机器人产业潜力超汽车... 11月17日,在2026年亚太经合组织工商领导人峰会上,小米CEO雷军介绍了公司在AI、智能制造和机...
保研举报成风,这不只是“坏人变... 保研举报成风,这不只是“坏人变小了” 制度留操作空间。高校保研季举报成风:这不是学生坏,是制度留了太...
广东01年医护女孩为00年闺蜜... 据河南广播电视台小莉帮忙,广东一位01年的女孩,亲自为自己00年的闺蜜接生。她们的缘分有多深?女孩称...
广东网友为迎接APEC会议周有... 11月14日,2026年APEC领导人会议周新闻中心举办了广东省、深圳市专场中外媒体吹风会。这是20...
动车插座在头顶被吐槽像在打吊瓶... 近日,有网友在社交平台发帖分享自己的乘车经历:乘坐D2928次动车组时,发现车厢内的充电插座安装在顶...
万斯称与特朗普无分歧 一致反对... JD·万斯周一表示,他与总统唐纳德·特朗普在伊朗战争问题上完全一致。此前,他曾将共和党在中期选举中的...
痛风人群这4种饮品要少喝 咖啡... 很多尿酸高、痛风人群都知道啤酒、果汁会升高尿酸,那么有没有什么饮料对尿酸“很友好”,甚至还能降低痛风...
医生辟谣左侧睡根本不伤心:正常... 11月17日,经常朝左睡对心脏的影响引发关注。从解剖学角度看,心脏虽然位于胸腔偏左,但它并非孤零零地...
96岁奶奶扒着车窗含泪送孙女返... 近日,湖南,假期快要结束,孙女准备返程。96岁的奶奶扒着车窗,眼里满是不舍。一句有空常回家看看,戳中...
人民日报:从《持械入宋》火爆看... 有能够让行业内外普遍认可的作品出现,是一种新文艺类型成熟的重要标志。正是因为“家里家外”系列、《盛夏...