tspproblem.cpp

遗传算法vc++语言版源程序,台湾大学编写。

#include "TSPProblem.h"
#include "CommonUtility.h"
#include <fstream>

using namespace std;

//#include "GA1DArraySolution.h"

TSPProblem::TSPProblem(size_t num)
{
/*
	m_City.resize(num);
	for(size_t a=0;a<num;a++)
	{
		//m_City[a].x = ::RG.IRandom(0,100);
		m_City[a].x = cos((double)a*2.0*3.1415926/(double)num);
		m_City[a].y = sin((double)a*2.0*3.1415926/(double)num);
		//m_City[a].y = ::RG.IRandom(0,100);
	}
*/
	m_City.resize(num*num);

	for(int i=0;i<num;i++)
	{
		for(int j=0;j<num;j++)
		{
			m_City[i*num+j].x = i;
			m_City[i*num+j].y = j;
		}
	}

	m_problemDim = m_City.size();
}
TSPProblem::TSPProblem(const TSPProblem& src)
{
//	if(src == NULL) return;

	for(size_t a=0;a<src.m_City.size();a++)
	{
		this->m_City = src.m_City;
	}
	m_problemDim = src.m_problemDim;
}
double TSPProblem::GetResult(void* parm)
{
	//GA1DArraySolution *sol = static_cast<GA1DArraySolution*>(parm);
	vector<double>	*pArray = static_cast<vector<double>*>(parm);

	double dist = 0.0;
	size_t a;
	for(a=0;a<(*pArray).size()-1;a++)
	{
		int c1 = (*pArray)[a];
		int c2 = (*pArray)[a+1];
		dist += Distance(m_City[c1],m_City[c2]);
	}
	dist += Distance(m_City[(*pArray)[a]],m_City[(*pArray)[0]]);
	return dist;
}

void TSPProblem::LogHeader(ostream& os)
{
	os << "Travelling Salesman Problem Configuration:\n";
	os << "Number of Cities:\t" << (int)m_City.size();
	os << "Posistion of Cities:\n";
	os << "\tid\tX\ty\n";
	for(int i=0;i<(int)m_City.size();i++)
	{
		os << "\t" << i << "\t" << m_City[i].x << "\t" << m_City[i].y << endl;
	}
	os << "Distance of Cities:\n";
	os << "\ta\tb\tdistance\n";
	for(int i=0;i<(int)m_City.size();i++)
		for(int j=i+1;j<(int)m_City.size();j++)
			os << "\t" << i << "\t" << j << "\t" << Distance(m_City[i], m_City[j]) << endl;
	os << endl;
}

void TSPProblem::GetExternalData(void* input)
{
	vector<vector<double > > *tar = (vector<vector<double > > *)input;
	tar->resize(m_problemDim);
	for(size_t i=0;i<tar->size();i++)
	{
		(*tar)[i].resize(m_problemDim);
		for(size_t j=0;j<(*tar)[i].size();j++)
			(*tar)[i][j] = Distance(m_City[i], m_City[j]);
	}
}

void TSPProblem::OutputResult(const char *filename, void* parm)
{
	ofstream out(filename);
	if(out.fail())
		return;
	out << "# vtk DataFile Version 1.0\n";
	out << "TSP Problem Plot\n";
	out << "ASCII\n";
	out << "DATASET POLYDATA\n";
	out << "POINTS " << (int)m_City.size() << " float\n";
	for(size_t i=0;i<m_City.size();i++)
		out << m_City[i].x << "\t" << m_City[i].y << "\t0.0\n";
	out << endl << endl;
	out << "LINES " << (int)m_City.size()-1 << " " << 3*(int)m_City.size() - 3 << endl;
	vector<double>	*pArray = static_cast<vector<double>*>(parm);
	for(size_t i=1;i<pArray->size();i++)
		out << "2 " << (int)(*pArray)[i-1] << " " << (int)(*pArray)[i] << endl;

	out << "POINT_DATA " << (int)m_City.size() <<endl;
	out << "SCALARS cityID float 1\n";
	out << "LOOKUP_TABLE default\n";
	for(size_t i=0;i<m_City.size();i++)
		out << i << " ";
	out << endl;
	out.close();
}