版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領
文檔簡介
2023/2/51數(shù)學建模常用智能算法
及其Matlab實現(xiàn)負責人:胡丹
成員:袁莉莉王霖侯金靈馬婷
指導教師:周長禮2023/2/52引言在管理科學、計算機科學、分子物理學和生物以及超大規(guī)模集成電路設計等科技領域中,存在著大量的組合優(yōu)化問題,其中的NP完全問題,其求解時間隨問題規(guī)模呈指數(shù)級增長,當規(guī)模稍大時就會因時間限制而失去可行性。以目前已成熟的數(shù)值計算理論和算法,或者根本無法求解,或者其求解的計算量是爆炸的。城市2425262728293031計算時間1s24s10m4.3h4.9d136d10.8a325a2023/2/53為此我們引入現(xiàn)今流行的智能算法,如遺傳算法,模擬退火算法,禁忌搜索算法,蟻群算法,和粒子群算法等。
我們前期所做的主要工作是參考了一些相關書目,組織了討論小組,對相關的算法進行了研究,并利用這些智能算法解決了TSP問題,下面我們就這些智能算法進行詳細介紹。2023/2/54遺傳算法是在70年代初期由美國密執(zhí)根大學的Holland教授發(fā)展起來的。1975年,Holland發(fā)表了第一批比較系統(tǒng)論述遺傳算法的專著《自然系統(tǒng)和人工系統(tǒng)的自適應》(AdaptationinNaturalandArtificialSystems)。遺傳算法主要借用生物進化中“適者生存”的規(guī)律揭示了大自然生物進化過程中的一個規(guī)律:最適合生存的個體往往產(chǎn)生了更大的后代群體。2023/2/55蟻群算法是由意大利學者A,Dofigo,M,Maniezzo等人于1992年通過模擬自然界中螞蟻集體尋食的行為而提出的一種基于種群的啟發(fā)式仿生進化算法。它采用分布式并行計算機制,易與其他方法結合,具有較強的魯棒性,但搜索時間長且易限入局部最優(yōu)解是其突出的缺點。ACO算法由一群簡單的人工螞蟻通過人工信息素(即一種分布式的數(shù)字信息,人工螞蟻利用該信息和問題相關的啟發(fā)式信息逐步構造問題的解,相當于真實蟻群的外激素,簡稱信息素)進行間接通訊,相互協(xié)作,從而求出問題的最優(yōu)解。2023/2/56禁忌搜索(TabuSearch簡稱TS)的思想最早由FredGlover(1986)提出,它是對局部鄰域搜索的一種擴展,是一種全局逐步尋優(yōu)算法,禁忌搜索算法在局部搜索過程中,使用一個“記憶”裝置,即禁忌表,驅(qū)使算法禁忌重復相同的搜索步驟,轉(zhuǎn)而搜索解空間的新區(qū)域,以逃離局部最優(yōu)。2023/2/57粒子群算法(ParticleSwarmOptimization,PSO)最早是由Eberhart和Kennedy于1995年提出,它的基本概念源于對鳥群覓食行為的研究。設想這樣一個場景:一群鳥在隨機搜尋食物,在這個區(qū)域里只有一塊食物,所有的鳥都不知道食物在哪里,但是它們知道當前的位置離食物還有多遠則找到食物的最優(yōu)策略最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。2023/2/58模擬退火算法是1982年KirkPatrick將退火思想引入組合優(yōu)化領域,提出一種解大規(guī)模組合優(yōu)化問題的算法,對NP完全組合優(yōu)化問題尤其有效。這源于固體的退火過程,即先將溫度加到很高,再緩慢降溫(即退火),使達到能量最低點。如果急速降溫(即為淬火)則不能達到最低點。2023/2/59TSP問題綜述旅行商問題是一個典型的NP完全問題。它可簡單地描述為:對于n個城市,它們之間的距離已知,一旅行商要從某一城市出發(fā)走遍所有的城市,且一個城市只能經(jīng)過一次,最后回到出發(fā)城市,問如何選擇路線可使所走過的路程最短。2023/2/510建立TSP問題的數(shù)學模型如下:2023/2/511遺傳算法的原理
遺傳算法通過模擬生物學的自然選擇和自然遺傳機制模擬生命進化的原理來尋求問題的最優(yōu)解,它的基本思想是:把問題的解表示成“染色體”,在執(zhí)行遺傳算法之前,隨機地給出一群初始“染色體”(種群)即假設解。然后,把這些假設解置于問題的“環(huán)境”中,并按適者生存的原則,選擇出較適應環(huán)境的“染色體”進行復制,再通過交叉、變異過程產(chǎn)生更適應環(huán)境的新一代“染色體”群。這樣,經(jīng)過一代一代的進化,最后收斂到最適應環(huán)境的一個“染色體”上,它就是問題的最優(yōu)解。2023/2/512遺傳算法的描述Step1初始化種群規(guī)模size、交叉概率Pc、變異概率Pm和迭代次數(shù)t。Step2隨機產(chǎn)生初始種群;計算初始種群的適應度。Step3根據(jù)一定的選擇策略選擇父體1和父體2。Step4產(chǎn)生一個0~1隨機數(shù)。Step5判斷P1<Pc是否成立,如果成立,把父體1和父體2按一定交叉方法生成子個體1和子個體2;否則把父體1和父體2作為新的子個體1和子個體2。2023/2/513
Step6判斷P2<Pm,如果成立把子個體1和子個體2按一定變異方法變異。Step7判斷產(chǎn)生子個體數(shù)是否等于種群規(guī)模,如果是則轉(zhuǎn)向Step8;否則轉(zhuǎn)向Step3。Step8評估種群的適應度;新產(chǎn)生的子代成為父代。Step9判斷是否滿足終止條件,如果滿足則終止;否則轉(zhuǎn)向Step3.2023/2/514遺傳算法流程圖2023/2/515遺傳算法的優(yōu)點與缺陷遺傳算法簡單、易于實現(xiàn),能夠并行化,具有強魯棒性和全局搜索能力。遺傳算法與其他啟發(fā)式算法有較好的兼容性,可以用其他的算法求初始解。缺點則表現(xiàn)為早熟現(xiàn)象、局部尋優(yōu)能力較差等。所以,一些常規(guī)遺傳算法并不一定是針對某一問題的最佳求解。2023/2/516禁忌搜索算法禁忌搜索算法是一種全局性鄰域搜索算法,模擬人類具有記憶功能的尋優(yōu)特征,是局部搜索算法的一種推廣,它通過局部鄰域搜索機制和相應的禁忌準則來避免迂回搜索,并通過破禁水平來釋放一些被禁忌的優(yōu)良狀態(tài),進而保證多樣化的有效探索,以最終實現(xiàn)全局優(yōu)化。2023/2/517禁忌搜索算法主要過程Stepl算法初始化,設置參數(shù),包括城市數(shù)目、禁忌長度、候選集長度和最大迭代步數(shù)等Step2生成初始解,作為迭代搜索的起點Step3根據(jù)上述初始解,按照一定規(guī)則生成鄰域,并在鄰域中選取元素生成候選集。Step4由于鄰域的相互性,將已經(jīng)搜過的解進行禁忌,避免迂回搜索,以跳出局部最優(yōu)2023/2/518Step5從候選集中選出未被禁忌表禁忌的當前局部最優(yōu)解,若此解優(yōu)于當前解,則用其替換當前解,成為最優(yōu)解Step6更新禁忌表(增添新的禁忌解或根據(jù)解禁準則,對滿足條件的解進行解禁)Step7判斷是否滿足終止條件(設為限定最大迭代步數(shù),或滿足所要求精度),若滿足,則輸出最優(yōu)解,終止算法;若不滿足,則將當前局部最優(yōu)解作為下次迭代的起點,轉(zhuǎn)Step3各種優(yōu)化算法解決TSP問題2023/2/519禁忌搜索算法優(yōu)點
從移動規(guī)則看,每次只與最優(yōu)點比較,而不與經(jīng)過點比較,故可以爬出局部最優(yōu)。選優(yōu)規(guī)則始終保持曾經(jīng)達到的最優(yōu)點,所以即使離開了全局最優(yōu)點也不會失去全局最優(yōu)性。終止規(guī)則不以達到局部最優(yōu)為終止規(guī)則,而以最大迭代次數(shù)、出現(xiàn)頻率限制或者目標值偏離程度為終止規(guī)則。2023/2/520蟻群算法
蟻群算法是通過模擬自然界中螞蟻集體尋徑的行為而提出的一種基于種群的啟發(fā)式仿生進化算法。它采用分布式并行計算機制,易與其他方法結合,具有較強的魯棒性。它由一群簡單的人工螞蟻通過人工信息素進行間接通訊,相互協(xié)作,從而求出問題的最優(yōu)解。2023/2/521蟻群算法描述Step1初始每條路徑上的信息激素濃度相等。Step2把m只螞蟻隨機地放置在n個城市上,并把已訪問的城市寫入禁忌表。Step3如果第k(k=1,2,……,m)只螞蟻還有未訪問的城市,則該只螞蟻根據(jù)決策選擇下一個城市(i是該螞蟻當前所在城市,j<(N-禁忌表),是一個由城市i到城市j之間的路徑長度和信息激素濃度構成的函數(shù)),把選擇的城市j寫入禁忌表,直到所有的城市訪問完。2023/2/522Step4計算k(k=1,2,……,m)條路徑的路徑長度,選出本次最優(yōu)路徑。Step5根據(jù)本次螞蟻的訪問情況更新每一條邊上的信息激素濃度,清空禁忌表。Step6判斷是否滿足結束條件,如果不滿足,轉(zhuǎn)到Step2;否則結束。下圖為流程圖2023/2/5232023/2/524蟻群算法的主要特點(1)分布式計算、正反饋機制和貪婪式搜索相結合;(2)具有很強的并行性;(3)更好的可擴充性;(4)概率型的通用全局優(yōu)化方法;(5)不依賴于優(yōu)化本身的嚴格數(shù)學性質(zhì),諸如連續(xù)性、可導性;各種優(yōu)化算法解決TSP問題2023/2/525粒子群算法
PSO算法是將群體中的每個個體視為多維搜索空間中一個沒有質(zhì)量和體積的粒子(點),這些粒子在搜索空間中以一定的速度飛行,并根據(jù)粒子本身的飛行經(jīng)驗以及同伴的飛行經(jīng)驗對自己的飛行速度進行動態(tài)調(diào)整,即每個粒子通過統(tǒng)計迭代過程中自身的最優(yōu)值和群體的最優(yōu)值來不斷地修正自己的前進方向和速度大小,從而形成群體尋優(yōu)的正反饋機制。PSO算法就是這樣依據(jù)每個粒子對環(huán)境的適應度將個體逐步移到較優(yōu)的區(qū)域,并最終搜索、尋找到問題的最優(yōu)解。2023/2/526粒子群算法的數(shù)學描述
在D維的搜索空間中,有隨機分布的m個粒子組成的一個初始粒子群,每個粒子有各自的位置和速度。如第i個粒子的位置表示為一個D維的向量,速度也是一個D維的向量,記為。每個粒子記住自己在迭代過程中找到的最優(yōu)位置,記為,整個粒子群迄今為止搜索到的最優(yōu)位置為全局最優(yōu)解記。這樣的尋優(yōu)為局部PSO算法,經(jīng)過一定的迭代后,改用全局最優(yōu)解,即全局PSO算法進行迭代以加快收斂。2023/2/527可用下面的公式來表示粒子每輪的更新行為:
(2.1)(2.2)其中為粒子速度,為粒子位置,C1,C2稱為學習因子或加速常量,通常在間取值,C1為調(diào)節(jié)粒子飛向自身最好位置的步長,C2為調(diào)節(jié)粒子向全局最好位置飛行步長;r1,r2是(0,1)區(qū)間內(nèi)兩個隨機正數(shù),為個體意識(個體最佳解位置),為群體最佳解位置.為慣性權重,使粒子保持運動慣性,控制前一速度對當前速度的影響;t為飛行的次數(shù)。2023/2/528粒子群算法的流程如下:Stepl:初始化,設定加速常數(shù)C1和C2,最大進化代數(shù)將當前進化代數(shù)置為t=1,在定義空間中隨機產(chǎn)生m個粒子X1,X2,…,Xm,組成初始種群X(t),隨機產(chǎn)生各粒子初速度V1,V2,…,VS組成位移變化矩陣V(t)。Step2:計算種群中所有粒子的適應值,初始化每粒子pbest為當前粒子,設定種群的gbest為當前種群的最優(yōu)粒子。2023/2/529Step3:種群x(t)演化,對種群中的每一個粒子:(1)按(2.1),(2.2)式更新粒子的位置和速度。(2)計算粒子的適應值。(3)比較粒子的適應值和自身的最優(yōu)值pbest。如果當前值比pbest更優(yōu),則更新pbest為當前值,并更新pbest位置到n維空間中的當前位置。(4)比較粒子適應值與種群最優(yōu)值。如果當前值比gbest更優(yōu),則更新gbest為當前種群最優(yōu)粒子。Step4:檢查結束條件,若滿足,則結束尋優(yōu);否則,t=t+1,轉(zhuǎn)至Step2.。結束條件為尋優(yōu)達到最大進化代數(shù),或評價值小于給定精度。2023/2/530
模擬退火算法
模擬退火算法是80年代發(fā)展起來的一種用于求解大規(guī)模優(yōu)化問題的隨機搜索算法,它以優(yōu)化問題求解過程與物理系統(tǒng)退火過程之間的相似性為基礎;優(yōu)化的目標函數(shù)相當于金屬的內(nèi)能;優(yōu)化問題的自變量組合狀態(tài)空間相當于金屬的內(nèi)能狀態(tài)空間;問題的求解過程就是找一個組合狀態(tài),使目標函數(shù)值最小。利用Metropolis準則并適當?shù)乜刂茰囟鹊南陆颠^程實現(xiàn)模擬退火,從而達到在多項式時間內(nèi)求解全局優(yōu)化問題的目標。2023/2/531模擬退火算法描述
Step1初始化:初始溫度T(充分大),初始解狀態(tài)S(是算法迭代的起點),每個T值的迭代次數(shù)Lstep2對k=1,……,L做第(3)至第6步:step3產(chǎn)生新解S′Step4計算增量Δt′=C(S′)-C(S),其中C(S)為評價函數(shù)2023/2/532Step5若Δt′<0則接受S′作為新的當前解,否則以概率exp(-Δt′/T)接受S′作為新的當前解.Step6如果滿足終止條件則輸出當前解作為最優(yōu)解,結束程序。終止條件通常取為連續(xù)若干個新解都沒有被接受時終止算法。step7T逐漸減少,且T->0,然后轉(zhuǎn)第2步。2023/2/533模擬退火算法的優(yōu)缺點:
與以往的近似算法相比,模擬退火算法具有描述簡單、使用靈活、運用廣泛、運行效率高和較少受到初始條件約束等優(yōu)點。2023/2/534各種算法應用TSP問題及結果分析
我們將各種智能算法應用于解決TSP問題,下面我們以30個城市的TSP問題為例進行結果分析下表為30個城市的TSP仿真結果,其中30個城市的坐標如下:
[x,y]=[4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;443
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 無人機產(chǎn)業(yè)前景及投資機會報告
- 救災物資儲備與調(diào)度管理方案
- 水利設施錨桿施工合同
- 水廠國際合作項目合同
- 停車場物業(yè)服務合同模板
- 課程設計牛頭刨床方案3
- 空竹課程設計與定位
- 免租金食堂租賃合同
- 電力工程項目總監(jiān)招聘協(xié)議
- 2024裝修合同簽訂的注意事項
- DB11T 2250-2024重點用能單位能耗在線監(jiān)測系統(tǒng)接入技術規(guī)范
- (必會)企業(yè)人力資源管理師(三級)近年考試真題題庫(含答案解析)
- 電力工程投標方案(技術標)
- 2024年職業(yè)院校技能大賽數(shù)字化裝備制造技術賽項理論題庫(備賽500題)
- 《中外歷史綱要》(下)
- 正畸提前結束協(xié)議書
- 電話銷售人員聘用合同
- 2024年山西電力職業(yè)技術學院單招職業(yè)適應性測試題庫匯編
- 工業(yè)機器人技術分析報告
- 故事繪本愚公移山
- 中國文化概論-第三章中國傳統(tǒng)服飾文化
評論
0/150
提交評論