tspind.cpp

多目标进化算法源代码

#include "TSPInd.h"

#include <cmath>
#include <cstddef>
#include "Individual.h"
#include "PermutationChromosome.h"
#include "RandomNr.h"
#include "TIKEAFExceptions.h"

using namespace std;


TSPMatrix::TSPMatrix(	size_t		dim,
			RandomNr&	rn )
	: dimension( dim )
{
	matrix = new int*[ dimension ];
	for ( size_t s = 0; s < dimension; ++s )
	{
		matrix[ s ] = new int[ dimension ];
	}
				
	for ( size_t s = 0; s < dimension; ++s )
	{
		matrix[ s ][ s ] = 0; // unnecessary actually...
		for ( size_t t = s + 1; t < dimension; ++t )
		{
			int	cost = rn.uniformMinMax( 1, 100 );
					
			matrix[ s ][ t ] = cost;
			matrix[ t ][ s ] = cost;
		}
	}
}
			
			
TSPMatrix::~TSPMatrix()
{
	for ( size_t s = 0; s < dimension; ++s)
	{
		delete[] matrix[ s ];
	}
	delete[] matrix;
}
			
			
int
TSPMatrix::at(	int	x,
		int	y )
{
	return matrix[ x ][ y ];
}



TSPIndividual::TSPIndividual(	RandomNr&		rn,
				vector< TSPMatrix* >&	f,
				PermutationChromosome*	pc )
	: Individual( rn, f.size() ), fare( f ), chromosome( pc )
{
	nrOfTowns = fare[ 0 ]->dimension;
	maxDist = static_cast< double >( nrOfTowns - 1 ) * 99;
}


TSPIndividual::TSPIndividual(	RandomNr&		rn,
				vector< TSPMatrix* >&	f )
	: Individual( rn, f.size() ), fare( f )
{
	nrOfTowns = fare[ 0 ]->dimension;
	maxDist = static_cast< double >( nrOfTowns - 1 ) * 99;
	chromosome = new PermutationChromosome( randomNr, nrOfTowns );
}
			
			
TSPIndividual::~TSPIndividual()
{
	delete chromosome;
}
			
			
void
TSPIndividual::subInitRandom()
{
	chromosome->initRandom();
}
			
			
bool
TSPIndividual::subMutate()
{
	if ( randomNr.flipP( 0.1 ) )
	{
		chromosome->swapMutation();
		// chromosome->moveSequenceMutation();
		// chromosome->scrambleSublistMutation();
		// chromosome->inversionMutation();
				
		return true;
	}
	else
	{
		return false;
	}
}
			
			
Individual*
TSPIndividual::clone()
{
	PermutationChromosome*	pc = dynamic_cast< PermutationChromosome* >( chromosome->clone() );
				
	return new TSPIndividual( randomNr, fare, pc );
}
			
			
double
TSPIndividual::distance(	Distance	type,	// ignore
				Individual*	ind )
	throw ( NilException )
{
#ifndef NOTIKEAFEXCEPTIONS
	if ( ind == 0 )
	{
		throw NilException( "TSP::distance" );
	}
#endif
			
	double	totalDistance = 0;
				
	for ( size_t s = 0; s < nrOfObjectives; ++s )
	{
		double	dist = ( getObjective( s ) - ind->getObjective( s ) ) / maxDist;
					
		totalDistance += dist * dist;
	}
	return sqrt( totalDistance );
}
			
			
bool
TSPIndividual::covers( Individual* ind )
	throw ( NilException )
{
#ifndef NOTIKEAFEXCEPTIONS
	if ( ind == 0 )
	{
		throw NilException( "TSP::covers" );
	}
#endif
			
	return Individual::covers( false, ind );
}
			
			
bool
TSPIndividual::dominates( Individual* ind )
	throw ( NilException )
{
#ifndef NOTIKEAFEXCEPTIONS
	if ( ind == 0 )
	{
		throw NilException( "TSP::dominates" );
	}
#endif
			
	return Individual::dominates( false, ind );
}
			
			
double
TSPIndividual::subGetObjective( size_t index )
{
	double		objective = 0;
	TSPMatrix*	matrix = fare[ index ];
				
	for ( size_t s = 0; s < nrOfTowns; ++s )
	{
		int	x = chromosome->get( s ) - 1,
			y = chromosome->get( ( s + 1 ) % nrOfTowns ) - 1;
			
		objective += matrix->at( x, y );
	}
	return objective;
}
			
			
void
TSPIndividual::mateWith(	Individual*		ind,
				vector< Individual* >&	children )
	throw ( NilException )
{
#ifndef NOTIKEAFEXCEPTIONS
	if ( ind == 0 )
	{
		throw NilException( "TSP::mateWith" );
	}
#endif
				
	if ( randomNr.flipP( 0.8 ) )
	{
		PermutationChromosome*	daughter = new PermutationChromosome( randomNr, nrOfTowns );
		PermutationChromosome*	son = new PermutationChromosome( randomNr, nrOfTowns );
		TSPIndividual*		tspInd = dynamic_cast< TSPIndividual* >( ind );
				
		PermutationChromosome::uniformOrderBasedCrossover( randomNr, chromosome, tspInd->chromosome, daughter, son );
				
		children.push_back( new TSPIndividual( randomNr, fare, daughter ) );
		children.push_back( new TSPIndividual( randomNr, fare, son ) );
	}
	else
	{
		children.push_back( clone() );
		children.push_back( ind->clone() );
	}
}