遗传算法解决TSP问题

#include "gaTSP.h" //CHB:创建一个随机的城市周游路径 vector<int> SGenome::GrabPermutation( int &limit ) { vector<int> vecPerm; //CHB:使用limit-1，是希望整数数组从0开始计算 for( int i=0; i<limit; i++ ) { int NextPossibleNumber = RandInt( 0, limit-1 ); while( TestNumber( vecPerm, NextPossibleNumber ) ) { NextPossibleNumber = RandInt( 0, limit-1 ); } vecPerm.push_back( NextPossibleNumber ); } return vecPerm; } bool SGenome::TestNumber( const vector<int> &vec, const int &number ) { for( int i=0; i<vec.size(); i++ ) { if( vec[i] == number ) { return true; } } return false; } void CgaTSP::Render( HDC surface, int cx, int cy ) { if( m_pMap ) { for (int city_num = 0; city_num < m_pMap->m_vecCityCoOrds.size(); ++city_num) { int x = (int)m_pMap->m_vecCityCoOrds[city_num].x; int y = (int)m_pMap->m_vecCityCoOrds[city_num].y; Ellipse(surface, x-CITY_SIZE, y+CITY_SIZE, x+CITY_SIZE, y-CITY_SIZE); } } vector<int> route = m_vecPopulation[m_iFittestGenome].vecCities; if ( m_iGeneration != 0 ) { MoveToEx( surface, (int)m_pMap->m_vecCityCoOrds[ route[0] ].x, (int)m_pMap->m_vecCityCoOrds[ route[0] ].y, NULL ); for (int i=1; i<route.size(); ++i) { int CityX = (int)m_pMap->m_vecCityCoOrds[route[i]].x; int CityY = (int)m_pMap->m_vecCityCoOrds[route[i]].y; LineTo(surface, CityX, CityY); //draw the numbers representing the order the cities are visited. //No point drawing them after about a 100 cities as the display //just becomes confused if (NUM_CITIES < 100) { string CityNumber = itos(i); TextOut(surface, CityX, CityY, CityNumber.c_str(), CityNumber.size()); } } LineTo(surface, (int)m_pMap->m_vecCityCoOrds[route[0]].x, (int)m_pMap->m_vecCityCoOrds[route[0]].y); } string sGen = itos(m_iGeneration); sGen = "Generation: " + sGen; TextOut(surface, 5, 5, sGen.c_str(), sGen.size()); if (!m_bStarted) { string Start = "Press Return to start a new run"; TextOut(surface, cx/2 - (Start.size() * 3), cy - 20, Start.c_str(), Start.size()); } else { string Start = "Space to stop"; TextOut(surface, cx/2 - (Start.size() * 3), cy - 20, Start.c_str(), Start.size()); } } void CgaTSP::Run( HWND hwnd ) { CreateStartingPopulation(); m_bStarted = true; } void CgaTSP::CreateStartingPopulation() { m_vecPopulation.clear(); for( int i=0; i<m_iPopSize; ++i ) { m_vecPopulation.push_back( SGenome( m_iChromoLength ) ); } m_iGeneration = 0; m_dShortestRoute = 9999999; m_iFittestGenome = 0; m_bStarted = false; } void CgaTSP::Epoch() { Reset(); double best = 0; //CHB:计算总群的适应性 CalculatePopulationsFitness(); //CHB:如果最终找到了一个解，就推出循环 // best = m_pMap->BestPossibleRoute(); best = 500; if( ( m_dShortestRoute <= best ) ) { //CHB: m_bStarted = false; return; } //CHB:为新种群创建一个临时矢量 vector<SGenome> vecNewPop; //CHB:首先把上一代中NUM_BEST_TO_ADD个优秀个体 //加入到种群中 for( int i=0; i<NUM_BEST_TO_ADD; i++ ) { vecNewPop.push_back( m_vecPopulation[m_iFittestGenome] ); } //CHB:现在再创建种群其余的成员 while( vecNewPop.size() != m_iPopSize ) { //CHB:选取两个基因组做父代 SGenome mum = RouletteWheelSelection(); SGenome dad = RouletteWheelSelection(); //CHB:创建两个子代 SGenome baby1, baby2; //CHB:进行杂交 CrossoverPMX( mum.vecCities, dad.vecCities, baby1.vecCities, baby2.vecCities ); //CHB:在做变异 MutateEM( baby1.vecCities ); MutateEM( baby2.vecCities ); //CHB:将他们加入到新种群 vecNewPop.push_back( baby1 ); vecNewPop.push_back( baby2 ); } //CHB:复制到下一个generation m_vecPopulation = vecNewPop; //CHB:generatio数加1 ++m_iGeneration; } void CgaTSP::Reset() { //just make the shortest route some excessively large distance m_dShortestRoute = 999999999; m_dLongestRoute = 0; m_dTotalFitness = 0; } void CgaTSP::CalculatePopulationsFitness() { //CHB：对每一个染色体 for( int i=0; i<m_iPopSize; i++ ) { //CHB:计算染色体周游路线的路程长度 double TourLength = m_pMap->GetTourLength( m_vecPopulation[i].vecCities ); m_vecPopulation[i].dFitness = TourLength; //CHB:在每一代中保存最短（即最优）的路程长度 if( TourLength < m_dShortestRoute ) { m_dShortestRoute = TourLength; m_iFittestGenome = i; } //CHB:在每一代中保存最长（即最差）的路程长度 if( TourLength > m_dLongestRoute ) { m_dLongestRoute = TourLength; } }//下一代染色体 //CHB:计算完所有的路程长度，下一步就算他们的适应性分数 for( i=0; i<m_iPopSize; i++ ) { m_vecPopulation[i].dFitness = m_dLongestRoute - m_vecPopulation[i].dFitness; } } //CHB:赌轮选择法，从群体中选择一个基于组，选中基因 //的概率正比于基因组的适应性分数 SGenome& CgaTSP::RouletteWheelSelection() { double fSlice = RandFloat() * m_dTotalFitness; double cfTotal = 0.0; int SelectGenome = 0; for( int i=0; i<m_iPopSize; i++ ) { cfTotal += m_vecPopulation[i].dFitness; if( cfTotal > fSlice ) { SelectGenome = i; break; } } return m_vecPopulation[SelectGenome]; } //CHB:杂交算法 //这个函数要求两个染色体在同一随机位置上断裂开来，然后 //将他们在断开点以后的部分进行互换， //以形成两个新的染色体 void CgaTSP::CrossoverPMX( const vector<int> &mum, const vector<int> &dad, vector<int> &baby1, vector<int> &baby2 ) { baby1 = mum; baby2 = dad; //CHB:首先进行检测，决定mum和dad两个是否需要进行互换 //CHB:杂交的概率有参数m_dCrossoverRate确定。 //如果不发生杂交，则两个父辈染色体不作任何改变地就直接复制为子代 //函数立即返回 if( ( RandFloat() > m_dCrossoverRate ) || ( mum == dad ) ) { return; } //CHB:首先选取染色体的一节（section）的开始点 int beg = RandInt( 0, mum.size() - 2 ); int end = beg; //CHB:再选取一个结束点 while( end <= beg ) { end = RandInt( 0, mum.size() - 1 ); } //CHB:从beg到end，一次寻找匹配的基因对 //并交换两个染色体中的位置 vector<int>::iterator posGene1, posGene2; for( int pos = beg; pos < end+1; pos++ ) { //CHB:这些是要做交换的基因 int gene1 = mum[pos]; int gene2 = dad[pos]; if( gene1 != gene2 ) { //CHB:将它们从子代baby1中找出来，并进行交换 posGene1 = find( baby1.begin(), baby1.end(), gene1 ); posGene2 = find( baby1.begin(), baby1.end(), gene2 ); swap( *posGene1, *posGene2 ); //同理 posGene1 = find(baby2.begin(), baby2.end(), gene1); posGene2 = find(baby2.begin(), baby2.end(), gene2); swap(*posGene1, *posGene2); } }//下一对 } //CHB:交换变异操作 //变异后，必须形成一个回路，而交换变异能做到 void CgaTSP::MutateEM( vector<int> &chromo ) { //CHB:根据变异率，确定是否需要返回 if ( RandFloat() > m_dMutationRate ) return; //CHB:选择第一个基因 int pos1 = RandInt( 0, chromo.size() - 1 ); //CHB:选择第二个基因 int pos2 = pos1; while( pos1 == pos2 ) { pos2 = RandInt( 0, chromo.size() - 1 ); } //CHB:交换他们的位置 swap( chromo[pos1], chromo[pos2] ); }