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:
- Population
of people (Community)
- Problem
in community?
- Yes:
(Community facing villain attacks)
- Select Parents to mate (Selection)
- Mix (recombine) genes to form new offspring having
both parents traits (Recombination)
- 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)
- 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.
- 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++; fit = (double) cnt/SIZE; cout<<"fit = "<<fit<<endl; 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;
int num;
srand(time(0));
for(int i = 0 ; i < SIZE ; i++ )
{
num = rand() % SIZE; 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++;
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;
*(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)
{
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++;
fit = (double) cnt/SIZE;
cout<<"fitness = "<<fit<<endl;
return fit;
}
void mutate (int *arr)
{
srand(time(0));
int i = rand()%8;
*(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));
for(int i = 0 ; i < SIZE ; i++ )
{
num = rand() % SIZE;
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)
{
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;
for(int i = 0; i < SIZE; i++)
{
femaleParent[i] = rand()%2;
}
mate(maleParent,femaleParent,offspring);
offspringFitness = calcFitness(offspring);
while(offspringFitness != 1)
{
if( offspringFitness < 0.15){
mutate(maleParent);
mutate(femaleParent);
}
nextGeneration(maleParent,femaleParent,offspring);
mate(maleParent,femaleParent,offspring);
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.
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.