蟻群算法及其應用研究

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

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

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

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

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

6、信息素才被得到增強。這種規(guī)則和偽隨機比例規(guī)則的使用都是為了讓算法的尋優(yōu)過程更具有指導性,最短路徑的尋找始終是在當前找到的最短路徑的附近進行。在所有的螞蟻遍歷完n個城市之后,各路徑上信息素量根據(jù)式(2進行更新。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ù)具體算法的不同,表達式也可以不同,要根據(jù)具體問題選擇不同的表達形式。蟻密和蟻量系統(tǒng)模型僅在于的不同。在蟻密系統(tǒng)模型中,一只螞蟻在經(jīng)過路徑(i, j

7、上釋放的信息素量為每單位長度Q,在蟻量模型中,螞蟻在經(jīng)過路徑上釋放的信息素量為每單位長度Q/dij。而在蟻周模型中,與上述兩種模型的ij k表達式不同,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ù)一系列標準測試問題上運行的實驗表明,蟻周算法的性能優(yōu)于其他兩種算法。因此,蟻周算法模型往往被稱為螞蟻系統(tǒng),另外兩種

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

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

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

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

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

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

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

15、擴展,應用較多的是靜態(tài)組合優(yōu)化問題,改進并將其應用于動態(tài)組合優(yōu)化問題和連續(xù)優(yōu)化問題是值得探索的。參考文獻: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)化算法及其應用研究進展J .計算機測量與控制,2003(12.5溫文波,杜維.蟻群算法綜

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