travelspview.cpp

用遗传算法实现巡回旅行商（邮差问题）的程序。可自由设置城市位置及数目

// travelSPView.cpp : implementation of the CTravelSPView class
//

#include "stdafx.h"
#include "travelSP.h"
#include "item.h"
#include "count.h"
#include "travelSPDoc.h"
#include "travelSPView.h"
#include "preinit.h"

#include "stdlib.h"

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

/////////////////////////////////////////////////////////////////////////////
// CTravelSPView

IMPLEMENT_DYNCREATE(CTravelSPView, CView)

BEGIN_MESSAGE_MAP(CTravelSPView, CView)
	//{{AFX_MSG_MAP(CTravelSPView)
	ON_COMMAND(ID_SETPREINIT, OnSetpreinit)
	ON_WM_LBUTTONDOWN()
	ON_COMMAND(ID_RUN, OnRun)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CTravelSPView construction/destruction

CTravelSPView::CTravelSPView()
{
	// TODO: add construction code here
	isrunning=0;
}

CTravelSPView::~CTravelSPView()
{
}

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

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CTravelSPView drawing

void CTravelSPView::OnDraw(CDC* pDC)
{
	CTravelSPDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here

	CString str;
	int i,x,y;
	str.Format("maxindiv=%d  maxgen=%d  citysum=%d  crossrate=%.4lf",pDoc->maxindiv,pDoc->maxgen,pDoc->citysum,pDoc->crossrate);
	pDC->TextOut(0,0,str);
	pDC->TextOut(0,40,"Set the position of cities with mouse.Less than 500 cities.");
	pDC->Rectangle(3,60,580,480);
	for(i=0;i<pDoc->citysum;i++)
	{
		x=pDoc->citysite[i].x;
		y=pDoc->citysite[i].y;
		pDC->SetPixel(x,y,RGB(80,0,150));
		pDC->Rectangle(x-2,y-2,x+2,y+2);
		str.Format("%d",i);
		pDC->TextOut(x+2,y-2,str);
	}

	if(pDoc->complete_run==1)
	{
		CPen pen1(PS_SOLID,1,RGB(0,0,200));
		pDC->SelectObject(&pen1);
		pDC->MoveTo(pDoc->citysite[pDoc->bestcitynumseries[0]]);
		for(i=1;i<pDoc->citysum;i++)
			pDC->LineTo(pDoc->citysite[pDoc->bestcitynumseries[i]]);
		pDC->LineTo(pDoc->citysite[pDoc->bestcitynumseries[0]]);
		str.Format("最佳路线如图,长度:%.4lf，查看文件calcdata.txt和result.txt",pDoc->best_s);
		pDC->TextOut(1,20,str);
		
	}

}

/////////////////////////////////////////////////////////////////////////////
// CTravelSPView diagnostics

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CTravelSPView message handlers

void CTravelSPView::OnSetpreinit() 
{
	preinit init;
	CTravelSPDoc* pDoc = GetDocument();
	if(isrunning==0)
	if(init.DoModal())
	{
		pDoc->maxindiv=init.m_maxindiv;
		pDoc->maxgen=init.m_maxgen;
		pDoc->crossrate=init.m_crossrate;
	}
	this->Invalidate();
		

}

void CTravelSPView::OnLButtonDown(UINT nFlags, CPoint point) 
{
	
	CTravelSPDoc* pDoc = GetDocument();
	pDoc->complete_run=0;

	if(point.x>6&&point.x<560&&point.y>64&&point.y<466&&isrunning==0)
	{
		pDoc->complete_run=0;
		pDoc->citysum++;
		pDoc->citysite[pDoc->citysum-1]=point;  
		
	}
	CView::OnLButtonDown(nFlags, point);
	this->Invalidate();
}

void CTravelSPView::OnRun() 
{
	CTravelSPDoc* pDoc = GetDocument();
	count pcount;
	int i;	FILE *fp;
	struct CityMsg *tempcity;

	pcount.maxgen=pDoc->maxgen;
	pcount.citysum=pDoc->citysum;
	pcount.maxindiv=pDoc->maxindiv;
	pcount.crossrate=pDoc->crossrate;
	pcount.citysite =pDoc->citysite;

	pDoc->best_s=0;
	pDoc->bestcitynumseries=(int *)calloc(sizeof(int),pcount.citysum);
	isrunning=1;
	pcount.init();
	fp=fopen("calcdata.txt","a");
	for(i=1;i<=pcount.maxgen;i++)//only there,i from 1.
	{
		pcount.producegen();//produce a new generation and calculate th fitness.
		tempreport(pcount,i,fp);   //report and select the best one.
		tempcity=pcount.city;
		pcount.city=pcount.newcity;
		pcount.newcity=tempcity;
		processinfo(i,pcount.maxgen);//
	}
	fclose(fp);
	fp=fopen("result.txt","w");
	finalreport(fp);
	fclose(fp);
	isrunning=0;

	this->Invalidate(TRUE);
	
}
//////////////report the result:
void CTravelSPView::tempreport(count pcount,int n,FILE *fp)
{

	CString str1,str2;
	int i,j,best_i;
	double best_s,bestfitness=0;
	CTravelSPDoc* pDoc = GetDocument();	
	str2.Format("第%d代：\n",n);
	for(i=0;i<pcount.maxindiv;i++)
	{
		str1.Format("%4d: ",i);
		str2+=str1;
		for(j=0;j<pcount.citysum;j++)
		{
			str1.Format("%d ",pcount.newcity[i].citynum[j]);
			str2+=str1;
		}
		str1.Format(" fit: %.4lf\n",pcount.newcity[i].fitness);
		str2+=str1;
		if(pcount.newcity[i].fitness>bestfitness)
		{
			bestfitness=pcount.newcity[i].fitness;
			best_s=pcount.fit_t-pcount.newcity[i].fitness;
			best_i=i;
		}
	}

	str1.Format("最佳个体：%d  ,最短路径：%.4lf\n\n",best_i,best_s);
	str2+=str1;
	if(pDoc->best_s==0||pDoc->best_s>best_s)
	{
		pDoc->best_s=best_s;
		pDoc->bestcitygen=n;
		for(j=0;j<pcount.citysum;j++)
			pDoc->bestcitynumseries[j]=pcount.newcity[best_i].citynum[j];
	}
	fprintf(fp,"%s",str2);
	
}


void CTravelSPView::finalreport(FILE *fp)
{
	int i;
	CString str1,str2;
	CTravelSPDoc* pDoc = GetDocument();	
	str2="\n\n------------------------------------------------\n最后结果：\n";
	str1.Format("最佳个体所在的代：%d       最短路程：%.4lf \n",pDoc->bestcitygen,pDoc->best_s);
	str2+=str1;
	str2+="\n其基因系列为：\n";
	for(i=0;i<pDoc->citysum;i++)
	{
		str1.Format("%d  ",pDoc->bestcitynumseries[i]);
		str2+=str1;
	}
	fprintf(fp,"%s",str2);
	pDoc->complete_run=1;


}

void CTravelSPView::processinfo(int i,int n)
{
	double proc;
	CClientDC dc(this);
	CString str;
	proc=100*(double)i/(double)n;
	str.Format("正在运行 %.1lf %%...",proc);
	dc.TextOut(1,20,str);


}