gatsp.cpp

用c+++实现的遗传算法解决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] );
}