數(shù)學建模常用智能算法與Matlab實現(xiàn)

1、2021-11-231負 責 人：胡 丹 成 員：袁莉莉 王 霖 侯金靈 馬婷 指導教師: 周 長 禮2021-11-232l在管理科學、計算機科學、分子物理學和生物以及超大規(guī)在管理科學、計算機科學、分子物理學和生物以及超大規(guī)模集成電路設計等科技領域中，存在著大量的組合優(yōu)化問模集成電路設計等科技領域中，存在著大量的組合優(yōu)化問題，其中的題，其中的NP完全問題，其求解時間隨問題規(guī)模呈指數(shù)完全問題，其求解時間隨問題規(guī)模呈指數(shù)級增長，當規(guī)模稍大時就會因時間限制而失去可行性。以級增長，當規(guī)模稍大時就會因時間限制而失去可行性。以目前已成熟的數(shù)值計算理論和算法，或者根本無法求解，目前已成熟的數(shù)值計算理論和算

2、法，或者根本無法求解，或者其求解的計算量是爆炸的或者其求解的計算量是爆炸的。城市城市2425262728293031計算時間1s24s10m4.3h4.9d136d10.8a325a2021-11-233為此我們引入現(xiàn)今流行的智能算法，如遺傳算法，模擬退火算法，禁忌搜索算法，蟻群算法，和粒子群算法等。 我們前期所做的主要工作是參考了一些相關書目，組織了討論小組，對相關的算法進行了研究，并利用這些智能算法解決了TSP問題，下面我們就這些智能算法進行詳細介紹。2021-11-234l遺傳算法是在遺傳算法是在70年代初期由美國密執(zhí)根大學年代初期由美國密執(zhí)根大學的的Holland教授發(fā)展起來的。教授發(fā)

3、展起來的。1975年，年，Holland發(fā)表了第一批比較系統(tǒng)論述遺傳算發(fā)表了第一批比較系統(tǒng)論述遺傳算法的專著法的專著自然系統(tǒng)和人工系統(tǒng)的自適應自然系統(tǒng)和人工系統(tǒng)的自適應（Adaptation in Natural and Artificial Systems）。遺傳算法主要借用生物進化中）。遺傳算法主要借用生物進化中“適者生存適者生存”的規(guī)律揭示了大自然生物進化的規(guī)律揭示了大自然生物進化過程中的一個規(guī)律：最適合生存的個體往往過程中的一個規(guī)律：最適合生存的個體往往產(chǎn)生了更大的后代群體。產(chǎn)生了更大的后代群體。2021-11-235l蟻群算法是由意大利學者蟻群算法是由意大利學者A，Dofigo，M，

4、Maniezzo 等人于等人于1992 年通過模擬自然界中螞蟻年通過模擬自然界中螞蟻集體尋食的行為而提出的一種基于種群的啟發(fā)式集體尋食的行為而提出的一種基于種群的啟發(fā)式仿生進化算法。它采用分布式并行計算機制仿生進化算法。它采用分布式并行計算機制,易與易與其他方法結合其他方法結合,具有較強的魯棒性具有較強的魯棒性,但搜索時間長但搜索時間長且易限入局部最優(yōu)解是其突出的缺點。且易限入局部最優(yōu)解是其突出的缺點。A C O 算算法由一群簡單的人工螞蟻通過人工信息素法由一群簡單的人工螞蟻通過人工信息素(即一種即一種分布式的數(shù)字信息分布式的數(shù)字信息,人工螞蟻利用該信息和問題相人工螞蟻利用該信息和問題相關的啟

5、發(fā)式信息逐步構造問題的解，關的啟發(fā)式信息逐步構造問題的解， 相當于真實相當于真實蟻群的外激素，蟻群的外激素， 簡稱信息素簡稱信息素)進行間接通訊，相進行間接通訊，相互協(xié)作，從而求出問題的最優(yōu)解?；f(xié)作，從而求出問題的最優(yōu)解。2021-11-236l禁忌搜索（禁忌搜索（Tabu Search 簡稱簡稱TS）的思想最）的思想最早由早由FredGlover(1986)提出，它是對局部鄰域提出，它是對局部鄰域搜索的一種擴展，是一種全局逐步尋優(yōu)算法，搜索的一種擴展，是一種全局逐步尋優(yōu)算法，禁忌搜索算法在局部搜索過程中，使用一個禁忌搜索算法在局部搜索過程中，使用一個“記憶記憶”裝置，即禁忌表，驅使算法禁忌

6、重復裝置，即禁忌表，驅使算法禁忌重復相同的搜索步驟，轉而搜索解空間的新區(qū)域，相同的搜索步驟，轉而搜索解空間的新區(qū)域，以逃離局部最優(yōu)。以逃離局部最優(yōu)。2021-11-237l粒子群算法（粒子群算法（ Particle Swarm Optimization, PSO）最早是由）最早是由Eberhart和和Kennedy于于1995年提出，它的基本概念源于對鳥群覓食行為的年提出，它的基本概念源于對鳥群覓食行為的研究。設想這樣一個場景研究。設想這樣一個場景:一群鳥在隨機搜尋一群鳥在隨機搜尋食物，在這個區(qū)域里只有一塊食物，所有的鳥食物，在這個區(qū)域里只有一塊食物，所有的鳥都不知道食物在哪里，但是它們知道當

7、前的位都不知道食物在哪里，但是它們知道當前的位置離食物還有多遠則找到食物的最優(yōu)策略最簡置離食物還有多遠則找到食物的最優(yōu)策略最簡單有效的就是搜尋目前離食物最近的鳥的周圍單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域區(qū)域 。 2021-11-238l模擬退火算法是模擬退火算法是1982年年KirkPatrick將退火思將退火思想引入組合優(yōu)化領域，提出一種解大規(guī)模組合想引入組合優(yōu)化領域，提出一種解大規(guī)模組合優(yōu)化問題的算法，對優(yōu)化問題的算法，對NP完全組合優(yōu)化問題尤完全組合優(yōu)化問題尤其有效。這源于固體的退火過程，即先將溫度其有效。這源于固體的退火過程，即先將溫度加到很高加到很高,再緩慢降溫再緩慢降溫(即

8、退火即退火)，使達到能量最，使達到能量最低點。如果急速降溫低點。如果急速降溫(即為淬火即為淬火)則不能達到最則不能達到最低點低點。2021-11-239l旅行商問題是一個典型的旅行商問題是一個典型的NP完全問題。它可完全問題。它可簡單地描述為：對于簡單地描述為：對于n個城市，它們之間的距個城市，它們之間的距離已知離已知,一旅行商要從某一城市出發(fā)走遍所有一旅行商要從某一城市出發(fā)走遍所有的城市，且一個城市只能經(jīng)過一次的城市，且一個城市只能經(jīng)過一次,最后回到最后回到出發(fā)城市，問如何選擇路線可使所走過的路程出發(fā)城市，問如何選擇路線可使所走過的路程最短。最短。 2021-11-2310l建立建立TSP問

9、題的數(shù)學模型如下：問題的數(shù)學模型如下：jiijijxdzminjiijx1ViVjxjiij, 1VSSxSjiij, 1,Vjixij,1 , 02021-11-2311 遺傳算法通過模擬生物學的自然選擇和自然遺傳機制遺傳算法通過模擬生物學的自然選擇和自然遺傳機制模擬生命進化的原理來尋求問題的最優(yōu)解，它的基本模擬生命進化的原理來尋求問題的最優(yōu)解，它的基本思想是：把問題的解表示成思想是：把問題的解表示成“染色體染色體”，在執(zhí)行遺傳，在執(zhí)行遺傳算法之前，隨機地給出一群初始算法之前，隨機地給出一群初始“染色體染色體”(種群種群)即假即假設解。然后，把這些假設解置于問題的設解。然后，把這些假設解置于

10、問題的“環(huán)境環(huán)境”中，中，并按適者生存的原則，選擇出較適應環(huán)境的并按適者生存的原則，選擇出較適應環(huán)境的“染色體染色體”進行復制，再通過交叉、變異過程產(chǎn)生更適應環(huán)境的進行復制，再通過交叉、變異過程產(chǎn)生更適應環(huán)境的新一代新一代“染色體染色體”群。這樣，經(jīng)過一代一代的進化，群。這樣，經(jīng)過一代一代的進化，最后收斂到最適應環(huán)境的一個最后收斂到最適應環(huán)境的一個“染色體染色體”上，它就是上，它就是問題的最優(yōu)解。問題的最優(yōu)解。2021-11-2312lStep 1 初始化種群規(guī)模初始化種群規(guī)模size、交叉概率、交叉概率Pc、變、變異概率異概率Pm和迭代次數(shù)和迭代次數(shù)t。lStep 2 隨機產(chǎn)生初始種群；計算

11、初始種群的適隨機產(chǎn)生初始種群；計算初始種群的適應度。應度。lStep 3 根據(jù)一定的選擇策略選擇父體根據(jù)一定的選擇策略選擇父體1和父體和父體2。lStep 4 產(chǎn)生一個產(chǎn)生一個01隨機數(shù)。隨機數(shù)。lStep 5 判斷判斷P1Pc是否成立，如果成立，把父是否成立，如果成立，把父體體1和父體和父體2按一定交叉方法生成子個體按一定交叉方法生成子個體1和子個和子個體體2；否則把父體；否則把父體1和父體和父體2作為新的子個體作為新的子個體1和子和子個體個體2。2021-11-2313Step 6 Step 6 判斷判斷P2PmP2Pm，如果成立把子個體，如果成立把子個體1 1和子個體和子個體2 2按按一

12、定變異方法變異。一定變異方法變異。Step 7 Step 7 判斷產(chǎn)生子個體數(shù)是否等于種群規(guī)模，如判斷產(chǎn)生子個體數(shù)是否等于種群規(guī)模，如 果是則轉向果是則轉向Step8Step8；否則轉向；否則轉向Step3Step3。Step 8 Step 8 評估種群的適應度；新產(chǎn)生的子代成為評估種群的適應度；新產(chǎn)生的子代成為 父代。父代。Step 9 Step 9 判斷是否滿足終止條件，如果滿足則終止；否判斷是否滿足終止條件，如果滿足則終止；否 則轉向則轉向Step 3Step 32021-11-2314遺傳算法流程圖2021-11-2315l遺傳算法簡單、易于實現(xiàn)，能夠并行化，遺傳算法簡單、易于實現(xiàn)，能

13、夠并行化，具有強魯棒性和全局搜索能力。遺傳算法具有強魯棒性和全局搜索能力。遺傳算法與其他啟發(fā)式算法有較好的兼容性，可以與其他啟發(fā)式算法有較好的兼容性，可以用其他的算法求初始解。用其他的算法求初始解。l缺點則表現(xiàn)為早熟現(xiàn)象、局部尋優(yōu)能力較缺點則表現(xiàn)為早熟現(xiàn)象、局部尋優(yōu)能力較差等。所以，一些常規(guī)遺傳算法并不一定差等。所以，一些常規(guī)遺傳算法并不一定是針對某一問題的最佳求解。是針對某一問題的最佳求解。2021-11-2316l禁忌搜索算法是一種全局性鄰域搜索算法，模禁忌搜索算法是一種全局性鄰域搜索算法，模擬人類具有記憶功能的尋優(yōu)特征，是局部搜索擬人類具有記憶功能的尋優(yōu)特征，是局部搜索算法的一種推廣，它

14、通過局部鄰域搜索機制和算法的一種推廣，它通過局部鄰域搜索機制和相應的禁忌準則來避免迂回搜索，并通過破禁相應的禁忌準則來避免迂回搜索，并通過破禁水平來釋放一些被禁忌的優(yōu)良狀態(tài)，進而保證水平來釋放一些被禁忌的優(yōu)良狀態(tài)，進而保證多樣化的有效探索，以最終實現(xiàn)全局優(yōu)化多樣化的有效探索，以最終實現(xiàn)全局優(yōu)化 。2021-11-2317lStep l 算法初始化，設置參數(shù)，包括城市數(shù)算法初始化，設置參數(shù)，包括城市數(shù)目、禁忌長度、候選集長度和最大迭代步數(shù)等目、禁忌長度、候選集長度和最大迭代步數(shù)等lStep 2 生成初始解，作為迭代搜索的起點生成初始解，作為迭代搜索的起點 lStep 3 根據(jù)上述初始解，按照一定

15、規(guī)則生成根據(jù)上述初始解，按照一定規(guī)則生成鄰域，并在鄰域中選取元素生成候選集。鄰域，并在鄰域中選取元素生成候選集。lStep 4 由于鄰域的相互性，將已經(jīng)搜過的解由于鄰域的相互性，將已經(jīng)搜過的解進行禁忌，避免迂回搜索，以跳出局部最優(yōu)進行禁忌，避免迂回搜索，以跳出局部最優(yōu)2021-11-2318lStep 5 從候選集中選出未被禁忌表禁忌的當從候選集中選出未被禁忌表禁忌的當前局部最優(yōu)解前局部最優(yōu)解 ，若此解優(yōu)于當前解，則用其替，若此解優(yōu)于當前解，則用其替換當前解，成為最優(yōu)解換當前解，成為最優(yōu)解lStep 6 更新禁忌表（增添新的禁忌解或更新禁忌表（增添新的禁忌解或 根據(jù)根據(jù)解禁準則，對滿足條件的解

16、進行解禁）解禁準則，對滿足條件的解進行解禁）lStep 7 判斷是否滿足終止條件判斷是否滿足終止條件(設為限定最大設為限定最大迭代步數(shù)，或滿足所要求精度迭代步數(shù)，或滿足所要求精度)，若滿足，則，若滿足，則輸出最優(yōu)解，終止算法；若不滿足，則將當前輸出最優(yōu)解，終止算法；若不滿足，則將當前局部最優(yōu)解作為下次迭代的起點，轉局部最優(yōu)解作為下次迭代的起點，轉Step 3l各種優(yōu)化算法解決各種優(yōu)化算法解決TSP問題問題2021-11-2319l 從移動規(guī)則看，每次只與最優(yōu)點比較，而不與從移動規(guī)則看，每次只與最優(yōu)點比較，而不與經(jīng)過點比較，故可以爬出局部最優(yōu)。經(jīng)過點比較，故可以爬出局部最優(yōu)。l選優(yōu)規(guī)則始終保持曾

17、經(jīng)達到的最優(yōu)點，所以即選優(yōu)規(guī)則始終保持曾經(jīng)達到的最優(yōu)點，所以即使離開了全局最優(yōu)點也不會失去全局最優(yōu)性。使離開了全局最優(yōu)點也不會失去全局最優(yōu)性。l終止規(guī)則不以達到局部最優(yōu)為終止規(guī)則，而以終止規(guī)則不以達到局部最優(yōu)為終止規(guī)則，而以最大迭代次數(shù)、出現(xiàn)頻率限制或者目標值偏離最大迭代次數(shù)、出現(xiàn)頻率限制或者目標值偏離程度為終止規(guī)則。程度為終止規(guī)則。2021-11-2320 蟻群算法是通過模擬自然界中螞蟻集體尋徑的蟻群算法是通過模擬自然界中螞蟻集體尋徑的行為而提出的一種基于種群的啟發(fā)式仿生進化行為而提出的一種基于種群的啟發(fā)式仿生進化算法。它采用分布式并行計算機制算法。它采用分布式并行計算機制,易與其他易與其他

18、方法結合方法結合,具有較強的魯棒性具有較強的魯棒性 。它由一群簡單。它由一群簡單的人工螞蟻通過人工信息素進行間接通訊，相的人工螞蟻通過人工信息素進行間接通訊，相互協(xié)作，從而求出問題的最優(yōu)解。互協(xié)作，從而求出問題的最優(yōu)解。2021-11-2321lStep 1 初始每條路徑上的信息激素濃度相等。初始每條路徑上的信息激素濃度相等。 lStep 2 把把m只螞蟻隨機地放置在只螞蟻隨機地放置在n個城市上個城市上,并并把已訪問的城市寫入禁忌表。把已訪問的城市寫入禁忌表。 lStep 3 如果第如果第 k(k=1,2,m)只螞蟻還有未訪只螞蟻還有未訪問的城市問的城市,則該只螞蟻根據(jù)決策則該只螞蟻根據(jù)決策

19、選擇下一個城市選擇下一個城市( i是該螞蟻當前所在城市，是該螞蟻當前所在城市，j(N-禁忌表禁忌表), 是一是一個由城市個由城市i 到城市到城市 j 之間的路徑長度和信息激素之間的路徑長度和信息激素濃度構成的函數(shù)濃度構成的函數(shù)),把選擇的城市把選擇的城市j 寫入禁忌表，直寫入禁忌表，直到所有的城市訪問完。到所有的城市訪問完。 ijpijp2021-11-2322lStep 4 計算計算 k(k=1,2,m) 條路徑的路徑長條路徑的路徑長度，選出本次最優(yōu)路徑。度，選出本次最優(yōu)路徑。lStep 5 根據(jù)本次螞蟻的訪問情況更新每一條根據(jù)本次螞蟻的訪問情況更新每一條邊上的信息激素濃度，清空禁忌表。邊上

20、的信息激素濃度，清空禁忌表。 lStep 6 判斷是否滿足結束條件判斷是否滿足結束條件,如果不滿足，如果不滿足，轉到轉到Step 2 ； 否則結束。否則結束。下圖為流程圖下圖為流程圖 2021-11-23232021-11-2324l(1)分布式計算、正反饋機制和貪婪式搜索相結分布式計算、正反饋機制和貪婪式搜索相結合；合；l(2)具有很強的并行性；具有很強的并行性；l(3)更好的可擴充性；更好的可擴充性；l(4)概率型的通用全局優(yōu)化方法；概率型的通用全局優(yōu)化方法；l(5)不依賴于優(yōu)化本身的嚴格數(shù)學性質，諸如連不依賴于優(yōu)化本身的嚴格數(shù)學性質，諸如連續(xù)性、可導性；續(xù)性、可導性；l各種優(yōu)化算法解決各

21、種優(yōu)化算法解決TSP問題問題2021-11-2325 PSO算法是將群體中的每個個體視為多維搜索空算法是將群體中的每個個體視為多維搜索空間中一個沒有質量和體積的粒子間中一個沒有質量和體積的粒子(點點)，這些粒子，這些粒子在搜索空間中以一定的速度飛行，并根據(jù)粒子本在搜索空間中以一定的速度飛行，并根據(jù)粒子本身的飛行經(jīng)驗以及同伴的飛行經(jīng)驗對自己的飛行身的飛行經(jīng)驗以及同伴的飛行經(jīng)驗對自己的飛行速度進行動態(tài)調整，即每個粒子通過統(tǒng)計迭代過速度進行動態(tài)調整，即每個粒子通過統(tǒng)計迭代過程中自身的最優(yōu)值和群體的最優(yōu)值來不斷地修正程中自身的最優(yōu)值和群體的最優(yōu)值來不斷地修正自己的前進方向和速度大小，從而形成群體尋優(yōu)自

22、己的前進方向和速度大小，從而形成群體尋優(yōu)的正反饋機制。的正反饋機制。PSO算法就是這樣依據(jù)每個粒子算法就是這樣依據(jù)每個粒子對環(huán)境的適應度將個體逐步移到較優(yōu)的區(qū)域，并對環(huán)境的適應度將個體逐步移到較優(yōu)的區(qū)域，并最終搜索、尋找到問題的最優(yōu)解。最終搜索、尋找到問題的最優(yōu)解。2021-11-2326粒子群算法的數(shù)學描述粒子群算法的數(shù)學描述 在在D維的搜索空間中，有隨機分布的維的搜索空間中，有隨機分布的m個粒子組個粒子組成的一個初始粒子群，每個粒子有各自的位置和成的一個初始粒子群，每個粒子有各自的位置和速度。如第速度。如第i個粒子的位置表示為一個個粒子的位置表示為一個D維的向維的向量量 ,速度也是一個速度

23、也是一個D 維的向量，記維的向量，記為為 。每個粒子記住自己在迭代過程。每個粒子記住自己在迭代過程中找到的最優(yōu)位置，記為中找到的最優(yōu)位置，記為 ，整個粒，整個粒子群迄今為止搜索到的最優(yōu)位置為全局最優(yōu)解子群迄今為止搜索到的最優(yōu)位置為全局最優(yōu)解記記 。 這樣的尋優(yōu)為局部這樣的尋優(yōu)為局部PSO算法，經(jīng)過一定的迭代后，算法，經(jīng)過一定的迭代后，改用全局最優(yōu)解，即全局改用全局最優(yōu)解，即全局PSO算法進行迭代以加算法進行迭代以加快收斂。快收斂。 ,1,2,.,iiii Dxx xx,1,2,.,iiii Dvv vv,1,2,.,iiii Dpp pp,1,2,.,gggg Dpppp2021-11-232

24、7可用下面的公式來表示粒子每輪的更新行為：可用下面的公式來表示粒子每輪的更新行為： (2.1) (2.2) 其中其中 為粒子速度，為粒子速度， 為粒子位置，為粒子位置，C1，C2稱為學習因子或加速常量，通常在稱為學習因子或加速常量，通常在 間取值，間取值， C1為調節(jié)粒子飛向自身最好位置的步長為調節(jié)粒子飛向自身最好位置的步長, C2 為為調節(jié)粒子向全局最好位置飛行步長；調節(jié)粒子向全局最好位置飛行步長；r1，r2 是是（0，1）區(qū)間內兩個隨機正數(shù)，）區(qū)間內兩個隨機正數(shù)， 為個體意識為個體意識（個體最佳解位置），（個體最佳解位置）， 為群體最佳解位置為群體最佳解位置. 為慣性權重，使粒子保持運動慣

25、性，控制前一為慣性權重，使粒子保持運動慣性，控制前一速度對當前速度的影響速度對當前速度的影響; t 為飛行的次數(shù)。為飛行的次數(shù)。)()()() 1(,22,11,txprctxprctvwtvdidgdidididi) 1()() 1(,tvtxtxdididi, i dv, i dx0 , 2, i dp,g dpw2021-11-2328粒子群算法的流程如下：粒子群算法的流程如下：Step l： 初始化，設定加速常數(shù)初始化，設定加速常數(shù)C1和和C2，最大進化，最大進化代數(shù)代數(shù) 將當前進化代數(shù)置為將當前進化代數(shù)置為 t = 1 ，在定義空間，在定義空間 中隨機產(chǎn)生中隨機產(chǎn)生m個粒子個粒子X1

26、,X2,Xm，組成初始，組成初始種群種群X(t),隨機產(chǎn)生各粒子初速度隨機產(chǎn)生各粒子初速度V1，V2,VS組成組成位移變化矩陣位移變化矩陣V(t)。Step 2： 計算種群中所有粒子的適應值，初始化每計算種群中所有粒子的適應值，初始化每粒子粒子pbest為當前粒子，設定種群的為當前粒子，設定種群的gbest為當前為當前種群的最優(yōu)粒子。種群的最優(yōu)粒子。maxTnR2021-11-2329Step 3：種群：種群x(t)演化，對種群中的每一個粒子：演化，對種群中的每一個粒子：(1) 按按(2.1),(2.2)式更新粒子的位置和速度。式更新粒子的位置和速度。(2) 計算粒子的適應值。計算粒子的適應值

27、。(3) 比較粒子的適應值和自身的最優(yōu)值比較粒子的適應值和自身的最優(yōu)值pbest。如果當前。如果當前值比值比pbest更優(yōu)，則更新更優(yōu)，則更新pbest為當前值，并更新為當前值，并更新pbest位置到位置到n維空間中的當前位置。維空間中的當前位置。(4) 比較粒子適應值與種群最優(yōu)值。如果當前值比比較粒子適應值與種群最優(yōu)值。如果當前值比gbest更優(yōu)，則更新更優(yōu)，則更新gbest為當前種群最優(yōu)粒子。為當前種群最優(yōu)粒子。 Step 4： 檢查結束條件，若滿足，則結束尋優(yōu)；否則，檢查結束條件，若滿足，則結束尋優(yōu)；否則，t = t + 1，轉至，轉至Step 2.。結束條件為尋優(yōu)達到最大進。結束條件為

28、尋優(yōu)達到最大進化代數(shù)化代數(shù) ，或評價值小于給定精度，或評價值小于給定精度 。maxT2021-11-2330 模擬退火算法是模擬退火算法是80年代發(fā)展起來的一種用于年代發(fā)展起來的一種用于求解大規(guī)模優(yōu)化問題的隨機搜索算法，它以優(yōu)化求解大規(guī)模優(yōu)化問題的隨機搜索算法，它以優(yōu)化問題求解過程與物理系統(tǒng)退火過程之間的相似性問題求解過程與物理系統(tǒng)退火過程之間的相似性為基礎；優(yōu)化的目標函數(shù)相當于金屬的內能；優(yōu)為基礎；優(yōu)化的目標函數(shù)相當于金屬的內能；優(yōu)化問題的自變量組合狀態(tài)空間相當于金屬的內能化問題的自變量組合狀態(tài)空間相當于金屬的內能狀態(tài)空間；問題的求解過程就是找一個組合狀態(tài)，狀態(tài)空間；問題的求解過程就是找一個

29、組合狀態(tài)，使目標函數(shù)值最小。利用使目標函數(shù)值最小。利用Metropolis準則并適當準則并適當?shù)乜刂茰囟鹊南陆颠^程實現(xiàn)模擬退火，從而達到地控制溫度的下降過程實現(xiàn)模擬退火，從而達到在多項式時間內求解全局優(yōu)化問題的目標在多項式時間內求解全局優(yōu)化問題的目標 。2021-11-2331Step 1 初始化：初始溫度初始化：初始溫度T(充分大充分大)，初始解，初始解狀態(tài)狀態(tài)S(是算法迭代的起點是算法迭代的起點)， 每個每個T值的迭代次值的迭代次數(shù)數(shù)L step 2 對對k=1，L做第做第(3)至第至第6步：步： step 3 產(chǎn)生新解產(chǎn)生新解S Step 4 計算增量計算增量t=C(S)-C(S)，其中

30、，其中C(S)為為評價函數(shù)評價函數(shù) 2021-11-2332Step 5 若若t0，然后轉第，然后轉第2步。步。2021-11-2333 與以往的近似算法相比與以往的近似算法相比,模擬退火算法具有模擬退火算法具有描述簡單、使用靈活、運用廣泛、運行效率高描述簡單、使用靈活、運用廣泛、運行效率高和較少受到初始條件約束等優(yōu)點。和較少受到初始條件約束等優(yōu)點。2021-11-2334 我們將各種智能算法應用于解決我們將各種智能算法應用于解決TSP問題，下面我們以問題，下面我們以30個城市的個城市的TSP問題為例進行結果分析問題為例進行結果分析l下表為下表為30個城市的個城市的TSP仿真結果，其中仿真結果

31、，其中30個城市的坐標如個城市的坐標如下：下：l 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 35;4 502021-11-2335l實驗環(huán)境：實驗環(huán)境：MATLAB 7.0 l實驗方法：在算法中設置計數(shù)器，當解轉移迭實驗方法：在算法中設置計數(shù)器，當解轉移迭 代次數(shù)代次數(shù)達到計數(shù)器規(guī)定的值時，無須考

32、慮算法的終止條件即刻達到計數(shù)器規(guī)定的值時，無須考慮算法的終止條件即刻終止算法觀察實驗結果，實驗結果統(tǒng)計。終止算法觀察實驗結果，實驗結果統(tǒng)計。l設置算法參數(shù)：遺傳算法中初始種群的大小為設置算法參數(shù)：遺傳算法中初始種群的大小為100，交，交叉概率為叉概率為0.8。變異概率為。變異概率為0.1。在蟻群算法中信息素重。在蟻群算法中信息素重要程度的參數(shù)要程度的參數(shù), 啟發(fā)式因子重要程度的參數(shù)啟發(fā)式因子重要程度的參數(shù), 信息素蒸發(fā)信息素蒸發(fā)系數(shù)系數(shù), 信息素增加強度系數(shù)信息素增加強度系數(shù).禁忌算法中禁忌長度為禁忌算法中禁忌長度為150，保留前保留前100個最好候選解。個最好候選解。2021-11-233601020304050607080901000102030405060708090100圖圖3.1 30個城市坐標位置圖個城市坐標位置圖2021-11-2337算法算法迭代次迭代次數(shù)數(shù)平均解平均解最好解最好解方差方差遺傳算遺傳算法法500476.90924437.153 1227.217819蟻群算蟻群算法法200428.88425.649 7.75151禁忌搜禁忌搜索算法索算法1