gademoview.cpp

遗传算法演示程序

		if(_whichMut == FLIP) _whichMut = GAUSSIAN;
		// any crossover is ok for real represenation...
	}

	if(_ops) _ops->configure();

	// now construct the genetic algorithm using the genome
	// that we have configured.

	switch(_whichGA) {
	case STEADY_STATE:
		_theGA = new GASteadyStateGA(*_theGenome);
		break;
	case STEADY_STATE_SHARING: {
		_theGA = new GASteadyStateGA(*_theGenome);
		GASharing share;
		_theGA->scaling(share);
							   }
		break;
	case INCREMENTAL:
		_theGA = new GAIncrementalGA(*_theGenome);
		break;
	case DEME:
		_theGA = new GADemeGA(*_theGenome);
		break;
	case CROWDING:
		_theGA = new GADCrowdingGA(*_theGenome);
		break;
	case SIMPLE:
	default:
		_theGA = new GASimpleGA(*_theGenome);
		break;
	}

	// set up the parameters on the genetic algorithm

	_theGA->pMutation(_pmut);
	_theGA->pCrossover(_pcross);
	_theGA->nGenerations(_ngen);
	_theGA->populationSize(_popsize);
	_theGA->initialize();
}

void 
CGademoView::draw(CDC* pDC) {
	if(! _theGA || ! _theGenome) return;

	RECT rect;
	GetClientRect(&rect);

	int width = rect.right;
	int height = rect.bottom;

	TEXTMETRIC  tm;
	pDC->GetTextMetrics( &tm );
	int charht = tm.tmHeight + tm.tmExternalLeading;

	const int BUF=30;

	unsigned int w = width - 2 * BUF;
	unsigned int h = height - 2 * BUF - charht;
	unsigned int d = (w < h ? w : h);
	w -= d;
	h -= d;
	unsigned int originx = BUF + w/2;
	unsigned int originy = BUF + h/2;

	float maxx = 0;
	float minx = 0;

	if(_whichRep == BINARY_4BIT || _whichRep == BINARY_8BIT) {
		const GABin2DecPhenotype& map = ((GABin2DecGenome*)_theGenome)->phenotypes();
		maxx = map.max(0);
		minx = map.min(0);
	}
	else {
		maxx = ((GARealGenome*)_theGenome)->alleleset().upper();
		minx = ((GARealGenome*)_theGenome)->alleleset().lower();
	}

	float factor = (float)d;
	factor /= maxx - minx;

 	int txtx = width/2;
	int txty = height - charht -5;

    pDC->SetTextColor(RGB(0,0,255));

	CString txt;
	txt.Format("%d", _theGA->generation());
	pDC->TextOut(txtx, txty, txt);

	static int NCOL=5;
	static int rpval[] = {100,  0,  0,  0,100};
	static int gpval[] = {  0,100,  0,100,100};
	static int bpval[] = {  0,  0,100,100,  0};
	static int rval[]  = {255,  0,  0,  0,255};
	static int gval[]  = {  0,255,  0,255,255};
	static int bval[]  = {  0,  0,255,255,  0};

	if(_showGrid) {
		CPen gpen( PS_SOLID, 2, RGB(240, 240, 240) );
		CPen* oldpen = pDC->SelectObject( &gpen );
		for(float i=minx; i<=maxx; i+=1.0){
			int x = (int)(originx + d/2 + factor*i);
			pDC->MoveTo(x,(int)(originy + d/2 + factor*maxx));
			pDC->LineTo(x,(int)(originy + d/2 - factor*maxx));
			int y = (int)(originy + d/2 - factor*i);
			pDC->MoveTo((int)(originx + d/2 - factor*maxx),y);
			pDC->LineTo((int)(originx + d/2 + factor*maxx),y);
		}
		pDC->SelectObject( oldpen );
	}

	if(_whichGA == DEME) {
		GADemeGA& ga = (GADemeGA&)(*_theGA);
		for(int i=0; i<ga.nPopulations(); i++) {
			CPen poppen( PS_SOLID, 2, RGB(rpval[i%NCOL], gpval[i%NCOL], bpval[i%NCOL]) );
			CPen bestpen( PS_SOLID, 2, RGB(rval[i%NCOL], gval[i%NCOL], bval[i%NCOL]) );
			drawPopulation(pDC, ga.population(i), originx, originy, d, factor,
				&poppen, &bestpen);
		}
	}
	else {
		CPen greypen( PS_SOLID, 2, RGB(150,150,150) );
		CPen redpen( PS_SOLID, 2, RGB(255,0,0) );
		drawPopulation(pDC, _theGA->population(), originx, originy, d, factor,
			&greypen, &redpen);
	}
}

// in windows, upper left is 0,0 and lower right is +,+
void 
CGademoView::drawPopulation(CDC* pDC, const GAPopulation& pop, 
								 int originx, int originy, int d, float factor,
								 CPen* miscpen, CPen* bestpen) {
	CPen* oldpen = pDC->SelectObject( miscpen );
	int xbest=0;
	int ybest=0;

	if(_whichRep == BINARY_4BIT || _whichRep == BINARY_8BIT) {
		for(int i=0; i<pop.size(); i++) {
			GABin2DecGenome& g = (GABin2DecGenome&)(pop.individual(i));
			int x = (int)(originx + d/2 + factor * g.phenotype(0));
			int y = (int)(originy + d/2 - factor * g.phenotype(1));
			pDC->MoveTo(x-1,y);
			pDC->LineTo(x+1,y);
			pDC->MoveTo(x,y-1);
			pDC->LineTo(x,y+1);
		}

		GABin2DecGenome& b = (GABin2DecGenome&)(pop.best());
		xbest = (int)(originx + d/2 + factor * b.phenotype(0));
		ybest = (int)(originy + d/2 - factor * b.phenotype(1));
	}
	else {
		for(int i=0; i<pop.size(); i++) {
			GARealGenome& g = (GARealGenome&)(pop.individual(i));
			int x = (int)(originx + d/2 + factor * g.gene(0));
			int y = (int)(originy + d/2 - factor * g.gene(1));
			pDC->MoveTo(x-1,y);
			pDC->LineTo(x+1,y);
			pDC->MoveTo(x,y-1);
			pDC->LineTo(x,y+1);
		}
		GARealGenome& b = (GARealGenome&)(pop.best());
		xbest = (int)(originx + d/2 + factor * b.gene(0));
		ybest = (int)(originy + d/2 - factor * b.gene(1));
	}

	pDC->SelectObject( bestpen );

	pDC->SelectStockObject(GRAY_BRUSH);
	pDC->MoveTo(xbest-2,ybest);
	pDC->LineTo(xbest+2,ybest);
	pDC->MoveTo(xbest,ybest-2);
	pDC->LineTo(xbest,ybest+2);

	pDC->SelectObject( oldpen );
}





// Mutation is define generically here so that we can change 
// mutation behavior during the course of an evolution without
// restarting the evolution.
int
CGademoView::GenericMutation(GAGenome& g, float pmut) {
	int n = 0;
	if(_whichRep == BINARY_4BIT || _whichRep == BINARY_8BIT) {
		switch(_whichMut) {
		case FLIP:
		default:
			n = GA1DBinaryStringGenome::FlipMutator(g, pmut);
			break;
		}
	}
	else {
		switch(_whichMut) {
		case BOUNDARY:
			n = RealBoundaryMutation(g, pmut);
			break;
		case UNIFORM_MUT:
			n = RealUniformMutation(g, pmut);
			break;
		case GAUSSIAN:
		default:
			n = RealGaussianMutation(g, pmut);
			break;
		}
	}
	return n;
}

// This generic crossover operator lets us change crossover
// during the course of an evolution.
int
CGademoView::GenericCrossover(const GAGenome& p1, const GAGenome& p2, GAGenome* c1, GAGenome* c2) {
	int n = 0;
	if(_whichRep == BINARY_4BIT || _whichRep == BINARY_8BIT) {
		switch(_whichCross) {
		case SINGLE_POINT:
			n = GA1DBinaryStringGenome::OnePointCrossover(p1,p2,c1,c2);
			break;
		case TWO_POINT:
			n = GA1DBinaryStringGenome::TwoPointCrossover(p1,p2,c1,c2);
			break;
		case UNIFORM:
		default:
			n = GA1DBinaryStringGenome::UniformCrossover(p1,p2,c1,c2);
			break;
		}

	}
	else {
		switch(_whichCross) {
		case UNIFORM:
			n = GARealGenome::UniformCrossover(p1,p2,c1,c2);
			break;
		case BLX:
			n = RealBLXCrossover(p1,p2,c1,c2);
			break;
		case SINGLE_POINT:
			n = GARealGenome::OnePointCrossover(p1,p2,c1,c2);
			break;
		case TWO_POINT:
			n = GARealGenome::TwoPointCrossover(p1,p2,c1,c2);
			break;
		case AVERAGING:
		default:
			n = RealAveragingCrossover(p1,p2,c1,c2);
			break;
		}
	}

	return n;
}







// calculate the distance between two two-dimensional genomes.
// used only in the deterministic crowding ga
float
CGademoView::RealComparator(const GAGenome& g1, const GAGenome& g2) {
  GARealGenome &a = (GARealGenome &)g1;
  GARealGenome &b = (GARealGenome &)g2;

  float dist = 0;

  float x = b.gene(0) - a.gene(0);
  float y = b.gene(1) - a.gene(1);
  dist = (float)sqrt(x*x + y*y);

  return dist;
}

// warning! this gaussian implementation does not consider enumerated and
// discretized allele sets!!
int
CGademoView::RealGaussianMutation(GAGenome& g, float pmut) {
  GARealGenome &genome = (GARealGenome &)g;

  int n=0;
  for(int i=0; i<genome.length(); i++) {
	  if(GAFlipCoin(pmut)) {
		  float v;
		  do {
			  v = GAGaussianFloat(genome.gene(i));
		  } while(v < genome.alleleset(i).lower() || v > genome.alleleset(i).upper()); 
		  genome.gene(i, v);
		  n++;
	  }
  }
  return n;
}

int
CGademoView::RealUniformMutation(GAGenome& g, float pmut) {
  GARealGenome &genome = (GARealGenome &)g;

  int n=0;
  for(int i=0; i<genome.length(); i++) {
	  if(GAFlipCoin(pmut)) {
		  genome.gene(i, genome.alleleset(i).allele());
		  n++;
	  }
  }
  return n;
}

int
CGademoView::RealBoundaryMutation(GAGenome& g, float pmut) {
  GARealGenome &genome = (GARealGenome &)g;

  int n=0;
  for(int i=0; i<genome.length(); i++) {
	  if(GAFlipCoin(pmut)) {
		  genome.gene(i, (GARandomBit() ? 
							genome.alleleset(i).lower() :
							genome.alleleset(i).upper()));
		  n++;
	  }
  }
  return n;
}


// warning! these crossovers assume that mom and dad and children are all
// the same length!
int
CGademoView::RealBLXCrossover(const GAGenome& p1, const GAGenome& p2, GAGenome* c1, GAGenome* c2) {
  const GARealGenome &mom = (const GARealGenome &)p1;
  const GARealGenome &dad = (const GARealGenome &)p2;

  int n=0;

  if(c1) {
	  GARealGenome& sis = (GARealGenome&)*c1;
	  for(int i=0; i<mom.length(); i++) {
		  float lo = GAMin(mom.gene(i), dad.gene(i));
		  float hi = GAMax(mom.gene(i), dad.gene(i));
		  float dist = (float)0.5 * (hi - lo);
		  lo -= dist;
		  hi += dist;
		  lo = GAMax(lo, sis.alleleset(i).lower());
		  hi = GAMin(hi, sis.alleleset(i).upper());
		  sis.gene(i, GARandomFloat(lo, hi));
	  }
	  n++;
  }
  if(c2) {
	  GARealGenome& bro = (GARealGenome&)*c2;
	  for(int i=0; i<mom.length(); i++) {
		  float lo = GAMin(mom.gene(i), dad.gene(i));
		  float hi = GAMax(mom.gene(i), dad.gene(i));
		  float dist = (float)0.5 * (hi - lo);
		  lo -= dist;
		  hi += dist;
		  lo = GAMax(lo, bro.alleleset(i).lower());
		  hi = GAMin(hi, bro.alleleset(i).upper());
		  bro.gene(i, GARandomFloat(lo, hi));
	  }
	  n++;
  }

  return n;
}

int
CGademoView::RealAveragingCrossover(const GAGenome& p1, const GAGenome& p2, GAGenome* c1, GAGenome* c2) {
  const GARealGenome &mom = (const GARealGenome &)p1;
  const GARealGenome &dad = (const GARealGenome &)p2;

  int n=0;
  if(c1) {
	  GARealGenome& sis = (GARealGenome&)*c1;
	  for(int i=0; i<mom.length(); i++) {
		  float v = (float)0.5 * (mom.gene(i) + dad.gene(i));
		  v = GAMax(v, sis.alleleset(i).lower());
		  v = GAMin(v, sis.alleleset(i).upper());
		  sis.gene(i, v);
	  }
	  n++;
  }
  if(c2) {
	  GARealGenome& bro = (GARealGenome&)*c2;
	  for(int i=0; i<mom.length(); i++) {
		  float v = (float)0.5 * (mom.gene(i) + dad.gene(i));
		  v = GAMax(v, bro.alleleset(i).lower());
		  v = GAMin(v, bro.alleleset(i).upper());
		  bro.gene(i, v);
	  }
	  n++;
  }

  return n;
}








/*****************************************************************************/
/* Type:        2D FUNCTION                                                  */
/* Name:        Objective2D_1                                                */
/* Description: 2D tooth                                                     */
/* Boundaries:  -6 < x < 6                                                   */
/*              -6 < y < 6                                                   */
/* Source:      modified Himmelblau's function from Deb, K.                  */
/*              'GA in multimodal function optimazation' Masters thesis      */
/*		TCGA Rep. 89002 / U. of Alabama                              */
/*****************************************************************************/
float CGademoView::Loaf(GAGenome& genome) {
	float x = 0;
	float y = 0;

	if(_whichRep == BINARY_4BIT || _whichRep == BINARY_8BIT) {
		GABin2DecGenome& g = (GABin2DecGenome&)genome;
		x = g.phenotype(0);
		y = g.phenotype(1);
	}
	else {
		GARealGenome& g = (GARealGenome&)genome;
		x = g.gene(0);
		y = g.gene(1);
	}
	float z = -((x*x+y-11)*(x*x+y-11)+(x+y*y-7)*(x+y*y-7))/200 + 10;
	return z;
}


/*****************************************************************************/
/* Type:        2D FUNCTION                                                  */
/* Name:        Objective2D_2                                                */
/* Description: Foxholes (25)                                                */
/* Boundaries:  -60 < x < 60                                                 */
/*              -60 < y < 60                                                 */
/* Source:      Shekel's Foxholes problem from De Jong's Diss.(1975)         */
/*              'GA in multimodal function optimazation' Masters thesis      */
/*		TCGA Rep. 89002 / U. of Alabama                              */
/*****************************************************************************/
float CGademoView::Foxholes(GAGenome& genome) {
	static float ai[25],bi[25];
	static int inited = 0;
	if(!inited) {
		for (int j=0; j<25; j++) {
			ai[j] = (float)(16 * ((j % 5) -2));
			bi[j] = (float)(16 * ((j / 5) -2));
		}
		inited = 1;
	}

	float x =0;
	float y =0;
	if(_whichRep == BINARY_4BIT || _whichRep == BINARY_8BIT) {
		GABin2DecGenome& g = (GABin2DecGenome&)genome;
		x = g.phenotype(0);
		y = g.phenotype(1);
	}
	else {
		GARealGenome& g = (GARealGenome&)genome;
		x = g.gene(0);
		y = g.gene(1);
	}

	int i;
	double sum = 0.0;

	for (i=0; i<25; i++) {
		sum += (1.0 / (1.0 + i + pow((x-ai[i]),6.0) + pow((y-bi[i]),6.0)));
	}
	double z = 500.0 - (1 / (0.002 + sum));
	return (float)z;
}


/*****************************************************************************/
/* Type:        2D FUNCTION                                                  */
/* Name:        Objective2D_3                                                */
/* Description: Schwefel's nasty (4 glob. Max bei (+-420.96/+-420.96)        */
/* Boundaries:  -500 < x < 500                                               */
/*              -500 < y < 500                                               */
/* Source:      Schwefel's function in Schoeneburg                           */
/*****************************************************************************/
float CGademoView::Schwefel(GAGenome& genome) {
	float x =0;
	float y =0;
	if(_whichRep == BINARY_4BIT || _whichRep == BINARY_8BIT) {
		GABin2DecGenome& g = (GABin2DecGenome&)genome;
		x = g.phenotype(0);
		y = g.phenotype(1);
	}
	else {
		GARealGenome& g = (GARealGenome&)genome;
		x = g.gene(0);
		y = g.gene(1);
	}

	double z = fabs(x) * sin(sqrt(fabs(x))) + fabs(y) * sin(sqrt(fabs(y)));
	return (float)(500.0 + z);
}


/*****************************************************************************/
/* Type:        2D FUNCTION                                                  */
/* Name:        Objective2D_4                                                */
/* Description: Mexican Hat                                                  */
/* Boundaries:  -10 < x < 10                                                 */
/*              -10 < y < 10                                                 */
/* Source:                                                                   */
/*****************************************************************************/
float CGademoView::Ripples(GAGenome& genome) {
	float x =0;
	float y =0;
	if(_whichRep == BINARY_4BIT || _whichRep == BINARY_8BIT) {
		GABin2DecGenome& g = (GABin2DecGenome&)genome;
		x = g.phenotype(0);
		y = g.phenotype(1);
	}
	else {
		GARealGenome& g = (GARealGenome&)genome;
		x = g.gene(0);
		y = g.gene(1);
	}

	double z = sin(sqrt(x*x + y*y))*sin(sqrt(x*x + y*y)) - 0.5;
	z /= ((1.0 + 0.001*(x*x + y*y))*(1.0 + 0.001*(x*x + y*y)));
	z = (0.5 - z);
	return (float)z;
}



/*****************************************************************************/
/* Type:        2D FUNCTION                                                  */
/* Name:        Objective2D_5                                                */
/* Description: Mexican Hat                                                  */
/* Boundaries:  -10 < x < 10                                                 */
/*              -10 < y < 10                                                 */
/* Source:      same as ripples but with center shifted by 2 in x            */
/*****************************************************************************/
float CGademoView::RipplesShifted(GAGenome& genome) {
	float x =0;
	float y =0;
	if(_whichRep == BINARY_4BIT || _whichRep == BINARY_8BIT) {
		GABin2DecGenome& g = (GABin2DecGenome&)genome;
		x = g.phenotype(0);
		y = g.phenotype(1);
	}
	else {
		GARealGenome& g = (GARealGenome&)genome;
		x = g.gene(0);
		y = g.gene(1);
	}

	double z = sin(sqrt((x-2)*(x-2) + y*y))*sin(sqrt((x-2)*(x-2) + y*y)) - 0.5;
	z /= ((1.0 + 0.001*((x-2)*(x-2) + y*y))*(1.0 + 0.001*((x-2)*(x-2) + y*y)));
	z = (0.5 - z);
	return (float)z;
}