deme.cc

genetic programming in C++ Adam Fraser University Of Salford, Salford, M5 4WT, United Kingdom

// deme.cpp

//--------------------------------------------------------------------------
// This code is a component of Genetic Programming in C++ (Version 0.40)
// Copyright Adam P. Fraser, 1993,1994
// This code is released for non-commercial use only.
// For comments, improvements, additions (or even money !?) contact:
// Adam Fraser, Postgraduate Section, Dept of Elec & Elec Eng,
// Maxwell Building, University Of Salford, Salford, M5 4WT, United Kingdom.
// Internet: [e-mail]
// Tel: (UK) 061 745 5000 x3633
// Fax: (UK) 061 745 5999
//--------------------------------------------------------------------------


// by Adam P. Fraser

// What is demetic grouping ?

// Don't you read the gp mailing list this comes up about every two weeks.

// The total population undergoing the evolutionary process is subdivided into a number
// of groups (demes) which are unable to interact with other groups except through the
// use of migratory agents which are selected using a probabilistic measure.  This
// subdivision of the population allows the demes to evolve along separate paths
//  without this path becoming tightly focused upon any particular area within the 
// global search space


// Huh, Demes what are they good for, say it again! [ with apologies to Bruce Springsteen ]

// Hmmmm, damn good question it probably needs a good answer but I am not going to try.
// Demes have been used to halt premature convergence of the population as they are
// unlikely to find the same sub optimal structure.  Demes are also good when considering
// the relatedness of structures (my particular area of study so don't get me started on
// it or you will never shut me up), they could also be useful in using muliple population
// by considering them as tribes and electing tribal leaders who compete for the deme.

// From biology there are two theories Fisher and Wright to paraphrase.
//  Fisher feels that everything should be able to reproduce with every other member
//  of the population ( a bit like late 1960's but without the rather strange halluciogenics )
//  Wright thinks populations get forced into groups due to enviromental constraints such
//  as two tortoises ten miles apart.
// Anyway do what you will here is the code.


// include gpmain ( pop, gpv, gp and gene )
#include "gpmain.hpp"
// for random number generator
#include "gprand.hpp"


// MAIN CODE...


// Demetic grouping selection in which grouping is  carried out through spatial groups
// on a ONE dimensional torus ( therefore a hoop ). Sub populations are placed within
// a valley and only random wanderers can get out. These must therefore be specifically
// found and moved around etc....
// apf 25 February 1994

#define DemesSize 10    // size of demetic grouping
#define AWanderer 10  // this is set as 1 in (AWanderer) chance of turning into a
											// wanderer who escapes their valley

// NOTE: This is exceptionally long and complicated code and hence I despise it for all
// it's worth.  I could have subdivided the code into smaller functional blocks but as demetic
// constraints mean that most of the code is spent setting up the system it seemed better to
// include it all in one block.. if you think of a better way please e-mail, snail whatever.
// I hate this way of doing it.....

// NOTE2: If your initial population gets the same value there will be no crossover !!!!!

// Select parents and child  for generate.cc
// Result is that best and second best of a particular deme are exchanged with the worst
// of that deme.  This is all deterministic rather than probablistic.. arguments on a postcard!
GP** Population::SelectParentsAndChild()
{
	GP *ppgpReturn[3], *pgp = pgpHeader, *pgpSelect = Select(); // randomly select some gp

// Initialise the return values to their default == the selected gene....
  ppgpReturn[0] = pgpSelect;
	ppgpReturn[1] = pgpSelect;
  ppgpReturn[2] = pgpSelect;

// move the start of the deme to the correct section of the population..............
	while ( (pgp + DemesSize) < pgpSelect ) pgp += DemesSize;

// Check whether you wish to make this a wanderer and move the start position accordingly
	if (!(gp_rand()%AWanderer))   
	{
// left or right on 1-d scape 0 = left, 1 = right
		if ( gp_rand() % 2)   
		{
// if you are at edge of population moving away loop back to start
			if ( (pgp + DemesSize) >= (pgpHeader+PopulationSize) )  pgp = pgpHeader;
// else add another deme
			else                                                                                                                                                                                                            pgp += DemesSize;
		}
		else
		{
// if you are at start of population moving nearer go to end 
			if  (pgp == pgpHeader ) pgp = (pgpHeader + PopulationSize) - DemesSize;
// else minus another deme
			else                                                                    pgp -= DemesSize;
		}
	}

// Check through the whole deme checking for worst and best gps...................
  if ( (pgp + DemesSize) < (pgpHeader + PopulationSize) )
  {
// below is the normal case .......
		for ( unsigned char ch = 0; ch < DemesSize; ch++, pgp++ )
		{
// if this fitness is greater than best fitness so far, swap
			if (pgp->iFitness > ppgpReturn[0]->iFitness )
			{
// if best is changing and old value is greater than second best change second best...
	if ( ppgpReturn[0]->iFitness > ppgpReturn[1]->iFitness ) ppgpReturn[1] = ppgpReturn[0];
				ppgpReturn[0] = pgp;
      }

// if the fitness is greater than the second best fitness and it has not already been set
// to the absolute best take this value
			if ( (pgp->iFitness > ppgpReturn[1]->iFitness) && ( ppgpReturn[0] != pgp ) )
				ppgpReturn[1] = pgp;

// if this fitness is worse than worst fitness so far, swap.
			if (pgp->iFitness < ppgpReturn[2]->iFitness) ppgpReturn[2] = pgp;
		}
	}
  else
  {
//exceptional case is when there is a potential to overrun population....
	for ( unsigned char ch = 0; ch < DemesSize; ch++, pgp++ )
		{
//loop back around to the start of the hoop if there is a problem
			if ( pgp == (pgpHeader + PopulationSize) ) pgp = pgpHeader;  //loop back around

// if this fitness is greater than best fitness so far, swap
			if (pgp->iFitness > ppgpReturn[0]->iFitness )
			{
// if best is changing and old value is greater than second best change second best...
	if ( ppgpReturn[0]->iFitness > ppgpReturn[1]->iFitness ) ppgpReturn[1] = ppgpReturn[0];
				ppgpReturn[0] = pgp;
      }

// if the fitness is greater than the second best fitness and it has not already been set
// to the absolute best take this value
			if ( (pgp->iFitness > ppgpReturn[1]->iFitness) && ( ppgpReturn[0] != pgp ) )
				ppgpReturn[1] = pgp;

// if this fitness is worse than worst fitness so far, swap.
			if (pgp->iFitness < ppgpReturn[2]->iFitness) ppgpReturn[2] = pgp;
		}
  }

// return 3 member array
	return ppgpReturn;
}