什么是人工智能算法65.pptx
- 文档编号:18672629
- 上传时间:2023-08-28
- 格式:PPTX
- 页数:65
- 大小:602.53KB
什么是人工智能算法65.pptx
《什么是人工智能算法65.pptx》由会员分享,可在线阅读,更多相关《什么是人工智能算法65.pptx(65页珍藏版)》请在冰点文库上搜索。
什么是人工智能算法n随着计算机技术的飞速发展,智能计算方法的应用领域也越来越广泛,当前存在的一些智能算法有人工神经网络遗传算法模拟退火算法群集智能蚁群算法粒子群算等等。
蚁群算法只是其中的一种。
人工智能计算也有人称之为“软计算”,是们受自然(生物界)规律的启迪,根据其原理,模仿求解问题的算法。
从自然界得到启迪,模仿其结构进行发明创造,这就是仿生学。
这是我们向自然界学习的一个方面。
另一方面,我们还可以利用仿生原理进行设计(包括设计算法),这就是智能计算的思想。
1蚁群算法n起源n应用领域n研究背景n基本原理2蚁群优化算法起源蚁群算法最开始的提出是在90年代有人受了蚂蚁觅食时的通讯机制的启发用来解决计算机算法学中经典的“旅行商问题(TravelingSalesmanProblem,TSP)”。
TSP问题属于易于描述但难于解决的著名难题之一,至今世界上还有不少人在研究它。
该问题的基本描述是:
某售货员要到若干个村庄售货,各村庄之间的路程是已知的,为了提高效率,售货员决定从所在商店出发,到每个村庄都售货一次后再返回商店,问他应选择一条什么路线才能使所走的总路程最短?
其实有很多实际问题可归结为TSP问题。
3蚁群优化算法起源例如邮路问题就是一个TSP问题。
假定有一辆邮车要到n个不同的地点收集邮件,这种情况可以用n十1个结点的图来表示。
一个结点表示此邮车出发并要返回的那个邮局,其余的n个结点表示要收集邮件的n个地点。
邮车所行经的路线是一条周游路线,希望求出具有最小长度的周游路线。
再举一个例子在一条装配线上用一个机械手去紧固待装配部件上的螺帽问题。
机械手由其初始位置(该位置在第一个要紧固的螺帽的上方)开始,依次移动到其余的每一个螺帽,最后返回到初始位置。
一条最小成本周游路线将使这机械手完成其工作所用的时间取最小值。
所以TSP问题的研究也是具有很多实际价值。
4蚁群算法应用领域这种方法能够被用于解决大多数优化问题或者能够转化为优化求解的问题。
现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信QoS管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面,群智能理论和方法为解决这类应用问题提供了新的途径。
5蚁群优化算法研究背景1/3蚁群算法属于群智理论。
群智能理论研究领域有两种主要的算法:
蚁群算法(AntColonyOptimization,ACO)和微粒群算法(ParticleSwarmOptimization,PSO)。
前者是对蚂蚁群落食物采集过程的模拟,已成功应用于许多离散优化问题。
微粒群算法也是起源于对简单社会系统的模拟,最初是模拟鸟群觅食的过程,但后来发现它是一种很好的优化工具。
6蚁群优化算法研究背景2/3与大多数基于梯度的应用优化算法不同,群智能依靠的是概率搜索算法。
虽然概率搜索算法通常要采用较多的评价函数,但是与梯度方法及传统的演化算法相比,其优点还是显著的,主要表现在以下几个方面:
1无集中控制约束,不会因个别个体的故障影响整个问题的求解,确保了系统具备更强的可靠性2以非直接的信息交流方式确保了系统的扩展性3并行分布式算法模型,可充分利用多处理器4对问题定义的连续性无特殊要求5算法实现简单7蚁群优化算法研究背景3/3群智能方法易于实现,算法中仅涉及各种基本的数学操作,其数据处理过程对CPU和内存的要求也不高。
而且,这种方法只需目标函数的输出值,而无需其梯度信息。
已完成的群智能理论和应用方法研究证明群智能方法是一种能够有效解决大多数全局优化问题的新方法。
更为重要是,群智能潜在的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证。
无论是从理论研究还是应用研究的角度分析,群智能理论及其应用研究都是具有重要学术意义和现实价值的。
8蚁群算法原理蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。
蚂蚁在运动过程中,能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递,而且蚂蚁在运动过程中能够感知这种物质,并以此指导自己的运动方向,因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象:
某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。
为了说明蚁群算法的原理,先简要介绍一下蚂蚁搜寻食物的具体过程。
在蚁群寻找食物时,它们总能找到一条从食物到巢穴之间的最优路径。
这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。
当它们碰到一个还没有走过的路口时就随机地挑选一条路径前行。
与此同时释放出与路径长度有关的信息素。
路径越长,释放的激素浓度会越低.当后来的蚂蚁再次碰到这个路口的时候选择激素浓度较高路径概率就会相对较大。
这样形成一个正反馈。
最优路径上的激索浓度越来越大而其它的路径上激素浓度却会随着时间的流逝而消减。
最终整个蚁群会找出最优路径。
9简化的蚂蚁寻食过程1/3蚂蚁从A点出发,速度相同,食物在D点,可能随机选择路线ABD或ACD。
假设初始时每条分配路线一只蚂蚁,每个时间单位行走一步,本图为经过9个时间单位时的情形:
走ABD的蚂蚁到达终点,而走ACD的蚂蚁刚好走到C点,为一半路程。
10简化的蚂蚁寻食过程2/3本图为从开始算起,经过18个时间单位时的情形:
走ABD的蚂蚁到达终点后得到食物又返回了起点A,而走ACD的蚂蚁刚好走到D点。
11简化的蚂蚁寻食过程3/3假设蚂蚁每经过一处所留下的信息素为一个单位,则经过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路线。
这也就是前面所提到的正反馈效应。
12自然蚁群与人工蚁群算法基于以上蚁群寻找食物时的最优路径选择问题,可以构造人工蚁群,来解决最优化问题,如TSP问题。
人工蚁群中把具有简单功能的工作单元看作蚂蚁。
二者的相似之处在于都是优先选择信息素浓度大的路径。
较短路径的信息素浓度高,所以能够最终被所有蚂蚁选择,也就是最终的优化结果。
两者的区别在于人工蚁群有一定的记忆能力,能够记忆已经访问过的节点。
同时,人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径,而不是盲目的。
例如在TSP问题中,可以预先知道当前城市到下一个目的地的距离。
13蚁群算法与TSP问题1/3TSP问题表示为一个N个城市的有向图G=(N,A),其中城市之间距离目标函数为,其中为城市1,2,n的一个排列,。
14,|j),(iAn1,2,.,NNjinnijd)(nliilldwf11)(),(21niiiw11iin蚁群算法与TSP问题2/3TSP问题的人工蚁群算法中,假设m只蚂蚁在图的相邻节点间移动,从而协作异步地得到问题的解。
每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定:
1信息素值也称信息素痕迹。
2可见度,即先验值。
信息素的更新方式有2种,一是挥发,也就是所有路径上的信息素以一定的比率进行减少,模拟自然蚁群的信息素随时间挥发的过程;二是增强,给评价值“好”(有蚂蚁走过)的边增加信息素。
15蚁群算法与TSP问题3/3蚂蚁向下一个目标的运动是通过一个随机原则来实现的,也就是运用当前所在节点存储的信息,计算出下一步可达节点的概率,并按此概率实现一步移动,逐此往复,越来越接近最优解。
蚂蚁在寻找过程中,或者找到一个解后,会评估该解或解的一部分的优化程度,并把评价信息保存在相关连接的信息素中。
16初始的蚁群优化算法基于图的蚁群系统(GBAS)1/12初始的蚁群算法是基于图的蚁群算法,graph-basedantsystem,简称为GBAS,是由GutjahrWJ在2000年的FutureGenerationComputingSystems提出的,算法步骤如下:
STEP0对n个城市的TSP问题,城市间的距离矩阵为,给TSP图中的每一条弧赋信息素初值,假设m只蚂蚁在工作,所有蚂蚁都从同一城市出发。
当前最好解是。
17,|j),(iAn1,2,.,NNjinnijd)(),(ji|1)0(Aij0i),2,1(nw初始的蚁群优化算法基于图的蚁群系统(GBAS)2/12STEP1(外循环)如果满足算法的停止规则,则停止计算并输出计算得到的最好解。
否则使蚂蚁s从起点出发,用表示蚂蚁s行走的城市集合,初始为空集,。
STEP2(内循环)按蚂蚁的顺序分别计算。
当蚂蚁在城市i,若完成第s只蚂蚁的计算。
否则,若,则以概率,到达j,;若则到达重复STEP2。
180i)(sL)(sLms11sm()|(,),()LsNlilAlLs=F蜗或0()|(,),()LsNTlilAlLsi蜗-笷且
(1),
(1)ijijijlTkpjTktt-=-0,ijpjT=()(),:
LsLsjij=U0()|(,),()LsNTlilAlLsi蜗-=F且000,()(),:
;iLsLsiii=U初始的蚁群优化算法基于图的蚁群系统(GBAS)3/12STRP3对,若,按中城市的顺序计算路径程度;若,路径长度置为一个无穷大值(即不可达)。
比较m只蚂蚁中的路径长度,记走最短路径的蚂蚁为t。
若,则。
用如下公式对W路径上的信息素痕迹加强,对其他路径上的信息素进行挥发。
得到新的,重复步骤STEP1。
191sm()LsN=()Ls()LsN()()fLtfLW*X,0,1,2,.kXk=*lim1kkpXXe-=GBAS算法的收敛性分析1/8定理满足指定条件的马尔可夫过程依概率1收敛到,其中为一条最优路径,定义为:
证明分析:
蚁群算法中,一但达到全局最优,由只记录第一个最优解.证明分三部分:
n证明以概率1达到一个最优路径n证明
(1)上式成立n证明以概率1收敛到一个最优路径32(),(),0,1,.,kXkWkkt=*(,)XWt=*W*t*1,(,)0
(1)ijWijWt=LLL为的一条弧其他f(L(t)f(w)GBAS算法的收敛性分析2/8证明以概率1到达一个最优路径对于最优路径,令为蚁群中的一个蚂蚁在第k次外循环后第一次走到最优路径的事件.表示仅第k次外循环没有走到的事件,但前k-1次可能走到过这条最优路径.永远不会被走到的事件为,其概率为:
33*WkF*WkF*W*W12FFLII12*1*1()|)(2kkPFFPkWPkW=LILLI*第次循环蚁群没有走到第ik次循环蚁群没有走到W前次循环蚁群没有走到GBAS算法的收敛性分析3/8任意给定的固定弧(i,j),在第k次循环后,其信息素值的下界可以计算出.34111111111()
(1)
(1)ln
(1)
(1)ln
(1)ln
(1)
(1)ln1
(1)ln
(1)(3)lnijkijllKklijllKKlijlKlijlkllKkKktrtrtrtrt-=-=-=-=-+=-=-照LLGBAS算法的收敛性分析4/8令,任何一个固定节点最多有(n-1)后续节点,并且其弧上的信息素值都小于1或者等于1.得:
蚁群中的一只蚂蚁在第次循环走到路径W*的概率为一个蚁群中至少有一只蚂蚁,因此这是一个蚁群到达最优路径的一个下界.上式右侧与k无关,3511
(1)ln
(1)KlijlKrt-=D=-,
(1)lnijpkKnkD吵-k(kK)*(,)*()()(4)1)lnWijijWpknkD-LLGBAS算法的收敛性分析5/8则取对数有从而得到36*(,*)1()1()
(1)lnwijijWPkWpknkD-前次循环蚁群没有走到*1*(1()
(1)ln
(2)(5)kwkKPkWnk=D-LLLL前次循环蚁群没有走到*ln(1()()
(1)ln
(1)lnwwkKkKnknk=DD-=-邋12()1PFF=LUUGBAS算法的收敛性分析6/8证明右式成立随机过程以概率1达到一条最优路径.当某条最优路径Z在第k次循环被首次走到后,在第k+1轮循环按信息素的更新原则,可以用归纳法证明,对于任意37*1,(,)0ijWijWt=为的一条弧其他(i,j)W*,r=1,2,.111011()
(1)()
(1)*(6)KrrrijlijKlllKqlKrKKqWtrtrr+-+=+=-+-+照LLGBAS算法的收敛性分析7/8由于级数是发散的,可知.因此,当时,在第K轮迭代之后,该弧永远不再被加强,从而有也既弧上的信息素之和将趋于0.对于信息素的更新公式
(2),可以归纳证明(6)式的第二项与(i,j)弧无关,结合(7)式可得的极限存在,且所有的极限之和为1.对于所有的38lr1
(1)0llr=-=1()
(1)(07)(KrijlijlKKrKtrt+-=+=-LL(,)*ijW(,)*ijW(,)()1,ijijAkkt=成立(,)*ijW1lim()lim(*(8,*)*)ijlrlKrXWWtt+=LL,即可得GBAS算法的收敛性分析8/8结合前两部分讨论,当Xn首次到达最优路径后,对于任何最优路径上的弧,
(1)式的转移概率,即依概率1收敛到.39()1ijpl(),(),0,1,.,kXkWkkt=*(,)XWt=其他算法及收敛性分析1/4MAX-MIN蚁群优化算法指定挥发系数不随时间变化,这是和GBAS算法不同的一点,改变了信息素挥发和增强的规则(9式),同时给出一个下界控制信息素的挥发.定理在MAX-MIN算法中,40min
(1)kt-minmax
(1)
(1),
(1)(,)()max
(1)
(1),
(1),01,
(1)ijijijijijkWkijWkkkkrtrttrttrt-+-=-令:
其中,则定理5.2.1的结论也成立。
其他算法及收敛性分析2/441ij
(1)
(1)p0
(1)
(1)|(,)
(1)
(1)1.ijillTiijijijakjTakjTAkakijAkkth-=-=-LLLLLiij式蚂蚁转移概率更一般的规则由存储在每个节点的路由表数据结构A=a|(i,j)A决定,即转移概率为其中,取决于三部分因素,T是从i可以直接到达的节点结合。
第一部分为每个节点的信息素痕迹和预见度第二部分为每()个蚂蚁自身的记忆表中存储的历史信息.第三部分为问题的约束条件.其他算法及收敛性分析3/442
(1)
(1)
(1)
(1)
(1)01
(1),.ijijilillTijijkkjTkkkjTTSPkdababththababh-=-=LLLLLLLLLLij常见的路由表信息由下式求得:
a其中,为残留信息的相对重要程度,为预见值的相对重要程度。
和体现了相关信息痕迹和预见度对蚂蚁决策的相对影响。
问题中为先验知识其他算法及收敛性分析4/443
(1)1.,()
(1)():
(1)(),(0,1)ijijijijijkkijkkkktttttrtr-D=-+D-ij信息素痕迹为时刻连接城市和的路径上的信息残留浓度为避免过多的残留信息会淹没全局最优解需要在每只蚂蚁完成一次循环后对残留信息进行更新,削弱旧信息,增强新信息.记(i,j)弧上的信息素在第k-1个循环的变化为(k-1),则保留的信息素为然后进行信息素的挥发其中为信息素的衰退系数.蚁群优化算法技术问题解的表达形式与算法的实现每一节点的记忆信息和系数的确定蚁群的规模和停止规则信息素的更改44解的表达形式与算法的实现1/4-解的表达形式解的表达形式基于TSP问题的蚁群优化算法,其解的形式是所有城市的一个排列(闭圈,这种情况下谁在第一并不重要),信息素痕迹按每个弧记录。
而对于一般以顺序作为解的优化问题,谁在第一是很重要的。
蚁群算法在解决这类问题时,只需要建立一个虚拟的始终点,就可以把TSP问题的解法推广,用于诸多的优化问题。
诸如车间作业及下料等问题,他们的共同特点是解以一个顺序表示。
TSP问题寻找的是最短回路,而一般优化问题中,STEP3中的判断条件需要根据实际问题进行修改。
45()LsN解的表达形式与算法的实现2/4-算法的实现例:
0-1背包问题的解顺序表达形式与算法实现。
设有一个容积为b的背包,n个尺寸分别为,价值分别为的物品,0-1背包问题的数学模型为:
假设其解的顺序表达形式为,其中为的一个排列。
46(1,2,.,)iain=(1,2,.,)icin=11max.0,1,1,.,niiiniiiicxstaxbxjn=()120,.,niii()12,.,niii()1,2,3,.,n解的表达形式与算法的实现3/4-算法的实现建立有向图,其中A中共有条弧。
初始信息素痕迹定义为。
设第s只蚂蚁第k步所走的路线为,表示蚂蚁从0点出发,顺序到达。
第步按TSP算法的转移概率公式行走选择。
若则,否则,此蚂蚁不再继续行走,退回起点。
47(,)GVA=0,1,2,.,(,)|,VnAijijV=
(1)nn+1
(1)ijnnt=+12()(0,.,)kLsiii=12,.,kiii1k+1ki+11jkijab+=121()(0,.,)kkLsiiii+=解的表达形式与算法的实现4/4-算法的实现对蚁群重复以上过程,比较m只蚂蚁的装包值并记忆具有最大装包值的蚂蚁为t。
把GBAS算法中步骤3中的改为,若满足此条件则替换当前最好解为,对W上的弧进行信息素的加强,其他弧进行信息素的挥发。
算法中记录了三个信息:
信息素痕迹;行走路线;和问题的约束条件,以确定是否将加入。
48()0,1,2,.,iiLsicsm=()()fLtfw:
()WLt=ijt121()(0,.,)kkLsiiii+=11jkijab+=1ki+每一节点的记忆信息和系数的确定-需要记忆的信息1/3算法中需要记忆的信息有三部分。
第一部分信息是存在每个节点的路由表数据结构,由此决定的的转移概率为其中T可以看成节点i的邻域。
49|(,)iijAaijA=
(1)
(1)|(,)iijAkakijA-=-
(1)
(1),0ijilijlTakjTakPjT-=
(1)
(1)
(1)
(1)
(1),0ijijililijlTkkkkakjTjTababthth-=每一节点的记忆信息和系数的确定-需要记忆的信息2/3第二部分需要记忆的信息是每个蚂蚁的记忆表中存储着的自身的历史信息,这一部分主要由算法的中的记忆,表示蚂蚁已经行走过的节点。
第三部分为问题的约束条件。
在GBAS中,T集合表示满足约束条件的候选集,在背包问题的蚁群算法中由判别条件,来实现记忆功能。
50()Ls11jkijab+=121()(0,.,)kkLsiiii+=每一节点的记忆信息和系数的确定-系数的确定3/3残留信息的相对重要程度和预见值的相对重要程度体现了相关信息痕迹和预见度对蚂蚁决策的相对影响。
Dorigo在求解TSP问题时,推荐参数的最佳设置为:
。
51ab1,5,0.5abr=蚁群的规模和停止规则一、蚁群大小一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数。
二、终止条件1给定一个外循环的最大数目,表明已经有足够的蚂蚁工作;2当前最优解连续K次相同而停止,其中K是一个给定的整数,表示算法已经收敛,不再需要继续;3目标值控制规则,给定优化问题(目标最小化)的一个下界和一个误差值,当算法得到的目标值同下界之差小于给定的误差值时,算法终止。
52信息素的更改1/6信息素的更新分为离线和在线两种方式。
离线方式(同步更新方式)的主要思想是在若干只蚂蚁完成n个城市的访问后,统一对残留信息进行更新处理。
信息素的在线更新(异步更新方式)即蚂蚁每行走一步,立即回溯并且更新行走路径上的信息素。
53信息素的更改2/6离线方式的信息素更新可以进一步分为单蚂蚁离线更新和蚁群离线更新。
蚁群离线更新方式是在蚁群中的m只蚂蚁全部完成n城市的访问(第k-1次蚁群循环)后,统一对残留信息进行更新处理。
其中,为第k-1次循环后的的信息素的痕迹值。
单蚂蚁离线更新是在第s只蚂蚁完成对所有n个城市的访问后,进行路径回溯,更新行走路径上的信息素,同时释放分配给它的资源。
更新公式为第s+1只蚂蚁根据重新计算路由表。
54()
(1)
(1)ijijijkkkttt=-+D-()ijkt
(1)()()ijijijsssttt+=+D
(1)ijst+信息素的更改3/6TSP问题中,蚁群优化算法根据信息素痕迹更新方式不同可以分为不同的算法,采用离线方式,并且时,其中W为t循环中m只蚂蚁所行走的最佳路线或第t只蚂蚁所行走的一条路径。
Q为一个常数,该算法名为蚁环算法(ant-cyclealgotithm),特点是行走的路径越短对应保存的信息素的值就越大。
55
(1)()ijijksttD-D或为(),(,)(,)0ijQWtijWijWtD=信息素的更改4/6GBAS算法是典型的离线信息素更新方式。
该算法中,蚁群中蚂蚁的先后出行顺序没有相关性,但是每次循环需要记忆m只蚂蚁的行走路径,以进行比较选择最优路径。
相对而言,单蚂蚁离线更新方式记忆信息少,只需要记忆第s只蚂蚁的路径,并通过信息素更新后,释放该蚂蚁的所有记录信息。
实际上这种方式等价于蚁群离线方式中只有一只蚂蚁。
56信息素的更改5/6与单蚂蚁离线更新方式相比,信息量记忆更小的是信息素在线更新方式,即蚂蚁每走一步,马上回溯并且更新刚刚走过的路径上的信息素,其规则为其中,k为蚂蚁行走的第k步。
57
(1)()()ijijijkkkttt+=+D信息素的更改6/6蚁量算法(ant-quantityalgorithm)的信息素更新为,Q为常量,表示i到j的距离,这样信息浓度会随城市距离的减小而加大。
蚁密算法(ant-densityalgorithm)信息素更新为。
以上三种算法中,蚁环算法效果最好,因为他用的是全局信息,而其余两种算法用的是局部信息。
蚁环离线更新方法很好地保证了残留信息不至于无限积累,非最优路径会逐渐随时间推移被忘记。
58()ijijQkdtD=ijd()ijkQtD=应用1/5光网络的智能管理分布式动态选路及波长分配(RWA,RoutingandWavelengthAssignment)是指在实时业务情况下光通路的路由选择和波长分配的优化问题,是实现自动交换光网络(ASON,AutomaticallySwitchedOpticalNetwork)的关键技术之一。
研究RWA问题的目的是尽可能减少所需要的波长数和降低光路连接请求的阻塞率。
由于RWA问题是NP-C问题,文献中大多将RWA问题拆分成路由和波长分配两个子问题分别加以解决。
但是,由于RWA问题本身是一个不可分割的整体,把RWA分开考虑必然造成难以得到全局最优解的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 什么是 人工智能 算法 65