基本蚁群算法的c源程序

1、基本蚁群算法的C+源程序 2006-12-01 09:36关键词： 蚁群算法 C+ 源程 序 ACS基本蚁群算法的C+源程序/ 基本蚁群算法程序/ 程序在 vc+6.0 下面同过，对原来的做了一点修改。/ 你可以使用本代码，如果感到对你有用的话，请通知作者，作者会很高兴/ 通讯地址： fashionxu/by FashionXu#include "stdafx.h"#include#include#include#include蚂蚁数量城市数量 最大跌代次数using namespace std;const int iAntCount=34;/ const int iCit

2、yCount=51;/ const int iItCount=2000;/ const double Q=100;const double alpha=1; const double beta=5;const double rou=0.5;int besttouriCityCount;/最有路径列表double rnd(int low,double uper)/获得随机数double p=(rand()/(double)RAND_MAX)*(uper)-(low)+(low); return (p);int rnd(int uper) return (rand()%uper);class GI

3、nfo/tsp 地图信息，包含了信息素，城市距离，和信息素变化矩阵 public:double m_dDeltTrialiCityCountiCityCount;double m_dTrialiCityCountiCityCount;double distanceiCityCountiCityCount;GInfo Map;class antprivate:int ChooseNextCity();/选择城市double probiCityCount;int m_iCityCount;int AllowedCityiCityCount;/没有走过的城市public: void addcity(

4、int city); int tabuiCityCount;void Clear();void UpdateResult(); double m_dLength; double m_dShortest; void move();ant();void move2last();void ant:move2last()int i;for(i=0;i iCityCount;i+)if (AllowedCityi=1)addcity(i);break; void ant:Clear()m_dLength=0;int i;for(i=0; i iCityCount;i+)probi=0;AllowedCi

5、tyi=1;i=tabuiCityCount-1;m_iCityCount=0;addcity(i);ant:ant()m_dLength=m_dShortest=0; m_iCityCount=0;int i;for(i=0;i iCityCount;i+)AllowedCityi=1;probi=0;void ant:addcity(int city)/add city to tabu;tabum_iCityCount=city;m_iCityCount+;AllowedCitycity=0;int ant:ChooseNextCity()/Update the probability o

6、f path selection/select a path from tabum_iCityCount-1 to nextint i;int j=10000;double temp=0;int curCity=tabum_iCityCount-1;for (i=0;i iCityCount;i+)if(AllowedCityi=1)temp+=pow(1.0/Map.distancecurCityi),beta)*pow(Map.m_dTrialc urCityi),alpha);double sel=0;for (i=0;i iCityCount;i+)if(AllowedCityi=1)

7、probi=pow(1.0/Map.distancecurCityi),beta)*pow(Map.m_dTrial curCityi),alpha)/temp;sel+=probi;elseprobi=0;double mRate=rnd(0,sel);double mSelect=0;for ( i=0;i iCityCount;i+)if(AllowedCityi=1)mSelect+=probi ;if (mSelect>=mRate) j=i;break;if (j=10000)temp=-1;for (i=0;i iCityCount;i+)if(AllowedCityi=1

8、)if (temp temp=pow(1.0/Map.distancecurCityi),beta)*pow(Map.m_dTrial curCityi),alpha);j=i;return j;void ant:UpdateResult()/ Update the length of tourint i;for(i=0;i iCityCount-1;i+)m_dLength+=Map.distancetabuitabui+1; m_dLength+=Map.distancetabuiCityCount-1tabu0;void ant:move()/the ant move to next t

9、own and add town ID to j;j=ChooseNextCity();addcity(j);class projectpublic:void UpdateTrial();double m_dLength;void initmap();ant antsiAntCount;void GetAnt();void StartSearch();project();void project:UpdateTrial()/calculate the changes of trial informationint i;int j;for(i=0;i iAntCount;i+)

10、for (j=0;j iCityCount-1;j+) Map.m_dDeltTrialantsi.tabujantsi.tabuj+1+=Q/antsi.m _dLength ;Map.m_dDeltTrialantsi.tabuj+1antsi.tabuj+=Q/antsi.m_ dLength;Map.m_dDeltTrialantsi.tabuiCityCount-1antsi.tabu0+=Q/an tsi.m_dLength;Map.m_dDeltTrialantsi.tabu0antsi.tabuiCityCount-1+=Q/an tsi.m_dLength;for (i=0;

11、i iCityCount;i+)for (j=0;j iCityCount;j+)Map.m_dTrialij=(rou*Map.m_dTrialij+Map.m_dDeltTrialij );Map.m_dDeltTrialij=0;void project:initmap()int i;int j;for(i=0;i iCityCount;i+)for (j=0;j iCityCount;j+)Map.m_dTrialij=1;Map.m_dDeltTrialij=0; project:project()/initial map,read map infomation from file

12、. et. initmap();m_dLength=10e9;ifstream in("eil51.tsp");struct cityint num;int x;int y;cciCityCount;for (int i=0;i iCityCount;i+)in>>cci.num>>cci.x>>cci.y;besttouri=0;int j;for(i=0;i iCityCount;i+)for (j=0;j iCityCount;j+)Map.distanceij=sqrt(pow(cci.x-ccj.x),2)+pow(cci.y-

13、cc j.y),2);void project:GetAnt()/randomly put ant into mapint i=0;int city;srand( (unsigned)time( NULL ) +rand();for (i=0;i iAntCount;i+)city=rnd(iCityCount);antsi.addcity(city);void project:StartSearch()/begin to find best solutionint max=0;/every ant tours timesint i;int j;double temp;int temptour

14、iCityCount;while (max iItCount)for(j=0;j iAntCount;j+)for (i=0;i iCityCount-1;i+)antsj.move();for(j=0;j iAntCount;j+) antsj.move2last();antsj.UpdateResult ();/find out the best solution of the step and put it into temp int t;temp=ants0.m_dLength;for (t=0;t iCityCount;t+)temptourt=ants0.tabut;for(j=0

15、;j iAntCount;j+)if (temp antsj.m_dLength) temp=antsj.m_dLength;for ( t=0;t iCityCount;t+)temptourt=antsj.tabut;if(temp m_dLength)m_dLength=temp;for ( t=0;t iCityCount;t+)besttourt=temptourt;printf("%d : %fn",max,m_dLength); UpdateTrial();for(j=0;j iAntCount;j+) antsj.Clear();max+;printf("The shor