Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Genetic Algorithm Library

, 7 Apr 2012 GPL3
A framework for genetic algorithms
galdemoapps.zip
TSP.exe
GeneticLibrary.dll
TestApp1.exe
TestApp2.exe
GaSchedule.exe
GaSchedule.cfg
GalDemoSource.zip
TestApp1
TestApp1.vcxproj.filters
TestApp2
TestApp2.vcxproj.filters
TSP
res
.svn
entries
prop-base
Toolbar.bmp.svn-base
TSP.ico.svn-base
props
text-base
Toolbar.bmp.svn-base
TSP.ico.svn-base
TSP.rc2.svn-base
tmp
prop-base
props
text-base
Toolbar.bmp
TSP.ico
TSP.vcxproj.filters
GaSchedule
Algorithm
GaSchedule.cfg
GaSchedule.vcxproj.filters
res
GaSchedule.ico
galdocumentation.zip
doxygen.png
Graphic
ab_cp.png
alg_st.png
a_cr.png
c_cp.png
i_cp.png
mp_cr.png
mv_cr.png
r_cp.png
s_cp.png
s_cr.png
galsource.zip
GeneticLibrary
build
release
gcc_bsd
gcc_linux
gcc_macos
gcc_solaris
icc_linux
icc_macos
icc_win
mingw
msvc
scc_solaris
makefiles
gcc_bsd_debug
gcc_bsd_release
gcc_linux_debug
gcc_linux_release
gcc_macos_debug
gcc_macos_release
gcc_solaris_debug
gcc_solaris_release
icc_linux_debug
icc_linux_release
icc_macos_debug
icc_macos_release
scc_solaris_debug
scc_solaris_release
source
vs
/*! \file Population.cpp
    \brief This file implements classes and datatypes of chromosomes population.
*/

/*
 * 
 * website: http://www.coolsoft-sd.com/
 * contact: support@coolsoft-sd.com
 *
 */

/*
 * 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;

		// set sizes for sorted groups of best and worst chromosomes
		if( !_parameters.GetSorting() )
		{
			_best.SetMaxSize( _parameters.GetBestTrackCount() );
			_worst.SetMaxSize( _parameters.GetWorstTrackCount() );
		}

		// set comparators for sorted groups of best and worst chromosomes
		_best.SetComparator( _configuration->GetSortComparator() );
		_worst.SetComparator( _configuration->GetSortComparator() );
	}

	// Free resources used by the population
	GaPopulation::~GaPopulation()
	{
		if( _chromosomes )
		{
			// free memory used by chromosomes
			for( int i = 0; i < _currentSize; i++ )
			{
				if( _chromosomes[ i ] )
					delete _chromosomes[ i ];
			}

			// free memory used by population's chromorsome table
			delete[] _chromosomes;
		}
	}

	// Virtual copy constructor
	GaPopulation* GaPopulation::Clone(bool copyChromosomes) const
	{
		// create new population with the same parameters
		GaPopulation* newPopulation = new GaPopulation( _prototype, _configuration );

		if( copyChromosomes )
		{
			// copy chromosomes
			for( int i = 0; i < _currentSize; i++ )
				newPopulation->_chromosomes[ i ] = new GaScaledChromosome( *_chromosomes[ i ] );

			// set size of new population
			newPopulation->_currentSize = _currentSize;

			// copy best and worst chromosome groups to new population if needed
			if( _parameters.GetSorting() )
			{
				_best.CopyTo( newPopulation->_best, true );
				_worst.CopyTo( newPopulation->_worst, true );
			}

			// copy statistics
			newPopulation->_statistics = _statistics;
		}

		return newPopulation;
	}

	// Initialization of the population, it creates random chromosomes based on provided chromosome prototype.
	void GaPopulation::InitializePopulation(bool fill /* = true */)
	{
		if( !_parameters.GetResizable() || fill )
		{
			// verify population parameters
			if( !_chromosomes || !_prototype )
				return;

			// clear best and worst chromosome tracking
			_best.Clear();
			_worst.Clear();

			// fill the population
			for( int i = 0; i < _parameters.GetPopulationSize(); i++ )
			{
				// make new chromosome from prototype
				GaChromosomePtr ptr = _prototype->MakeNewFromPrototype();
				ptr->RefreshFitness();
				float scaled = ptr->GetFitness();

				// remove old chromosome if any
				if( _chromosomes[ i ] )
					delete _chromosomes[ i ];

				// add new chromosome to the population
				_chromosomes[ i ] = new GaScaledChromosome( ptr, this, i );
			}

			// initialize statistics
			_statistics.Clear();

			_currentSize = _parameters.GetPopulationSize();

			// sort population if needed
			ResortPopulation( true, true, true );
		}
		else
		{
			// clear best and worst chromosome tracking
			_best.Clear();
			_worst.Clear();

			// fill the population
			for( int i = 0; i < _currentSize; i++ )
			{
				// remove old chromosome if any
				if( _chromosomes[ i ] )
					delete _chromosomes[ i ];
			}

			_currentSize = 0;

			// initialize statistics
			_statistics.Clear();
		}
	}

	// Fills the given array with indices of the best chromosomes in the population
	// Returns number of saved chromosomes
	int GaPopulation::GetBestChromosomes(int* results,
		int start,
		int numberOfChromosomes) const
	{
		// population initialized?
		if( !results || numberOfChromosomes <= 0 || !_chromosomes )
			return 0;

		if( _parameters.GetSorting() )
		{
			if( start >= _currentSize )
				return 0;

			// population is sorted - return first N indecies

			int end = start + numberOfChromosomes;
			int lim = _currentSize < end ? _currentSize : end;
			int i = 0;
			for( int j = start; j < lim; i++, j++ )
				results[ i ] = j;

			return i;
		}
		else
		{
			if( start >= _best.GetCurrentSize() )
				return 0;

			// get best chromosomes indecies form sorted group

			int end = start + numberOfChromosomes;
			int lim = _best.GetCurrentSize() < numberOfChromosomes ? _best.GetCurrentSize() : numberOfChromosomes;
			int i = 0;
			for( int j = start; j < lim; i++, j++ )
				results[ i ] = _best.GetAt( j );

			return i;
		}
	}

	// Fills the given array with the best chromosomes in the population
	// Returns number of saved chromosomes
	int GaPopulation::GetBestChromosomes(GaChromosomePtr* results,
		int start,
		int numberOfChromosomes) const
	{
		// population initialized?
		if( !results || numberOfChromosomes <= 0 || !_chromosomes )
			return 0;

		if( _parameters.GetSorting() )
		{
			if( start >= _currentSize )
				return 0;

			// population is sorted - return first N chromosomes

			int end = start + numberOfChromosomes;
			int lim = _currentSize < end ? _currentSize : end;
			int i = 0;
			for( int j = start; j < lim; i++, j++ )
				results[ i ] = _chromosomes[ j ]->GetChromosome();

			return i;
		}
		else
		{
			if( start >= _best.GetCurrentSize() )
				return 0;

			// get best chromosomes form sorted group

			int end = start + numberOfChromosomes;
			int lim = _best.GetCurrentSize() < numberOfChromosomes ? _best.GetCurrentSize() : numberOfChromosomes;
			int i = 0;
			for( int j = start; j < lim; i++, j++ )
				results[ i ] = _chromosomes[ _best.GetAt( j ) ]->GetChromosome();

			return i;
		}
	}

	// Fills the given array with indices of the worst chromosomes in the population
	// Returns number of saved chromosomes
	int GaPopulation::GetWorsChromosomes(int* results,
		int start,
		int numberOfChromosomes) const
	{
		// population initialized?
		if( !results || numberOfChromosomes <= 0 || !_chromosomes )
			return 0;

		if( _parameters.GetSorting() )
		{
			if( start >= _currentSize )
				return 0;

			// population is sorted - return last N indecies
			int end = start + numberOfChromosomes;
			int n = _currentSize < end ? _currentSize : end;
			int lim = _currentSize - n;
			int i = 0;
			for( int j = _currentSize - start - 1; j >= lim; i++, j-- )
				results[ i ] = j;

			return i;
		}
		else
		{
			if( start >= _worst.GetCurrentSize() )
				return 0;

			// get worst chromosomes indecies form sorted group
			int end = start + numberOfChromosomes;
			int lim = _worst.GetCurrentSize() < end ? _worst.GetCurrentSize() : end;
			int i = 0;
			for( int j = 0; j < lim; i++, j++ )
				results[ i ] = _worst.GetAt( j );

			return lim;
		}
	}

	// Fills the given array with the worst chromosomes in the population
	// Returns number of saved chromosomes
	int GaPopulation::GetWorsChromosomes(GaChromosomePtr* results,
		int start,
		int numberOfChromosomes) const
	{
		// population initialized?
		if( !results || numberOfChromosomes <= 0 || !_chromosomes )
			return 0;

		if( _parameters.GetSorting() )
		{
			if( start >= _currentSize )
				return 0;

			// population is sorted - return last N chromosomes
			int end = start + numberOfChromosomes;
			int n = _currentSize < end ? _currentSize : end;
			int lim = _currentSize - n;
			int i = 0;
			for( int j = _currentSize - start - 1; j >= lim; i++, j-- )
				results[ i ] = _chromosomes[ j ]->GetChromosome();

			return i;
		}
		else
		{
			if( start >= _worst.GetCurrentSize() )
				return 0;

			// get worst chromosomes form sorted group
			int end = start + numberOfChromosomes;
			int lim = _worst.GetCurrentSize() < end ? _worst.GetCurrentSize() : end;
			int i = 0;
			for( int j = 0; j < lim; i++, j++ )
				results[ i ] = _chromosomes[ _worst.GetAt( j ) ]->GetChromosome();

			return lim;
		}
	}

	// Replaces chromosome at given position with new one
	// Returns 1 if chromosome is replaced, otherwise returns 0
	int GaPopulation::Replace(int index,
		GaChromosomePtr newChromosome)
	{
		// verify parameters
		if( !_chromosomes || index < 0 || index >= _currentSize || newChromosome.IsNULL() )
			return 0;

		// difference of old and new chromosome's fitness value
		float fitnessDiff = newChromosome->GetFitness() - _chromosomes[ index ]->GetChromosome()->GetFitness();
		float scaledFitnessDiff = 0;

		if( _parameters.GetSorting() )
		{
			// make scaled chromosome
			GaScaledChromosome* newScaled = new GaScaledChromosome( newChromosome, this, -1 );

			GaScaledChromosome* oldScalde = _chromosomes[ index ];

			// difference of old and new chromosome's scaled fitness value
			scaledFitnessDiff = newScaled->GetScaledFitness() - oldScalde->GetScaledFitness();

			int res = oldScalde->CompareFitnesses( *newScaled );

			// new chromsome should be inserted at same position as old one had
			if( res == 0 )
			{
				// replace chromosomes
				delete _chromosomes[ index ];
				_chromosomes[ index ] = newScaled;
				newScaled->SetIndex( index );
			}
			else 
			{
				int oldIndex = index;

				// new chromosome should be placed below old one (new has worse fitness)
				if( res > 0 )
				{
					for( ; _chromosomes[ index ]->CompareFitnesses( *newScaled ) > 0 && index < _currentSize - 1; index++ )
					{
						_chromosomes[ index ] = _chromosomes[ index + 1 ];
						_chromosomes[ index ]->SetIndex( index );
					}
				}
				// new chromosome should be placed above old one (new has better fitness)
				else
				{
					for( ; _chromosomes[ index ]->CompareFitnesses( *newScaled ) < 0 && index > 0; index-- )
					{
						_chromosomes[ index ] = _chromosomes[ index - 1 ];
						_chromosomes[ index ]->SetIndex( index );
					}
				}

				// replace chromosomes
				delete oldScalde;
				_chromosomes[ index ] = newScaled;
				_chromosomes[ index ]->SetIndex( index );
			}
		}
		else
		{
			GaSortedGroupType groups = _chromosomes[ index ]->GetGroups();
			float oldScaledFitness = _chromosomes[ index ]->GetScaledFitness();

			// remove chromsome from the groups if it was in any
			_best.Remove( index );
			_worst.Remove( index );

			// replace chromosomes
			_chromosomes[ index ]->SetChromosome( newChromosome );

			// old chromosome was in best chromosome group
			if( groups & GASGT_BEST )
			{
				// try adding new chrosmsome into worst chromosome group
				_worst.Add( index );

				// find chromosome which should be placed in the group insted old one
				RefreshBestGroup();
			}

			// old chromosome was in worst chromosome group
			if( groups & GASGT_WORST )
			{
				// try adding new chrosmsome into best chromosome group
				_best.Add( index );

				// find chromosome which should be placed in the group insted old one
				RefreshWorstGroup();
			}

			if( !( groups & ( GASGT_BEST | GASGT_BEST ) ) )
			{
				// insert new chromosome in best or worst chromsome group if needed
				_best.Add( index );
				_worst.Add( index );
			}

			// difference of old and new chromosome's scaled fitness value
			scaledFitnessDiff += _chromosomes[ index ]->GetScaledFitness() - oldScaledFitness;
		}

		// update statistics with new values of fitnesses
		UpdateStatistics( fitnessDiff, scaledFitnessDiff );

		return 1;
	}

	// Replaces group chromosomes with new ones
	// Returns number of replaced chromosomes
	int GaPopulation::ReplaceGroup(int* indices,
		GaChromosomePtr* newChromosomes,
		int numberOfChromosomes)
	{
		// verify parameters
		if( !indices || !newChromosomes || numberOfChromosomes <= 0 || !_chromosomes )
			return 0;

		// number of replaced chromosomes
		int replaced = 0;

		float totalFitnessDiff = 0;
		float totalScaledFitnessDiff = 0;

		if( _parameters.GetSorting() )
		{
			struct GaReplacementTabelEntry
			{
				int index;

				GaScaledChromosome* chromosome;

				// Inserts entry into replacement table
				static void Insert(GaReplacementTabelEntry* table, int size, GaScaledChromosome* chromosome, int index)
				{
					if( index == -1 )
					{
						// find place in replacement table for new chromosome (use fitness value)
						for( ; size > 0 && chromosome->CompareFitnesses( *table[ size - 1 ].chromosome ) > 0; size-- )
							table[ size ] = table[ size - 1 ];
					}
					else
					{
						// find place in replacement table for new chromosome (chromosome index)
						for( ; size > 0 && chromosome->GetIndex() < table[ size - 1 ].index; size-- )
							table[ size ] = table[ size - 1 ];
					}

					// insert into replacement table
					table[ size ].index = index;
					table[ size ].chromosome = chromosome;
				}

			}* replacementTable = new GaReplacementTabelEntry[ 2 * numberOfChromosomes ];

			// size of replacement table
			int replacementTableSize = 0;

			// fill the replacement table
			for( int j = 0; j < 2; j++ )
			{
				for( int i = 0; i < numberOfChromosomes; i++ )
				{
					int index = indices[ i ];

					// verify passed index and chromosome pointer
					if( index < 0 || index >= _currentSize || newChromosomes[ i ].IsNULL() )
						continue;

					// choromosome which is going to be inserted into table
					GaScaledChromosome* chromosome = !j ? _chromosomes[ index ] 
						: new GaScaledChromosome( newChromosomes[ i ], this, -1 );

					// insert chromsome infos into replacement table
					GaReplacementTabelEntry::Insert( replacementTable, replacementTableSize, chromosome, !j ? index : -1 );

					replacementTableSize++;
				}
			}

			if( replacementTableSize > 0 )
			{
				int previousPosition = 0;
				do
				{
					int currentPosition = previousPosition;

					// find minimal group in replacement tabel which can be replaced at once
					for( int sum = 0; currentPosition < replacementTableSize; currentPosition++ )
					{
						sum += replacementTable[ currentPosition ].index == -1 ? +1 : -1;

						// minimal group found
						if( !sum )
							break;
					}

					// direction of passing through population and replacement table
					int dir = replacementTable[ previousPosition ].index >= 0 ? +1 : -1;

					// the first and the last indices (replacment table) of the minimal replacement group
					int replacementIndex = dir == +1 ? previousPosition : currentPosition;
					int limit = dir == +1 ? currentPosition : previousPosition;

					// current index at which new chromosome should be inserted
					int insertionIndex = replacementTable[ replacementIndex ].index;

					// replace all chromosomes in the minimal replacement group
					for( int currentIndex = insertionIndex; dir * replacementIndex <= dir * limit; )
					{
						GaReplacementTabelEntry* entry = replacementTable + replacementIndex;
						GaScaledChromosome* chromosome = 
							currentIndex < _currentSize && currentIndex >= 0 ? _chromosomes[ currentIndex ] : NULL;

						bool move = true;

						// chromosome should be inserted
						if( entry->index < 0 )
						{
							// insert as much as possible chromosome at this point
							//while( dir * replacementIndex <= dir * limit && 
							if(	( !chromosome || dir * chromosome->CompareFitnesses( *entry->chromosome ) <= 0 ) )
							{
								// add to population
								_chromosomes[ insertionIndex ] = entry->chromosome;
								_chromosomes[ insertionIndex ]->SetIndex( insertionIndex );

								// update fitness difference
								totalFitnessDiff += entry->chromosome->GetChromosome()->GetFitness();
								totalScaledFitnessDiff += entry->chromosome->GetScaledFitness();

								// next replacement entry
								replacementIndex += dir;
								//entry += dir;

								// move inseratation point
								insertionIndex += dir;

								move = false;
							}
						}
						// chromosome should be remove?
						else if( currentIndex == entry->index )
						{
							// update fitness difference
							totalFitnessDiff -= chromosome->GetChromosome()->GetFitness();
							totalScaledFitnessDiff -= chromosome->GetScaledFitness();

							// free memory used by scaled chromosome
							delete chromosome;

							// next replacement entry
							replacementIndex += dir;

							// next existing chromosome
							currentIndex += dir;

							move = false;

							replaced++;
						}

						if( move )
						{
							// new chromosome should not be inserted now just move existing chromosome
							_chromosomes[ insertionIndex ] = chromosome;
							_chromosomes[ insertionIndex ]->SetIndex( insertionIndex );
							insertionIndex += dir;

							// next existing chromosome
							currentIndex += dir;
						}
					}

					// move to the begining of new minimal replacement group
					previousPosition = currentPosition + 1;
				} while( previousPosition < replacementTableSize );
			}
			delete[] replacementTable;
		}
		else
		{
			bool bestRemoved = false, worstRemoved = false;

			// replace the chromosomes
			for( int i = 0; i <  numberOfChromosomes; i++ )
			{
				int index = indices[ i ];

				// verify passed arguments for replacement
				if( index >= 0 && index < _currentSize && !newChromosomes[ i ].IsNULL() )
				{
					GaSortedGroupType groups = _chromosomes[ index ]->GetGroups();

					// set flags if the groups should be refreshed
					bestRemoved |= ( groups & GASGT_BEST ) != 0;
					worstRemoved |= ( groups & GASGT_WORST ) != 0;

					// remove from sorted group if it was in any
					_best.Remove( index );
					_worst.Remove( index );

					// calculate the difference of fitness values between two chromosomes
					totalFitnessDiff += newChromosomes[ i ]->GetFitness() - _chromosomes[ index ]->GetChromosome()->GetFitness();
					float oldScaledFitnessDiff = _chromosomes[ index ]->GetScaledFitness();

					// replace chromsome
					_chromosomes[ index ]->SetChromosome( newChromosomes[ i ] );

					// try adding new chromosome in opposite group from old one
					if( ( groups & ( GASGT_BEST | GASGT_WORST ) ) == GASGT_BEST )
						_worst.Add( index );
					if( ( groups & ( GASGT_WORST | GASGT_BEST ) ) == GASGT_WORST )
						_best.Add( index );

					// calculate the difference of scaled fitness values between two chromosomes
					totalScaledFitnessDiff += _chromosomes[ index ]->GetScaledFitness() - oldScaledFitnessDiff;

					replaced++;
				}
			}

			// refresh groups if needed
			if( bestRemoved )
				RefreshBestGroup();
			if( worstRemoved )
				RefreshWorstGroup();
		}

		// update statistics with new values of fitnesses
		UpdateStatistics( totalFitnessDiff, totalScaledFitnessDiff );

		return replaced;
	}

	// Inserts chromosome into population
	// Returns 1 if chromosome is inserted, otherwise returns 0
	int GaPopulation::Insert(GaChromosomePtr chromosome)
	{
		if( chromosome.IsNULL() )
			return 0;

		float fitnessDiff = 0;
		float scaledFitnessDiff = 0;

		if( _parameters.GetSorting() )
		{
			GaScaledChromosome* scaled = new GaScaledChromosome( chromosome, this, -1 );

			// find the postition for chromosome and insert it
			int i = _currentSize - 1;
			for( ; i >= 0 && scaled->CompareFitnesses( *_chromosomes[ i ] ) >= 0; i-- )
			{
				// when population is full worst chromosome is removed
				if( i + 1 == _parameters.GetPopulationSize() )
				{
					// calculate fitness difference
					fitnessDiff -= _chromosomes[ i ]->GetChromosome()->GetFitness();
					scaledFitnessDiff -= _chromosomes[ i ]->GetScaledFitness();

					// remove chromosome
					delete _chromosomes[ i ];
				}
				else
				{
					// move chromosome down
					_chromosomes[ i + 1 ] = _chromosomes[ i ];
					_chromosomes[ i + 1 ]->SetIndex( i + 1 );
				}
			}

			// popunalion is full and new chromosome cannot fit in it
			if( i + 1 == _parameters.GetPopulationSize() )
				// remove new chromsome
				delete scaled;
			else
			{
				// insert chromosome
				_chromosomes[ i + 1 ] = scaled;
				scaled->SetIndex( i + 1 );

				// calculate fitness difference
				fitnessDiff += chromosome->GetFitness();
				scaledFitnessDiff += scaled->GetScaledFitness();
			}

			// increase population size
			if( _currentSize < _parameters.GetPopulationSize() )
				_currentSize++;
		}
		else
		{
			// population still not full?
			if( _currentSize < _parameters.GetPopulationSize() )
			{
				GaScaledChromosome* scaled = new GaScaledChromosome( chromosome, this, -1 );

				// insert chromosome
				_chromosomes[ _currentSize ] = scaled;
				scaled->SetIndex( _currentSize );

				// calculate fitness difference
				fitnessDiff += chromosome->GetFitness();
				scaledFitnessDiff += scaled->GetScaledFitness();

				// increase population size
				_currentSize++;

				// refresh best and worst chromosome groups
				_best.Add( _currentSize - 1 );
				_worst.Add( _currentSize - 1 );
			}
		}

		// updates statistics
		UpdateStatistics( fitnessDiff, scaledFitnessDiff );

		return 1;
	}

	// Inserts a group of choromosomes in population
	// Returns number of inserted chromosomes
	int GaPopulation::InsertGroup(GaChromosomePtr* chromosomes,
		int numberOfChromosomes)
	{
		if( !numberOfChromosomes  || !chromosomes )
			return 0;

		int inserted = 0;

		float fitnessDiff = 0;
		float scaledFitnessDiff = 0;

		if( _parameters.GetSorting() )
		{
			if( _currentSize > 0 )
			{
				// sorted table of new chromosomes
				GaScaledChromosome** insertionTable = new GaScaledChromosome*[ numberOfChromosomes ];
				int insertionSize = 0;

				// sort new chromosomes and put them in insertion table
				for( int i = 0; i < numberOfChromosomes; i++ )
				{
					if( !chromosomes[ i ].IsNULL() )
					{
						// make scaled chromosome
						GaScaledChromosome* sc = new GaScaledChromosome( chromosomes[ i ], this, -1 );

						// find the position in table at which the chromosome should be inserted
						int j = insertionSize - 1;
						for( ; j >= 0 && sc->CompareFitnesses( *insertionTable[ j ] ) >= 0; j-- )
							insertionTable[ j + 1 ] = insertionTable[ j ];

						// add chromosome to tabel
						insertionTable[ j + 1 ] = sc;
						insertionSize++;
					}
				}

				if( insertionSize > 0 )
				{
					int populationPos = _currentSize - 1;
					// insert chromosomes from insertion table to population
					for( int i = populationPos + insertionSize; insertionSize > 0; i-- )
					{
						// selects the worst chromosome
						bool n = populationPos < 0 || _chromosomes[ populationPos ]->CompareFitnesses( *insertionTable[ insertionSize - 1 ] ) >= 0;

						GaScaledChromosome* sc = n ? insertionTable[ --insertionSize ] : _chromosomes[ populationPos-- ];

						// selected chromosome fits in population?
						if( i < _parameters.GetPopulationSize() )
						{
							// insert or move chromosome
							_chromosomes[ i ] = sc;
							sc->SetIndex( i );

							// new chromosomes has been added
							if( n )
							{
								// increase population size
								_currentSize++;

								// update fitness values
								fitnessDiff += sc->GetChromosome()->GetFitness();
								scaledFitnessDiff += sc->GetScaledFitness();

								inserted++;
							}
						}
						// selected chromosome doesn't fit in population?
						else
						{
							// removing chromosome was in popultaion?
							if( !n )
							{
								_currentSize--;

								// update fitness values
								fitnessDiff -= sc->GetChromosome()->GetFitness();
								scaledFitnessDiff -= sc->GetScaledFitness();
							}

							// remove chromsome
							delete sc;
						}
					}
				}

				// delete temp insertion table
				delete[] insertionTable;
			}
			else
			{
				// insert new chromosomes into population in sorted order
				for( int i = 0; i < numberOfChromosomes; i++ )
				{
					if( !chromosomes[ i ].IsNULL() )
					{
						// make scaled chromosome
						GaScaledChromosome* sc = new GaScaledChromosome( chromosomes[ i ], this, -1 );

						// find the position at which the chromosome should be inserted
						int j = _currentSize - 1;
						for( ; j >= 0 && sc->CompareFitnesses( *_chromosomes[ j ] ) >= 0; j-- )
						{
							// remove last chromosome if the population is full
							if( j + 1 == _parameters.GetPopulationSize() )
							{
								GaScaledChromosome* m = _chromosomes[ j + 1 ];

								// update fitness values
								fitnessDiff -= m->GetChromosome()->GetFitness();
								scaledFitnessDiff -= m->GetScaledFitness();

								delete m;
							}

							// insert new chromosome
							_chromosomes[ j + 1 ] = _chromosomes[ j ];

							inserted++;
						}

						// new chromosome fit into population
						if( j + 1 == _parameters.GetPopulationSize() )
							// remove new chromosome which cannot fit
							delete sc;
						else
						{
							// add chromosome to table
							_chromosomes[ j + 1 ] = sc;
							_currentSize++;

							// update fitness values
							fitnessDiff += sc->GetChromosome()->GetFitness();
							scaledFitnessDiff += sc->GetScaledFitness();
						}
					}
				}
			}
		}
		else
		{
			// insert new chromosomes
			for( int i = 0; i < numberOfChromosomes; i++ )
			{
				// stop if population is full
				if( _currentSize >= _parameters.GetPopulationSize() )
					break;

				if( !chromosomes[ i ].IsNULL() )
				{
					// add new chromosome
					_chromosomes[ _currentSize ] = new GaScaledChromosome( chromosomes[ i ], this, _currentSize );
					_currentSize++;

					// refresh best and worst chromosome groups
					_best.Add( _currentSize - 1 );
					_worst.Add( _currentSize - 1 );

					inserted++;
				}
			}
		}

		// updates statistics
		UpdateStatistics( fitnessDiff, scaledFitnessDiff );

		return inserted;
	}

	// Removes chromosome at given position
	// Returns 1 if chromosome is removed, otherwise returns 0
	int GaPopulation::Remove(int chromosome)
	{
		// check parameters
		if( chromosome < 0 || !_parameters.GetResizable() || chromosome >= _currentSize )
			return 0;

		// chromosome which is going to be removed
		GaScaledChromosome* old = _chromosomes[ chromosome ];

		// fintes values differences
		float fitnessDiff = -old->GetChromosome()->GetFitness();
		float scaledFitnessDiff = -old->GetScaledFitness();

		// move chromosomes
		for( int i = chromosome; i < _currentSize; i++ )
		{
			_chromosomes[ i ] = _chromosomes[ i + 1 ];
			_chromosomes[ i ]->SetIndex( i );
		}

		if( !_parameters.GetSorting() )
		{
			// update best and worst chromosome groups

			_best.Clear();
			_worst.Clear();

			_currentSize--;

			RefreshBestGroup();
			RefreshWorstGroup();
		}
		else
			_currentSize--;

		// remove chromosome
		delete old;

		// update statistics
		UpdateStatistics( fitnessDiff, scaledFitnessDiff );

		return 1;
	}

	// Removes chromosomes at given positions
	// Returns number of removed chromosomes
	int GaPopulation::RemoveGroup(int* chromosomes,
		int numberOfChromosomes)
	{
		if( !chromosomes || numberOfChromosomes < 0 || !_parameters.GetResizable() )
			return 0;

		int removed = 0;

		float fitnessDiff = 0;
		float scaledFitnessDiff = 0;

		// sort remove table in descending by chromosome's index
		int* removeTable = new int[ numberOfChromosomes ];
		int removeTableSize = 0;
		for( int i = 0; i < numberOfChromosomes; i++ )
		{
			int c = chromosomes[ i ];

			// valid index?
			if( c >= 0 && c < _currentSize )
			{
				// find position to insert
				int j = removeTableSize - 1;
				for( ; j >= 0 && c < removeTable[ j ]; j-- )
					removeTable[ j + 1 ] = removeTable[ j ];

				// insert
				removeTable[ j + 1 ] = c;
				removeTableSize++;
			}
		}

		// clears best and worst chromosome groups
		if( !_parameters.GetSorting() )
		{
			_best.Clear();
			_worst.Clear();
		}

		// remove chromosomes
		for( int i = 0, pos = 0; removeTableSize > 0; i++ )
		{
			// current chromosome should be removed
			if( i == removeTable[ removeTableSize - 1 ] )
			{
				// fintes values differences
				fitnessDiff -= _chromosomes[ i ]->GetChromosome()->GetFitness();
				scaledFitnessDiff -= _chromosomes[ i ]->GetScaledFitness();

				// remove chromosome
				delete _chromosomes[ i ];

				// next chromosome index for removing
				removeTableSize--;
				_currentSize--;

				removed++;
			}
			else 
			{
				// needs moving of current chromosome
				if( pos != i )
				{
					_chromosomes[ pos ] = _chromosomes[ i ];
					_chromosomes[ pos ]->SetIndex( pos );
				}

				// try inserting current chromosome into sorted groups
				if( !_parameters.GetSorting() )
				{
					_best.Add( pos );
					_worst.Add( pos );
				}

				// next position
				pos++;
			}
		}

		// update statistics
		UpdateStatistics( fitnessDiff, scaledFitnessDiff );

		delete[] removeTable;

		return removed;
	}

	// Removes all chromosomes from population and clears statistics
	void GaPopulation::Clear(bool clearStatistics)
	{
		if( clearStatistics )
			_statistics.Clear();

		// remove all chromosomes
		if( _chromosomes )
		{
			for( int i = 0; i < _currentSize; i++ )
			{
				if( _chromosomes[ i ] )
					delete _chromosomes[ i ];

				_chromosomes[ i ] = 0;
			}
		}

		if( _parameters.GetResizable() )
			_currentSize = 0;
	}

	// Returns ranking of chromosome.
	// If chromosome has no ranking returns -1.
	int GaPopulation::GetChromosomeRanking(int chromosomeIndex,
									   bool reverse/* = false*/)
	{
		// check passed parameters
		if( chromosomeIndex < 0 || chromosomeIndex > _currentSize )
			return -1;

		if( _parameters.GetSorting() )
			// population is sorted, chromosome index is its rank
			return reverse ? _currentSize - chromosomeIndex - 1 : chromosomeIndex;

		// ranking of chromosome in best group
		int rank = _best.GetRanking( chromosomeIndex );
		if( rank >= 0 )
			return reverse ? _currentSize - rank : rank;

		// ranking of chromosome in worst group
		rank = _worst.GetRanking( chromosomeIndex );
		if( rank >= 0 )
			return reverse ? rank : _currentSize - rank;

		return -1;
	}

	// Sets parameter of the population
	void GaPopulation::SetParameters(const GaPopulationParameters& parameters)
	{
		bool refreshBest = false, refreshWorst = false, resort = true;

		int oldSize = _parameters.GetPopulationSize();
		int newSize = parameters.GetPopulationSize();
		
		int lim = _currentSize < newSize ? _currentSize : newSize;

		// size changed?
		if( oldSize != newSize )
		{
			// allocate memory for new array of chromosomes
			GaScaledChromosome** n = new GaScaledChromosome*[ newSize ];

			// copy existing chromosomes to new array
			for( int i = 0; i < lim; i++ )
				n[ i ] = _chromosomes[ i ];

			// remove some chromosomes if new population size is smaller then old
			for( int i = lim; i < _currentSize; i++ )
			{
				// remove chromosome from sorted groups if it was in any
				if( !parameters.GetSorting() )
				{
					refreshBest |= _best.Remove( i );
					refreshWorst |= _worst.Remove( i );
				}

				delete _chromosomes[ i ];
			}

			// should the population be filled
			if( !parameters.GetResizable() )
			{
				// add new chromosome if new population size is bigger then old
				for( int i = lim; i < newSize; i++ )
				{
					// because the new chromosomes is added the groups should be refreshed or the population resorted 
					refreshBest = refreshWorst = resort = true;

					// make new chromosome from prototype
					n[ i ] = new GaScaledChromosome( _prototype->MakeNewFromPrototype(), this, i );
				}
			}

			// swap arrays of chromosomes
			delete[] _chromosomes;
			_chromosomes = n;
		}

		_usingScaledFitness = parameters.GetUsingScaledFitness();

		if( !parameters.GetSorting() )
		{
			// the groups should be refreshed if new size is bigger
			refreshBest |= parameters.GetBestTrackCount() > _parameters.GetBestTrackCount();
			refreshWorst |= parameters.GetWorstTrackCount() > _parameters.GetWorstTrackCount();

			// set new sizes for sorted groups
			_best.SetMaxSize( parameters.GetBestTrackCount() );
			_worst.SetMaxSize( parameters.GetWorstTrackCount() );

			// save new parameters
			_parameters = parameters;

			// refresh sorted group if needed
			if( refreshBest )
				RefreshBestGroup();
			if( refreshWorst )
				RefreshWorstGroup();
		}
		else
		{
			// sorted groups are disabled
			_best.SetMaxSize( 0 );
			_worst.SetMaxSize( 0 );

			resort |= parameters.GetSorting() != _parameters.GetSorting();
			resort |= parameters.GetUsingScaledFitness() != _parameters.GetUsingScaledFitness();

			// save new parameters
			_parameters = parameters;

			// should the population be resorted?
			if( resort )
				ResortPopulation( false, false, true );
		}
	}

	// Sets comparator used for sorting the chromosomes
	void GaPopulation::SetSortComparator(const GaFitnessComparator* comparator)
	{
		_best.Clear();
		_worst.Clear();

		_best.SetComparator( _configuration->GetSortComparator() );
		_worst.SetComparator( _configuration->GetSortComparator() );
		_statistics.SetFitnessComparator( comparator );
	}

	// Updates statistics for population after replacing chromosome(s)
	void GaPopulation::UpdateStatistics(float fitnessChange,
									float scaledFitnessChange)
	{
		// updates size of population
		_statistics.ChangeValue( GSV_POPULATION_SIZE, (float)_currentSize, false );

		// updates total and avarge fitnesses
		_statistics.ChangeValue( GSV_TOTAL_FITNESS, fitnessChange, true );

		// updates scaled fitnes only if needed
		if( _configuration->Scaling().HasOperation() && _configuration->Scaling().GetOperation().IsRankingBased() )
			_statistics.ChangeValue( GSV_TOTAL_FITNESS_SCALED, scaledFitnessChange, true );

		// updates value of the best chromsome's fitness
		int best = 0;
		if( GetBestChromosomes( &best, 0, 1 ) )
		{
			_statistics.ChangeValue( GSV_BEST_FITNESS, _chromosomes[ best ]->GetChromosome()->GetFitness(), false );
			_statistics.ChangeValue( GSV_BEST_FITNESS_SCALED, _chromosomes[ best ]->GetScaledFitness(), false );
		}

		// updates value of the worst chromsome's fitness
		int worst = 0;
		if( GetWorsChromosomes( &worst, 0, 1 ) )
		{
			_statistics.ChangeValue( GSV_WORST_FITNESS, _chromosomes[ worst ]->GetChromosome()->GetFitness(), false );
			_statistics.ChangeValue( GSV_WORST_FITNESS_SCALED, _chromosomes[ worst ]->GetScaledFitness(), false );
		}
	}

	// Should be called when scaling operation is changed
	void GaPopulation::RescaleAll()
	{
		float totalScaled = 0;
		for( int i = 0; i < _currentSize; i++ )
		{
			_chromosomes[ i ]->Rescale();
			totalScaled += _chromosomes[ i ]->GetScaledFitness();
		}

		_statistics.ChangeValue( GSV_TOTAL_FITNESS_SCALED, totalScaled, false );
	}

	// Sorting of the population
	void GaPopulation::ResortPopulation(bool refreshFitnesses,
		bool scalingChanged,
		bool comparatorChanged)
	{
		float totalFittness = 0;

		if( refreshFitnesses )
		{
			// fitness evaluation is changed, calculate total fitness difference
			for( int i = 0; i < _currentSize; i++ )
			{
				_chromosomes[ i ]->GetChromosome()->RefreshFitness();
				totalFittness += _chromosomes[ i ]->GetChromosome()->GetFitness();
			}
			
			// updates statistics
			_statistics.ChangeValue( GSV_TOTAL_FITNESS, totalFittness, false );
			UpdateStatistics( 0, 0 );
		}

		if( refreshFitnesses || comparatorChanged )
		{
			// first step sorting is done using the unscaled fitnes values
			bool oldFlag = _usingScaledFitness;
			_usingScaledFitness = false;

			if( _parameters.GetSorting() )
				// resort population
				qsort( _chromosomes, _currentSize, sizeof( _chromosomes[ 0 ] ), GaPopulation::SortComparison );
			else
			{
				// no sorting, refresh best and worst chromosome groups

				_best.Clear();
				_worst.Clear();

				RefreshBestGroup();
				RefreshWorstGroup();
			}

			_usingScaledFitness = oldFlag;
		}

		// resacling of all chromosomes
		bool rescale = scalingChanged || ( ( refreshFitnesses || comparatorChanged ) && _configuration->Scaling().HasOperation() );

		// second step sorting (if needed) is done using scaled fitness values
		if( _usingScaledFitness )
		{
			// rescale of all chromosomes if needed
			if( rescale )
				RescaleAll();

			if( _parameters.GetSorting() )
				// resort population
				qsort( _chromosomes, _currentSize, sizeof( _chromosomes[ 0 ] ), GaPopulation::SortComparison );
			else
			{
				// no sorting, refresh best and worst chromosome groups

				_best.Clear();
				_worst.Clear();

				RefreshBestGroup();
				RefreshWorstGroup();
			}
		}

		if( _parameters.GetSorting() )
		{
			// update ranking of scaled chromosomes
			for( int i = 0; i < _currentSize; i++ )
				_chromosomes[ i ]->SetIndex( i );
		}

		// update sacaled fitnes values if the scaling is ranking based
		if( rescale && !_usingScaledFitness )
			RescaleAll();

		// updates new statistics
		UpdateStatistics( 0, 0 );
		_statistics.ChangeValue( GSV_TOTAL_FITNESS, totalFittness, false );
	}

	// Comparison of chromosomes for sorting population
	int GaPopulation::SortComparison(const void* first,
										  const void* second)
	{
		return -( *(const GaScaledChromosome**)first )->CompareFitnesses( **(const GaScaledChromosome**)second );
	}

} // Population

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The GNU General Public License (GPLv3)

Share

About the Author

Mladen Janković
Software Developer
Serbia Serbia
No Biography provided

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.1411023.1 | Last Updated 7 Apr 2012
Article Copyright 2008 by Mladen Janković
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid