《智能算法AntAlgorithm》由會員分享，可在線閱讀，更多相關(guān)《智能算法AntAlgorithm（40頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

2、新 *( 1 ) ( )ij ij ij ijtt 1 m k ij ij k 其中 , 0, k kij Q k L 如 果 螞 蟻 在 本 次 循 環(huán) 中 經(jīng) 過 路 徑 (i,j) 否 則 * * , 0, ij Q L 如 果 邊 (i,j) 是 所 找 出 的 最 優(yōu) 解 的 一 部 分 否 則 帶精英策略的螞蟻系統(tǒng) 上式中 表示精英螞蟻引起的路徑 (i, j)上的信息素量 的增加 * *L 特點： 可以使螞蟻系統(tǒng)找出更優(yōu)的解 找到這些解的時間更短 精英螞蟻過多會導(dǎo)致搜索早熟收斂 是精英螞蟻的個數(shù) 是所找出的最優(yōu)解的路徑長度 蟻群系統(tǒng) 蟻群系統(tǒng) (Ant Colony System,

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

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

5、( , ) ( , )r s r s r s 1 , ( , ) 0, gbLrs 如 果 (r,s) 全 局 最 優(yōu) 路 徑 否 則 蟻群系統(tǒng)全局更新規(guī)則 為信息素?fù)]發(fā)參數(shù)， 0 1 為到目前為止找出的全局最優(yōu)路徑 gbL 全局更新規(guī)則的另一個類型稱為迭代最優(yōu) 區(qū)別 :使用 代替 ， 為當(dāng)前迭代 (循環(huán) )中的最優(yōu)路徑 長度 這兩種類型對蟻群系統(tǒng)性能的影響差別很小，全局最優(yōu) 的性能要稍微好一些 gbL ibLibL 蟻群系統(tǒng)局部更新規(guī)則 類似于蟻密和蟻量模型中的更新規(guī)則 螞蟻應(yīng)用下列局部更新規(guī)則對它們所經(jīng)過的邊進(jìn)行 激素更新 ( , ) ( 1 ) ( , ) ( , ) 01 r s r

6、s r s 其 中 , 為 一 個 參 數(shù) , 0 1 nnnL 實驗發(fā)現(xiàn)， 可以產(chǎn)生好的結(jié)果，其中 n是城 市的數(shù)量， 是由最近的鄰域啟發(fā)產(chǎn)生的一個路徑 長度 nnL 局部更新規(guī)則可以有效地避免螞蟻收斂到同一路徑 最大 -最小螞蟻系統(tǒng) 蟻群算法將螞蟻的搜索行為集中到最優(yōu)解的 附近可以提高解的質(zhì)量和收斂速度，從而改 進(jìn)算法的性能。但這種搜索方式會使 早熟收 斂 行為更容易發(fā)生 最大 -最小螞蟻系統(tǒng) (Max-Min Ant System, MMAS)能將這種搜索方式和一種能夠 有效避 免早熟收斂 的機(jī)制結(jié)合在一起，從而使算法 獲得最優(yōu)的性能 最大 -最小螞蟻系統(tǒng) MMAS和 AS主要有三個方面

7、不同： 為了充分利用循環(huán)最優(yōu)解和到目前為止找出的最優(yōu) 解，在每次循環(huán)之后，只有一只螞蟻進(jìn)行信息素更 新。這只螞蟻可能是找出當(dāng)前循環(huán)中最優(yōu)解的螞蟻， 也可能是找出從實驗開始以來最優(yōu)解的螞蟻 為避免搜索的停滯，在每個解的元素上的的信息素 軌跡量的值域范圍被限制在 區(qū)間內(nèi) 將信息素軌跡初始化為 max min max , 信息素軌跡更新 在 MMAS中，只有一只螞蟻用于在每次循環(huán)后更新 信息軌跡 經(jīng)修改的軌跡更新規(guī)則如下： ( 1 ) ( ) ijb e s tij ijtt 1 ( )ijb e s t b e s tfs 表示迭代最優(yōu)解或全局最優(yōu)解的值 在蟻群算法中主要使用全局最優(yōu)解，而在 MM

8、AS中 則主要使用迭代最優(yōu)解 ()bestfs 信息素軌跡的限制 不管是選擇迭代最優(yōu)還是全局最優(yōu)螞蟻來進(jìn) 行信息素更新，都可能導(dǎo)致搜索的停滯。 停滯現(xiàn)象發(fā)生的原因 ：在每個選擇點上一個 選擇的信息素軌跡量明顯高于其他的選擇。 避免停滯狀態(tài)發(fā)生的方法 ：影響用來選擇下 一解元素的概率，它直接依賴于信息素軌跡 和啟發(fā)信息。通過限制信息素軌跡的影響， 可以很容易地避免各信息素軌跡之間的差異 過大。 信息素軌跡的限制 MMAS對信息素軌跡的最小值和最大值分別施加 了 和 的限制，從而使得對所有信息素軌 跡 ，有 min max ()ij t m in m a x()ij t MMAS收斂 ：在每個選擇

9、點上，其中一個解元素 上的軌跡量為 ，而所有其他可選擇的解元素上 的軌跡量為 。 min max 若 MMAS收斂，通過始終選擇信息素量最大的解 元素所構(gòu)造的解將與算法找出的最優(yōu)解相一致 信息素軌跡的限制 的選取 max m a x 1 1() ()ij t ti opt i t fs opt其 中 , f ( s ) 為 對 于 一 個 具 體 問 題 的 最 優(yōu) 解 g b o p t漸 進(jìn) 的 最 大 值 估 計 通 過 使 用 f ( s ) 代 替 f ( s ) 來 實 現(xiàn) 的選取要基于 兩點假設(shè) 最優(yōu)解在搜索停滯發(fā)生之前不久被找出 對解構(gòu)造的主要影響是由信息素軌跡的上限與下限之間

10、 的相對差異決定 min 信息素軌跡的限制 在一個選擇點上選擇相應(yīng)解元素的概率 Pdec直接取 決于 和 min max 在每個選擇點上螞蟻需在 avg=n/2個解元素中選擇 m a x m a x m in( 1 ) de cP av g 螞蟻構(gòu)造最優(yōu)解，需作 n次正確的決策 de c n be stPP m a xm a x m in ( 1 )( 1 ) ( 1 ) ( 1 ) n b e s td e c nd e c b e s t PP a v g P a v g P 信息素軌跡的初始化 在第一次循環(huán)后所有信息素軌跡與 相一致 max(1) 通過選擇對這種類型的軌跡初始化來增加在算

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

12、ng mixed models on an assembly line, SMMAL)是指一定時間內(nèi)，在一 條生產(chǎn)線上生產(chǎn)出多種不同型號的產(chǎn)品，產(chǎn)品的品 種可以隨顧客需求的變化而變化。 SMMAL是車間 作業(yè)調(diào)度問題 (job-shop scheduling problem, JSP)的具體應(yīng)用之一。 問題描述 以汽車組裝為例，即在組裝所有車輛的過程中，所 確定的組裝順序應(yīng)使各零部件的使用速率均勻化。 如果不同型號的汽車消耗零部件的種類大致相同， 那么原問題可簡化為單級 SMMAL調(diào)度問題。 2 1, 1 1 1 m in ( ) D n m p ip j p ji j i p j b x 1

13、, 0,ji ijx 如 果 車 型 在 調(diào) 度 中 的 位 置 否 則 i ip i p db D 問題描述 i表示車型數(shù)的標(biāo)號 n表示需要裝配的車型數(shù) m表示裝配線上需要的零部件種類總數(shù) p表示生產(chǎn)調(diào)度中子裝配的標(biāo)號 表示零部件 p的理想使用速率 j表示車型調(diào)度結(jié)果 (即排序位置 )的標(biāo)號 D表示在一個生產(chǎn)循環(huán)中需要組裝的各種車型的 總和 p 問題描述 di表示在一個生產(chǎn)循環(huán)中車型 i的數(shù)量 bip表示生產(chǎn)每輛 i車型需要零部件 p的數(shù)量 表示在組裝線調(diào)度中前 j-1臺車消耗零部件 p的 數(shù)量和 1 , 0 ,0j p j p j i i p pxb 且 1,jp 蟻群算法在 SMMAL中

14、的應(yīng)用 假設(shè)有 3種車型 A、 B、 C排序，每個生產(chǎn)循環(huán)需 A型車 3 輛， B型車 2輛， C型車 1輛，則每個循環(huán)共需生產(chǎn) 6輛 車。采用下圖的搜索空間定義，列表示 6個排序階段， 行表示有 3種車型可以選擇。蟻群算法就是不斷改變圓 圈的大小，最終尋找到滿意的可行解。 搜索的初始狀態(tài) 簡單 SMMAL排序的搜索空間舉例 經(jīng)過若干次迭代之后，搜索空間變化，此時 最可能的可行解為 B-A-C-A-B-A 若干次迭代后的狀態(tài) 局部搜索 ( )的計算 ij 2 1, 1 () ij m p ip k p p Q jb 局部搜索 采用的是貪心策略 ij 基本思路：每一步均從當(dāng)前可選擇策略中選 取，

15、使目標(biāo)函數(shù)值增加最少的策略，即在確 定第 j個位置組裝的車型時，如果有多種車 型可供選擇，則從中選擇一種車型 i，使第 j 個位置組裝車型 i時各零部件的使用速率最 為均勻。 狀態(tài)轉(zhuǎn)移概率 狀態(tài)轉(zhuǎn)移概率公式如下 ( 1 ) , ( 1 )() 0, k ij ij k k ij ij ij j tabu i tabu pt 若 否 則 信息素更新規(guī)則 LB表示目標(biāo)函數(shù)的下限值 表示當(dāng)前目標(biāo)函數(shù)的平均值 Zcutr表示當(dāng)前的目標(biāo)函數(shù)值 這種動態(tài)標(biāo)記的方法可在搜索過程中加大可行解間信息素的 差別，避免算法早熟 Z 0 ( 1 ) , 0, c utr k ij Z L B ij Z L B 如 果

16、 車 型 在 調(diào) 度 中 的 位 置 否 則 _ 1 n an t k ij ij k ( ) ( 1 ) ( )ij ij ijt n t 實驗數(shù)據(jù) 實驗參數(shù)設(shè)置 螞蟻系統(tǒng) 螞蟻數(shù)量 N_ant = 5 最大循環(huán)周期 Ncmax = 400 = 0.2 Q = 20000 = 0.9 LB = 0.0 蟻群系統(tǒng) q0 = 0.5 全局更新規(guī)則中的 和局部更新規(guī)則中的 均取 0.1 實驗參數(shù)設(shè)置 最大 -最小螞蟻系統(tǒng) 選取全局最優(yōu)解 ()bestfs m in 0 m a x 0 0 , 1 , L DL 是 利 用 貪 心 策 略 算 得 的 目 標(biāo) 函 數(shù) 值 帶有精英策略的螞蟻系統(tǒng) 精英螞蟻數(shù)量 :1只 實驗結(jié)果 實驗結(jié)果分析 直接用貪心策略求解結(jié)果： 3293.4375 螞蟻系統(tǒng)求解 SMMAL問題的性能較差 對于這個具體的問題，帶精英策略的螞蟻系 統(tǒng)的求解性能并 不好于 螞蟻系統(tǒng) 蟻群系統(tǒng)的性能相對于前兩者而言，有了很 大幅度的提高 最大 -最小螞蟻系統(tǒng)的性能最好，大多數(shù)情 況下的求解結(jié)果已達(dá)到實際的最優(yōu)解 實驗界面 實驗界面 蟻群系統(tǒng)在 TSP問題中的應(yīng)用 10城市 TSP問題 20城市 TSP問題 蟻群系統(tǒng)在 TSP問題中的應(yīng)用 30城市 TSP問題 48城市 TSP問題 Questions