|
|
马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？我要加入
x
- //基本蚁群算法程序
- //程序在vc++6.0下面同过，对原来的做了一点修改。
- //你可以使用本代码，如果感到对你有用的话，请通知作者，作者会很高兴。
- //通讯地址：[email]fashionxu@163.com[/email]
- //by FashionXu
- #include
- #include
- #include
- #include
- using namespace std;
- const int iAntCount=34;//ant numbers
- const int iCityCount=51;
- const int iItCount=2000;
- const double Q=100;
- const double alpha=1;
- const double beta=5;
- const double rou=0.5;
- int besttour[iCityCount];
- 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 GInfo
- {
- public:
- double m_dDeltTrial[iCityCount][iCityCount];//信息素增量
- double m_dTrial[iCityCount][iCityCount];//信息素痕迹
- double distance[iCityCount][iCityCount];//距离
- };
- GInfo Map;
- class ant
- {
- private:
- int ChooseNextCity();
- double prob[iCityCount];//转移概率
- int m_iCityCount;
- int AllowedCity[iCityCount];
- public:
- void addcity(int city);
- int tabu[iCityCount];//行走路径
- void Clear();
- void UpdateResult();
- double m_dLength;
- double m_dShortest;
- void move();
- ant();
- void move2last();
- };
- void ant::move2last()
- {
- int i;
- for(i=0;i if (AllowedCity[i]==1)
- {
- addcity(i);
- break;
- }
- }
- void ant::Clear()
- {
- m_dLength=0;
- int i;
- for(i=0;i {
- prob[i]=0;
- AllowedCity[i]=1;
- }
- i=tabu[iCityCount-1];
- m_iCityCount=0;
- addcity(i);
- }
- ant::ant()
- {
- m_dLength=m_dShortest=0;
- m_iCityCount=0;
- int i;
- for(i=0;i {
- AllowedCity[i]=1;
- prob[i]=0;
- }
- }
- void ant::addcity(int city)
- {
- //add city to tabu;
- tabu[m_iCityCount]=city;
- m_iCityCount++;
- AllowedCity[city]=0;
- }
- int ant::ChooseNextCity()
- {
- //Update the probability of path selection
- //select a path from tabu[m_iCityCount-1] to next
- int i;
- int j=10000;
- double temp=0;
- int curCity=tabu[m_iCityCount-1];
- for (i=0;i
- {
- if((AllowedCity[i]==1))
- {
- temp+=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha);
- //距离 //残留信息量
- }
- }
- double sel=0;
- for (i=0;i
- {
- if((AllowedCity[i]==1))
- {
- prob[i]=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha)/temp;
- sel+=prob[i];
- }
- else
- prob[i]=0;
- }
- double mRate=rnd(0,sel);
- double mSelect=0;
- for ( i=0;i
- {
- if((AllowedCity[i]==1))
- mSelect+=prob[i] ;
- if (mSelect>=mRate)
- {j=i;break;}
- }
- if (j==10000)
- {
- temp=-1;
- for (i=0;i
- {
- if((AllowedCity[i]==1))
- if (temp
- {
- temp=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha);
- j=i;
- }
- }
- }
- return j;
- }
- void ant::UpdateResult()
- {
- // Update the length of tour
- int i;
- for(i=0;i m_dLength+=Map.distance[tabu[i]][tabu[i+1]];
- m_dLength+=Map.distance[tabu[iCityCount-1]][tabu[0]];
- }
- void ant::move()
- {
- //the ant move to next town and add town ID to tabu.
- int j;
- j=ChooseNextCity();
- addcity(j);
- }
- class project
- {
- public:
- void UpdateTrial();
- double m_dLength;
- void initmap();
- ant ants[iAntCount];
- void GetAnt();
- void StartSearch();
- project();
- };
- void project::UpdateTrial()
- {
- //calculate the changes of trial information
- int i;
- int j;
- for(i=0;i {
- for (j=0;j {
- Map.m_dDeltTrial[ants[i].tabu[j]][ants[i].tabu[j+1]]+=Q/ants[i].m_dLength ;
- Map.m_dDeltTrial[ants[i].tabu[j+1]][ants[i].tabu[j]]+=Q/ants[i].m_dLength;
- }
- Map.m_dDeltTrial[ants[i].tabu[iCityCount-1]][ants[i].tabu[0]]+=Q/ants[i].m_dLength;
- Map.m_dDeltTrial[ants[i].tabu[0]][ants[i].tabu[iCityCount-1]]+=Q/ants[i].m_dLength;
- }
- for (i=0;i {
- for (j=0;j {
- Map.m_dTrial[i][j]=(rou*Map.m_dTrial[i][j]+Map.m_dDeltTrial[i][j] );
- Map.m_dDeltTrial[i][j]=0;
- }
- }
- }
- void project::initmap()
- {
- int i;
- int j;
- for(i=0;i for (j=0;j {
- Map.m_dTrial[i][j]=1;
- Map.m_dDeltTrial[i][j]=0;
- }
- }
- project::project()
- {
- //initial map,read map infomation from file . et.
- initmap();
- m_dLength=10e9;
- ifstream in("eil51.tsp");
- struct city
- {
- int num;
- int x;
- int y;
- }cc[iCityCount];
-
- for (int i=0;i
- {
- in>>cc[i].num>>cc[i].x>>cc[i].y;
- besttour[i]=0;
- }
- int j;
- for(i=0;i for (j=0;j
- {
- {
- Map.distance[i][j]=sqrt(pow((cc[i].x-cc[j].x),2)+pow((cc[i].y-cc[j].y),2));
- }
- }
- }
- void project::GetAnt()
- {
- //randomly put ant into map
- int i=0;
- int city;
- srand( (unsigned)time( NULL ) +rand());
- for (i=0;i {
- city=rnd(iCityCount);
- ants[i].addcity(city);
- }
- }
- void project::StartSearch()
- {
- //begin to find best solution
- int max=0;//every ant tours times
- int i;
- int j;
- double temp;
- int temptour[iCityCount];
- while (max
- {
- for(j=0;j
- {
- for (i=0;i ants[j].move();
- }
- for(j=0;j
- {
- ants[j].move2last();
- ants[j].UpdateResult ();
- }
- //find out the best solution of the step and put it into temp
- int t;
- temp=ants[0].m_dLength;
- for (t=0;t
- temptour[t]=ants[0].tabu[t];
- for(j=0;j
- {
- if (temp>ants[j].m_dLength)
- {
- temp=ants[j].m_dLength;
- for ( t=0;t temptour[t]=ants[j].tabu[t];
- }
- }
- if(temp
- m_dLength=temp;
- for ( t=0;t
- {
- besttour[t]=temptour[t];
- }
- printf("%d : %f\n",max,m_dLength);
- UpdateTrial();
- for(j=0;j ants[j].Clear();
- max++;
- }
- printf("The shortest toure is : %f\n",m_dLength);
- for ( int t=0;t printf(" %d ",besttour[t]);
- }
- int main()
- {
- project TSP;
- TSP.GetAnt();
- TSP.StartSearch();
- return 0;
- }
[ 本帖最后由 风花雪月 于 2006-11-20 08:43 编辑 ] |
评分
-
1
查看全部评分
-
|
发表于 2006-11-15 21:01
提升卡
变色卡
显身卡
