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

《《碩士畢業(yè)論文答辯》ppt課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

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

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

3、發(fā)城市，要求找出一條最短的路徑；該問(wèn)題可抽象像為求完全圖(n個(gè)節(jié)點(diǎn))的最短路徑問(wèn)題。更新機(jī)制：在t+n時(shí)刻，此時(shí)所有的螞蟻完成了一次遍歷，為了避免殘留信息素過(guò)多而淹沒(méi)距離因素，在每只螞蟻?zhàn)咄暌徊交蛘叩淮魏?，要?duì)路徑上的信息素進(jìn)行更新操作，各路徑上信息素可根據(jù)以下公式做調(diào)整：根據(jù)計(jì)算方式不同，有蟻周模型、蟻量模型和蟻密模型三種基本模型，本文的研究都是基于蟻周模型的，其模型為：研究背景——蟻群算法數(shù)學(xué)模型(2)研究背景——蟻群算法研究方向算法理論改進(jìn)參數(shù)分析應(yīng)用推廣數(shù)學(xué)證明1:算法易出現(xiàn)局部最優(yōu)、停滯等不良現(xiàn)象2:在求解較大規(guī)模問(wèn)題時(shí)，算法的運(yùn)行時(shí)間過(guò)長(zhǎng)3:算法的收斂速度慢

4、4:算法參數(shù)的設(shè)置帶有很強(qiáng)的經(jīng)驗(yàn)性和隨機(jī)性，沒(méi)有嚴(yán)格的理論認(rèn)證研究表明蟻群算法具有較強(qiáng)的魯棒性、分布式計(jì)算、易于與其優(yōu)化算法結(jié)合等優(yōu)點(diǎn)；但隨著問(wèn)題規(guī)模的擴(kuò)大，算法的運(yùn)行時(shí)間和最優(yōu)解都不能認(rèn)人滿意，性能明顯下降。大量研究表明蟻群算法也存在一些不足，主要有：蟻群算法研究方向:算法改進(jìn)——研究背景針對(duì)蟻群算法存在的不足，國(guó)內(nèi)外學(xué)者開(kāi)展了大量有意義的研究。研究成果主要涉及路徑搜索策略、信息素更新策略和最優(yōu)解保留策略等方面；研究行為主要是進(jìn)行算法改進(jìn)或驗(yàn)證。有些改進(jìn)算法的性能相比基本蟻群算法而言有了較大水平的提高，如最大最小蟻群算法是目前求解TSP問(wèn)題的最好方法之一；有些已成為主流的

5、蟻群算法,如：蟻群系統(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)——研究過(guò)程(1)基本蟻群算法中，路徑上的初始信息素大小是相同的，蟻群創(chuàng)建的第一條路徑所獲得的信息主要是城市之間的距離信息，此時(shí)，蟻群算法相當(dāng)于貪婪算法。第一次循環(huán)中蟻群在所經(jīng)過(guò)的路徑上留下的信息素不一定能反映出最優(yōu)路徑的方向。正反饋的作用會(huì)使得這條不是最優(yōu)解的路徑上的信息素得到不應(yīng)有的增強(qiáng)，阻礙以后的螞蟻發(fā)現(xiàn)更

6、好的全局最優(yōu)解。為此，本文改進(jìn)算法在任意兩個(gè)城市之間安排的信息素是等量的,但是這等量的信息素要平均到兩個(gè)之間的路徑上,由于城市之間的距離是不相同的,所以平均到每一小段上的信息素量就是距離的倒數(shù)與分配到這兩城市之間的信息素量之積。為提高初始階段螞蟻的搜索能力，改進(jìn)算法將各路徑上的初始信息素的值按照最大最小蟻群算法思想限定其大小。所以其數(shù)學(xué)模型為：1：初始信息素本文算法改進(jìn)——研究過(guò)程(2)2:路徑選擇策略的改進(jìn)相關(guān)文獻(xiàn)表明，自然螞蟻無(wú)視覺(jué)能力，無(wú)法感知距離的遠(yuǎn)近,在節(jié)點(diǎn)選擇時(shí)，僅能依靠信息素濃度。為更好的模擬自然螞蟻,本文改進(jìn)算法在選擇下一個(gè)城市時(shí)不再考慮距離因素,僅考慮信息

7、素濃度。同時(shí)為有效的提高優(yōu)化速度,降低局部最優(yōu)解停滯的可能性,本文采用偽隨機(jī)性選擇策略,并在搜索過(guò)程中動(dòng)態(tài)地調(diào)整確定性選擇的概率。即螞蟻在t時(shí)刻有城市i到城市j的轉(zhuǎn)移概率由下式確定：3:信息素更新策略策略的改進(jìn)本文算法改進(jìn)——研究過(guò)程(3)兩層信息素更新策略：第1層:原有信息素的揮發(fā)第2層:借鑒獎(jiǎng)懲蟻群算法思想，在完成每次循環(huán)進(jìn)行信息素?fù)]發(fā)后，根據(jù)螞蟻所建立路徑的長(zhǎng)短，進(jìn)行排序，只有前w只建立短路徑的螞蟻被挑選出來(lái)進(jìn)行獎(jiǎng)勵(lì)，其他(m-w)只建立路徑的螞蟻進(jìn)行懲罰。最大最小蟻群算法思想：若某段路徑弧段的信息素相對(duì)其他