tsp.cpp

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

#include "TSP.h"

TSP::TSP()
{
	// set conditions
	m_Nodes.resize(5);
	m_Nodes[0].x = 0.0;m_Nodes[0].y = 0.0;
	m_Nodes[1].x = 5.0;m_Nodes[1].y = 0.0;
	m_Nodes[2].x = 10.0;m_Nodes[2].y = 0.0;
	m_Nodes[3].x = 10.0;m_Nodes[3].y = 10.0;
	m_Nodes[4].x = 5.0;m_Nodes[4].y = 5.0;

	// set domain first
	m_Domain.resize(1);
	m_Domain[0].m_Type = DT_PERMUTATE;
	m_IfRepeat = false;
	m_Domain[0].m_Set.resize(5);
	for(int a=0;a<5;a++)
		m_Domain[0].m_Set[a] = a+1;

	// set param
	m_Param.resize(5);
	for(int b=0;b<5;b++)  // initialization
	{
		m_Param[b].m_Val = b;
		m_Param[b].m_pDomain = &(m_Domain[0]);
	}
}

double TSP::GetResult(vector<CParam> &cs)
{
    double dist = 0.0;

	for(size_t a=0;a<cs.size()-1;a++)
	{
		dist += Distance(m_Nodes[cs[a].m_Val],m_Nodes[cs[a+1].m_Val]);
	}
	dist += Distance(m_Nodes[cs[a].m_Val],m_Nodes[cs[0].m_Val]);
	return dist;
}

CParam TSP::RandomNewParam(int iNonFix)
{
	int i=0, pid;
	for(pid=0;pid<(int)m_Param.size();pid++)
	{
		if(i==iNonFix)
			break;
		if(m_Param[pid].m_pDomain->m_Type!=DT_FIX)
			i++;
	}
	CParam temp;
	CDomain tempD;
	tempD = *m_Param[i].m_pDomain;
	temp.m_pDomain = &tempD;
	if(temp.m_pDomain->m_Type==DT_SET && !m_IfRepeat)
	{
		for(pid=0;pid<(int)m_Param.size();pid++)
		{
			if(pid==i)
				continue;
			int j=0;
			while(j<(int)tempD.m_Set.size())
			{
				if(tempD.m_Set[j]==m_Param[pid].m_Val)
					tempD.m_Set.erase(tempD.m_Set.begin() + j);
				else
					j++;
			}
		}
	}
	temp.GetRandomValue();
	temp.m_pDomain = m_Param[i].m_pDomain;
	return temp;
}

void TSP::NewParamSet()
{
	vector<CParam> Fixed;
	int psize = (int)m_Param.size();
	for(int i=0;i<psize/2;i++)
	{
		int a = rand()%psize;
		int b = rand()%psize;
		if((*(m_Param[a].m_pDomain))==(*(m_Param[b].m_pDomain)))
			swap(m_Param[a].m_Val, m_Param[b].m_Val);
	}
}