学步园

完整下载

/*基本遗传<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span>求解TSP<br /> *<br /> *选择操作使用转赌轮算法<br /> *变异算子采用逆转变异算法<br /> *交叉时先使用顺序编码，单点交叉，然后解码<br /> *运行效果并不理想<br /> *<br /> *本程序写作过程中主要参考了 合肥工业大学 蒋荣2009年的硕士学位论文《遗传算法在TSP上的应用》<br /> *<br /> * @author :onezeros@yahoo.cn<br /> */<br /> #include <iostream><br /> #include <fstream><br /> #include <vector><br /> #include <algorithm><br /> #include <math.h><br /> #include <stdlib.h><br /> #include <time.h><br /> #include <assert.h><br /> using namespace std;</p> <p>//roulette selection<br /> int roulette_select(double* arr,int num)<br /> {<br /> //srand((unsigned)time(NULL));<br /> int i;<br /> double* stage=new double[num];<br /> stage[0]=arr[0];<br /> for (i=1;i<num;i++){<br /> stage[i]=stage[i-1]+arr[i];<br /> }</p> <p> double d=(double)rand()/RAND_MAX*stage[num-1];<br /> i=0;<br /> while(d>stage[i]){<br /> i++;<br /> }</p> <p> delete[] stage;</p> <p> assert(i<num||i>=0);<br /> return i;<br /> }<br /> //generate a integer sequence from 0 to n-1 at random<br /> void rand_int_order(vector<int>& randorder,const int n)<br /> {<br /> assert(n>1); </p> <p> randorder.clear();<br /> randorder.resize(n);<br /> vector<int> recoder;<br /> for (int i=0;i<n;i++){<br /> recoder.push_back(i);<br /> }</p> <p> for(int i=0;i<n;i++){<br /> int sel=rand()%recoder.size();<br /> randorder[i]=recoder[sel];<br /> recoder.erase(recoder.begin()+sel);<br /> }<br /> //assertion<br /> assert(randorder.size()==n);</p> <p>}<br /> //sequence based sequence_encode<br /> void sequence_encode(vector<int>& chromosome)<br /> {<br /> vector<int>standard;<br /> for (int i=0;i<chromosome.size();i++){<br /> standard.push_back(i);<br /> }<br /> vector<int>::iterator ite;<br /> for (int i=0;i<chromosome.size();i++){<br /> ite=find(standard.begin(),standard.end(),chromosome[i]);<br /> assert(ite!=standard.end());<br /> chromosome[i]=ite-standard.begin();<br /> standard.erase(ite);<br /> }</p> <p>}<br /> //sequence_decode<br /> void sequence_decode(vector<int>& chromosome)<br /> {<br /> vector<int>standard;<br /> for (int i=0;i<chromosome.size();i++){<br /> standard.push_back(i);<br /> }<br /> for (int i=0;i<chromosome.size();i++){<br /> int t=chromosome[i];<br /> chromosome[i]=standard[t];<br /> standard.erase(standard.begin()+t);<br /> }</p> <p>}</p> <p>/*<br /> //function test<br /> int main()<br /> {<br /> //srand((unsigned)time(NULL));<br /> //double a[10];<br /> //int result[10];<br /> //for (int i=0;i<10;i++){<br /> // a[i]=10;<br /> // result[i]=0;<br /> //}<br /> //<br /> //for (int i=0;i<100;i++){<br /> // int d=roulette_select((double*)a,10);<br /> // cout<<d<<" ";<br /> // result[d]++;<br /> // //cout<<rand()%10<<endl;<br /> //}<br /> //cout<<endl;<br /> //for(int i=0;i<10;i++){<br /> // cout<<result[i]<<endl;<br /> //}</p> <p> /*vector<int> v;<br /> rand_int_order(v,5);<br /> for (int i=0;i<5;i++){<br /> cout<<v[i]<<" ";<br /> }<br /> cout<<endl;<br /> sequence_encode(v);<br /> for (int i=0;i<5;i++){<br /> cout<<v[i]<<" ";<br /> }<br /> cout<<endl;<br /> sequence_decode(v);<br /> for (int i=0;i<5;i++){<br /> cout<<v[i]<<" ";<br /> }<br /> cout<<endl;<br /> }<br /> */</p> <p>int main()<br /> {<br /> srand((unsigned)time(NULL));</p> <p> //read data from file<br /> fstream filein("data/berlin52.tsp.processed",ios::in);<br /> fstream fileout("data/result.txt",ios::out);<br /> if (filein==NULL){<br /> cout<<"cannot open data file"<<endl;<br /> return 1;<br /> }<br /> if (fileout==NULL){<br /> cout<<"cannot open a file to write data"<<endl;<br /> return 1;<br /> }</p> <p> //number of cities<br /> unsigned int cityNum;<br /> //standard path<br /> int* standardPath;</p> <p> //distance between cities<br /> double** distance;</p> <p> //read data from filein<br /> filein>>cityNum;<br /> cout<<cityNum<<endl;</p> <p> standardPath=new int[cityNum];<br /> for (int i=0;i<cityNum;i++){<br /> filein>>standardPath[i];<br /> }</p> <p> distance=new double* [cityNum];<br /> for (int i=0;i<cityNum;i++){<br /> distance[i]=new double[cityNum];<br /> for (int j=0;j<cityNum;j++){<br /> filein>>distance[i][j];<br /> }<br /> }<br /> //////////////////////////////////////////////////////////////////////////<br /> //parameters<br /> //number of generations<br /> unsigned int generation = 1000;<br /> //size of the population,i.e. number of chromosomes<br /> unsigned int populationSize = 70;<br /> //number of genes in a individual,i.e. length of chromosome<br /> unsigned int chromLen = cityNum;<br /> //mutate rate ,generally it is between 0.05 and 0.3<br /> double mutationRate = 0.7;<br /> //crossover rate ,generally it is about 0.7<br /> double crossoverRate = 0.9; </p> <p> // define the population<br /> vector<vector<int> > population;<br /> //initialize population at random<br /> for (int i=0;i<populationSize;i++){<br /> vector<int> chromo;<br /> rand_int_order(chromo,chromLen);<br /> population.push_back(chromo);<br /> } </p> <p> //length of best path found<br /> double best_path_len=1<<(8*sizeof(int)-2);<br /> //index of best individual<br /> int bestIndex=0;<br /> //evolution<br /> for (int g=0;g<generation;g++){<br /> //fitness value,i.e. length of the path<br /> double* fitness=new double[populationSize];<br /> //calculate fitness of every individual<br /> for(int i=0;i<populationSize;i++){<br /> fitness[i]=0;<br /> }</p> <p> //update population<br /> vector<vector<int> > parentGeneration=population;<br /> population.clear(); </p> <p> for (int s=0;s<populationSize;s++){<br /> for (int l=0;l<chromLen-1;l++){<br /> fitness[s]+=distance[parentGeneration[s][l]][parentGeneration[s][l+1]];<br /> }<br /> fitness[s]+=distance[parentGeneration[s][chromLen-1]][parentGeneration[s][0]];<br /> if (fitness[s]<best_path_len){<br /> best_path_len=fitness[s];<br /> bestIndex=s;<br /> }<br /> }</p> <p> //epoch<br /> while(population.size()<populationSize){<br /> //roulette selection</p> <p> //children<br /> vector<int> baby1,baby2;<br /> int rs=roulette_select(fitness,populationSize);<br /> baby1=parentGeneration[rs];<br /> rs=roulette_select(fitness,populationSize);<br /> baby2=parentGeneration[rs];</p> <p> //crossover<br /> if(baby1!=baby2){<br /> if (rand()/RAND_MAX<crossoverRate){<br /> //sequence based sequence_encode<br /> sequence_encode(baby1);<br /> sequence_encode(baby2);<br /> //single point crossover<br /> int index=rand()%chromLen;<br /> int tmp=baby1[index];<br /> baby1[index]=baby2[index];<br /> baby2[index]=tmp;<br /> //sequence_decode<br /> sequence_decode(baby1);<br /> sequence_decode(baby2);<br /> }<br /> }<br /> //reverse mutate<br /> int point1=rand()%chromLen;<br /> int point2=point1;<br /> while(point1==point2){<br /> point2=rand()%chromLen;<br /> }<br /> if (point1>point2){<br /> int tmp=point1;<br /> point1=point2;<br /> point2=tmp;<br /> }<br /> //reverse<br /> reverse(baby1.begin()+point1,baby1.begin()+point2);<br /> reverse(baby2.begin()+point1,baby2.begin()+point2);</p> <p> //update population<br /> population.push_back(baby1);<br /> population.push_back(baby2);<br /> }<br /> //if populationSize is odd,after the epoch,size of population will be populationSize+1<br /> if (population.size()>populationSize){<br /> population.pop_back();<br /> } </p> <p> fileout<<"generation :"<<g<<endl<br /> <<"best distance found for the moment: "<br /> <<best_path_len<<endl<br /> <<"best distance found in this epoch: "<br /> <<fitness[bestIndex]<<endl<br /> <<"best path found for the moment:"<<endl;<br /> for (int i=0;i<cityNum;i++){<br /> fileout<<population[bestIndex][i]<<" ";<br /> }<br /> fileout<<endl;<br /> //to console<br /> cout<<"generation :"<<g<<endl<br /> <<"best distance found for the moment: "<br /> <<best_path_len<<endl<br /> <<"best distance found in this epoch: "<br /> <<fitness[bestIndex]<<endl<br /> <<"best path found for the moment:"<<endl;<br /> for (int i=0;i<cityNum;i++){<br /> cout<<population[bestIndex][i]<<" ";<br /> }<br /> cout<<endl;<br /> delete[] fitness;<br /> }</p> <p> //show standard path and distance<br /> fileout<<"standard path:"<<endl;<br /> double standardbestlen=0;<br /> for (int i=0;i<cityNum;i++){<br /> fileout<<standardPath[i]<<" ";<br /> }<br /> for (int i=0;i<cityNum-1;i++){<br /> standardbestlen+=distance[standardPath[i]][standardPath[i+1]];<br /> }<br /> standardbestlen+=distance[standardPath[cityNum-1]][standardPath[0]];<br /> fileout<<endl<<"length of standard path: "<<endl<<" "<<standardbestlen<<endl;</p> <p> //append the best result found in this test to a file named "best.txt"<br /> fstream bestout("data/best.txt",ios::app);<br /> if (bestout==NULL){<br /> cout<<"cannot open a file to write data"<<endl;<br /> return 1;<br /> }<br /> bestout<<best_path_len<<endl;<br /> for (int i=0;i<cityNum;i++){<br /> bestout<<population[bestIndex][i]<<" ";<br /> }<br /> bestout<<endl;</p> <p> //free memory/////////////////////////////////////////////////////////////<br /> filein.close();<br /> fileout.close();<br /> bestout.close();</p> <p> delete[] standardPath;<br /> for (int i=0;i<cityNum;i++){<br /> delete[] distance[i];<br /> }<br /> delete[] distance;<br /> return 0;<br /> }</p> <p>