mainfrm.cpp

针对基于遗传算法的TSP 问题求解, 尝试了多种遗传操作, 分析了这些操作在遗传算法中的作用, 讨论了基因片段保序在利用遗传算法求解TSP 问题中的重要性.

// MainFrm.cpp : implementation of the CMainFrame class
//

#include "stdafx.h"
#include "TspSA.h"
#include "TspSADoc.h"
#include "TspSAView.h"
#include "math.h"
#include "MainFrm.h"

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

//似乎必须放在下面，如果把这些全局变量定义放在最顶处则报错 why？
std::vector<SYCity> vecCitys;						//城市列表
std::vector<SYCityDistance> vecCityDistances;		//城市距离列表
int CityNumber = 0;									//城市个数
double InitialTemperature = 0.0;					//初始温度
double NowTemperature = 0.0;						//当前迭代温度
int	NowExternalIterNumber = 0;						//当前外循环迭代次数
int NowInnerIterNumber = 0;							//当前内循环迭代次数
BOOL IsComputing = FALSE;

/////////////////////////////////////////////////////////////////////////////
// CMainFrame

IMPLEMENT_DYNCREATE(CMainFrame, CFrameWnd)

BEGIN_MESSAGE_MAP(CMainFrame, CFrameWnd)
	//{{AFX_MSG_MAP(CMainFrame)
	ON_WM_CREATE()
	ON_COMMAND(ID_FILE_OPEN, OnFileOpen)
	ON_COMMAND(ID_FILE_START, OnFileStart)
	ON_UPDATE_COMMAND_UI(ID_FILE_START, OnUpdateFileStart)
	ON_UPDATE_COMMAND_UI(ID_FILE_OPEN, OnUpdateFileOpen)
	ON_COMMAND(ID_APP_GETCODE, OnAppGetcode)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

static UINT indicators[] =
{
	ID_SEPARATOR,           // status line indicator
};

/////////////////////////////////////////////////////////////////////////////
// CMainFrame construction/destruction

CMainFrame::CMainFrame()
{
}

CMainFrame::~CMainFrame()
{
}

int CMainFrame::OnCreate(LPCREATESTRUCT lpCreateStruct)
{
	if (CFrameWnd::OnCreate(lpCreateStruct) == -1)
		return -1;
	
	if (!m_wndStatusBar.Create(this) ||
		!m_wndStatusBar.SetIndicators(indicators,
		  sizeof(indicators)/sizeof(UINT)))
	{
		TRACE0("Failed to create status bar\n");
		return -1;      // fail to create
	}

	// TODO: Delete these three lines if you don't want the toolbar to
	//  be dockable

	return 0;
}

BOOL CMainFrame::PreCreateWindow(CREATESTRUCT& cs)
{
	cs.style &= ~FWS_ADDTOTITLE;
	if( !CFrameWnd::PreCreateWindow(cs) )
		return FALSE;
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	m_strTitle = "www.huisoft.com.cn  模拟退火算法求解TSP问题";
	return TRUE;
}

/////////////////////////////////////////////////////////////////////////////
// CMainFrame diagnostics

#ifdef _DEBUG
void CMainFrame::AssertValid() const
{
	CFrameWnd::AssertValid();
}

void CMainFrame::Dump(CDumpContext& dc) const
{
	CFrameWnd::Dump(dc);
}

#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CMainFrame message handlers


void CMainFrame::OnFileOpen() 
{
	CString strFileName;
	char szFilter[200];
	strcpy( szFilter, "TXT Files (*.txt)|*.txt||" );
	CFileDialog *pFileDialog;
	pFileDialog = new CFileDialog( TRUE, 
								NULL, 
								NULL, 
								OFN_HIDEREADONLY,
								szFilter,
								this );
	if( IDOK == pFileDialog->DoModal() )
	{
		CTspSAView *pView = (CTspSAView*)GetActiveView();
		ClearSA();
		pView->ClearInfos();
		
		CString strValue, strTemp;
		strFileName = pFileDialog->GetPathName();
		CStdioFile DataFile( strFileName, CFile::modeRead );
		CString strReadString;
		int ncityindex = 1;
		while( DataFile.ReadString(strReadString) ) 
		{
			strReadString.TrimLeft();
			strReadString.TrimRight();

			CString cityName, citycodx, citycody;
			int nspace = 0;
			nspace = strReadString.Find(" ");
			if( nspace > 0 )
				cityName = strReadString.Left( nspace );

			strReadString = strReadString.Mid( nspace+1 );
			nspace = strReadString.Find(" ");
			if( nspace > 0 )
				citycodx = strReadString.Left( nspace );

			strReadString = strReadString.Mid( nspace+1 );
			citycody = strReadString;

			SYCity tmpCity;
			tmpCity.m_strName = "城市 "+cityName;
			tmpCity.m_nIndex = ncityindex;
			tmpCity.m_Coordinate.m_fcodx = atof( citycodx );
			tmpCity.m_Coordinate.m_fcody = atof( citycody );

			vecCitys.push_back( tmpCity );

			ncityindex++;
		}
		DataFile.Close();

		InitialSA();
		strTemp = "共读入城市信息";
		strValue.Format("%d",CityNumber);
		strTemp += strValue;
		strTemp += "个";
		pView->AddString( strTemp );

		strTemp = "计算城市距离完成";
		pView->AddString( strTemp );
	}	

	delete pFileDialog;
}

UINT SACompution(LPVOID pParam)
{
	IsComputing = TRUE;

	srand( (unsigned)time( NULL ) );

	CFile cityfile("C:\\sacitysfile.txt", CFile::modeCreate|CFile::modeWrite);
	CFile iterfile("C:\\saitersfile.txt", CFile::modeCreate|CFile::modeWrite);

	CString strTemp, strValue;
	CTspSAView *pView = (CTspSAView*)pParam;
	HWND ViewHWND = pView->GetSafeHwnd();

	strTemp = "开始计算";
	::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );

	SYRouter ResultRouter( NowTemperature, NowExternalIterNumber, NowInnerIterNumber );

	strTemp = "生成初始路径:";
	::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );
	strTemp = FormRouterString( ResultRouter );
	::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );

	while(1)
	{
		strTemp = "新的内循环开始，当前温度为";
		strValue.Format("%10.4f",NowTemperature);
		strTemp += strValue;
		::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );
		strTemp = "当前路径为:";
		::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );
		strTemp = FormRouterString( ResultRouter );
		::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );

		double deltatotaldis = 0.0;
		while(1)
		{
			SYRouter SelRouter( ResultRouter.m_CityRouter, NowTemperature, NowExternalIterNumber, NowInnerIterNumber );

			deltatotaldis = SelRouter.m_fTotalDistance-ResultRouter.m_fTotalDistance;
			if( deltatotaldis <= 0.0 )
			{
				ResultRouter = SelRouter;
			}
			else
			{
				double chgprobability = exp( -(deltatotaldis/NowTemperature) );
				int randomnum = rand();
				double random = ((double)(randomnum%10000))/10000.0;
				if(chgprobability > random )
				{
					ResultRouter = SelRouter;
				}
			}

			if( JudgeOverInnerLoop(0) )
			{
				break;
			}
			else
				NowInnerIterNumber++;
		}

		if( JudgeOverExternalLoop(0) )
			break;
		else
		{
			NowTemperature = CountDownTemperature( NowTemperature, 0 );
			NowExternalIterNumber++;
			NowInnerIterNumber = 0;

			strValue.Format("%d %.4f\n",NowExternalIterNumber, ResultRouter.m_fTotalDistance );
			iterfile.Write( strValue, strValue.GetLength() );

		}
	}

	strTemp = "计算得最佳路径为:";
	::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );
	strTemp = FormRouterString( ResultRouter );
	::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );
	
	GetRouterFileString( ResultRouter, strTemp );
	cityfile.Write( strTemp, strTemp.GetLength() );

	cityfile.Close();
	iterfile.Close();

	IsComputing = FALSE;
	return 0;
}

void CMainFrame::OnFileStart() 
{
	CTspSAView *pView = (CTspSAView*)GetActiveView();
	AfxBeginThread( SACompution, (LPVOID)pView );
}

void CMainFrame::OnUpdateFileStart(CCmdUI* pCmdUI) 
{
	if( vecCityDistances.empty() || IsComputing )
		pCmdUI->Enable(FALSE);
	else
		pCmdUI->Enable(TRUE);
}

void CMainFrame::OnUpdateFileOpen(CCmdUI* pCmdUI) 
{
	if( IsComputing )
		pCmdUI->Enable(FALSE);
	else
		pCmdUI->Enable(TRUE);
}

void CMainFrame::OnAppGetcode() 
{
	CString strTemp;
	strTemp.LoadString(IDS_HELP_HOMEPAGE);
	::ShellExecute(NULL, "open", strTemp, NULL, NULL, SW_SHOWNORMAL);	
}