碩士畢業(yè)論文答辯課件

1、蟻群算法研究及其應(yīng)用主要內(nèi)容1:論文研究背景2:本文改進算法3:蟻群算法參數(shù)組合優(yōu)化4:TSP仿真系統(tǒng)介紹5:本文結(jié)論6:致謝研究背景蟻群算法原理 螞蟻算法是一種用來尋找最優(yōu)解決方案的機率型技術(shù),其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)最短路徑的行為.自然螞蟻尋找食物行為：螞蟻在路徑上前進時會根據(jù)前邊走過的螞蟻所留下的分泌物(信息素)選擇其要走的路徑。其選擇一條路徑的概率與該路徑上分泌物的強度成正比。因此，由大量螞蟻組成的群體的集體行為實際上構(gòu)成一種學習信息的正反饋現(xiàn)象：某一條路徑走過的螞蟻越多，后面的螞蟻選擇該路徑的可能性就越大。螞蟻的個體間通過這種信息的交流尋求通向食物的最短路徑。這種優(yōu)化過程

2、的本質(zhì):協(xié)調(diào)機制：螞蟻間實際上是通過分泌物來互相通信、協(xié)同工作的。選擇機制：信息素越多的路徑，被選擇的概率越大。更新機制：路徑上面的信息素會隨螞蟻的經(jīng)過而增長，而且同時也隨時間的推移逐漸揮發(fā)消失。研究背景蟻群算法數(shù)學模型(1)初始時刻( )，各條路徑上的信息素相等.選擇機制：在 t( ) 時刻，螞蟻在運動過程中根據(jù)各條路徑上信息素和路徑長度因素共同決定移動方向，螞蟻由位置i移動到位置j 的轉(zhuǎn)移概率的計算公式如下: 本文以著名的旅行商問題(TSP)為例，建立蟻群算法數(shù)學模型，該問題可以描述為：一個旅行商從n個城市的某一出發(fā)個訪問其他所有城市一次且僅一次后再回到出發(fā)城市，要求找出一條最短的路徑；該

3、問題可抽象像為求完全圖( n個節(jié)點)的最短路徑問題。更新機制：在 t+n時刻，此時所有的螞蟻完成了一次遍歷，為了避免殘留信息素過多而淹沒距離因素，在每只螞蟻走完一步或者迭代一次后，要對路徑上的信息素進行更新操作，各路徑上信息素可根據(jù)以下公式做調(diào)整：根據(jù)計算方式不同，有蟻周模型、蟻量模型和蟻密模型三種基本模型，本文的研究都是基于蟻周模型的，其模型為：研究背景蟻群算法數(shù)學模型(2)研究背景蟻群算法研究方向算法理論改進 參數(shù)分析應(yīng)用推廣數(shù)學證明1:算法易出現(xiàn)局部最優(yōu)、停滯等不良現(xiàn)象2:在求解較大規(guī)模問題時，算法的運行時間過長3:算法的收斂速度慢4:算法參數(shù)的設(shè)置帶有很強的經(jīng)驗性和隨機性，沒有嚴格的理

4、論認證 研究表明蟻群算法具有較強的魯棒性、分布式計算、易于與其優(yōu)化算法結(jié)合等優(yōu)點；但隨著問題規(guī)模的擴大，算法的運行時間和最優(yōu)解都不能認人滿意，性能明顯下降。大量研究表明蟻群算法也存在一些不足，主要有：蟻群算法研究方向:算法改進研究背景 針對蟻群算法存在的不足，國內(nèi)外學者開展了大量有意義的研究。研究成果主要涉及路徑搜索策略、信息素更新策略和最優(yōu)解保留策略等方面；研究行為主要是進行算法改進或驗證。有些改進算法的性能相比基本蟻群算法而言有了較大水平的提高，如最大最小蟻群算法是目前求解TSP問題的最好方法之一；有些已成為主流的蟻群算法,如：蟻群系統(tǒng)，基于排序的蟻群系統(tǒng)，最優(yōu)最差蟻群系統(tǒng)等。 針對基本蟻

5、群算法的不足，本文在借鑒其他算法優(yōu)點的基礎(chǔ)上提出一種改進的蟻群算法。該算法從以下幾個方面對基本蟻群算法進行了改進： 1:初始信息素的改進2:路徑選擇策略的改進3:信息素更新策略的改進本文算法改進研究過程(1) 基本蟻群算法中，路徑上的初始信息素大小是相同的，蟻群創(chuàng)建的第一條路徑所獲得的信息主要是城市之間的距離信息，此時，蟻群算法相當于貪婪算法。第一次循環(huán)中蟻群在所經(jīng)過的路徑上留下的信息素不一定能反映出最優(yōu)路徑的方向。正反饋的作用會使得這條不是最優(yōu)解的路徑上的信息素得到不應(yīng)有的增強，阻礙以后的螞蟻發(fā)現(xiàn)更好的全局最優(yōu)解。為此，本文改進算法在任意兩個城市之間安排的信息素是等量的,但是這等量的信息素要

6、平均到兩個之間的路徑上,由于城市之間的距離是不相同的,所以平均到每一小段上的信息素量就是距離的倒數(shù)與分配到這兩城市之間的信息素量之積。為提高初始階段螞蟻的搜索能力，改進算法將各路徑上的初始信息素的值按照最大最小蟻群算法思想限定其大小。所以其數(shù)學模型為：1：初始信息素本文算法改進研究過程(2)2:路徑選擇策略的改進相關(guān)文獻表明，自然螞蟻無視覺能力，無法感知距離的遠近,在節(jié)點選擇時，僅能依靠信息素濃度。為更好的模擬自然螞蟻,本文改進算法在選擇下一個城市時不再考慮距離因素,僅考慮信息素濃度。同時為有效的提高優(yōu)化速度,降低局部最優(yōu)解停滯的可能性,本文采用偽隨機性選擇策略,并在搜索過程中動態(tài)地調(diào)整確定性

7、選擇的概率。即螞蟻 在 t時刻有城市 i 到城市 j 的轉(zhuǎn)移概率由下式確定：3:信息素更新策略策略的改進本文算法改進研究過程(3)兩層信息素更新策略：第1層:原有信息素的揮發(fā)第2層:借鑒獎懲蟻群算法思想，在完成每次循環(huán)進行信息素揮發(fā)后，根據(jù)螞蟻所建立路徑的長短，進行排序，只有前w只建立短路徑的螞蟻被挑選出來進行獎勵，其他 (m-w )只建立路徑的螞蟻進行懲罰。最大最小蟻群算法思想：若某段路徑弧段的信息素相對其他路徑弧段的信息素而言在數(shù)量上占據(jù)絕對的優(yōu)勢時,會引起算法過早地收斂。對這一不足,本文借鑒MMAS思想,對各路徑上的信息素量施加最小最大限制。采用兩層信息素更新策略和最大最小蟻群算法思想開

8、始初始化螞蟻構(gòu)建路徑所有螞蟻結(jié)束？路徑排序信息素更新滿足結(jié)束條件？結(jié)束NYNY本文算法改進算法流程本文算法改進性能驗證算法平均最優(yōu)解平均迭代次數(shù)平均運行時間(s)基本蟻群算法449.353512429最大最小蟻群算法437.96289829本文改進算法443.992710423文獻48算法439.9628未知31文獻49算法447.7771未知33TSP51問題各算法性能比較表算法平均最優(yōu)解平均迭代次數(shù)平均運行時間基本蟻群算法564.649823839最大最小蟻群系統(tǒng)559.223819834本文改進算法561.341018926 TSP76問題的實驗結(jié)果參數(shù)組合優(yōu)化研究背景 蟻群算法的參數(shù)數(shù)

9、目眾多，參數(shù)對算法性能的影響較大。文獻表明:蟻群算法參數(shù)的合理組合能夠在一定程度上提高算法的全局搜索能力和加快算法的收斂速度，但遺憾的是，目前各參數(shù)該如何取值只是根據(jù)經(jīng)驗來選取合適的參數(shù)值。 針對蟻群算法參數(shù)空間大、參數(shù)選擇難的問題，本文對蟻群算法參數(shù)的組合優(yōu)化問題進行了討論。采用實例仿真法確定各個參數(shù)的合理取值區(qū)間，采用粒子群算法首次對蟻群算法的五個重要參數(shù)的組合優(yōu)化問題進行了探討，提出了基于粒子群的蟻群算法參數(shù)最優(yōu)組合優(yōu)化方案。參數(shù)組合優(yōu)化研究過程提出問題:本文將蟻群算法抽象為一個函數(shù)，其五個參數(shù)為函數(shù)的自變量，則有函數(shù) ，那么參數(shù)的連續(xù)區(qū)域優(yōu)化問題可以定義為：確定蟻群算法五個主要參數(shù) 的

10、值，使得函數(shù) 取得最優(yōu)值。由這個定義我們自然地可以將參數(shù)的優(yōu)化看成一個組合優(yōu)化問題，而且是一個連續(xù)域的組合優(yōu)化問題。選定方法:粒子群算法，因粒子群優(yōu)化算法具有很強的全局優(yōu)化能力，能較快地收斂于可接受解；而且粒子群優(yōu)化算法參數(shù)少，算法簡單易實現(xiàn)，效率較高。解決問題: 實例仿真法：綜合考慮算法的全局搜索能力和收斂速度兩項性能指標，確定各參數(shù)的合理區(qū)間. 采用“三步走”策略確定蟻群算法參數(shù)的較優(yōu)組合： (1)利用實例仿真法確定的各個參數(shù)的合理區(qū)間 (2)利用粒子群優(yōu)化算法，確定參數(shù)的最佳組合 (3)多次結(jié)果，求平均結(jié)束初始化生成粒子群循環(huán)迭代求全局最佳位置以及最優(yōu)適應(yīng)度函數(shù)值求每個粒子個體最佳位置移

11、動粒子更新粒子速度向量滿足循環(huán)條件？開始NYYN參數(shù)組合優(yōu)化關(guān)鍵技術(shù)參數(shù)組合優(yōu)化有效性驗證參數(shù)類型組次參數(shù)取值最優(yōu)路徑長度參數(shù)最佳組合11.604.89340.7547544.721.495.10330.7857554.031.055.08300.8057576.141.014.75340.7467614.87參數(shù)隨機組合51.351.25200.5018027.062.504.90340.187794.673.505.79400.898059.281.005.00280.5047670.495.305.04460.8028205.24應(yīng)用推廣研究背景 蟻群算法提出十幾年來，取得了豐碩的應(yīng)用性

12、成果，主要有：物流配送問題、VRP問題、函數(shù)優(yōu)化問題、車間作業(yè)調(diào)度問題、網(wǎng)絡(luò)路由問題、電力系統(tǒng)機器人領(lǐng)域、控制參數(shù)組合優(yōu)化問題、聚類分析、數(shù)據(jù)挖掘、數(shù)字圖象處理、生命科學化學工業(yè)等等。大量有價值的研究成果將陸續(xù)發(fā)表，不斷地拓寬了其應(yīng)用領(lǐng)域。 本文主要從算法實現(xiàn)方面進行應(yīng)用推廣。 本文采用軟件工程思想，利用軟件開發(fā)技術(shù)，設(shè)計并實現(xiàn)了蟻群算法參數(shù)訓(xùn)練系統(tǒng)及蟻群算法TSP問題仿真系統(tǒng)；通過參數(shù)訓(xùn)練仿真系統(tǒng)，用戶可以訓(xùn)練得到蟻群算法參數(shù)的理想組合；通過蟻群算法仿真系統(tǒng)，用戶可以記錄并查看算法求解TSP問題過程的中間數(shù)據(jù)，最優(yōu)解及最優(yōu)路徑，查看收斂圖，路徑收斂趨勢圖及算法間性能比較圖。 應(yīng)用推廣研究方案

13、采用方法：軟件工程方法，UML方法模塊劃分：關(guān)鍵技術(shù)UML關(guān)鍵類圖CAnt成員屬性int *ptabuint m_dLengthint m_iCityCountint *pAllowedCity成員屬性double *m_distancedouble *m_dTrialdouble *m_dDeltTrailCMapInfo成員方法CMapInfo(int m_iCityCount)CMapInfo()CAntProject成員屬性CAnt *antsdouble m_dLength成員方法CAntProject( )CAntProject( )int initMap( )int Update

14、Trail( )int GetAnt( )int StartSearch( )CAgent成員屬性double dposiAgentDimdouble dbestiAgentDimdouble dviAgentDimdouble m_dFitnessdouble m_dBestFitness成員方法CAgent( )CAgent( )int UpdateFitness( )int UpdatePos( )成員方法Cant( )Cant( )int addcity(int city)int ChooseNextCity( )int MoveTo(int city)int MoveToLast(

15、)int UpdateResult( )int Clear( )應(yīng)用推廣研究結(jié)果主界面收斂趨勢圖最佳路徑圖收斂趨勢比較圖研究結(jié)論在算法研究方面:本文改進的蟻群算法，理論上更加接近自然螞蟻行為；仿真結(jié)果表明改進算法降低了算法的運行時間，提高算法的收斂速度，該算法能在求解速度和解的質(zhì)量上取得一個較好的平衡，該算法是一種有效的算法。在算法參數(shù)組合優(yōu)化方面:本文采用實例仿真法，全面分析蟻群算法五個重要參數(shù)對算法性能的影響，求得各參數(shù)的合理區(qū)間；結(jié)合粒子群算法，首次全面探討蟻群算法的五個重要參數(shù)的組合優(yōu)化問題，提出蟻群算法參數(shù)組優(yōu)化方案，該方案突了傳統(tǒng)取值的局限性。在算法應(yīng)用推廣方面:本文運用軟件開發(fā)技術(shù)，設(shè)計并實現(xiàn)蟻群算法