Click here to Skip to main content
11,582,850 members (69,692 online)
Click here to Skip to main content

Genetic Algorithm

, 17 May 2005 CPOL 109.5K 8 27
Rate this:
Please Sign up or sign in to vote.
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

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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Loay Al Lusi
Engineer
Kuwait 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.
For more info, please check my linkedin page.

You may also be interested in...

Comments and Discussions

 
Questionquestion Pin
HöûSsèm Öptïmïste23-Apr-15 4:05
memberHöûSsèm Öptïmïste23-Apr-15 4:05 
AnswerRe: question Pin
Loay Al Lusi25-Apr-15 1:46
memberLoay Al Lusi25-Apr-15 1:46 
Questiongenetic algorithm for minimisation Pin
Member 1008418729-May-13 23:14
memberMember 1008418729-May-13 23:14 
GeneralMy vote of 1 Pin
dariush_ha26-Jun-12 10:54
memberdariush_ha26-Jun-12 10:54 
GeneralCan you help me Pin
Lemany7611-Apr-12 0:36
memberLemany7611-Apr-12 0:36 
GeneralMy vote of 4 Pin
DarkElieDraven27-Mar-12 7:48
memberDarkElieDraven27-Mar-12 7:48 
Questionga based filter Pin
proyanga29-Jan-12 18:31
memberproyanga29-Jan-12 18:31 
QuestionMutation Pin
Member 845447411-Dec-11 6:04
memberMember 845447411-Dec-11 6:04 
QuestionSome douts of the GA program code... Pin
Member 456894126-Aug-11 0:32
memberMember 456894126-Aug-11 0:32 
AnswerRe: Some douts of the GA program code... Pin
Loay Al Lusi25-Apr-15 2:08
memberLoay Al Lusi25-Apr-15 2:08 
Generalneed of help Pin
pallavi khatri6-Sep-10 23:13
memberpallavi khatri6-Sep-10 23:13 
GeneralRe: need of help Pin
luay19858-Sep-10 2:08
memberluay19858-Sep-10 2:08 
Generalchecking Pin
Joannecw865-Sep-10 15:18
memberJoannecw865-Sep-10 15:18 
GeneralRe: checking Pin
luay19856-Sep-10 1:41
memberluay19856-Sep-10 1:41 
Generalabout genetic algorithm Pin
nalinikanta sutar18-Aug-10 22:48
membernalinikanta sutar18-Aug-10 22:48 
GeneralGA Code Pin
B.V.Raghavendra20-Jun-10 22:09
memberB.V.Raghavendra20-Jun-10 22:09 
QuestionWhat is chrom? Pin
Joannecw8613-Jun-10 19:33
memberJoannecw8613-Jun-10 19:33 
AnswerRe: What is chrom? Pin
luay198513-Jun-10 22:59
memberluay198513-Jun-10 22:59 
GeneralRe: What is chrom? Pin
Joannecw8614-Jun-10 19:00
memberJoannecw8614-Jun-10 19:00 
GeneralRe: What is chrom? Pin
luay198514-Jun-10 20:06
memberluay198514-Jun-10 20:06 
GeneralRe: What is chrom? Pin
Joannecw8614-Jun-10 20:57
memberJoannecw8614-Jun-10 20:57 
GeneralRe: What is chrom? Pin
luay198514-Jun-10 20:59
memberluay198514-Jun-10 20:59 
GeneralRe: What is chrom? Pin
Joannecw861-Jul-10 20:51
memberJoannecw861-Jul-10 20:51 
Generali want an idea???????? any one can help Pin
vibhor sharma8-Apr-10 12:26
membervibhor sharma8-Apr-10 12:26 
GeneralRe: i want an idea???????? any one can help Pin
luay198514-Jun-10 0:11
memberluay198514-Jun-10 0:11 
QuestionFitness function for multicast routing Pin
kruthikan29-Mar-10 22:43
memberkruthikan29-Mar-10 22:43 
GeneralFitness function Pin
Parisa.gharavi4-Dec-09 9:18
memberParisa.gharavi4-Dec-09 9:18 
GeneralRe: Fitness function Pin
luay19854-Dec-09 9:42
memberluay19854-Dec-09 9:42 
GeneralFitness function Pin
Parisa.gharavi4-Dec-09 9:18
memberParisa.gharavi4-Dec-09 9:18 
GeneralGenetic algorithm in Matlab Pin
Parisa.gharavi30-Nov-09 21:21
memberParisa.gharavi30-Nov-09 21:21 
GeneralRe: Genetic algorithm in Matlab Pin
luay19852-Dec-09 21:41
memberluay19852-Dec-09 21:41 
GeneralThis is a good example for new starters. Mustafa Öner Dikdere Pin
Oner Dikdere (TR)30-May-08 1:09
memberOner Dikdere (TR)30-May-08 1:09 
GeneralRe: This is a good example for new starters. Mustafa Öner Dikdere [modified] Pin
ahyeek10-Mar-09 16:35
memberahyeek10-Mar-09 16:35 
GeneralHi my friend Pin
fiore451-May-08 2:30
memberfiore451-May-08 2:30 
GeneralRe: Hi my friend Pin
luay198530-May-08 1:31
memberluay198530-May-08 1:31 
Generalhelp me Pin
ahmadi_javad15-Apr-08 0:58
memberahmadi_javad15-Apr-08 0:58 
GeneralUpdating soon Pin
luay198517-May-05 22:31
memberluay198517-May-05 22:31 
GeneralIN OTHER WORDS.... Pin
BobbyQSoft17-May-05 9:42
memberBobbyQSoft17-May-05 9:42 
GeneralRe: IN OTHER WORDS.... Pin
luay198520-May-05 5:14
memberluay198520-May-05 5:14 
GeneralPleaaaaase, DO improve your article ! Pin
Kochise17-May-05 1:57
memberKochise17-May-05 1:57 
GeneralRe: Pleaaaaase, DO improve your article ! Pin
luay198520-May-05 5:10
memberluay198520-May-05 5:10 
GeneralRe: Pleaaaaase, DO improve your article ! Pin
ahyeek8-Apr-09 6:09
memberahyeek8-Apr-09 6:09 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.150603.1 | Last Updated 17 May 2005
Article Copyright 2005 by Loay Al Lusi
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid