蚁群算法(C++版)

/ AO.cpp : 定义控制台应用程序的入口点。#pragma once#include #include #include const double ALPHA=1.0; /启发因子，信息素的重要程度const double BETA=2.0; /期望因子，城市间距离的重要程度const double ROU=0.5; /信息素残留参数const int N_ANT_COUNT=34; /蚂蚁数量const int N_IT_COUNT=1000; /迭代次数const int N_CITY_COUNT=51; /城市数量const double DBQ=100.0; /总的信息素const double DB_MAX=10e9; /一个标志数，10的9次方double g_TrialN_CITY_COUNTN_CITY_COUNT; /两两城市间信息素，就是环境信息素double g_DistanceN_CITY_COUNTN_CITY_COUNT; /两两城市间距离/eil51.tsp城市坐标数据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;/返回指定范围内的随机整数int rnd(int nLow,int nUpper) return nLow+(nUpper-nLow)*rand()/(RAND_MAX+1);/返回指定范围内的随机浮点数double rnd(double dbLow,double dbUpper) double dbTemp=rand()/(double)RAND_MAX+1.0); return dbLow+dbTemp*(dbUpper-dbLow);/返回浮点数四舍五入取整后的浮点数double ROUND(double dbA) return (double)(int)(dbA+0.5);/定义蚂蚁类class CAntpublic: CAnt(void); CAnt(void);public: int m_nPathN_CITY_COUNT; /蚂蚁走的路径 double m_dbPathLength; /蚂蚁走过的路径长度 int m_nAllowedCityN_CITY_COUNT; /没去过的城市 int m_nCurCityNo; /当前所在城市编号 int m_nMovedCityCount; /已经去过的城市数量public: int ChooseNextCity(); /选择下一个城市 void Init(); /初始化 void Move(); /蚂蚁在城市间移动 void Search(); /搜索路径 void CalPathLength(); /计算蚂蚁走过的路径长度;/构造函数CAnt:CAnt(void)/析构函数CAnt:CAnt(void)/初始化函数，蚂蚁搜索前调用void CAnt:Init() for (int i=0;iN_CITY_COUNT;i+) m_nAllowedCityi=1; /设置全部城市为没有去过 m_nPathi=0; /蚂蚁走的路径全部设置为0 /蚂蚁走过的路径长度设置为0 m_dbPathLength=0.0; /随机选择一个出发城市 m_nCurCityNo=rnd(0,N_CITY_COUNT); /把出发城市保存入路径数组中 m_nPath0=m_nCurCityNo; /标识出发城市为已经去过了 m_nAllowedCitym_nCurCityNo=0; /已经去过的城市数量设置为1 m_nMovedCityCount=1;/选择下一个城市/返回值 为城市编号int CAnt:ChooseNextCity() int nSelectedCity=-1; /返回结果，先暂时把其设置为-1 /= /计算当前城市和没去过的城市之间的信息素总和 double dbTotal=0.0; double probN_CITY_COUNT; /保存各个城市被选中的概率 for (int i=0;i 0.0) /总的信息素值大于0 dbTemp=rnd(0.0,dbTotal); /取一个随机数 for (int i=0;iN_CITY_COUNT;i+) if (m_nAllowedCityi = 1) /城市没去过 dbTemp=dbTemp-probi; /这个操作相当于转动轮盘，如果对轮盘选择不熟悉，仔细考虑一下 if (dbTemp 0.0) /轮盘停止转动，记下城市编号，直接跳出循环 nSelectedCity=i; break; /= /如果城市间的信息素非常小 ( 小到比double能够表示的最小的数字还要小 ) /那么由于浮点运算的误差原因，上面计算的概率总和可能为0 /会出现经过上述操作，没有城市被选择出来 /出现这种情况，就把第一个没去过的城市作为返回结果 /题外话：刚开始看的时候，下面这段代码困惑了我很长时间，想不通为何要有这段代码，后来才搞清楚。 if (nSelectedCity = -1) for (int i=0;iN_CITY_COUNT;i+) if (m_nAllowedCityi = 1) /城市没去过 nSelectedCity=i; break; /= /返回结果，就是城市的编号 return nSelectedCity;/蚂蚁在城市间移动void CAnt:Move() int nCityNo=ChooseNextCity(); /选择下一个城市 m_nPathm_nMovedCityCount=nCityNo; /保存蚂蚁走的路径 m_nAllowedCitynCityNo=0;/把这个城市设置成已经去过了 m_nCurCityNo=nCityNo; /改变当前所在城市为选择的城市 m_nMovedCityCount+; /已经去过的城市数量加1/蚂蚁进行搜索一次void CAnt:Search() Init(); /蚂蚁搜索前，先初始化 /如果蚂蚁去过的城市数量小于城市数量，就继续移动 while (m_nMovedCityCount N_CITY_COUNT) Move(); /完成搜索后计算走过的路径长度 CalPathLength();/计算蚂蚁走过的路径长度void CAnt:CalPathLength() m_dbPathLength=0.0; /先把路径长度置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; /加上从最后城市返回出发城市的距离 n=m_nPath0; m_dbPathLength=m_dbPathLength+g_Distancemn; /tsp类class CTsppublic: CTsp(void); CTsp(void);public: CAnt m_cAntAryN_ANT_COUNT; /蚂蚁数组 CAnt m_cBestAnt; /定义一个蚂蚁变量，用来保存搜索过程中的最优结果 /该蚂蚁不参与搜索，只是用来保存最优结果public: /初始化数据 void InitData(); /开始搜索 void Search(); /更新环境信息素 void UpdateTrial();/构造函数CTsp:CTsp(void)CTsp:CTsp(void)/初始化数据void CTsp:InitData() /先把最优蚂蚁的路径长度设置成一个很大的值 m_cBestAnt.m_dbPathLength=DB_MAX; /计算两两城市间距离 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); /初始化环境信息素，先把城市间的信息素设置成一样 /这里设置成1.0，设置成多少对结果影响不是太大，对算法收敛速度有些影响 for (int i=0;iN_CITY_COUNT;i+) for (int j=0;jN_CITY_COUNT;j+) g_Trialij=1.0; /更新环境信息素void CTsp:UpdateTrial() /临时数组，保存各只蚂蚁在两两城市间新留下的信息素 double dbTempAryN_CITY_COUNTN_CITY_COUNT; memset(dbTempAry,0,sizeof(dbTempAry); /先全部设置为0 /计算新增加的信息素,保存到临时数组里 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; dbTempArynm=dbTempArynm+DBQ/m_cAntAryi.m_dbPathLength; dbTempArymn=dbTempArynm; /最后城市和开始城市之间的信息素 n=m_cAntAryi.m_nPath0; dbTempArynm=dbTempArynm+DBQ/m_cAntAryi.m_dbPathLength; dbTempArymn=dbTempArynm; /= /更新环境信息素 for (int i=0;iN_CITY_COUNT;i+) for (int j=0;jN_CITY_COUNT;j+) g_Trialij=g_Trialij*ROU+dbTempAryij; /最新的环境信息素 = 留存的信息素 + 新留下的信息素 void CTsp:Search() char cBuf256; /打印信息用 /在迭代次数内进行循环 for (int i=0;iN_IT_COUNT;i+) /每只蚂蚁搜索一遍 for (int j=0;jN_ANT_COUNT;j+) m_cAntAryj.Search(); /保存最佳结果 for (int j=0;jN_ANT_COUNT;j+) if (m_cAntAryj.m_dbPathLength m_cBestAnt.m_dbPathLength) m_cBestAnt=m_cAntAryj; /更新环境信息素 UpdateTrial(); /输出目前为止找到的最优路径的长度 sprintf(cBuf,n%d %.0f,i+1,m_cBestAnt.m_dbPathLength); printf(cBuf); int main() /用当前时间点初始化随机种子，防止每次运行的结果都相同 time_t tm; time(&tm); unsigned int nSeed=(unsigned int)tm; srand(nSeed); /开始搜索 CTsp tsp; tsp.InitData(); /初始化 tsp.Search(); /开始搜索 /输出结果 print