mainfrm.cpp

用VC++编写的蚁群算法求解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

//////////////////////////////全局变量定义///////////////////////////////////

std::vector<SYCity> vecCitys;						//城市列表
std::vector<SYCityDistance> vecCityDistances;		//城市距离列表
int CityNumber = 0;									//城市个数
int FileType;										//文件格式 0 无效格式 1 坐标格式 2 对称距离矩阵格式
BOOL IsComputing = FALSE;                           //SA算法开始计算标志  FALSE 未开始计算 TRUE 已开始计算 
double	best_trip_length;
double fMaxCityDistance;
int CURRENT_CITY;
int START_CITY;
int CURRENT_TOUR_INDEX=0;
double tau0;
double ALPHA;
double BETA;
double RHO;
double TAU[100][100];
double dTAU[100][100];
double ETA[100][100];
int CURRENT_TOUR[100][2];
int best_tour[100][2];
double CityDistances[100][100];
int Allowed[100];
int a,b;//用于记录，第a次循环，第b只蚂蚁走的最好
/////////////////////////////////////////////////////////////////////////////
// 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)
	//}}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  蚁群算法ACO求解TSP问题";
	m_strTitle = "智能算法库——蚁群算法ACO求解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();

		pView->ClearInfos();
		
		CString strValue, strTemp;
		BOOL readfilesucflg = TRUE;
		strFileName = pFileDialog->GetPathName();
		CStdioFile DataFile( strFileName, CFile::modeRead );
		CString strReadString;

		DataFile.ReadString(strReadString);
		if( strReadString == "coordinate" )
			FileType = 1;
		else if( strReadString == "distancematrix" )
			FileType = 2;
		else
			FileType = 0;

		if( FileType == 0 )
		{
			readfilesucflg = FALSE;
		}
		else
		{
			if( FileType == 1 )
			{
				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++;
				}
			}
			else if( FileType == 2 )
			{
				int nMatrixRow = 1;			//代表第几个城市所对应的行
				int nMatrixCol = 1;
				int nMaxMatrixCol = -1;		//记录第一行的列数,后续行的列数如果不等于第一行,则数据文件错误
				CString strDistance;
				while( DataFile.ReadString(strReadString) )
				{
					strReadString.TrimLeft();
					strReadString.TrimRight();
	
					if( strReadString.IsEmpty() )
						continue;

					int nspace = 0;
					nMatrixCol = 1;
					while(1)
					{
						nspace = strReadString.Find(" ");
						SYCityDistance tmp_citydistance;
						if( nspace > 0 )
						{
							strDistance = strReadString.Left( nspace );
							tmp_citydistance.m_fDistance = atof( strDistance );
							tmp_citydistance.m_nFromCity = nMatrixRow;
							tmp_citydistance.m_nToCity = nMatrixCol;
							vecCityDistances.push_back( tmp_citydistance );

							strReadString = strReadString.Mid( nspace+1 );
							strReadString.TrimLeft();
						}
						else 
						{
							if( !strReadString.IsEmpty() )
							{
								strDistance = strReadString;
								tmp_citydistance.m_fDistance = atof( strDistance );
								tmp_citydistance.m_nFromCity = nMatrixRow;
								tmp_citydistance.m_nToCity = nMatrixCol;
								vecCityDistances.push_back( tmp_citydistance );

								strReadString.Empty();
								break;
							}
							else
								break;
						}
						nMatrixCol++;
					}

					if( nMaxMatrixCol < 0 )
						nMaxMatrixCol = nMatrixCol;
					else
					{
						if( nMaxMatrixCol != nMatrixCol )
						{
							readfilesucflg = FALSE;
							break;
						}
					}
	
					nMatrixRow++;
				}
			}
		}

		DataFile.Close();

		if( readfilesucflg )
		{
			InitialSA();

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

			strTemp = "计算城市距离完成";
			pView->AddString( strTemp );
		}
		else
		{
			strTemp = "读入数据文件错误";
			pView->AddString( strTemp );
		}
	}
	delete pFileDialog;
}

UINT SACompution(LPVOID pParam)
{
	int nIndex;
		for ( int i=0;i<CityNumber;i++)
			for ( int j=0;j<CityNumber;j++)
			{
		nIndex = i*CityNumber+j;

		std::vector<SYCityDistance>::iterator iter_citydis;
		iter_citydis = vecCityDistances.begin()+nIndex;

	  	CityDistances[i][j]=iter_citydis->m_fDistance;
		ETA[i][j]=1/CityDistances[i][j];
			}

	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 = "ACO算法开始计算…………";
	::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );

	strTemp = "初始化路径上的信息素…………";
	::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );

	double best_length=(double)CityNumber*fMaxCityDistance;
	for (int n=0;n<CityNumber;n++)
	{
		NNAnt * nnANT = new NNAnt(n);
		
		nnANT->search();
		double tour_length=calc_length();
		if (tour_length<best_length)
			best_length=tour_length;
		delete nnANT;
	}
	 tau0=1/((double)best_length);
	for(i=0;i<CityNumber;i++)
		for(int j=0;j<CityNumber;j++)
			TAU[i][j]=tau0;

	strTemp = "开始搜索：";
	::SendMessage( ViewHWND, WYWM_INFOVIEWAPPENDINFO, (WPARAM)(&strTemp), (LPARAM)0 );
	
		ALPHA=1;
		BETA=5;
		RHO=0.65;

best_trip_length=(double)CityNumber*fMaxCityDistance;


for( i=0;i<CityNumber;i++)
		for(int j=0;j<CityNumber;j++)
			dTAU[i][j]=0;

	for (int t=0;t<200;t++)
	{
		for (int k=0;k<CityNumber;k++)
		{
			ACSAnt * acsANT = new ACSAnt(k);


			acsANT->search();


			strTemp = "第";
			strValue.Format("%d",t+1);
			strTemp += strValue;
			strTemp += "次循环第";
			strValue.Format("%2d",k+1);
			strTemp += strValue;
			strTemp += "只蚂蚁找到的路径为：";
			pView->AddString( strTemp );
			
			strValue.Format("%3d",CURRENT_TOUR[0][0]);
			strTemp = strValue;
			for (int f=0;f<CityNumber;f++)
			{
				strValue.Format("%3d",CURRENT_TOUR[f][1]);
			strTemp += strValue;
			}
			pView->AddString( strTemp );

			double tour_length=calc_length();

			strTemp = "路径长度为：";
			strValue.Format("%f",tour_length);
			strTemp += strValue;			
			pView->AddString( strTemp );
		
			if (tour_length<best_trip_length)
			{
			a=t;
			b=k;
			for (int i=0;i<CityNumber;i++)
			{
				best_tour[i][0]=CURRENT_TOUR[i][0];
				best_tour[i][1]=CURRENT_TOUR[i][1];
			}
			best_trip_length=tour_length;
		
			}
	

	for(int n=0;n<CityNumber;n++)
	{
		int i=CURRENT_TOUR[n][0];
		int j=CURRENT_TOUR[n][1];
		dTAU[i][j]+=(1.0/tour_length);
		dTAU[j][i]+=(1.0/tour_length);//由于对称
	}

	delete acsANT;

			}		

		for(int i=0;i<CityNumber;i++)
			for(int j=0;j<CityNumber;j++)
			TAU[i][j]=RHO*TAU[i][j]+dTAU[i][j];

		for( i=0;i<CityNumber;i++)
			for(int j=0;j<CityNumber;j++)
			dTAU[i][j]=0;

		}
			strTemp = "最佳路径为第";
			strValue.Format("%d",(a+1));
			strTemp += strValue;
			strTemp += "次循环第";
			strValue.Format("%d",(b+1));
			strTemp += strValue;
			strTemp += "只蚂蚁找到：";
			pView->AddString( strTemp );


			strValue.Format("%3d",best_tour[0][0]);
			strTemp = strValue;
			for (int k=0;k<CityNumber;k++)
			{
				strValue.Format("%3d",best_tour[k][1]);
			strTemp += strValue;
			}
			pView->AddString( strTemp );
			
			
			strTemp = "路径长度为：";
			strValue.Format("%f",best_trip_length);
			strTemp += strValue;			
			pView->AddString( strTemp );

	return 1;
}
                         
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);
}