基于改進禁忌搜尋算法求解TSP問題（Matlab代碼實作）

目錄

​​1 概述​​

​​2 改進禁忌搜尋算法​​

​​3 運作結果​​

​​4 參考文獻​​

​​5 Matlab代碼實作​​

1 概述

當城市數量較少時,理論上可以通過窮舉法來列舉出最優方案,然而當城市數量較多時,所有路線之和将呈指數增加,是以求解過程非常複雜而且很難找到最優解。目前,求解TSP問題的算法大緻可劃分為兩類,分别是确定性算法和智能優化算法5。确定性算法通常是指能利用數學公式解出具體的某個數值,且該結果即為最優解,例如線性規劃、動态規劃、完全枚舉等方法,然而該類算法隻适用于小規模算例求解,是以,考慮到現實應用情況,在規模較大時,人們常常選擇目前廣受關注的智能優化算法,例如遺傳算法、粒子群算法、模拟退火算法、禁忌搜尋算法、免疫算法以及人工神經網絡6等等。本文主要通過遺傳算法和禁忌搜尋算法兩種算法進行混合求解,結合兩種算法的優勢,對TSP問題進行優化求解,提高解的品質。

TSP問題作為一個典型的組合優化問題,多年來衆多學者都對其展開了深入研究,以期尋找

到一個最優算法來應用到實際生活中。由于TSP問題是一個NP難題,是以一般使用目前較為普遍的智能優化算法進行計算其最短路徑，

禁忌搜尋算法便是其中之一。該算法通過引入禁忌表和特赦準則來避免搜尋陷入局部最優,在各個行業中均獲得了廣泛應用。但是,該算法也存在一定的缺陷,比如對初始解的依賴性。是以,本文為了克服該缺點,将傳統的禁忌搜尋算法進行了改進,借助遺傳算法來對初始解進行優化,進而得到更優解。通過案例仿真表明,加入遺傳算法後,實驗結果有了很大的改善，得到了更優的路線方案,縮短了總旅程的距離,驗證了算法改進後的有效性和可行性。

2 改進禁忌搜尋算法

1986年,Fred Glover教授提出了禁忌搜尋算法( TabuSearch，簡稱TS算法)10l，指出該算法的局部搜尋能力非常強,并且也能避免算法陷入局部最優,進而找到全局最優解，是一種全局疊代尋優算法。多年來,該算法也以其靈活的記憶特性和特赦準則,受到了衆多學者的青睐。

所謂禁忌,是指禁止重複操作,類似于模拟人的思維模式,如果該區域已經搜尋過,則下次搜尋時可以通過禁忌表來進行記錄,避免重複低效搜尋,但也并非完全隔絕,對于更優的解,也可以通過特赦準則對其進行釋放,改善解的品質，避免遺漏。

3 運作結果

4 參考文獻

5 Matlab代碼實作