蟻群算法及其應(yīng)用研究

1、蟻群算法及其應(yīng)用研究趙天男,王曉紅(渤海大學(xué)信息科學(xué)工程學(xué)院,遼寧錦州121000摘要:蟻群算法是一種新型的模擬進(jìn)化算法,是受到真實蟻群的覓食機(jī)制的啟發(fā)而提出的。介紹了蟻群算法的基本原理和工作機(jī)制,并分別就蟻群算法的理論和應(yīng)用進(jìn)行了闡述,包括蟻群算法改進(jìn)的不同算法以及蟻群算法在各個領(lǐng)域中的應(yīng)用,并進(jìn)一步給出了研究重點和發(fā)展方向。關(guān)鍵詞:蟻群算法;優(yōu)化問題;應(yīng)用研究中圖分類號:TP312文獻(xiàn)標(biāo)識碼:A文章編號:1672-7800(201006-0034-021蟻群算法的基本原理真實的螞蟻有能力在沒有任何可見提示下找出從蟻穴到食物源的最短路徑,并能隨環(huán)境的變化而變化搜索出新的路徑,產(chǎn)生新的選擇,蟻

2、群算法也是通過模擬真實蟻群的這一特征進(jìn)行工作的。1.1螞蟻的覓食行為像螞蟻這類群居昆蟲,雖然沒有視覺,卻能找到從蟻穴到食物源的最短路徑。單只螞蟻的行為及其簡單,在蟻群覓食的過程中釋放信息素,通過對路徑上信息素強(qiáng)度的感知來選擇所要行進(jìn)的方向,并傳遞信息。當(dāng)遇到新的障礙物時,信息素軌跡會被障礙物暫時性阻斷,螞蟻會隨機(jī)地選擇下一步的方向,重新構(gòu)建起新的連續(xù)的信息素路徑。隨著時間的推移,選擇短路徑的螞蟻越來越多,留下的信息素濃度也會加強(qiáng),從而使后繼的螞蟻以較大的概率選擇短路徑。他們這種自催化過程形成的信息正反饋機(jī)制使得他們可以找到新的最短路徑。1.2蟻群算法的基本原理蟻群算法是受到真實蟻群集體行為的啟

3、發(fā)而得到的新型優(yōu)化算法,人工螞蟻和真實螞蟻存在異同。人工螞蟻和真螞蟻的螞蟻一樣,是一群相互合作的個體并且他們有著共同的任務(wù),他們都是通過使用信息素進(jìn)行間接通訊,而且人工螞蟻利用了真實螞蟻覓食行為中的自催化機(jī)制。但人工蟻群也存在真螞蟻所不具有的一些特性,蟻群這種記憶并非存儲于螞蟻個體,而是分布在路徑上。人工螞蟻實質(zhì)上是由一個離散狀態(tài)到另一個離散狀態(tài)的躍遷。信息素的釋放時間是根據(jù)不同情況而改變的。為了提高系統(tǒng)總體上的性能,蟻群被賦予了其他的功能,如局部優(yōu)化、原路返回等。蟻群算法最初是應(yīng)用在對稱的旅行商問題,下面對求解旅行商問題進(jìn)行簡單的說明。旅行商問題就是指給定n 個城市,并給出兩兩城市間的距離,

4、要求確定一條經(jīng)過各城市最短的路徑。螞蟻根據(jù)城市的距離和連接邊上信息素濃度為變量的概率函數(shù)選擇下一城市。為了滿足問題的約束條件,在完成一次循環(huán)前,不允許螞蟻選擇已經(jīng)訪問過的城市,需要由禁忌表控制。完成循環(huán)后,路徑上都會留下濃度不同的信息素,我們可以通過對信息素濃度的強(qiáng)度,選擇出最短路徑。算法的基本流程圖如圖1所示 。圖1基本流程圖初始時刻,各條路徑上的信息素量相等,設(shè)ij (0=C (C 為常數(shù)。螞蟻k (1,2,m 在運動過程中根據(jù)各條路徑上的信息素決定轉(zhuǎn)移方向。螞蟻系統(tǒng)所使用的狀態(tài)轉(zhuǎn)移規(guī)則被稱為隨機(jī)比例規(guī)則,它給出了位于城市i 的螞蟻k 選擇移動到城市j 的概率。在t 時刻,螞蟻k 在城市i

5、 選擇城市j 的轉(zhuǎn)移概率P ij k (t 為:軟件導(dǎo)刊Software Guide第9卷%第6期作者簡介:趙天男(1985-,女,遼寧本溪人,渤海大學(xué)信息科學(xué)工程學(xué)院碩士研究生,研究方向為計算機(jī)網(wǎng)絡(luò);王曉紅(1983-,男,山西呂梁人,渤海大學(xué)信息科學(xué)工程學(xué)院碩士研究生,研究方向為虛擬現(xiàn)實。第6期P ij k(t=ij(tij(tSallowed kis(tis(t,jallowed k0otherwise(1其中ij表示為邊(i,j上的信息素軌跡強(qiáng)度;ij表示為邊(i,j的能見度,反映由城市i轉(zhuǎn)移到城市j的啟發(fā)程度,這個量在螞蟻系統(tǒng)的運行過程中不改變。蟻群算法中只有那些屬于最短路徑上的邊的

6、信息素才被得到增強(qiáng)。這種規(guī)則和偽隨機(jī)比例規(guī)則的使用都是為了讓算法的尋優(yōu)過程更具有指導(dǎo)性,最短路徑的尋找始終是在當(dāng)前找到的最短路徑的附近進(jìn)行。在所有的螞蟻遍歷完n個城市之后,各路徑上信息素量根據(jù)式(2進(jìn)行更新。ij(t+1=·ij(t+ij(t,t+1ij(t,t+1=mk=1ij k(t,t+1(2ij(t,t+1表示第k只螞蟻在時刻(t,t+1留在(i,j上的信息素的量,它的值根據(jù)螞蟻表現(xiàn)的優(yōu)劣程度而定。路徑越短,信息素釋放的就越多。根據(jù)具體算法的不同,表達(dá)式也可以不同,要根據(jù)具體問題選擇不同的表達(dá)形式。蟻密和蟻量系統(tǒng)模型僅在于的不同。在蟻密系統(tǒng)模型中,一只螞蟻在經(jīng)過路徑(i, j

7、上釋放的信息素量為每單位長度Q,在蟻量模型中,螞蟻在經(jīng)過路徑上釋放的信息素量為每單位長度Q/dij。而在蟻周模型中,與上述兩種模型的ij k表達(dá)式不同,ij k(t,t+n表示更新螞蟻k所走的路徑,(t,t+n表示螞蟻經(jīng)過n步完成一次循環(huán),具體的更新值由式(3所示:ij k(t,t+n=Q/L k(3螞蟻k在本次循環(huán)中經(jīng)過路徑(i,j否則在蟻密和蟻量系統(tǒng)中,螞蟻建立方案的同時釋放信息素,是局部的更新。而在蟻周系統(tǒng)中,是在螞蟻已經(jīng)完全建立了軌跡后再釋放信息素,是利用了整體的信息。根據(jù)一系列標(biāo)準(zhǔn)測試問題上運行的實驗表明,蟻周算法的性能優(yōu)于其他兩種算法。因此,蟻周算法模型往往被稱為螞蟻系統(tǒng),另外兩種

8、模型不被使用。2改進(jìn)的蟻群優(yōu)化算法近年來,蟻群優(yōu)化算法研究主要集中在改善蟻群算法的性能方面。改進(jìn)的方法主要是在搜索控制的具體方面不同,但這些算法都是基于螞蟻找出最優(yōu)解來指導(dǎo)螞蟻搜索的過程。(1帶精英策略的螞蟻系統(tǒng)(Ant System with elitist strate-gy是最早的改進(jìn)螞蟻系統(tǒng)。在這個系統(tǒng)中,為了使到目前所找出的最優(yōu)解在下一循環(huán)中對螞蟻更有吸引力,在每次循環(huán)之后給予最優(yōu)解以額外的信息素量,這樣的解被稱為全局最優(yōu)解,找出這個解的螞蟻被稱為精英螞蟻。但是該系統(tǒng)存在缺點,若在進(jìn)化過程中,解的總質(zhì)量提高了,解元素之間的差異減小了,將導(dǎo)致選擇概率的差異也隨之減小,使得搜索過程不會集

9、中到所找出的最優(yōu)解附近,阻止了對更優(yōu)解的進(jìn)一步搜索。(2基于優(yōu)化排序的螞蟻系統(tǒng)(Rank-Based Bersion of Ant System:將遺傳算法中排序的概念擴(kuò)展應(yīng)用到螞蟻系統(tǒng)中,當(dāng)每只螞蟻都生成一條路徑后,螞蟻按路徑長度排序,螞蟻對激素軌跡量更新的貢獻(xiàn)根據(jù)該螞蟻的排名進(jìn)行加權(quán)。只考慮w 只最好的螞蟻,而且要以有效避免上述的某些局部極優(yōu)路徑被很多螞蟻過分重視的情況發(fā)生。(3最大最小螞蟻系統(tǒng)(Max-Min Ant System與蟻群系統(tǒng)相似,為了充分利用循環(huán)最優(yōu)解和到目前為止找出的最優(yōu)解,在每次循環(huán)之后,只有一只螞蟻進(jìn)行信息素更新。這只螞蟻可能是找出當(dāng)前循環(huán)中最優(yōu)解的螞蟻,也可能是找

10、出從實驗開始以來最優(yōu)解的螞蟻。而在螞蟻系統(tǒng)中,對所有螞蟻走過的路徑都進(jìn)行信息素更新。為了避免搜索的停滯,把每個解的元素上的信息素軌跡量的值域范圍限制在Min,Max區(qū)間內(nèi)。在螞蟻系統(tǒng)中的信息素軌跡量不被限制,使得一些路徑上的軌跡量遠(yuǎn)高于其他邊,螞蟻都沿著同條路徑移動,組織了進(jìn)一步搜索更優(yōu)解的行為。(4最優(yōu)-最差螞蟻系統(tǒng)(Best-Worst Ant System。該算法在蟻群算法的基礎(chǔ)上進(jìn)一步增強(qiáng)了搜索過程的指導(dǎo)性,使得螞蟻的搜索更集中于當(dāng)前所找出的最好路徑的領(lǐng)域內(nèi)。蟻群算法的任務(wù)就是引導(dǎo)問題的解向著全局最優(yōu)的方向不斷進(jìn)化。該算法的思想就是對最優(yōu)解進(jìn)行更大限度的增強(qiáng),而對最差解進(jìn)行削弱,使得屬

11、于最優(yōu)路徑的邊與屬于最差路徑的邊之間的信息量差異進(jìn)一步增大,從而使螞蟻的搜索行為更集中于最優(yōu)解的附近。蟻群算法還可以與其他智能優(yōu)化算法相融合,取長補短,改進(jìn)和完善算法的性能。目前蟻群算法可以與遺傳算法、粒子群算法等進(jìn)行融合,更有效的解決一些問題。3蟻群算法在優(yōu)化問題中的應(yīng)用蟻群算法最初被用經(jīng)典的組合優(yōu)化問題,隨著研究的深入,應(yīng)用范圍不斷擴(kuò)大,現(xiàn)在應(yīng)用到靜態(tài)組合優(yōu)化問題、動態(tài)組合優(yōu)化問題、連續(xù)空間優(yōu)化問題、以及其他領(lǐng)域。下面分別介紹了在不同領(lǐng)域中的應(yīng)用:3.1在靜態(tài)組合優(yōu)化中的應(yīng)用蟻群算法最先應(yīng)用于旅行商問題(TSP問題,它是組合優(yōu)化中研究最多的NP問題之一,該問題主要是在n個城市中,必須訪問每

12、個城市且每個城市只能訪問一次,最后回到起始城市,尋找最短路徑。目前,求解TSP問題的方法有很多,窮舉搜索法、最近鄰算法、插入算法等,也有其他優(yōu)化算法,例如:模擬退火算法、遺傳算法、神經(jīng)網(wǎng)絡(luò)算法、禁忌算法等。許多研究表明,應(yīng)用群算優(yōu)化算法求解TSP問題要優(yōu)于其他的方法。二次分配問題(QAP指的是分配n個設(shè)備給n個地點使得分配代價最小。事實上,QAP問題是一般化的TSP問題。車間任務(wù)調(diào)度問題(JSP指的是一組M臺機(jī)器和一組T 個任務(wù),任務(wù)有一組制定的將在這些機(jī)器上執(zhí)行的操作序列組成。還有許多問題,像車輛路線問題(VRP、圖著色問題(GCP、有序排列問題(SOP、最短的公共父序列問題(SCS等。趙天

13、男,王曉紅:蟻群算法及其應(yīng)用研究35··3.2在動態(tài)組合優(yōu)化中的應(yīng)用在動態(tài)組合優(yōu)化問題中,問題的解是隨時間而變化的。蟻群算法在解決動態(tài)組合優(yōu)化問題中主要是通信網(wǎng)絡(luò)。在國際上Schoonderwerd 等人首先將蟻群算法應(yīng)用于路由問題,White 等人將蟻群算法運用在單對單點和單對多點的有向連接的網(wǎng)絡(luò)路由中,而Dicarogy 等人基于蟻群算法設(shè)計了自適應(yīng)的路由算法。在國內(nèi),開展了基于蟻群算法的QoS 路由調(diào)度方法的研究。4結(jié)束語蟻群算法問世至今已有十多年的時間,其理論和應(yīng)用都有了很大的進(jìn)步,蟻群算法從最初求解旅行商問題開始,已經(jīng)逐步發(fā)展為一個優(yōu)化工具,并且較為成功地應(yīng)用到科

14、學(xué)和工程中的多個領(lǐng)域。眾多研究已經(jīng)證明,蟻群算法具有很強(qiáng)的發(fā)現(xiàn)較好解的能力,因為該算法不僅利用了正反饋原理,而且是一種本質(zhì)并行的算法,不同個體之間不斷進(jìn)行信息交流和傳遞,從而能夠相互協(xié)作。蟻群算法相對于各種比較成熟的計算智能方法來說,它的數(shù)學(xué)離了基礎(chǔ)相對薄弱,缺乏具備普遍意義的理論性分析。算法中涉及的各種參數(shù)設(shè)置也沒有確切的理論依據(jù),通常都是通過經(jīng)驗來確定。因此,蟻群算法還有許多問題需要解決,它的應(yīng)用也有待進(jìn)一步的發(fā)掘。蟻群算法還有許多要研究的地方,主要是:進(jìn)一步的研究算法收斂性的分析,得出更強(qiáng)的收斂性證明并得出收斂速度將會加速算法的發(fā)展;蟻群算法的理論性分析和參數(shù)的設(shè)置;蟻群算法的應(yīng)用領(lǐng)域的

15、擴(kuò)展,應(yīng)用較多的是靜態(tài)組合優(yōu)化問題,改進(jìn)并將其應(yīng)用于動態(tài)組合優(yōu)化問題和連續(xù)優(yōu)化問題是值得探索的。參考文獻(xiàn):1DORIGO M ,GAMBARDELLA L M.Ant colony system :a coopera -tive learning approach to the traveling salesman problem J .IEEE Transactions on Evolutionary Computation ,1997(1.2DORIGO M ,MANIEZZO V ,COLORNI A.Ant system :optimization by a colon of coop

16、erating agents.IEEE Transactions on Systems ,Man and Cybernetics ,PartB ,1996(1.3COLORM A ,DORIGO M ,MANIEZZO V.Distributed optimization by ant colonies C .Proc of the First European conf.On Artificial Life ,Paris ,France Elsevier Publishing ,1991.4李士勇.蟻群優(yōu)化算法及其應(yīng)用研究進(jìn)展J .計算機(jī)測量與控制,2003(12.5溫文波,杜維.蟻群算法綜

17、述J .石油化工自動化,2002(1.6姜長園.蟻群算法的理論及應(yīng)用J .計算機(jī)時代,2004(6.7倪慶劍,邢漢承.蟻群算法及其應(yīng)用研究進(jìn)展J .計算機(jī)應(yīng)用與軟件,2008(8.(責(zé)任編輯:周曉輝C 語言中浮點數(shù)存儲異常的研究與實踐田耕,成平廣(重慶教育學(xué)院計算機(jī)科學(xué)系,重慶400067摘要:通過對浮點數(shù)存儲方式的分析,指出了浮點數(shù)在C 語言編程過程中出現(xiàn)的不足,并采用3種方法巧妙地進(jìn)行彌補和解決,對C 語言學(xué)習(xí)者有一定的指導(dǎo)作用和參考意義。關(guān)鍵詞:C 語言;浮點數(shù);存儲格式;改進(jìn)中圖分類號:TP312文獻(xiàn)標(biāo)識碼:A文章編號:1672-7800(201006-0036-031問題的提出在科學(xué)計算中,時常會出現(xiàn)實數(shù)的運算,而實數(shù)在計算機(jī)中以浮