1、./ AO.cpp : 定義控制臺應用程序的入口點。#pragma once#include #include #include const double ALPHA=1.0; /啟發(fā)因子，信息素的重要程度const double BETA=2.0; /期望因子，城市間距離的重要程度const double ROU=0.5; /信息素殘留參數(shù)const int N_ANT_COUNT=34; /螞蟻數(shù)量const int N_IT_COUNT=1000; /迭代次數(shù)const int N_CITY_COUNT=51; /城市數(shù)量const double DBQ=100.0; /總的信息素con

2、st double DB_MAX=10e9; /一個標志數(shù)，10的9次方double g_TrialN_CITY_COUNTN_CITY_COUNT; /兩兩城市間信息素，就是環(huán)境信息素double g_DistanceN_CITY_COUNTN_CITY_COUNT; /兩兩城市間距離/eil51.tsp城市坐標數(shù)據(jù)double x_AryN_CITY_COUNT= 37,49,52,20,40,21,17,31,52,51, 42,31,5,12,36,52,27,17,13,57, 62,42,16,8,7,27,30,43,58,58, 37,38,46,61,62,63,32,45,

3、59,5, 10,21,5,30,39,32,25,25,48,56, 30;double y_AryN_CITY_COUNT= 52,49,64,26,30,47,63,62,33,21, 41,32,25,42,16,41,23,33,13,58, 42,57,57,52,38,68,48,67,48,27, 69,46,10,33,63,69,22,35,15,6, 17,10,64,15,10,39,32,55,28,37, 40;/返回指定范圍內(nèi)的隨機整數(shù)int rnd(int nLow,int nUpper) return nLow+(nUpper-nLow)*rand()/(RA

4、ND_MAX+1);/返回指定范圍內(nèi)的隨機浮點數(shù)double rnd(double dbLow,double dbUpper) double dbTemp=rand()/(double)RAND_MAX+1.0); return dbLow+dbTemp*(dbUpper-dbLow);/返回浮點數(shù)四舍五入取整后的浮點數(shù)double ROUND(double dbA) return (double)(int)(dbA+0.5);/定義螞蟻類class CAntpublic: CAnt(void); CAnt(void);public: int m_nPathN_CITY_COUNT; /螞蟻走

5、的路徑 double m_dbPathLength; /螞蟻走過的路徑長度 int m_nAllowedCityN_CITY_COUNT; /沒去過的城市 int m_nCurCityNo; /當前所在城市編號 int m_nMovedCityCount; /已經(jīng)去過的城市數(shù)量public: int ChooseNextCity(); /選擇下一個城市 void Init(); /初始化 void Move(); /螞蟻在城市間移動 void Search(); /搜索路徑 void CalPathLength(); /計算螞蟻走過的路徑長度;/構(gòu)造函數(shù)CAnt:CAnt(void)/析構(gòu)函數(shù)

6、CAnt:CAnt(void)/初始化函數(shù)，螞蟻搜索前調(diào)用void CAnt:Init() for (int i=0;iN_CITY_COUNT;i+) m_nAllowedCityi=1; /設置全部城市為沒有去過 m_nPathi=0; /螞蟻走的路徑全部設置為0 /螞蟻走過的路徑長度設置為0 m_dbPathLength=0.0; /隨機選擇一個出發(fā)城市 m_nCurCityNo=rnd(0,N_CITY_COUNT); /把出發(fā)城市保存入路徑數(shù)組中 m_nPath0=m_nCurCityNo; /標識出發(fā)城市為已經(jīng)去過了 m_nAllowedCitym_nCurCityNo=0; /已

7、經(jīng)去過的城市數(shù)量設置為1 m_nMovedCityCount=1;/選擇下一個城市/返回值 為城市編號int CAnt:ChooseNextCity() int nSelectedCity=-1; /返回結(jié)果，先暫時把其設置為-1 /= /計算當前城市和沒去過的城市之間的信息素總和 double dbTotal=0.0; double probN_CITY_COUNT; /保存各個城市被選中的概率 for (int i=0;i 0.0) /總的信息素值大于0 dbTemp=rnd(0.0,dbTotal); /取一個隨機數(shù) for (int i=0;iN_CITY_COUNT;i+) if (

8、m_nAllowedCityi = 1) /城市沒去過 dbTemp=dbTemp-probi; /這個操作相當于轉(zhuǎn)動輪盤，如果對輪盤選擇不熟悉，仔細考慮一下 if (dbTemp 0.0) /輪盤停止轉(zhuǎn)動，記下城市編號，直接跳出循環(huán) nSelectedCity=i; break; /= /如果城市間的信息素非常小 ( 小到比double能夠表示的最小的數(shù)字還要小 ) /那么由于浮點運算的誤差原因，上面計算的概率總和可能為0 /會出現(xiàn)經(jīng)過上述操作，沒有城市被選擇出來 /出現(xiàn)這種情況，就把第一個沒去過的城市作為返回結(jié)果 /題外話：剛開始看的時候，下面這段代碼困惑了我很長時間，想不通為何要有這段代

9、碼，后來才搞清楚。 if (nSelectedCity = -1) for (int i=0;iN_CITY_COUNT;i+) if (m_nAllowedCityi = 1) /城市沒去過 nSelectedCity=i; break; /= /返回結(jié)果，就是城市的編號 return nSelectedCity;/螞蟻在城市間移動void CAnt:Move() int nCityNo=ChooseNextCity(); /選擇下一個城市 m_nPathm_nMovedCityCount=nCityNo; /保存螞蟻走的路徑 m_nAllowedCitynCityNo=0;/把這個城市設置

10、成已經(jīng)去過了 m_nCurCityNo=nCityNo; /改變當前所在城市為選擇的城市 m_nMovedCityCount+; /已經(jīng)去過的城市數(shù)量加1/螞蟻進行搜索一次void CAnt:Search() Init(); /螞蟻搜索前，先初始化 /如果螞蟻去過的城市數(shù)量小于城市數(shù)量，就繼續(xù)移動 while (m_nMovedCityCount N_CITY_COUNT) Move(); /完成搜索后計算走過的路徑長度 CalPathLength();/計算螞蟻走過的路徑長度void CAnt:CalPathLength() m_dbPathLength=0.0; /先把路徑長度置0 int

11、 m=0; int n=0; for (int i=1;iN_CITY_COUNT;i+) m=m_nPathi; n=m_nPathi-1; m_dbPathLength=m_dbPathLength+g_Distancemn; /加上從最后城市返回出發(fā)城市的距離 n=m_nPath0; m_dbPathLength=m_dbPathLength+g_Distancemn; /tsp類class CTsppublic: CTsp(void); CTsp(void);public: CAnt m_cAntAryN_ANT_COUNT; /螞蟻數(shù)組 CAnt m_cBestAnt; /定義一個螞

12、蟻變量，用來保存搜索過程中的最優(yōu)結(jié)果 /該螞蟻不參與搜索，只是用來保存最優(yōu)結(jié)果public: /初始化數(shù)據(jù) void InitData(); /開始搜索 void Search(); /更新環(huán)境信息素 void UpdateTrial();/構(gòu)造函數(shù)CTsp:CTsp(void)CTsp:CTsp(void)/初始化數(shù)據(jù)void CTsp:InitData() /先把最優(yōu)螞蟻的路徑長度設置成一個很大的值 m_cBestAnt.m_dbPathLength=DB_MAX; /計算兩兩城市間距離 double dbTemp=0.0; for (int i=0;iN_CITY_COUNT;i+) f

13、or (int j=0;jN_CITY_COUNT;j+) dbTemp=(x_Aryi-x_Aryj)*(x_Aryi-x_Aryj)+(y_Aryi-y_Aryj)*(y_Aryi-y_Aryj); dbTemp=pow(dbTemp,0.5); g_Distanceij=ROUND(dbTemp); /初始化環(huán)境信息素，先把城市間的信息素設置成一樣 /這里設置成1.0，設置成多少對結(jié)果影響不是太大，對算法收斂速度有些影響 for (int i=0;iN_CITY_COUNT;i+) for (int j=0;jN_CITY_COUNT;j+) g_Trialij=1.0; /更新環(huán)境信息

14、素void CTsp:UpdateTrial() /臨時數(shù)組，保存各只螞蟻在兩兩城市間新留下的信息素 double dbTempAryN_CITY_COUNTN_CITY_COUNT; memset(dbTempAry,0,sizeof(dbTempAry); /先全部設置為0 /計算新增加的信息素,保存到臨時數(shù)組里 int m=0; int n=0; for (int i=0;iN_ANT_COUNT;i+) /計算每只螞蟻留下的信息素 for (int j=1;jN_CITY_COUNT;j+) m=m_cAntAryi.m_nPathj; n=m_cAntAryi.m_nPathj-1;

15、 dbTempArynm=dbTempArynm+DBQ/m_cAntAryi.m_dbPathLength; dbTempArymn=dbTempArynm; /最后城市和開始城市之間的信息素 n=m_cAntAryi.m_nPath0; dbTempArynm=dbTempArynm+DBQ/m_cAntAryi.m_dbPathLength; dbTempArymn=dbTempArynm; /= /更新環(huán)境信息素 for (int i=0;iN_CITY_COUNT;i+) for (int j=0;jN_CITY_COUNT;j+) g_Trialij=g_Trialij*ROU+d

16、bTempAryij; /最新的環(huán)境信息素 = 留存的信息素 + 新留下的信息素 void CTsp:Search() char cBuf256; /打印信息用 /在迭代次數(shù)內(nèi)進行循環(huán) for (int i=0;iN_IT_COUNT;i+) /每只螞蟻搜索一遍 for (int j=0;jN_ANT_COUNT;j+) m_cAntAryj.Search(); /保存最佳結(jié)果 for (int j=0;jN_ANT_COUNT;j+) if (m_cAntAryj.m_dbPathLength m_cBestAnt.m_dbPathLength) m_cBestAnt=m_cAntAryj; /更新環(huán)境信息素 UpdateTrial(); /輸出目前為止找到的最優(yōu)路徑的長度 sprintf(cBuf,n%d %.0f,i+1,m_cBestAnt.m_dbPathLength); printf(cBuf); int main() /用當前時間點初始化隨機種子，防止每次運行的結(jié)果都相同 time_t tm; time(&tm); unsigned int nSeed=(unsigned int)tm; srand(nSeed); /開始搜索 CTsp tsp