模拟退火求解旅行商問題

不用說，一看标題就知道，又是人工智能課的實驗了……

首先不妨轉載一下網上看來的算法描述：

模拟退火算法可分為解空間、目标函數和初始解三部分，其基本思想是： 

（1）初始化：初始溫度 $T$（充分大），初始解狀态 $s$（是算法疊代的起點），每個 $T$ 值的疊代次數為 $L$； 

（2）對 $k = 1, ……, L$ 做第（3）至第（6）步； 

（3）産生新解 $s′$； 

（4）計算增量 $\Delta c=cost(s′)-cost(s)$，其中 $cost(s)$ 為評價函數； 

（5）若 $\Delta c \le 0$ 則接受 $s′$ 作為新的目前解，否則以機率 $exp(-\Delta c/T)$ 接受 $s′$ 作為新的目前解； 

（6）如果滿足終止條件則輸出目前解作為最優解，結束程式。終止條件通常取為連續若幹個新解都沒有被接受時終止算法。 

（7）$T$ 逐漸減少，且 $T$ 趨于 $0$，然後轉第 $2$ 步運算。

轉載的流程圖：

測試用例（城市編号、橫坐标、縱坐标）：

1 20833.3333 17100.0000
2 20900.0000 17066.6667
3 21300.0000 13016.6667
4 21600.0000 14150.0000
5 21600.0000 14966.6667
6 21600.0000 16500.0000
7 22183.3333 13133.3333
8 22583.3333 14300.0000
9 22683.3333 12716.6667
10 23616.6667 15866.6667
11 23700.0000 15933.3333
12 23883.3333 14533.3333
13 24166.6667 13250.0000
14 25149.1667 12365.8333
15 26133.3333 14500.0000
16 26150.0000 10550.0000
17 26283.3333 12766.6667
18 26433.3333 13433.3333
19 26550.0000 13850.0000
20 26733.3333 11683.3333
21 27026.1111 13051.9444
22 27096.1111 13415.8333
23 27153.6111 13203.3333
24 27166.6667 9833.3333
25 27233.3333 10450.0000
26 27233.3333 11783.3333
27 27266.6667 10383.3333
28 27433.3333 12400.0000
29 27462.5000 12992.2222      

注：任意兩城市間距離為歐氏距離。

資料來源：​​http://www.math.uwaterloo.ca/tsp/world/wi29.tsp​​

最優路徑長度：27603

代碼：

#include<bits/stdc++.h>
#define pb(x) push_back(x)
using namespace std;
const double r=0.95; //退火系數
const double Tmin=1e-8; //終止溫度
const int maxStep=1000;
const int N=105;

struct City{
    int id;
    double x,y;
    City(){}
    City(int _id,double _x,double _y) {
        id=_id, x=_x, y=_y;
    }
};
vector<City> cities; //城市資訊存儲
int pos[N];

vector<int> now,nxt; //路徑存儲

inline double Dist(const City& a,const City& b)
{
    return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
double Length(const vector<int>& p)
{
    double res=0.0;
    for(int i=0;i<p.size();i++)
    {
        int x=pos[p[i]], y=pos[p[(i+1)%p.size()]];
        res+=Dist(cities[x],cities[y]);
    }
    return res;
}

int main()
{
    srand(time(nullptr));

    int id; double x,y;
    while(cin>>id>>x>>y)
        cities.pb(City(id,x,y)), pos[id]=cities.size()-1;

    for(auto x:cities) now.pb(x.id);
    random_shuffle(now.begin(),now.end());

    cout<<"初始解路徑："<<endl;
    for(auto x:now) cout<<x<<' '; cout<<endl;

    double T=50000.0;
    while(T>Tmin)
    {
        for(int step=1;step<=maxStep;step++)
        {
            nxt=now;
            int u=0, v=0;
            while(u==v) u=rand()%nxt.size(), v=rand()%nxt.size();
            swap(nxt[u],nxt[v]);

            double L1=Length(now), L2=Length(nxt);
            if(L2-L1<0) now=nxt;
            else
            {
                double rnd=(rand()%101)*1.0/100.0;
                if(rnd<exp((L1-L2)/T)) now=nxt;
            }
        }
        T*=r;
    }

    cout<<"最終解路徑："<<endl;
    for(auto x:now) cout<<x<<' '; cout<<endl;
    cout<<"路徑總長度："<<endl;
    cout<<Length(now)<<endl;
}      

結果：

由于随機數種子設定緣故，每次運作結果都不一樣，給出某一次運作的結果。

 ​