【文章內(nèi)容簡介】 隨機的，但螞蟻可通過自組織過程形成高 度有序的群體行為。 由上述假設(shè)可見，基本蟻群算法的 尋優(yōu)機制包含兩個基本階段：適應(yīng)階段和協(xié)作階段。在適應(yīng)階段，各候選解根據(jù)積累的信息不斷調(diào)整自身結(jié)構(gòu)，路徑上經(jīng)過的螞蟻越多，信息量越大 ，則該路徑越容易被選擇，時間越長，信息量越小；在協(xié)作階段，候選解之間通過信息交流 ，以期望產(chǎn)生性能更好的解。 螞蟻覓食的過程與 旅行商問題 (TSP)之間有很大的相似性，以求解 TSP 為例 ，其 蟻群算法的數(shù)學(xué)模型 如下： 求解 n 個城市的 TSP 時 ， 設(shè) 蟻群中螞蟻的數(shù)量為 m ； ()ibt表示 t 時刻位于城市i 的螞蟻個數(shù)，則1 ()niim b t???； ijd 表示兩城市 i 和 j 間的距離； ij? 表示路徑 (, )ij 的能見度 ，反映由城市 i 轉(zhuǎn)移到城市 j 的啟發(fā)程度； ij? 表示連接城市 i 和 j 路徑上的信息 素 強度。在初始時刻各條路徑上的信息 素 量相等，即 (0)ij C? ? （ C 為常數(shù)）。 螞蟻 k ( 1,2, ,km? )在運動過程中，根據(jù)各條路徑上的信息 素 量 決定轉(zhuǎn)移方向。用禁忌表 ktabu ( 1,2, ,km? )來記錄螞蟻 k 當(dāng)前所走過的城市。在搜索過程中，螞蟻根據(jù)路徑上的信息素量及路徑的啟發(fā)信息來計算轉(zhuǎn)移概率 。 ()kijPt表示在 t 時刻螞蟻 k 由 i 轉(zhuǎn)移到 j 的轉(zhuǎn)移概率： [ ( ) ] [ ( ) ] ,[ ( ) ] [ ( ) ]()0kaij ijkakis isijs ta b utt j t abuttPtot he rw i se???????? ? ??? ?? ????? () 其中， 參數(shù) ? 和 ? 分別反映螞蟻 在運動過程中所積累的信息和啟發(fā)信息在其選擇路徑中的相對重要性。 每只螞蟻在完成對 n 個城市的遍歷后，要對殘余信息進行更新處理，以避免殘余信息過多而淹沒了啟發(fā)信息。由此， tn? 時刻在路徑 (, )ij 上的信息素量根據(jù)下式 進行 調(diào)整： ( ) (1 ) ( ) ( )ij ij ijt n t t? ? ? ?? ? ? ? ? ? () 1( ) ( )ijm kij ktt???? ? ?? () 基于微粒群算法的 圖像 閾值分割 方法 及 其 應(yīng)用 8 其中 ， ? 是信息素揮發(fā)系數(shù)，則 1?? 表示信息素殘余因子； ()ij t??表示本次循環(huán)中路徑 (, )ij 上的信息素增量； ()ijk t??表示 本次循環(huán)中第 k 只螞蟻留 在路徑 (, )ij 上的信息素量。 在實際應(yīng)用中，ij??、ijk?? 、ijkP的表達形式可以不同， 要 根據(jù) 具體問題 、具體算法 來 加以 確定。 蟻群算法流程 以 TSP 為例，基本蟻群算法的實現(xiàn)流程 如下 ： ⑴ 初始化各參數(shù)。 令 時間 t =0， 迭代次數(shù) N =0，設(shè)置最大迭代次數(shù) maxN ，螞蟻總數(shù)為 m ，元素（城市）個數(shù)為 n ，令連 接元素 i 和 j 路徑上的信息量 ()ijt? =C (C為常數(shù) )，初始時刻 (0)ij?? =0； ⑵ 迭代次數(shù) N =N +1； ⑶ 螞蟻的禁忌表索引號 k =1； ⑷ 螞蟻數(shù)目 k =k +1； ⑸ 根據(jù)狀態(tài)轉(zhuǎn)移概率公式 ()計算的概率選擇下一個元素 j ， j? ktabu ， 螞蟻個體向元素 j 前進 ； ⑹ 修改禁忌表。將元素 j 放到該螞蟻個體的禁忌表中； ⑺ 若 km? ，元素未遍歷完，則轉(zhuǎn)到第 ⑷ 步，否則繼續(xù)執(zhí)行第 ⑻ 步； ⑻ 按照公式 ()和 ()進行信息量更新； ⑼ 若 maxNN? ，則迭代結(jié)束并輸出計算結(jié)果，否則清空禁忌表 并轉(zhuǎn)到第 ⑵ 步。 微粒群算法 微粒群算法 思想的起源 自然界中，鳥群中的每個個體是離散的，它們的排列看起來是隨機的，但在整體的運動過程中卻保持著驚人的同步性。這些呈分布狀態(tài)的群體所表現(xiàn)出的似乎是有意識的集中控制，這一特性引起了研究者們的注意 。有些研究者對鳥群的運動進行了計算機仿真，通過對個體設(shè)定簡單的運動規(guī)則，來模擬鳥群整體的復(fù)碩士學(xué)位論文 9 雜行為。 1986 年， Craig Reynolds 提出了 Boid 模型 ，用以模擬鳥類聚集飛行的行為。仿真的目的主要是研究如何對各種可能的運動進行描述和控制。通過對 現(xiàn)實世界中這些群體運動的觀察，在計算機中復(fù)制和重建這些運動軌跡，并對這些運動進行抽象建模，以發(fā)現(xiàn)新的運動模式。 Reynolds 在仿真中采用了下列三條簡單的行為規(guī)則 [36]： ⑴ 飛離最近的個體，以避免碰撞 ⑵ 飛向目標 ⑶ 飛向 群體的中心 群體中的每個個體的行為都遵循以上的三條規(guī)則，通過這個模型來模擬整個群體的運動。 生物學(xué)家 Frank Heppner 在 Boid 模型的基礎(chǔ)上增加了 一個仿真條件 —— 鳥類被吸引飛向棲息地 ， 提出了新的鳥群模型。 在仿真中，鳥群在剛飛起的時候并沒有目的地，在空中自然地形成群體， 直到群體中的一只鳥飛向棲息地，當(dāng)設(shè)置期望棲息比期望留在鳥群中具有較大的適應(yīng)值時，每只鳥都離開群體飛向棲息地，隨后就自然形成鳥群，整個群體飛向棲息地。 鳥類尋找棲息地與對一個特定問題尋找解很相似 ，已經(jīng)找到棲息地的鳥引導(dǎo)它周圍的鳥飛向棲息地的方式，增加了整個鳥群都找到棲息地的可能性。 美國社會心理學(xué)家 James Kennedy 和電氣工程師 Russell Eberhart 受到這個模型的啟發(fā)于1995 年共同提出了微粒群優(yōu)化算法（ Particle Swarm Optimization, PSO）。該算法將鳥群運 動模型中的棲息地類比于所求問題解空間中可能解的位置，通過個體間的信息傳遞，引導(dǎo)整個群體向可能解的方向移動，在求解過程中逐步增加發(fā)現(xiàn)較好解的 可能性。 群體中的鳥被抽象成為沒有質(zhì)量和體積的“微?！?，通過這些微粒間的相互協(xié)作和信息共享，使其運動速度受到自身和群體的歷史運動狀態(tài)的影響，以自身和群體的歷史最優(yōu)位置來對微粒當(dāng)前的運動方向和運動速度加以影響，較好地協(xié)調(diào)微粒本身和群體運動之間的關(guān)系，以利于群體在復(fù)雜的解空間中進行尋優(yōu)操作。 微粒群算法基本原理 基于微粒群算法的 圖像 閾值分割 方法 及 其 應(yīng)用 10 PSO 算法 與其它進化類算法類似，也采用“群體”與“進化 ”的概念，同樣也是依據(jù)個體（微粒）的適應(yīng)值大小進行操作。所不同的是， PSO 算法不像其它進化算法那樣對于個體使用進化算子，而是將每個個體看作是在 n 維搜索空間中的一個沒有重量和體積的微粒，并在搜索空間中以一定的速度飛行。 通過對環(huán)境的學(xué)習(xí)和適應(yīng) ，根據(jù)個體和群體的飛行經(jīng)驗的綜合分析結(jié)果來動態(tài)調(diào)整 飛行速度。 在整個尋優(yōu)過程中，每個微粒的適應(yīng)值（ Fitness Value）取決于所選優(yōu)化函數(shù)的值。并且每個微粒都具有以下幾類信息：微粒當(dāng)前所處的位置；到目前為止 微粒所經(jīng)歷過的有最好適應(yīng)值的 位置 pbest， pbest 視為 微粒自身的飛行經(jīng)驗 ；到目前為止整個群體所有微粒所經(jīng)歷過的最好位置 gbest（ gbest 是 pbest 中的最優(yōu)值）。 PSO 算法是一種基于迭代模式的優(yōu)化算法，最初被用于連續(xù)空間的優(yōu)化。在連續(xù)空間坐標系中，該算法的數(shù)學(xué)描述如下： 設(shè)微粒群體規(guī)模為 N。 微粒 i ( 1,2, ,iN? )在 n 維空間中 當(dāng)前 的坐標位置為 12( , , , )i i i inx x x x? 。 微粒 i ( 1,2, ,iN? )當(dāng)前的飛行速度為 12( , , , )i i i inv v v v? 。 微粒 i ( 1,2, ,iN? )所經(jīng)歷的最好位置為 12( , , , )i i i inp p p p? 根據(jù)以上的定義，微粒 i ( 1,2, ,iN? )在第 j （ 1,2, ,jN? ）維子空間中的飛行速度可描述為： 1 1 2 2( 1 ) ( ) ( ) ( ( ) ( ) ) ( ) ( ( ) ( ) )ij ij ij ij gj ijv t v t c ran d t p t x t c ran d t p t x t? ? ? ? ? ? ? ? ? ? () ( 1 ) ( ) ( 1 )ij ij ijx t x t v t? ? ? ? () 其中： t 表示第 t 代； 1c ， 2c 為加速常數(shù)，通常在 0~2 間取值； 1rand ~U(0,1)和2rand ~U(0,1)為兩個相互獨立的隨機函數(shù)； gjp 為整個群體所有微粒所經(jīng)歷的最好位置。 為了減少在進化過程中，微粒離開搜索空間的可能性， ijv 通常限定在一定的范圍內(nèi)，即 max max[ , ]ijv v v?? 。如果問題的搜索空間限定在 max max[ , ]xx? 內(nèi)，則可設(shè)定 max maxv k x?? ， ?? 。 微粒群算法流程 基本 PSO 算法的流程如下： 碩士學(xué)位論文 11 ⑴ 初始化所有微粒。群體規(guī)模 N；在允許范圍內(nèi)隨機設(shè)置微粒的初始位置和速度；每個微粒的 pbest 設(shè)為其初始位置 ， pbest 中的最 優(yōu) 值設(shè)為 gbest。 ⑵ 計算每個微粒的適應(yīng)值 。 ⑶ 對每個微粒，將其適應(yīng)值與其經(jīng)歷過的最 優(yōu) 位置 pbest 進行比較，如果優(yōu)于 pbest，則將其作為當(dāng)前的最 優(yōu) 位置 pbest。 ⑷ 對每個微粒，將其適應(yīng)值與 群體 經(jīng)歷過的最 優(yōu) 位置 gbest 進 行比較，如果優(yōu)于 gbest，則將其作為 群體 的最 優(yōu) 位置 gbest。 ⑸ 根據(jù)方程 ()和 ()對微粒的速度和位置進行進化。 ⑹ 檢查終止條件 (達到預(yù)設(shè)最大迭代次數(shù) maxG 或者滿足足夠好的適應(yīng)值，或者最優(yōu)解停滯不再變化 )。若滿足終止條件，則停止迭代 ，輸出結(jié)果 ；否則返回步驟 ⑵ 。 基本微粒群算法的結(jié)構(gòu)流程圖如圖 所示。 微粒群算法的發(fā)展 PSO 算法是一種原理簡單的啟發(fā)式算法。它可以用于求解一些非線性 、 多峰基于微粒群算法的 圖像 閾值分割 方法 及 其 應(yīng)用 12 值的復(fù)雜的優(yōu)化問題， 其 算法易于實現(xiàn)，需要 調(diào)整的參數(shù)也很少，因此受到了相關(guān)領(lǐng)域眾多學(xué)者的關(guān)注。作為一種新型的優(yōu)化搜索算法，基本 PSO 算法不是很完善，在實際應(yīng)用中，存在過早收斂以及全局收斂性差的缺點 [37][38]。針對這些問題，研究者對該算法做了大量的改進研究，主要體現(xiàn)在： PSO 算法離散二進制模型[39][40]、 參數(shù)的選擇與設(shè)計 [41][42][43]等。 PSO 算法離散二進制模型 PSO 算法最初是一種基于實值連續(xù)空間的優(yōu)化技巧，然而許多工程應(yīng)用問題是組合優(yōu)化問題，因而需要將微粒群算法在二進制空間進行擴展。二進制 PSO 算法也為 PSO 算法與遺傳算法的性能比較提供了一個有用的方式。 在離散二進制模型中，個體進行二進制決策的概率是一個與個體和群體相關(guān)的函數(shù)， 文獻 [10]對它的 定義如下： ( ( ) 1 ) ( ( 1 ) , ( 1 ) , , )ij ij ij ij gjP x t f x t v t p p? ? ? ? () 其中： ( ( ) 1)ijP x t ? 是個體 i 為位串上第 j 位選擇 1 的概率（選擇 0 的概率為 1? P）； ()ijxt是個體 i 的位串位置 j 的當(dāng)前 狀態(tài)； t 是當(dāng)前時間步； ()ijvt代表個體做一個或另一個選擇的傾向； ijp 是迄今為止發(fā)現(xiàn)的最好狀態(tài)，例如，如果 ijx 為 1 時個體取得最大成功，那么 ijp 為 1；如果 ijx 為 0 時個體取得最大成功，那么 ijp 為 0； gjp 是鄰域的最好狀態(tài)，如果鄰域的任一成員在處于 1 狀態(tài)時取得最大成功，那么 gjp 為 1；否則為 0。 二進制 PSO 算法與基本 PSO 算法的主要區(qū)別在于位置更新方程不同。離散二進制模型中速度和位置更新等式可表示為： 1 1 2 2( 1 ) ( ) ( ) ( ( ) ( ) ) ( ) ( ( ) ( ) )ij ij ij ij gj ijv t v t c ran d t p t x t c ran d t p t x t? ? ? ? ? ? ? ? ? ? () if( () ( )ijrand S v? ) then ijx =1； () else ijx =0； 碩士學(xué)位論文 13 其中 ()ijSv為 Sigmoid 函數(shù)，定義為： 1()1 ex p ( )ij ijSv v? ??； ()rand 為 [0， 1]之間的隨機數(shù)。速度分量ijv決定了位置分量ijx取 1 或 0 的概率，ijv越大，則ijx取 1 的概率越大。在離散二進制 PSO 算法中，保留了 maxv ，它可以限制 ijv ，以使 ()ijSv 不會太接近 或 ，從而限制 ijx 取 1 或