population.cc

linux下的一个分组遗传算法

//
// population.cc - Used for the Genetic Grouping Algorithm
//
// author: J.I.v.Hemert
// last updated : 07-11-1997
//
// This file implements the class PopulationC.
//


#include "population.h"


extern MLCG rnd;


//------------------------------------------------ Public functions


void PopulationC::Initialize (GaParamsT gaparameters, int nrofobjects, bool debugactive, int k_coloring, ColoringT coloringalgorithm)
// Ask every geno in the population to initialize itself.
{
	int i;
	bestindex = 0;
	totalevaluations = 0;

	debug = debugactive;
	gaparams = gaparameters;

	// Check for some disastrous errors which could ruin the experiments
	if (gaparams.PopulationSize > MAXPOPSIZE)
	{
		cerr << "Error: population size is larger than " << MAXPOPSIZE << endl;
		exit (2);
	}
	if (gaparams.PopulationSize < 4)
	{
		cerr << "Error: population size must be larger than 3 " << endl;
		exit (2);
	}
	if ((gaparams.N_Crossover % 2) == 1)
	{
		gaparams.N_Crossover++;
		cerr << "Warning:  crossover should be an even number, using " << gaparams.N_Crossover << " instead" << endl;
	}

	for (i = 0; i < gaparams.PopulationSize; i++)
		population[i].Initialize (nrofobjects, gaparams.AllelMutationProb, k_coloring, coloringalgorithm);

} // Initialize ()


void PopulationC::Evaluate ()
// Ask fitness of every geno and make a total, note that
// we do not ask every geno to calculate it's fitness.
// note: could be faster by letting the evaluation in the
// GenotypeC update our bestfitness variable.
{
	int i;
	int object;								// holds first faulty gene

	for (i = 0; i < gaparams.PopulationSize; i++)
	{
		// This switch adds quite some extra load on the cpu
		if (debug)
			switch (population[i].IsValid (object))
			{
				case none:
					break;
				case badcoloring:
					cerr << endl << "Found an invalid genoom! [badcoloring in gene "
							<< object << "]" << endl;
					population[i].Print ();
					break;
				case duplicatecolor:
					cerr << endl << "Found an invalid genoom! [duplicatecolor]" << endl;
					population[i].Print ();
					break;
				case illegalcolorused:
					cerr << endl << "Found an invalid genoom! [illegalcolorused in gene "
							<< object << "]" << endl;
					population[i].Print ();
					break;
			}

		// Look for a better best fitness
		if (population[bestindex].GetFitness () > population[i].GetFitness ())
			bestindex = i;
	}
} // Evaluate ()


void PopulationC::Reproduce ()
// Use the genetic operators to form a new generation.
{
	PlayTwoTournament ();
	ApplyCrossover ();
	ApplyMutation ();
	ApplyInversion ();

} // Reproduce ()


void PopulationC::PrintBest (ofstream & output)
// Print out the best geno from the pack.
{
	output << bestindex << ": ";
	population[bestindex].Print (output);

} // PrintBest ()


void PopulationC::PrintBest ()
// Print out the best geno from the pack, to standard error.
{
	cerr << bestindex << ": ";
	population[bestindex].Print (/* cerr */);

} // PrintBest ()


void PopulationC::PrintPop ()
// Give a printout of all genos, warning creates a lot
// of output. Output goes to standerd error.
{
	int i;

	for (i = 0; i < gaparams.PopulationSize; i++)
	{
		cerr << i << ": ";
		population[i].Print (/* cerr */);
	}
} // PrintPop ()


double PopulationC::GetBestFitness ()
// Return the fitness value of the best geno, there is no
// calculation done here.
{
	return (population[bestindex].GetFitness ());

} // GetBestFitness ()


double PopulationC::GetColorsUsed ()
// Return the fitness value of the best geno, there is no
// calculation done here.
{
	return (population[bestindex].GetColorsUsed ());

} // GetBestFitness ()


double PopulationC::GetTotalEvaluations ()
// Return the number of evaluations done so far by this
// population, no calculation done here.
{
	return (totalevaluations);

} // GetTotalEvaluations ()


//------------------------------------------------ Private functions


void PopulationC::PlayTwoTournament ()
// Does the noisy-sort algorithm mentioned by E.Falkenhauer
// in "A New Representation and Operators for GGA applied to
// Grouping Problems". It takes at random two genos from the
// poplation. The geno with the best fitness is put back into
// the population, while the loser goes into a queue. This 
// queue ill replace our population, which leaves us with
// a noisy-sort on our population.
{
	int n, i, j;
	GenotypeC temp[MAXPOPSIZE];		// copy of population to use for selection
	bool removed[MAXPOPSIZE];		// holds the losers

	for (i = 0; i < gaparams.PopulationSize; i++)
	{
		removed[i] = false;
		population[i].Copy (temp[i]);
	}

	// We'll have to do this populationsize times
	for (n = 0; n < gaparams.PopulationSize - 1; n++)
	{
		// choose two genos for a tournament
		i = rnd.asLong () % gaparams.PopulationSize;
		while (removed[i])
			i = (i + 1) % gaparams.PopulationSize;
		j = rnd.asLong () % gaparams.PopulationSize;
		while ((i == j) || (removed[j]))
			j = (j + 1) % gaparams.PopulationSize;

		// pick winner and put it back, put loser in queue
		if ((temp[i].GetFitness () <= temp[j].GetFitness ()) && (n < gaparams.PopulationSize - 1))
		{
			temp[j].Copy (population[n]);
			removed[j] = true;
		}
		else
		{
			temp[i].Copy (population[n]);
			removed[i] = true;
		}
	}

	// Don't forget the last one
	i = 0;
	while (removed[i])
		i++;
	temp[i].Copy (population[n]);

} // PlayTwoTournament ()


void PopulationC::ApplyCrossover ()
// Does crossover operation on N_Crossove individuals.
{
	int i;

	for (i = 0; i < gaparams.N_Crossover; i = i + 2)
	{
		population[gaparams.PopulationSize - i - 1].Crossover (population[gaparams.PopulationSize - i - 2], population[i], population[i + 1]);
		totalevaluations += 2;
	}
} // ApplyCrossover ()


void PopulationC::ApplyMutation ()
// Choose N_Mutation genos and do a mutation on each of them.
{
	int i, j;
	bool mutated[MAXPOPSIZE];

	for (i = 0; i < gaparams.PopulationSize; i++)
		mutated[i] = false;

	for (i = 0; i < gaparams.N_Mutation; i++)
	{
		j = rnd.asLong () % gaparams.PopulationSize;
		while (mutated[j])
			j = (j + 1) % gaparams.PopulationSize;
		mutated[j] = true;
		population[j].Mutation ();
		totalevaluations++;
	}

} // ApplyMutation ()


void PopulationC::ApplyInversion ()
// Choose N_Inversion genos and do an inversion on each of them.
{
	int i, j;
	bool inverted[MAXPOPSIZE];

	for (i = 0; i < gaparams.PopulationSize; i++)
		inverted[i] = false;

	for (i = 0; i < gaparams.N_Inversion; i++)
	{
		j = rnd.asLong () % gaparams.PopulationSize;
		while (inverted[j])
			j = (j + 1) % gaparams.PopulationSize;
		inverted[j] = true;
		population[j].Inversion ();
		totalevaluations++;
	}

} // ApplyInversion ()


// eof population.cc