




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、1,蟻群算法及其應(yīng)用,2,啟發(fā)式算法_分類,現(xiàn)代優(yōu)化算法: 80年代初興起 禁忌搜索(tabu search) 模擬退火(simulated annealing) 神經(jīng)網(wǎng)絡(luò)(neural networks) 遺傳算法(genetic algorithms) 螞蟻算法(Ant Algorithm,群體智能,Swarm Intelligence),3,遺傳算法,遺傳算法(GeneticAlgorithm,GA)是1962年密切根大學(xué)Holland教授首次提出的一種全局優(yōu)化算法,它借用了生物遺傳學(xué)的觀點(diǎn),通過自然選擇、遺傳、變異等作用機(jī)制,實(shí)現(xiàn)各個(gè)體的適應(yīng)性的提高,并迅速推廣到優(yōu)化、搜索、機(jī)器學(xué)習(xí)等
2、方面。,4,遺傳算法的過程,5,蟻群算法,1 原理 2 在TSP中的應(yīng)用及改進(jìn) 3 在QoS多播路由中的應(yīng)用,6,1 蟻群算法原理,20 世紀(jì)90 年代初,意大利學(xué)者Dorigo 等受螞蟻覓食行為的啟發(fā),提出了蟻群算法,是一種仿生算法。 螞蟻在覓食過程中可以找出巢穴到食物源的最短路徑,為什么? (1)信息素(pheromone) (2)正反饋現(xiàn)象:某一路徑上走過的螞蟻越多,則后來者選擇該路徑的概率就越大。,7,簡化的螞蟻尋食過程,螞蟻從A點(diǎn)出發(fā),速度相同,食物在D點(diǎn),可能隨機(jī)選擇路線ABD或ACD。假設(shè)初始時(shí)每條分配路線一只螞蟻,每個(gè)時(shí)間單位行走一步,本圖為經(jīng)過9個(gè)時(shí)間單位時(shí)的情形:走ABD的
3、螞蟻到達(dá)終點(diǎn),而走ACD的螞蟻剛好走到C點(diǎn),為一半路程。,8,簡化的螞蟻尋食過程,經(jīng)過18個(gè)時(shí)間單位時(shí)的情形:走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A,而走ACD的螞蟻剛好走到D點(diǎn)。,9,自然蟻群與人工蟻群,相似之處在于:都是優(yōu)先選擇信息素濃度大的路徑。 兩者的區(qū)別: (1)在于人工蟻群有一定的記憶能力,能夠記憶已經(jīng)訪問過的節(jié)點(diǎn)。 (2)人工蟻群選擇路徑時(shí)不是盲目的。而是按一定規(guī)律有意識(shí)地尋找最短路徑。例如,在TSP問題中,可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。,10,應(yīng)用一:TSP問題,旅行商問題(TSP,traveling salesman problem)1960年首先提出。
4、問題描述: 一商人去n個(gè)城市銷貨,所有城市走一遍再回到起點(diǎn),使所走路程最短。 TSP在許多工程領(lǐng)域具有廣泛的應(yīng)用價(jià)值 例如電路板布線、VLSI芯片設(shè)計(jì)、機(jī)器人控制、交通路由等。 TSP的求解是NP-hard問題。隨著城市數(shù)目的增多,問題空間將呈指數(shù)級增長。,11,TSP問題的數(shù)學(xué)描述,TSP問題表示為一個(gè)N個(gè)城市的有向圖G=(N,A),其中 城市之間距離 目標(biāo)函數(shù)為 其中, ,為城市1,2,n的 一個(gè)排列, 。,12,螞蟻算法求解TSP,下面以TSP為例說明基本蟻群算法模型。 首先將m只螞蟻隨機(jī)放置在n個(gè)城市,位于城市i的第k只螞蟻選擇下一個(gè)城市j的概率為:,13,螞蟻算法求解TSP,其中:
5、表示邊(i,j)上的信息素濃度; 是啟發(fā)信息,d是城市i和j之間的距離; 和反映了信息素與啟發(fā)信息的相對重要性; 表示螞蟻k已經(jīng)訪問過的城市列表。 當(dāng)所有螞蟻完成周游后,按以下公式進(jìn)行信息素更新。,14,螞蟻算法求解TSP,其中:為小于1的常數(shù),表示信息的持久性。,其中:Q為常數(shù);lk表示第k只螞蟻在本次迭代中走過的路徑,Lk為路徑長度。,15,求解TSP算法步驟,初始化隨機(jī)放置螞蟻,為每只螞蟻建立禁忌表tabuk,將初始節(jié)點(diǎn)置入禁忌表中; 迭代過程 k=1 while k=ItCount do (執(zhí)行迭代) for i = 1 to m do (對m只螞蟻循環(huán)) for j = 1 to n
6、 - 1 do (對n個(gè)城市循環(huán)) 根據(jù)式(1),采用輪盤賭方法在窗口外選擇下一個(gè)城市j; 將j置入禁忌表,螞蟻轉(zhuǎn)移到j(luò); end for end for 計(jì)算每只螞蟻的路徑長度; 根據(jù)式(2)更新所有螞蟻路徑上的信息量; k = k + 1; end while 輸出結(jié)果,結(jié)束算法.,16,蟻群的規(guī)模和停止規(guī)則,一、蟻群大小 一般情況下蟻群中螞蟻的個(gè)數(shù)不超過TSP圖中節(jié)點(diǎn)的個(gè)數(shù)。 二、終止條件 1 給定一個(gè)外循環(huán)的最大數(shù)目; 2 當(dāng)前最優(yōu)解連續(xù)K次相同而停止,其中K是一個(gè)給定的整數(shù),表示算法已經(jīng)收斂,不再需要繼續(xù)。,17,螞蟻算法的缺點(diǎn),螞蟻算法的缺點(diǎn): 1)收斂速度慢 2)易于陷入局部最優(yōu)
7、 改進(jìn): 1)采用局部優(yōu)化,設(shè)計(jì)了三種優(yōu)化算子。 2)采用蟻群優(yōu)化算法。 3)其它優(yōu)化算法,18,改進(jìn)一:局部優(yōu)化(算子1 ),19,對Kroa100,算子1優(yōu)化前后的路徑如圖所示。優(yōu)化前(28596),算子1優(yōu)化后(26439),20,改進(jìn)一:局部優(yōu)化(算子2 ),21,對Kroa100,算子2優(yōu)化前后的路徑如圖所示。算子1(26439),算子2優(yōu)化后(23012),22,TSP具有鄰域特征,設(shè)置候選窗口,窗口大小應(yīng)取一個(gè)合理值。 螞蟻總是優(yōu)先選擇候選窗口中的城市。搜索結(jié)束后,根據(jù)候選窗口對路徑進(jìn)行優(yōu)化,如果將候選窗口內(nèi)的節(jié)點(diǎn)交換到當(dāng)前節(jié)點(diǎn)附近后距離更短,則進(jìn)行變異。,改進(jìn)一:局部優(yōu)化(算子
8、3 ),23,對Kroa100,算子3優(yōu)化前后的路徑如圖所示。(23012),算子3優(yōu)化后(21282),24,收斂特性對比,25,改進(jìn)二:蟻群優(yōu)化算法,1)ACS采用了更為大膽的行為選擇規(guī)則,在城市r的螞蟻k轉(zhuǎn)移到城市s的規(guī)則為:,26,2.1.4蟻群優(yōu)化算法,第三,僅對全局最優(yōu)解邊上的信息素進(jìn)行加強(qiáng),更新如下:,27,其它改進(jìn),1)精英策略 2)基于排序的螞蟻系統(tǒng) 3) MAX-MIN螞蟻系統(tǒng),28,應(yīng)用二:QoS多播路由問題,什么是多播路由? 構(gòu)造一棵費(fèi)用最小的多播樹,且滿足以下限制條件: (1) d(T(s, D)D (延時(shí)) (2) dj(T(s, D)DJ (抖動(dòng)) (3) pl(T(s, D)PL (丟包率) (4) b(T(s, D)B. (帶寬),29,路徑的QoS參數(shù)計(jì)算,30,
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 股東對公司借款及資金用途協(xié)議
- 股權(quán)100%轉(zhuǎn)讓及環(huán)保項(xiàng)目合作開發(fā)合同
- 礦山監(jiān)控建設(shè)方案
- 裝修公司聯(lián)動(dòng)方案
- 物業(yè)工作方案
- 租賃企業(yè)整改方案模板
- 商場安全設(shè)備方案
- 地面修復(fù)改造方案
- 編織安全工作評估方案
- 物業(yè)絡(luò)配置方案模板
- GB/T 16451-1996天然脂肪醇
- (約克)機(jī)組熱回收技術(shù)
- 《小學(xué)趣味語文》PPT課件(優(yōu)秀)
- 疫苗及其制備技術(shù)課件
- 世界衛(wèi)生組織-人瘤病毒疫苗:世衛(wèi)組織立場文件2022年5月(英譯中)
- (完整版)常見腫瘤AJCC分期手冊第八版(中文版)
- 《企業(yè)轉(zhuǎn)型升級研究》文獻(xiàn)綜述(3000字)
- 人教版PEP初中八年級下冊英語全冊課件
- 幼兒園大班數(shù)學(xué):《認(rèn)識(shí)單雙數(shù)》課件
- 日本文化介紹
- 藥廠MES系統(tǒng)解決方案
評論
0/150
提交評論