蟻群算法(C++版)

/ AO.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。#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; /總的信息素const double DB_MAX=10e9; /一個(gè)標(biāo)志數(shù)，10的9次方double g_TrialN_CITY_COUNTN_CITY_COUNT; /兩兩城市間信息素，就是環(huán)境信息素double g_DistanceN_CITY_COUNTN_CITY_COUNT; /兩兩城市間距離/eil51.tsp城市坐標(biāo)數(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,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)的隨機(jī)整數(shù)int rnd(int nLow,int nUpper) return nLow+(nUpper-nLow)*rand()/(RAND_MAX+1);/返回指定范圍內(nèi)的隨機(jī)浮點(diǎn)數(shù)double rnd(double dbLow,double dbUpper) double dbTemp=rand()/(double)RAND_MAX+1.0); return dbLow+dbTemp*(dbUpper-dbLow);/返回浮點(diǎn)數(shù)四舍五入取整后的浮點(diǎn)數(shù)double ROUND(double dbA) return (double)(int)(dbA+0.5);/定義螞蟻類class CAntpublic: CAnt(void); CAnt(void);public: int m_nPathN_CITY_COUNT; /螞蟻?zhàn)叩穆窂?double m_dbPathLength; /螞蟻?zhàn)哌^(guò)的路徑長(zhǎng)度 int m_nAllowedCityN_CITY_COUNT; /沒(méi)去過(guò)的城市 int m_nCurCityNo; /當(dāng)前所在城市編號(hào) int m_nMovedCityCount; /已經(jīng)去過(guò)的城市數(shù)量public: int ChooseNextCity(); /選擇下一個(gè)城市 void Init(); /初始化 void Move(); /螞蟻在城市間移動(dòng) void Search(); /搜索路徑 void CalPathLength(); /計(jì)算螞蟻?zhàn)哌^(guò)的路徑長(zhǎng)度;/構(gòu)造函數(shù)CAnt:CAnt(void)/析構(gòu)函數(shù)CAnt:CAnt(void)/初始化函數(shù)，螞蟻搜索前調(diào)用void CAnt:Init() for (int i=0;iN_CITY_COUNT;i+) m_nAllowedCityi=1; /設(shè)置全部城市為沒(méi)有去過(guò) m_nPathi=0; /螞蟻?zhàn)叩穆窂饺吭O(shè)置為0 /螞蟻?zhàn)哌^(guò)的路徑長(zhǎng)度設(shè)置為0 m_dbPathLength=0.0; /隨機(jī)選擇一個(gè)出發(fā)城市 m_nCurCityNo=rnd(0,N_CITY_COUNT); /把出發(fā)城市保存入路徑數(shù)組中 m_nPath0=m_nCurCityNo; /標(biāo)識(shí)出發(fā)城市為已經(jīng)去過(guò)了 m_nAllowedCitym_nCurCityNo=0; /已經(jīng)去過(guò)的城市數(shù)量設(shè)置為1 m_nMovedCityCount=1;/選擇下一個(gè)城市/返回值 為城市編號(hào)int CAnt:ChooseNextCity() int nSelectedCity=-1; /返回結(jié)果，先暫時(shí)把其設(shè)置為-1 /= /計(jì)算當(dāng)前城市和沒(méi)去過(guò)的城市之間的信息素總和 double dbTotal=0.0; double probN_CITY_COUNT; /保存各個(gè)城市被選中的概率 for (int i=0;i 0.0) /總的信息素值大于0 dbTemp=rnd(0.0,dbTotal); /取一個(gè)隨機(jī)數(shù) for (int i=0;iN_CITY_COUNT;i+) if (m_nAllowedCityi = 1) /城市沒(méi)去過(guò) dbTemp=dbTemp-probi; /這個(gè)操作相當(dāng)于轉(zhuǎn)動(dòng)輪盤，如果對(duì)輪盤選擇不熟悉，仔細(xì)考慮一下 if (dbTemp 0.0) /輪盤停止轉(zhuǎn)動(dòng)，記下城市編號(hào)，直接跳出循環(huán) nSelectedCity=i; break; /= /如果城市間的信息素非常小 ( 小到比double能夠表示的最小的數(shù)字還要小 ) /那么由于浮點(diǎn)運(yùn)算的誤差原因，上面計(jì)算的概率總和可能為0 /會(huì)出現(xiàn)經(jīng)過(guò)上述操作，沒(méi)有城市被選擇出來(lái) /出現(xiàn)這種情況，就把第一個(gè)沒(méi)去過(guò)的城市作為返回結(jié)果 /題外話：剛開(kāi)始看的時(shí)候，下面這段代碼困惑了我很長(zhǎng)時(shí)間，想不通為何要有這段代碼，后來(lái)才搞清楚。 if (nSelectedCity = -1) for (int i=0;iN_CITY_COUNT;i+) if (m_nAllowedCityi = 1) /城市沒(méi)去過(guò) nSelectedCity=i; break; /= /返回結(jié)果，就是城市的編號(hào) return nSelectedCity;/螞蟻在城市間移動(dòng)void CAnt:Move() int nCityNo=ChooseNextCity(); /選擇下一個(gè)城市 m_nPathm_nMovedCityCount=nCityNo; /保存螞蟻?zhàn)叩穆窂?m_nAllowedCitynCityNo=0;/把這個(gè)城市設(shè)置成已經(jīng)去過(guò)了 m_nCurCityNo=nCityNo; /改變當(dāng)前所在城市為選擇的城市 m_nMovedCityCount+; /已經(jīng)去過(guò)的城市數(shù)量加1/螞蟻進(jìn)行搜索一次void CAnt:Search() Init(); /螞蟻搜索前，先初始化 /如果螞蟻去過(guò)的城市數(shù)量小于城市數(shù)量，就繼續(xù)移動(dòng) while (m_nMovedCityCount N_CITY_COUNT) Move(); /完成搜索后計(jì)算走過(guò)的路徑長(zhǎng)度 CalPathLength();/計(jì)算螞蟻?zhàn)哌^(guò)的路徑長(zhǎng)度void CAnt:CalPathLength() m_dbPathLength=0.0; /先把路徑長(zhǎng)度置0 int 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; /定義一個(gè)螞蟻?zhàn)兞?，用?lái)保存搜索過(guò)程中的最優(yōu)結(jié)果 /該螞蟻不參與搜索，只是用來(lái)保存最優(yōu)結(jié)果public: /初始化數(shù)據(jù) void InitData(); /開(kāi)始搜索 void Search(); /更新環(huán)境信息素 void UpdateTrial();/構(gòu)造函數(shù)CTsp:CTsp(void)CTsp:CTsp(void)/初始化數(shù)據(jù)void CTsp:InitData() /先把最優(yōu)螞蟻的路徑長(zhǎng)度設(shè)置成一個(gè)很大的值 m_cBestAnt.m_dbPathLength=DB_MAX; /計(jì)算兩兩城市間距離 double dbTemp=0.0; for (int i=0;iN_CITY_COUNT;i+) for (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)境信息素，先把城市間的信息素設(shè)置成一樣 /這里設(shè)置成1.0，設(shè)置成多少對(duì)結(jié)果影響不是太大，對(duì)算法收斂速度有些影響 for (int i=0;iN_CITY_COUNT;i+) for (int j=0;jN_CITY_COUNT;j+) g_Trialij=1.0; /更新環(huán)境信息素void CTsp:UpdateTrial() /臨時(shí)數(shù)組，保存各只螞蟻在兩兩城市間新留下的信息素 double dbTempAryN_CITY_COUNTN_CITY_COUNT; memset(dbTempAry,0,sizeof(dbTempAry); /先全部設(shè)置為0 /計(jì)算新增加的信息素,保存到臨時(shí)數(shù)組里 int m=0; int n=0; for (int i=0;iN_ANT_COUNT;i+) /計(jì)算每只螞蟻留下的信息素 for (int j=1;jN_CITY_COUNT;j+) m=m_cAntAryi.m_nPathj; n=m_cAntAryi.m_nPathj-1; dbTempArynm=dbTempArynm+DBQ/m_cAntAryi.m_dbPathLength; dbTempArymn=dbTempArynm; /最后城市和開(kāi)始城市之間的信息素 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+dbTempAryij; /最新的環(huán)境信息素 = 留存的信息素 + 新留下的信息素 void CTsp:Search() char cBuf256; /打印信息用 /在迭代次數(shù)內(nèi)進(jìn)行循環(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)路徑的長(zhǎng)度 sprintf(cBuf,n%d %.0f,i+1,m_cBestAnt.m_dbPathLength); printf(cBuf); int main() /用當(dāng)前時(shí)間點(diǎn)初始化隨機(jī)種子，防止每次運(yùn)行的結(jié)果都相同 time_t tm; time(&tm); unsigned int nSeed=(unsigned int)tm; srand(nSeed); /開(kāi)始搜索 CTsp tsp; tsp.InitData(); /初始化 tsp.Search(); /開(kāi)始搜索 /輸出結(jié)果 print