蚁群算法C++实现,解决TSP问题

1C++基本蚁群算法代码#includeiostream#includefstream#includemath.h#includetime.husingnamespacestd;constintiAntCount=34;//antnumbersconstintiCityCount=51;constintiItCount=2000;constdoubleQ=100;constdoublealpha=1;constdoublebeta=5;constdoublerou=0.5;intbesttour[iCityCount];doublernd(intlow,doubleuper){doublep=(rand()/(double)RAND_MAX)*((uper)-(low))+(low);return(p);};intrnd(intuper){return(rand()%uper);};classGInfo{public:doublem_dDeltTrial[iCityCount][iCityCount];doublem_dTrial[iCityCount][iCityCount];doubledistance[iCityCount][iCityCount];};GInfoMap;classant{private:intChooseNextCity();doubleprob[iCityCount];intm_iCityCount;intAllowedCity[iCityCount];public:voidaddcity(intcity);inttabu[iCityCount];voidClear();voidUpdateResult();doublem_dLength;doublem_dShortest;voidmove();ant();voidmove2last();};voidant::move2last(){inti;for(i=0;iiCityCount;i++)if(AllowedCity[i]==1){addcity(i);break;}}voidant::Clear(){m_dLength=0;inti;for(i=0;iiCityCount;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;inti;for(i=0;iiCityCount;i++){AllowedCity[i]=1;prob[i]=0;}}voidant::addcity(intcity){//addcitytotabu;tabu[m_iCityCount]=city;m_iCityCount++;AllowedCity[city]=0;}intant::ChooseNextCity(){//Updatetheprobabilityofpathselection//selectapathfromtabu[m_iCityCount-1]tonextinti;intj=10000;doubletemp=0;intcurCity=tabu[m_iCityCount-1];for(i=0;iiCityCount;i++){if((AllowedCity[i]==1)){temp+=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha);}}doublesel=0;for(i=0;iiCityCount;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];}elseprob[i]=0;}doublemRate=rnd(0,sel);doublemSelect=0;for(i=0;iiCityCount;i++){if((AllowedCity[i]==1))mSelect+=prob[i];if(mSelect=mRate){j=i;break;}}if(j==10000){temp=-1;for(i=0;iiCityCount;i++){if((AllowedCity[i]==1))if(temppow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha)){temp=pow((1.0/Map.distance[curCity][i]),beta)*pow((Map.m_dTrial[curCity][i]),alpha);j=i;}}}returnj;}voidant::UpdateResult(){//Updatethelengthoftourinti;for(i=0;iiCityCount-1;i++)m_dLength+=Map.distance[tabu[i]][tabu[i+1]];m_dLength+=Map.distance[tabu[iCityCount-1]][tabu[0]];}voidant::move(){//theantmovetonexttownandaddtownIDtotabu.intj;j=ChooseNextCity();addcity(j);}classproject{public:voidUpdateTrial();doublem_dLength;voidinitmap();作者：cwyhs0012007-4-1018:49回复此发言2C++基本蚁群算法代码antants[iAntCount];voidGetAnt();voidStartSearch();project();};voidproject::UpdateTrial(){//calculatethechangesoftrialinformationinti;intj;for(i=0;iiAntCount;i++){for(j=0;jiCityCount-1;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;iiCityCount;i++){for(j=0;jiCityCount;j++){Map.m_dTrial[i][j]=(rou*Map.m_dTrial[i][j]+Map.m_dDeltTrial[i][j]);Map.m_dDeltTrial[i][j]=0;}}}voidproject::initmap(){inti;intj;for(i=0;iiCityCount;i++)for(j=0;jiCityCount;j++){Map.m_dTrial[i][j]=1;Map.m_dDeltTrial[i][j]=0;}}project::project(){//initialmap,readmapinfomationfromfile.et.initmap();m_dLength=10e9;ifstreamin(eil51.tsp);structcity{intnum;intx;inty;}cc[iCityCount];for(inti=0;iiCityCount;i++){incc[i].numcc[i].xcc[i].y;besttour[i]=0;}intj;for(i=0;iiCityCount;i++)for(j=0;jiCityCount;j++){{Map.distance[i][j]=sqrt(pow((cc[i].x-cc[j].x),2)+pow((cc[i].y-cc[j].y),2));}}}voidproject::GetAnt(){//randomlyputantintomapinti=0;intcity;srand((unsigned)time(NULL)+rand());for(i=0;iiAntCount;i++){city=rnd(iCityCount);ants[i].addcity(city);}}voidproject::StartSearch(){//begintofindbestsolutionintmax=0;//everyanttourstimesinti;intj;doubletemp;inttemptour[iCityCount];while(maxiItCount){for(j=0;jiAntCount;j++){for(i=0;iiCityCount-1;i++)ants[j].move();}for(j=0;jiAntCount;j++){ants[j].move2last();ants[j].UpdateResult();}//findoutthebestsolutionofthestepandputitintotempintt;temp=ants[0].m_dLength;for(t=0;tiCityCount;t++)temptour[t]=ants[0].tabu[t];for(j=0;jiAntCount;j++){if(tempants[j].m_dLength){temp=ants[j].m_dLength;for(t=0;tiCityCount;t++)temptour[t]=ants[j].tabu[t];}}if(tempm_dLength){m_dLength=temp;for(t=0;tiCityCount;t++)besttour[t]=temptour[t];}printf(%d:%f\n,max,m_dLength);UpdateTrial();for(j=0;jiAntCount;j++)ants[j].Clear();max++;}printf(Theshortesttoureis:%f\n,m_dLength);for(intt=0;tiCityCount;t++)printf(%d,besttour[t]);}intmain(){projectTSP;TSP.GetAnt();TSP.StartSearch();return0;}