TSP問題，旅行商問題：假如一個旅行商人要拜訪n個城市，他必須選擇所有要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最後要回到原來出發的城市。選擇全部路徑中的最小值。TSP具有NP計算復雜度（NP是指在非確定性圖靈機上有多項式時間算法的問題）。TSP問題是數圖論中重要的一個問題，即“已給一個n個點的完全圖，每條邊都有一個長度，求總長度最短的經過每個頂點正好一次的封閉回路”。
蟻群算法：蟻群算法是一種基於種群，通過模擬蟻群采集食物的過程的啟發式搜索算法。螞蟻通過釋放信息素來記錄路徑，並趨向於走信息素量較多的路徑來尋找最佳路徑。其中一些限制的參數。
1.信息素的總量：螞蟻擁有的信息素是有一定總量的，則在出發出信息素量較多，在一定距離後信息素會用盡，以防止其越走越遠。
2.觀測范圍：螞蟻有一定的觀測范圍，會選擇信息素較多的路徑。
3.出錯概率：螞蟻有一定的出錯概率，會不往信息素最多的區域走。這使算法不過早的收斂。
4.信息素的消減速度：信息素以一定的速度消減，使一些不合適的路徑上的信息素能消失，以減少對螞蟻的干擾。
5.記憶能力：螞蟻應該記住之前總過的路徑，以防止回頭，但是這個值較大時，會較低效率。
結合TSP問題，應做的一些改進：
螞蟻數量為m，城市數量為n，城市間的距離為D[ i ] [ j ]。螞蟻行走的過程不應該是以一定速度行走，而是以 一個時間段進行行走，在這個時間段內，每個螞蟻都能完整的從一個城市走到另一個城市。則在n個時間段後，螞蟻完成了一次回路，則n個時間段合起來為一次循環，計循環次數為K。每只螞蟻在一個循環中走過的城市編號，保存在 Path [m] [n];中，對於Path[m][0]]默認為出發點，則螞蟻無法走路徑中的點,則最後一個點不是初始點，但之後要回到初始點，要注意一下。
對於這個系統，應該選擇標記的是點還是邊，即螞蟻留下信息素的地方是邊還是點。暫時使用邊，以方便之後的信息素消散的操作。雖然對於一個點去選取其下一個路徑來說，下一個點上的信息素濃度與下一條邊上的濃度效果是相同的，但由於這是完全圖，對於其他點在選取邊時，會被其他點的最佳選取所增加的信息素所干擾。
對於信息素，在蟻群算法中有兩種信息素，一種是找到食物的螞蟻留下的信息素，一種是找到家的螞蟻留下的信息素。而在TSP中，螞蟻肯定會找到家，則只有一種信息素。則每完成一次循環後，進行信息素的更新。信息素的更新公式：
Phe [ i ][ j ] = Dis* Phe[i][j] + DPhe[i][j]
Phe 表示 每條邊上的信息素濃度，Dis為信息素消逝的速率，DPhe為本次循環內的邊ij的信息素增加量。DPhe的值為 每個螞蟻在本次循環留在路徑ij上的信息素量KDPhe的總和，對於KDPhe有三種模型，Ant-Circle System ， Ant-Quantity System 和 Ant-Density System.效果最好的為第一種。具體為
Ant-Circle System ： KDPhe = Q / LK 或0（當螞蟻未經過此路徑時。Q為一個常量，LK為這個循環中，此螞蟻的總路程）
Ant-Quantity System ： KDPhe = Q / D[i][j] 或0
Ant-Density System .： KDPhe = Q 或 0
顯然，第一種的效果更好，當螞蟻的總路程越短，使其留下來的信息素量越高。
代碼如下：
using namespace std;
//使用10個螞蟻，進行10個城市的TSP問題求解。
const int MMax = 9999;//螞蟻數量,螞蟻數量根據城市數量決定。
const int NMax = 500;//城市數量最大數量，超過出錯
int m,n;//螞蟻數量與城市數量
const double Q = 999 ;//常量
const int K = 1000;//循環總次數
int D[NMax][NMax];//路徑長度
double Phe[NMax][NMax];//邊對應的信息素濃度
int LK;//螞蟻此循環中的總路徑長度
int Path[MMax][NMax];//記錄螞蟻的路徑，用於防止走重復的路。記錄的是點
int ant;//螞蟻當前所在點
int i,j,k,p;//循環使用
double Dis = 0.1;//每次信息素 消失的速率
int sameNum,samePhe[NMax];//每次去尋找信息素最多的邊，如初始情況，信息素量都相同時，要
//隨機的去從中選取邊。
int bugNum,bugTry[NMax];//出錯情況下進行的選擇
double bugP = 0.90;//每一次操作的出錯概率
//後來發現，出錯概率要結合螞蟻數與城市數進行判斷，而定值Q為估計距離
int start;//出發點，城市編號從0 - n-1.
double Max;//用來選取最多信息素的邊
bool Passed[NMax];//用來判斷城市是否已經經過，是否可以選取
int main()
{
//載入數據
fstream f("data.txt",ios::in);
f >> n;
if( n > NMax)//本來想直接賦值，後來又決定從文件中讀入。
return 0;
for(i = 0;i>D[i][j];
for(i = 0;i < n;i++)
D[i][i] = 0;
f >> start;
if(start > n-1)return 0;//沒必要的檢測，如果文件未正確書寫，發生意外的錯誤，概不負責。
f.close();
for(i = 0;i < n;i++)
for(j = 0; j < n;j++)
Phe[i][j] = 1;//初始化每條邊上的信息素濃度
for(i = 0;i< m;i++)
Path[i][0] = start;//每只螞蟻的出發點都固定
m = 999;//螞蟻數為城市數的2倍,後來發現不夠
for(k = 0;k < K;k++){
for(i = 0;i < n;i++)
for(j = 0; j < n;j++)
Phe[i][j] *= Dis ;//每次循環後，進行信息素的消逝
srand((unsigned)time(NULL));
for(i = 0;i < m;i++){//對於每只螞蟻，進行一次循環
ant = start;
for(j = 0;j < n;j++)
Passed[j] = false;
Passed[ant] = true;
for(j = 1;j < n;j++){//每只螞蟻選n-1次邊
Max = 0;
sameNum = 0 ;
bugNum = 0;
for(p = 0;p < n;p++)
if(!Passed[p])
Max = Max > Phe[ant][p] ? Max : Phe[ant][p] ;//尋找周圍邊上信息素的最大值
for(p = 0;p < n;p++)
if(Max == Phe[ant][p])
if(!Passed[p])
samePhe[sameNum++] = p;//記錄信息素取最大值時，對應的city編號和數量
for(p = 0;p < n;p++)
if(!Passed[p])
bugTry[bugNum++] = p;
if( (double)rand() /32765 < bugP)
ant = samePhe[ rand() % sameNum ] ;//用隨機數，從中選中一條邊
else
ant = bugTry [ rand() % bugNum ] ;//出錯情況下，隨機選一條邊
Passed[ant] = true;//路徑經過
Path[i][j] = ant;//保存路徑
}
}
//完成對每一個螞蟻的操作後，進行增加信息素的操作，使用Ant-Circle System
for(i = 0; i < m;i++){
LK = 0 ;
for(j = 0; j < n-1;j++)
LK += D[Path[i][j]][Path[i][j+1]];//計算一次循環中螞蟻的總路程
LK += D[Path[i][j]][Path[i][0]];//回到初始點
for(j = 0; j < n-1;j++)
Phe[Path[i][j]][Path[i][j+1]] += Q/LK ;
Phe[Path[i][j]][Path[i][0]] += Q/LK ;//初始點
}
}
p = 0xfffff;//雖然已經完成操作，但我們要直觀的從所有現有路徑中找出最短的路徑。
for(i = 0;i < m;i++){
LK = 0;
for(j = 0;j < n-1;j++)
LK += D[Path[i][j]][Path[i][j+1]];//計算一次循環中螞蟻的總路程
LK += D[Path[i][j]][Path[i][0]];//回到初始點
if(LK < p){
p = LK;
start = i;
}
}
for(i = 0;i < n; i++)
cout << Path[start][i]<<"->";
cout << Path[start][0]<
寫好後對測試用例進行測試，只有10個城市的最佳路徑求解，發現一開始的代碼執行後得到的結果偏差較大而且次次不同。然後對其中的一些常量進行了更改。但是發現這些常量是息息相關的，更改一個則會導致其他的常數效果變差。如當我將螞蟻數量增加時，每次循環後增加的信息素量會變大，而使每一次的新的信息素增加占信息素量的比例變得極大，而是其對之前可能有的較好路徑的敏感度降低。
決定這些常量的值是一件困難的事，測試了半天後，發現太難去尋找一個較好的搭配，而且在我選取的常量的搭配中，最多嘗試了100000次循環依舊沒有求的最佳解。完。
