tspview.c

麻省理工开发的免费遗传算法类库GAlib,很好用

#undef SCALE
#undef BUF




















// Here are the genome operators that we want to use for this problem.
float
Objective(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;
}

void
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
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
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
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
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 we override the _write method for the List class.  This lets us see
// exactly what we want (the default _write method dumps out pointers to the
// data rather than the data contents).
//   This routine prints out the contents of each element of the list, 
// separated by a space.  It does not put a newline at the end of the list.
//   Notice that you can override ANY function of a template class.  This is
// called "specialization" in C++ and it lets you tailor the behaviour of a 
// template class to better fit the type.
int
GAListGenome<int>::write(ostream & os) const
{
  int *cur, *head;
  GAListIter<int> iter(*this);
  if((head=iter.head()) != 0) os << *head << " ";
  for(cur=iter.next(); cur && cur != head; cur=iter.next())
    os << *cur << " ";

  return os.fail() ? 1 : 0;
}


// If your compiler does not do automatic instantiation (e.g. g++ 2.6.8),
// then define the NO_AUTO_INST directive.
#ifdef NO_AUTO_INST
#include <ga/GAList.C>
#include <ga/GAListGenome.C>
template class GAList<int>;
template class GAListGenome<int>;
#endif
































// Here are two versions of the graphic interface.  One version for those of
// you with MOTIF on your systems, and one version for those of you with only
// the athena widget set.  Sorry, no Windoze version yet...

#ifdef USE_MOTIF

Widget
ConstructWidgets(Widget toplevel) {
  Widget shell = 
    XtVaCreatePopupShell("shell", topLevelShellWidgetClass, toplevel, NULL);

  Widget form = 
    XtVaCreateManagedWidget("form", xmFormWidgetClass, shell, NULL);

  Pixmap pix;
  Pixel fg, bg;
  unsigned int depth;
  XtVaGetValues(form, XmNforeground, &fg, XmNbackground, &bg, 
		XmNdepth, &depth, NULL);
  pix = 
    XCreatePixmapFromBitmapData(XtDisplay(form),
				RootWindowOfScreen(XtScreen(form)),
				(char *)bm[bmRewind].bits,
				bm[bmRewind].width, bm[bmRewind].height,
				fg, bg, depth);
  Widget rewind = 
    XtVaCreateManagedWidget("rewind", xmPushButtonWidgetClass, form,
			    XmNbottomAttachment, XmATTACH_FORM,
			    XmNlabelType, XmPIXMAP,
			    XmNlabelPixmap, pix,
			    NULL);
  pix = 
    XCreatePixmapFromBitmapData(XtDisplay(form),
				RootWindowOfScreen(XtScreen(form)),
				(char *)bm[bmStop].bits,
				bm[bmStop].width, bm[bmStop].height,
				fg, bg, depth);
  Widget stop = 
    XtVaCreateManagedWidget("stop", xmPushButtonWidgetClass, form,
			    XmNleftAttachment, XmATTACH_WIDGET,
			    XmNleftWidget, rewind,
			    XmNbottomAttachment, XmATTACH_FORM,
			    XmNlabelType, XmPIXMAP,
			    XmNlabelPixmap, pix,
			    NULL);
  pix = 
    XCreatePixmapFromBitmapData(XtDisplay(form),
				RootWindowOfScreen(XtScreen(form)),
				(char *)bm[bmForward].bits,
				bm[bmForward].width, bm[bmForward].height,
				fg, bg, depth);
  Widget step = 
    XtVaCreateManagedWidget("step", xmPushButtonWidgetClass, form,
			    XmNleftAttachment, XmATTACH_WIDGET,
			    XmNleftWidget, stop,
			    XmNbottomAttachment, XmATTACH_FORM,
			    XmNlabelType, XmPIXMAP,
			    XmNlabelPixmap, pix,
			    NULL);
  pix = 
    XCreatePixmapFromBitmapData(XtDisplay(form),
				RootWindowOfScreen(XtScreen(form)),
				(char *)bm[bmForwardStop].bits,
				bm[bmForwardStop].width,
				bm[bmForwardStop].height,
				fg, bg, depth);
  Widget some = 
    XtVaCreateManagedWidget("some", xmPushButtonWidgetClass, form,
			    XmNleftAttachment, XmATTACH_WIDGET,
			    XmNleftWidget, step,
			    XmNbottomAttachment, XmATTACH_FORM,
			    XmNlabelType, XmPIXMAP,
			    XmNlabelPixmap, pix,
			    NULL);
  pix = 
    XCreatePixmapFromBitmapData(XtDisplay(form),
				RootWindowOfScreen(XtScreen(form)),
				(char *)bm[bmFastForward].bits,
				bm[bmFastForward].width,
				bm[bmFastForward].height,
				fg, bg, depth);
  Widget evolve = 
    XtVaCreateManagedWidget("evolve", xmPushButtonWidgetClass, form,
			    XmNleftAttachment, XmATTACH_WIDGET,
			    XmNleftWidget, some,
			    XmNbottomAttachment, XmATTACH_FORM,
			    XmNlabelType, XmPIXMAP,
			    XmNlabelPixmap, pix,
			    NULL);
  XtAddCallback(rewind, XmNactivateCallback, ResetCB, (XtPointer)ga);
  XtAddCallback(stop, XmNactivateCallback, StopCB, (XtPointer)ga);
  XtAddCallback(step, XmNactivateCallback, StepCB, (XtPointer)ga);
  XtAddCallback(some, XmNactivateCallback, EvolveSomeCB, (XtPointer)ga);
  XtAddCallback(evolve, XmNactivateCallback, EvolveCB, (XtPointer)ga);

  canvas = 
    XtVaCreateManagedWidget("canvas", xmDrawingAreaWidgetClass, form,
			    XmNtopAttachment, XmATTACH_FORM,
			    XmNrightAttachment, XmATTACH_FORM,
			    XmNleftAttachment, XmATTACH_FORM,
			    XmNbottomAttachment, XmATTACH_WIDGET,
			    XmNbottomWidget, rewind,
			    NULL);
  XtAddCallback(canvas, XmNexposeCallback, DrawCB, (XtPointer)ga);

  return shell;
}

#else

void
ExposureEH(Widget w, XtPointer cd, XEvent*, Boolean*) {
  DrawCB(w,cd,0);
}

Widget
ConstructWidgets(Widget toplevel) {
  Widget form = 
    XtVaCreateManagedWidget("form", formWidgetClass, toplevel, NULL);

  canvas =
    XtVaCreateManagedWidget("canvas", widgetClass, form, NULL);
  XtAddEventHandler(canvas, ExposureMask, False, ExposureEH, (XtPointer)ga);

  Widget ctrlbox = 
    XtVaCreateManagedWidget("controls", boxWidgetClass, form, 
			    XtNfromVert, canvas,
			    XtNorientation, "vertical",
			    NULL);
  Widget rewind = 
    XtVaCreateManagedWidget("rewind", commandWidgetClass, ctrlbox, NULL);
  Widget stop = 
    XtVaCreateManagedWidget("stop", commandWidgetClass, ctrlbox, NULL);
  Widget step = 
    XtVaCreateManagedWidget("step", commandWidgetClass, ctrlbox, NULL);
  Widget some = 
    XtVaCreateManagedWidget("some", commandWidgetClass, ctrlbox, NULL);
  Widget evolve = 
    XtVaCreateManagedWidget("evolve", commandWidgetClass, ctrlbox, NULL);

  XtAddCallback(rewind, XtNcallback, ResetCB,      (XtPointer)ga);
  XtAddCallback(stop,   XtNcallback, StopCB,       (XtPointer)ga);
  XtAddCallback(step,   XtNcallback, StepCB,       (XtPointer)ga);
  XtAddCallback(some,   XtNcallback, EvolveSomeCB, (XtPointer)ga);
  XtAddCallback(evolve, XtNcallback, EvolveCB,     (XtPointer)ga);

  Widget quit = 
    XtVaCreateManagedWidget("quit", commandWidgetClass, ctrlbox, NULL);
  XtAddCallback(quit,   XtNcallback, QuitCB,  (XtPointer)0);

  return toplevel;
}

#endif