基于蟻群算法解決旅行商問題

學(xué)號(hào)：能力拓展訓(xùn)練題目基于蟻群算法解決tsp問題學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專業(yè)班級(jí)姓名指導(dǎo)教師2023——2023學(xué)年第2學(xué)期目錄TOC\o"1-3"\h\u27432一.介紹 ③計(jì)算。2.4流程邏輯開始開始初始化初始化設(shè)定設(shè)定集合,對(duì)每只螞蟻對(duì)每只螞蟻=計(jì)算螞蟻所走過的路程和計(jì)算螞蟻所走過的路程和更新最小路徑ｍｉｎ更新最小路徑ｍｉｎ對(duì)每條路徑計(jì)算對(duì)每條路徑計(jì)算設(shè)定ＮＣ＝ＮＣ＋１設(shè)定ＮＣ＝ＮＣ＋１acacbbacbacbNNYY清空所有的集合清空所有的集合得出最短路徑得出最短路徑N集合N集合滿YY結(jié)束結(jié)束圖12.5接口程序中的子函數(shù)：voidaddcity(intcity);voidClear();voidUpdateResult();voidmove();voidmove2last();voidshucout();voidUpdateTrial();voidinitmap();voidGetAnt();voidStartSearch();三．程序#include<iostream>#include<math.h>#include<time.h>usingnamespacestd;constintN_ANT_COUNT=34;//螞蟻數(shù)量，一般取值原那么為：城市數(shù)量/螞蟻數(shù)量=1.5左右constintN_CITY_COUNT=51;//城市數(shù)量intN_IT_COUNT;//=5000;//迭代次數(shù)，就是搜索次數(shù)constdoubleDB_Q=100;//總的信息素constdoubleDB_ALPHA=1;//信息素重要程度constdoubleDB_BETA=3;//這個(gè)數(shù)越大，那么螞蟻往信息素大的地方走的概率就越大constdoubleDB_ROU=0.5;//環(huán)境信息素?fù)]發(fā)速度intbesttour[N_CITY_COUNT];//最正確路徑列表//獲得指定范圍內(nèi)的一個(gè)隨機(jī)數(shù)doublernd(intlow,doubleuper){doublep=(rand()/(double)RAND_MAX)*((uper)-(low))+(low);return(p);};//獲得指定上限范圍內(nèi)的一個(gè)隨機(jī)數(shù)intrnd(intuper){return(rand()%uper);};//tsp地圖信息，包含了信息素，城市距離，和信息素變化矩陣classGInfo{public:doublem_dDeltTrial[N_CITY_COUNT][N_CITY_COUNT];//臨時(shí)保存信息素，更新環(huán)境信息素的時(shí)候使用，每只螞蟻周游完各個(gè)城市后開始計(jì)算doublem_dTrial[N_CITY_COUNT][N_CITY_COUNT];//城市間的信息素，就是環(huán)境信息素doubledistance[N_CITY_COUNT][N_CITY_COUNT];//城市間距離};GInfoMap;//定義螞蟻類classant{private:intChooseNextCity();//選擇下一個(gè)城市doubleprob[N_CITY_COUNT];//臨時(shí)變量數(shù)組，選擇下一個(gè)城市的時(shí)候，保存各個(gè)城市被選中的概率值intm_nCityCount;//記錄螞蟻已經(jīng)走過的城市數(shù)目intAllowedCity[N_CITY_COUNT];//沒有走過的城市，數(shù)組索引對(duì)應(yīng)城市編號(hào)public:doublem_dLength;doublem_dShortest;inttabu[N_CITY_COUNT];//記錄走過的城市，里面存的是城市的編號(hào)，數(shù)組索引表示走的順序。public:ant();voidaddcity(intcity);voidClear();voidUpdateResult();voidmove();voidmove2last();voidshucout();};//只剩下一個(gè)城市沒走過時(shí)才調(diào)用，直接移動(dòng)到最后一個(gè)城市voidant::move2last(){for(inti=0;i<N_CITY_COUNT;i++){if(AllowedCity[i]==1){addcity(i);break;}}}//清空數(shù)據(jù)，螞蟻周游完各個(gè)城市后，要重新開始周游各個(gè)城市時(shí)調(diào)用voidant::Clear(){m_dLength=0;for(inti=0;i<N_CITY_COUNT;i++){prob[i]=0;AllowedCity[i]=1;}i=tabu[N_CITY_COUNT-1];//用最后一個(gè)城市作為出發(fā)城市m_nCityCount=0;addcity(i);}//初始化ant::ant(){m_dLength=m_dShortest=0;m_nCityCount=0;for(inti=0;i<N_CITY_COUNT;i++){AllowedCity[i]=1;prob[i]=0;}}//增加一個(gè)城市到走過的城市數(shù)組中，并改變沒走過的城市數(shù)組中的標(biāo)志voidant::addcity(intcity){//addcitytotabu;tabu[m_nCityCount]=city;m_nCityCount++;AllowedCity[city]=0;}intant::ChooseNextCity(){//更新概率的路徑選擇//選擇一條路徑,從tabu[m_nCityCount-1]到下一個(gè)intj=10000;doubletemp=0.0;intcurCity=tabu[m_nCityCount-1];//當(dāng)前走到那個(gè)城市了//先計(jì)算當(dāng)前城市和沒有走過的城市，兩兩之間的信息素的總和for(inti=0;i<N_CITY_COUNT;i++){if(AllowedCity[i]==1){temp=temp+pow((1.0/Map.distance[curCity][i]),DB_BETA)*pow((Map.m_dTrial[curCity][i]),DB_ALPHA);}}//計(jì)算沒有走過的城市被選中的概率doublesel=0;for(i=0;i<N_CITY_COUNT;i++){if(AllowedCity[i]==1){prob[i]=pow((1.0/Map.distance[curCity][i]),DB_BETA)*pow((Map.m_dTrial[curCity][i]),DB_ALPHA)/temp;sel+=prob[i];}else{prob[i]=0;}}//下面的操作實(shí)際上就是遺傳算法中的輪盤選擇doublemRate=rnd(0,sel);doublemSelect=0;for(i=0;i<N_CITY_COUNT;i++){if(AllowedCity[i]==1){mSelect+=prob[i];}if(mSelect>=mRate){j=i;break;}}//這種情況只有在temp=0.0的時(shí)候才會(huì)出現(xiàn)if(j==10000){for(i=0;i<N_CITY_COUNT;i++){if(AllowedCity[i]==1){j=i;break;}}}returnj;}//計(jì)算周游完城市后，走過的路徑長(zhǎng)度voidant::UpdateResult(){//修正旅行距離for(inti=0;i<N_CITY_COUNT-1;i++){m_dLength+=Map.distance[tabu[i]][tabu[i+1]];}m_dLength+=Map.distance[tabu[N_CITY_COUNT-1]][tabu[0]];//最后城市和開始城市間的距離}//移動(dòng)到下一個(gè)城市voidant::move(){//theantmovetonexttownandaddtownIDtotabu.intn=ChooseNextCity();addcity(n);}classproject{public:doublem_dLength;antants[N_ANT_COUNT];public:project();voidUpdateTrial();voidinitmap();voidGetAnt();voidStartSearch();};//更新環(huán)境信息素//這里采用的是ANT-CYCLE模式，即每只螞蟻周游完城市后才更新voidproject::UpdateTrial(){//calculatethechangesoftrialinformationintm=0;intn=0;for(inti=0;i<N_ANT_COUNT;i++)//計(jì)算每只螞蟻在兩兩城市間留下的信息素，螞蟻?zhàn)哌^的路徑越短，留下的信息素?cái)?shù)值越大{for(intj=0;j<N_CITY_COUNT-1;j++)//計(jì)算兩兩城市間的信息素{m=ants[i].tabu[j];n=ants[i].tabu[j+1];Map.m_dDeltTrial[m][n]+=DB_Q/ants[i].m_dLength;Map.m_dDeltTrial[n][m]+=DB_Q/ants[i].m_dLength;}//最后城市到開始城市間的信息素m=ants[i].tabu[N_CITY_COUNT-1];n=ants[i].tabu[0];Map.m_dDeltTrial[m][n]+=DB_Q/ants[i].m_dLength;Map.m_dDeltTrial[n][m]+=DB_Q/ants[i].m_dLength;}//最新的環(huán)境信息素=消失掉的信息素+新留下的信息素for(inta=0;a<N_CITY_COUNT;a++){for(intj=0;j<N_CITY_COUNT;j++){Map.m_dTrial[a][j]=(DB_ROU*Map.m_dTrial[a][j]+Map.m_dDeltTrial[a][j]);Map.m_dDeltTrial[a][j]=0;}}}//初始化voidproject::initmap(){for(inti=0;i<N_CITY_COUNT;i++){for(intj=0;j<N_CITY_COUNT;j++){Map.m_dTrial[i][j]=1;Map.m_dDeltTrial[i][j]=0;}}}project::project(){//initialmapinitmap();m_dLength=10e9;structcity{intnum;intx;inty;} cc[N_CITY_COUNT];//城市坐標(biāo)數(shù)據(jù)來(lái)自國(guó)際通用的數(shù)據(jù)eil51.tspintx_Ary[51]={37,49,52,20,40,21,17,31,52,51,42,31,5,12,36,52,27,17,13,57,62,42,16,8,7,27,30,43,58,58,37,38,46,61,62,63,32,45,59,5,10,21,5,30,39,32,25,25,48,56,30};inty_Ary[51]={52,49,64,26,30,47,63,62,33,21,41,32,25,42,16,41,23,33,13,58,42,57,57,52,38,68,48,67,48,27,69,46,10,33,63,69,22,35,15,6,17,10,64,15,10,39,32,55,28,37,40};for(inti=0;i<N_CITY_COUNT;i++){cc[i].x=x_Ary[i];cc[i].y=y_Ary[i];cc[i].num=i;}//計(jì)算兩兩城市間距離，需要進(jìn)行四舍五入取整//eil51.tsp的最短路徑426，是按四舍五入取整后的距離算出來(lái)的。for(intb=0;b<N_CITY_COUNT;b++){for(intj=0;j<N_CITY_COUNT;j++){Map.distance[b][j]=(int)(sqrt(pow((cc[b].x-cc[j].x),2)+pow((cc[b].y-cc[j].y),2))+0.5);}}}voidproject::GetAnt(){//初始化隨機(jī)種子srand((unsigned)time(NULL));//為每只螞蟻隨機(jī)分配一個(gè)出發(fā)城市intcity=0;for(inti=0;i<N_ANT_COUNT;i++){city=rnd(N_CITY_COUNT);ants[i].addcity(city);}}voidproject::StartSearch(){//begintofindbestsolutionintmax=0;//everyanttourstimesdoubletemp;inttemptour[N_CITY_COUNT];doubledbMin=0.0;while(max<N_IT_COUNT){dbMin=100000000.0;//本次疊迭中的最小路徑長(zhǎng)度f(wàn)or(intj=0;j<N_ANT_COUNT;j++){for(inti=0;i<N_CITY_COUNT-1;i++){ants[j].move();}}for(intc=0;c<N_ANT_COUNT;c++){ants[c].move2last();ants[c].UpdateResult();//計(jì)算路徑總長(zhǎng)度}//findoutthebestsolutionofthestepandputitintotemptemp=ants[0].m_dLength;for(intt=0;t<N_CITY_COUNT;t++){temptour[t]=ants[0].tabu[t];}for(intd=0;d<N_ANT_COUNT;d++){if(temp>ants[d].m_dLength){temp=ants[d].m_dLength;for(intt=0;t<N_CITY_COUNT;t++){temptour[t]=ants[d].tabu[t];}}if(dbMin>ants[j].m_dLength){dbMin=ants[j].m_dLength;}}if(temp<m_dLength){m_dLength=temp;for(intt=0;t<N_CITY_COUNT;t++){besttour[t]=temptour[t];}}printf("%d:%.0f\n",max,m_dLength);UpdateTrial();//全部螞蟻遍歷各個(gè)城市后，更新環(huán)境信息素for(inte=0;e<N_ANT_COUNT;e++)//再搜索一次{ants[e].Clear();}max++;}printf("Theshortesttoureis:%f\n",m_dLength);for(intt=0;t<N_CITY_COUNT;t++){printf("%d",besttour[t]);}}voidshucout(){cout<<"******本程序是利用蟻群算法求解TSP問題，即最旅游城市中的最段距離和行走路線*****"<<endl<<endl<<endl<<endl<<endl<<endl<<endl;cout<<"51個(gè)城市X軸坐標(biāo)為："<<endl;cout<<"37,49,52,20,40,21,17,31,52,51,"<<endl;cout<<"42,31,5,12,36,52,27,17,13,57,"<<endl;cout<<"62,42,16,8,7,27,30,43,58,58,"<<endl;cout<<"37,38,46,61,62,63,32,45,59,5,"<<endl;cout<<"10,21,5,30,39,32,25,25,48,56,"<<endl;cout<<"30"<<endl;cout<<"城市Y軸坐標(biāo)為："<<endl;cout<<"52,49,64,26,30,47,63,62,33,21"<<endl;cout<<"41,32,25,42,16,41,23,33,13,58"<<endl;cout<<"42,57,57,52,38,68,48,67,48,27"<<endl;cout<<"69,46,10,33,63,69,22,35,15,6"<<endl;cout<<"17,10,64,15