姓名：彭帥 學(xué)號：17021210850

【嵌牛導(dǎo)讀】：蟻群算法(ACO)是受自然界中螞蟻搜索食物行為的啟發(fā)，是一種群智能優(yōu)化算法。粒子群優(yōu)化具有相當快的逼近最優(yōu)解的速度，可以有效的對系統(tǒng)的參數(shù)進行優(yōu)化。

【嵌牛鼻子】：優(yōu)化算法

【嵌牛提問】：蟻群算法與粒子群算法優(yōu)缺點？

【嵌牛正文】：

蟻群算法(ACO)是受自然界中螞蟻搜索食物行為的啟發(fā)，是一種群智能優(yōu)化算法。它基于對自然界真實蟻群的集體覓食行為的研究，模擬真實的蟻群協(xié)作過程。算法由若干個螞蟻共同構(gòu)造解路徑，通過在解路徑上遺留并交換信息素提高解的質(zhì)量，進而達到優(yōu)化的目的。蟻群算法作為通用隨機優(yōu)化方法，已經(jīng)成功的應(yīng)用于TSP等一系列組合優(yōu)化問題中，并取得了較好的結(jié)果。但由于該算法是典型的概率算法，算法中的參數(shù)設(shè)定通常由實驗方法確定，導(dǎo)致方法的優(yōu)化性能與人的經(jīng)驗密切相關(guān)，很難使算法性能最優(yōu)化。

蟻群算法中每只螞蟻要選擇下一步所要走的地方，在選路過程中，螞蟻依據(jù)概率函數(shù)選擇將要去的地方，這個概率取決于地點間距離和信息素的強度。

(ｔ+ｎ) = (t)+Δ(ｔ+ｎ)

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

在上述概率方程中，參數(shù)α和β:是通過實驗確定的。它們對算法性能同樣有很大的影響。α值的大小表明留在每個節(jié)點上信息量受重視的程度，其值越大，螞蟻選擇被選過的地點的可能性越大。β值的大小表明啟發(fā)式信息受重視的程度。

這兩個參數(shù)對蟻群算法性能的影響和作用是相互配合，密切相關(guān)的。但是這兩個參數(shù)只能依靠經(jīng)驗或重復(fù)調(diào)試來選擇。

在采用蟻群－粒子群混合算法時，我們可以利用PSO對蟻群系統(tǒng)參數(shù)α和β的進行訓(xùn)練。具體訓(xùn)練過程：假設(shè)有n個粒子組成一個群落，其中第i個粒子表示為一個二維的向量xi = ( xi1 , xi2 ) , i

= 1, 2,?,n，即第i個粒子在搜索空間的中的位置是xi。換言之，每個粒子的位置就是一個潛在的解。將xi帶入反饋到蟻群系統(tǒng)并按目標函數(shù)就可以計算出其適應(yīng)值，根據(jù)適應(yīng)值的大小衡量解的優(yōu)劣。

蟻群算法的優(yōu)點：

蟻群算法與其他啟發(fā)式算法相比，在求解性能上，具有很強的魯棒性（對基本蟻群算法模型稍加修改，便可以應(yīng)用于其他問題）和搜索較好解的能力。

蟻群算法是一種基于種群的進化算法，具有本質(zhì)并行性，易于并行實現(xiàn)。

蟻群算法很容易與多種啟發(fā)式算法結(jié)合，以改善算法性能。

蟻群算法存在的問題：

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

（1），如果參數(shù)α和β設(shè)置不當，導(dǎo)致求解速度很慢且所得解的質(zhì)量特別差。

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

（3），基本蟻群算法中理論上要求所有的螞蟻選擇同一路線，該線路即為所求的最優(yōu)線路；但在實際計算中，在給定一定循環(huán)數(shù)的條件下很難達到這種情況。

另一方面，在其它的實際應(yīng)用中，如圖像處理中尋求最優(yōu)模板問題，我們并不要求所有的螞蟻都找到最優(yōu)模板，而只需要一只找到最優(yōu)模板即可。如果要求所有的螞蟻都找到最優(yōu)模板，反而影響了計算效率。

蟻群算法收斂速度慢、易陷入局部最優(yōu)。蟻群算法中初始信息素匱乏。蟻群算法一般需要較長的搜索時間，其復(fù)雜度可以反映這一點；而且該方法容易出現(xiàn)停滯現(xiàn)象，即搜索進行到一定程度后，所有個體發(fā)現(xiàn)的解完全一致，不能對解空間進一步進行搜索，不利于發(fā)現(xiàn)更好的解。

粒子群優(yōu)化具有相當快的逼近最優(yōu)解的速度，可以有效的對系統(tǒng)的參數(shù)進行優(yōu)化。粒子群算法的本質(zhì)是利用當前位置、全局極值和個體極值3個信息，指導(dǎo)粒子下一步迭代位置。其個體充分利用自身經(jīng)驗和群體經(jīng)驗調(diào)整自身的狀態(tài)是粒子群算法具有優(yōu)異特性的關(guān)鍵。PSO算法的優(yōu)勢在于求解一些連續(xù)函數(shù)的優(yōu)化問題。

PSO算法存在的問題：

問題最主要的是它容易產(chǎn)生早熟收斂（尤其是在處理復(fù)雜的多峰搜索問題中）、局部尋優(yōu)能力較差等。PSO算法陷入局部最小，主要歸咎于種群在搜索空間中多樣性的丟失。

不同算法的混合模型主要分為兩類：（1）全局優(yōu)化算法與局部優(yōu)化算法混合；（2）全局優(yōu)化算法與全局優(yōu)化算法混合?？v觀各種與PSO算法相關(guān)的混合算法，大多數(shù)基本上采用一種策略對其改進，要么與其他算法，要么加入變異操作，同時采用兩種策略的混合算法較少。

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

因此如果將局部搜索和變異操作同時混合到PSO算法中，通過適當?shù)恼{(diào)節(jié)，發(fā)揮各自的優(yōu)點，提高算法的開發(fā)能力，增加變異操作防止算法早熟，來共同提高PSO算法的全局尋優(yōu)能力。

融合策略：

（1）針對蟻群算法初始信息素匱乏的缺點，采用其他算法生成初始信息素分布，利用蟻群算法求精確解，從而提高時間效率和求解精度。（使用的其他算法的求解結(jié)果以什么規(guī)則轉(zhuǎn)換成蟻群算法的信息素初值，需要通過多次實驗）

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

（3）蟻群算法中α，β的選取往往是通過經(jīng)驗來取得的，而選取不當時會造成算法的性能大大降低，因此可以利用其他算法對蟻群系統(tǒng)參數(shù)α，β進行訓(xùn)練。

（4）對于蟻群算法出現(xiàn)過早收斂于非全局最優(yōu)解以及時間過長的缺點，可以通過使用蟻群算法進行搜索，然后用其他算法對蟻群算法得到的有效路由路徑，通過選擇、交叉、變異等優(yōu)化過程，產(chǎn)生性能更優(yōu)的下一代群體。

（5）PSO算法由于局部尋優(yōu)能力較差，因此可以在搜索過程中融入確定性局部搜索算法。