population.cpp

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

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

			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++;
					}
				}

				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++;
				}
			}
		}