螞蟻算法ppt課件(編輯修改稿)
2025-05-26 03:44 本頁面
【文章內(nèi)容簡介】 調(diào)度問題(SP)Colorni,Dorigo,ManiezzoStizleBaueretalDenBesten,Dorigo,Maniezzo陳義寶、周濟(jì)等ASJSPASFSPACSSMTTPACSSMTWTP工件排序蟻群算法19941997199919992022表 2螞蟻算法及其應(yīng)用（續(xù)） 路由問題（ RP）Bullnheimer,Hartl,StraussGambardella,Taillard,AgazziSchoonderwoerd,Bonabeau,vanderputetalWhite,Pagurek,OppacherDiCaro,DorigoSubramanian,Druschel,ChenHeusseetalNavarroVarela,Sinclair李生紅，劉澤民，周正張素兵，劉澤民丁建立、陳增強(qiáng)、袁著祉ASVRPHASVRPABC,ABCsmart,ABCbackwardASGAAntNetFA,AntNetFSRegularantsCAFACOVWPVC路由選擇分布式多播路由動態(tài)路由選擇199719991996199819981997,1998199719981999202220222022其他問題 Gambardella,DorigoCostaandHertzMichel,MiddendorfLeguizamon,MichalewiczLiang,Smith馬良，蔣馥馬良，王龍德丁建立、陳增強(qiáng)、袁著祉HASSOPANTCOLASSCSASMKPACORAP度限制最小樹（ DCMST）背包問題螞蟻算法螞蟻算法收斂性分析19971997199819991999199920222022螞蟻算法可研究問題 螞蟻算法的研究與發(fā)展歷史畢竟較短，還存在諸多問題：（ 1）它的發(fā)展遠(yuǎn)沒有形成完整的理論體系；（ 2）模型對問題具有依賴性，研究者必須根據(jù)問題的特點選擇和修正模型；（ 3）算法的參數(shù)選擇更多的是依靠實驗和經(jīng)驗，沒有定理或公認(rèn)的確定方法；（ 4）由于初始信息素匱乏，計算時間偏長，對實時應(yīng)用不利。這些都表明其理論和實踐方面有許多問題尚需更深入的研究。舉例 1：遺傳算法與螞蟻算法的融合 l 遺傳算法具有快速隨機(jī)的全局搜索能力，但不能很好地利用系統(tǒng)的反饋信息 ,當(dāng)求解到一定范圍時往往作大量無為的冗余迭代，求精確解效率低。l 螞蟻系統(tǒng)是一種并行的分布式正反饋系統(tǒng)，它是通過信息素的累積和更新收斂于最優(yōu)路徑上，但初期信息素匱乏，初始求解速度慢。l 遺傳算法與螞蟻算法的融合模型，采用遺傳算法生成初始信息素分布，利用螞蟻算法反復(fù)迭代求精確解，以期達(dá)到優(yōu)勢互補。遺傳算法的基本原理圖 31簡單遺傳算法進(jìn)化過程示例種群位串 適應(yīng)值 排序1 101101101132 110001110023 011101010114 01100100104交叉位11000111000111010101變異位11000101010111011100新后代11000101010111001100選擇交叉變異新 后代遺傳算法的特點 遺傳算法具有進(jìn)化計算的所有特征，其優(yōu)點是：l （ 1）具有大范圍全局搜索的能力，與問題領(lǐng)域無關(guān)；l （ 2）搜索從群體出發(fā)，具有潛在的并行性；l （ 3）可進(jìn)行多值比較，魯棒性強(qiáng)；l （ 4）搜索使用評價函數(shù)啟發(fā)，過程簡單；l （ 5）使用概率機(jī)制進(jìn)行迭代，具有隨機(jī)性；l （ 6）具有可擴(kuò)展性，容易與其它算法結(jié)合。但遺傳算法在編碼表示、適應(yīng)度函數(shù)、選擇策略、控制參數(shù)等方面還存在諸多問題。特別是，對于系統(tǒng)中的反饋信息利用不夠，當(dāng)求解到一定范圍時往往作大量無為的冗余迭代，求精確解效率低。 遺傳算法與螞蟻算法的融合思想 遺傳算法與螞蟻算法的融合 （ GeicAlgorithm—AntAlgorithm簡稱 GAAA） ,其基本思想是汲取兩種算法的優(yōu)點，克服各自的缺陷，優(yōu)勢互補。在時間效率上優(yōu)于螞蟻算法，在求精解效率上優(yōu)于遺傳算法，是時間效率和求解效率都比較好的一種新的啟發(fā)式方法。其基本思路是算法前過程采用遺傳算法，充分利用遺傳算法的快速性、隨機(jī)性、全局收斂性，其結(jié)果是產(chǎn)生有關(guān)問題的初始信息素分布。算法后過程采用螞蟻算法，在有一定初始信息素分布的情況下，充分利用螞蟻算法并行性、正反饋性、求精解效率高等特點。 GAAA算法總體框架與流程 圖 32GAAA算法總體框架 定義目標(biāo)函數(shù) 生成若干組優(yōu)化解定義適應(yīng)值函數(shù) 轉(zhuǎn)化為初始信息素分布問題 遺傳算法 螞蟻算法 最好解圖 33GAAA算法詳細(xì)流圖GAAA中遺傳算法的模型選擇定義 l GAAA中的遺傳算法 是基于優(yōu)勝選擇遺傳算法的原理與定義。l 編碼與適應(yīng)值函數(shù)： 如 TSP問題，以城市的遍歷次序作為遺傳算法的編碼，適應(yīng)度函數(shù)取為哈密頓圈的長度的倒數(shù)。l 種群生成與染色體選擇： 利用隨機(jī)函數(shù)生成一定數(shù)量的十進(jìn)制實數(shù)編碼種群，根據(jù)適應(yīng)值函數(shù)選擇準(zhǔn)備進(jìn)行交配的一對染色體父串。l 交叉算子： 采用 Davis提出的順序交叉方法。l 變異算子 ：采用逆轉(zhuǎn)變異方法。l 交叉算子： 采用 Davis提出的順序交叉方法，先進(jìn)行常規(guī)的雙點交叉，在進(jìn)行維持原有相對訪問順序的巡回路線修改。具體交叉如下：l （ 1）隨機(jī)在父串上選擇一個交配區(qū)域，如兩父串選定為：l old1=12|3451
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1