基本蟻群算法的c源程序

1、基本蟻群算法的C+源程序 2006-12-01 09:36關(guān)鍵詞： 蟻群算法 C+ 源程 序 ACS基本蟻群算法的C+源程序/ 基本蟻群算法程序/ 程序在 vc+6.0 下面同過(guò)，對(duì)原來(lái)的做了一點(diǎn)修改。/ 你可以使用本代碼，如果感到對(duì)你有用的話(huà)，請(qǐng)通知作者，作者會(huì)很高興/ 通訊地址： fashionxu/by FashionXu#include "stdafx.h"#include#include#include#include螞蟻數(shù)量城市數(shù)量 最大跌代次數(shù)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)/獲得隨機(jī)數(shù)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;/沒(méi)有走過(guò)的城市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