模擬退火演算法tsp

⑶ 什麼是tsp問題，數學模型中的一種模型問題

Traveling Saleman Problem 旅行商問題
「旅行商問題」常被稱為「旅行推銷員問題」，是指一名推銷員要拜訪多個地點時，如何找到在拜訪每個地點一次後再回到起點的最短路徑。規則雖然簡單，但在地點數目增多後求解卻極為復雜。以42個地點為例，如果要列舉所有路徑後再確定最佳行程，那麼總路徑數量之大，幾乎難以計算出來。多年來全球數學家絞盡腦汁，試圖找到一個高效的演算法，近來在大型計算機的幫助下才取得了一些進展。 TSP問題在物流中的描述是對應一個物流配送公司，欲將n個客戶的訂貨沿最短路線全部送到。如何確定最短路線。 TSP問題最簡單的求解方法是枚舉法。它的解是多維的、多局部極值的、趨於無窮大的復雜解的空間，搜索空間是n個點的所有排列的集合，大小為（n-1）。可以形象地把解空間看成是一個無窮大的丘陵地帶，各山峰或山谷的高度即是問題的極值。求解TSP，則是在此不能窮盡的丘陵地帶中攀登以達到山頂或谷底的過程。

具體參見網路
http://ke..com/view/1162183.htm

多個旅行商同時出發的問題稱為MTSP問題。設立虛點轉化為TSP即可求解。
數學模型是可以用線性規劃來描述，但是在多項式求解時間內無解，所以才出現了各種啟發式演算法，什麼遺傳演算法，模擬退火，蟻群演算法之類的

⑷ 模擬退火演算法在TSP問題怎樣體現出來的

Procere SIMULATED_ANNEALING;
begin
INITIALIZE (i0, t0, L0); { 初始化i0, t0, L0 }
k:=0;
i:=i
0;
Repeat
{ 對每個tk產生Lk個解，這Lk個解構成了一條長為Lk的Mapkob鏈}
for l:=1 to Lk do begin
GENERATE (j from Si); { 從當前解i的鄰域Si中產生新解j }
{ 以下 3 行即 Metropolis 演算法，共迭代了Lk 次 }
if f(j) <= f(i) then i:=j
else
if exp((f(i)-f(j))/ tk) >= random[0, 1) then i:=j {模擬退火演算法就是在這里體現，根據溫度變化隨機接受一個不良解，以防止局部最優現象，而隨著溫度（tk）的降低，接受不良解的概率越來越低，最終逼近最優解}
end;
k:=k+1;
CALCULATE_LENGTH (Lk); { 重新計算Mapkob鏈長Lk }
CALCULATE_CONTROL(tk); { 重新計算控制參數值tk }
until stop_criterion { 演算法停止准則 }
End;

⑸ 模擬退火演算法每次的解為什麼不一樣

模擬退火每次的解不同是很正常的，因為模擬退火本身是一種隨機演算法，轉移向更差的解不是必然而是概率性的，也就是說每次執行演算法時，執行過程轉移到的解可能都是完全不一樣的。

至於TSP問題，本身屬於NP-hard問題，找不到存在多項式時間復雜度的解。

如果要求精確的解，目前可行的方法有枚舉、分支限界、動態規劃等，但這些方法適用的數據范圍都很小，一旦數據規模變大，它們都將無能為力。

所以目前廣泛使用的大都是一些隨機演算法，比如蟻群、遺傳等，模擬退火就是其中的一種，這些演算法的一大特點就是通過隨機去逼近最優解，但也有可能得到錯解。

只有窮舉法可以保證得到最優解，但是窮舉法在數據量比較大的時候運行時間通常是不能接受的，所以用了各種近似方法。

模擬退火演算法新解的產生和接受可分為如下四個步驟：

第一步是由一個產生函數從當前解產生一個位於解空間的新解；為便於後續的計算和接受，減少演算法耗時，通常選擇由當前新解經過簡單地變換即可產生新解的方法，如對構成新解的全部或部分元素進行置換、互換等，注意到產生新解的變換方法決定了當前新解的鄰域結構，因而對冷卻進度表的選取有一定的影響。

第二步是計算與新解所對應的目標函數差。因為目標函數差僅由變換部分產生，所以目標函數差的計算最好按增量計算。事實表明，對大多數應用而言，這是計算目標函數差的最快方法。

第三步是判斷新解是否被接受,判斷的依據是一個接受准則，最常用的接受准則是Metropolis准則: 若ΔT<0則接受S′作為新的當前解S，否則以概率exp(-ΔT/T)接受S′作為新的當前解S。

第四步是當新解被確定接受時，用新解代替當前解，這只需將當前解中對應於產生新解時的變換部分予以實現，同時修正目標函數值即可。此時，當前解實現了一次迭代。可在此基礎上開始下一輪試驗。而當新解被判定為舍棄時，則在原當前解的基礎上繼續下一輪試驗。

⑹ 退火演算法的應用領域及示例

作為模擬退火演算法應用，討論旅行商問題(Travelling Salesman Problem,簡記為TSP)：設有n個城市，用數碼1,…,n代表。城市i和城市j之間的距離為d(i,j) i,j=1,…,n．TSP問題是要找遍訪每個域市恰好一次的一條迴路，且其路徑總長度為最短.。
求解TSP的模擬退火演算法模型可描述如下：
解空間 解空間S是遍訪每個城市恰好一次的所有迴路，是{1,……,n}的所有循環排列的集合,S中的成員記為(w1,w2,……,wn)，並記wn+1= w1。初始解可選為(1,……,n)
目標函數 此時的目標函數即為訪問所有城市的路徑總長度或稱為代價函數：
我們要求此代價函數的最小值。
新解的產生 隨機產生1和n之間的兩相異數k和m,
若k<m,則將
(w1,w2,…,wk,wk+1,…,wm,…,wn)
變為：
(w1,w2,…,wm,wm-1,…,wk+1,wk,…,wn).
如果是k>m,則將
(w1,w2,…,wm,wm+1,…,wk,…,wn)
變為：
(wm,wm-1,…,w1,wm+1,…,wk-1,wn,wn-1,…,wk).
上述變換方法可簡單說成是「逆轉中間或者逆轉兩端」。
也可以採用其他的變換方法，有些變換有獨特的優越性，有時也將它們交替使用，得到一種更好方法。
代價函數差 設將(w1,w2,……,wn)變換為(u1,u2,……,un)，則代價函數差為：
根據上述分析，可寫出用模擬退火演算法求解TSP問題的偽程序：
Procere TSPSA:
begin
init-of-T; { T為初始溫度}
S={1,……,n}; {S為初始值}
termination=false;
while termination=false
begin
for i=1 to L do
begin
generate(S′form S); { 從當前迴路S產生新迴路S′}
Δt:=f(S′））-f(S);{f(S)為路徑總長}
IF（Δt<0) OR (EXP(-Δt/T)>Random-of-[0,1])
S=S′；
IF the-halt-condition-is-TRUE THEN
termination=true;
End;
T_lower;
End;
End
模擬退火演算法的應用很廣泛，可以較高的效率求解最大截問題(Max Cut Problem)、0-1背包問題(Zero One Knapsack Problem)、圖著色問題(Graph Colouring Problem)、調度問題(Scheling Problem)等等。 模擬退火演算法的應用很廣泛，可以求解NP完全問題，但其參數難以控制，其主要問題有以下三點：
⑴ 溫度T的初始值設置問題。
溫度T的初始值設置是影響模擬退火演算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優解的可能性大，但因此要花費大量的計算時間；反之，則可節約計算時間，但全局搜索性能可能受到影響。實際應用過程中，初始溫度一般需要依據實驗結果進行若干次調整。
⑵ 退火速度問題。
模擬退火演算法的全局搜索性能也與退火速度密切相關。一般來說，同一溫度下的「充分」搜索（退火）是相當必要的，但這需要計算時間。實際應用中，要針對具體問題的性質和特徵設置合理的退火平衡條件。
⑶ 溫度管理問題。
溫度管理問題也是模擬退火演算法難以處理的問題之一。實際應用中，由於必須考慮計算復雜度的切實可行性等問題，常採用如下所示的降溫方式：
T(t+1)=k×T(t)
式中k為正的略小於1.00的常數,t為降溫的次數 優點：計算過程簡單，通用，魯棒性強，適用於並行處理，可用於求解復雜的非線性優化問題。
缺點：收斂速度慢，執行時間長，演算法性能與初始值有關及參數敏感等缺點。
經典模擬退火演算法的缺點：
⑴如果降溫過程足夠緩慢，多得到的解的性能會比較好，但與此相對的是收斂速度太慢；
⑵如果降溫過程過快，很可能得不到全局最優解。
􀂄 模擬退火演算法的改進
⑴ 設計合適的狀態產生函數，使其根據搜索進程的需要
表現出狀態的全空間分散性或局部區域性。
⑵ 設計高效的退火策略。
⑶ 避免狀態的迂迴搜索。
⑷ 採用並行搜索結構。
⑸ 為避免陷入局部極小，改進對溫度的控制方式
⑹ 選擇合適的初始狀態。
⑺ 設計合適的演算法終止准則。
也可通過增加某些環節而實現對模擬退火演算法的改進。
主要的改進方式包括：
⑴ 增加升溫或重升溫過程。在演算法進程的適當時機，將溫度適當提高，從而可激活各狀態的接受概率，以調整搜索進程中的當前狀態，避免演算法在局部極小解處停滯不前。
⑵ 增加記憶功能。為避免搜索過程中由於執行概率接受環節而遺失當前遇到的最優解，可通過增加存儲環節，將一些在這之前好的態記憶下來。
⑶ 增加補充搜索過程。即在退火過程結束後，以搜索到的最優解為初始狀態，再次執行模擬退火過程或局部性搜索。
⑷ 對每一當前狀態，採用多次搜索策略，以概率接受區域內的最優狀態，而非標准SA的單次比較方式。
⑸ 結合其他搜索機制的演算法，如遺傳演算法、混沌搜索等。
⑹上述各方法的綜合應用。

⑺ 模擬退火求tsp問題可以用python編程嗎

模擬退火求tsp問題可以用python編程
也許最初設計 Python 這種語言的人並沒有想到今天Python 會在工業和科研上獲得如此廣泛的使用。著名的自由軟體作者Eric Raymond 在他的文章《如何成為一名黑客》中，將Python 列為黑客應當學習的四種編程語言之一，並建議人們從Python 開始學習編程。這的確是一個中肯的建議，對於那些從來沒有學習過編程或者並非計算機專業的編程學習者而言，Python 是最好的選擇之一。Python 第一次學習Python，我只用了不到二十分鍾的時間，站在書店裡把一本教初學編程的人學習Python 的書翻了一遍。也是從那時起，我開始被這種神奇的語言吸引。 Python 可以用來開發symbian 上的東西。 易用與速度的完美結合Python 是一種用起來很方便的語言，很多初學Java 的人都會被 Java 的CLASSPATH 搞得暈頭轉向，花上半天的時間才搞明白原來是CLASSPATH 搞錯了自己的 Hello World 才沒法運行。

⑻ 求模擬退火演算法解旅行商問題的C++代碼

我自己寫的：
#include<stdlib.h>
#include<cmath>
#include<algorithm>
using namespace std;
static double Tmax = 10, Tmin = 0.1, r = 0.999999;
static int k = 100;
inline void random_sele(int &fl, int &fp, int arr[], int n)
{
do
{
fl = rand() % n;
fp = rand() % n;
} while (fl == arr[fp] || arr[fl] == arr[fp]);
};
inline bool accept(double r1, double r2, double T)
{
const unsigned int MASK((1 << 30) - 1);
double p = 1.0 / (1.0 + exp((r2 - r1) / T));
unsigned int temp1=((rand()<<20)^(rand()<<10)^rand())&MASK;
unsigned int temp2=((rand()<<20)^(rand()<<10)^rand())&MASK;
double res=(1.0*temp1+1.0*temp2/MASK);
return res < p*MASK;
}
void set_SA()
{
printf(" Tmax Tmin r k\n");
printf(" %.8f %.8f %.8f %d \n",Tmax,Tmin,r,k);
printf("Input Tmax,Tmin,r,k:\n");
scanf("%lf%lf%lf%d",&Tmax,&Tmin,&r,&k);
}
void TSP_SA(int arr[], double &evl, int n, double map[][2000])
{
double r1, r2, T = Tmax;
int i, fl, sl, fp, sp;
int show_s=0;
srand(11827);
while (T >= Tmin)
{
for (i = 0; i < k; i++)
{
random_sele(fl, fp, arr, n);
sl = arr[fl], sp = arr[fp];
r1 = map[fl][sl] + map[fp][sp] + map[sp][arr[sp]];
r2 = map[fl][sp] + map[sp][sl] + map[fp][arr[sp]];
if (accept(r1, r2, T))
{
arr[fp] = arr[sp];
arr[fl] = sp;
arr[sp] = sl;
sl = sp;
evl = evl + r2 - r1;
}
}
if(++show_s==1000000/k)
{
printf("T=%f evl=%f\n",T,evl);
show_s=0;
}
T *= r;
}
}