《碩士畢業(yè)論文答辯》PPT課件.ppt

《《碩士畢業(yè)論文答辯》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《碩士畢業(yè)論文答辯》PPT課件.ppt（27頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

3、路徑；該問題可抽象像為求完全圖( n個(gè)節(jié)點(diǎn))的最短路徑問題。0t 0t 0 )()( )()()( kalloweds isis ijijkij allowedjiftt tttP k 更新機(jī)制：在 t+n時(shí)刻，此時(shí)所有的螞蟻完成了一次遍歷，為了避免殘留信息素過多而淹沒距離因素，在每只螞蟻?zhàn)咄暌徊交蛘叩淮魏螅獙?duì)路徑上的信息素進(jìn)行更新操作，各路徑上信息素可根據(jù)以下公式做調(diào)整：根據(jù)計(jì)算方式不同，有蟻周模型、蟻量模型和蟻密模型三種基本模型，本文的研究都是基于蟻周模型的，其模型為： mk kijij ijijij tnt 1 )()1()( else jikifLQ kkij 0 ),(只 螞

4、蟻 在 本 次 迭 代 中 過第 研究背景蟻群算法數(shù)學(xué)模型(2) 研究背景蟻群算法研究方向算法理論改進(jìn) 參數(shù)分析應(yīng)用推廣數(shù)學(xué)證明1:算法易出現(xiàn)局部最優(yōu)、停滯等不良現(xiàn)象2:在求解較大規(guī)模問題時(shí)，算法的運(yùn)行時(shí)間過長3:算法的收斂速度慢4:算法參數(shù)的設(shè)置帶有很強(qiáng)的經(jīng)驗(yàn)性和隨機(jī)性，沒有嚴(yán)格的理論認(rèn)證 研究表明蟻群算法具有較強(qiáng)的魯棒性、分布式計(jì)算、易于與其優(yōu)化算法結(jié)合等優(yōu)點(diǎn)；但隨著問題規(guī)模的擴(kuò)大，算法的運(yùn)行時(shí)間和最優(yōu)解都不能認(rèn)人滿意，性能明顯下降。大量研究表明蟻群算法也存在一些不足，主要有：蟻群算法研究方向: 算法改進(jìn)研究背景 針對(duì)蟻群算法存在的不足，國內(nèi)外學(xué)者開展了大量有意義的研究。研究成果主要涉及路

5、徑搜索策略、信息素更新策略和最優(yōu)解保留策略等方面；研究行為主要是進(jìn)行算法改進(jìn)或驗(yàn)證。有些改進(jìn)算法的性能相比基本蟻群算法而言有了較大水平的提高，如最大最小蟻群算法是目前求解TSP問題的最好方法之一；有些已成為主流的蟻群算法,如：蟻群系統(tǒng)，基于排序的蟻群系統(tǒng)，最優(yōu)最差蟻群系統(tǒng)等。 針對(duì)基本蟻群算法的不足，本文在借鑒其他算法優(yōu)點(diǎn)的基礎(chǔ)上提出一種改進(jìn)的蟻群算法。該算法從以下幾個(gè)方面對(duì)基本蟻群算法進(jìn)行了改進(jìn)： 1:初始信息素的改進(jìn)2:路徑選擇策略的改進(jìn)3:信息素更新策略的改進(jìn) 本文算法改進(jìn)研究過程(1) 基本蟻群算法中，路徑上的初始信息素大小是相同的，蟻群創(chuàng)建的第一條路徑所獲得的信息主要是城市之間的距離

6、信息，此時(shí)，蟻群算法相當(dāng)于貪婪算法。第一次循環(huán)中蟻群在所經(jīng)過的路徑上留下的信息素不一定能反映出最優(yōu)路徑的方向。正反饋的作用會(huì)使得這條不是最優(yōu)解的路徑上的信息素得到不應(yīng)有的增強(qiáng)，阻礙以后的螞蟻發(fā)現(xiàn)更好的全局最優(yōu)解。為此，本文改進(jìn)算法在任意兩個(gè)城市之間安排的信息素是等量的,但是這等量的信息素要平均到兩個(gè)之間的路徑上,由于城市之間的距離是不相同的,所以平均到每一小段上的信息素量就是距離的倒數(shù)與分配到這兩城市之間的信息素量之積。為提高初始階段螞蟻的搜索能力，改進(jìn)算法將各路徑上的初始信息素的值按照最大最小蟻群算法思想限定其大小。所以其數(shù)學(xué)模型為：1：初始信息素 else jiifdQijij 0)0(

7、maxmin )0( ij 本文算法改進(jìn)研究過程(2)2:路徑選擇策略的改進(jìn)相關(guān)文獻(xiàn)表明，自然螞蟻無視覺能力，無法感知距離的遠(yuǎn)近,在節(jié)點(diǎn)選擇時(shí)，僅能依靠信息素濃度。為更好的模擬自然螞蟻,本文改進(jìn)算法在選擇下一個(gè)城市時(shí)不再考慮距離因素,僅考慮信息素濃度。同時(shí)為有效的提高優(yōu)化速度,降低局部最優(yōu)解停滯的可能性,本文采用偽隨機(jī)性選擇策略,并在搜索過程中動(dòng)態(tài)地調(diào)整確定性選擇的概率。即螞蟻 在 t時(shí)刻有城市 i 到城市 j 的轉(zhuǎn)移概率由下式確定： 0maxP qqifP iuallowedu k 0 )( kallowedk ikij tabujtp k 3:信息素更新策略策略的改進(jìn)本文算法改進(jìn)研究過程(

8、3)兩層信息素更新策略：第1層:原有信息素的揮發(fā)第2層:借鑒獎(jiǎng)懲蟻群算法思想，在完成每次循環(huán)進(jìn)行信息素?fù)]發(fā)后，根據(jù)螞蟻所建立路徑的長短，進(jìn)行排序，只有前w只建立短路徑的螞蟻被挑選出來進(jìn)行獎(jiǎng)勵(lì)，其他 (m-w )只建立路徑的螞蟻進(jìn)行懲罰。最大最小蟻群算法思想：若某段路徑弧段的信息素相對(duì)其他路徑弧段的信息 素而言在數(shù)量上占據(jù)絕對(duì)的優(yōu)勢時(shí),會(huì)引起算法過早地收斂。對(duì)這一不足,本文借鑒MMAS思想,對(duì)各路徑上的信息素量施加最小最大限制。采用兩層信息素更新策略和最大最小蟻群算法思想)()1()( tnt ijij mwrij wrijij mrwifrwm Qnt wrifrwm Qntnt 11)( 0

9、)()( maxmin )( tij 開始初始化螞蟻構(gòu)建路徑所有螞蟻結(jié)束？路徑排序信息素更新 滿足結(jié)束條件？結(jié)束NYN Y 本文算法改進(jìn)算法流程 本文算法改進(jìn)性能驗(yàn)證算法平均最優(yōu)解平均迭代次數(shù)平均運(yùn)行時(shí)間(s)基本蟻群算法449.3535 124 29最大最小蟻群算法437.9628 98 29本文改進(jìn)算法443.9927 104 23文獻(xiàn)48算法439.9628未知31文獻(xiàn)49算法447.7771未知33TSP51問題各算法性能比較表算法平均最優(yōu)解平均迭代次數(shù)平均運(yùn)行時(shí)間基本蟻群算法564.6498 238 39 最大最小蟻群系統(tǒng)559.2238 198 34本文改進(jìn)算法561.3410 1

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

11、則有函數(shù) ，那么參數(shù)的連續(xù)區(qū)域優(yōu)化問題可以定義為：確定蟻群算法五個(gè)主要參數(shù) 的值，使得函數(shù) 取得最優(yōu)值。由這個(gè)定義我們自然地可以將參數(shù)的優(yōu)化看成一個(gè)組合優(yōu)化問題，而且是一個(gè)連續(xù)域的組合優(yōu)化問題。選定方法:粒子群算法，因粒子群優(yōu)化算法具有很強(qiáng)的全局優(yōu)化能力，能較快地收斂于可接受解；而且粒子群優(yōu)化算法參數(shù)少，算法簡單易實(shí)現(xiàn)，效率較高。解決問題: 實(shí)例仿真法：綜合考慮算法的全局搜索能力和收斂速度兩項(xiàng)性能指標(biāo)，確定各參數(shù)的合理區(qū)間. 采用“三步走”策略確定蟻群算法參數(shù)的較優(yōu)組合： (1)利用實(shí)例仿真法確定的各個(gè)參數(shù)的合理區(qū)間 (2)利用粒子群優(yōu)化算法，確定參數(shù)的最佳組合 (3)多次結(jié)果，求平均),(

12、Qmf 結(jié)束 初始化生成粒子群循環(huán)迭代求全局最佳位置以及最優(yōu)適應(yīng)度函數(shù)值求每個(gè)粒子個(gè)體最佳位置移動(dòng)粒子更新粒子速度向量 滿足循環(huán)條件？ 開始NY Y N 參數(shù)組合優(yōu)化關(guān)鍵技術(shù) 參數(shù)組合優(yōu)化有效性驗(yàn)證參數(shù)類型組次參數(shù)取值最優(yōu)路徑長度參數(shù)最佳組合1 1.60 4.89 34 0.75 4 7544.72 1.49 5.10 33 0.78 5 7554.03 1.05 5.08 30 0.80 5 7576.14 1.01 4.75 34 0.74 6 7614.87 參數(shù)隨機(jī)組合5 1.35 1.25 20 0.50 1 8027.06 2.50 4.90 34 0.1 8 7794.67 3.

13、50 5.79 40 0.8 9 8059.28 1.00 5.00 28 0.50 4 7670.49 5.30 5.04 46 0.80 2 8205.24 m Q 應(yīng)用推廣研究背景 蟻群算法提出十幾年來，取得了豐碩的應(yīng)用性成果，主要有：物流配送問題、VRP問題、函數(shù)優(yōu)化問題、車間作業(yè)調(diào)度問題、網(wǎng)絡(luò)路由問題、電力系統(tǒng)機(jī)器人領(lǐng)域、控制參數(shù)組合優(yōu)化問題、聚類分析、數(shù)據(jù)挖掘、數(shù)字圖象處理、生命科學(xué)化學(xué)工業(yè)等等。大量有價(jià)值的研究成果將陸續(xù)發(fā)表，不斷地拓寬了其應(yīng)用領(lǐng)域。 本文主要從算法實(shí)現(xiàn)方面進(jìn)行應(yīng)用推廣。 本文采用軟件工程思想，利用軟件開發(fā)技術(shù)，設(shè)計(jì)并實(shí)現(xiàn)了蟻群算法參數(shù)訓(xùn)練系統(tǒng)及蟻群算法TSP問題

14、仿真系統(tǒng)；通過參數(shù)訓(xùn)練仿真系統(tǒng)，用戶可以訓(xùn)練得到蟻群算法參數(shù)的理想組合；通過蟻群算法仿真系統(tǒng)，用戶可以記錄并查看算法求解TSP問題過程的中間數(shù)據(jù)，最優(yōu)解及最優(yōu)路徑，查看收斂圖，路徑收斂趨勢圖及算法間性能比較圖。 應(yīng)用推廣研究方案采用方法：軟件工程方法，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_iCi

15、tyCount)CMapInfo() CAntProject成員屬性CAnt *antsdouble m_dLength成員方法CAntProject( )CAntProject( )int initMap( ) int UpdateTrail( )int GetAnt( )int StartSearch( ) CAgent成員屬性double dposiAgentDimdouble dbestiAgentDimdouble dviAgentDimdouble m_dFitnessdouble m_dBestFitness成員方法CAgent( )CAgent( )int UpdateFitn

16、ess( )int UpdatePos( )成員方法Cant( )Cant( )int addcity(int city)int ChooseNextCity( )int MoveTo(int city)int MoveToLast( )int UpdateResult( )int Clear( ) 應(yīng)用推廣研究結(jié)果主界面 收斂趨勢圖 最佳路徑圖 收斂趨勢比較圖 研究結(jié)論在算法研究方面:本文改進(jìn)的蟻群算法，理論上更加接近自然螞蟻行為；仿真結(jié)果表明改進(jìn)算法降低了算法的運(yùn)行時(shí)間，提高算法的收斂速度，該算法能在求解速度和解的質(zhì)量上取得一個(gè)較好的平衡，該算法是一種有效的算法。在算法參數(shù)組合優(yōu)化方面:本

17、文采用實(shí)例仿真法，全面分析蟻群算法五個(gè)重要參數(shù)對(duì)算法性能的影響，求得各參數(shù)的合理區(qū)間；結(jié)合粒子群算法，首次全面探討蟻群算法的五個(gè)重要參數(shù)的組合優(yōu)化問題，提出蟻群算法參數(shù)組優(yōu)化方案，該方案突了傳統(tǒng)取值的局限性。在算法應(yīng)用推廣方面:本文運(yùn)用軟件開發(fā)技術(shù)，設(shè)計(jì)并實(shí)現(xiàn)蟻群算法仿真系統(tǒng)，包括蟻群算法參數(shù)訓(xùn)練模塊和蟻群算法TSP問題仿真模塊。通過仿真系統(tǒng)用戶可以很直觀的了解各算法求解TSP問題時(shí)的收斂趨勢圖、路徑圖、運(yùn)行時(shí)間及最優(yōu)路徑等等。 未來研究1:對(duì)所提出的改進(jìn)算法的收斂性進(jìn)行研究2:對(duì)所提出的蟻群算法參數(shù)組合優(yōu)化方案的可行性進(jìn)行理論論證3:對(duì)仿真系統(tǒng)進(jìn)行壓力測試，進(jìn)一步排除bug4:封裝算法代碼為庫文件，方便第三方調(diào)用，推廣蟻群蟻群算法應(yīng)用 致謝感謝王更生教授的指導(dǎo)！感謝各位老師的蒞臨！感謝父母的支持！感謝各位同學(xué)的支持！敬請(qǐng)各位老師指導(dǎo)！