permutationchromosome.cpp

多目标进化算法源代码

/*******************************************************************************
	PermutationChromosome.cpp
		
		last change: 02/04/1999
		
		version: 0.0.0
		
		design:	Eckart Zitzler
			Paul E. Sevinc
			
		implementation:	Paul E. Sevinc
		
		(c) 1998-1999:	Computer Engineering and Networks Laboratory
				Swiss Federal Institute of Technology Zurich
		
		description:
			See PermutationChromosome.h
*******************************************************************************/

#include "PermutationChromosome.h"

#include <cstddef>
#include <vector>
#include "Chromosome.h"
#include "RandomNr.h"
#include "TIKEAFExceptions.h"

using namespace std;


PermutationChromosome::PermutationChromosome(	RandomNr&	rn,
						size_t		size )
	: Chromosome( rn ), length( size ), permutation( size )
{
	for ( size_t s = 0; s < length; ++s )
	{
		permutation[ s ] = static_cast< int >( s + 1 );
	}
}


void
PermutationChromosome::permute(	size_t	from,	// inclusive
				size_t	to )	// exclusive
{
	size_t		nr = to - from;
	vector< int >	copy( nr );
	
	// prepare for permutation...
	for ( size_t s = 0; s < nr; ++s )
	{
		copy[ s ] = permutation[ from + s ];
	}
	
	// ...and permute
	for ( size_t s = 0; s < nr; ++s )
	{
		// draw the index that will henceforth be at position s
		size_t	index = randomNr.uniform0Max( nr );
		
		// if it has already been used, try the next one
		while ( copy[ index ] == 0 )
		{
			index = ( index + 1 ) % nr;
		}
		permutation[ from + s ] = copy[ index ];
		copy[ index ] = 0; // mark as used
	}
}


void
PermutationChromosome::initRandom()
{
	permute( 0, length );
}


void
PermutationChromosome::mutate()
{
}


Chromosome*
PermutationChromosome::clone()
{
	PermutationChromosome*	pc = new PermutationChromosome( randomNr, length );

	for ( size_t s = 0; s < length; ++s )
	{
		pc->permutation[ s ] = permutation[ s ];
	}
	return pc;
}


size_t
PermutationChromosome::size()
{
	return length;
}


int
PermutationChromosome::get( size_t index )
	throw ( LimitsException )
{
#ifndef NOTIKEAFEXCEPTIONS
	if ( index >= length )
	{
		throw LimitsException( "from PermutationChromosome::get" );
	}
#endif

	return permutation[ index ];
}


void
PermutationChromosome::inversionMutation()
{
	size_t	startPoint,
		endPoint,
		exchanges;
	
	// define the beginning and ending (inclusive) of
	// the sublist to be inverted
	startPoint = randomNr.uniform0Max( length );
	do
	{
		endPoint = randomNr.uniform0Max( length );
	} while ( endPoint == startPoint );
	if ( endPoint < startPoint ) // loops endlessly if length < 2!
	{
		size_t	s;

		s = startPoint;
		startPoint = endPoint;
		endPoint = s;
	}

	exchanges = ( endPoint - startPoint + 1 ) / 2;
	for ( size_t s = 0; s < exchanges; ++s )
	{
		size_t	d = startPoint + s,
			u = endPoint - s;
		int	p;
			
		p = permutation[ d ];
		permutation[ d ] = permutation[ u ];
		permutation[ u ] = p;
	}	
}


void
PermutationChromosome::scrambleSublistMutation()
{
	size_t	startPoint,
		endPoint;

	// define the beginning and ending (inclusive) of
	// the sublist to be scrambled
	startPoint = randomNr.uniform0Max( length );
	do
	{
		endPoint = randomNr.uniform0Max( length );
	} while ( endPoint == startPoint ); // loops endlessly if length < 2!

	if ( startPoint < endPoint )
	{
		permute( startPoint, endPoint + 1 );
	}
	else
	{
		permute( endPoint, startPoint + 1 );
	}
}


void
PermutationChromosome::moveSequenceMutation()
{
	size_t		startPoint,
			endPoint,
			moves = static_cast< size_t >( randomNr.uniformMinMax( 1, static_cast< int >( length ) ) );
	vector< int >	copy( length );
	
	for ( size_t s = 0; s < length; ++s )
	{
		copy[ s ] = permutation[ s ];
	}

	// define the beginning and ending (inclusive) of
	// the sequence to be moved
	startPoint = randomNr.uniform0Max( length );
	do
	{
		endPoint = randomNr.uniform0Max( length );
	} while ( endPoint == startPoint ); // loops endlessly if length < 2!
	if ( endPoint < startPoint )
	{
		size_t	s;
		
		s = startPoint;
		startPoint = endPoint;
		endPoint = s;
	}
	
	// circularly shift the sequence
	for ( size_t s = startPoint; s <= endPoint; ++s )
	{
		permutation[ ( s + moves ) % length ] = copy[ s ];
		copy[ s ] = 0; // mark as used
	}

	// reestablish the remaining alleles
	size_t	nr = length - ( endPoint - startPoint + 1 ),
		indexNew = ( startPoint + moves - 1 ) % length,
		indexOld = ( endPoint + moves ) % length;

	for ( size_t s = 0; s < nr; ++s )
	{
		// don't copy the moved alleles
		while ( copy[ indexOld ] == 0 )
		{
			indexOld = ( indexOld - 1 ) % length;
		}

		permutation[ indexNew ] = copy[ indexOld ];
		indexNew = ( length + indexNew - 1 ) % length;
		indexOld = ( length + indexOld - 1 ) % length;
	}
}


void
PermutationChromosome::swapMutation()
{
	size_t	firstPoint,
		secondPoint;
	int	p;

	// draw the two indices to be exchanged...
	firstPoint = randomNr.uniform0Max( length );
	do
	{
		secondPoint = randomNr.uniform0Max( length );
	} while ( secondPoint == firstPoint ); // loops endlessly if length < 2!
	
	// ...and exchange them
	p = permutation[ firstPoint ];
	permutation[ firstPoint ] = permutation[ secondPoint ];
	permutation[ secondPoint ] = p;
}


void
PermutationChromosome::uniformOrderBasedCrossover(	RandomNr&		rn,
							PermutationChromosome*	mother,
							PermutationChromosome*	father,
							PermutationChromosome*	daughter,
							PermutationChromosome*	son )
	throw ( NilException, LimitsException )
{
#ifndef NOTIKEAFEXCEPTIONS
	if ( mother == 0 || father == 0 || daughter == 0 || son == 0 )
	{
		throw NilException( "from PermutationChromosome::uniformOrderBasedCrossover" );
	}

	size_t		length = mother->size();

	if ( length != father->size() || length != daughter->size() || length != son->size() )
	{
		throw LimitsException( "from PermutationChromosome::uniformOrderBasedCrossover" );
	}
#endif

#ifdef NOTIKEAFEXCEPTIONS
	size_t		length = mother->size();
#endif
	vector< bool >	bitmask( length );
	vector< int >	motherRemains( 0 ),
			fatherRemains( 0 );

	// define which indices will be identical in mother &
	// daugther (true) or father and son (false) respectively
	for ( size_t s = 0; s < length; ++s )
	{
		bitmask[ s ] = rn.flipP( 0.5 );
    	}

	for ( size_t s = 0; s < length; ++s )
	{
		if ( bitmask[ s ] )
		{
			// copy the female index but, remember the male one...
			daughter->permutation[ s ] = mother->permutation[ s ];
			fatherRemains.push_back( father->permutation[ s ] );
		}
		else
		{
			// ...and vice versa
			son->permutation[ s ] = father->permutation[ s ];
			motherRemains.push_back( mother->permutation[ s ] );
		}
	}

	size_t	s = 0,
		rLength = motherRemains.size(),
		corrected = 0; // to avoid unnecessary loops

	// store all the unused indices of the mother in the daugther
	// in order of their appearance in the father...
	for ( size_t out = 0; ( out < length ) && ( corrected < rLength ); ++out )
	{
		for ( size_t in = 0; in < rLength; ++in )
		{
			if ( father->permutation[ out ] == motherRemains[ in ] )
			{
				// don't overwrite an already used position
				while ( bitmask[ s ] )
				{
					++s;
				}
				daughter->permutation[ s ] = motherRemains[ in ];
				++s;
				++corrected;
				break; // no need to compare further remains
			}
		}
	}

	s = 0;
	rLength = fatherRemains.size();
	corrected = 0;

	// ...and vice versa
	for ( size_t out = 0; ( out < length ) && ( corrected < rLength ); ++out )
	{
		for ( size_t in = 0; in < rLength; ++in )
		{
			if ( mother->permutation[ out ] == fatherRemains[ in ] )
			{
				while ( !bitmask[ s ] )
				{
					++s;
				}
				son->permutation[ s ] = fatherRemains[ in ];
				++s;
				++corrected;
				break;
			}
		}
	}
}


void
PermutationChromosome::edgeRecombinationCrossover(	RandomNr&		rn,
							PermutationChromosome*	mother,
							PermutationChromosome*	father,
							PermutationChromosome*	child )
	throw ( NilException, LimitsException )
{
#ifndef NOTIKEAFEXCEPTIONS
	if ( mother == 0 || father == 0 || child == 0 )
	{
		throw NilException( "from PermutationChromosome::edgeRecombinationCrossover" );
	}

	size_t	length = mother->size();

	if ( length != father->size() || length != child->size() )
	{
		throw LimitsException( "from PermutationChromosome::edgeRecombinationCrossover" );
	}
#endif
	
#ifdef NOTIKEAFEXCEPTIONS
	size_t	length = mother->size();
#endif
	// create a length*5 table
	int**	table = new int*[ length ];

	for ( size_t s = 0; s < length; ++s )
	{
		table[ s ] = new int[ 5 ];
	}

	// store the mother's neighbour information
	for ( size_t s = 0; s < length; ++s )
	{
		size_t	row = static_cast< size_t >( mother->permutation[ s ] - 1 ),
			right = ( s + 1 ) % length,
			left = ( length + s - 1 ) % length;
		
		table[ row ][ 0 ] = 2;
		table[ row ][ 1 ] = mother->permutation[ right ];
		table[ row ][ 2 ] = mother->permutation[ left ];
	}

	// update with the father's neighbour information
	for ( size_t s = 0; s < length; ++s )
	{
		bool	changedFirst = false,
			changedSecond = false;
		size_t	row =  static_cast< size_t >( father->permutation[ s ] - 1 );
		int	right = father->permutation[ ( s + 1 ) % length ],
			left = father->permutation[ ( length + s - 1 ) % length ];
		int&	iref1 = table[ row ][ 1 ];
		int&	iref2 = table[ row ][ 2 ];

		if ( iref1 == right || iref1 == left )
		{
			iref1 = -iref1;
			changedFirst = true;
		}
		if ( iref2 == right || iref2 == left )
		{
			iref2 = -iref2;
			changedSecond = true;
		}
		
		if ( changedFirst && !changedSecond )
		{
			if ( iref1 == -right )
			{
				table[ row ][ 0 ] = 3;
				table[ row ][ 3 ] = left;
			}
			else
			{
				table[ row ][ 0 ] = 3;
				table[ row ][ 3 ] = right;
			}
		}
		else if ( !changedFirst && changedSecond )
		{
			if ( iref2 == -right )
			{
				table[ row ][ 0 ] = 3;
				table[ row ][ 3 ] = left;
			}
			else
			{
				table[ row ][ 0 ] = 3;
				table[ row ][ 3 ] = right;
			}
		}
		else if ( !changedFirst && !changedSecond )
		{
			table[ row ][ 0 ] = 4;
			table[ row ][ 3 ] = right;
			table[ row ][ 4 ] = left;
		}
	}

	// start with either the mother's first allele or the father's...
	if ( rn.flipP( 0.5 ) )
	{
		child->permutation[ 0 ] = mother->permutation[ 0 ];
	}
	else
	{
		child->permutation[ 0 ] = father->permutation[ 0 ];
	}

	// ...and then use the neighbour information to
	// determine the allele order
	for ( size_t s = 1; s < length; ++s ) // Yep, 1 (not 0)!
	{
		int	cpsm = child->permutation[ s - 1 ];
		size_t	x = static_cast< size_t >( cpsm - 1 );

		// delete cpsm from the table
		for ( size_t t = 0; t < length; ++t )
		{
			int	tt0 = table[ t ][ 0 ];
			
			for ( int i = 1; i <= tt0; ++i )
			{
				int	tti = table[ t ][ i ];
				
				if ( tti == cpsm || tti == -cpsm )
				{
					table[ t ][ i ] = table[ t ][ tt0 ];
					--table[ t ][ 0 ];
					break; // check the next row
				}
			}
		}

		// if all of cpsm's neighbours have been used,
		// simply check the next table row
		while ( table[ x ][ 0 ] == 0 )
		{
			x = ( x + 1 ) % length;
		}

		int	best = table[ x ][ 1 ];
		size_t	cols = static_cast< size_t >( table[ x ][ 0 ] );
		
		for ( size_t y = 2; ( best > 0 ) && ( y <= cols ); ++y ) // Yep, 2!
		{
			int	txy = table[ x ][ y ];

			if ( txy < 0 )
			{
				best = txy;
			}
			else if ( table[ txy - 1 ][ 0 ] < table[ best - 1 ][ 0 ] )
			{
				best = txy;
			}
		}
		
		child->permutation[ s ] = best < 0 ? -best : best;
	}

	// get rid of the table
	for ( size_t s = 0; s < length; ++s )
	{
		delete[] table[ s ];
	}
	delete[] table;
}