tspdemoview.cpp

用vc编的tsp算法

// tspdemoView.cpp : implementation of the CTspdemoView class
//

#include "stdafx.h"

#include <math.h>
#include "tspdemo.h"

#include "tspdemoDoc.h"
#include "tspdemoView.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CTspdemoView

IMPLEMENT_DYNCREATE(CTspdemoView, CView)

BEGIN_MESSAGE_MAP(CTspdemoView, CView)
	//{{AFX_MSG_MAP(CTspdemoView)
	ON_COMMAND(GA_CNTRL_EVOLVE, OnEvolve)
	ON_COMMAND(GA_CNTRL_REWIND, OnReset)
	ON_COMMAND(GA_CNTRL_STEP, OnStep)
	ON_COMMAND(GA_CNTRL_STOP, OnStop)
	ON_COMMAND(GA_MALG_CROWDING, OnSelectGACrowding)
	ON_COMMAND(GA_MALG_SIMPLE, OnSelectGASimple)
	ON_COMMAND(GA_MALG_SS, OnSelectGASteadyState)
	ON_COMMAND(GA_CNTRL_SOME, OnEvolveSome)
	ON_UPDATE_COMMAND_UI(GA_MALG_CROWDING, OnUpdateGACrowding)
	ON_UPDATE_COMMAND_UI(GA_MALG_DEME, OnUpdateGADeme)
	ON_UPDATE_COMMAND_UI(GA_MALG_INCREMENTAL, OnUpdateGAIncremental)
	ON_UPDATE_COMMAND_UI(GA_MALG_SIMPLE, OnUpdateGASimple)
	ON_UPDATE_COMMAND_UI(GA_MALG_SS, OnUpdateGASteadyState)
	ON_COMMAND(GA_MALG_DEME, OnSelectGADeme)
	ON_COMMAND(GA_MALG_INCREMENTAL, OnSelectGAIncremental)
	ON_COMMAND(GA_PARAMETERS, OnParameters)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CTspdemoView construction/destruction

CTspdemoView::CTspdemoView(){
	_whichFunction = MIN_DIST;
	_whichGA = SIMPLE;

	_theGenome = 0;
	_theGA = 0;
	_params = 0;
	
	_pmut = 0.01;
	_pcross = 0.9;
	_ngen = 150;
	_popsize = 40;

	_enabled = 1;
	_running = 0;

	configure();
}

CTspdemoView::~CTspdemoView(){
	delete _theGA;
	delete _theGenome;
	delete _params;
}

BOOL CTspdemoView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CTspdemoView drawing

void CTspdemoView::OnDraw(CDC* pDC){
	CTspdemoDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);

	draw(pDC);
}

/////////////////////////////////////////////////////////////////////////////
// CTspdemoView diagnostics

#ifdef _DEBUG
void CTspdemoView::AssertValid() const
{
	CView::AssertValid();
}

void CTspdemoView::Dump(CDumpContext& dc) const
{
	CView::Dump(dc);
}

CTspdemoDoc* CTspdemoView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CTspdemoDoc)));
	return (CTspdemoDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CTspdemoView message handlers

void CTspdemoView::OnEvolve() {
	if(!_running) {
		_enabled = -1;
		AfxBeginThread(Evolve, this, THREAD_PRIORITY_NORMAL);
	}
}

void CTspdemoView::OnReset() {
	_enabled = 0;
	while(_running) { ; } // wait for thread to stop
	_theGA->initialize();
	InvalidateRect(NULL);
}

void CTspdemoView::OnStep() {
	if(!_running) {
		_enabled = _theGA->generation()+1;
		AfxBeginThread(Evolve, this, THREAD_PRIORITY_NORMAL);
	}
}

void CTspdemoView::OnStop() {
	_enabled = 0;
}

void CTspdemoView::OnEvolveSome() {
	if(!_running) {
		_enabled = _theGA->generation()+10;
		AfxBeginThread(Evolve, this, THREAD_PRIORITY_NORMAL);
	}
}




UINT CTspdemoView::Evolve(LPVOID param) {
	CTspdemoView* ptr = reinterpret_cast<CTspdemoView*>(param);

	if(ptr->_running) return 0;
	int n = ptr->_enabled;
	while(ptr->_enabled != 0) {
		ptr->_running = 1;
		if((n < 0 && ptr->_theGA->done() == gaFalse) || ptr->_theGA->generation() < n){
			ptr->_theGA->step();
			ptr->InvalidateRect(NULL);
		}
		else {
			ptr->_enabled = 0;
		}
	}
	ptr->_running = 0;
	ptr->InvalidateRect(NULL);
	return 0;
}








void CTspdemoView::OnSelectGASimple() {
	_whichGA = SIMPLE;
	configure();	
	InvalidateRect(NULL);
}

void CTspdemoView::OnSelectGASteadyState() {
	_whichGA = STEADY_STATE;
	configure();	
	InvalidateRect(NULL);
}

void CTspdemoView::OnSelectGAIncremental() {
	_whichGA = INCREMENTAL;
	configure();	
	InvalidateRect(NULL);
}

void CTspdemoView::OnSelectGACrowding() {
	_whichGA = CROWDING;
	configure();	
	InvalidateRect(NULL);
}

void CTspdemoView::OnSelectGADeme() {
	_whichGA = DEME;
	configure();	
	InvalidateRect(NULL);
}

void CTspdemoView::OnUpdateGASimple(CCmdUI* pCmdUI) {
	if(_whichGA == SIMPLE) pCmdUI->SetCheck(1);
	else pCmdUI->SetCheck(0);
}

void CTspdemoView::OnUpdateGASteadyState(CCmdUI* pCmdUI) {
	if(_whichGA == STEADY_STATE) pCmdUI->SetCheck(1);
	else pCmdUI->SetCheck(0);
}

void CTspdemoView::OnUpdateGAIncremental(CCmdUI* pCmdUI) {
	if(_whichGA == INCREMENTAL) pCmdUI->SetCheck(1);
	else pCmdUI->SetCheck(0);
}

void CTspdemoView::OnUpdateGACrowding(CCmdUI* pCmdUI) {
	if(_whichGA == CROWDING) pCmdUI->SetCheck(1);
	else pCmdUI->SetCheck(0);
}

void CTspdemoView::OnUpdateGADeme(CCmdUI* pCmdUI) {
	if(_whichGA == DEME) pCmdUI->SetCheck(1);
	else pCmdUI->SetCheck(0);
}





void CTspdemoView::OnParameters() {
	if(! _params) {
		_params = new CGAParametersDialog(this);
		_params->m_pcross = pCrossover();
		_params->m_pmut = pMutation();
		_params->m_ngen = nGenerations();
		_params->m_popsize = populationSize();
		if(_params->Create() != TRUE) {
			delete _params;
			_params = 0;
		}
	}
	else {
		_params->ShowWindow(SW_RESTORE);
		_params->EnableWindow();
		_params->UpdateWindow();
//		_params->SetActiveWindow();
	}

	if(_params) {
		_params->GetDlgItem(IDC_APPLY)->EnableWindow(FALSE);
		_params->GetDlgItem(IDC_REVERT)->EnableWindow(FALSE);
	}
}




float CTspdemoView::pCrossover(float n) {
	if(0.0<=n && n<=1.0) {
		_pcross = _theGA->pCrossover(n);
	}
	return _pcross;
}
float CTspdemoView::pMutation(float n) {
	if(0.0<=n && n<=1.0) {
		_pmut = _theGA->pMutation(n);
	}
	return _pmut;
}
int CTspdemoView::populationSize(int n) {
	return _popsize = _theGA->populationSize(n);
}
int CTspdemoView::nGenerations(int n) {
	return _ngen = _theGA->nGenerations(n);
}







int CTspdemoView::ntowns = 0;
double CTspdemoView::DISTANCE[MAX_TOWNS][MAX_TOWNS];
double CTspdemoView::x[MAX_TOWNS];
double CTspdemoView::y[MAX_TOWNS];
double CTspdemoView::theight;
double CTspdemoView::twidth;

// read in the information we need to do the tsp problem
int
CTspdemoView::readConfigFile() {
  ifstream in(TSP_FILE);
  if(in.eof()) {
 //   cerr << "could not read data file " << TSP_FILE << "\n";
    return 1;
  }
  ntowns=0;
  do {
	double dump;
    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";
    return 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];
  }
  twidth = maxx - minx;
  theight = maxy - miny;

  return 0;
}

// Configure the genome and/or genetic algorithm based upon the
// settings that have been specified via the user interface.
// First we create a genome, then we configure it, then we create
// a genetic algorithm using the genome (the GA clones the genome
// to create its population, so the genome must be configured
// before we create the genetic algorithm).  Finally, we set the
// parameters on the genetic algorithm.
void 
CTspdemoView::configure() {
	if(readConfigFile()) return;

	delete _theGenome;

	_theGenome = new GAListGenome<int>;
	_theGenome->initializer(Initializer);
	_theGenome->comparator(Comparator);