Introduction
Hi everyone .. this tip is about Genetic search algorithm ... in general, it's used to find a maximum or minimum value of a given function using the concept of biological chromes and genes.
Basics
So for now ... what we need to do ... is to make 2 population set ... where a current set has the initial points (chromes), and the next set containing the points (chromes) produced by the first set .... and so on ... until we finish the number of iterations.
i.e.: Current set for randomly initialized chromes:
Current population of 4 chromes:
- each row is a chrome.
- each chrome consist of 6 genes (6 columns) [ 1 sign bit and 5 other bits ] and a fitness value [the last column to the right] that represent the function value y(x) at the value of the given chrome (x) ... where the chrome is converted to an integer value from the bits conversion ...
c no.
| Sb
| b5
| b4
| b3
| b2
| b1
| fit
|
1
| 0
| 1
| 0
| 1
| 1
| 0
| 8
|
2
| 1
| 0
| 0
| 1
| 0
| 0
| 6
|
3
| 0
| 0
| 1
| 0
| 1
| 0
| 9
|
4
| 0
| 0
| 0
| 1
| 1
| 0
| 12 |
Functions
1. Picking the Best Chromes
As in the actual life principles ... " Survival is for the strongest " , so we choose the best 2 elements of the set (current population) according to their fitness (highest fitness as we are looking for the maximum value of the function).
The new set:
c no.
| Sb
| b5
| b4
| b3
| b2
| b1
| fit
|
4
| 0
| 0
| 0
| 1
| 1
| 0
| 12
|
3
| 0
| 0
| 1
| 0
| 1
| 0
| 9
|
|
|
|
|
| | |
|
|
| |
|
|
|
| |
2. Cross Over To Generate the Children
So now, in the new set, we have the two chromes picked from the old set ... they are parents to the other two chromes in the set who will be generated by crossing over the two chromes at a certain point and exchange the two parts as follows:
Cross over occurred after bit 3 (notice the bold and the italic digits being crossed in the children from the parents).
c no.
| Sb
| b5
| b4
| b3
| b2
| b1
| fit
|
4
| 0
| 0
| 0
| 1
| 1
| 0
| 12
|
3
| 0
| 0
| 1
| 0
| 1
| 0
| 9
|
child 1
| 0
| 0
| 0
| 0
| 1
| 0
| 14
|
child 2
| 0
| 0
| 1
| 1
| 1
| 0
| 5 |
3. Mutation with a Low Probability
Mutation occurs with a low probability in one chrome in the set... by inverting one of the bits in the chrome.
4. Loop Termination
Now, we have the new set ... so we make the old set equal to the new one ... and do the 1, 2, and 3 again depending on the number of iterations.
Step By Step Coding
#include<stdio.h> //to use the printf function
#include<conio.h> //to use the getche function
#include<stdlib.h> //to use the rand function
typedef struct Chrom {
short int bit[6];
int fit;
}chrom;
void *evpop(chrom popcurrent[4]); int x(chrom popcurrent);
int y(int x);
void *pickchroms(chrom popcurrent[4]);
void *crossover(chrom popnext[4]);
void *mutation(chrom popnext[4]);
void main() {
int num; int i,j;
printf("\nWelcome to the Genetic Algorithm coded by Loay Al Lusi
:http://www.linkedin.com/in/loayallusi in May 2005 \nThe Algorithm is based on the function
y = -x^2 + 5 to find the maximum value of the function...\n");
enter: printf("\nPlease enter the no. of iterations: ");
scanf("%d",&num);
chrom popcurrent[4]; chrom popnext[4];
if(num<1) goto enter;
evpop(popcurrent);
for(i=0;i<num;i++) {
printf("\ni = %d\n",i);
for(j=0;j<4;j++)
popnext[j]=popcurrent[j];
pickchroms(popnext); crossover(popnext); mutation(popnext);
for(j=0;j<4;j++)
popcurrent[j]=popnext[j];
}
printf("\nPress any key to end ! ");
flushall(); getche();
}
void *evpop(chrom popcurrent[4]) {
int i,j,value;
int random;
for(j=0;j<4;j++) {
for(i=0;i<6;i++)
{
random=rand(); random=(random%2); popcurrent[j].bit[i]=random; }
value=x(popcurrent[j]); popcurrent[j].fit=y(x(popcurrent[j])); printf("\n popcurrent[%d]=%d%d%d%d%d%d value=%d fitness = %d",j,
popcurrent[j].bit[5],popcurrent[j].bit[4],popcurrent[j].bit[3],popcurrent[j].bit[2],
popcurrent[j].bit[1],popcurrent[j].bit[0],value,popcurrent[j].fit);
}
return(0);
}
int x(chrom popcurrent) {
int z;
z=(popcurrent.bit[0]*1)+(popcurrent.bit[1]*2)+(popcurrent.bit[2]*4)+(popcurrent.bit[3]*8)+(popcurrent.bit[4]*16);
if(popcurrent.bit[5]==1)
z=z*(-1); return(z); }
int y(int x) {
int y;
y=-(x*x)+5; return(y);
}
void *pickchroms(chrom popcurrent[4]) {
int i,j;
chrom temp;
for(i=0;i<3;i++) for(j=0;j<3;j++)
{
if(popcurrent[j+1].fit>popcurrent[j].fit)
{
temp=popcurrent[j+1];
popcurrent[j+1]=popcurrent[j];
popcurrent[j]=temp;
} }
for(i=0;i<4;i++)
printf("\nSorting:popnext[%d] fitness=%d",i,popcurrent[i].fit); printf("\n"); flushall(); return(0);
}
void *crossover(chrom popnext[4]) {
int random;
int i;
random=rand(); random=((random%5)+1); for(i=0;i<random;i++) {
popnext[2].bit[i]=popnext[0].bit[i]; popnext[3].bit[i]=popnext[1].bit[i]; }
for(i=random;i<6;i++) {
popnext[2].bit[i]=popnext[1].bit[i]; popnext[3].bit[i]=popnext[0].bit[i]; }
for(i=0;i<4;i++)
popnext[i].fit=y(x(popnext[i]));
for(i=0;i<4;i++)
printf("\nCrossOver popnext[%d]=%d%d%d%d%d%d value=%d fitness = %d",i,
popnext[i].bit[5],popnext[i].bit[4],popnext[i].bit[3],popnext[i].bit[2],
popnext[i].bit[1],popnext[i].bit[0],x(popnext[i]),popnext[i].fit);
return(0);
}
void *mutation(chrom popnext[4]) {
int random;
int row,col,value;
random=rand()%50;
if (random==25) {
col=rand()%6; row=rand()%4;
if (popnext[row].bit[col]==0) popnext[row].bit[col]=1 ;
else if (popnext[row].bit[col]==1) popnext[row].bit[col]=0;
popnext[row].fit=y(x(popnext[row])); value=x(popnext[row]);
printf("\nMutation occured in popnext[%d] bit[%d]:=%d%d%d%d%d%d value=%d
fitness=%d",row,col,popnext[row].bit[5],popnext[row].bit[4],popnext[row].bit[3],
popnext[row].bit[2],popnext[row].bit[1],popnext[row].bit[0],value,popnext[row].fit);
}
return(0);
}
Finally
Hope you benefit from this code ... with Allah's blessings.
I'm Loay Al-Lusi, a Computer Engineer, graduated in March 2007 from Amman Al-ahliya University / Jordan, then graduated with IMBA (International Masters of Business Administration) from Griffith Uni in Brisbane, Australia.
Currently working as a Technical Consultant in Kuwait.
For more info, please check my linkedin page.