population.cpp

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

		// 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 ];
					}