影音先锋男人资源在线观看,精品国产日韩亚洲一区91,中文字幕日韩国产,2018av男人天堂,青青伊人精品,久久久久久久综合日本亚洲,国产日韩欧美一区二区三区在线

遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》.ppt

上傳人:max****ui 文檔編號(hào):15004154 上傳時(shí)間:2020-08-02 格式:PPT 頁(yè)數(shù):60 大?。?32KB
收藏 版權(quán)申訴 舉報(bào) 下載
遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》.ppt_第1頁(yè)
第1頁(yè) / 共60頁(yè)
遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》.ppt_第2頁(yè)
第2頁(yè) / 共60頁(yè)
遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》.ppt_第3頁(yè)
第3頁(yè) / 共60頁(yè)

下載文檔到電腦,查找使用更方便

14.9 積分

下載資源

還剩頁(yè)未讀,繼續(xù)閱讀

資源描述:

《遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》.ppt》由會(huì)員分享,可在線閱讀,更多相關(guān)《遼寧大學(xué)智能控制課件《蟻群優(yōu)化算法》.ppt(60頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第五部分,蟻群優(yōu)化算法Ant Colony Optimization,參考文獻(xiàn),M. Dorigo and T. Stutzle, Ant Colony OptimizationM: MIT Press, 2004 段海濱,蟻群算法原理極其應(yīng)用M,2007.科學(xué)出版社,0 蟻群優(yōu)化算法的歷史沿革,意大利學(xué)者M(jìn)arco Dorigo(Alberto Colorni)于1991年在其博士論文中提出。 和Vittorio Maniezzo一同設(shè)計(jì)了第一個(gè)ACO算法螞蟻系統(tǒng)(Ant System)。 在真實(shí)螞蟻覓食行為的啟發(fā)下提出的一種高度創(chuàng)新性的啟發(fā)式算法。,Marco Dorigo,Macro D

2、origo,重要文獻(xiàn),Colorni等,1994,“Ant System for Job-shop Scheduling” Colorni等,1996,“Heuristics From Natrure for Hard Combinatorial Optimization Problems” Dorigo M等,1996,“Ant system: optimization by a colony of cooperating agents”,Ant system: optimization by a colony of cooperating agents,更加系統(tǒng)地闡述了蟻群算法的基本原理和

3、數(shù)學(xué)模型; 與遺傳算法、禁忌搜索算法、模擬退火算法、爬山法等進(jìn)行了仿真實(shí)驗(yàn)比較; 把單純地解決對(duì)稱(chēng)TSP拓展到解決非對(duì)稱(chēng)TSP、QAP和JSP; 對(duì)蟻群算法中的初始化參數(shù)對(duì)性能的影響做了初步探討; 蟻群算法發(fā)展史上的一篇奠基性文章。,近期發(fā)展,2000年,Dorigo M和Bonabeau E等在Nature上發(fā)表蟻群算法的研究綜述,把這一領(lǐng)域的研究推向了國(guó)際學(xué)術(shù)的最前沿; 進(jìn)入21世紀(jì)的最近幾年里,Nature曾多次對(duì)蟻群算法的研究成果進(jìn)行報(bào)告。,相關(guān)書(shū)籍,2004年9月,Marco Dorigo and Thomas SttzleAnt Colony Optimization; 系統(tǒng)介紹蟻

4、群算法,為蟻群算法的傳播和科普做出了很重要一步; 2007年翻譯成中文出版。,理論建設(shè),在理論建設(shè)方面,ACO取得的成果比較少,也是最薄弱的一方面。 1999年Gutjahr W J的技術(shù)報(bào)告和2000年的論文中首次對(duì)蟻群算法的收斂性進(jìn)行了證明。 將蟻群算法的行為簡(jiǎn)化為在一幅代表所求問(wèn)題的有向圖上的隨機(jī)行走過(guò)程,進(jìn)而從有向圖論的角度對(duì)一種改進(jìn)蟻群算法圖搜索螞蟻系統(tǒng)(Graph-Based Ant System,GBAS)的收斂性進(jìn)行了理論分析。 采用的數(shù)學(xué)工具是Markov鏈,證明了在一些合理的假設(shè)條件下他所提出的GBAS能以一定概率收斂到所求問(wèn)題的最優(yōu)解。,蟻群優(yōu)化算法的發(fā)展,精華螞蟻系統(tǒng)(

5、Elitist Strategy for Ant System,EAS) 對(duì)解構(gòu)造過(guò)程中表現(xiàn)優(yōu)異的人工螞蟻給予特殊的信息素釋放獎(jiǎng)勵(lì); Ant-Q算法 將蟻群算法與Q學(xué)習(xí)算法結(jié)合,利用多個(gè)人工螞蟻的協(xié)同效應(yīng); 后期 蟻群系統(tǒng)(Ant Colony System,ACS), 基于排序的螞蟻系統(tǒng)(Rank Based version AS,ASrank), 最大最小螞蟻系統(tǒng)(Max-Min Ant System,MMAS),蟻群優(yōu)化算法的應(yīng)用,路由類(lèi)問(wèn)題 旅行商、車(chē)輛路由、順序排列等 分配類(lèi)問(wèn)題 二次分配、圖著色、廣義分配、頻率分配、大學(xué)生課程時(shí)間表等 調(diào)度類(lèi)問(wèn)題 工序車(chē)間、開(kāi)放車(chē)間、工作流車(chē)間、總

6、延遲、總權(quán)重延遲、項(xiàng) 目調(diào)度、組車(chē)間等,蟻群優(yōu)化算法的應(yīng)用,子集類(lèi)問(wèn)題 多重背包、最大獨(dú)立集、冗余分配、集合覆蓋、帶權(quán)約束圖樹(shù)分割、邊帶權(quán)l(xiāng)-基樹(shù)、最大圖等 機(jī)器學(xué)習(xí)類(lèi)問(wèn)題 分配規(guī)則、貝葉斯網(wǎng)絡(luò)、模糊系統(tǒng)等 網(wǎng)絡(luò)路由類(lèi)問(wèn)題 面向連接的網(wǎng)絡(luò)路由、無(wú)連接的網(wǎng)絡(luò)路由、光學(xué)網(wǎng)絡(luò)路由等,1 蟻群優(yōu)化算法的生物學(xué)基礎(chǔ),阿根廷螞蟻 雙橋?qū)嶒?yàn),實(shí)驗(yàn)結(jié)果(1),摘自Ant Colony Optimization,實(shí)驗(yàn)結(jié)果(2),摘自Ant Colony Optimization,實(shí)驗(yàn)結(jié)果(3),摘自Ant Colony Optimization,障礙實(shí)驗(yàn),摘自Ant System: Optimization b

7、y A Colony of Cooperating Agents,生物螞蟻的特點(diǎn),沒(méi)有視覺(jué) 計(jì)算與記憶能力有限 依賴(lài)信息素(pheromone)通信、協(xié)作 釋放 揮發(fā) 正反饋,2 人工蟻群系統(tǒng),人工螞蟻與生物螞蟻的區(qū)別 人工螞蟻具有一定的記憶能力 人工螞蟻具有一定的視力(啟發(fā)) 人工螞蟻生活在離散的時(shí)間環(huán)境中,人工蟻群模型,摘自Ant System: Optimization by A Colony of Cooperating Agents,人工蟻群,a) 初始狀態(tài); b) t=0,無(wú)信息素,人工螞蟻以等概率選擇左 轉(zhuǎn)或右轉(zhuǎn); c) t=1 ,較短的路徑上信息素濃度較高,人工 螞蟻以較高

8、的概率選擇信息素濃度高的路徑,實(shí)例:TSP,Graph (N,E) Euclidean距離 螞蟻數(shù)量,實(shí)例:TSP,人工螞蟻的行為 路徑選擇的概率是城市距離和路徑上信息素濃度的函數(shù); 符合TSP規(guī)則; 完成一次旅行后,在經(jīng)過(guò)的路徑上釋放信息素; 無(wú)需按原路返回。,實(shí)例:TSP(參數(shù)與機(jī)制),路徑上的信息素濃度 信息素更新 信息素釋放(ant-cycle),實(shí)例:TSP(參數(shù)與機(jī)制),路徑選擇概率,TSP蟻群算法(ant-cycle),Step 1 Initialize: Set t:=0 t is the time counter Set NC:=0 NC is the cycles coun

9、ter For every edge (i,j) set an initial value for trail intensity and Place the m ants on the n nodes,TSP蟻群算法(ant-cycle),Step 2 Set s:=1 s is the tabu list index For k:=1 to m do Place the starting town of the k-th ant in tabuk(s),TSP蟻群算法(ant-cycle),Step 3 Repeat until tabu list is full this ste

10、p will be repeated (n-1) times Set s:=s+1 For k:=1 to m do Choose the town j to move to, with probability at time t the k-th ant is on town i=tabuk(s-1) Move the k-th ant to the town j Insert town j in tabuk (s),TSP蟻群算法(ant-cycle),Step 4.1 For k:=1 to m do Move the k-th ant from tabuk(n) to tabuk(

11、1) Compute the length Lk of the tour described by the k-th ant Update the shortest tour found,TSP蟻群算法(ant-cycle),Step 4.2 For every edge (i,j) For k:=1 to m do,TSP蟻群算法(ant-cycle),Step 5 For every edge (i,j) compute according to equation Set t:=t+n Set NC:=NC+1 For every edge (i,j) set,TSP蟻群算法(ant

12、-cycle),Step 6 If (NC < NCMAX) and (not stagnation behavior) then Empty all tabu lists Goto step 2 else Print shortest tour Stop,3 蟻群算法調(diào)整與參數(shù)設(shè)置,:信息素的相對(duì)重要性; :?jiǎn)l(fā)性因素的相對(duì)重要性; :信息素殘留因子; Q :常數(shù),控制信息素的釋放; m :蟻群規(guī)模; 其他: 蟻群的初始分布,信息素釋放算法ant-cycle,ant-cycle,信息素釋放算法ant-density,ant-density,信息素釋放算法ant-quantity,ant-

13、quantity,信息素釋放算法對(duì)比,測(cè)試集: Oliver30 problem 循環(huán)次數(shù):NCMAX=5000 測(cè)試次數(shù):10,摘自Ant Colony Optimization,GA:424.635,實(shí)驗(yàn)數(shù)據(jù)1 ant-cycle,摘自Ant Colony Optimization,實(shí)驗(yàn)數(shù)據(jù)2 ant-cycle,摘自Ant Colony Optimization,實(shí)驗(yàn)數(shù)據(jù)3 ant-cycle,摘自Ant Colony Optimization,參數(shù):,ant-cycle NCMAX=5000,摘自Ant Colony Optimization,蟻群規(guī)模:m,ant-cycle 4x4

14、grid,,摘自Ant Colony Optimization,蟻群初始分布,均勻分布優(yōu)于集中(單一城市)分布 隨機(jī)分布略好于均勻分布,算法復(fù)雜度,O(NCn2m) step 1 : O(n2+m), step 2 : O(m), step 3 : O(n2m), step 4 : O(n2m), step 5 : O(n2), step 6 : O(nm).,實(shí)驗(yàn)數(shù)據(jù)(算法復(fù)雜度),摘自Ant Colony Optimization,4 實(shí)例:JSP,Job-shop Scheduling Problem M:機(jī)器數(shù)量 J :任務(wù)數(shù) ojm:工序 djm:工時(shí) :工序集合,JSP(M

15、uth & Thompson 6x6),JSP,3x2 problem,JSP,路徑選擇,JSP,待訪問(wèn)節(jié)點(diǎn)集合: 下一步允許訪問(wèn)節(jié)點(diǎn)集合: 算法結(jié)束:,,5 實(shí)例:PID參數(shù)整定,整定參數(shù) 目標(biāo)函數(shù),PID參數(shù)整定,Kp=12.345 Td=6.7890 Ti =9.8765 (123456789098765)x(1234567890),PID參數(shù)整定,信息素釋放,PID參數(shù)整定,路徑選擇概率,6 蟻群優(yōu)化算法研究現(xiàn)狀,蟻群系統(tǒng)(Ant Colony System,ACS) 基于排序的螞蟻系統(tǒng)(Rank Based version AS,ASrank) 最大最小螞蟻系統(tǒng)(Max-Min An

16、t System,MMAS),蟻群系統(tǒng)ACS,結(jié)合Q-learning; ACS采用了更為大膽的行為選擇規(guī)則; 只增強(qiáng)屬于全局最優(yōu)解的路徑上的信息素;,到當(dāng)前為止全局最優(yōu)的路徑長(zhǎng)度,蟻群系統(tǒng)ACS,引入負(fù)反饋機(jī)制。每當(dāng)螞蟻由一個(gè)節(jié)點(diǎn)移動(dòng)到另一個(gè)節(jié)點(diǎn)時(shí),該路徑上的信息素按照如下公式被相應(yīng)的消除一部分,從而實(shí)現(xiàn)一種信息素的局部調(diào)整,以減小已選擇過(guò)的路徑再次被選擇的概率。,最大最小螞蟻系統(tǒng)MMAS,修改了AS的信息素更新方式; 每次迭代之后只有一只螞蟻能夠進(jìn)行信息素的更新,以獲取更好的解; 為了避免搜索停滯,路徑上的信息素濃度被限制在MAX,MIN 范圍內(nèi); 信息素的初始值被設(shè)為其取值上限,有助于增加算法初始階段的搜索能力。,基于排序的螞蟻系統(tǒng)ASrank,與“精英策略”相似; 算法中總是更新更好進(jìn)程上的信息素; 選擇的標(biāo)準(zhǔn)是其行程長(zhǎng)度決定的排序;,基于排序的螞蟻系統(tǒng)ASrank,每個(gè)螞蟻釋放信息素的強(qiáng)度通過(guò)排序加權(quán)處理確定。其中,為每次迭代后釋放信息素的螞蟻總數(shù)。,

展開(kāi)閱讀全文
溫馨提示:
1: 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!