Matlab蟻群算法介紹PPT

1、改進(jìn)的蟻群算法及其應(yīng)用SA07011068 章宗長(zhǎng)SA07011065 石軻2008-6-23改進(jìn)的蟻群算法Macro DorigoGambardella帶精英策略的螞蟻系統(tǒng)o 帶精英策略的螞蟻系統(tǒng)（Ant System with elitist strategy, ASelite）是最早的改進(jìn)螞蟻系統(tǒng)o 遺傳算法中的精英策略n傳統(tǒng)的遺傳算法可能會(huì)導(dǎo)致最適應(yīng)個(gè)體的遺傳信息丟失n精英策略的思想是保留住一代中的最適應(yīng)個(gè)體o 螞蟻系統(tǒng)中的精英策略n每次循環(huán)之后給予最優(yōu)解以額外的信息素量n這樣的解被稱為全局最優(yōu)解（global-best solution）n找出這個(gè)解的螞蟻被稱為精英螞蟻(elitis

2、t ants)帶精英策略的螞蟻系統(tǒng)o 信息素根據(jù)下式進(jìn)行更新*(1)( )ijijijijtt1mkijijk其中,0,kkijQkL如果螞蟻 在本次循環(huán)中經(jīng)過路徑(i,j)否則*,0,ijQL如果邊(i,j)是所找出的最優(yōu)解的一部分否則帶精英策略的螞蟻系統(tǒng)o 上式中 表示精英螞蟻引起的路徑(i, j)上的信息素量的增加 *Lo 特點(diǎn)：n可以使螞蟻系統(tǒng)找出更優(yōu)的解n找到這些解的時(shí)間更短n精英螞蟻過多會(huì)導(dǎo)致搜索早熟收斂o 是精英螞蟻的個(gè)數(shù)o 是所找出的最優(yōu)解的路徑長(zhǎng)度蟻群系統(tǒng)o 蟻群系統(tǒng)(Ant Colony System, ACS)是由Dorigo和Gambardella在1996年提出的o

3、蟻群系統(tǒng)做了三個(gè)方面的改進(jìn)：n狀態(tài)轉(zhuǎn)移規(guī)則為更好更合理地利用新路徑和利用關(guān)于問狀態(tài)轉(zhuǎn)移規(guī)則為更好更合理地利用新路徑和利用關(guān)于問題的先驗(yàn)知識(shí)提供了方法題的先驗(yàn)知識(shí)提供了方法n全局更新規(guī)則只應(yīng)用于最優(yōu)的螞蟻路徑上全局更新規(guī)則只應(yīng)用于最優(yōu)的螞蟻路徑上n在建立問題解決方案的過程中，應(yīng)用局部信息素更新規(guī)在建立問題解決方案的過程中，應(yīng)用局部信息素更新規(guī)則則蟻群系統(tǒng)狀態(tài)轉(zhuǎn)移規(guī)則o 一只位于節(jié)點(diǎn)r的螞蟻通過應(yīng)用下式給出的規(guī)則選擇下一個(gè)將要移動(dòng)到的城市s0arg max ( , ) ( , ) ,ku allowedr ur uqqsS如果按先驗(yàn)知識(shí)選擇路徑否則其中，S根據(jù)下列公式得到( )( ),( )( )

4、( )0,kijijkkisisijs allowedttjallowedttPtotherwise蟻群系統(tǒng)狀態(tài)轉(zhuǎn)移規(guī)則o q是在0,1區(qū)間均勻分布的隨機(jī)數(shù)o q0的大小決定了利用先驗(yàn)知識(shí)與探索新路徑之間的相對(duì)重要性。o 上述狀態(tài)轉(zhuǎn)移規(guī)則被稱為偽隨機(jī)比例規(guī)則o 特點(diǎn)：傾向于選擇短的且有著大量信息素的邊作為移動(dòng)方向蟻群系統(tǒng)全局更新規(guī)則o 只有全局最優(yōu)的螞蟻才被允許釋放信息素o 目的：使螞蟻的搜索主要集中在當(dāng)前循環(huán)為止所找出的最好路徑的領(lǐng)域內(nèi)o 全局更新在所有螞蟻都完成它們的路徑之后執(zhí)行，使用下式對(duì)所建立的路徑進(jìn)行更新( , )(1)( , )( , )r sr sr s1,( , )0,gbLr

5、 s如果(r,s) 全局最優(yōu)路徑否則蟻群系統(tǒng)全局更新規(guī)則o 為信息素?fù)]發(fā)參數(shù)，0 1o 為到目前為止找出的全局最優(yōu)路徑gbLo 全局更新規(guī)則的另一個(gè)類型稱為迭代最優(yōu)n區(qū)別:使用 代替 ， 為當(dāng)前迭代(循環(huán))中的最優(yōu)路徑長(zhǎng)度n這兩種類型對(duì)蟻群系統(tǒng)性能的影響差別很小，全局最優(yōu)的性能要稍微好一些gbLibLibL蟻群系統(tǒng)局部更新規(guī)則o 類似于蟻密和蟻量模型中的更新規(guī)則o 螞蟻應(yīng)用下列局部更新規(guī)則對(duì)它們所經(jīng)過的邊進(jìn)行激素更新( , )(1)( , )( , )01r sr sr s其中, 為一個(gè)參數(shù),01nnn Lo 實(shí)驗(yàn)發(fā)現(xiàn)， 可以產(chǎn)生好的結(jié)果，其中n是城市的數(shù)量， 是由最近的鄰域啟發(fā)產(chǎn)生的一個(gè)路徑

6、長(zhǎng)度nnLo 局部更新規(guī)則可以有效地避免螞蟻收斂到同一路徑最大-最小螞蟻系統(tǒng)o 蟻群算法將螞蟻的搜索行為集中到最優(yōu)解的附近可以提高解的質(zhì)量和收斂速度，從而改進(jìn)算法的性能。但這種搜索方式會(huì)使早熟收斂行為更容易發(fā)生o 最大-最小螞蟻系統(tǒng)(Max-Min Ant System, MMAS)能將這種搜索方式和一種能夠有效避免早熟收斂的機(jī)制結(jié)合在一起，從而使算法獲得最優(yōu)的性能最大-最小螞蟻系統(tǒng)o MMAS和AS主要有三個(gè)方面不同：n 為了充分利用循環(huán)最優(yōu)解和到目前為止找出的最優(yōu)解，在每次循環(huán)之后，只有一只螞蟻進(jìn)行信息素更新。這只螞蟻可能是找出當(dāng)前循環(huán)中最優(yōu)解的螞蟻，也可能是找出從實(shí)驗(yàn)開始以來最優(yōu)解的螞蟻

7、n 為避免搜索的停滯，在每個(gè)解的元素上的的信息素軌跡量的值域范圍被限制在 區(qū)間內(nèi)n 將信息素軌跡初始化為maxminmax,信息素軌跡更新o 在MMAS中，只有一只螞蟻用于在每次循環(huán)后更新信息軌跡o 經(jīng)修改的軌跡更新規(guī)則如下：(1)( )ijbestijijtt1()ijbestbestf so 表示迭代最優(yōu)解或全局最優(yōu)解的值o 在蟻群算法中主要使用全局最優(yōu)解，而在MMAS中則主要使用迭代最優(yōu)解()bestf s信息素軌跡的限制o 不管是選擇迭代最優(yōu)還是全局最優(yōu)螞蟻來進(jìn)行信息素更新，都可能導(dǎo)致搜索的停滯。o 停滯現(xiàn)象發(fā)生的原因：在每個(gè)選擇點(diǎn)上一個(gè)選擇的信息素軌跡量明顯高于其他的選擇。o 避免停

8、滯狀態(tài)發(fā)生的方法：影響用來選擇下一解元素的概率，它直接依賴于信息素軌跡和啟發(fā)信息。通過限制信息素軌跡的影響，可以很容易地避免各信息素軌跡之間的差異過大。信息素軌跡的限制o MMAS對(duì)信息素軌跡的最小值和最大值分別施加了 和 的限制，從而使得對(duì)所有信息素軌跡 ，有minmax( )ijtm inm ax( )ijto MMAS收斂：在每個(gè)選擇點(diǎn)上，其中一個(gè)解元素上的軌跡量為 ，而所有其他可選擇的解元素上的軌跡量為 。minmaxo 若MMAS收斂，通過始終選擇信息素量最大的解元素所構(gòu)造的解將與算法找出的最優(yōu)解相一致信息素軌跡的限制o 的選取maxm ax11( )()ijttio p titfs

9、opt其中,f(s)為對(duì)于一個(gè)具體問題的最優(yōu)解gbopt漸進(jìn)的最大值估計(jì)通過使用f(s )代替f(s)來實(shí)現(xiàn)o 的選取要基于兩點(diǎn)假設(shè)n最優(yōu)解在搜索停滯發(fā)生之前不久被找出n對(duì)解構(gòu)造的主要影響是由信息素軌跡的上限與下限之間的相對(duì)差異決定min信息素軌跡的限制o 在一個(gè)選擇點(diǎn)上選擇相應(yīng)解元素的概率Pdec直接取決于 和minmaxo 在每個(gè)選擇點(diǎn)上螞蟻需在avg=n/2個(gè)解元素中選擇maxmaxmin(1)decPavgo 螞蟻構(gòu)造最優(yōu)解，需作n次正確的決策d e cnb e stPPmaxmaxmin(1)(1)(1)(1)nbestdecndecbestPPavgPavgP信息素軌跡的初始化o

10、在第一次循環(huán)后所有信息素軌跡與 相一致max(1)o 通過選擇對(duì)這種類型的軌跡初始化來增加在算法的第一次循環(huán)期間對(duì)新解的探索o 當(dāng)將信息素軌跡初始化為 時(shí)，選擇概率將增加得更加緩慢o 實(shí)驗(yàn)表明，將初始值設(shè)為 可以改善最大-最小螞蟻系統(tǒng)的性能maxmax(1)信息素軌跡的平滑化o 基本思想：通過增加選擇有著低強(qiáng)度信息素軌跡量解元素的概率以提高探索新解的能力*max( )( )( )( )ijijijtttt *( )( )ijijtt其中,01,和分別為平滑化之前和之后的信息素軌跡量o 平滑機(jī)制有助于對(duì)搜索空間進(jìn)行更有效的探索蟻群算法的應(yīng)用混流裝配線調(diào)度混流裝配線(sequencing mixe

11、d models on an assembly line, SMMAL)是指一定時(shí)間內(nèi)，在一條生產(chǎn)線上生產(chǎn)出多種不同型號(hào)的產(chǎn)品，產(chǎn)品的品種可以隨顧客需求的變化而變化。SMMAL是車間作業(yè)調(diào)度問題(job-shop scheduling problem, JSP)的具體應(yīng)用之一。問題描述o 以汽車組裝為例，即在組裝所有車輛的過程中，所確定的組裝順序應(yīng)使各零部件的使用速率均勻化。如果不同型號(hào)的汽車消耗零部件的種類大致相同，那么原問題可簡(jiǎn)化為單級(jí)SMMAL調(diào)度問題。21,111min()Dnmpipjpjijipjbx1,0,jiijx如果車型 在調(diào)度中的 位置否則iipipd bD問題描述o i表

12、示車型數(shù)的標(biāo)號(hào)o n表示需要裝配的車型數(shù)o m表示裝配線上需要的零部件種類總數(shù)o p表示生產(chǎn)調(diào)度中子裝配的標(biāo)號(hào)o 表示零部件p的理想使用速率o j表示車型調(diào)度結(jié)果(即排序位置)的標(biāo)號(hào)o D表示在一個(gè)生產(chǎn)循環(huán)中需要組裝的各種車型的總和p問題描述o di表示在一個(gè)生產(chǎn)循環(huán)中車型i的數(shù)量o bip表示生產(chǎn)每輛i車型需要零部件p的數(shù)量o 表示在組裝線調(diào)度中前j-1臺(tái)車消耗零部件p的數(shù)量和1,0,0jpjpjiippx b且1,jp蟻群算法在SMMAL中的應(yīng)用o 假設(shè)有3種車型A、B、C排序，每個(gè)生產(chǎn)循環(huán)需A型車3輛，B型車2輛，C型車1輛，則每個(gè)循環(huán)共需生產(chǎn)6輛車。采用下圖的搜索空間定義，列表示6個(gè)排

13、序階段，行表示有3種車型可以選擇。蟻群算法就是不斷改變圓圈的大小，最終尋找到滿意的可行解。搜索的初始狀態(tài)簡(jiǎn)單SMMAL排序的搜索空間舉例o 經(jīng)過若干次迭代之后，搜索空間變化，此時(shí)最可能的可行解為B-A-C-A-B-A若干次迭代后的狀態(tài)局部搜索( )的計(jì)算ij21,1()ijmpipkppQjbo 局部搜索 采用的是貪心策略ijo 基本思路：每一步均從當(dāng)前可選擇策略中選取，使目標(biāo)函數(shù)值增加最少的策略，即在確定第j個(gè)位置組裝的車型時(shí)，如果有多種車型可供選擇，則從中選擇一種車型i，使第j個(gè)位置組裝車型i時(shí)各零部件的使用速率最為均勻。狀態(tài)轉(zhuǎn)移概率o 狀態(tài)轉(zhuǎn)移概率公式如下(1),(1)( )0,kiji

14、jkkijijijj tabuitabupt 若否則信息素更新規(guī)則o LB表示目標(biāo)函數(shù)的下限值o 表示當(dāng)前目標(biāo)函數(shù)的平均值o Zcutr表示當(dāng)前的目標(biāo)函數(shù)值o 這種動(dòng)態(tài)標(biāo)記的方法可在搜索過程中加大可行解間信息素的差別，避免算法早熟Z0(1),0,cutrkijZLBijZLB如果車型 在調(diào)度中的 位置否則_1n antkijijk()(1)( )ijijijtnt 實(shí)驗(yàn)數(shù)據(jù)實(shí)驗(yàn)參數(shù)設(shè)置o 螞蟻系統(tǒng)n螞蟻數(shù)量N_ant = 5n最大循環(huán)周期Ncmax = 400n = 0.2nQ = 20000n = 0.9nLB = 0.0o 蟻群系統(tǒng)nq0 = 0.5n全局更新規(guī)則中的 和局部更新規(guī)則中的 均取0.1實(shí)驗(yàn)參數(shù)設(shè)置o 最大-最小螞蟻系統(tǒng)n 選取全局最優(yōu)解()bestf smin0max00,1,LD L 是利用貪心策略算得的目標(biāo)函數(shù)值o 帶有精英策略的螞蟻系統(tǒng)n精英螞蟻數(shù)量:1只實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)結(jié)果分析