population.cpp

遗传算法的四个源程序和源代码

/*! \file Population.cpp
    \brief This file implements classes and datatypes of chromosomes population.
*/

/*
 * 
 * website: http://www.coolsoft-sd.com/
 * contact: [e-mail]
 *
 */

/*
 * Genetic Algorithm Library
 * Copyright (C) 2007-2008 Coolsoft Software Development
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 *
 */

#include "Population.h"

namespace Population
{

	// Copy chromosome indicies to given sorted group
	void GaSortedGroup::CopyTo(GaSortedGroup& destination,
		bool sameSorting) const
	{
		destination.Clear();

		if( sameSorting )
		{
			// copy to destination in source's order
			for( int i = 0; i < _currentSize && i < destination._maxSize; i++, destination._currentSize++ )
				destination._chromosomesIndecies[ i ] = _chromosomesIndecies[ i ];
		}
		else
		{
			// add new chromsomes to destination in destination's sorting order
			for( int i = 0; i < _currentSize; i++ )
				destination.Add( _chromosomesIndecies[ i ] );
		}
	}

	// Adds chromosome to the group.
	// Returns position at which this chromosome has been inserted
	// or -1 if chromosome hasn't been inserted.
	int GaSortedGroup::Add(int chromosomeIndex)
	{
		// is group disabled?
		if( !_chromosomesIndecies || !_population || !_comparator || 
			( _population->GetAt( chromosomeIndex ).GetGroupFlag( _type ) && _type != GASGT_OTHER ) )
			return -1;

		// first chromosome?
		if( !_currentSize )
		{
			_chromosomesIndecies[ _currentSize++ ] = chromosomeIndex;

			// mark this chromosome that it's belongs to this group
			if( _type != GASGT_OTHER )
				_population->GetAt( chromosomeIndex ).SetGroupFlags( _type );

			return 0;
		}

		int rev = _type == GASGT_WORST ? -1 : 1;

		float fitness = _population->GetAt( chromosomeIndex ).GetFitnessForComparison();

		// the group is full, qickly check if the chromosome should be in the group
		if( _currentSize == _maxSize && 
			rev * (*_comparator)( fitness, _population->GetAt( _chromosomesIndecies[ _currentSize - 1 ] ).GetFitnessForComparison() ) <= 0 )
			return -1;

		// if the last chromosome from this group will be removed,
		// clears mark that the last chromosome belongs to this group
		bool removeLast = _currentSize == _maxSize && ( _type != GASGT_OTHER || _type != GASGT_NONE );
		if( removeLast )
			_population->GetAt( _chromosomesIndecies[ _currentSize - 1 ] ).ClearGroupFlags( _type );

		// find position at which the chromosome should be inserted and make room for it
		int i = _currentSize < _maxSize ? _currentSize : _maxSize - 1;
		for( ; i > 0 && rev * (*_comparator)( fitness, _population->GetAt( _chromosomesIndecies[ i - 1 ] ).GetFitnessForComparison() ) > 0; i-- )
			_chromosomesIndecies[ i ] = _chromosomesIndecies[ i - 1 ];

		// insert new chromosome
		_chromosomesIndecies[ i ] = chromosomeIndex;

		if( !removeLast )
			_currentSize++;

		// mark this chromosome that it's belongs to this group
		if( _type != GASGT_OTHER )
			_population->GetAt( chromosomeIndex ).SetGroupFlags( _type );

		return i;
	}

	// Removes chromosome index from the group.
	// Returns TRUE if the chromosome is removed.
	bool GaSortedGroup::Remove(int chromosomeIndex)
	{
		// group is not disabled and does chromosome belongs to the group?
		if( !_chromosomesIndecies ||
			( !_population->GetAt( chromosomeIndex ).GetGroupFlag( _type ) && _type != GASGT_OTHER ) )
			return false;

		int rev = _type == GASGT_WORST ? -1 : 1;

		float fitness = _population->GetAt( chromosomeIndex ).GetFitnessForComparison();

		// qickly check if the chromosome should be in the group
		if( rev * (*_comparator)( fitness, _population->GetAt( _chromosomesIndecies[ _currentSize - 1 ] ).GetFitnessForComparison() ) < 0 )
			return false;

		// find position of chromosome's index in the group
		int pos = 0;
		for( ; pos < _currentSize; pos++ )
		{
			if( _chromosomesIndecies[ pos ] == chromosomeIndex )
				break;
		}

		// is the chromosome in the group?
		if( pos < _currentSize )
		{
			// clears mark that this chromosome belongs to this group
			if( _type != GASGT_OTHER  )
				_population->GetAt( chromosomeIndex ).ClearGroupFlags( _type );

			// remove from the group
			for( int i = pos; i < _currentSize - 1 ; i++ )
				_chromosomesIndecies[ i ] = _chromosomesIndecies[ i + 1 ];

			_currentSize--;

			return true;
		}

		return false;
	}

	// Removes all chromosomes from the group
	void GaSortedGroup::Clear()
	{
		if( _type != GASGT_OTHER )
		{
			// remove chromosome's marks
			while( _currentSize > 0 )
				_population->GetAt( _chromosomesIndecies[ --_currentSize ] ).ClearGroupFlags( _type );
		}
		else
			_currentSize = 0;
	}

	// Returns ranking of chromosome.
	// If chromosomi is not in group returns -1;
	int GaSortedGroup::GetRanking(int chromosomeIndex)
	{
		// check parameters
		if( chromosomeIndex < 0 || chromosomeIndex >= _population->GetCurrentSize() || !_currentSize )
			return -1;

		int rev = _type == GASGT_WORST ? -1 : 1;

		// qickly check if the chromosome should be in the group
		float fitness = _population->GetAt( chromosomeIndex ).GetFitnessForComparison();
		if( rev * (*_comparator)( fitness, _population->GetAt( _chromosomesIndecies[ _currentSize - 1 ] ).GetFitnessForComparison() ) < 0 )
			return -1;

		// find chromosome
		for( int i = 0; i < _currentSize; i++ )
		{
			if( _chromosomesIndecies[ i ] == chromosomeIndex )
				return i;
		}

		// chromosome wasn't found
		return -1;
	}

	// Returns refernece to scaled chromosome at given position
	GaScaledChromosome& GaSortedGroup::GetScaledChromosomeAt(int pos) const
	{
		return _population->GetAt( _chromosomesIndecies[ pos ] );
	}

	// Sets maximum size of the group
	void GaSortedGroup::SetMaxSize(int size)
	{
		// nothing changed?
		if( size == _maxSize )
			return;

		if( size < 0 )
			_maxSize = 0;
		else
			_maxSize = size;

		int* oldIndecies = _chromosomesIndecies;

		if( !_maxSize )
		{
			// clear if size is zero
			Clear();
			_chromosomesIndecies = NULL;
		}
		else
		{
			// new array of chromosome indecies
			_chromosomesIndecies = new int[ _maxSize ];

			int len = 0;
			if( oldIndecies )
			{
				// copy indecies from old array
				len = _maxSize < _currentSize ? _maxSize : _currentSize;
				for( int i = 0; i < len; i++ )
					_chromosomesIndecies[ i ] = oldIndecies[ i ];
			}

			// new size
			_currentSize = len;
		}

		// free memory used by old array
		if( oldIndecies )
			delete[] oldIndecies;
	}

	// Returns fitnes comparator used to sort the group
	void GaSortedGroup::SetComparator(const GaFitnessComparator* comparator)
	{
		if( _comparator != comparator )
		{
			_comparator = comparator;

			int rev = _type == GASGT_WORST ? -1 : 1;

			// resort group
			for( int i = 0; i < _currentSize; i++ )
			{
				int c = _chromosomesIndecies[ i ];
				int j = i - 1;
				for( ; j >= 0 && rev * ( *_comparator )( _population->GetAt( _chromosomesIndecies[ j ] ), _population->GetAt( c ) ) > 0; j-- )
					_chromosomesIndecies[ j + 1 ] = _chromosomesIndecies[ j ];

				_chromosomesIndecies[ j + 1 ] = c;
			}
		}
	}

	// Initialization of the parameters
	GaPopulationParameters::GaPopulationParameters(int populationSize,
		bool resizable,
		bool sorting,
		bool useScaldeFitness,
		int bestTrackCount,
		int worstTrackCount) : _resizable(resizable),
		_sorting(sorting),
		_usingScaledFitness(useScaldeFitness)
	{
		SetPopulationSize( populationSize );
		SetBestTrackCount( bestTrackCount );
		SetWorstTrackCount( worstTrackCount );
	}

	// Sets how many best chromosomes in the population are cached
	void GaPopulationParameters::SetBestTrackCount(int count)
	{
		if( count < 1 )
			_bestTrackCount = 1;
		else if( count > _populationSize )
			_bestTrackCount = _populationSize;
		else
			_bestTrackCount = count;
	}

	// Sets how many worst chromosomes in the population are cached
	void GaPopulationParameters::SetWorstTrackCount(int count)
	{
		if( count < 1 )
			_worstTrackCount = 1;
		else if( count > _populationSize )
			_worstTrackCount = _populationSize;
		else
			_worstTrackCount = count;
	}

	// Global instance of default configuration
	GaPopulationConfiguration* GaPopulationConfiguration::_default = NULL;

	// Makes global instance of default configuration
	void GaPopulationConfiguration::MakeDefault()
	{
		if( !_default )
		{
			// default population parameters
			GaPopulationParameters deafultParams( 10, false, true, false, 0, 0 );

			// deafult comaratore used for sorting
			GaFitnessComparator* deafultComparator = GaFitnessComparatorCatalogue::Instance().GetEntryData( "GaMaxFitnessComparator" );

			// get default selection and make temp parameters for it
			GaSelectionOperation* defaultSelection = GaSelectionCatalogue::Instance().GetEntryData( "GaSelectRouletteWheel" );
			GaSelectionParams* selectionParams = (GaSelectionParams*)defaultSelection->MakeParameters();
			selectionParams->SetSelectionSize( 2 );

			// get default replacement and make temp parameters for it
			GaReplacementOperation* defaultReplacement = GaReplacementCatalogue::Instance().GetEntryData( "GaReplaceWorst" );
			GaReplacementParams* replacementParams = (GaReplacementParams*)defaultReplacement->MakeParameters();
			replacementParams->SetReplacementSize( 2 );

			// get default coupling and make temp parameters for it
			GaCouplingOperation* defaultCoupling = GaCouplingCatalogue::Instance().GetEntryData( "GaInverseCoupling" );
			GaCouplingParams* couplingParams = (GaCouplingParams*)defaultCoupling->MakeParameters();
			couplingParams->SetNumberOfOffsprings( 2 );

			// make default configuration
			_default = new GaPopulationConfiguration( deafultParams, deafultComparator, defaultSelection, selectionParams, defaultReplacement, replacementParams,
				defaultCoupling, couplingParams, NULL, NULL );

			// delete temp parameters
			if( selectionParams )
				delete selectionParams;
			if( replacementParams )
				delete replacementParams;
			if( couplingParams )
				delete couplingParams;
		}
	}

	// Binds population to the configuration
	void GaPopulationConfiguration::BindPopulation(GaPopulation* population,
		bool refresh)
	{
		if( population )
		{
			_populations.push_back( population );

			if( refresh )
			{
				// refresh population object
				population->SetParameters( _parameters );
				population->SetSortComparator( _sortingComparator );
				population->ResortPopulation( false, true, true );
			}
		}
	}

	// Sets parameter of the population(s)
	void GaPopulationConfiguration::SetParameters(const GaPopulationParameters& parameters)
	{
		// refresh populations
		for( list<GaPopulation*>::iterator it = _populations.begin(); it != _populations.end(); ++it )
			(*it)->SetParameters( _parameters );

		_parameters = parameters;
	}

	// Sets scaling operation
	void GaPopulationConfiguration::SetOperation(GaScalingOperation* operation,
											 GaScalingParams* parameters)
	{
		_scaling.SetOperation( operation, *parameters );

		// refresh populations
		for( list<GaPopulation*>::iterator it = _populations.begin(); it != _populations.end(); ++it )
			(*it)->ResortPopulation( false, true, false );
	}

	// Sets parameters for scaling operation
	void GaPopulationConfiguration::SetOperationParams(GaScalingParams* parameters)
	{
		_scaling.SetParameters( *parameters );

		// refresh populations
		for( list<GaPopulation*>::iterator it = _populations.begin(); it != _populations.end(); ++it )
			(*it)->ResortPopulation( false, true, false );
	}

	// Sets comparator used for sorting the chromosomes
	void GaPopulationConfiguration::SetSortComparator(const GaFitnessComparator* comparator)
	{
		if( _sortingComparator != comparator )
		{
			_sortingComparator = comparator;

			for( list<GaPopulation*>::iterator it = _populations.begin(); it != _populations.end(); ++it )
			{
				(*it)->SetSortComparator( _sortingComparator );
				(*it)->ResortPopulation( false, false, true );
			}
		}
	}

	// Prepares population for initialization
	GaPopulation::GaPopulation(GaChromosome* prototype,
		GaPopulationConfiguration* configuration) : _prototype(prototype),
		_configuration(configuration),
		_parameters(configuration->GetParameters()),
		_best( this, GASGT_BEST ),
		_worst( this, GASGT_WORST ),
		_statistics(configuration->GetSortComparator()),
		_currentSize(0)
	{
		_configuration->BindPopulation( this, false );

		_usingScaledFitness = _parameters.GetUsingScaledFitness();
		int populationSize = _parameters.GetPopulationSize();

		// initialize table of population's chromorsome table
		_chromosomes = new GaScaledChromosome*[ populationSize ];
		for( int i = 0; i < populationSize; i++ )
			_chromosomes[ i ] = NULL;

		// empty population
		_currentSize = 0;