population.cpp

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

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