遗传算法的应用（求解迷宫问题）

遗传算法（Genetic Algorithm）：

是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。

每个个体实际上是染色体(chromosome)带有特征的实体。

染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。

因此，在一开始需要实现从表现型到基因型的映射即编码工作。

由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。

这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

遗传算法可以运用于迷宫的求解问题

共包含6个文件（vs工程）

CBobsMap.h文件

#ifndef CBOBSMAP_H
#define CBOBSMAP_H

///////////////////////////////////////////////////////////////////////
//
//		File: CBobsMap.h
//
//		Author: Mat Buckland
//
//		Desc: Class for defining the map described in chapter 3
//
///////////////////////////////////////////////////////////////////////

#include "stdlib.h"
#include "windows.h"
#include <vector>

#include "defines.h"


using namespace std;




class CBobsMap
{
private:
	
	//storage for the map
	static const int	map[MAP_HEIGHT][MAP_WIDTH];

	static const int	m_iMapWidth;
	static const int	m_iMapHeight;

	//index into the array which is the start point
	static const int	m_iStartX;
	static const int	m_iStartY;

	//and the finish point
	static const int	m_iEndX;
	static const int	m_iEndY;


public:

	//we can use this array as Bobs memory if rqd
	int					memory[MAP_HEIGHT][MAP_WIDTH];

	CBobsMap()
	{
		ResetMemory();

	}

	//takes a string of directions and see's how far Bob
	//can get. Returns a fitness score proportional to the 
	//distance reached from the exit.
	double TestRoute(const vector<int> &vecPath, CBobsMap &memory);

	//given a surface to draw on this function uses the windows GDI
	//to display the map.
	void Render(const int cxClient, const int cyClient, HDC surface);

	//draws whatever path may be stored in the memory
	void MemoryRender(const int cxClient, const int cyClient, HDC surface);

	void ResetMemory();


};



#endif



			

CGABob.h

#ifndef CGABOB_H
#define CGABOB_H

/////////////////////////////////////////////////////////////////////////
//
//		File: CGABob.h
//
//		Author: Mat Buckland
//
//		Desc: definition of the SGenome class and the genetic algorithm
//			  class CGABob from chapter 3
//
/////////////////////////////////////////////////////////////////////////

#include <vector>
#include <sstream>

#include "defines.h"
#include "CBobsMap.h"
#include "utils.h"

using namespace std;



//--------------------------------------------------------------
//	define the genome structure
//--------------------------------------------------------------
struct SGenome
{
	vector<int> vecBits;
	
	double		dFitness;
	

	SGenome():dFitness(0){}
	
	SGenome(const int num_bits):dFitness(0)
	{
		//create a random bit string
		for (int i=0; i<num_bits; ++i)
		{
			vecBits.push_back(RandInt(0, 1));
		}
	}
};


//--------------------------------------------------------------
//	define the genetic algorithm class
//---------------------------------------------------------------
class CgaBob
{
private:

	//the population of genomes
	vector<SGenome>	m_vecGenomes;
	
	//size of population
	int             m_iPopSize;

	double          m_dCrossoverRate;
	
	double          m_dMutationRate;
	
	//how many bits per chromosome
	int             m_iChromoLength;

	//how many bits per gene
	int             m_iGeneLength;
	
	int             m_iFittestGenome;
	
	double          m_dBestFitnessScore;
	
	double          m_dTotalFitnessScore;
	
	int             m_iGeneration;

	//create an instance of the map class
	CBobsMap        m_BobsMap;

	//we use another CBobsMap object to keep a record of 
	//the best route each generation as an array of visited
	//cells. This is only used for display purposes.
	CBobsMap		m_BobsBrain;

	//lets you know if the current run is in progress.
	bool			m_bBusy;
	

	
	void        Mutate(vector<int> &vecBits);
	
	void        Crossover(const vector<int>	&mum,
                        const vector<int> &dad,
                        vector<int>       &baby1,
                        vector<int>       &baby2);
	
	SGenome&		RouletteWheelSelection();
	
	//updates the genomes fitness with the new fitness scores and calculates
  //the highest fitness and the fittest member of the population.
  void			  UpdateFitnessScores();

	//decodes a vector of bits into a vector of directions (ints)
  vector<int>	Decode(const vector<int> &bits);
	
	//converts a vector of bits into decimal. Used by Decode.
  int				  BinToInt(const vector<int> &v);

	//creates a start population of random bit strings
  void			  CreateStartPopulation();

public:
	
	CgaBob(double cross_rat,
         double mut_rat,
         int    pop_size,
         int    num_bits,
         int    gene_len):m_dCrossoverRate(cross_rat),
                          m_dMutationRate(mut_rat),
                          m_iPopSize(pop_size),
                          m_iChromoLength(num_bits),
                          m_dTotalFitnessScore(0.0),
                          m_iGeneration(0),
                          m_iGeneLength(gene_len),
                          m_bBusy(false)
		
	{
		CreateStartPopulation();
	}
	
	void			Run(HWND hwnd);

	void			Render(int cxClient, int cyClient, HDC surface);

  void			Epoch();
	
	//accessor methods
	int				Generation(){return m_iGeneration;}
	int				GetFittest(){return m_iFittestGenome;}
  bool      Started(){return m_bBusy;}
  void			Stop(){m_bBusy = false;}
};



#endif

#ifndef DEFINES_H
#define DEFINES_H

/////////////////////////////////////////////////////////////////////////
//
//		File:   Defines.h
//
//		Author: Mat Buckland
//
//		Desc:   #defines for the code project 'pathfinder'
//
/////////////////////////////////////////////////////////////////////////

#define WINDOW_WIDTH	450
#define WINDOW_HEIGHT	300

#define MAP_WIDTH		15
#define MAP_HEIGHT		10

#define CROSSOVER_RATE	0.7
#define MUTATION_RATE	0.001

#define POP_SIZE		140
#define CHROMO_LENGTH	70
#define GENE_LENGTH		2

#endif

#ifndef UTILS_H
#define UTILS_H

/////////////////////////////////////////////////////////////////////////
//
//		File: Utils.h
//
//		Author: Mat Buckland
//
//		Desc: useful utilities
//
/////////////////////////////////////////////////////////////////////////

#include <stdlib.h>
#include <math.h>
#include <sstream>
#include <string>

using namespace std;

//-----------------------------------------------------------------------
//	some random number functions.
//-----------------------------------------------------------------------
inline int	  RandInt(int x,int y) {return rand()%(y-x+1)+x;}

inline double RandFloat()		   {return (rand())/(RAND_MAX+1.0);}

inline bool   RandBool()
{
	if (RandInt(0,1)) return true;

	else return false;
}

//returns a random float in the range -1 < n < 1
inline double RandomClamped()	   {return RandFloat() - RandFloat();}

//-----------------------------------------------------------------------
// useful string functions
//-----------------------------------------------------------------------

//int to string function
string itos(int arg);




#endif

CBobsMap.cpp

#include "CBobsMap.h"


//this defines our little maze which Bob wanders
//around in
const int CBobsMap::map[MAP_HEIGHT][MAP_WIDTH] = 
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1,
 8, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1,
 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1,
 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1,
 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1,
 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1,
 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 5,
 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};


const int CBobsMap::m_iMapHeight = MAP_HEIGHT;
const int CBobsMap::m_iMapWidth  = MAP_WIDTH;

const int CBobsMap::m_iStartX = 14;
const int CBobsMap::m_iStartY = 7;

const int CBobsMap::m_iEndX = 0;
const int CBobsMap::m_iEndY = 2;


//-------------------------------Render -----------------------------

void CBobsMap::Render(const int cxClient,
					  const int cyClient,
					  HDC surface)
{
	const int border = 20;
	
	int BlockSizeX = (cxClient - 2*border)/m_iMapWidth;
	int BlockSizeY = (cyClient - 2*border)/m_iMapHeight;

	HBRUSH	BlackBrush, RedBrush, OldBrush;
	HPEN	NullPen, OldPen;

	//grab a null pen so we can see the outlines of the cells
	NullPen = (HPEN)GetStockObject(NULL_PEN);

	//grab a brush to fill our cells with
	BlackBrush = (HBRUSH)GetStockObject(BLACK_BRUSH);

	//create a brush for the exit/entrance points
	RedBrush = CreateSolidBrush(RGB(255,0,0));

	//select them into the device conext
	OldBrush = (HBRUSH)SelectObject(surface, BlackBrush);
	OldPen	 =	 (HPEN)SelectObject(surface, NullPen);
	
	for (int y=0; y<m_iMapHeight; ++y)
	{
		for (int x=0; x<m_iMapWidth; ++x)
		{
			//calculate the corners of each cell
			int left  = border + (BlockSizeX * x);
			int right = left + BlockSizeX;
			
			int top    = border + (BlockSizeY * y);
			int bottom = top + BlockSizeY;
			
			//draw black rectangle if this is a wall
			if (map[y][x] == 1)
			{
				SelectObject(surface, BlackBrush);

				//draw the cell
				Rectangle(surface, left, top, right, bottom);
			}
			
			//draw red for exit and entrance
			if ( (map[y][x] == 5) || (map[y][x] == 8))
			{
				SelectObject(surface, RedBrush);

				//draw the cell
				Rectangle(surface, left, top, right, bottom);
			}
			
			
		}
	}

	//restore the original brush
	SelectObject(surface, OldBrush);

	//and pen
	SelectObject(surface, OldPen);
}

//-------------------------------MemoryRender ------------------------
//
//	//draws whatever path may be stored in the memory
//--------------------------------------------------------------------
void CBobsMap::MemoryRender(const int cxClient,
							const int cyClient,
							HDC surface)
{
	const int border = 20;
	
	int BlockSizeX = (cxClient - 2*border)/m_iMapWidth;
	int BlockSizeY = (cyClient - 2*border)/m_iMapHeight;
	
	HBRUSH	GreyBrush, OldBrush;
	HPEN	NullPen, OldPen;
	
	//grab a brush to fill our cells with
	GreyBrush = (HBRUSH)GetStockObject(LTGRAY_BRUSH);

	//grab a pen
	NullPen = (HPEN)GetStockObject(NULL_PEN);
	
	//select them into the device conext
	OldBrush = (HBRUSH)SelectObject(surface, GreyBrush);
	OldPen	 =	(HPEN)SelectObject(surface, NullPen);
	
	for (int y=0; y<m_iMapHeight; ++y)
	{
		for (int x=0; x<m_iMapWidth; ++x)
		{
			//calculate the corners of each cell
			int left  = border + (BlockSizeX * x);
			int right = left + BlockSizeX;
			
			int top    = border + (BlockSizeY * y);
			int bottom = top + BlockSizeY;
			
			//draw green rectangle if this is a wall
			if (memory[y][x] == 1)
			{
				Rectangle(surface, left, top, right, bottom);
			}
		}
	}
	
	//restore the original brush
	SelectObject(surface, OldBrush);
	
	//and pen
	SelectObject(surface, OldPen);

}

//---------------------------- TestRoute ---------------------------
//
//	given a decoded vector of directions and a map object representing
//	Bob's memory, this function moves Bob through the maze as far as 
//	he can go updating his memory as he moves.
//-------------------------------------------------------------------
double CBobsMap::TestRoute(const vector<int> &vecPath, CBobsMap &Bobs)
{
	int posX = m_iStartX;
	int posY = m_iStartY;

	for (int dir=0; dir<vecPath.size(); ++dir)
	{
		int NextDir = vecPath[dir];

		switch(vecPath[dir])
		{
		case 0: //North

			//check within bounds and that we can move
			if ( ((posY-1) < 0 ) || (map[posY-1][posX] == 1) )
			{
				break;
			}

			else
			{
				posY -= 1;
			}

			break;

		case 1: //South

			//check within bounds and that we can move
			if ( ((posY+1) >= m_iMapHeight) || (map[posY+1][posX] == 1) )
			{
				break;
			}
			
			else
			{
				posY += 1;
			}

			break;

		case 2: //East

			//check within bounds and that we can move
			if ( ((posX+1) >= m_iMapWidth ) || (map[posY][posX+1] == 1) )
			{
				break;
			}
			
			else
			{
				posX += 1;
			}

			break;

		case 3: //West

			//check within bounds and that we can move
			if ( ((posX-1) < 0 ) || (map[posY][posX-1] == 1) )
			{
				break;
			}
			
			else
			{
				posX -= 1;
			}

			break;

		}//end switch

		//mark the route in the memory array
		Bobs.memory[posY][posX] = 1;

	}//next direction

	//now we know the finish point of Bobs journey, let's assign
	//a fitness score which is proportional to his distance from
	//the exit

	int	DiffX = abs(posX - m_iEndX);
	int DiffY = abs(posY - m_iEndY);

	//we add the one to ensure we never divide by zero. Therefore
	//a solution has been found when this return value = 1
	return 1/(double)(DiffX+DiffY+1);
}

//--------------------- ResetMemory --------------------------
//
//	resets the memory map to zeros
//------------------------------------------------------------
void CBobsMap::ResetMemory()
{
	for (int y=0; y<m_iMapHeight; ++y)
	{
		for (int x=0; x<m_iMapWidth; ++x)
		{
			memory[y][x] = 0;
		}
	}
}

#include "CgaBob.h"



//--------------------------RouletteWheelSelection-----------------
//
//	selects a member of the population by using roulette wheel 
//	selection as described in the text.
//------------------------------------------------------------------
SGenome& CgaBob::RouletteWheelSelection()
{
	double fSlice	= RandFloat() * m_dTotalFitnessScore;
	
	double cfTotal	= 0.0;
	
	int	SelectedGenome = 0;
	
	for (int i=0; i<m_iPopSize; ++i)
	{
		
		cfTotal += m_vecGenomes[i].dFitness;
		
		if (cfTotal > fSlice) 
		{
			SelectedGenome = i;
			break;
		}
	}
	
	return m_vecGenomes[SelectedGenome];
}

//----------------------------Mutate---------------------------------
//	iterates through each genome flipping the bits acording to the
//	mutation rate
//--------------------------------------------------------------------
void CgaBob::Mutate(vector<int> &vecBits)
{
	for (int curBit=0; curBit<vecBits.size(); curBit++)
	{
		//do we flip this bit?
		if (RandFloat() < m_dMutationRate)
		{
			//flip the bit
			vecBits[curBit] = !vecBits[curBit];
		}
	}//next bit
}

//----------------------------Crossover--------------------------------
//	Takes 2 parent vectors, selects a midpoint and then swaps the ends
//	of each genome creating 2 new genomes which are stored in baby1 and
//	baby2.
//---------------------------------------------------------------------
void CgaBob::Crossover( const vector<int> &mum,
						const vector<int> &dad,
						vector<int>		  &baby1,
						vector<int>		  &baby2)
{
	//just return parents as offspring dependent on the rate
	//or if parents are the same
	if ( (RandFloat() > m_dCrossoverRate) || (mum == dad)) 
	{
		baby1 = mum;
		baby2 = dad;

		return;
	}
	
	//determine a crossover point
	int cp = RandInt(0, m_iChromoLength - 1);

	//swap the bits
	for (int i=0; i<cp; ++i)
	{
		baby1.push_back(mum[i]);
		baby2.push_back(dad[i]);
	}

	for (i=cp; i<mum.size(); ++i)
	{
		baby1.push_back(dad[i]);
		baby2.push_back(mum[i]);
	}
}
//-----------------------------------Run----------------------------------
//
//	This is the function that starts everything. It is mainly another 
//	windows message pump using PeekMessage instead of GetMessage so we
//	can easily and dynamically make updates to the window while the GA is 
//	running. Basically, if there is no msg to be processed another Epoch
//	is performed.
//------------------------------------------------------------------------
void CgaBob::Run(HWND hwnd)
{
	//The first thing we have to do is create a random population
	//of genomes
	CreateStartPopulation();
	
	m_bBusy = true;
		
}
//----------------------CreateStartPopulation---------------------------
//
//-----------------------------------------------------------------------
void CgaBob::CreateStartPopulation()
{
	//clear existing population
	m_vecGenomes.clear();
	
	for (int i=0; i<m_iPopSize; i++)
	{
		m_vecGenomes.push_back(SGenome(m_iChromoLength));
	}

	//reset all variables
	m_iGeneration		 = 0;
	m_iFittestGenome	 = 0;
	m_dBestFitnessScore  = 0;
	m_dTotalFitnessScore = 0;
}
//--------------------------------Epoch---------------------------------
//
//	This is the workhorse of the GA. It first updates the fitness
//	scores of the population then creates a new population of
//	genomes using the Selection, Croosover and Mutation operators
//	we have discussed
//----------------------------------------------------------------------
void CgaBob::Epoch()
{
	
	UpdateFitnessScores();

	//Now to create a new population
	int NewBabies = 0;

	//create some storage for the baby genomes 
	vector<SGenome> vecBabyGenomes;

	while (NewBabies < m_iPopSize)
	{
		//select 2 parents
		SGenome mum = RouletteWheelSelection();
		SGenome dad = RouletteWheelSelection();

		//operator - crossover
		SGenome baby1, baby2;
		Crossover(mum.vecBits, dad.vecBits, baby1.vecBits, baby2.vecBits);

		//operator - mutate
		Mutate(baby1.vecBits);
		Mutate(baby2.vecBits);

		//add to new population
		vecBabyGenomes.push_back(baby1);
		vecBabyGenomes.push_back(baby2);

		NewBabies += 2;
	}

	//copy babies back into starter population
	m_vecGenomes = vecBabyGenomes;

	//increment the generation counter
	++m_iGeneration;
}

//---------------------------UpdateFitnessScores------------------------
//	updates the genomes fitness with the new fitness scores and calculates
//	the highest fitness and the fittest member of the population.
//	Also sets m_pFittestGenome to point to the fittest. If a solution
//	has been found (fitness == 1 in this example) then the run is halted
//	by setting m_bBusy to false
//-----------------------------------------------------------------------
void CgaBob::UpdateFitnessScores()
{
	m_iFittestGenome		= 0;
	m_dBestFitnessScore		= 0;
	m_dTotalFitnessScore	= 0;

	CBobsMap TempMemory;
	 
	//update the fitness scores and keep a check on fittest so far
	for (int i=0; i<m_iPopSize; ++i)
	{
		//decode each genomes chromosome into a vector of directions
		vector<int> vecDirections = Decode(m_vecGenomes[i].vecBits);

		//get it's fitness score
		m_vecGenomes[i].dFitness = m_BobsMap.TestRoute(vecDirections, TempMemory);

		//update total
		m_dTotalFitnessScore += m_vecGenomes[i].dFitness;

		//if this is the fittest genome found so far, store results
		if (m_vecGenomes[i].dFitness > m_dBestFitnessScore)
		{
			m_dBestFitnessScore = m_vecGenomes[i].dFitness;

			m_iFittestGenome = i;

			m_BobsBrain = TempMemory;

			//Has Bob found the exit?
			if (m_vecGenomes[i].dFitness == 1)
			{
				//is so, stop the run
				m_bBusy = false;
			}
		}

		TempMemory.ResetMemory();
	
	}//next genome
}

//---------------------------Decode-------------------------------------
//
//	decodes a vector of bits into a vector of directions (ints)
//
//	0=North, 1=South, 2=East, 3=West
//-----------------------------------------------------------------------
vector<int> CgaBob::Decode(const vector<int> &bits)
{
	vector<int>	directions;

	//step through the chromosome a gene at a time
	for (int gene=0; gene < bits.size(); gene += m_iGeneLength)
	{
		//get the gene at this position
		vector<int> ThisGene;
		
		for (int bit = 0; bit < m_iGeneLength; ++bit)
		{
			ThisGene.push_back(bits[gene+bit]);
		}

		//convert to decimal and add to list of directions
		directions.push_back(BinToInt(ThisGene));
	}

	return directions;
}

//-------------------------------BinToInt-------------------------------
//	converts a vector of bits into an integer
//----------------------------------------------------------------------
int	CgaBob::BinToInt(const vector<int> &vec)
{
	int val = 0;
	int multiplier = 1;
	
	for (int cBit=vec.size(); cBit>0; cBit--)
	{
		val += vec[cBit-1] * multiplier;
		
		multiplier *= 2;
	}

	return val;
}



//------------------------- Render -------------------------------
//
//	given a surface to render to this function renders the map
//	and the best path if relevant. cxClient/cyClient are the 
//	dimensions of the client window.
//----------------------------------------------------------------
void CgaBob::Render(int cxClient, int cyClient, HDC surface)
{
	//render the map
	m_BobsMap.Render(cxClient, cyClient, surface);

	//render the best route
	m_BobsBrain.MemoryRender(cxClient, cyClient, surface);

	//Render additional information
	string s = "Generation: " + itos(m_iGeneration);
	TextOut(surface, 5, 0, s.c_str(), s.size());
	
	if (!m_bBusy)
	{
		string Start = "Press Return to start a new run";
		
		TextOut(surface, cxClient/2 - (Start.size() * 3), cyClient - 20, Start.c_str(), Start.size());
	}
	
	else
		
	{
		string Start = "Space to stop";
		
		TextOut(surface, cxClient/2 - (Start.size() * 3), cyClient - 20, Start.c_str(), Start.size());
	}
	
}

#include "utils.h"


//--------------------------itos------------------------------------
//	converts an integer to a string
//------------------------------------------------------------------		
string itos(int arg)
{
    ostringstream buffer;
	
	//send the int to the ostringstream
    buffer << arg;	
	
	//capture the string
    return buffer.str();		
}

//#define WIN32_LEAN_AND_MEAN

#include <windows.h>   
#include <stdlib.h>
#include <time.h>

#include "CgaBob.h"
#include "defines.h"

using namespace std;



///////////////////////GLOBALS ////////////////////////////////////

char*			szApplicationName = "Chapter3 - Pathfinder";
char*			szWindowClassName = "PFclass";

//pointer to the GA object
CgaBob*	g_pGABob;


//-----------------------------------WinProc------------------------------------------
//
//------------------------------------------------------------------------------------
LRESULT CALLBACK WindowProc(HWND hwnd, 
						    UINT msg, 
                            WPARAM wparam, 
                            LPARAM lparam)
{
	//device context for our window
	HDC				hdc;	
	PAINTSTRUCT     ps;

	//these hold the dimensions of the client window area
	static int cxClient, cyClient;

	//used to create the back buffer
	static HDC		hdcBackBuffer;
	static HBITMAP	hBitmap;
	static HBITMAP	hOldBitmap;
						  

	switch(msg)
	{	
    case WM_CREATE: 
		{
			//seed the random number generator
			srand((unsigned) time(NULL));

			//create the GA class
			g_pGABob = new CgaBob(CROSSOVER_RATE,
								            MUTATION_RATE,
							            	POP_SIZE,
								            CHROMO_LENGTH,
								            GENE_LENGTH);
			
			//get the size of the client window
			RECT rect;
			GetClientRect(hwnd, &rect);

			cxClient = rect.right;
			cyClient = rect.bottom;

			//create a surface for us to render to(backbuffer)
			hdcBackBuffer = CreateCompatibleDC(NULL);

			HDC hdc = GetDC(hwnd);

			hBitmap = CreateCompatibleBitmap(hdc,
											 cxClient,
											 cyClient);

			ReleaseDC(hwnd, hdc);

			hOldBitmap = (HBITMAP)SelectObject(hdcBackBuffer, hBitmap);


		} 
			
		break;
		//check key press messages
		case WM_KEYUP:
		{
			switch(wparam)
			{
				case VK_RETURN:
				{
					g_pGABob->Run(hwnd);

				}
					
				break;

				case VK_ESCAPE:
				{
					PostQuitMessage(0);
				}

				break;

				case VK_SPACE:
					{
						g_pGABob->Stop();
					}
					
					break;

				
			}//end switch
		}

		break;

		//has the user resized the client area?
		case WM_SIZE:
		{
			cxClient = LOWORD(lparam);
			cyClient = HIWORD(lparam);

			//resize the backbuffer accordingly
			SelectObject(hdcBackBuffer, hOldBitmap);

			HDC hdc = GetDC(hwnd);

			hBitmap = CreateCompatibleBitmap(hdc,
											cxClient,
											cyClient);

			ReleaseDC(hwnd, hdc);
			
			hOldBitmap = (HBITMAP)SelectObject(hdcBackBuffer, hBitmap);
		} 

		break;
  
		case WM_PAINT: 
		{

			hdc = BeginPaint(hwnd, &ps);
			
			//fill our backbuffer with white
			BitBlt(hdcBackBuffer, 0, 0, cxClient, cyClient, NULL, NULL, NULL, WHITENESS);
			
			//render the map and best route
			g_pGABob->Render(cxClient, cyClient, hdcBackBuffer);
			
			//now blit backbuffer to front
			BitBlt(hdc, 0, 0, cxClient, cyClient, hdcBackBuffer, 0, 0, SRCCOPY);

			ReleaseDC(hwnd, hdc);
			
			EndPaint(hwnd, &ps);
		} 
			
		break;

		case WM_DESTROY: 
		{
			
			SelectObject(hdcBackBuffer, hOldBitmap);
			
			//clean up our backbuffer objects
			DeleteDC(hdcBackBuffer);
			DeleteObject(hBitmap);

			//delete our GA object
			delete g_pGABob;

			// kill the application, this sends a WM_QUIT message 
			PostQuitMessage(0);

   		} 
			
		break;

		default:break;

	}//end switch

	// default msg handler 
	return (DefWindowProc(hwnd, msg, wparam, lparam));

}//end WinProc


//-----------------------------------WinMain-----------------------------------------
//	Entry point for our windows application
//-----------------------------------------------------------------------------------
int WINAPI WinMain(	HINSTANCE hinstance,
					HINSTANCE hprevinstance,
					LPSTR lpcmdline,
					int ncmdshow)
{

	WNDCLASSEX winclass; 
	HWND	   hwnd;	 
	MSG		   msg;		 

	// first fill in the window class stucture
	winclass.cbSize         = sizeof(WNDCLASSEX);
	winclass.style			    = CS_HREDRAW | CS_VREDRAW;
	winclass.lpfnWndProc	  = WindowProc;
	winclass.cbClsExtra		  = 0;
	winclass.cbWndExtra		  = 0;
	winclass.hInstance		  = hinstance;
	winclass.hIcon			    = LoadIcon(NULL, IDI_APPLICATION);
	winclass.hCursor		    = LoadCursor(NULL, IDC_ARROW); 
	winclass.hbrBackground	= NULL; 
	winclass.lpszMenuName	  = NULL;
	winclass.lpszClassName	= szWindowClassName;
	winclass.hIconSm        = LoadIcon(NULL, IDI_APPLICATION);


	// register the window class
	if (!RegisterClassEx(&winclass))
		return 0;

	// create the window
	if (!(hwnd = CreateWindowEx(NULL,									
								szWindowClassName,						
								szApplicationName,						
								WS_OVERLAPPEDWINDOW | WS_VISIBLE,
					 			0,0,									
								WINDOW_WIDTH,WINDOW_HEIGHT,				
								NULL,									
								NULL,								
								hinstance,								
								NULL)))									
	return 0;

	ShowWindow(hwnd, ncmdshow);
	UpdateWindow(hwnd);

	//enter the message loop
	bool bDone = false;

	while(!bDone)
	{
					
		while( PeekMessage( &msg, NULL, 0, 0, PM_REMOVE ) ) 
		{
			if( msg.message == WM_QUIT ) 
			{
				// Stop loop if it's a quit message
				bDone = true;
			} 

			else 
			{
				TranslateMessage( &msg );
				DispatchMessage( &msg );
			}
		}
		
    //if the user has started the run update the GA and display
    //accordingly
    if (g_pGABob->Started())
    {
	    //update the gun
      g_pGABob->Epoch();

	    //this will call WM_PAINT 
	    InvalidateRect(hwnd, NULL, TRUE);
		  UpdateWindow(hwnd);
    }
					
					
	}//end while
	

  UnregisterClass( szWindowClassName, winclass.hInstance );
 
             
  return 0;                                   
             

} // end WinMain

参考资料：

遗传算法

遗传算法的应用（求解迷宫问题）

原文：http://blog.csdn.net/u011889952/article/details/44805609