訪問【W(wǎng)RITE-BUG數(shù)字空間】_[內(nèi)附完整源碼和文檔]

該項(xiàng)目主要是利用局部搜索算法（LS）和模擬退火算法（SA）解決 TSP 問題。先是使用 LS 求解 TSP 問題，再嘗試 SA 問題，比較兩者，在效率上 SA 更占有。最后再在 LS 的基礎(chǔ)上使用 SA，再優(yōu)化 SA 部分算法，嘗試求解 TSP 問題。選用的 TSP 測(cè)例為 eil101（有 101 個(gè)城市）。代碼使用 python 語言編寫，因此運(yùn)算速度因?yàn)檎Z言特性比編程語言要低。

摘要

該項(xiàng)目主要是利用局部搜索算法（LS）和模擬退火算法（SA）解決 TSP 問題。先是使用 LS 求解 TSP 問題，再嘗試 SA 問題，比較兩者，在效率上 SA 更占有。最后再在 LS 的基礎(chǔ)上使用 SA，再優(yōu)化 SA 部分算法，嘗試求解 TSP 問題。選用的 TSP 測(cè)例為 eil101（有 101 個(gè)城市）。代碼使用 python 語言編寫，因此運(yùn)算速度因?yàn)檎Z言特性比編程語言要低。

導(dǎo)言

旅行商問題，即 TSP 問題（Traveling Salesman Problem），是求最短路徑的問題，即“已給一個(gè) n 個(gè)點(diǎn)的完全圖，每條邊都有一個(gè)長(zhǎng)度，求總長(zhǎng)度最短的經(jīng)過每個(gè)頂點(diǎn)正好一次的封閉回路”。TSP 是組合優(yōu)化問題，可以被證明具有 NPC 計(jì)算復(fù)雜性。如果希望暴力搜索其最佳解，其復(fù)雜度將是 O(n!)，其計(jì)算量隨著 n 的增加將輕易超過目前計(jì)算機(jī)的可能算力。因此我們需要用更智能的方法求解。

于是我們先考慮局部搜索算法。局部搜索算法是貪心算法，他往往往鄰域中最好的狀態(tài)搜索，因此容易進(jìn)入局部最優(yōu)結(jié)果，而無法跳出局部最優(yōu)的區(qū)域。

第二部分使用模擬退火算法。模擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降,結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。模擬退火算法比起局部搜索算法，賦予了一定跳出局部最優(yōu)解的能力，但能否跳出局部最優(yōu)解依然依賴隨機(jī)性。

實(shí)驗(yàn)過程

首先使用兩種不同的局部搜索算法。

第一種選擇鄰域的方法是隨機(jī)交換兩個(gè)城市在序列中的順序。每次循環(huán)中產(chǎn)生的候選序列為城市數(shù)（以下用 Cs 表示）*10，并從中選擇一個(gè)最優(yōu)的（距離最短的）作為下一步。

第二種選擇鄰域的方法是隨機(jī)交換三個(gè)城市在序列中的順序。每次循環(huán)中產(chǎn)生的候選序列為 Cs*10，并從中選擇一個(gè)最優(yōu)的（距離最短的）作為下一步。

這兩種算法都按以下步驟實(shí)現(xiàn)：

錄入初始狀態(tài)，并打亂順序產(chǎn)生一組隨機(jī)狀態(tài)，從這組狀態(tài)（包括初始狀態(tài)）中選最佳的狀態(tài)作為起點(diǎn)；

Repeat:

產(chǎn)生一個(gè)集合 S

Repeat 10 * Cs times: