蟻群演算法與粒子群演算法優缺點個人精華篇

蟻群演算法與粒子群演算法優缺點

蟻群演算法(aco)是受自然界中螞蟻搜尋食物行為的啟發，是一種群智慧型優化演算法。它基於對自然界真實蟻群的集體覓食行為的研究，模擬真實的蟻群協作過程。演算法由若干個螞蟻共同構造解路徑，通過在解路徑上遺留並交換資訊素提高解的質量，進而達到優化的目的。

蟻群演算法作為通用隨機優化方法，已經成功的應用於tsp等一系列組合優化問題中，並取得了較好的結果。但由於該演算法是典型的概率演算法，演算法中的引數設定通常由實驗方法確定，導致方法的優化效能與人的經驗密切相關，很難使演算法效能最優化。

蟻群演算法中每只螞蟻要選擇下一步所要走的地方，在選路過程中，螞蟻依據概率函式選擇將要去的地方，這個概率取決於地點間距離和資訊素的強度。

(ｔ+ｎ) = (t

上述方程表示資訊素的保留率，1－表示資訊素的揮發率，為了防止資訊的無限積累，取值範圍限定在0～1。δ ij 表示螞蟻k在時間段t到 (t +n)的過程中，在i到j的路徑上留下的殘留資訊濃度。

在上述概率方程中，引數α和β:是通過實驗確定的。它們對演算法效能同樣有很大的影響。

α值的大小表明留在每個節點上資訊量受重視的程度，其值越大，螞蟻選擇被選過的地點的可能性越大。β值的大小表明啟發式資訊受重視的程度。

這兩個引數對蟻群演算法效能的影響和作用是相互配合，密切相關的。但是這兩個引數只能依靠經驗或重複除錯來選擇。

在採用蟻群－粒子群混合演算法時，我們可以利用pso對蟻群系統引數α和β的進行訓練。具體訓練過程：假設有n個粒子組成乙個群落，其中第i個粒子表示為乙個二維的向量 xi = ( xi1 , xi2 ) , i = 1, 2, ,n，即第i個粒子在搜尋空間的中的位置是xi。

換言之，每個粒子的位置就是乙個潛在的解。將xi帶入反饋到蟻群系統並按目標函式就可以計算出其適應值，根據適應值的大小衡量解的優劣。

蟻群演算法的優點：

蟻群演算法與其他啟發式演算法相比，在求解效能上，具有很強的魯棒性（對基本蟻群演算法模型稍加修改，便可以應用於其他問題）和搜尋較好解的能力。

蟻群演算法是一種基於種群的進化演算法，具有本質並行性，易於並行實現。

蟻群演算法很容易與多種啟發式演算法結合，以改善演算法效能。

蟻群演算法存在的問題：

tsp問題是一類經典的組合優化問題，即在給定城市個數和各城市之間距離的條件下，找到一條遍歷所有城市且每個城市只能訪問一次的總路程最短的路線。蟻群演算法在tsp問題應用中取得了良好的效果，但是也存在一些不足：

（1），如果引數α和β設定不當，導致求解速度很慢且所得解的質量特別差。

（2），基本蟻群演算法計算量大，求解所需時間較長。

（3），基本蟻群演算法中理論上要求所有的螞蟻選擇同一路線，該線路即為所求的最優線路；但在實際計算中，在給定一定迴圈數的條件下很難達到這種情況。

另一方面，在其它的實際應用中，如影象處理中尋求最優模板問題，我們並不要求所有的螞蟻都找到最優模板，而只需要乙隻找到最優模板即可。如果要求所有的螞蟻都找到最優模板，反而影響了計算效率。

蟻群演算法收斂速度慢、易陷入區域性最優。蟻群演算法中初始資訊素匱乏。蟻群演算法一般需要較長的搜尋時間，其複雜度可以反映這一點；而且該方法容易出現停滯現象，即搜尋進行到一定程度後，所有個體發現的解完全一致，不能對解空間進一步進行搜尋，不利於發現更好的解。

粒子群優化具有相當快的逼近最優解的速度，可以有效的對系統的引數進行優化。粒子群演算法的本質是利用當前位置、全域性極值和個體極值3個資訊，指導粒子下一步迭代位置。其個體充分利用自身經驗和群體經驗調整自身的狀態是粒子群演算法具有優異特性的關鍵。

pso演算法的優勢在於求解一些連續函式的優化問題。

pso演算法存在的問題：

問題最主要的是它容易產生早熟收斂（尤其是在處理複雜的多峰搜尋問題中）、區域性尋優能力較差等。pso演算法陷入區域性最小，主要歸咎於種群在搜尋空間中多樣性的丟失。

不同演算法的混合模型主要分為兩類：（1）全域性優化演算法與區域性優化演算法混合；（2）全域性優化演算法與全域性優化演算法混合。縱觀各種與pso演算法相關的混合演算法，大多數基本上採用一種策略對其改進，要麼與其他演算法，要麼加入變異操作，同時採用兩種策略的混合演算法較少。

上述策略中，兩者之間有一定的矛盾性，全域性演算法與區域性演算法相混合，儘管可以提高區域性收斂速度，但也加劇了陷入區域性極小的可能；全域性演算法與全域性演算法的混合，演算法的區域性細化能力仍然沒有改善。但如果只加入變異操作，則演算法的探測能力得到提高，但也損害了其區域性開發能力。

因此如果將區域性搜尋和變異操作同時混合到pso演算法中，通過適當的調節，發揮各自的優點，提高演算法的開發能力，增加變異操作防止演算法早熟，來共同提高pso演算法的全域性尋優能力。

融合策略：

（1）針對蟻群演算法初始資訊素匱乏的缺點，採用其他演算法生成初始資訊素分布，利用蟻群演算法求精確解，從而提高時間效率和求解精度。（使用的其他演算法的求解結果以什麼規則轉換成蟻群演算法的資訊素初值，需要通過多次實驗）

（2）將其他演算法（如遺傳演算法）引入到蟻群演算法系統的每次迭代過程中。以蟻群系統每一代形成的解作為其他演算法的初始種群，然後經過其他演算法的多次迭代，試圖尋找更好的解，從而加快蟻群系統的收斂速度，提高求解速率。

（3）蟻群演算法中α，β的選取往往是通過經驗來取得的，而選取不當時會造成演算法的效能大大降低，因此可以利用其他演算法對蟻群系統引數α，β進行訓練。

（4）對於蟻群演算法出現過早收斂於非全域性最優解以及時間過長的缺點，可以通過使用蟻群演算法進行搜尋，然後用其他演算法對蟻群演算法得到的有效路由路徑，通過選擇、交叉、變異等優化過程，產生效能更優的下一代群體。

（5） pso演算法由於區域性尋優能力較差，因此可以在搜尋過程中融入確定性區域性搜尋演算法。