gatsp.h

用c+++实现的遗传算法解决tsp（旅行商）问题源码

#ifndef __INC_GATSP_H__
#define __INC_GATSP_H__


#include <vector>
#include <fstream>
#include <windows.h>
#include <algorithm>
#include <iostream>

#include "mapTSP.h"
#include "define.h"

using namespace std;

struct SGenome
{
	vector< int > vecCities;
	double        dFitness;
	SGenome() : dFitness( 0 )
	{
	}

	SGenome( int nc ) : dFitness( 0 )
	{
		vecCities = GrabPermutation( nc );
	}

	vector<int> GrabPermutation( int &limit );

	bool TestNumber( const vector<int> &vec, const int &number );

};

class CgaTSP
{
private:
	CmapTSP*             m_pMap;
	bool                 m_bStarted;
	vector<SGenome>      m_vecPopulation;
	double               m_dMutationRate;
	double               m_dCrossoverRate;
	double               m_dTotalFitness;
	double               m_dShortestRoute;
	double               m_dLongestRoute;
	int                  m_iPopSize;
	int                  m_iChromoLength;
	int                  m_iFittestGenome;
	int                  m_iGeneration;
	
	void MutateEM( vector<int> &chromo );
	void CrossoverPMX( const vector<int> &mum,
		               const vector<int> &dad,
					   vector<int> &baby1,
					   vector<int> &baby2 );

	SGenome& RouletteWheelSelection();

	void CalculatePopulationsFitness();
	void CalculateBestWorstAvTot();
	void Reset();
	void CreateStartingPopulation();
public:
	CgaTSP( double mu_rat,
		    double cross_rat,
			int pop_size,
		    int NumCities,
		    int map_width,
			int map_heigth) : m_dMutationRate( mu_rat ),
			                  m_dCrossoverRate( cross_rat ),
							  m_iPopSize( pop_size ),
							  m_iFittestGenome( 0 ),
							  m_iGeneration( 0 ),
							  m_dShortestRoute( 999999999 ),
							  m_dLongestRoute( 0 ),
							  m_iChromoLength( NumCities ),
							  m_bStarted( false )
	{
		m_pMap = new CmapTSP( map_width,
			                  map_heigth,
							  NumCities );
		CreateStartingPopulation();
	}
	~CgaTSP()
	{
	//	if( m_pMap )
			delete m_pMap;
	}

	void Render( HDC surface, int cx, int cy );
	void Epoch();
	void Run( HWND hwnd );
	void Resize( int cxClient, int cyClient )
	{
		m_pMap->Resize( cxClient, cyClient );
	}
	void Stop()
	{
		m_bStarted = false;
	}
	bool Started()
	{
		return m_bStarted;
	}
};


#endif //  __INC_GATSP_H__