姓名:彭帥 學(xué)號:17021210850
【嵌牛導(dǎo)讀】:蟻群算法(ACO)是受自然界中螞蟻搜索食物行為的啟發(fā)吮炕,是一種群智能優(yōu)化算法参淹。粒子群優(yōu)化具有相當(dāng)快的逼近最優(yōu)解的速度,可以有效的對系統(tǒng)的參數(shù)進(jìn)行優(yōu)化乏悄。
【嵌牛鼻子】:優(yōu)化算法
【嵌牛提問】:蟻群算法與粒子群算法優(yōu)缺點浙值?
【嵌牛正文】:
蟻群算法(ACO)是受自然界中螞蟻搜索食物行為的啟發(fā),是一種群智能優(yōu)化算法檩小。它基于對自然界真實蟻群的集體覓食行為的研究开呐,模擬真實的蟻群協(xié)作過程。算法由若干個螞蟻共同構(gòu)造解路徑规求,通過在解路徑上遺留并交換信息素提高解的質(zhì)量筐付,進(jìn)而達(dá)到優(yōu)化的目的。蟻群算法作為通用隨機(jī)優(yōu)化方法阻肿,已經(jīng)成功的應(yīng)用于TSP等一系列組合優(yōu)化問題中瓦戚,并取得了較好的結(jié)果。但由于該算法是典型的概率算法冕茅,算法中的參數(shù)設(shè)定通常由實驗方法確定,導(dǎo)致方法的優(yōu)化性能與人的經(jīng)驗密切相關(guān)蛹找,很難使算法性能最優(yōu)化姨伤。
蟻群算法中每只螞蟻要選擇下一步所要走的地方,在選路過程中庸疾,螞蟻依據(jù)概率函數(shù)選擇將要去的地方乍楚,這個概率取決于地點間距離和信息素的強(qiáng)度。
(t+n) = (t)+Δ(t+n)
上述方程表示信息素的保留率届慈,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ù)α和β的進(jìn)行訓(xùn)練谓形。具體訓(xùn)練過程:假設(shè)有n個粒子組成一個群落,其中第i個粒子表示為一個二維的向量xi = ( xi1 , xi2 ) , i
= 1, 2,?,n状共,即第i個粒子在搜索空間的中的位置是xi套耕。換言之,每個粒子的位置就是一個潛在的解峡继。將xi帶入反饋到蟻群系統(tǒng)并按目標(biāo)函數(shù)就可以計算出其適應(yīng)值冯袍,根據(jù)適應(yīng)值的大小衡量解的優(yōu)劣。
蟻群算法的優(yōu)點:
蟻群算法與其他啟發(fā)式算法相比碾牌,在求解性能上康愤,具有很強(qiáng)的魯棒性(對基本蟻群算法模型稍加修改,便可以應(yīng)用于其他問題)和搜索較好解的能力舶吗。
蟻群算法是一種基于種群的進(jìn)化算法征冷,具有本質(zhì)并行性,易于并行實現(xiàn)誓琼。
蟻群算法很容易與多種啟發(fā)式算法結(jié)合检激,以改善算法性能。
蟻群算法存在的問題:
TSP問題是一類經(jīng)典的組合優(yōu)化問題腹侣,即在給定城市個數(shù)和各城市之間距離的條件下叔收,找到一條遍歷所有城市且每個城市只能訪問一次的總路程最短的路線。蟻群算法在TSP問題應(yīng)用中取得了良好的效果傲隶,但是也存在一些不足:
(1)饺律,如果參數(shù)α和β設(shè)置不當(dāng),導(dǎo)致求解速度很慢且所得解的質(zhì)量特別差跺株。
(2)复濒,基本蟻群算法計算量大,求解所需時間較長乒省。
(3)巧颈,基本蟻群算法中理論上要求所有的螞蟻選擇同一路線,該線路即為所求的最優(yōu)線路袖扛;但在實際計算中洛二,在給定一定循環(huán)數(shù)的條件下很難達(dá)到這種情況。
另一方面攻锰,在其它的實際應(yīng)用中晾嘶,如圖像處理中尋求最優(yōu)模板問題,我們并不要求所有的螞蟻都找到最優(yōu)模板娶吞,而只需要一只找到最優(yōu)模板即可垒迂。如果要求所有的螞蟻都找到最優(yōu)模板,反而影響了計算效率妒蛇。
蟻群算法收斂速度慢机断、易陷入局部最優(yōu)楷拳。蟻群算法中初始信息素匱乏。蟻群算法一般需要較長的搜索時間吏奸,其復(fù)雜度可以反映這一點欢揖;而且該方法容易出現(xiàn)停滯現(xiàn)象,即搜索進(jìn)行到一定程度后奋蔚,所有個體發(fā)現(xiàn)的解完全一致她混,不能對解空間進(jìn)一步進(jìn)行搜索,不利于發(fā)現(xiàn)更好的解泊碑。
粒子群優(yōu)化具有相當(dāng)快的逼近最優(yōu)解的速度坤按,可以有效的對系統(tǒng)的參數(shù)進(jìn)行優(yōu)化。粒子群算法的本質(zhì)是利用當(dāng)前位置馒过、全局極值和個體極值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)化算法混合兼耀⊙怪纾縱觀各種與PSO算法相關(guān)的混合算法求冷,大多數(shù)基本上采用一種策略對其改進(jìn),要么與其他算法窍霞,要么加入變異操作匠题,同時采用兩種策略的混合算法較少。
上述策略中但金,兩者之間有一定的矛盾性韭山,全局算法與局部算法相混合,盡管可以提高局部收斂速度冷溃,但也加劇了陷入局部極小的可能钱磅;全局算法與全局算法的混合,算法的局部細(xì)化能力仍然沒有改善似枕。但如果只加入變異操作盖淡,則算法的探測能力得到提高,但也損害了其局部開發(fā)能力凿歼。
因此如果將局部搜索和變異操作同時混合到PSO算法中褪迟,通過適當(dāng)?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)驗來取得的王污,而選取不當(dāng)時會造成算法的性能大大降低罢吃,因此可以利用其他算法對蟻群系統(tǒng)參數(shù)α,β進(jìn)行訓(xùn)練昭齐。
(4)對于蟻群算法出現(xiàn)過早收斂于非全局最優(yōu)解以及時間過長的缺點尿招,可以通過使用蟻群算法進(jìn)行搜索,然后用其他算法對蟻群算法得到的有效路由路徑阱驾,通過選擇就谜、交叉、變異等優(yōu)化過程里覆,產(chǎn)生性能更優(yōu)的下一代群體丧荐。
(5)PSO算法由于局部尋優(yōu)能力較差,因此可以在搜索過程中融入確定性局部搜索算法喧枷。