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

2、略的螞蟻系統信息素根據下式進行更新其中帶精英策略的螞蟻系統上式中 表示精英螞蟻引起的路徑(i, j)上的信息素量的增加 特點：可以使螞蟻系統找出更優的解找到這些解的時間更短精英螞蟻過多會導致搜索早熟收斂 是精英螞蟻的個數 是所找出的最優解的路徑長度蟻群系統蟻群系統(Ant Colony System, ACS)是由Dorigo和Gambardella在1996年提出的蟻群系統做了三個方面的改進：狀態轉移規則為更好更合理地利用新路徑和利用關于問題的先驗知識提供了方法全局更新規則只應用于最優的螞蟻路徑上在建立問題解決方案的過程中，應用局部信息素更新規則蟻群系統狀態轉移規則一只位于節點r的螞蟻通過應

3、用下式給出的規則選擇下一個將要移動到的城市s其中，S根據下列公式得到蟻群系統狀態轉移規則q是在0,1區間均勻分布的隨機數q0的大小決定了利用先驗知識與探索新路徑之間的相對重要性。上述狀態轉移規則被稱為偽隨機比例規則特點：傾向于選擇短的且有著大量信息素的邊作為移動方向蟻群系統全局更新規則只有全局最優的螞蟻才被允許釋放信息素目的：使螞蟻的搜索主要集中在當前循環為止所找出的最好路徑的領域內全局更新在所有螞蟻都完成它們的路徑之后執行，使用下式對所建立的路徑進行更新蟻群系統全局更新規則 為信息素揮發參數，0 1 為到目前為止找出的全局最優路徑全局更新規則的另一個類型稱為迭代最優區別:使用 代替 ， 為當

4、前迭代(循環)中的最優路徑長度這兩種類型對蟻群系統性能的影響差別很小，全局最優的性能要稍微好一些蟻群系統局部更新規則類似于蟻密和蟻量模型中的更新規則螞蟻應用下列局部更新規則對它們所經過的邊進行激素更新實驗發現， 可以產生好的結果，其中n是城市的數量， 是由最近的鄰域啟發產生的一個路徑長度局部更新規則可以有效地避免螞蟻收斂到同一路徑最大-最小螞蟻系統蟻群算法將螞蟻的搜索行為集中到最優解的附近可以提高解的質量和收斂速度，從而改進算法的性能。但這種搜索方式會使早熟收斂行為更容易發生最大-最小螞蟻系統(Max-Min Ant System, MMAS)能將這種搜索方式和一種能夠有效避免早熟收斂的機制結

5、合在一起，從而使算法獲得最優的性能最大-最小螞蟻系統MMAS和AS主要有三個方面不同：為了充分利用循環最優解和到目前為止找出的最優解，在每次循環之后，只有一只螞蟻進行信息素更新。這只螞蟻可能是找出當前循環中最優解的螞蟻，也可能是找出從實驗開始以來最優解的螞蟻為避免搜索的停滯，在每個解的元素上的的信息素軌跡量的值域范圍被限制在 區間內將信息素軌跡初始化為信息素軌跡更新在MMAS中，只有一只螞蟻用于在每次循環后更新信息軌跡經修改的軌跡更新規則如下： 表示迭代最優解或全局最優解的值在蟻群算法中主要使用全局最優解，而在MMAS中則主要使用迭代最優解信息素軌跡的限制不管是選擇迭代最優還是全局最優螞蟻來進

6、行信息素更新，都可能導致搜索的停滯。停滯現象發生的原因：在每個選擇點上一個選擇的信息素軌跡量明顯高于其他的選擇。避免停滯狀態發生的方法：影響用來選擇下一解元素的概率，它直接依賴于信息素軌跡和啟發信息。通過限制信息素軌跡的影響，可以很容易地避免各信息素軌跡之間的差異過大。信息素軌跡的限制MMAS對信息素軌跡的最小值和最大值分別施加了 和 的限制，從而使得對所有信息素軌跡 ，有MMAS收斂：在每個選擇點上，其中一個解元素上的軌跡量為 ，而所有其他可選擇的解元素上的軌跡量為 。若MMAS收斂，通過始終選擇信息素量最大的解元素所構造的解將與算法找出的最優解相一致信息素軌跡的限制 的選取 的選取要基于兩

7、點假設最優解在搜索停滯發生之前不久被找出對解構造的主要影響是由信息素軌跡的上限與下限之間的相對差異決定信息素軌跡的限制在一個選擇點上選擇相應解元素的概率Pdec直接取決于 和在每個選擇點上螞蟻需在avg=n/2個解元素中選擇螞蟻構造最優解，需作n次正確的決策信息素軌跡的初始化在第一次循環后所有信息素軌跡與 相一致通過選擇對這種類型的軌跡初始化來增加在算法的第一次循環期間對新解的探索當將信息素軌跡初始化為 時，選擇概率將增加得更加緩慢實驗表明，將初始值設為 可以改善最大-最小螞蟻系統的性能信息素軌跡的平滑化基本思想：通過增加選擇有著低強度信息素軌跡量解元素的概率以提高探索新解的能力平滑機制有助于

8、對搜索空間進行更有效的探索蟻群算法的應用混流裝配線調度混流裝配線(sequencing mixed models on an assembly line, SMMAL)是指一定時間內，在一條生產線上生產出多種不同型號的產品，產品的品種可以隨顧客需求的變化而變化。SMMAL是車間作業調度問題(job-shop scheduling problem, JSP)的具體應用之一。問題描述以汽車組裝為例，即在組裝所有車輛的過程中，所確定的組裝順序應使各零部件的使用速率均勻化。如果不同型號的汽車消耗零部件的種類大致相同，那么原問題可簡化為單級SMMAL調度問題。問題描述i表示車型數的標號n表示需要裝配的車

9、型數m表示裝配線上需要的零部件種類總數p表示生產調度中子裝配的標號 表示零部件p的理想使用速率j表示車型調度結果(即排序位置)的標號D表示在一個生產循環中需要組裝的各種車型的總和問題描述di表示在一個生產循環中車型i的數量bip表示生產每輛i車型需要零部件p的數量 表示在組裝線調度中前j-1臺車消耗零部件p的數量和蟻群算法在SMMAL中的應用假設有3種車型A、B、C排序，每個生產循環需A型車3輛，B型車2輛，C型車1輛，則每個循環共需生產6輛車。采用下圖的搜索空間定義，列表示6個排序階段，行表示有3種車型可以選擇。蟻群算法就是不斷改變圓圈的大小，最終尋找到滿意的可行解。搜索的初始狀態簡單SMM

10、AL排序的搜索空間舉例經過若干次迭代之后，搜索空間變化，此時最可能的可行解為B-A-C-A-B-A若干次迭代后的狀態局部搜索( )的計算局部搜索 采用的是貪心策略基本思路：每一步均從當前可選擇策略中選取，使目標函數值增加最少的策略，即在確定第j個位置組裝的車型時，如果有多種車型可供選擇，則從中選擇一種車型i，使第j個位置組裝車型i時各零部件的使用速率最為均勻。狀態轉移概率狀態轉移概率公式如下信息素更新規則LB表示目標函數的下限值 表示當前目標函數的平均值Zcutr表示當前的目標函數值這種動態標記的方法可在搜索過程中加大可行解間信息素的差別，避免算法早熟實驗數據實驗參數設置螞蟻系統螞蟻數量N_ant = 5最大循環周期Ncmax = 400 = 0.2Q = 20000 = 0.9LB = 0.0蟻群系統q0 = 0.5全局更新規則中的 和局部更新規則中的 均取0.1實驗參數設置最大-最小螞蟻系統 選取全局最優解帶有精英策略的螞蟻系統精英螞蟻數量:1只實驗結果實驗結果分析直接用貪心策略求解結果：3293.4375螞蟻系統求解SMMAL問題的性能較差對于這個具體的問