population.cpp

一个用c++编写的多目标遗传算法程序

/*******************************************************************************
	Population.cpp
	
		last change: 01/19/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 Population.h
*******************************************************************************/

#include "Population.h"

#include <climits>
#include <cstddef>
#include <vector>
#include "Individual.h"
#include "RandomNr.h"
#include "TIKEAFExceptions.h"

using namespace std;


Population::Population( RandomNr& rn )
	: randomNr( rn )
{
}


Population::~Population()
{
}


void
Population::sort( bool increasing )
{
	if ( size() < 2 )
	{
		return;
	}
	
	if ( increasing )
	{
		// smaller fitness values come first
		quicksortUp( 0, static_cast< int >( size() ) - 1 );
	}
	else
	{
		// smaller fitness values come last
		quicksortDown( 0, static_cast< int >( size() ) - 1 );
	}
}


void
Population::quicksortUp(	int	left,	// inclusive
				int	right )	// inclusive
{
// see Wirth, Niklaus.
//	- Algorithmen und Datenstrukturen.

	int		i = left,
			j = right;
	Individual*	x = at( ( left + right ) / 2 );

	do
	{
		while ( at( i )->fitness < x->fitness )
		{
			++i;
		}
		while ( x->fitness < at( j )->fitness )
		{
			--j;
		}
		if ( i <= j )
		{
			switchAt( i, j );
			++i;
			--j;
		}
	} while ( i <= j );

	if ( left < j )
	{
		quicksortUp( left, j );
	}
	if ( i < right )
	{
		quicksortUp( i, right );
	}
}


void
Population::quicksortDown(	int	left,	// inclusive
				int	right )	// inclusive
{
	int		i = left,
			j = right;
	Individual*	x = at( ( left + right ) / 2 );

	do
	{
		while ( at( i )->fitness > x->fitness )
		{
			++i;
		}
		while ( x->fitness > at( j )->fitness )
		{
			--j;
		}
		if ( i <= j )
		{
			switchAt( i, j );
			++i;
			--j;
		}
	} while ( i <= j );

	if ( left < j )
	{
		quicksortDown( left, j );
	}
	if ( i < right )
	{
		quicksortDown( i, right );
	}
}


void
Population::initRandom()
{
	size_t	length = size();
	
	for ( size_t s = 0; s < length; ++s )
	{
		at( s )->initRandom();
	}
}


void
Population::mutate()
{
	size_t	length = size();
	
	for ( size_t s = 0; s < length; ++s )
	{
		at( s )->mutate();
	}
}


void
Population::updateParetoSet( Population* paretoSet )
	throw ( NilException )
{
#ifndef NOTIKEAFEXCEPTIONS
	if ( paretoSet == 0 )
	{
		throw NilException( "from Population::updateParetoSet" );
	}
#endif

	nondominatedPoints( paretoSet );
	paretoSet->deleteCovered();
}


void
Population::nondominatedPoints( Population* pop )
{
	size_t		length = size();
	vector< bool >	dominated( length );

	for ( size_t s = 0; s < length; ++s )
	{
		dominated[ s ] = false;
	}

	// mark dominated individuals
	for ( size_t s = 0; s < length; ++s )
	{
		if ( !dominated[ s ] )
		{
			Individual*	ind = at( s );
			
			for ( size_t t = 0; t < length; ++t )
			{
				if ( !dominated[ t ] && ind->dominates( at( t ) ) )
				{
					dominated[ t ] = true;
				}
			}
		}
	}

	// clone nondominated individuals
	for ( size_t s = 0; s < length; ++s )
	{
		if ( !dominated[ s ] )
		{
			pop->pushBack( at( s )->clone() );
		}
	}
}


void
Population::deleteCovered()
{
// NOTE: not all covered points are deleted
// 	if several nondominated points are equal, exactly one of them survives

	size_t			length = size();
	vector< bool >		covered( length );
	vector< size_t >	indices;

	for ( size_t s = 0; s < length; ++s )
	{
		covered[ s ] = false;
	}
	indices.reserve( length );

	// mark covered individuals
	for ( size_t s = 0; s < length; ++s )
	{
		if ( !covered[ s ] )
		{
			Individual*	ind = at( s );

			for ( size_t t = 0; t < length; ++t )
			{
				if ( !covered[ t ] && ( t != s ) && ind->covers( at( t ) ) )
				{
					covered[ t ] = true;
				}
			}
		}
	}

	// get rid of marked individuals
	for ( size_t s = 0; s < length; ++s )
	{
		if ( covered[ s ] )
		{
			indices.push_back( s );
		}
	}
	deleteAt( indices );
}


void
Population::mate2( Population* pool )
{
	if ( pool == 0 )
	{
		pool = this;
	}

	size_t			length = size();
	vector< bool >		used( length );
	vector< Individual* >	children( 0 );
		
	for ( size_t s = 0; s < length; ++s )
	{
		used[ s ] = false;
	}
	children.reserve( 2 * length ); // assumption: 2 children out of 2 parents

	if ( length % 2 != 0 ) // odd number of parents?
	{
		size_t	index = randomNr.uniform0Max( length );
		
		pool->pushBack( at( index )->clone() );
		used[ index ];
	}
	for ( size_t s = length / 2; s > 0; --s )
	{
		size_t	firstIndex,
			secondIndex;

		firstIndex = randomNr.uniform0Max( length );
		while ( used[ firstIndex ] )
		{
			firstIndex = ( firstIndex + 1 ) % length;
		}
		secondIndex = randomNr.uniform0Max( length );
		while ( used[ secondIndex ] || firstIndex == secondIndex )
		{
			secondIndex = ( secondIndex + 1 ) % length;
		}

		at( firstIndex )->mateWith( at( secondIndex ), children );
		used[ firstIndex ] = true;
		used[ secondIndex ] = true;
	}
	
	length = children.size();
	for ( size_t s = 0; s < length; ++s )
	{
		pool->pushBack( children[ s ] );
	}
}


void
Population::mate2(	Individual::Distance	disType,
			double			distance,
			int			maxAttempts,
			Population*		pool )
	throw ( LimitsException )
{
#ifndef NOTIKEAFEXCEPTIONS
	if ( maxAttempts < 1 )
	{
		throw LimitsException( "from Population::mate2" );
	}
#endif

	if ( pool == 0 )
	{
		pool = this;
	}

	size_t			length = size();
	vector< bool >		used( length );
	vector< Individual* >	children( 0 );
		
	for ( size_t s = 0; s < length; ++s )
	{
		used[ s ] = false;
	}
	children.reserve( 2 * length ); // assumption: 2 children out of 2 parents
	
	if ( length % 2 != 0 ) // odd number of parents?
	{
		size_t	index = randomNr.uniform0Max( length );
		
		pool->pushBack( at( index )->clone() );
		used[ index ];
	}
	for ( size_t s = length / 2; s > 0; --s )
	{
		size_t	firstIndex,
			secondIndex;
		int	attempts = 0;

		firstIndex = randomNr.uniform0Max( length );
		while ( used[ firstIndex ] )
		{
			firstIndex = ( firstIndex + 1 ) % length;
		}
		do
		{
			secondIndex = randomNr.uniform0Max( length );
			while ( used[ secondIndex ] || firstIndex == secondIndex )
			{
				secondIndex = ( secondIndex + 1 ) % length;
			}
			++attempts;
		} while ( ( at( firstIndex )->distance( disType, at( secondIndex ) ) > distance ) && ( attempts < maxAttempts ) );

		at( firstIndex )->mateWith( at( secondIndex ), children );
		used[ firstIndex ] = true;
		used[ secondIndex ] = true;
	}
	
	length = children.size();
	for ( size_t s = 0; s < length; ++s )
	{
		pool->pushBack( children[ s ] );
	}
}


void
Population::aveLinkCluster(	Individual::Distance	disType,
				size_t			maxSize )
{
	size_t			nr = size(),
				nrOfClusters = nr;
	vector< size_t >	clusterBeg( nr );
	vector< size_t >	indLinks( nr );

	for ( size_t s = 0; s < nr; ++s )
	{
		clusterBeg[ s ] = s;
		indLinks[ s ] = nr;
	}

	while ( nrOfClusters > maxSize )
	{
		double	minDis = DBL_MAX;	// see <climits> - replace by
						// numeric_limits< double >::max()
						// when <limits> is available
		size_t	cluster1,
			cluster2;

		for ( size_t s = 0; s < nrOfClusters; ++s )
		{
			for ( size_t t = s + 1; t < nrOfClusters; ++t )
			{
				double	curDis = 0;
				int	pairCount = 0;
				size_t	x = clusterBeg[ s ];
				
				while ( x != nr )
				{
					size_t		y = clusterBeg[ t ];
					Individual*	ind = at( x );
					
					while ( y != nr )
					{
						curDis += ind->distance( disType, at( y ) );
						++pairCount;
						y = indLinks[ y ];
					}
					
					x = indLinks[ x ];
				}
				
				curDis /= pairCount;
				if ( curDis < minDis )
				{
					cluster1 = s;
					cluster2 = t;
					minDis = curDis;
				}
			}
		}

		// join clusters 1 and 2
		size_t	index = clusterBeg[ cluster1 ];

		while ( indLinks[ index ] != nr )
		{
			index = indLinks[ index ];
		}

		indLinks[ index ] = clusterBeg[ cluster2 ];

		--nrOfClusters;
		clusterBeg[ cluster2 ] = clusterBeg[ nrOfClusters ];
	}

	// get centroids
	vector< Individual* >	centroids( nrOfClusters );

	for ( size_t s = 0; s < nrOfClusters; ++s )
	{
		double	minDis = DBL_MAX;	// see <climits> - replace by
						// numeric_limits< double >::max()
						// when <limits> is available
		size_t	centroid,
			x = clusterBeg[ s ];
		
		while ( x != nr )
		{
			double		curDis = 0;
			size_t		y = clusterBeg[ s ];
			Individual*	ind = at( x );
			
			while ( y != nr )
			{
				curDis += ind->distance( disType, at( y ) );
				y = indLinks[ y ];
			}
			
			if ( curDis < minDis )
			{
				minDis = curDis;
				centroid = x;
			}
			
			x = indLinks[ x ];
		}
		
		centroids[ s ] = at( centroid )->clone();
	}
	
	// keep centroids only
	deleteAll();
	for ( size_t s = 0; s < nrOfClusters; ++s )
	{
		pushBack( centroids[ s ] );
	}
}