1、2022/9/81數(shù)學(xué)建模常用智能算法 及其Matlab實(shí)現(xiàn)負(fù) 責(zé) 人：胡 丹 成 員：袁莉莉 王 霖 侯金靈 馬婷 指導(dǎo)教師: 周 長 禮2022/9/82引言在管理科學(xué)、計算機(jī)科學(xué)、分子物理學(xué)和生物以及超大規(guī)模集成電路設(shè)計等科技領(lǐng)域中，存在著大量的組合優(yōu)化問題，其中的NP完全問題，其求解時間隨問題規(guī)模呈指數(shù)級增長，當(dāng)規(guī)模稍大時就會因時間限制而失去可行性。以目前已成熟的數(shù)值計算理論和算法，或者根本無法求解，或者其求解的計算量是爆炸的。城市2425262728293031計算時間1s24s10m4.3h4.9d136d10.8a325a2022/9/83為此我們引入現(xiàn)今流行的智能算法，如遺傳算

2、法，模擬退火算法，禁忌搜索算法，蟻群算法，和粒子群算法等。 我們前期所做的主要工作是參考了一些相關(guān)書目，組織了討論小組，對相關(guān)的算法進(jìn)行了研究，并利用這些智能算法解決了TSP問題，下面我們就這些智能算法進(jìn)行詳細(xì)介紹。2022/9/84遺傳算法是在70年代初期由美國密執(zhí)根大學(xué)的Holland教授發(fā)展起來的。1975年，Holland發(fā)表了第一批比較系統(tǒng)論述遺傳算法的專著自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)（Adaptation in Natural and Artificial Systems）。遺傳算法主要借用生物進(jìn)化中“適者生存”的規(guī)律揭示了大自然生物進(jìn)化過程中的一個規(guī)律：最適合生存的個體往往產(chǎn)生了更

3、大的后代群體。2022/9/85蟻群算法是由意大利學(xué)者A，Dofigo，M，Maniezzo 等人于1992 年通過模擬自然界中螞蟻集體尋食的行為而提出的一種基于種群的啟發(fā)式仿生進(jìn)化算法。它采用分布式并行計算機(jī)制,易與其他方法結(jié)合,具有較強(qiáng)的魯棒性,但搜索時間長且易限入局部最優(yōu)解是其突出的缺點(diǎn)。A C O 算法由一群簡單的人工螞蟻通過人工信息素(即一種分布式的數(shù)字信息,人工螞蟻利用該信息和問題相關(guān)的啟發(fā)式信息逐步構(gòu)造問題的解， 相當(dāng)于真實(shí)蟻群的外激素， 簡稱信息素)進(jìn)行間接通訊，相互協(xié)作，從而求出問題的最優(yōu)解。2022/9/86禁忌搜索（Tabu Search 簡稱TS）的思想最早由FredG

4、lover(1986)提出，它是對局部鄰域搜索的一種擴(kuò)展，是一種全局逐步尋優(yōu)算法，禁忌搜索算法在局部搜索過程中，使用一個“記憶”裝置，即禁忌表，驅(qū)使算法禁忌重復(fù)相同的搜索步驟，轉(zhuǎn)而搜索解空間的新區(qū)域，以逃離局部最優(yōu)。2022/9/87粒子群算法（ Particle Swarm Optimization, PSO）最早是由Eberhart和Kennedy于1995年提出，它的基本概念源于對鳥群覓食行為的研究。設(shè)想這樣一個場景:一群鳥在隨機(jī)搜尋食物，在這個區(qū)域里只有一塊食物，所有的鳥都不知道食物在哪里，但是它們知道當(dāng)前的位置離食物還有多遠(yuǎn)則找到食物的最優(yōu)策略最簡單有效的就是搜尋目前離食物最近的鳥的

5、周圍區(qū)域 。 2022/9/810建立TSP問題的數(shù)學(xué)模型如下：2022/9/811遺傳算法的原理 遺傳算法通過模擬生物學(xué)的自然選擇和自然遺傳機(jī)制模擬生命進(jìn)化的原理來尋求問題的最優(yōu)解，它的基本思想是：把問題的解表示成“染色體”，在執(zhí)行遺傳算法之前，隨機(jī)地給出一群初始“染色體”(種群)即假設(shè)解。然后，把這些假設(shè)解置于問題的“環(huán)境”中，并按適者生存的原則，選擇出較適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制，再通過交叉、變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群。這樣，經(jīng)過一代一代的進(jìn)化，最后收斂到最適應(yīng)環(huán)境的一個“染色體”上，它就是問題的最優(yōu)解。2022/9/812遺傳算法的描述Step 1 初始化種群規(guī)模si

6、ze、交叉概率Pc、變異概率Pm和迭代次數(shù)t。Step 2 隨機(jī)產(chǎn)生初始種群；計算初始種群的適應(yīng)度。Step 3 根據(jù)一定的選擇策略選擇父體1和父體2。Step 4 產(chǎn)生一個01隨機(jī)數(shù)。Step 5 判斷P1Pc是否成立，如果成立，把父體1和父體2按一定交叉方法生成子個體1和子個體2；否則把父體1和父體2作為新的子個體1和子個體2。2022/9/816禁忌搜索算法禁忌搜索算法是一種全局性鄰域搜索算法，模擬人類具有記憶功能的尋優(yōu)特征，是局部搜索算法的一種推廣，它通過局部鄰域搜索機(jī)制和相應(yīng)的禁忌準(zhǔn)則來避免迂回搜索，并通過破禁水平來釋放一些被禁忌的優(yōu)良狀態(tài)，進(jìn)而保證多樣化的有效探索，以最終實(shí)現(xiàn)全局優(yōu)

7、化 。2022/9/817禁忌搜索算法主要過程Step l 算法初始化，設(shè)置參數(shù)，包括城市數(shù)目、禁忌長度、候選集長度和最大迭代步數(shù)等Step 2 生成初始解，作為迭代搜索的起點(diǎn) Step 3 根據(jù)上述初始解，按照一定規(guī)則生成鄰域，并在鄰域中選取元素生成候選集。Step 4 由于鄰域的相互性，將已經(jīng)搜過的解進(jìn)行禁忌，避免迂回搜索，以跳出局部最優(yōu)2022/9/818Step 5 從候選集中選出未被禁忌表禁忌的當(dāng)前局部最優(yōu)解 ，若此解優(yōu)于當(dāng)前解，則用其替換當(dāng)前解，成為最優(yōu)解Step 6 更新禁忌表（增添新的禁忌解或 根據(jù)解禁準(zhǔn)則，對滿足條件的解進(jìn)行解禁）Step 7 判斷是否滿足終止條件(設(shè)為限定最

8、大迭代步數(shù)，或滿足所要求精度)，若滿足，則輸出最優(yōu)解，終止算法；若不滿足，則將當(dāng)前局部最優(yōu)解作為下次迭代的起點(diǎn)，轉(zhuǎn)Step 3各種優(yōu)化算法解決TSP問題2022/9/819禁忌搜索算法優(yōu)點(diǎn) 從移動規(guī)則看，每次只與最優(yōu)點(diǎn)比較，而不與經(jīng)過點(diǎn)比較，故可以爬出局部最優(yōu)。選優(yōu)規(guī)則始終保持曾經(jīng)達(dá)到的最優(yōu)點(diǎn)，所以即使離開了全局最優(yōu)點(diǎn)也不會失去全局最優(yōu)性。終止規(guī)則不以達(dá)到局部最優(yōu)為終止規(guī)則，而以最大迭代次數(shù)、出現(xiàn)頻率限制或者目標(biāo)值偏離程度為終止規(guī)則。2022/9/8232022/9/824蟻群算法的主要特點(diǎn) (1)分布式計算、正反饋機(jī)制和貪婪式搜索相結(jié)合；(2)具有很強(qiáng)的并行性；(3)更好的可擴(kuò)充性；(4)概

9、率型的通用全局優(yōu)化方法；(5)不依賴于優(yōu)化本身的嚴(yán)格數(shù)學(xué)性質(zhì)，諸如連續(xù)性、可導(dǎo)性；各種優(yōu)化算法解決TSP問題2022/9/825粒子群算法 PSO算法是將群體中的每個個體視為多維搜索空間中一個沒有質(zhì)量和體積的粒子(點(diǎn))，這些粒子在搜索空間中以一定的速度飛行，并根據(jù)粒子本身的飛行經(jīng)驗(yàn)以及同伴的飛行經(jīng)驗(yàn)對自己的飛行速度進(jìn)行動態(tài)調(diào)整，即每個粒子通過統(tǒng)計迭代過程中自身的最優(yōu)值和群體的最優(yōu)值來不斷地修正自己的前進(jìn)方向和速度大小，從而形成群體尋優(yōu)的正反饋機(jī)制。PSO算法就是這樣依據(jù)每個粒子對環(huán)境的適應(yīng)度將個體逐步移到較優(yōu)的區(qū)域，并最終搜索、尋找到問題的最優(yōu)解。2022/9/826粒子群算法的數(shù)學(xué)描述 在D

10、維的搜索空間中，有隨機(jī)分布的m個粒子組成的一個初始粒子群，每個粒子有各自的位置和速度。如第i個粒子的位置表示為一個D維的向量 ,速度也是一個D 維的向量，記為 。每個粒子記住自己在迭代過程中找到的最優(yōu)位置，記為 ，整個粒子群迄今為止搜索到的最優(yōu)位置為全局最優(yōu)解記 。 這樣的尋優(yōu)為局部PSO算法，經(jīng)過一定的迭代后，改用全局最優(yōu)解，即全局PSO算法進(jìn)行迭代以加快收斂。 2022/9/827可用下面的公式來表示粒子每輪的更新行為： (2.1) (2.2) 其中 為粒子速度， 為粒子位置，C1，C2稱為學(xué)習(xí)因子或加速常量，通常在 間取值， C1為調(diào)節(jié)粒子飛向自身最好位置的步長, C2 為調(diào)節(jié)粒子向全局

11、最好位置飛行步長；r1，r2 是（0，1）區(qū)間內(nèi)兩個隨機(jī)正數(shù)， 為個體意識（個體最佳解位置）， 為群體最佳解位置. 為慣性權(quán)重，使粒子保持運(yùn)動慣性，控制前一速度對當(dāng)前速度的影響; t 為飛行的次數(shù)。2022/9/828粒子群算法的流程如下：Step l： 初始化，設(shè)定加速常數(shù)C1和C2，最大進(jìn)化代數(shù) 將當(dāng)前進(jìn)化代數(shù)置為 t = 1 ，在定義空間 中隨機(jī)產(chǎn)生m個粒子X1,X2,Xm，組成初始種群X(t),隨機(jī)產(chǎn)生各粒子初速度V1，V2,VS組成位移變化矩陣V(t)。Step 2： 計算種群中所有粒子的適應(yīng)值，初始化每粒子pbest為當(dāng)前粒子，設(shè)定種群的gbest為當(dāng)前種群的最優(yōu)粒子。2022/9

12、/829Step 3：種群x(t)演化，對種群中的每一個粒子：(1) 按(2.1),(2.2)式更新粒子的位置和速度。(2) 計算粒子的適應(yīng)值。(3) 比較粒子的適應(yīng)值和自身的最優(yōu)值pbest。如果當(dāng)前值比pbest更優(yōu)，則更新pbest為當(dāng)前值，并更新pbest位置到n維空間中的當(dāng)前位置。(4) 比較粒子適應(yīng)值與種群最優(yōu)值。如果當(dāng)前值比gbest更優(yōu)，則更新gbest為當(dāng)前種群最優(yōu)粒子。 Step 4： 檢查結(jié)束條件，若滿足，則結(jié)束尋優(yōu)；否則，t = t + 1，轉(zhuǎn)至Step 2.。結(jié)束條件為尋優(yōu)達(dá)到最大進(jìn)化代數(shù) ，或評價值小于給定精度 。2022/9/830 模擬退火算法 模擬退火算法是8

13、0年代發(fā)展起來的一種用于求解大規(guī)模優(yōu)化問題的隨機(jī)搜索算法，它以優(yōu)化問題求解過程與物理系統(tǒng)退火過程之間的相似性為基礎(chǔ)；優(yōu)化的目標(biāo)函數(shù)相當(dāng)于金屬的內(nèi)能；優(yōu)化問題的自變量組合狀態(tài)空間相當(dāng)于金屬的內(nèi)能狀態(tài)空間；問題的求解過程就是找一個組合狀態(tài)，使目標(biāo)函數(shù)值最小。利用Metropolis準(zhǔn)則并適當(dāng)?shù)乜刂茰囟鹊南陆颠^程實(shí)現(xiàn)模擬退火，從而達(dá)到在多項(xiàng)式時間內(nèi)求解全局優(yōu)化問題的目標(biāo) 。2022/9/831模擬退火算法描述Step 1 初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點(diǎn))， 每個T值的迭代次數(shù)L step 2 對k=1，L做第(3)至第6步： step 3 產(chǎn)生新解S Step 4 計算

14、增量t=C(S)-C(S)，其中C(S)為評價函數(shù) 2022/9/834各種算法應(yīng)用TSP問題及結(jié)果分析 我們將各種智能算法應(yīng)用于解決TSP問題，下面我們以30個城市的TSP問題為例進(jìn)行結(jié)果分析下表為30個城市的TSP仿真結(jié)果，其中30個城市的坐標(biāo)如下： x,y=41 94;37 84;54 67;25 62;7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 54;22 60;83 46;91 38;25 38;24 42;58 69;71 71;74 78;87 76;18 40;13 40;82 7;62 32;58 35;45 21;41 26;44

15、35;4 502022/9/835實(shí)驗(yàn)環(huán)境：MATLAB 7.0 實(shí)驗(yàn)方法：在算法中設(shè)置計數(shù)器，當(dāng)解轉(zhuǎn)移迭 代次數(shù)達(dá)到計數(shù)器規(guī)定的值時，無須考慮算法的終止條件即刻終止算法觀察實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)結(jié)果統(tǒng)計。設(shè)置算法參數(shù)：遺傳算法中初始種群的大小為100，交叉概率為0.8。變異概率為0.1。在蟻群算法中信息素重要程度的參數(shù), 啟發(fā)式因子重要程度的參數(shù), 信息素蒸發(fā)系數(shù), 信息素增加強(qiáng)度系數(shù).禁忌算法中禁忌長度為150，保留前100個最好候選解。2022/9/836圖3.1 30個城市坐標(biāo)位置圖2022/9/837算法迭代次數(shù)平均解最好解方差遺傳算法500476.90924437.1531227.217819蟻群算法200428.88425.6497.75151禁忌搜索算法1000461.3991423.949785.8090模擬退火算法100423.9725423.740609/838以下是