一種多蟻群偽并行優(yōu)化算法

一種多蟻群偽并行優(yōu)化算法

在大自然中實際尋找螞蟻的行為的啟發(fā)下，杜里格米在20世紀90年代初設(shè)計了第一種螞蟻優(yōu)化算法（as）。該算法是一種基于多主體的模擬進化全局搜索算法,它采用分布式控制,具有自組織性和正反饋性,優(yōu)化過程不依賴于優(yōu)化問題本身的嚴格數(shù)學(xué)性質(zhì),并且具有潛在的并行性。人們對蟻群算法的研究已經(jīng)顯示出該算法在求解復(fù)雜優(yōu)化問題(特別是離散優(yōu)化問題)方面的優(yōu)越性。蟻群算法也存在一些不足,蟻群算法在構(gòu)造解的過程中,隨機選擇策略使得算法的進化速度變慢,正反饋原理旨在強化性能較好的解,卻容易出現(xiàn)停滯現(xiàn)象,從而以極大的概率引導(dǎo)蟻群走向局部最優(yōu)解。1基本控制指導(dǎo)模型自然界中的蟻群具有自組織行為,在沒有視覺的情況下,能夠找出從食物源到蟻巢的最短路徑。此外,蟻群還具有極強的環(huán)境適應(yīng)能力,當(dāng)原先最短的路徑上出現(xiàn)障礙物時,能夠再發(fā)現(xiàn)一條新的最短路徑。生物學(xué)家經(jīng)過仔細研究發(fā)現(xiàn)螞蟻之間通過一種稱之為“信息素(pheromone)”的物質(zhì)進行間接通信、相互協(xié)作來發(fā)現(xiàn)最短路徑。螞蟻在運動過程中,不但能夠在它所經(jīng)過的路徑上留下該物質(zhì),而且能夠感知它的存在及強度,并朝著該物質(zhì)強度高的方向移動,以此指導(dǎo)自己的運動方向。因為蟻群優(yōu)化算法首先被應(yīng)用于解決旅行商問題(travelingsalesmanproblem,TSP),所以基本蟻群優(yōu)化算法模型一般使用TSP問題來進行描述,下面針對n個城市的TSP問題給出了基本蟻群的優(yōu)化算法模型。螞蟻從起始點開始按隨機比例規(guī)則根據(jù)轉(zhuǎn)移概率Pkij來選擇將要移動到的城市。在t時刻,螞蟻k在城市i選擇城市j的轉(zhuǎn)移概率為其中,allowedk={0,1,…,n-1}表示螞蟻k下一步允許選擇的城市;τij為邊(i,j)上的信息素強度;ηij為邊(i,j)的能見度;α為信息啟發(fā)式因子,表示信息素對路徑選擇的重要性;β為期望啟發(fā)式因子,表示啟發(fā)信息對路徑選擇的重要性。經(jīng)過n個時刻,螞蟻完成一次循環(huán),各路徑上的信息素量根據(jù)下式進行調(diào)整:其中,ρ為信息素揮發(fā)因子;m為蟻群中螞蟻的數(shù)目;Q為信息素強度,為常數(shù);Lk為螞蟻k在一次循環(huán)中走過的路徑長度。2多昆蟲群協(xié)同進化的算法不論是DorigoM提出的基本蟻群算法,還是大部分學(xué)者所提出的改進蟻群算法,都是基于單種蟻群、單種信息素的算法,主要模擬了實際蟻群信息系統(tǒng)的一部分。多蟻群偽并行優(yōu)化算法的思想是將一個總的蟻群分成若干個子蟻群,不同的蟻群賦以不同的控制參數(shù),對各蟻群分別進行相互獨立的蟻群尋優(yōu),各蟻群在獨立尋優(yōu)過程中采用最大最小螞蟻系統(tǒng)(max-minantcolony,MMAS)算法,并引入信息素平滑機制,以提高算法的全局尋優(yōu)能力;各子蟻群在獨立運行一定代數(shù)后,通過遷移算子聯(lián)系,實現(xiàn)多蟻群的協(xié)同進化,最優(yōu)解的獲取是多個蟻群協(xié)同進化的綜合結(jié)果。由于各蟻群采用不同的控制參數(shù)相對獨立地執(zhí)行尋優(yōu)過程,具有不同的信息素分布模式,因此進化方向保持一定的差異,保證了搜索的充分性和收斂結(jié)果的全局最優(yōu)性。遷移算子將各蟻群在尋優(yōu)過程中出現(xiàn)的精英螞蟻的尋優(yōu)結(jié)果以信息素更新的形式,每隔一定的代數(shù)便引入到其他子蟻群,通過更新信息素矩陣,實現(xiàn)子蟻群之間的信息交換。此外,算法采取精英保留策略,保證每一進化代整個蟻群產(chǎn)生的最優(yōu)結(jié)果不被破壞和丟失。整個尋優(yōu)過程結(jié)束后,各子蟻群中的精英個體排序,得到待求解問題的最優(yōu)規(guī)劃方案及若干次優(yōu)方案。因為此算法是在單機環(huán)境下模擬各子蟻群并行、協(xié)同尋優(yōu),所以把它稱為“偽并行”。2.1局部最優(yōu)解的變異蟻群算法是根據(jù)當(dāng)前較好的路徑更新路徑信息素量,經(jīng)過多次迭代后已有的最好路徑上的信息素就會非常強,而較差的路徑上的信息素就會很弱,這樣螞蟻就會集中在當(dāng)前最好的路徑上。隨著計算步驟的增加,螞蟻跳出現(xiàn)有最好路徑的可能性會變小,這樣算法就很容易早熟收斂到了局部最優(yōu)解。針對此問題,文獻給出了對最優(yōu)個體進行變異的方法使算法跳出局部最優(yōu);文獻設(shè)計了基于信息素的變異算子使算法跳出局部最優(yōu);文獻提出了動態(tài)的調(diào)整信息素量的分配使算法跳出局部最優(yōu)。本文通過引入信息素平滑機制,以達到使算法跳出局部最優(yōu)的目的。當(dāng)算法在尋優(yōu)過程中某個子蟻群連續(xù)一定代數(shù)最優(yōu)解沒有變化時,則該子蟻群開始進行信息素平滑,信息素的平滑按下式進行:其中,τij為路徑(i,j)上當(dāng)前的信息素值;τmin為MMAS中各路徑上的最小允許信息素值;δ為系數(shù),用以控制信息素平滑作用的大小。當(dāng)δ為0時,相當(dāng)于關(guān)閉此操作;當(dāng)δ為1時,各路徑上信息素值置為最小。2.2多昆蟲群偽并行優(yōu)化算法人類文明的進步是一個優(yōu)勝劣汰的過程,先進的文明征服和替代落后的文明。人類社會的優(yōu)勝劣汰通過兩種方式進行,一種是文化的交流和融合,另一種方式是戰(zhàn)爭和入侵。一般,在文明產(chǎn)生的早期,其發(fā)展比較快,等到一定時期后就會停滯不前,也就是內(nèi)部優(yōu)化已經(jīng)無法前進,此時要么大量學(xué)習(xí)優(yōu)秀文化得以生存,要么通過戰(zhàn)爭被新的文明替代。本文就是仿照這種社會進化過程設(shè)計了遷移算子。當(dāng)多蟻群偽并行優(yōu)化算法中的各子蟻群獨立進化了一定代數(shù)后,各子蟻群中的精英螞蟻的尋優(yōu)結(jié)果以信息素更新的形式被遷移到其他子蟻群,精英螞蟻所走過的路徑在其他子蟻群中得到獎勵,釋放獎勵信息素,其信息素的更新公式如下所示:其中,為子蟻群m中路徑(i,j)上的信息素量(m≠n);Q0為獎勵的信息素的總量;Ln為第n個子蟻群的精英螞蟻所找到的最優(yōu)路徑的長度。多蟻群偽并行優(yōu)化算法的具體算法步驟如下:步驟1指定各子蟻群的控制參數(shù),指定開始進行精英螞蟻遷移操作的子蟻群進化代數(shù)T,設(shè)置初始信息素,初始化各算法運行變量。步驟2各子蟻群按照MMAS算法開始獨立尋優(yōu),在尋優(yōu)過程中若子蟻群的最優(yōu)解連續(xù)一定代數(shù)(算法參數(shù)中設(shè)置)沒有進化,則進行信息素平滑,更新子蟻群信息素矩陣。步驟3若各子蟻群的最優(yōu)解滿足要求或算法運行代數(shù)大于參數(shù)設(shè)定值,則排列各子蟻群最優(yōu)解并退出算法;否則執(zhí)行步驟4。步驟4各子蟻群的精英螞蟻在子蟻群間進行遷移操作,按照式(6)進行精英螞蟻所走路徑的信息素獎勵,轉(zhuǎn)向步驟2。3與其他昆蟲群算法的研究比例本節(jié)在VC++6.0環(huán)境下用TSPLIB中的TSP算例來測試本文設(shè)計的算法,并與其他蟻群算法進行類比。沿用TSPLIB中的記法,算例中的數(shù)字表示城市的數(shù)目(如算例ch150的城市數(shù)目是150)。下面分別對算法參數(shù)的選取、算法的收斂性仿真和類比仿真進行說明。3.1仿真實驗主要參數(shù)設(shè)計算法參數(shù)的選取了參考文獻提出的“三步走”方法,具體步驟如下:(1)確定螞蟻數(shù)目,按照(城市規(guī)模/螞蟻數(shù)目)≈1.5的選擇策略來確定螞蟻的總數(shù)目;(2)參數(shù)粗調(diào),調(diào)整取值范圍較大的信息啟發(fā)式因子α,期望啟發(fā)式因子β,信息素強度Q等,以得到較理想的解。(3)參數(shù)微調(diào),調(diào)整取值范圍較小的信息素揮發(fā)因子ρ。通過“三步走”的方法最終確定的算法運行參數(shù)為:α=1.0,β=3.0,ρ=0.1。Q針對不同的問題取值不一樣,對于后面仿真過程中用到的eil51和st70問題Q取125.0,ch150和a280問題Q取1000.0。對于本文設(shè)計的算法,各子蟻群在上面參數(shù)的基礎(chǔ)上進行變動。仿真中還用到了MMAS算法,通過實驗確定該算法的最大和最小約束信息素量為τmax=100.,τmin=0.01,其他參數(shù)同上。3.2實際最優(yōu)解及其求解使用本文設(shè)計的多蟻群偽并行優(yōu)化算法對TSPLIB中的eil51問題和st70問題進行仿真,檢驗算法的收斂性。算法設(shè)置5個子蟻群,每個子蟻群獨立運行200代后進行精英螞蟻遷移操作,如此反復(fù)6次(共計1200代),使用最優(yōu)解繪制收斂圖如圖1、圖2所示。eil51問題的實際最優(yōu)解是426,st70問題的實際最優(yōu)解是675。通過收斂過程圖可以看到,算法在運行初期能夠快速的收斂,在130代后趨于平穩(wěn),由于算法中的信息素平滑機制和子蟻群間精英螞蟻的遷移操作,因此該算法仍然能夠在解空間向接近最優(yōu)解的方向繼續(xù)搜索。最終,對eil51問題的仿真在第558代搜索到了最好解428.014236,對st70問題的仿真在第1069代搜索到了最好解676.507413。3.3算法仿真結(jié)果使用AS,MMAS和本文設(shè)計的多蟻群偽并行優(yōu)化算法對TSPLIB中的eil51,ch150,a2803個問題進行類比仿真,其中AS算法使用蟻周模型。在使用AS算法和MMAS算法仿真時,每次運行1200代,共運行10次;在使用多蟻群偽并行優(yōu)化算法仿真時,使用3個子蟻群,每個子蟻群獨立尋優(yōu)200代后進行精英遷移操作,如此反復(fù)6次(共計1200代),同樣運行該算法10次。eil51問題的類比仿真結(jié)果(理論最優(yōu)值為426),ch150問題的類比仿真結(jié)果(理論最優(yōu)值為6528),a280問題的類比仿真結(jié)果(理論最優(yōu)值為2579)見表1～表3。通過表1～表3的類比仿真結(jié)果可以看到