tspview.c

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

/* ----------------------------------------------------------------------------
  tsp.C
  mbwall 17jan96
---------------------------------------------------------------------------- */
#include <stdio.h>
#include <iostream.h>
#include <math.h>
#include <values.h>
#include <ga/ga.h>

// comment this line if you don't have MOTIF on your system
//#define USE_MOTIF

#ifdef USE_MOTIF
#include <Xm/Xm.h>
#include <Xm/Form.h>
#include <Xm/PushB.h>
#include <Xm/Protocols.h>
#include <Xm/DrawingA.h>
#else
#include <X11/Intrinsic.h>
#include <X11/StringDefs.h>
#include <X11/Shell.h>
#include <X11/Xaw/Form.h>
#include <X11/Xaw/Command.h>
#include <X11/Xaw/Box.h>
#endif

// Set this up for your favorite TSP.  The sample one is a contrived problem
// with the towns laid out in a grid (so it is easy to figure out what the 
// shortest distance is, and there are many different paths with the same
// shortest path).  File format is that used by the TSPLIB problems.  You can 
// grab more problems from 
// 
// 
// Apologies for using fixed-length arrays.  But this is an example, not 
// production code ;)
#define MAX_TOWNS 50
#define TSP_FILE "tsp_rect_20.txt"

float DISTANCE[MAX_TOWNS][MAX_TOWNS];
double x[MAX_TOWNS],y[MAX_TOWNS];
int ntowns = 0;
float width, height;


float Objective(GAGenome&);
int   Mutator(GAGenome&, float);
void  Initializer(GAGenome&);
float Comparator(const GAGenome&, const GAGenome&);
int   Crossover(const GAGenome&, const GAGenome&, GAGenome*, GAGenome*);
void  ERXOneChild(const GAGenome&, const GAGenome&, GAGenome*);





#ifdef USE_MOTIF

#include "bitmaps/rew.xbm"
#include "bitmaps/stop.xbm"
#include "bitmaps/fwds.xbm"
#include "bitmaps/ffst.xbm"
#include "bitmaps/ffwd.xbm"

typedef struct _BitmapInfo {
  int width, height;
  unsigned char *bits;
} BitmapInfo;

static BitmapInfo bm[] = {
  {stop_width, stop_height, (unsigned char *)stop_bits},
  {rew_width, rew_height, (unsigned char *)rew_bits},
  {fwds_width, fwds_height, (unsigned char *)fwds_bits},
  {ffst_width, ffst_height, (unsigned char *)ffst_bits},
  {ffwd_width, ffwd_height, (unsigned char *)ffwd_bits}
};

enum {
  bmStop,
  bmRewind,
  bmForward,
  bmForwardStop,
  bmFastForward,
  nBitmaps
};

#endif

Widget ConstructWidgets(Widget);
void QuitCB(Widget, XtPointer, XtPointer);
void InitCB(Widget, XtPointer, XtPointer);
void DrawCB(Widget, XtPointer, XtPointer);
void ResetCB(Widget, XtPointer, XtPointer);
void StopCB(Widget, XtPointer, XtPointer);
void StepCB(Widget, XtPointer, XtPointer);
void EvolveSomeCB(Widget, XtPointer, XtPointer);
void EvolveCB(Widget, XtPointer, XtPointer);
void DrawIndividual(GAGenome&, Display*, Drawable, GC, int, int);
void Refresh();

static int geninc = 10;

static char *fallbacks[] = {
  ".function: 0",
  "*canvas.width:  500",
  "*canvas.height: 300",

// motif-specific fallbacks

  "*fontList:	-*-helvetica-bold-r-*-*-*-140-*-*-*-*-*-*",

// athena-specific fallbacks

  "*font:		-*-helvetica-bold-r-*-*-*-140-*-*-*-*-*-*",

  (char *)NULL
};

static XtWorkProcId procid;
static Boolean Evolve(int);
static XtAppContext appc;
static Widget canvas;
static GAGeneticAlgorithm* ga;
static GC thegc;
static int done = 0;


int
main(int argc, char** argv) {
  cout << "Travelling salesperson demonstration program.  Use the 'ga'\n";
  cout << "option to specify which type of genetic algorithm you would\n";
  cout << "like to use to do the evolution.  Options for the ga are:\n";
  cout << "   1 - steady-state\n";
  cout << "   2 - deterministic crowding\n";
  cout << "   3 - simple\n";
  cout << "\n";
  cout.flush();

// read in the cities and create the DISTANCE-matrix

  double dump;
  ifstream in(TSP_FILE); 
  if(!in) {
    cerr << "could not read data file " << TSP_FILE << "\n";
    exit(1);
  }
  ntowns=0;
  do {
    in >> dump;
    if(!in.eof()) {
      in >> x[ntowns];
      in >> y[ntowns];
      ntowns++;
    }
  } while(!in.eof() && ntowns < MAX_TOWNS);
  in.close();
  if(ntowns >= MAX_TOWNS) {
    cerr << "data file contains more towns than allowed for in the fixed\n";
    cerr << "arrays.  Recompile the program with larger arrays or try a\n";
    cerr << "smaller problem.\n";
    exit(1);
  }


  double dx,dy;
  int i, j;
  for(i=0;i<ntowns;i++) {
    for(j=i; j<ntowns;j++) {
      dx=x[i]-x[j]; dy=y[i]-y[j];
      DISTANCE[j][i]=DISTANCE[i][j]=sqrt(dx*dx+dy*dy);
    }
  }
  float minx=MAXFLOAT, maxx=MINFLOAT, miny=MAXFLOAT, maxy=MINFLOAT;
  for(i=0; i<ntowns; i++) {
    minx = (minx < x[i]) ? minx : x[i];
    maxx = (maxx > x[i]) ? maxx : x[i];
  }
  for(i=0; i<ntowns; i++) {
    miny = (miny < y[i]) ? miny : y[i];
    maxy = (maxy > y[i]) ? maxy : y[i];
  }
  width = maxx - minx;
  height = maxy - miny;


// figure out which GA to use 

  int whichGA = 0;

  for(int ii=1; ii<argc; ii++){
    if(strcmp("ga", argv[ii]) == 0){
      if(++ii >= argc){
        cerr << argv[0] << ": you must specify a ga:\n";
	cerr << "  1 - steady-state\n";
	cerr << "  2 - deterministic crowding\n";
	cerr << "  3 - simple\n";
	cerr << "\n";
        exit(1);
      }
      else{
        whichGA = atoi(argv[ii]);
        continue;
      }
    }
  }


  GAListGenome<int> genome(Objective);
  genome.initializer(::Initializer);
  genome.mutator(::Mutator);
  genome.comparator(::Comparator);
  genome.crossover(::Crossover);

  switch(whichGA){
  case 2:
    {
      ga = new GADCrowdingGA(genome);
      cerr << "  using deterministic crowding GA...\n";
    }
    break;
  case 3:
    {
      ga = new GASimpleGA(genome);
      GASigmaTruncationScaling sigma1;
      ga->scaling(sigma1);
      cerr << "  using simple GA...\n";
    }
    break;
  case 1:
  default:
    {
      ga = new GASteadyStateGA(genome);
      GASigmaTruncationScaling sigma;
      ga->scaling(sigma);
      ga->set(gaNpReplacement, 0.5);
      cerr << "  using steady-state GA...\n";
    }
    break;
  }

  ga->minimize();
  ga->crossover(Crossover);
  ga->populationSize(50);
  ga->nGenerations(10000);
  ga->pMutation(0.3);
  ga->pCrossover(1.0);
  ga->selectScores(GAStatistics::AllScores);
  ga->parameters(argc, argv);
  ga->initialize();



  Widget toplevel = 
    XtAppInitialize(&appc, "TSPView", (XrmOptionDescRec*)NULL, 0,
		    &argc, argv, fallbacks, (ArgList)NULL, 0);
  Widget shell = ConstructWidgets(toplevel);

  XtRealizeWidget(shell);
  XtMapWidget(shell);

  static Atom wmDeleteWindow;
  wmDeleteWindow = XInternAtom(XtDisplay(toplevel), "WM_DELETE_WINDOW", False);
#ifdef USE_MOTIF
  XmAddWMProtocolCallback(shell, wmDeleteWindow, QuitCB, (XtPointer)0);
#else
  XSetWMProtocols(XtDisplay(toplevel), XtWindow(toplevel), &wmDeleteWindow, 1);
#endif

  XtGCMask valueMask = GCFunction | GCLineWidth;
  XGCValues gcValues;
  gcValues.function = GXcopy;
  gcValues.line_width = 2;
  thegc = XCreateGC(XtDisplay(toplevel), 
		    RootWindowOfScreen(XtScreen(toplevel)),
		    valueMask, &gcValues);

  while(!done){
    XEvent event;
    XtAppNextEvent(appc, &event);
    XtDispatchEvent(&event);
  }

  XFreeGC(XtDisplay(toplevel), thegc);
  delete ga;

  return 0;
}
















































Boolean
Evolve(int n){
  if((n < 0 && ga->done() == gaFalse) || ga->generation() < n){
    ga->step();
    if(ga->generation() % 10 == 0){
      cerr << "generation: " << ga->generation() << "\t";
      cerr<<"best score is "<< ga->population().best().score()<<"\n";
    }
    Refresh();
    return False;
  }

  return True;
}

void
ResetCB(Widget, XtPointer cd, XtPointer){
  GAGeneticAlgorithm* ga = (GAGeneticAlgorithm*)cd;
  if(procid){
    XtRemoveWorkProc(procid);
    procid = 0;
  }
  cerr << "initialized\n";
  ga->initialize();
  Refresh();
}

void
StopCB(Widget, XtPointer, XtPointer){
  if(procid){
    XtRemoveWorkProc(procid);
    procid = 0;
  }
}

void
StepCB(Widget, XtPointer cd, XtPointer){
  GAGeneticAlgorithm* ga = (GAGeneticAlgorithm*)cd;
  Evolve(ga->generation() + 1);
}

void
EvolveSomeCB(Widget, XtPointer cd, XtPointer){
  GAGeneticAlgorithm* ga = (GAGeneticAlgorithm*)cd;
  procid = XtAppAddWorkProc(appc, (XtWorkProc)Evolve,
			    (XtPointer)(ga->generation() + geninc));
}

void
EvolveCB(Widget, XtPointer, XtPointer){
  procid = XtAppAddWorkProc(appc, (XtWorkProc)Evolve, (XtPointer)(-1));
}

void
QuitCB(Widget, XtPointer, XtPointer){
  done = 1;
}

#define SCALE 10
#define BUF 10

void
DrawCB(Widget w, XtPointer cd, XtPointer){
  GAGeneticAlgorithm* ga = (GAGeneticAlgorithm*)cd;
  XClearWindow(XtDisplay(w), XtWindow(w));
  int nrows = (int)sqrt(1.3333333333 * ga->population().size()) + 1;
  int ncols = ga->population().size() / nrows + 1;
  int idx = 0;
  for(int i=0; i<nrows && idx < ga->population().size(); i++){
    for(int j=0; j<ncols && idx < ga->population().size(); j++){
      DrawIndividual(ga->population().best(idx++),
		     XtDisplay(w), XtWindow(w), thegc, 
		     BUF + i*(SCALE*width+BUF),
		     BUF + j*(SCALE*height+BUF));
    }
  } 
}


void
Refresh() {
  DrawCB(canvas, (XtPointer)ga, 0);
}


// draw an individual genome at the specified coordinates (in Xwindows space)
// Draw the paths that link the towns.  We draw a complete, closed loop
// so go for one more than the number of nodes in the list.
void
DrawIndividual(GAGenome& g, Display* display, Drawable drawable, GC gc,
	       int xx, int yy) {
  GAListGenome<int>& genome = (GAListGenome<int>&)g;
  for(int i=0; i<genome.size()+1; i++){
    int sidx = *genome.current();
    int eidx = *genome.next();
    XDrawLine(display, drawable, gc, 
	      xx+SCALE*x[sidx], yy+SCALE*y[sidx], 
	      xx+SCALE*x[eidx], yy+SCALE*y[eidx]);
  }
}