Dr. Mark Humphrys School of Computing. Dublin City University. My big idea: Ancient Brain Search:

# Basic genetic algorithm

```
// generic GA
// single linear binary chromosome
// interpretation of it is up to the program - no interpretation is made here

// I thought of randomising all objects in their constructors,
// but this is probably unnecessary half the time
// (and could even perhaps lead to infinite loops).
// Instead, I have a hierarchy of randomising,
// so calling the randomise() function on a Population
// randomises all the individuals within it, etc.

const int l = 30;		// length of chromosome
const int n = 50;		// size of population (should be even)
const double pc = 0.8;		// probability of crossover
const double pm = 0.005;	// probability of mutation

```

# A Chromosome:

```
typedef Boolean Allele;		// alphabet is 0,1 (k=2)

// my own array, with 1..n indexing:

class AlleleArray
{
public:
Allele secret[l];
Allele& operator[] ( int i ) { return secret[i-1]; }
// return reference because x[] might appear on lhs of equation
};

class Chromosome : public AlleleArray
{
public:
Chromosome& operator= ( Chromosome& c )
{
for ( int i=1; i<=l; i++ )
{ (*this)[i] = c[i]; }
return *this;
}

randomise()
{
for ( int i=1; i<=l; i++ )
{ (*this)[i] = r.flip(0.5); }	// a fair toss
}

friend ostream& operator<< ( ostream& stream, Chromosome& c)
{
for ( int i=1; i<=l; i++ )
{
Boolean b = c[i];
stream << b;
}
return stream;
}
};

```

# The main, problem-specific, forward declaration:

```
double positiveFitness ( Chromosome );

// how fit is this Chromosome?
// the user application must return a positive fitness

```

# An Individual:

```
class Individual
{
public:
Chromosome 	a;		// a[1] .. a[l]
int 		parent1;
int		parent2;
int 		crossoversite;
double 	fitness;

updateFitness()			// new chromosome..
{
fitness = positiveFitness(a);		// ask the application to rate it
if ( fitness < 0 )
{
// return error
}
}

Individual& operator= ( const Individual& x )
{
a = x.a;
parent1 = x.parent1;
parent2 = x.parent2;
crossoversite = x.crossoversite;
updateFitness();
return *this;
}

makeMe ( Chromosome c, int p1, int p2, int x )
{
a = c;
parent1 = p1;
parent2 = p2;
crossoversite = x;
updateFitness();
}

randomise()
{
a.randomise();
parent1 = 0;
parent2 = 0;
crossoversite = 0;
updateFitness();
}

friend ostream& operator<< ( ostream& stream, Individual& x)
{
sprintf ( buf, "(%3d,%3d)", x.parent1, x.parent2 );
stream << buf;
if ( x.crossoversite == l )
sprintf ( buf, ",  -   " );		// there was no crossover
else
sprintf ( buf, ", %3d  ", x.crossoversite );
stream << buf;
stream << x.a;
sprintf ( buf, " %8.3f", x.fitness );
stream << buf;
return stream;
}
};

```

# A Population:

```
class IndividualArray
{
public:
Individual secret[n];
Individual& operator[] ( int i ) { return secret[i-1]; }
};

class Population : public IndividualArray
{
public:
Population& operator= ( Population& p )
{
for ( int i=1; i<=n; i++ )
{ (*this)[i] = p[i]; }
return *this;
}

randomise()
{
for ( int i=1; i<=n; i++ )
{ (*this)[i].randomise(); }
}

Population()
{
if ( (n % 2) != 0 )
{
// return error
}
}
};

class World
{
public:
Population 	A;			// A[1] .. A[n]

// these statistics calculated by runStatistics:
Individual	best;
double 	worstFitness, averageFitness, sumFitness;

randomise() { A.randomise(); runStatistics(); }

int 		select();
crossover ( int, int );	// deposits output in:
Individual 	child1,child2;
Allele 	mutate ( Allele );
};

```

# Select a random individual for reproduction. Fittest most probable to be selected:

This uses simple summation of fitness (not Boltzmann), plus spin the weighted wheel.

```
int World :: select()
// actually called multiple times
// each time just selects one A[i] for reproduction
{
double point = r.prob() * sumFitness;
// random point between 0 and sigma fitnesses ('spin the wheel')
// find the individual intersecting this point
double partial = 0.0;
int i = 0;
while ( (partial<=point) && (i < n) )
{
i++;
partial = partial + A[i].fitness;
}
// the loop has stopped because either partial has just crossed the line, or i=n.
// either way:
return(i);
}

```

# Mix up the 2 parents' genes:

```
World :: crossover ( int parent1, int parent2 )
// writes output to child1,child2
{
// first build the chromosomes..
Chromosome p1 = A[parent1].a;
Chromosome p2 = A[parent2].a;
Chromosome c1;
Chromosome c2;
int site,i;

if ( r.flip(pc) ) 		// flip coin weighted with pc
site = r.restricted(1,l-1);	// crossover - random cut, from after 1 to after l-1
else
site = l;			// no crossover - 'cut' after l

// the cut comes after site,
// so elements 1 to site go to one side, site+1 to l into other:
for ( i=1; i<=site; i++ )
{
c1[i] = mutate(p1[i]);
c2[i] = mutate(p2[i]);
}
for ( i=site+1; i<=l; i++ )
{
c1[i] = mutate(p2[i]);
c2[i] = mutate(p1[i]);
}

// then build the individuals..
child1.makeMe ( c1, parent1, parent2, site );
child2.makeMe ( c2, parent1, parent2, site );
}

```

# Certain probability of mutation:

```
Allele World :: mutate ( Allele a )
// mutate allele a with probability pm
{
if ( r.flip(pm) )
return (!a);
else
return (a);
}

```

# Build a new population from the current one:

```
World :: next()
// replace population A
{
runStatistics(); 	// just for safety, make sure we are up to date with A
Population temp;
for ( int i=1; i<=n-1; i=i+2 )		// build in pairs - temp(1,2), temp(3,4), .. temp(n-1,n)
{
crossover ( select(), select() );	// select two mates and build 2 new children
temp[i] = child1;
temp[i+1] = child2;
}
// now we are finished with the old A. replace it:
A = temp;
}

World :: runStatistics()
// update various statistics about myself
{
best 		= A[1];
worstFitness 	= A[1].fitness;
sumFitness 	= A[1].fitness;
for ( int i=2; i<=n; i++ )
{
double f = A[i].fitness;
sumFitness = sumFitness + f;
if ( f < worstFitness ) worstFitness = f;
if ( f > best.fitness ) best = A[i];
}
// these all now fully calculated.
// all that remains is:
averageFitness = sumFitness / n;
}

// the GA library's statistical reports are only concerned with the GA internals.
// they only deal in concepts of 'string' and 'fitness'
// they have no idea why that string has that fitness,
// or what it means:

World :: detailedReport ( int t, ostream& stream )
{
runStatistics();
stream << "\n\n\n";
stream << "t=" << t << "\n";
stream << "  #  parents,xsite                          string  fitness \n";
stream << "------------------------------------------------------------\n";
for ( int i=1; i<=n; i++ )
{
sprintf ( buf, "%3d ", i );
stream << buf << A[i];
if ( A[i].fitness > averageFitness )
stream << " +";
stream << "\n";
}
stream << "------------------------------------------------------------\n";
}

World :: summaryReport ( int t, ostream& stream )
// (the outside world tells me what time (i.e. what generation) it is)
{
runStatistics();
sprintf ( buf, "t=%-3d worst=%0.3f average=%0.3f best=( ",
t, worstFitness, averageFitness );
stream << buf;
stream << best.a;
sprintf ( buf, " , %0.3f ) \n",
best.fitness );
stream << buf;
}

```
```
```

Feeds      w2mind.org      ancientbrain.com

On the Internet since 1987.