Genetic Algorithm - A 'Walt Disney' Introduction

Introduction

Genetic Algorithms(G.A.) are a way of solving problems by mimicking the same processes mother nature uses. They use the same combination of selection, recombination and mutation to evolve a solution to a problem.

G.A falls in the family of Heuristics (O my God... another big word… :D). Heuristics differ from “traditional” algorithms in that you don’t specify how exactly to derive the answer, rather you specify where to search for it. Here is an illustration/explanation by Faisal Sikder:

Here is an algorithm for driving to someone’s house:

"Take Highway 167 south to Puyallup. Take the South Hill Mall exit and drive 4.5 miles up the hill. Turn right at the light by the grocery store, and then take the first left. Turn into the driveway of the large tan house on the left, at 714 North Cedar."

Here’s a heuristic for getting to someone’s house:

"Find the last letter we mailed you. Drive to the town in the return address. When you get to town, ask someone where our house is. Everyone knows us—someone will be glad to help you. If you can’t find anyone, call us from a public phone, and we’ll come get you!"

G.A is rather polygamous in that though it belongs to the family of Heuristics, it also belongs to the family of evolutionary computing. Just as the Chinese martial art family uses tai chi to solve their problem, children of evolutionary computing use the concept of evolution to solve theirs. The children of Evolutionary Computing are Genetic Algorithm, Evolutionary Strategies, Evolutionary Programming and Genetic Programming.

Years back during my pre-med program, I was told about the presumed story of the origin of sickle cell anemia. Was a rather boring story so I made a “Walt Disney Animation” of mine:

Centuries ago, everyone’s red blood cells were round - pretty round girls. Then came these villains – ugly guys - causing problems for the neighborhood by attacking and killing these cute girls. They attacked and killed lots of the girls. At the height of it, a sorcerer cast a spell on parents. The change resulted to every female baby becoming ugly beings with an S-like shape. When the villains (boys) came to attack the girls, they got so scared and ran away. Because of this, they stopped attacking the community.

My brief Oscar winning story summaries the basic concept of genetic algorithm.
From the story, we realized the given metaphors:

Problem: Villains coming to attack the pretty girls in the village.
Mutation: Changes of the offspring as a result of the sorcerer's spell.

Other metaphors not directly insinuated from the story are selection and recombination.

Reproducing an offspring entails mating between 2 individuals (in humans atleast). Selection describes the scenario of who mates with whom. Offspring tend to have properties of both parents. In other words, the genes (what makes up the properties/characteristics of an individual) of an offspring is as a result of the recombination of the genes of the parents. For example:

Gene of Mom: 10001001110010111(Pretty and short :D)
Gene of Dad: 11010001001010011 (Ugly and tall :D) 
Gene of Offspring after recombination: 10000001001010111 (Pretty and tall) :D:D:D

Now let’s put this in the other they occurred in solving the problem faced by the community in our award winning story:

1. Population of people (Community)
2. Problem in community?
3. Yes: (Community facing villain attacks)

1. Select Parents to mate (Selection)
2. Mix (recombine) genes to form new offspring having both parents traits (Recombination)
3. If problem won’t make the current generation survive, tweak gene of offspring to allow him adapt (Mutate if need arises – make the female offspring s-like to scare villains off)
4. Offspring add to population making a new generation. If problem still persist, start over from 3a. If problem is solved (no more villains) go to 4.

4. No: (No problem in community/villains varnished) – Community lives happily ever after, story ends.

That is the outline of basic genetic algorithm! Simple huh?

Okay let’s solve a simple problem using this technique of evolutionary algorithm. We shall be solving a simple problem called maximizing 1’s. The aim of the program will be to maximize the number of 1’s in a given bit string (0’s and 1’s).

First let's solve this using "traditional" algorithm written in C++.

#include <iostream>
#include <time.h>
#define  SIZE 9
using namespace std;
int main()
  {
         int numArray[SIZE] ;
 
  srand(time(0));
       for(int i=0 ; i < SIZE ; i++)
                numArray[i] = rand()%2;
 
         for(int i=0 ; i < SIZE ; i++)
                if(numArray[i]==0)
                       numArray[i] = 1;
 
         for(int i=0 ; i < SIZE ; i++)
                cout<< numArray[i];
       return 0;
  }

(If you feel there is or are needs to write classes and objects for it, well, go ahead.)

Next, we will apply a simple evolutionary technique to give you a glimpse of the underlying concept of evolution algorithm. Examples in further series of this tutorial will be solved using genetic algorithm.

First we model "the community". Let’s call the random bit string a member of the population, probably a female. So we have:

int female[SIZE];

Next, we fill it with random bits as the problem entails.

for(int i=0 ; i < SIZE ; i++)
                female[i] =  rand()%2;

Since the female will mate with a male, let’s model the male character.

We might decide to generate a random number for it too but I’ll save myself the extra lines of code and make it a mix of 0’s and 1’s.

int male[SIZE] = {1,0,1,0,1,0,1,0,1};

With that done, we go to the next step in the outline – Is there a Problem in the community?

In our case, we check if it's all one, if its "fit" to eradicate the problem. Checking the current state of the community is termed calculating fitness. This is how we monitor the progress of each generation.

So this is what we’ll do. We’ll count the number of 1’s in the bit string. If its 9, Voila! Case solved. If its not, we keep breeding (Mating – Selection and Recombination – see below) hoping the next generation will be “fitter”.

I think it is rather easier to handle numbers between 0 and 1 than 0 and 9 so please forgive me for scaling the fitness as such. This is what we’ll do, we will count the numbers of 1’s and divide it by 9! That way, we’ll would normalize the number between 0 and 1. For example:

Number of 1’s = 0; fitness = 0/9 = 0;
Number of 1’s = 3; fitness = 3/9 = 0.33
Number of 1’s = 6; fitness = 6/9 = 0.67
Number of 1’s = 9; fitness = 9/9 = 1 (Yes!)

Enough said, let's write the function for it.

double  calcFitness (int *arr)
  {
         int cnt =  0;
       double  fit;
              for(int i = 0; i < SIZE; i++)
                       if(*(arr+i)  == 1)
                             cnt++; //count 1's
              fit = (double)  cnt/SIZE; //divide by 9 to normalize between 0 and 1.
              cout<<"fit = "<<fit<<endl;  //display fitness value.
       return  fit;}

Next we look at mating which we said involves selection and recombination of genes (parent’s properties).

Let’s create a function for it.

void  mate(int *female, int  *male, int *offspring)
  {
         static int mateCnt=0; //to count matings/generations

         int num;
       srand(time(0));
       //random recombination of genes
for(int i = 0 ; i  < SIZE ; i++ )
         {
              num = rand() % SIZE; //select a  random number from 0 to 8.
       //if random number is greater than i, take the bit in that location of the female
         //if not take from that of the male
              if(i  >= num)
                       *(offspring + i) = *(female  + num);
                else
                       *(offspring + i) = *(male +  num);
         }
       cout<<"After  mating: "<< mateCnt << endl ;
       cout<<"\n  Female: "<<endl;

                for(int i = 0; i < SIZE; i++)
                {
                       cout<<female[i];
                }

         cout<<"\n  Male: "<<endl;
              for(int i = 0; i < SIZE; i++)
                {
                       cout<<male[i];
                }
       cout<<"\n";
       mateCnt++; //Keep record of matings (for no just reason! :P)}

Phew, gone a long way! Next on the outline is mutation. Remember the sorcerer from the story that cast a spell when things got to its height? This is where she comes in.
If in the random process of recombination of genes, we were left with having:

Male: 000000000
Female: 000000000

Then now we have a problem. No matter how many times we let them mate, we will always result in an offspring with all zeros. In other words, we are stocked.

This in our own problem is the height of things where the sorcerer comes in.

If it ever gets to the stage, the sorcerer (which happens to be our Mutation function) would cast a spell that will convert one of the zeros in the parents to 1, thereby giving a chance of producing a sterile offspring.

For example,
Before mutation, bit string – 000000000
After mutation, bit string – 001000000 or 100000000 or 000000001 …

So let’s model our sorcerer!

void  mutate (int *arr)
  {
         srand(time(0));
       int i =  rand()%8; //random bit to mutate.

         *(arr+i)=1;

         cout<<"After  Mutation ==> ";
       for(int i = 0; i < SIZE; i++)
                {
                       cout<<*(arr+i);
                }
              cout<<"\n";
  }

Now the last part in our outline – 3d (offspring adds to/make new generation).

Let's call the function next generation.

void nextGeneration (int *male, int *female,  int *offspring)
  {
   //Hmm… Lets  randomly decide the sex of the child :D:D:D
  //We get a random number from 1 to 100…
  //If number is even, child is male; if odd, child is  female.. Fair enough? :D:D:D:D:D
srand(time(NULL));
int fate = rand()%100 + 1 ;
for(int i=0;  i<SIZE; i++)
         {
                if(fate%2 == 0)
                *(male + i) = *(offspring + i);

                else
                *(female + i) = *(offspring + i);
       }}

Yippy! We’ve finally modeled every piece in the outline based on the problem at hand. Now it’s time to fit these pieces together.

The full program is as follows:

#include <iostream>
#include <time.h>
#define SIZE 9
using namespace std;
#include <iostream>
  #include <time.h>
#define SIZE 9
using namespace std;
double calcFitness (int *arr)
  {
  int cnt = 0;
  double fit;
for(int i = 0; i < SIZE; i++)
  if(*(arr+i) == 1)
  cnt++; //count 1's
fit = (double) cnt/SIZE; //divide by 9 to normalize between 0 and 1.
cout<<"fitness = "<<fit<<endl; //display fitness value.
return fit;
}
void mutate (int *arr)
  {
  srand(time(0));
int i = rand()%8; //random string bit to mutate.
*(arr+i) = 1;
cout<<"After Mutation ==> ";
for(int i = 0; i < SIZE; i++)
  {
  cout<<*(arr+i);
  }
cout<<"\n";
}
void mate(int *male, int *female, int *offspring)
  {
int num;
srand(time(0));
//random recombination of genes
for(int i = 0 ; i < SIZE ; i++ )
  {
num = rand() % SIZE; //select a random number from 0 to 8.
//if random number is greater than i, take the bit in that location of the female
  //if not take from that of the male
if(i >= num)
  *(offspring + i) = *(female + num);
  else
  *(offspring + i) = *(male + num);
  }
cout<<"\n Male: "<<endl;
for(int i = 0; i < SIZE; i++)
  {
  cout<<male[i];
  }
cout<<"\n female: "<<endl;
for(int i = 0; i < SIZE; i++)
  {
  cout<<female[i];
  }
cout<<"\n";
}
void nextGeneration (int *male, int *female, int *offspring)
  {
  //Hmm… Lets randomly decide the sex of the child :D:D:D
  //We get a random number from 1 to 100…
  //If number is even, child is male; if odd, child is female.. Fair enough? :D:D:D:D:D
srand(time(NULL));
int fate = rand()%100 + 1 ;
for(int i=0; i<SIZE; i++)
  {
  if(fate%2 == 0)
  *(male + i) = *(offspring + i);
else
  *(female + i) = *(offspring + i);
}
}

void main()
  {
int maleParent[SIZE] = {1,0,1,0,1,0,1,0,1};
  int femaleParent[SIZE];
  int offspring[SIZE];
  double offspringFitness;
  int cnt = 1; //count generation
for(int i = 0; i < SIZE; i++)
  {
  femaleParent[i] = rand()%2;
  }
mate(maleParent,femaleParent,offspring);
offspringFitness = calcFitness(offspring);
  //loop for environmental selection, mutation and fitness
while(offspringFitness != 1)
  {
  //mutate if offspring fitness is low
  if( offspringFitness < 0.15){
  mutate(maleParent);
  mutate(femaleParent);
  }
nextGeneration(maleParent,femaleParent,offspring);
//Mating / Recombination
  mate(maleParent,femaleParent,offspring);
/* No need basically for environmental selection since only one form (gene)of 
   both parents exists. */
cout<<"Offspring "<<cnt<<": ";
for(int i = 0; i < SIZE; i++)
  {
  cout<<offspring[i];
  }
cout<<"\n";
offspringFitness = calcFitness(offspring);
cout<<"\n";
cnt++;
  }
cout<<endl;  }

Points of Interest

Since G.A. is not language specific, I have written the codes in a "c-like" fashion (not using classes, inheritance and othe OOP concepts) so as to be easily comprehensible by all. As annoying as the example and problem are, they were painstakenly designed to help you understand the basic concept of genetic algorithm. I shall gradually delve into more "serious" stuff in further tutorials.