tspdemoview.cpp

用vc编的tsp算法

	_theGenome->mutator(Mutator);
	_theGenome->crossover(Crossover);
	_theGenome->evaluator(MinimizeDistance);

	delete _theGA;

	GASigmaTruncationScaling sigma;

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

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




// This is the main drawing routine that renders the main window.
// To change how each genome is drawn, you should modify the 
// draw population method.
void 
CTspdemoView::draw(CDC* pDC) {
	TEXTMETRIC  tm;
	pDC->GetTextMetrics( &tm );
	int charht = tm.tmHeight + tm.tmExternalLeading;

	RECT rect;
	GetClientRect(&rect);

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

	if(!_theGenome) {
		pDC->SetTextColor(RGB(0,0,255));
		CString txt;
		txt.Format("no data file loaded");
		pDC->TextOut(width/2, height/3, txt);
		txt.Format("expecting file '%s'", TSP_FILE);
		pDC->TextOut(width/2, 2*height/3, txt);
		return;
	}
	else if(_running != 0) {
		pDC->SetTextColor(RGB(0,0,255));
		CString txt;
		txt.Format("evolving... %d", _theGA->generation());
		pDC->TextOut(20, 30, txt);
		return;
	}

 	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(_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), width, height, 10, 10, 
				&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(), width, height, 10, 10, 
			&greypen, &redpen);
	}
}







// These are the drawing routines that actually render the individual genomes
// to the main window.  If you change the genome type or prefer to see the
// genomes draw a different way, this is the place to do it.

// in ms windows, upper left is 0,0 and lower right is +,+

void 
CTspdemoView::drawPopulation(CDC* pDC, const GAPopulation& pop, 
							int width, int height, int scale, int buf,
							CPen* miscpen, CPen* bestpen) {  
	int nrows = (int)sqrt(1.3333333333 * pop.size()) + 1;
	int ncols = pop.size() / nrows + 1;
	int idx = 0;
	for(int i=0; i<nrows && idx < pop.size(); i++){
		for(int j=0; j<ncols && idx < pop.size(); j++){
		drawIndividual(pDC, pop.best(idx++),
			buf + i*(scale*twidth+buf),
			buf + j*(scale*theight+buf), scale);
		}
	} 
}

void 
CTspdemoView::drawIndividual(CDC* pDC, GAGenome& g, int xx, int yy, int scale) {
	GAListGenome<int>& genome = (GAListGenome<int>&)g;
	if(genome.size() > 0) {
		for(int i=0; i<genome.size()+1; i++){
			int sidx = *genome.current();
			int eidx = *genome.next();
			pDC->MoveTo(xx+scale*x[sidx], yy+scale*y[sidx]);
			pDC->LineTo(xx+scale*x[eidx], yy+scale*y[eidx]);
		}
	}
}








// If your genome needs a custom comparator, crossover, mutator,
// or initializer, define it here.  You can assign it to the
// genome later.  For the TSP we have custom methods for initializing,
// mutating, crossing, and comparison.

void
CTspdemoView::Initializer(GAGenome& g) {
  GAListGenome<int> &child=(GAListGenome<int> &)g;
  while(child.head()) child.destroy(); // destroy any pre-existing list

  int i,town;
  static int visit[MAX_TOWNS];

  memset(visit, 0, MAX_TOWNS*sizeof(int));
  town=GARandomInt(0,ntowns-1);
  visit[town]=1;
  child.insert(town,GAListBASE::HEAD); // the head node
 
  for( i=1; i<ntowns; i++) {
    do {
      town=GARandomInt(0,ntowns-1);
    } while (visit[town]);
    visit[town]=1;
    child.insert(town);
  }             // each subsequent node 
}

int
CTspdemoView::Mutator(GAGenome& g, float pmut) {
  GAListGenome<int> &child=(GAListGenome<int> &)g;
  register int n, i;
  if ((GARandomFloat() >= pmut) || (pmut <= 0)) return 0;

  n = child.size();
  
  if (GARandomFloat()<0.5) {
    child.swap(GARandomInt(0,n-1),GARandomInt(0,n-1)); // swap only one time
  }
  else {
    int nNodes = GARandomInt(1,((int)(n/2-1)));       // displace nNodes 
    child.warp(GARandomInt(0,n-1));                   // with or without
    GAList<int> TmpList;                              // inversion
    for(i=0;i<nNodes;i++) {
      int *iptr = child.remove();
      TmpList.insert(*iptr,GAListBASE::AFTER);
      delete iptr;
      child.next();
    }
    int invert;
    child.warp(GARandomInt(0,n-nNodes));
    invert = (GARandomFloat()<0.5) ? 0 : 1;
    if (invert) TmpList.head(); else TmpList.tail();

    for(i=0;i<nNodes;i++) {
      int *iptr = TmpList.remove();
      child.insert(*iptr,GAListBASE::AFTER);
      delete iptr;
      if (invert) TmpList.prev(); else TmpList.next();
    }
  }
  child.head();         // set iterator to root node

  return (1);
}

int
CTspdemoView::Crossover(const GAGenome& g1, const GAGenome& g2, GAGenome* c1, GAGenome* c2) {
  int nc=0;
  if(c1) { ERXOneChild(g1,g2,c1); nc+=1; }
  if(c2) { ERXOneChild(g1,g2,c2); nc+=1; }
  return nc;
}

void
CTspdemoView::ERXOneChild(const GAGenome& g1, const GAGenome& g2, GAGenome* c1) {
  GAListGenome<int> &mate1=(GAListGenome<int> &)g1;
  GAListGenome<int> &mate2=(GAListGenome<int> &)g2;
  GAListGenome<int> &sis=(GAListGenome<int> &)*c1;
  
  int i,j,k,t1,t2,town;

  static char CM[MAX_TOWNS][MAX_TOWNS],visit[MAX_TOWNS];
  memset(CM, 0, MAX_TOWNS*MAX_TOWNS*sizeof(char));
  memset(visit, 0, MAX_TOWNS*sizeof(char));

  while (sis.head()) sis.destroy();

  // create connection matrix
  mate1.head();
  for(j=0; j<ntowns; j++) {
    t1 = *mate1.current(); t2 = *mate1.next();
    CM[t1][t2]=1; CM[t2][t1]=1;
  }
  mate2.head();
  for(j=0; j<ntowns; j++) {
    t1 = *mate2.current(); t2 = *mate2.next();
    CM[t1][t2]=1; CM[t2][t1]=1;
  }
  
  // select 1st town randomly
  town=GARandomInt(0,ntowns-1);
  visit[town]=1; memset(CM[town], 0, MAX_TOWNS*sizeof(char));
  sis.insert(town); // the head node 
  
  GAList<int> PossFollowList;
  GAList<int> FollowersList[5];
  while (PossFollowList.head()) PossFollowList.destroy();
  for(k=0; k<5; k++) {
    while (FollowersList[k].head()) FollowersList[k].destroy(); 
  }
  
  // select the following town with the minimal no of next folling towns
  int nPoss,nFollow;
  for(i=1; i<ntowns; i++) {           
    nPoss = 0;
    for(j=0; j<ntowns; j++) {          // no of poss. following towns
      if (CM[j][town]) {
        nPoss += 1;
        PossFollowList.insert(j);}
    }
    // nPoss = 0;
    if (nPoss == 0) {
      do {town=GARandomInt(0,ntowns-1);} while (visit[town]); // no follower
      visit[town]=1; memset(CM[town], 0, MAX_TOWNS*sizeof(char));
      sis.insert(town); 
    }
    else {
      PossFollowList.head();
      for(j=0; j<nPoss; j++) {
        nFollow = 0; 
        town = (*PossFollowList.current());
        for(k=0; k<ntowns; k++) {
          if (CM[k][town]) nFollow++; 
        }
        FollowersList[nFollow].insert(town);
        PossFollowList.next();
      }
      k=0;
      while (FollowersList[k].size() == 0) k++;
      FollowersList[k].warp(GARandomInt(0,FollowersList[k].size()));
      town = (*FollowersList[k].current());
      visit[town]=1; memset(CM[town], 0, MAX_TOWNS*sizeof(char));
      sis.insert(town); 
    }
    while (PossFollowList.head()) PossFollowList.destroy();
    for(k=0; k<5; k++) {
      while (FollowersList[k].head()) FollowersList[k].destroy(); 
    }
  }
  sis.head();         // set iterator to head of list
}



float
CTspdemoView::Comparator(const GAGenome& g1, const GAGenome& g2) 
{
  GAListGenome<int> &a = (GAListGenome<int> &)g1;
  GAListGenome<int> &b = (GAListGenome<int> &)g2;

  int i,j,t1,t2;
  float dist=ntowns;

  static char CM1[MAX_TOWNS][MAX_TOWNS],CM2[MAX_TOWNS][MAX_TOWNS];
  memset(CM1, 0, MAX_TOWNS*MAX_TOWNS*sizeof(char));
  memset(CM2, 0, MAX_TOWNS*MAX_TOWNS*sizeof(char));

  // create connection matrix CM1
  a.head();
  for(i=0; i<ntowns; i++) {
    t1 = *a.current(); t2 = *a.next();
    CM1[t1][t2]=1; CM1[t2][t1]=1;
  }
  // create connection matrix CM2
  b.head();
  for(i=0; i<ntowns; i++) {
    t1 = *b.current(); t2 = *b.next();
    CM2[t1][t2]=1; CM2[t2][t1]=1;
  }
  //calc distance = how many edges are different
  for (i=0; i<ntowns; i++) {
    for (j=i; j<ntowns; j++) {
      if (CM1[i][j]&CM2[i][j]) dist--;
    }
  }
  return (dist);
}


// Here is/are the objective function(s) that will be used in
// this application.
float
CTspdemoView::MinimizeDistance(GAGenome& g) {
  GAListGenome<int> & genome = (GAListGenome<int> &)g;
  float dist = 0;
  if(genome.head()) {
    for(int i=0; i<ntowns; i++)
      dist += DISTANCE[*genome.current()][*genome.next()];
  }
  return dist;
}