15,945,344 members
Articles / Programming Languages / C
Tip/Trick

# Genetic Algorithm

Rate me:
17 May 2005CPOL2 min read 232.6K   28   45
Genetic Algorithm is used to search for maximum/minimum value of a given function using the concept of chromes and genes.

## 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

C++
```#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             		// creating the chrom structure
{
short int bit[6];
int fit;
}chrom;                           	// now we have a chrom type that we can use

void *evpop(chrom popcurrent[4]);    	//defining the functions that we will use
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()								// the main function
{
int num;								// num is the no. of iterations
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"); // introduction to the program

enter: printf("\nPlease enter the no. of iterations:  ");
scanf("%d",&num);             	// enter the no. of iterations in num

chrom popcurrent[4];                        	// we make 4 chromes of popcurrent
chrom popnext[4];                           	// we make 4 chromes of popnext

if(num<1)                               	// if a -ve number is inserted .. enter num again
goto enter;

evpop(popcurrent);                       	//initialise pop current

for(i=0;i<num;i++)                      	// loop num times
{

printf("\ni = %d\n",i);        	// print the iteration number

for(j=0;j<4;j++)
popnext[j]=popcurrent[j];            	//copy popcurrent to popnext in order to adjust it

pickchroms(popnext);                    	//pick best chromes
crossover(popnext);                      	//cross over to get children chromes
mutation(popnext);                       	//mutate with a low probability

for(j=0;j<4;j++)
popcurrent[j]=popnext[j];             	//copy the chromes of popnext to popcurrent

}                                           // loop back until no. of iterations is exceeded

printf("\nPress any key to end ! ");

flushall();                             		// flush the input buffer
getche();                                	// wait for a character from the keyboard to end

}                                            	//end of main

void *evpop(chrom popcurrent[4])               	//takes a pointer to a chrom of 4 elements
{
int i,j,value;
int random;
for(j=0;j<4;j++)                          // loop of j to choose chromes from [0] to [3]
{
for(i=0;i<6;i++)            			// loop of i to choose the gen of the chrom from  [0] to [5]

{
random=rand();               		// creating random value
random=(random%2);        			// make the random value o or 1 only
popcurrent[j].bit[i]=random;  		// initialising the bit[i] of chrom[j] with random
}   // end of for(i)

value=x(popcurrent[j]);               	// get the value of the chrom as integer
popcurrent[j].fit=y(x(popcurrent[j]));	// calcualte the fitness of chrom[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);     // print the chrom[j]

}    // end of for(j)

return(0);
}                              	//end of evpop function

int x(chrom popcurrent)        	//x function that evaluate the value of a given chrom
{
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);                  	// z=sum of the ( bits * their weights) with the sign value
return(z);                	//return the value of z
}                             	// end x function

int y(int x)          		// the y function that we look for it's maximum value takes x value
{
int y;
y=-(x*x)+5;            	// the function is y= - ( x^ 2 ) +5
return(y);
}                             	// end of y function

void *pickchroms(chrom popcurrent[4])   	// pickchroms takes a pointer to array of chroms
{

int i,j;
chrom temp;                            	//temp chrome to use in sorting

for(i=0;i<3;i++)               		//sorting the given set due to fitness
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;

}   // end of if
}                // end of for loop

for(i=0;i<4;i++)
printf("\nSorting:popnext[%d] fitness=%d",i,popcurrent[i].fit);   	//printing the result
printf("\n");                 //print new line
flushall();                                                       //flush the input buffer
return(0);
}                       //end of pick chromes function

void *crossover(chrom popnext[4]) // crossover function takes a pointer to array of chromes
{
int random;
int i;
random=rand();                                  	//random cross over point
random=((random%5)+1);                    		// cross point should be between (1 - 5)
for(i=0;i<random;i++)                     	//crossing the bits below the cross point index
{
popnext[2].bit[i]=popnext[0].bit[i];        	//child 1 cross over
popnext[3].bit[i]=popnext[1].bit[i];     	// child 2 cross over
} // end of for

for(i=random;i<6;i++)                        	// crossing the bits beyond the cross point index
{
popnext[2].bit[i]=popnext[1].bit[i];     	// child 1 cross over
popnext[3].bit[i]=popnext[0].bit[i];       	// chlid 2 cross over
}    // end of for

for(i=0;i<4;i++)
popnext[i].fit=y(x(popnext[i]));     	// calculating the fitness values for the new set

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);
// printing the bits, value and fitness for the chromes of the new set

return(0);
}                  // end crossover function

void *mutation(chrom popnext[4])   // mutation funtion given a pointer to array of chromes
{

int random;
int row,col,value;
random=rand()%50;                  //random value is between ( 0 - 49 )

if (random==25)    // Suppusiong Probability of mutation is 2 %
{
col=rand()%6;                           	// random column (gene) choosing
row=rand()%4;                           	// random row ( chrome ) choosing

if (popnext[row].bit[col]==0)          	// invert the bit to 1 if it was 0
popnext[row].bit[col]=1 ;

else if (popnext[row].bit[col]==1)       	// invert the bit to 0 if it was 1
popnext[row].bit[col]=0;

popnext[row].fit=y(x(popnext[row]));   	// calculate the fitness for the mutated chrome
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);

// print the chrome index,bits,value, fintness of the mutated chrome
}         	// end of if

return(0);
}                       //end of mutation```

## Finally

Hope you benefit from this code ... with Allah's blessings.

Written By
Engineer
Kuwait
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.

 First PrevNext
 need help! Member 1420607831-Mar-19 6:45 Member 14206078 31-Mar-19 6:45
 real coding sirine Telmoudi10-Jan-16 0:57 sirine Telmoudi 10-Jan-16 0:57
 question HöûSsèm Öptïmïste23-Apr-15 4:05 HöûSsèm Öptïmïste 23-Apr-15 4:05
 Re: question Loay Al Lusi25-Apr-15 1:46 Loay Al Lusi 25-Apr-15 1:46
 genetic algorithm for minimisation JZakaria29-May-13 23:14 JZakaria 29-May-13 23:14
 My vote of 1 dariush_ha26-Jun-12 10:54 dariush_ha 26-Jun-12 10:54
 Can you help me AJkkk11-Apr-12 0:36 AJkkk 11-Apr-12 0:36
 My vote of 4 DarkElieDraven27-Mar-12 7:48 DarkElieDraven 27-Mar-12 7:48
 ga based filter proyanga29-Jan-12 18:31 proyanga 29-Jan-12 18:31
 Mutation Member 845447411-Dec-11 6:04 Member 8454474 11-Dec-11 6:04
 Some douts of the GA program code... Member 456894126-Aug-11 0:32 Member 4568941 26-Aug-11 0:32
 Re: Some douts of the GA program code... Loay Al Lusi25-Apr-15 2:08 Loay Al Lusi 25-Apr-15 2:08
 Re: Some douts of the GA program code... Member 1353242927-Nov-17 18:50 Member 13532429 27-Nov-17 18:50
 need of help pallavi khatri6-Sep-10 23:13 pallavi khatri 6-Sep-10 23:13
 Re: need of help Loay Al Lusi8-Sep-10 2:08 Loay Al Lusi 8-Sep-10 2:08
 checking Joannecw865-Sep-10 15:18 Joannecw86 5-Sep-10 15:18
 Re: checking Loay Al Lusi6-Sep-10 1:41 Loay Al Lusi 6-Sep-10 1:41
 about genetic algorithm nalinikanta sutar18-Aug-10 22:48 nalinikanta sutar 18-Aug-10 22:48
 GA Code B.V.Raghavendra20-Jun-10 22:09 B.V.Raghavendra 20-Jun-10 22:09
 What is chrom? Joannecw8613-Jun-10 19:33 Joannecw86 13-Jun-10 19:33
 Re: What is chrom? Loay Al Lusi13-Jun-10 22:59 Loay Al Lusi 13-Jun-10 22:59
 Re: What is chrom? Joannecw8614-Jun-10 19:00 Joannecw86 14-Jun-10 19:00
 Re: What is chrom? Loay Al Lusi14-Jun-10 20:06 Loay Al Lusi 14-Jun-10 20:06
 Re: What is chrom? Joannecw8614-Jun-10 20:57 Joannecw86 14-Jun-10 20:57
 Re: What is chrom? Loay Al Lusi14-Jun-10 20:59 Loay Al Lusi 14-Jun-10 20:59
 Last Visit: 31-Dec-99 18:00     Last Update: 23-Jul-24 5:46 Refresh 12 Next ᐅ