genotype.cc

linux下的一个分组遗传算法

//
// genotype.cc - Used for the Genetic Grouping Algorithm
//
// author: J.I.v.Hemert
// last updated : 12-11-1997
//
// This file implements the class GenotypeC. It features the three genetic
// operators; crossover, mutation and inversion. Some functions to print
// out genos, a copy function and a function to get the fitness of a geno.
//


#include "genotype.h"


MLCG rnd;					// class to generate random numbers
static int idnum = 0;		// used for unique tagging of genos


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


void GenotypeC::Initialize (int numberofobjects, double allelemutationprobability, int k_coloring, ColoringT coloringalgorithm)
// Initialize the geno by making a coloring using the
// ColorObject function, and starting at a random node.
{
	int i, r;
	
	r = rnd.asLong ();

	idtag = idnum;
	idnum++;
	allelemutationprob = allelemutationprobability;

	coloringused = coloringalgorithm;

	if (coloringused == undefined)
	{
		cerr << "Error: No coloring algorithm defined";
		exit (2);
	}

	nrofgroups = 0;
	nrofcolors = k_coloring;
	nrofobjects = numberofobjects;

	if (nrofobjects > MAXOBJECTS)
	{
		cerr << "Error: number of objects is larger than " << MAXOBJECTS;
		exit (2);
	}

	for (i = 0; i < nrofobjects; i++)
		objects[i] = UNCOLORED;
	for (i = 0; i < nrofobjects; i++)
		ColorObject ((i + r) % nrofobjects);

	Evaluate ();

} // Initialize ()


void GenotypeC::Evaluate ()
// Calculate the fitness of a geno by penalizing every
// extra color used and every node having such a color.
{
	int i, j, max;
	int objectsingroup[MAXOBJECTS];		// number of objects in each group

	for (i = 0; i < nrofgroups; i++)
		objectsingroup[i] = 0;

	for (i = 0; i < nrofobjects; i++)
		objectsingroup[objects[i]]++;

	for (i = 0; i < nrofcolors; i++)
	{
		max = 0;
		for (j = 0; j < nrofgroups; j++)
			if (objectsingroup[max] < objectsingroup[j])
				max = j;
		objectsingroup[max] = 0;
	}

	fitness = nrofgroups - nrofcolors;

	for (i = 0; i < nrofgroups; i++)
		fitness = fitness + objectsingroup[i];

	// Count color occurrence, not needed until the
	// largefirst and smallfirst heuristics are implemented
	/*
	for (i = 0; i < nrofobjects; i++)
		groupsoccurrence[i] = 0;
	for (i = 0; i < nrofobjects; i++)
		groupsoccurrence[objects[i]]++;
	*/

} // Evaluate ()


void GenotypeC::Mutation ()
// Mutate a geno by eliminating some groups and reinserting
// the objects using the ColorObject function.
{
	int i;
	StackC savedobjects;			// objects form eliminated groups
	bool eliminated [MAXOBJECTS];	// marker-array for eliminated groups

	//cerr << "mutation " << idtag << endl;

	for (i = 0; i < nrofgroups; i++)
			eliminated[i] = false;

	// pick colors for elimination
	for (i = 0; i < nrofgroups; i++)
		if ((rnd.asLong () % 100) <= (allelemutationprob * 100))
		{
			eliminated[groups[i]] = true;
			groups[i] = ELIMINATED;
		}

	// Pick all colors that were in an eliminated group and mark
	// them uncolored
	for (i = 0; i < nrofobjects; i++)
	{
		if (eliminated[objects[i]])
		{
			objects[i] = UNCOLORED;
			savedobjects.Push (i);
		}
	}

	// Remove holes in group part created by elimination
	CompactGroupPart ();

	// Reinsert uncolored objects with ColorObject function
	while (!savedobjects.Empty ())
		ColorObject (savedobjects.Pop ());

	// Reevaluate geno
	Evaluate ();


} // Mutation ()


void GenotypeC::Inversion ()
// Apply inversion to the geno by selecting two points in the
// group-part and reversing the sequence of groups between
// these points.
{
	int i, j;
	int ip1, ip2;		// inversion points

	//cerr << "inversion " << idtag << endl;

	// Pick two points
	ip1 = rnd.asLong () % nrofgroups;
	ip2 = rnd.asLong () % nrofgroups;
	if (ip2 < ip1)
	{
		i = ip1;
		ip1 = ip2;
		ip2 = i;
	}

	// Invert string between the two points
	for (i = 0; i < (ip2 - ip1 + 1) / 2; i++)
	{
		j = groups[i + ip1];
		groups[i + ip1] = groups[ip2 - i];
		groups[ip2 - i] = j;
	}

	Evaluate ();

} // Inversion ()


void GenotypeC::Crossover (GenotypeC & otherparent, GenotypeC & child1, GenotypeC & child2)
// Do a crossover operation between the geno and another parent,
// producing two children. Using the procedure described by
// E.Falkenhauer and the ColorObject function to reinsert objects.
{
	int i, j;
	int p1cp1, p1cp2;				// crossover-points for parent P1
	int p2cp1, p2cp2;				// crossover-points for parent P2
	bool eliminated1 [MAXOBJECTS];	// marker-array for elimination process P1
	bool eliminated2 [MAXOBJECTS];	// marker-array for elimination process P2
	StackC objects1;				// holds objects from eliminated groups P1
	StackC objects2;				// holds objects from eliminated groups P2

	for (i = 0; i < nrofgroups; i++)
	{
		eliminated1[i] = false;
		eliminated2[i] = false;
	}

	//cerr << "crossover " << idtag << " " << otherparent.idtag << " " << child1.idtag << " " << child2.idtag << endl;

	// Choose crossover points
	p1cp1 = rnd.asLong () % nrofgroups;
	p1cp2 = rnd.asLong () % nrofgroups;
	if (p1cp2 < p1cp1)
	{
		i = p1cp1;
		p1cp1 = p1cp2;
		p1cp2 = i;
	}
	p2cp1 = rnd.asLong () % otherparent.nrofgroups;
	p2cp2 = rnd.asLong () % otherparent.nrofgroups;
	if (p2cp2 < p2cp1)
	{
		i = p2cp1;
		p2cp1 = p2cp2;
		p2cp2 = i;
	}

	// Copy parents to children
	Copy (child1);
	otherparent.Copy (child2);

	// Mark all groups losing at least one object with ELIMINATED
	for (i = 0; i < nrofobjects; i++)			// look at all objects
		for (j = p1cp1; j <= p1cp2; j++)		// walk through crossing-section
			if (objects[i] == groups[j])		// object is in injected group
			{
				eliminated2[child2.objects[i]] = true;		// mark group affected
				child2.objects[i] = groups[j] + child2.nrofgroups;	// new color
			}
	for (i = 0; i < otherparent.nrofobjects; i++)
		for (j = p2cp1; j <= p2cp2; j++)
			if (otherparent.objects[i] == otherparent.groups[j])
			{
				eliminated1[child1.objects[i]] = true;
				child1.objects[i] = otherparent.groups[j] + child1.nrofgroups;
			}

	// Eliminate effected groups
	for (i = 0; i < child1.nrofgroups; i++)
		if (eliminated1[child1.groups[i]])
				child1.groups[i] = ELIMINATED;

	for (i = 0; i < child2.nrofgroups; i++)
		if (eliminated2[child2.groups[i]])
				child2.groups[i] = ELIMINATED;

	// Collect objects member of an eliminated group
	for (i = 0; i < child2.nrofobjects; i++)
		if ((child2.objects[i] < child2.nrofgroups) && (eliminated2[child2.objects[i]]))
		{
			child2.objects[i] = UNCOLORED;
			objects2.Push (i);
		}
	for (i = 0; i < child1.nrofobjects; i++)
		if ((child1.objects[i] < child1.nrofgroups) && (eliminated1[child1.objects[i]]))
		{
			child1.objects[i] = UNCOLORED;
			objects1.Push (i);
		}

	// Inject group-part from parents into children
	child2.InsertGroup (groups, p1cp1, p1cp2, p2cp1);
	child1.InsertGroup (otherparent.groups, p2cp1, p2cp2, p1cp1);

	// Remove holes in group-array created by the elimination process
	child2.CompactGroupPart ();
	child1.CompactGroupPart ();

	// Reinsert objects from eliminted groups
	while (!objects2.Empty ())
		child2.ColorObject (objects2.Pop ());
	while (!objects1.Empty ())
		child1.ColorObject (objects1.Pop ());

	// Compute fitness of children
	child2.Evaluate ();
	child1.Evaluate ();

} // Crossover ()

void GenotypeC::Print (ofstream & output)
// Print out the geno's genes and it's fitness.
{
	int i;

	output << "(" << idtag << ") ";

	// Print out objects
	for (i = 0; i < nrofobjects; i++)
		if (objects[i] == UNCOLORED)
			output << "X ";
		else
			output << objects[i] << " ";

	output << " : ";

	// Print out groups
	for (i = 0; i < nrofgroups; i++)
		if (groups[i] == ELIMINATED)
			output << "X ";
		else
			output << groups[i] << " ";

	output << ", ";

	// Print out fitness
	output << "fitness: " << fitness << endl;

} // GenotypeC::Print ()



void GenotypeC::Print ()
// Print out the geno's genes and it's fitness.
{
	int i;

	cerr << "(" << idtag << ") ";

	// Print out objects
	for (i = 0; i < nrofobjects; i++)
		if (objects[i] == UNCOLORED)
			cerr << "X ";
		else
			cerr << objects[i] << " ";

	cerr << " : ";

	// Print out groups
	for (i = 0; i < nrofgroups; i++)
		if (groups[i] == ELIMINATED)
			cerr << "X ";
		else
			cerr << groups[i] << " ";

	cerr << ", ";

	// Print out fitness
	cerr << "fitness: " << fitness << endl;

} // GenotypeC::Print ()


double GenotypeC::GetFitness ()
{
	return (fitness);

} // GetFitness ()


void GenotypeC::Copy (GenotypeC & child)
// Copy the geno to the supplied recipiant.
{
	int i;

	for (i = 0; i < nrofobjects; i++)
		child.objects[i] = objects[i];
	for (i = 0; i < nrofgroups; i++)
		child.groups[i] = groups[i];

	child.nrofobjects = nrofobjects;
	child.nrofgroups = nrofgroups;
	child.fitness = fitness;

} // GenotypeC::Copy ()



double GenotypeC::GetColorsUsed ()
{
	return (nrofgroups);

} // GetColorsUsed ()


ErrorsT GenotypeC::IsValid (int & object)
// Check if all objects in the geno do not violate a solution, and
// check if there are no duplicate colors.
{
	int i = 0;
	int colors[MAXOBJECTS];			// number of times a groupnumber is used

	// Check duplicate groups
	for (i = 0; i < nrofgroups; i++)
		colors[i] = 0;

	for (i = 0; i < nrofgroups; i++)
		colors[groups[i]]++;

	for (i = 0; i < nrofgroups; i++)
		if (colors[i] != 1)
			return (duplicatecolor);

	// Check constraints of objects
	i = 0;
	while ((i < nrofobjects) && (ViolatedConstraints (i) == 0) && (objects[i] < nrofgroups))
		i++;

	// Return corresponding error
	if (i < nrofobjects)
	{
		if (ViolatedConstraints (i) != 0)
		{
			object = i;
			return (badcoloring);
		}
		if (objects[i] >= nrofgroups)
		{
			object = i;
			return (illegalcolorused);
		}
	}
	return (none);

} // IsValid ()


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


int GenotypeC::ViolatedConstraints (int object)
// Calculate the number of constraints an object violates.
{
	int violations;
	Link * ptr;

	// A constraint is violated when the node is connected to
	// a node with the same color
	violations = 0;
	for (ptr = problem.gradjl[object]; ptr; ptr = ptr->nextptr)
		if (objects[object] == objects[ptr->nodenr])
			violations++;
	
	return (violations);

} // ViolatedConstraints ()


void GenotypeC::ColorObject (int object)
// Color an object using the algoritm selected.
{
	switch (coloringused)
	{
		case firstfit:
			ColorObject_FirstFit (object);
			break;
		// These two have to be implemented
		/* 
		case smallfirst:
			ColorObject_OrderedColoring (object);
			break;
		case largefirst:
			ColorObject_OrderedColoring (object);
			break;
		*/
		default:
			cerr << "Error: No coloring algorithm defined";
			exit (2);
	}

} // ColorObject ()


/* NOT USED YET
void GenotypeC::ColorObject_OrderedColoring (int object)
// Colors an object by using some ordering heurstic, if no color
// is available it creates a new group and uses this to color
// the object with.
{
	int i = 0, j = 0, max;
	int objectsingroup[MAXOBJECTS];		// number of objects in each group
	int orderedcolors[MAXOBJECTS];		// number of objects in each group

	for (i = 0; i <= nrofgroups; i++)
		orderedcolors[i] = 0;
	
	for (i = 0; i <= nrofobjects; i++)
		objectsingroup[objects[i]]++;

	// Order colors
	for (i = 0; i < nrofgroups; i++)
	{
		max = 0;
		for (j = 0; j < nrofgroups; j++)
			if (coloringused == largefirst)
				if (objectsingroup[max] < objectsingroup[j])
					max = j;
			else
				if (objectsingroup[max] > objectsingroup[j])
					max = j;
		orderedcolors[i] = max;
		objectsingroup[max] = -1;
	}

	// Orderer coloring
	i = 0;
	objects[object] = orderedcolors[0];
	while (ViolatedConstraints (object) > 0)
	{
		i++;
		if (i < nrofgroups)
			objects[object] = orderedcolors[i];
		else
			objects[object] = i;
	}

	// New color used, update number of groups and
	// add a new color to the group-part
	if (i + 1 > nrofgroups)
	{
		nrofgroups = i + 1;
		groups[nrofgroups - 1] = nrofgroups - 1;
	}

} // ColorObject_OrderedColoring ()
*/


void GenotypeC::ColorObject_FirstFit (int object)
// Colors an object by using a first fit heurist, if no color
// is available it creates a new group and uses this to color
// the object with.
{
	int i = 0;

	// First Fit Coloring
	objects[object] = 0;
	while (ViolatedConstraints (object) > 0)
	{
		i++;
		objects[object] = i;
	}

	// New color used, update number of groups and
	// add a new color to the group-part
	if (i + 1 > nrofgroups)
	{
		nrofgroups = i + 1;
		groups[nrofgroups - 1] = nrofgroups - 1;
	}

} // ColorObject_FirstFit ()


void GenotypeC::InsertGroup (int parentgroups [], int cp1, int cp2, int position)
// Given the group-part and the crossing-points of another geno,
// this method inserts the groups between these points on the
// given position.
{
	int i;

	// Make room for to-be-inserted-groups
	for (i = nrofgroups; i > position; i--)
		groups[i + (cp2 - cp1)] = groups[i - 1];

	// Inject groups in the gene
	for (i = cp1; i <= cp2; i++)
		groups[i + position - cp1] = parentgroups[i] + nrofgroups;

	// Update number of groups
	nrofgroups = nrofgroups + (cp2 - cp1) + 1;

} // InsertGroup ()


void GenotypeC::CompactGroupPart ()
// After elimination of groups from the group-part of the gene,
// this method removes the holes created by elimination and
// renumbers the remaining groups to create a numbering between
// 0 and nrofgroups - 1.
{
	int i, j;
	bool found;		// used in finding each number 0...(nrfgroups-1)
	int max;		// maximum number currently used in group-part

	// Remove eliminated groups
	i = 0;
	while (i < nrofgroups)
		if (groups[i] == ELIMINATED)
		{
			for (j = i; j < nrofgroups - 1; j++)
				groups[j] = groups[j + 1];
			nrofgroups--;
		}
		else
			i++;

	// Renumber to get a nice permutation of 0,1,2,3... again
	i = 0;
	while (i < nrofgroups)
	{
		j = 0;
		found = false;
		max = 0;
		// Look for the current (i) number
		while ((j < nrofgroups) && (!found))
		{
			if (groups[j] > groups[max])
				max = j;
			if (groups[j] == i)
				found = true;
			else
				j++;
		}

		// Number (i) not found, give new number to largest number
		if (!found)
		{
			for (j = 0; j < nrofobjects; j++)
				if (objects[j] == groups[max])
					objects[j] = i;
			groups[max] = i;
		}
		i++;
	}
} // CompactGroup ()


// eof genotype.cc