【2019年整理】蚁群算法源代码

viewplaincopytoclipboardprint?/**********************************作者:陈杰*单位:四川大学计算机学院*邮件地址:[e-mail]*完成时间:2008年3月*********************************/#includeiostream#includemath.h#includetime.husingnamespacestd;//该程序是以蚁群系统为模型写的蚁群算法程序(强调：非蚂蚁周模型)，以三个著名的TSP问题为测试对象//通过微调参数，都可以获得较好的解/*//----------(1)问题一：Oliver30城市TSP问题best_length=423.7406;------------------------//该程序最好的结果是423.741，可运行多次获得//城市节点数目#defineN30//城市坐标doubleC[N][2]={{2,99},{4,50},{7,64},{13,40},{18,54},{18,40},{22,60},{24,42},{25,62},{25,38},{37,84},{41,94},{41,26},{44,35},{45,21},{54,67},{54,62},{58,35},{58,69},{62,32},{64,60},{68,58},{71,44},{71,71},{74,78},{82,7},{83,46},{83,69},{87,76},{91,38}};//----------上面参数是固定的，下面的参数是可变的-----------//蚂蚁数量#defineM30//最大循环次数NcMaxintNcMax=500;//信息启发因子，期望启发式因子，全局信息素挥发参数，局部信息素挥发参数,状态转移公式中的q0doublealpha=2,beta=3,rou=0.1,alpha1=0.1,qzero=0.01;//-----------问题一结束------------------------------------------------------------------------*//*//----------(2)问题二：Elion50城市TSP问题best_length=427.96;----------------------------//该程序最好的结果是428.468，可运行多次获得//城市节点数目#defineN50//城市坐标doubleC[N][2]={{5,64},{5,25},{5,6},{7,38},{8,52},{10,17},{12,42},{13,13},{16,57},{17,33},{17,63},{20,26},{21,47},{21,10},{25,32},{25,55},{27,68},{27,23},{30,48},{30,15},{31,62},{31,32},{32,22},{32,39},{36,16},{37,69},{37,52},{38,46},{39,10},{40,30},{42,57},{42,41},{43,67},{45,35},{46,10},{48,28},{49,49},{51,21},{52,33},{52,41},{52,64},{56,37},{57,58},{58,27},{58,48},{59,15},{61,33},{62,42},{62,63},{63,69}};//----------上面参数是固定的，下面的参数是可变的-----------//蚂蚁数量#defineM50//最大循环次数NcMaxintNcMax=1000;//信息启发因子，期望启发式因子，全局信息素挥发参数，局部信息素挥发参数,状态转移公式中的q0doublealpha=2,beta=4,rou=0.1,alpha1=0.1,qzero=0.01;//-----------问题二结束------------------------------------------------------------------------*///----------(3)问题三：Elion75城市TSP问题best_length=542.31;//该程序最好的结果是542.309，可运行多次获得//城市节点数目#defineN75//城市坐标doubleC[N][2]={{6,25},{7,43},{9,56},{10,70},{11,28},{12,17},{12,38},{15,5},{15,14},{15,56},{16,19},{17,64},{20,30},{21,48},{21,45},{21,36},{22,53},{22,22},{26,29},{26,13},{26,59},{27,24},{29,39},{30,50},{30,20},{30,60},{31,76},{33,34},{33,44},{35,51},{35,16},{35,60},{36,6},{36,26},{38,33},{40,37},{40,66},{40,60},{40,20},{41,46},{43,26},{44,13},{45,42},{45,35},{47,66},{48,21},{50,30},{50,40},{50,50},{50,70},{50,4},{50,15},{51,42},{52,26},{54,38},{54,10},{55,34},{55,45},{55,50},{55,65},{55,57},{55,20},{57,72},{59,5},{60,15},{62,57},{62,48},{62,35},{62,24},{64,4},{65,27},{66,14},{66,8},{67,41},{70,64}};//----------上面参数是固定的，下面的参数是可变的-----------//蚂蚁数量#defineM75//最大循环次数NcMaxintNcMax=1000;//信息启发因子，期望启发式因子，全局信息素挥发参数，局部信息素挥发参数,状态转移公式中的q0doublealpha=2,beta=5,rou=0.1,alpha1=0.1,qzero=0.1;//-----------问题三结束------------------------------------------------------------------------//===========================================================================================================//局部更新时候使用的的常量，它是由最近邻方法得到的一个长度//什么是最近邻方法?:)就是从源节点出发，每次选择一个距离最短的点来遍历所有的节点得到的路径//每个节点都可能作为源节点来遍历doubleLnn;//矩阵表示两两城市之间的距离doubleallDistance[N][N];//计算两个城市之间的距离doublecalculateDistance(inti,intj){returnsqrt(pow((C[i][0]-C[j][0]),2.0)+pow((C[i][1]-C[j][1]),2.0));}//由矩阵表示两两城市之间的距离voidcalculateAllDistance(){for(inti=0;iN;i++){for(intj=0;jN;j++){if(i!=j){allDistance[i][j]=calculateDistance(i,j);allDistance[j][i]=allDistance[i][j];}}}}//获得经过n个城市的路径长度doublecalculateSumOfDistance(int*tour){doublesum=0;for(inti=0;iN;i++){introw=*(tour+2*i);intcol=*(tour+2*i+1);sum+=allDistance[row][col];}returnsum;}classACSAnt;classAntColonySystem{private:doubleinfo[N][N],visible[N][N];//节点之间的信息素强度,节点之间的能见度public:AntColonySystem(){}//计算当前节点到下一节点转移的概率doubleTransition(inti,intj);//局部更新规则voidUpdateLocalPathRule(inti,intj);//初始化voidInitParameter(doublevalue);//全局信息素更新voidUpdateGlobalPathRule(int*bestTour,intglobalBestLength);};//计算当前节点到下一节点转移的概率doubleAntColonySystem::Transition(inti,intj){if(i!=j){return(pow(info[i][j],alpha)*pow(visible[i][j],beta));}else{return0.0;}}//局部更新规则voidAntColonySystem::UpdateLocalPathRule(inti,intj){info[i][j]=(1.0-alpha1)*info[i][j]+alpha1*(1.0/(N*Lnn));info[j][i]=info[i][j];}//初始化voidAntColonySystem::InitParameter(doublevalue){//初始化路径上的信息素强度tao0for(inti=0;iN;i++){for(intj=0;jN;j++){info[i][j]=value;info[j][i]=value;if(i!=j){visible[i][j]=1.0/allDistance[i][j];visible[j][i]=visible[i][j];}}}}//全局信息素更新voidAntColonySystem::UpdateGlobalPathRule(int*bestTour,intglobalBestLength){for(inti=0;iN;i++){introw=*(bestTour+2*i);intcol=*(bestTour+2*i+1);info[row][col]=(1.0-rou)*info[row][col]+rou*(1.0/globalBestLength);info[col][row]=info[row][col];}}classACSAnt{private:AntColonySystem*antColony;protected:intstartCity,cururentCity;//初始城市编号，当前城市编号intallowed[N];//禁忌表intTour[N][2];//当前路径intcurrentTourIndex;//当前路径索引，从0开始，存储蚂蚁经过城市的编号public:ACSAnt(AntColonySystem*acs,intstart){antColony=acs;startCity=start;}//开始搜索int*Search();//选择下一节点intChoose();//移动到下一节点voidMoveToNextCity(intnextCity);};//开始搜索int*ACSAnt::Search(){cururentCity=startCity;inttoCity;currentTourIndex=0;for(inti=0;iN;i++){allowed[i]=1;}allowed[cururentCity]=0;intendCity;i