couplingoperations.cpp

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

/*! \file CouplingOperations.cpp
    \brief This file contains implementation of coupling operation classes.
*/

/*
 * 
 * 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 "GlobalRandomGenerator.h"
#include "Population.h"
#include "CouplingOperations.h"

using namespace Population;
using namespace Population::CouplingOperations;

namespace Population
{
	namespace CouplingOperations
	{

		// Couples selected chromosomes and produce offsprings based on passed parameters
		void GaSimpleCoupling::operator ()(const GaPopulation& population,
			GaCouplingResultSet& output,
			const GaCouplingParams& parameters,
			int workerId,
			int numberOfWorkers) const
		{
			GaSortedGroup& parents = output.GetSelectionResultSet().SelectedGroup();
			int size = parents.GetCurrentSize();

			// how much offsprings should be produced
			int lim = parameters.GetNumberOfOffsprings() <= output.GetNumberOfOffsprings()
				? parameters.GetNumberOfOffsprings()
				: output.GetNumberOfOffsprings();

			// how much offsprings should be produced
			int outSize = lim / numberOfWorkers;
			if( outSize % 2 )
				outSize++;
			// first offspring position
			int outStart = outSize * workerId;

			// last worker do more if the work cann't be divided equaly
			if( workerId == numberOfWorkers - 1 )
				outSize = lim - outStart;

			// last offspring position
			lim = outStart + outSize;

			for( int i = outStart; i < lim; i += 2 )
			{
				// get parent's indices
				int pi1 = parents[ i % size ];
				int pi2 = parents[ ( i + 1 ) % size ];

				// get parents
				GaChromosomePtr p1 = population.GetAt( pi1 ).GetChromosome();
				GaChromosomePtr p2 = population.GetAt( pi2 ).GetChromosome();

				// make new chromosome and save it to result set
				GaChromosomePtr o1 = p1->Crossover( p2 );
				o1->Mutation();
				output.SetOffspringAt( i, o1, pi1 );

				if( i + 1 < lim )
				{
					// make new chromosome and save it to result set
					GaChromosomePtr o2 = p2->Crossover( p1 );
					o2->Mutation();
					output.SetOffspringAt( i + 1, o2, pi2 );
				}
			}
		}

		// Couples selected chromosomes and produce offsprings based on passed parameters
		void GaCrossCoupling::operator ()(const GaPopulation& population,
			GaCouplingResultSet& output,
			const GaCouplingParams& parameters,
			int workerId,
			int numberOfWorkers) const
		{
			GaSortedGroup& parents = output.GetSelectionResultSet().SelectedGroup();
			int size = parents.GetCurrentSize();

			// how much offsprings should be produced
			int lim = parameters.GetNumberOfOffsprings() <= output.GetNumberOfOffsprings()
				? parameters.GetNumberOfOffsprings()
				: output.GetNumberOfOffsprings();

			// how much offsprings should be produced
			int outSize = lim / numberOfWorkers;
			// first offspring position
			int outStart = outSize * workerId;

			// last worker do more if the work cann't be divided equaly
			if( workerId == numberOfWorkers - 1 )
				outSize += lim % numberOfWorkers;

			// last offspring position
			lim = outStart + outSize;

			for( int i = outStart; i < lim; i++ )
			{
				// get parent's indices
				int pi1 = parents[ i % size ];
				int pi2 = parents[ ( i + 1 ) % size ];

				// get parents
				GaChromosomePtr p1 = population.GetAt( pi1 ).GetChromosome();
				GaChromosomePtr p2 = population.GetAt( pi2 ).GetChromosome();

				GaChromosomePtr best;
				float bestFitness;

				// make few offspring but choose only the best one
				for( int j = ( (const GaMulitpleCrossoverCouplingParams&) parameters ).GetOffspringsPerParentPair(); 
					j > 0; j-- )
				{
					// make new offspring
					GaChromosomePtr o = p1->Crossover( p2 );
					o->Mutation();

					// is this chromosome the best
					if( best.IsNULL() || o->GetFitness() > bestFitness )
					{
						// save the best chromosome
						bestFitness = o->GetFitness();
						best = o;
					}
				}

				// save chromosome in the result set
				output.SetOffspringAt( i, best, pi1 );
			}
		}

		// Couples selected chromosomes and produce offsprings based on passed parameters
		void GaInverseCoupling::operator ()(const GaPopulation& population,
			GaCouplingResultSet& output,
			const GaCouplingParams& parameters,
			int workerId,
			int numberOfWorkers) const
		{
			GaSortedGroup& parents = output.GetSelectionResultSet().SelectedGroup();
			int size = parents.GetCurrentSize();

			// how much offsprings should be produced
			int lim = parameters.GetNumberOfOffsprings() <= output.GetNumberOfOffsprings()
				? parameters.GetNumberOfOffsprings()
				: output.GetNumberOfOffsprings();

			// how much offsprings should be produced
			int outSize = lim / numberOfWorkers;
			// first offspring position
			int outStart = outSize * workerId;

			// last worker do more if the work cann't be divided equaly
			if( workerId == numberOfWorkers - 1 )
				outSize += lim % numberOfWorkers;

			// last offspring position
			lim = outStart + outSize;

			for( int i = outStart; i < lim; i++ )
			{
				// get parent's indices
				int j = i % size;
				int pi1 = parents[ j ];
				int pi2 = parents[ size - 1 - j ];

				// get parents
				GaChromosomePtr p1 = population.GetAt( pi1 ).GetChromosome();
				GaChromosomePtr p2 = population.GetAt( pi2 ).GetChromosome();

				GaChromosomePtr best;
				float bestFitness;

				// make few offspring but choose only the best one
				for( int k = ( (const GaMulitpleCrossoverCouplingParams&) parameters ).GetOffspringsPerParentPair(); 
					k > 0; k-- )
				{
					// make new offspring
					GaChromosomePtr o = p1->Crossover( p2 );
					o->Mutation();

					// is this chromosome the best
					if( best.IsNULL() || o->GetFitness() > bestFitness )
					{
						// save the best chromosome
						bestFitness = o->GetFitness();
						best = o;
					}
				}

				// save chromosome in the result set
				output.SetOffspringAt( i, best, pi1 );
			}
		}

		// Couples selected chromosomes and produce offsprings based on passed parameters
		void GaBestAlwaysCoupling::operator ()(const GaPopulation& population,
			GaCouplingResultSet& output,
			const GaCouplingParams& parameters,
			int workerId,
			int numberOfWorkers) const
		{
			GaSortedGroup& parents = output.GetSelectionResultSet().SelectedGroup();
			int size = parents.GetCurrentSize();

			// how much offsprings should be produced
			int lim = parameters.GetNumberOfOffsprings() <= output.GetNumberOfOffsprings()
				? parameters.GetNumberOfOffsprings()
				: output.GetNumberOfOffsprings();

			// how much offsprings should be produced
			int outSize = lim / numberOfWorkers;
			// first offspring position
			int outStart = outSize * workerId;

			// last worker do more if the work cann't be divided equaly
			if( workerId == numberOfWorkers - 1 )
				outSize += lim % numberOfWorkers;

			// last offspring position
			lim = outStart + outSize;

			// the best selected chromosome is always one of the parents
			GaChromosomePtr p1 = output.GetSelectionResultSet()[ 0 ];

			for( int i = outStart; i < lim; i++ )
			{
				// get other parent
				int pi2 = parents[ i % size ];
				GaChromosomePtr p2 = population.GetAt( pi2 );

				GaChromosomePtr best;
				float bestFitness;

				// make few offspring but choose only the best one
				for( int j = ( (const GaMulitpleCrossoverCouplingParams&) parameters ).GetOffspringsPerParentPair(); 
					j > 0; j-- )
				{
					// make new offspring
					GaChromosomePtr o = p2->Crossover( p1 );
					o->Mutation();

					// is this chromosome the best
					if( best.IsNULL() || o->GetFitness() > bestFitness )
					{
						// save the best chromosome
						bestFitness = o->GetFitness();
						best = o;
					}
				}

				// save chromosome in the result set
				output.SetOffspringAt( i, best, pi2 );
			}
		}

		// Couples selected chromosomes and produce offsprings based on passed parameters
		void GaRandomCoupling::operator ()(const GaPopulation& population,
			GaCouplingResultSet& output,
			const GaCouplingParams& parameters,
			int workerId,
			int numberOfWorkers) const
		{
			GaSortedGroup& parents = output.GetSelectionResultSet().SelectedGroup();
			int size = parents.GetCurrentSize();

			// how much offsprings should be produced
			int lim = parameters.GetNumberOfOffsprings() <= output.GetNumberOfOffsprings()
				? parameters.GetNumberOfOffsprings()
				: output.GetNumberOfOffsprings();

			// parents which will be used by this worker
			int inSize = size / numberOfWorkers;
			int inStart = inSize * workerId;

			// how much offsprings should be produced and position for saving offsprings
			int outSize = lim / numberOfWorkers;
			int outStart = outSize * workerId;

			// last worker do more if the work cann't be divided equaly
			if( workerId == numberOfWorkers - 1 )
			{
				inSize += size % numberOfWorkers;
				outSize += lim % numberOfWorkers;
			}

			// last offspring position
			lim = outStart + outSize;

			// copules
			for( int i = outStart, j = 0; i < lim; i++, j++ )
			{
				// get parent's indices
				int pi1 = parents[ inStart + j % inSize ];
				int pi2 = parents[ GaGlobalRandomIntegerGenerator->Generate( size ) ];

				// get parents
				GaChromosomePtr p1 = population.GetAt( pi1 ).GetChromosome();
				GaChromosomePtr p2 = population.GetAt( pi2 ).GetChromosome();
				
				GaChromosomePtr best;
				float bestFitness;

				// make few offspring but choose only the best one
				for( int k = ( (const GaMulitpleCrossoverCouplingParams&) parameters ).GetOffspringsPerParentPair(); 
					k > 0; k-- )
				{
					// make new offspring
					GaChromosomePtr o = p1->Crossover( p2 );
					o->Mutation();

					// is this chromosome the best
					if( best.IsNULL() || o->GetFitness() > bestFitness )
					{
						// save the best chromosome
						bestFitness = o->GetFitness();
						best = o;
					}
				}

				// save chromosome in the result set
				output.SetOffspringAt( i, best, pi1 );
			}
		}

	} // CouplingOperations
} // Population