spea.cpp

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

/*******************************************************************************
	SPEA.cpp

		last change: 01/25/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 SPEA.h
*******************************************************************************/

#include "SPEA.h"

#include <cstddef>
#include "Individual.h"
#include "MOEA.h"
#include "Population.h"
#include "RandomNr.h"
#include "TIKEAFExceptions.h"
#include "VecPopulation.h"

using namespace std;


SPEA::SPEA(	RandomNr&	rn,
		size_t		ms,
		size_t		ps )
	: MOEA( rn, ms ), maxParetoSize( ps ), paretoSet( randomNr, maxParetoSize )
{
}


void
SPEA::select(	Population*	population,
		Population*	matingPool )
	throw ( NilException )
{
// see Thiele, Lothar / Zitzler, Eckart.
//	- An Evolutionary Algorithm for Multiobjective Optimization:
//	The Strength Pareto Approach.

#ifndef NOTIKEAFEXCEPTIONS
	if ( population == 0 || matingPool == 0 )
	{
		throw NilException( "from SPEA::select" );
	}
#endif

	// get new Pareto points and get rid of no-more-Pareto points
	population->updateParetoSet( &paretoSet );

	// if the Pareto set has become too big,
	// reduce it by average linkage clustering
	if ( paretoSet.size() > maxParetoSize )
	{
		paretoSet.aveLinkCluster( Individual::phenoObj, maxParetoSize );
	}

	size_t	parSetSize = paretoSet.size(),
		popSize = population->size(),
		unionSize = parSetSize + popSize;
	
	// assign strength to Pareto points
	for ( size_t s = 0; s < parSetSize; ++s )
	{
		Individual*	psInd = paretoSet.at( s );
		int		count = 0;

		for ( size_t t = 0; t < popSize; ++t )
		{
			if ( psInd->covers( population->at( t ) ) )
			{
				++count;
			}
		}
		psInd->fitness = count / static_cast< double >( popSize + 1 );
	}

	// assign fitness to population members
	for ( size_t s = 0; s < popSize; ++s )
	{
		Individual*	popInd = population->at( s );
		double		sum = 0;

		for ( size_t t = 0; t < parSetSize; ++t )
		{
			Individual*	psInd = paretoSet.at( t );
			
			if ( psInd->covers( popInd ) )
			{
				sum += psInd->fitness;
			}
		}
		popInd->fitness = sum + 1;
	}

	// fill the mating pool using binary tournament selection
	for ( size_t s = 0; s < matingPoolSize; ++s )
	{
		size_t		index1 = randomNr.uniform0Max( unionSize ),
				index2 = randomNr.uniform0Max( unionSize );
		Individual*	ind1 = index1 < popSize ? population->at( index1 ) : paretoSet.at( index1 - popSize );
		Individual*	ind2 = index2 < popSize ? population->at( index2 ) : paretoSet.at( index2 - popSize );

		if ( ind1->fitness < ind2->fitness )
		{
			matingPool->pushBack( ind1->clone() );
		}
		else
		{
			matingPool->pushBack( ind2->clone() );
		}
	}
}


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

	size_t	parSetSize = paretoSet.size();
	
	for ( size_t s = 0; s < parSetSize; ++s )
	{
		pop->pushBack( paretoSet.at( s )->clone() );
	}
}