tspdlg.cpp

TSP算法在VC环境中的另类实现

// TSPDlg.cpp : implementation file
//

#include "stdafx.h"
#include "TSP.h"
#include "TSPDlg.h"
#include <math.h>
#include <iostream>
#include <time.h>
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif
#define PopSize 50
using namespace std; 
/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About
int generation;          
int CurBest;            
struct GenoType
{
	int gene[NumVars];     
	double fitness;       
	double rfitness;      
	double cfitness;       
};
GenoType Individual[PopSize+1];      
GenoType newIndividual[PopSize+1];   
double  r[NumVars][NumVars]={
     	0, 1, 4, 6, 8, 1, 3, 7, 
 		1, 0, 7, 5, 3, 8, 3, 4, 
 		4, 7, 0, 3, 8, 3, 7, 9, 
 		6, 5, 3, 0, 3, 1, 5, 2, 
 		8, 3, 8, 3, 0, 2, 3, 1, 
 		1, 8, 3, 1, 2, 0, 3, 3, 
 		3, 3, 7, 5, 3, 3, 0, 7, 
 		7, 4, 9, 2, 1, 3, 7, 0,
 } ;//对称
class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CTSPDlg dialog

CTSPDlg::CTSPDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CTSPDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CTSPDlg)
	begincity = 0;
	MaxGens = 400;
	PMutation = 15;
	PXCross = 80;
	m_reasult = _T("");
	m_matrix = _T("");
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CTSPDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CTSPDlg)
	DDX_Text(pDX, IDC_EDIT_Begincity, begincity);
	DDX_Text(pDX, IDC_EDIT_MaxGens, MaxGens);
	DDX_Text(pDX, IDC_EDIT_PMutation, PMutation);
	DDX_Text(pDX, IDC_EDIT_PXCross, PXCross);
	DDX_Text(pDX, IDC_EDIT6, m_reasult);
	DDX_Text(pDX, IDC_EDIT1, m_matrix);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CTSPDlg, CDialog)
	//{{AFX_MSG_MAP(CTSPDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CTSPDlg message handlers

BOOL CTSPDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CTSPDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CTSPDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}
// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CTSPDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}
void swap(int *a,int *b)            
{
	int temp;
	temp=*a;
	*a=*b;
	*b=temp;
}
int IntGenerate()                       
{
	int RANGE_MIN = 0;
	int RANGE_MAX = NumVars;
	int rand10 = (((double) rand()/(double) RAND_MAX) * RANGE_MAX + RANGE_MIN);
	return rand10;    
}
void Keep_the_best() 
{
	int mem,i;
	CurBest=0;  
	for(mem=1;mem<PopSize;mem++)	
		if(Individual[mem].fitness<Individual[CurBest].fitness) // 冒泡找出最优 
			CurBest=mem;
	for(i=0;i<NumVars;i++)
		Individual[PopSize].gene[i]=Individual[CurBest].gene[i];
	Individual[PopSize].fitness=Individual[CurBest].fitness;
}
/**************************************************************/
/* name:Elitist
   author:wu
   function:择优
   time:2009年2月5日*/
/**************************************************************/
void Elitist()    
{
	int i;
	double best,worst;
	int best_mem,worst_mem;
	best=Individual[0].fitness;
	worst=Individual[0].fitness;
	//冒泡比较两个个体中的适应度，并可能选择较大的放入worst_mem和较小的放入best_mem 
	for(i=0;i<PopSize-1;++i)
	{
		if(Individual[i].fitness<Individual[i+1].fitness)
		{
			if(Individual[i].fitness<=best)
			{
				best=Individual[i].fitness;
				best_mem=i;
			}
			if(Individual[i+1].fitness>=worst)
			{
				worst=Individual[i+1].fitness;
				worst_mem=i+1;
			}
		}
		else
		{
			if(Individual[i].fitness>=worst)
			{
				worst=Individual[i].fitness;
				worst_mem=i;
			}
			if(Individual[i+1].fitness<=best)
			{
				best=Individual[i+1].fitness;
				best_mem=i+1;
			}
		} 
}
//如果新种群中最优个体优于父代中最优个体，则将其保存下来, 否则将当代中最差个体替换为父代中最优个体 
	if(best<=Individual[PopSize].fitness)
	{
		for(i=0;i<NumVars;i++)
			Individual[PopSize].gene[i]=Individual[best_mem].gene[i];
		Individual[PopSize].fitness=Individual[best_mem].fitness;    
	}
	else
	{
		for(i=0;i<NumVars;i++)
			Individual[worst_mem].gene[i]=Individual[PopSize].gene[i];
		Individual[worst_mem].fitness=Individual[PopSize].fitness;
	}
}
/**************************************************************/
/* name:Generation
   author:wu
   function:生成个体
   time:2009年2月5日*/
/**************************************************************/
void Generation()     
{
	int mem,i,j;     
	double sum=0.0;
	double p;
	double x[PopSize];
	for(mem=0;mem<PopSize;mem++)
		sum+=Individual[mem].fitness;
    // 由于此处选择应是fitness越小越好，而传统的轮盘赌算法为适应值越大越好，顾需将其做一个转换   
	for(mem=0;mem<PopSize;mem++)    
		x[mem]=sum-Individual[mem].fitness;

	sum=0.0;
	for(mem=0;mem<PopSize;mem++)
		sum+=x[mem];
	for(mem=0;mem<PopSize;mem++)
		Individual[mem].rfitness=x[mem]/sum;//求得适应率
	Individual[0].cfitness=Individual[0].rfitness;
	for(mem=1;mem<PopSize;mem++)                         
	{
		Individual[mem].cfitness=Individual[mem-1].cfitness+Individual[mem].rfitness;
	}
	for(i=0;i<PopSize;i++)
	{
		p=rand()%1000/1000.0;
		if(p<Individual[0].cfitness)
			newIndividual[i]=Individual[0];
		else
		{
			for(j=0;j<PopSize;j++)
				if(p>=Individual[j].cfitness && p<Individual[j+1].cfitness)
					newIndividual[i]=Individual[j+1];
		}
	}
	for(i=0;i<PopSize;i++)//将新种群中的个体复制到原种群中
	Individual[i]=newIndividual[i];
}

void CTSPDlg::OnOK() 
{
	UpdateData(true);
	int i; 
	generation = 0;
	srand( (unsigned)time( NULL ) ); 
	initialize();
	Evaluate();
	Keep_the_best();	
	while(generation<MaxGens)
	{
		
		generation++;
		Generation();
		crossover();
		Mutation();
		Evaluate();  
		Elitist();
	}
    CString csResult;	
	m_reasult="";
    csResult.Format("最佳路径为:");
    m_reasult+=csResult;
    csResult.Format("%d",begincity);
    m_reasult+=csResult;
	for (i = 1; i < NumVars; i++)
	{
		csResult.Format("-->%d",Individual[PopSize].gene[i]);
		m_reasult+=csResult;
	}
   csResult.Format("\r\n最佳适应值为：");
   m_reasult+=csResult;
   csResult.Format("%f",Individual[PopSize].fitness);
   m_reasult+=csResult;
	csResult.Format("\r\n程序执行完毕!\r\n");
	m_reasult+=csResult;
	UpdateData(false);
}
/**************************************************************/
/* name:mutate
   author:wu
   function:变异
   time:2009年2月4日*/
/**************************************************************/
void CTSPDlg::Mutation()
{
	int i;
	double x;
	int x1,x2;	
	for(i=0;i<PopSize;i++)
	{    
		x=(int)rand()%1000/1000.0;
		if(x<PMutation/100)
		{
			x1=0;
			x2=0;
			while(x1==0)
				x1=IntGenerate();
			while(x2==0)
				x2=IntGenerate();
			swap(&Individual[i].gene[x1],&Individual[i].gene[x2]);
		}
	}
}
/**************************************************************/
/* name:crossover
   author:Wu
   function:交叉
   time:2009年2月4日*/
/**************************************************************/
void CTSPDlg::crossover()
{
	int i,j;
	int min,max,flag;
	double x;
	for(i=0;i<PopSize;i++)
    {   
		x=rand()%1000/1000.0;
		if(x<PXCross/100)
		{
			min=0;
			max=0;
			while(min==0)
				min=IntGenerate();
			while(max==0)
				max=IntGenerate();
			if(max<min)
			{
				int temp;
				temp=max;
				max=min;
				min=temp;
			}
			flag=max;
			for(j=min;j<=(max+min)/2;j++)
			{
				swap(&Individual[i].gene[j],&Individual[i].gene[flag]);
				flag=flag-1;
			}
		}
    }
}
/*******************************************************/
/* name:evaluate
   author:Wu
   function:评估
   time:2009年2月4日*/         
/*******************************************************/
void CTSPDlg::Evaluate()
{
	int current_city=begincity;
	int next_city;
	
	for(int mem=0;mem<PopSize;mem++)
	{
		Individual[mem].fitness=0;
		for(int i=1;i<NumVars;i++)    
		{
			next_city=Individual[mem].gene[i];
			Individual[mem].fitness += r[current_city][next_city]; 
			current_city=next_city;
		}
		Individual[mem].fitness += r[current_city][begincity];
	}
}
/*******************************************************/
/* name:initialize()
   author:Wu
   function:初始化
   time:2009年2月4日*/         
/*******************************************************/
void CTSPDlg::initialize()
{
	UpdateData(true);
	int matrix[NumVars];
	int x1,x2;  
	int i,j,k;
	if (m_matrix!="")
	{
		for (i=0;i<NumVars;i++)
		{
			for (j=0;j<NumVars;j++)
			{
				r[i][j]=0;
			}
		}
		for (k=0;k<m_matrix.GetLength();k++)
		{
			if (m_matrix[k]=='(')
			{
              i=m_matrix[k+1]-48;
			  j=m_matrix[k+3]-48;
			  if (i>=0&&i<=7&&j>=0&&j<=7)
			  {
				  r[i][j]=m_matrix[k+5]-48;
                  r[j][i]=m_matrix[k+5]-48;
			  }
			 else
				 AfxMessageBox("距离设置不正确!");
			}
			k=k+6;
		}
		
	}
	for(i=1; i<NumVars; i++)   	//生成一个定值序列 ，0点为开始点，无需改变 
		matrix[i]=i;
	for(j=0;j<PopSize;j++)    
	{
		Individual[j].gene[0]=begincity;   //gene[0]表示出发城市
		
		for(int i=0;i<NumVars;i++)  //NumVars次交换来生成下一代
		{
			x1=0; x2=0;
			while(x1==0)
				x1=IntGenerate();
			while(x2==0)
				x2=IntGenerate();
			swap(&matrix[x1],&matrix[x2]);
		}
		for(i=1;i<NumVars;i++)
		Individual[j].gene[i]=matrix[i];
	}
}