收藏 分销(赏)

人工智能蚁群算法及其应用.pptx

上传人:可**** 文档编号:14578416 上传时间:2026-10-15 格式:PPTX 页数:51 大小:2.35MB 下载积分:8 金币
下载 相关
人工智能蚁群算法及其应用.pptx_第1页
第1页 / 共51页
人工智能蚁群算法及其应用.pptx_第2页
第2页 / 共51页


点击查看更多>>
资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,人工智能蚁群算法及其应用,人工智能蚁群算法及其应用,第1页,蚁群算法背景,20,世纪,50,年代中期创建了仿生学,大家从生物进化机理中受到启发。提出了许多用以处理复杂优化问题新方法,如进化规划、进化策略、遗传算法等,这些算法成功地处理了一些实际问题。,蚁群算法从蚂蚁觅食得到启发。,人工智能蚁群算法及其应用,第2页,蚁群算法背景,仿生算法,集群智能算法,概率型算法,遗传算法、进化算法,粒子群算法(课程论文,2,)、,蚁群算法,用来处理众多,NP-hard,问题,人工智能蚁群算法及其应用,第3页,蚁群算法背景,自然蚁群自组织行为特征,高度结构化组织,即使蚂蚁个体行为极其简单,但由个体组成蚁群却组成高度结构化社会组织,蚂蚁社会组员有分工,有相互通信和信息传递。,自然优化,蚁群在觅食过程中,在没有任何提醒下总能找到从蚁巢到食物源之间最短路径;当经过路线上出现障碍物时,还能快速找到新最优路径。,信息正反馈,蚂蚁在寻找食物时,在其经过路径上释放,信息素,(外激素)。蚂蚁基础没有视觉,但能在小范围内觉察同类散发信息素轨迹,由此来决定何去何从,并倾向于朝着信息素强度高方向移动。,自催化行为,某条路径上走过蚂蚁越多,留下信息素也越多(随时间蒸发一个别),以后蚂蚁选择该路径概率也越高。,人工智能蚁群算法及其应用,第4页,蚁,群算法,背景,概念原型,各个蚂蚁在没有事先告诉他们食物在什么地方前提下开始寻找食物。,当一只找到食物以后,它会向环境释放一个挥发性分泌物,pheromone(,称为,信息素,该物质伴随时间推移会逐步挥发消失,信息素浓度大小表征路径远近,),来实现,吸引其它蚂蚁过来,这么越来越多蚂蚁会找到食物。,有些蚂蚁,并没有像其它,蚂蚁一样总重复一样路,他们会另辟蹊径,假如另开辟道路比原来其它道路更短,那么,渐渐地,更多蚂蚁被吸引到这条较短路上来。,最终,经过一段时间运行,就可能会出现一条最短路径被大多数蚂蚁重复着。,人工智能蚁群算法及其应用,第5页,蚁,群算法提出,算法提出,蚁群算法(,Ant Colony Optimization,ACO,),又称蚂蚁算法,一个用来在图中寻找优化路径机率型算法。,它由,Marco Dorigo,于,1992,年在他博士论文“,Ant system:optimization by a colony of cooperating agents”,中提出,其灵感起源于蚂蚁在寻找食物过程中发觉路径行为。最早用于处理著名旅行商问题,(TSP,traveling salesman problem),。,人工智能蚁群算法及其应用,第6页,蚁,群算法提出,基础原理,蚁群算法是对自然界蚂蚁寻径方式进行模似而得出一个仿生算法。,蚂蚁在运动过程中,能够在它所经过路径上留下一个,称之为,信息素,(,pheromone),物质进行信息传递,而且蚂蚁在运动过程中能够感知这种物质,并以此指导自己运动方向,所以由大量蚂蚁组成蚁群集体行为便表现出一个信息正反馈现象:,某一路径上走过蚂蚁越多,则以后者选择该路径概率就越大,。,人工智能蚁群算法及其应用,第7页,蚁,群算法提出,简化蚂蚁,寻食正反馈过程,蚂蚁从,A,点出发,速度相同,食物在,D,点,可能随机选择路线,ABD,或,ACD,。假设初始时每,条路线分配一,只蚂蚁,每个时间单位行走一步,本图为经过,9,个时间单位时情形:走,ABD,蚂蚁抵达终点,而走,ACD,蚂蚁刚好走到,C,点,为二分之一旅程。,人工智能蚁群算法及其应用,第8页,蚁,群算法提出,本图为从开始算起,经过,18,个时间单位时情形:走,ABD,蚂蚁抵达终点后得到食物又返回了起点,A,,而走,ACD,蚂蚁刚好走到,D,点。,人工智能蚁群算法及其应用,第9页,蚁,群算法提出,假设蚂蚁每经过一处所留下信息素为一个单位,则经过,36,个时间单位后,全部开始一起出发蚂蚁都经过不一样路径从,D,点取得了食物,此时,ABD,路线往返了,2,趟,每一处信息素为,4,个单位,而,ACD,路线往返了一趟,每一处信息素为,2,个单位,其比值为,2,:,1,。,寻找食物过程继续进行,则按信息素指导,蚁群在,ABD,路线上增派一只蚂蚁(共,2,只),而,ACD,路线上依然为一只蚂蚁。再经过,36,个时间单位后,两条线路上信息素单位积累为,12,和,4,,比值为,3,:,1,。,若按以上规则继续,蚁群在,ABD,路线上再增派一只蚂蚁(共,3,只),而,ACD,路线上依然为一只蚂蚁。再经过,36,个时间单位后,两条线路上信息素单位积累为,24,和,6,,比值为,4,:,1,。,若继续进行,则按信息素指导,最终全部蚂蚁会放弃,ACD,路线,而都选择,ABD,路线。这也就是前面所提到,正反馈效应,。,人工智能蚁群算法及其应用,第10页,蚁,群算法提出,人工蚁群算法,基于以上蚁群寻找食物时最优路径选择问题,能够结构人工蚁群,来处理最优化问题,如,TSP,问题。,人工蚁群中把含有简单功效工作单元看作蚂蚁。二者相同之处于于都是优先选择信息素浓度大路径。较短路径信息素浓度高,所以能够最终被全部蚂蚁选择,也就是最终优化结果。,二者区分在于人工蚁群有一定,记忆能力,,能够记忆已经访问过节点。同时,人工蚁,群在选择,下一条路径时候是按一定算法规律有意识地寻找最短路径,而,不是盲目标,。比如在,TSP,问题中,能够预先知道当前城市到下一个目标地距离,。,人工蚁群,VS,自然蚁群,人工智能蚁群算法及其应用,第11页,蚁,群算法,特征,蚁,群算法,采取了分布式正反馈并行计算机制,易于与其它方法结合,并含有,较强,鲁棒性,。,(,1,)其原理是一个正反馈机制或称增强型学习系统;,它经过信息素不停更新到达最终收敛,于近似最,优路径上;,(,2,)它是一个通用型随机优化方法;,但人工蚂蚁决不是对实际蚂蚁一个简单模拟,它融进了人类智能;,(,3,)它是一个分布式优化方法;,不但适合当前串行计算机,而且适合未来并行计算机;,(,4,)它是一个全局优化方法;,不但可用于求解单目标优化问题,而且可用于求解多目标优化问题;,(,5,)它是一个启发式算法;,计算复杂性为,O,(NC*m*n,2,),,其中,NC,是迭代次数,,m,是蚂蚁数目,,n,是目标节点数目。,人工智能蚁群算法及其应用,第12页,蚁群算法特征,算法优点:,(,1,),求解问题快速性,由正反馈机制决定,(,2,),全局优化性,由分布式计算决定,防止蚁群在寻优空间中过早收敛,(,3,),有限时间内答案合理性,由贪婪式搜索模式决定,使能在搜索过程早期就找到能够接收很好解,人工智能蚁群算法及其应用,第13页,蚁群算法基础思想,算法流程图:,开始,初始化,迭代次数,Nc=Nc+1,蚂蚁,k=1,蚂蚁,k=k+1,按照状态转移概率公式选择下一个元素,修改禁忌表,K=,蚂蚁总数,m,?,按照公式进行信息量更新,满足结束条件?,输出程序计算结果,结束,Y,Y,N,N,人工智能蚁群算法及其应用,第14页,蚁群算法基础思想,以,TSP,问题为例:,1,、依据详细问题设置多只蚂蚁,分头并行搜索。,2,、每只蚂蚁完成一次周游后,在行进路上释放信息素,信息素量与解质量成正比。,3,、蚂蚁路径选择依据信息素强度大小(初始信息素量设为相等),同时考虑两点之间距离,采取随机局部搜索策略。这使得距离较短边,其上信息素量较大,以后蚂蚁选择该边概率也较大。,人工智能蚁群算法及其应用,第15页,蚁群算法基础思想,4,、每只蚂蚁只能走正当路线(经过每个城市,1,次且仅,1,次),为此设置禁忌表来控制。,5,、全部蚂蚁都搜索完一次就是迭代一次,每迭代一次就对全部边做一次信息素更新,原来蚂蚁死掉,新蚂蚁进行新一轮搜索。,6,、更新信息素包含原有信息素蒸发和经过路径上信息素增加。,7,、到达预定迭代步数,或出现,停滞现象,(全部蚂蚁都选择一样路径,解不再改变),则算法结束,以当前最优解作为问题解输出。,人工智能蚁群算法及其应用,第16页,蚁,群算法数学模型,TSP,算例分析,旅行商问题(,TSP,),给定,n,个,城市和两个两个城市之间距离,要求确定一条,经过全部城市仅一次,最短路径。,第一,步,:,初始化,将,m,只蚂蚁随机放到,n,个城市,每只蚂蚁禁忌表为蚂蚁当前所在城市,各,边信息素初始化,为,c,。,禁忌表表达了人工蚂蚁记忆性,使得蚂蚁不会走重复道路,提升了效率。,人工智能蚁群算法及其应用,第17页,蚁,群算法数学模型,第二步,:,选择路径路径,在,t,时刻,蚂蚁,k,从城市,i,转移到城市,j,概率为:,人工智能蚁群算法及其应用,第18页,蚁群算法数学模型,人工智能蚁群算法及其应用,第19页,蚁,群算法数学模型,蚁群规模和停顿规则,蚁群大小,:,普通情况下蚁群中蚂蚁个数不超出,TSP,图中节点个数。,终止条件,:,1,给定一个外循环最大数目,表明已经有足够蚂蚁工作;,2,当前最优解连续,K,次相同而停顿,其中,K,是一个给定整数,表示算法已经收敛,不再需要继续;,3,目标值控制规则,给定优化问题(目标最小化)一个下界和一个误差值,当算法得到目标值同下界之差小于给定误差值时,算法终止,。,第四步:输出结果,若未到达终止条件则,转步骤二,,不然,,输出当前最优解。,人工智能蚁群算法及其应用,第20页,TSP,应用举例,人工智能蚁群算法及其应用,第21页,TSP,应用举例,人工智能蚁群算法及其应用,第22页,TSP,应用举例,人工智能蚁群算法及其应用,第23页,TSP,应用举例,人工智能蚁群算法及其应用,第24页,TSP,应用举例,人工智能蚁群算法及其应用,第25页,TSP,应用举例,人工智能蚁群算法及其应用,第26页,改进蚁群优化算法,最优解保留策略蚂蚁系统,(带精英策略蚂蚁系统,ASelite,),蚁群系统,(,ACS,),最大,-,最小蚂蚁系统,(,MMAS,),基于优化排序蚂蚁系统,(,ASrank,),最优最差蚂蚁系统(,BWAS,),一个新自适应蚁群算法(,AACA,),基于混合行为蚁群算法(,HBACA,),改 进,蚁群算法,人工智能蚁群算法及其应用,第27页,普通蚁群算法框架主要有三个组成个别:,蚁群,活动;,信息素挥发;,信息素增强;,主要表达在转移概率公式和信息素更新公式。,人工智能蚁群算法及其应用,第28页,(一)带精英策略蚂蚁系统,特点,在信息素更新时给予当前最优解以额外信息素量,使最优解得到更加好利用。找到全局最优解蚂蚁称为“精英蚂蚁”。,精英蚂蚁在边 上增加信息素量;,精英蚂蚁个数;,当前全局最优解路径长度。,人工智能蚁群算法及其应用,第29页,特点,、状态转移规则,伪随机比率规则,设 为常数,为随机数,,假如 ,则蚂蚁转移下一座城市是使,取最大值城市;若 ,,仍按转移概率确定。,、全局更新规则,只有精英蚂蚁才允许释放,信息素,即只有全局最优解所属边才增加,信息素。,、局部更新规则,蚂蚁每次从城市 转移到,城市 后,边 上信息素适当降低。,普通,取值较大。,(二)蚁群系统,规则和都是为了使搜索过程更含有指导性,即使蚂蚁搜索主要集中在当前找出最好解邻域内。规则则是为了使已选边对以后蚂蚁含有较小影响力,以防止蚂蚁收敛到同一路径。,人工智能蚁群算法及其应用,第30页,(三)最大最小蚂蚁系统,关于 取值,没有确定方法,有,书例子中取为,0.01,,,10,;有书提出一个在最大,值给定情况下计算最小值公式。,1,、每次迭代后,只对最优解所属路径上信,息素更新。,特点,2,、对每条边信息素量限制在范围,内,目标是预防某一条路径上信息素量远,大于其余路径,防止过早收敛于局部最优解。,(四)基于优化排序蚂蚁系统,特点:,每次迭代完成后,蚂蚁所经路径由小到大排序,,并依据路径长度赋予不一样权重,路径越短权重越大。,信息素更新时对 考虑权重影响。,人工智能蚁群算法及其应用,第31页,特点:,主要是修改了,ACS,中全局更新公式,增加,对最差蚂蚁路径信息素更新,对最差解进,行减弱,使信息素差异深入增大。,(五)最优最差蚂蚁系统,(六)一个新自适应蚁群算法,特点:,将,ACS,中状态转移规则改为自适应伪随机,比率规则,动态调整转移概率,以防止出现,停滞现象。,说明:,在,ACS,状态转移公式中,是给定常数;在,AACA,中,是随平均节点分支数,ANB,而变,化变量。,ANB,较大,意味着下一步可选城市较多,也变大,表示选择信息素和距离最好边可能性增大;反之减小。,人工智能蚁群算法及其应用,第32页,(七)基于混合行为蚁群算法,特点:,按蚂蚁行为特征将蚂蚁分成,4,类,称为,4,个子蚁群,各子蚁群按各自转移规则行动,搜索路径,每迭代一次,更新当前最优解,按最优路径长度更新各条边上信息素,如此直至算法结束。,蚂蚁行为,蚂蚁在前进过程中,用以决定其下一步移动到哪个状态规则集合。,1,、蚂蚁以随机方式选择下一步要抵达状态。,2,、蚂蚁以贪婪方式选择下一步要抵达状态。,3,、蚂蚁按信息素强度选择下一步要抵达状态。,4,、蚂蚁按信息素强度和城市间距离选择下一步要抵达状态。,蚂蚁,行为,人工智能蚁群算法及其应用,第33页,蚁群算法与遗传、模拟退火算法比较,试验结果表明:,1,、蚁群算法所找出解质量最高,遗传算法次之,模拟退火算法最低。,2,、蚁群算法收敛速度最快,遗传算法次之,模拟退火算法最慢。蚁群算法之所以能够快速收敛到全局最优解,是因为该算法个体之间不停进行信息交流和传递。单个个体轻易收敛于局部最优,多个个体经过合作能够很快地收敛于解空间最优解附近。,人工智能蚁群算法及其应用,第34页,蚁,群算法应用,应用领域,蚁群算法,能够被用于处理大多数优化问题或者能够转化为优化求解问题。,现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信,QoS,管理、生物系统建模、流程规划、信号处理、机器人控制、决议支持以及仿真和系统辩识等方面,群智能理论和方法为处理这类应用问题提供了新路径。,人工智能蚁群算法及其应用,第35页,蚁,群算法应用,蚁群算法在电信路由优化中已取得了一定应用结果。,HP,企业和英国电信企业在,90,年代中后期都开展了这方面研究,设计了,蚁群路由算法,(,Ant Colony Routing,ACR,)。,每只蚂蚁就像蚁群优化算法中一样,依据它在网络上经验与性能,动态更新路由表项。假如一只蚂蚁因为经过了网络中堵塞路由而造成了比较大延迟,那么就对该表项做较大增强。同时依据信息素挥发机制实现系统信息更新,从而抛弃过期路由信息。这么,在当前最优路由出现拥堵现象时,,ACR,算法就能快速搜寻另一条可替换最优路径,从而提升网络均衡性、负荷量和利用率。当前这方面应用研究仍在升温,因为通信网络分布式信息结构、非稳定随机动态特征以及网络状态异步演化与,ACO,算法本质和特征非常相同。,人工智能蚁群算法及其应用,第36页,蚁,群算法应用,基于群智能聚类算法起源于对蚁群蚁卵分类研究。,Lumer,和,Faieta,将,Deneubourg,提出将蚁巢分类模型应用于数据聚类分析。其基础思想是将待聚类数据随机地散布到一个二维平面内,然后将虚拟蚂蚁分布到这个空间内,并以随机方式移动,当一只蚂蚁碰到一个待聚类数据时即将之捡起并继续随机运动,若运动路径附近数据与背负数据相同性高于设置标准则将其放置在该位置,然后继续移动,重复上述数据搬运过程。按照这么方法可实现对相同数据聚类。,人工智能蚁群算法及其应用,第37页,蚁,群算法应用,ACO,还在许多经典组合优化问题中取得了成功应用,如二次规划问题(,QAP,)、机器人路径规划、作业流程规划、图着色(,Graph Coloring,)等问题。,经过多年发展,,ACO,已成为能够有效处理实际二次规划问题几个主要算法之一。,AS,在作业流程计划(,Job-shop Scheduling,)问题中应用实例已经出现,这说明了,AS,在此领域应用潜力。利用,MAX-MIN AS,处理,PAQ,也取得了比较理想效果,并经过试验中计算数据证实采取该方法处理,PAQ,比较早,SA,算法更加好,且与禁忌搜索算法性能相当。利用,ACO,实现对生产流程和特料管理综合优化,并经过与遗传、模拟退火和禁忌搜索算法比较证实了,ACO,工程应用价值。,人工智能蚁群算法及其应用,第38页,蚁,群算法应用,许多研究者将,ACO,用于了武器攻击目标分配和优化问题、车辆运行路径规划、区域性无线电频率自动分配、,Bayesian networks,训练和集合覆盖等应用优化问题。,Costa,和,Herz,还提出了一个,AS,在规划问题方面扩展应用,图着色问题,并取得了可与其它启发式算法相比效果。,人工智能蚁群算法及其应用,第39页,应用举例:基于实时流媒体框架用户接入问题,人工智能蚁群算法及其应用,第40页,问题描述,(,1,)类似于传统结构,视频源依旧首先依据其到,NVS,延时、带宽以及,NVS,负载情况选择接入某个,NVS,。,(,2,)然后,用户请求该,NVS,所接入视频源并计算得出适当,proxy,接入选择(也可能直接接入该,NVS,)。,(,3,)随即,视频内容由该,NVS,经过,proxy,传输转发交付用户(或直接传输,对应于用户直连,NVS,情形)。,人工智能蚁群算法及其应用,第41页,问题描述,人工智能蚁群算法及其应用,第42页,适应函数,人工智能蚁群算法及其应用,第43页,人工智能蚁群算法及其应用,第44页,人工智能蚁群算法及其应用,第45页,人工智能蚁群算法及其应用,第46页,应用举例:以减排为目标发电调度问题,2026/10/15,47,污染物排放,除硫、除硝、除尘设备,排放到大气中,二氧化硫(,SO,2,),氮氧化物(,NO,x,),烟尘,人工智能蚁群算法及其应用,第47页,处理方案,2026/10/15,48,调度控制中心,电厂,1,电厂,n,单机优化,从发电机组设计角度减少排污,整体调度优化,设计实时发电优化调度算法,全厂优化,在满足全厂发电任务的前提下对发电任务再优化,人工智能蚁群算法及其应用,第48页,调度算法,本文算法:,蚁群算法,优化目标:,路径结构:,将调度任务 生成份配序列,人工智能蚁群算法及其应用,第49页,调度算法,选择概率,:,信息素更新规则:,人工智能蚁群算法及其应用,第50页,算法伪代码,人工智能蚁群算法及其应用,第51页,
展开阅读全文

开通  VIP、SVIP  下载更划算
下载10份以上建议开通 VIP 会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 通信科技 > 人工智能

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        关注我们

©2010-2026 宁波自信网络信息技术有限公司  版权所有

客服电话:0574-28810668  投诉电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服