Click here to Skip to main content
14,978,671 members
Please Sign up or sign in to vote.
2.67/5 (3 votes)
See more:
I implemented the C code for find the maximun of a function with 2 parametres which the source code is the following:
#include<stdio.h>          //to use the printf function
#include<conio.h>         //to use the getche function
#include<stdlib.h>
#include<math.h>         //to use the rand function
#include<time.h>
#define DIM_POP 4
#define NO_BIT 6
#define PAR_MIN -15.0      // studying the function into established interval [-2^3, 2^3]
#define PAR_MAX 15.0

typedef struct             // creating the chrom structure
   {
     int bit[2][NO_BIT];  //defining a matrix for point like (x,y);
     float fit;
   }chrom; 

   
                          

void evpop(chrom popcurrent[DIM_POP]);    //defining the functions that we will use
float xy(chrom popcurrent, int k);
float z(float x, float y);
void pickchroms(chrom popcurrent[DIM_POP]);
void crossover(chrom popnext[DIM_POP]);
void mutation(chrom popnext[DIM_POP]);

int main()                                    // the main function
{
   int num;                                     // num is the no. of iterations
   int i,j;

   printf("\nMaximum of the function z = -x^2-y^2 + 5 ");                         // introduction to the program


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

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


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

   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<DIM_POP;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<DIM_POP;j++)                     
        popcurrent[j]=popnext[j];               //copy the chromes of popnext to popcurrent 

    }
 
    
    printf("\nPress any key to end ! ");
   
    getche();                                        // wait for a character from the keyboard to end

}                                                      //end of main

 

void evpop(chrom popcurrent[DIM_POP])               //takes a pointer to a chrom of 4 elements
{
   int i,j,k,t,v;
   float x,y;
   int random;
   for(j=0;j<DIM_POP;j++)                          // loop of j to choose chromes from [0] to [DIM_POP]
    {
        for(k=0;k<2;k++)            // loop of i to choose the gen of the chrom from  [0] to [2]
        {
            for(i=0;i<NO_BIT;i++)
            {
            random=rand();               // creating random value
            random=(random%2);        // make the random value o or 1 only
            popcurrent[j].bit[k][i]=random;  // initialising the bit[k][i] of chrom[j] with random
            }
        }   // end of for(i)
        
         
        x=xy(popcurrent[j], 0); 
        y=xy(popcurrent[j], 1);             // get the value of the chrom as integer
        popcurrent[j].fit=z(x,y);        // calcualte the fitness of chrom[j]
        printf("\n popcurrent[%d]=(", j);
        for(v=0;v<2;v++)
        {
           for(t=NO_BIT-1;t>=0;t--)
               printf("%d",popcurrent[j].bit[v][t]);   // print the chrom[j]
           if(v==0)
              printf(",");
        }
        printf(")    value = (%f,%f)    fitness = %f",x,y,popcurrent[j].fit);                                                                                   
    }    // end of for(j)                                                              

                
}                                //end of evpop function

float xy(chrom popcurrent, int k)        //x function that evaluate the value of a given chrom
{
   float z;
   float dec=0.0;
   for(int i=0;i<NO_BIT;i++)
       dec=dec+popcurrent.bit[k][i]*pow(2,i);
   z=(PAR_MAX-PAR_MIN)*(dec/pow(2,NO_BIT))+PAR_MIN;
                        // z=sum of the ( bits * their weights) with the sign value parameterized into [-15,15]  
    return(z);                     
 }                                   // end xy function
 
 

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

void pickchroms(chrom popcurrent[])   // pickchroms takes a pointer to array of chroms
{
   int i,j;
   chrom temp;                            //temp chrome to use in sorting
   for(i=0;i<DIM_POP-1;i++)
         for(j=0;j<DIM_POP-1;j++)              //sorting the given set due to fitness
         {
             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<DIM_POP;i++)
  printf("\nSorting:popnext[%d] fitness=%f",i,popcurrent[i].fit);           //printing the result
  printf("\n");                 //print new line
                                                               //flush the input buffer
}                       //end of pick chromes function

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

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

      for(i=0;i<DIM_POP;i++)
       popnext[i].fit=z(xy(popnext[i], 0),xy(popnext[i],1));     // calculating the fitness values for the new set

      for(int i=0;i<DIM_POP;i++)
      {
          printf("\nCrossOver popnext[%d]=(", i);
          for(v=0;v<2;v++)
          {
              for(t=NO_BIT-1;t>=0;t--)
                  printf("%d",popnext[i].bit[v][t]);   // print the chrom[j]
              if(v==0)
                 printf(",");
          }
        printf(")  value = (%f,%f)  fitness = %f",xy(popnext[i], 0),
               xy(popnext[i], 1),popnext[i].fit); 
      }                         
      
                       // printing the bits, value and fitness for the chromes of the new set

}                  // end crossover function


void mutation(chrom popnext[DIM_POP])   // mutation funtion given a pointer to array of chromes
{
  
   int random;
   int row,col,v,t;
   float x,y;                                     
   random=rand()%50;                  //random value is between ( 0 - 49 )

   if (random==25)    // Suppusiong Probability of mutation is 2 % 
   {
      col=rand()%NO_BIT;                             // random column (gene) choosing                            
      row=rand()%DIM_POP;                           // random row ( chrome ) choosing
      for(int k=0;k<2;k++)
      {
         if (popnext[row].bit[k][col]==0)          // invert the bit to 1 if it was 0
             popnext[row].bit[k][col]=1 ;
     
             else if (popnext[row].bit[k][col]==1)       // invert the bit to 0 if it was 1
             popnext[row].bit[k][col]=0;
      }
       x=xy(popnext[row],0);
       y=xy(popnext[row],1); 
       popnext[row].fit=z(x,y);   // calculate the fitness for the mutated chrome
       printf("\nMutation occured in popnext[%d] bit[%d]:=(",row,col);
        for(v=0;v<2;v++)
        {
           for(t=NO_BIT-1;t>=0;t--)
               printf("%d",popnext[row].bit[v][t]);   // print the chrom[j]
           if(v==0)
              printf(",");
        }
        printf(")  value = (%f,%f)  fitness = %f",x,y,popnext[row].fit);

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


I had one problem at runtime: practically this program after a certain number of iterations, generates the same 4 chromosomes of the last time and so the my fitness doesn't improve. Anyone know tell me what is the problem in my algorithm?

Thank you in advance!
Posted
Updated 10-Jan-11 23:57pm
v3
Comments
TweakBird 9-Jan-11 13:29pm
   
Please use <pre> tag for code blocks.
Keith Barrow 9-Jan-11 13:30pm
   
Has it found the optimal solution?
Dalek Dave 9-Jan-11 15:10pm
   
Your code needs a lot more comment.

The function srand(time(NULL)); should only be called once before the rand() function is used for the first time.
   
v2
Comments
Dalek Dave 9-Jan-11 15:10pm
   
Good call.
Does the code produce a sensible answer when the function only depends on one variable? e.g. try it with 1 - x * x and not dependent on y. If that doesn't work you might be able to zoom in on whatever's wrong in you implementation of the -algorithm without multiple dimensions to look at.

Cheers,

Ash
   
You need to look at different techniques for selection e.g. roulette wheel selection and tournament selection. Read this article. I have edited your code and changed the chrom struct to include the point as an int[2]. I have used elitism in the selection. You need to increase the population size and to do that, you need to edit your crossover function to support any population size. Changing the constants in the code would change the performance of the algorithm. To improve this algorithm, I believe that using the roulette wheel selection technique would be better than the one implemented.

#include<stdio.h>          //to use the printf function
#include<conio.h>         //to use the getche function
#include<stdlib.h>
#include<math.h>         //to use the rand function
#include<time.h>

#define DIM_POP 100
#define ELITIST 5		// the number of chromosomes to keep (using the elitism selection concept)
#define PAR_MIN -15.0      // studying the function into established interval [-2^3, 2^3]
#define PAR_MAX 15.0
#define RESOLUTION 0.1      // minimum change in the parameter value 

typedef struct             // creating the chrom structure
{
	float point[2];  //defining a matrix for point like (x,y);
	float fit;
}chrom; 

void generatePoint(float point[2]);
float generateParam();
void evpop(chrom popcurrent[DIM_POP]);    //defining the functions that we will use
float calculateFitness(float x, float y);
void pickchroms(chrom popcurrent[DIM_POP]);
void crossover(chrom popnext[DIM_POP]);
void mutation(chrom popnext[DIM_POP]);

int main()                                    // the main function
{
	int num;                                     // num is the no. of iterations

	printf("\nMaximum of the function z = -x^2-y^2 + 5 ");                         // introduction to the program

	do
	{
		printf("\nPlease enter the no. of iterations:  ");
		scanf("%i",&num);                           // enter the no. of iterations in num
	}while(num<1);

	chrom population[DIM_POP];

	srand(time(NULL));


	evpop(population);                         //initialise pop current

	for(int i=0;i<num;i++)                            // loop num times
	{
		printf("\ni = %i\n",i);                     // print the iteration number

		pickchroms(population);                    //sort chromosomes
		crossover(population);                      //cross over to get children chromes
		mutation(population);                       //mutate
	}

	printf("\nPress any key to end ! ");
	getche();                                        // wait for a character from the keyboard to end
}

void generatePoint(float point[2])
{
	point[0] = generateParam();
	point[1] = generateParam();
}

float generateParam()
{
	float param = ((float)rand()/RAND_MAX)*(PAR_MAX-PAR_MIN) + PAR_MIN;

	float roundedParam = PAR_MIN;
	int counter = 1;
	while(roundedParam<param)
	{
		roundedParam = PAR_MIN + counter * RESOLUTION;
		counter++;
	}

	return roundedParam;
}

void evpop(chrom popcurrent[DIM_POP]) // generate the initial population
{
	for(int i=0;i<DIM_POP;i++)
	{
		generatePoint(popcurrent[i].point);
		popcurrent[i].fit=calculateFitness(popcurrent[i].point[0],popcurrent[i].point[1]);

		printf("\npopcurrent[%i]=(%f, %f)", i, popcurrent[i].point[0],popcurrent[i].point[1]);
		printf("\tfitness = %f",popcurrent[i].fit);
	}
}

float calculateFitness(float x, float y)          // the function that we look for it's maximum value takes (x,y) value
{
	float t;
	t=-(x*x)-(y*y)+5;            // the function is z= - ( x^ 2 ) - (y^ 2) +5
	return(t);
}

void pickchroms(chrom popcurrent[])   // pickchroms takes a pointer to array of chroms
{
	chrom temp;                            //temp chrome to use in sorting

	for(int i=0;i<DIM_POP-1;i++)
	{
		for(int j=0;j<DIM_POP-1-i;j++)              //sorting the given set according to fitness
		{
			if(popcurrent[j+1].fit>popcurrent[j].fit)
			{
				temp=popcurrent[j+1];
				popcurrent[j+1]=popcurrent[j];
				popcurrent[j]=temp;
			}
		}
	}

	for(int i=0;i<DIM_POP;i++)
		printf("\nSorting:popnext[%i] fitness=%f",i,popcurrent[i].fit);           //printing the result

	printf("\n");
}

void crossover(chrom popnext[DIM_POP]) // crossover function takes a pointer to array of chromes
{
	for(int i = ELITIST; i < DIM_POP; i++)
	{
		if(rand()%2 ==0)
			popnext[i].point[1] = popnext[rand()%DIM_POP].point[1];
		else
			popnext[i].point[2] = popnext[rand()%DIM_POP].point[2];

		popnext[i].fit = calculateFitness(popnext[i].point[0],popnext[i].point[1]);
	}

	// Print the population
	for(int i=0;i<DIM_POP;i++)
	{
		printf("\nCrossOver popnext[%i]=(%f, %f)", i, popnext[i].point[0], popnext[i].point[1]);
		printf("\tfitness = %f", popnext[i].fit);
	}
}


void mutation(chrom popnext[DIM_POP])   // mutation funtion given a pointer to array of chromes
{
	for(int i = ELITIST; i<DIM_POP; i++)
	{
		for(int j = 0; j < 2; j++)
		{
			if ((rand()%100)<20)    // Suppusiong Probability of mutation is 20 % 
			{
				popnext[i].point[j] = generateParam();
				popnext[i].fit=calculateFitness(popnext[i].point[0], popnext[i].point[1]);   // calculate the fitness for the mutated chrome

				// print the mutated chromosome
				printf("\nMutation occured in popnext[%i] gene[%i]:=(%f, %f)",i,j,popnext[i].point[0],popnext[i].point[1]);
				printf("\tfitness = %f",popnext[i].fit);
			}
		}
	}
}
   
Comments
euromecc 5-Apr-11 4:00am
   
In the function "float generateParam()" I think there is too much because with the instruction "float param = ((float)rand()/RAND_MAX)*(PAR_MAX-PAR_MIN) + PAR_MIN;" you alredy choose a number between PAR_MAX and PAR_MIN. Why do you need the instruction "roundedParam = PAR_MIN + counter * RESOLUTION;"?
M. Mohsen 16-Apr-11 18:47pm
   
Because due to the division in this statement "float param = ((float)rand()/RAND_MAX)*(PAR_MAX-PAR_MIN) + PAR_MIN;" the param variable may have many digits after the decimal. This makes the search space very big. For that reason, I had to use that while loop because it allows me to set a resolution say 0.1 this will keep all the numbers generated within one decimal place. This will decrease the search space effectively. I didn't use the round function and preferred to write it that way to allow the resolution to be say 0.5, which means that the numbers generated will be say 1, 0.5 and 2 (no fraction other than 0.5).
I change a little your code to introduce tabu search algorithm in a way that the best current solution, each cycle is inserted in tabu list. Because of this change I
deleted the elitism concept from the code in a way the crossover and mutation are applied to each single point of the population. But the program still has some
problem since its execution stops at runtime. What am I wrong?

C++



#include<stdlib.h>
#include<math.h> //to use the rand function
#include<time.h>

#define DIM_POP 100
//#define ELITIST 5 // the number of chromosomes to keep (using the elitism selection concept)
#define DIM_TABU 14 // dimension of tabu list
#define TENURE 7 //tenure time of tabu list
#define PAR_MIN -15.0 // studying the function into established interval [-2^3, 2^3]
#define PAR_MAX 15.0
#define RESOLUTION 0.1 // minimum change in the parameter value
#define S 0.1 //minimum distance between new point and tabu list points
typedef struct // creating the chrom structure
{
float point[2]; //defining a matrix for point like (x,y);
float fit;
int tenure; //defining tabu list parameter
}chrom;

void generatePoint(float point[2]);
float generateParam();
void evpop(chrom popcurrent[DIM_POP]); //defining the functions that we will use
float calculateFitness(float x, float y);
void pickchroms(chrom popcurrent[DIM_POP]);
void crossover(chrom popnext[DIM_POP]);
void mutation(chrom popnext[DIM_POP]);
void tabu_search(chrom popnext);
chrom tabu[DIM_TABU];

int main() // the main function
{
int num; // num is the no. of iterations

printf("\nMaximum of the function z = -x^2-y^2 + 5 "); // introduction to the program

do
{
printf("\nPlease enter the no. of iterations: ");
scanf("%i",&num); // enter the no. of iterations in num
}while(num<1);

chrom population[DIM_POP];


for(int i=0;i<dim_tabu;i++)>
{
tabu[i].tenure=0; //setting to 0 tabu list tenure
}

srand(time(NULL));


evpop(population); //initialise pop current

for(int i=0;i {
printf("\ni = %i\n",i); // print the iteration number

pickchroms(population); //sort chromosomes
crossover(population); //cross over to get children chromes
mutation(population); //mutate
pickchroms(population);
tabu_search(population[0]);
}

printf("\nPress any key to end ! ");
getche(); // wait for a character from the keyboard to end
}

void generatePoint(float point[2])
{
point[0] = generateParam();
point[1] = generateParam();
}

float generateParam()
{
float param = ((float)rand()/RAND_MAX)*(PAR_MAX-PAR_MIN) + PAR_MIN;

float roundedParam = PAR_MIN;
int counter = 1;
while(roundedParam<param)>
{
roundedParam = PAR_MIN + counter * RESOLUTION;
counter++;
}

return roundedParam;
}

void evpop(chrom popcurrent[DIM_POP]) // generate the initial population
{
for(int i=0;i<dim_pop;i++)>
{
generatePoint(popcurrent[i].point);
popcurrent[i].fit=calculateFitness(popcurrent[i].point[0],popcurrent[i].point[1]);

printf("\npopcurrent[%i]=(%f, %f)", i, popcurrent[i].point[0],popcurrent[i].point[1]);
printf("\tfitness = %f",popcurrent[i].fit);
}
}

float calculateFitness(float x, float y) // the function that we look for it's maximum value takes (x,y) value
{
float t;
t=-(x*x)-(y*y)+5; // the function is z= - ( x^ 2 ) - (y^ 2) +5
return(t);
}

void pickchroms(chrom popcurrent[]) // pickchroms takes a pointer to array of chroms
{
chrom temp; //temp chrome to use in sorting

for(int i=0;i<dim_pop-1;i++)>
{
for(int j=0;j {
if(popcurrent[j+1].fit>popcurrent[j].fit)
{
temp=popcurrent[j+1];
popcurrent[j+1]=popcurrent[j];
popcurrent[j]=temp;
}
}
}

for(int i=0;i<dim_pop;i++)>
printf("\nSorting:popnext[%i] fitness=%f",i,popcurrent[i].fit); //printing the result

printf("\n");
}

void crossover(chrom popnext[DIM_POP]) // crossover function takes a pointer to array of chromes
{
for(int i = 0; i < DIM_POP; i++)
{
if(rand()%2 ==0)
popnext[i].point[1] = popnext[rand()%DIM_POP].point[1];
else
popnext[i].point[2] = popnext[rand()%DIM_POP].point[2];

popnext[i].fit = calculateFitness(popnext[i].point[0],popnext[i].point[1]);
}

// Print the population
for(int i=0;i<dim_pop;i++)>
{
printf("\nCrossOver popnext[%i]=(%f, %f)", i, popnext[i].point[0], popnext[i].point[1]);
printf("\tfitness = %f", popnext[i].fit);
}
}


void mutation(chrom popnext[DIM_POP]) // mutation funtion given a pointer to array of chromes
{
for(int i = 0; i<dim_pop;> {
for(int j = 0; j < 2; j++)
{
if ((rand()%100)<20) // Suppusiong Probability of mutation is 20 %
{
popnext[i].point[j] = generateParam();
popnext[i].fit=calculateFitness(popnext[i].point[0], popnext[i].point[1]); // calculate the fitness for the mutated chrome

// print the mutated chromosome
printf("\nMutation occured in popnext[%i] gene[%i]:=(%f, %f)",i,j,popnext[i].point[0],popnext[i].point[1]);
printf("\tfitness = %f",popnext[i].fit);
}
}
}
}

void tabu_search(chrom popnext)
{
int flag=0;
int flag_2=0;
int i,j,k;
//checking if tabu list is empty
for(i=0;i<dim_tabu;i++)>
{
if(tabu[i].tenure==0)
continue;
flag=1;
break;
}
//decreasing tenure time if tabu list is not empty
if(flag)
{
for(j=0;j<dim_tabu;j++)>
{
if(tabu[j].tenure>0)
tabu[j].tenure--;
}
//checking distance between each element in tabu list and the new element marked as current best
for(k=0;k<dim_tabu;k++)>
{
if(sqrt(pow(tabu[j].point[0]-popnext.point[0],2)+pow(tabu[j].point[1]-popnext.point[1],2))>S)
continue;
flag_2=1;
break;
}
//inserting best current value into tabu list if it is different from all value already present in tabu list
if(flag_2)
{
for(k=0;k<dim_tabu;k++)>
{
if(tabu[k].tenure==0)
{
tabu[k]=popnext;
tabu[k].tenure=TENURE;
}
}
}
}
//inserting best current value in tabu list if it is empty
else
{
tabu[k]=popnext;
tabu[k].tenure=TENURE;
}
}

<pre lang="c++">
   
M. Mohsen unfortunately the algorithm doesn't work well even with your proposed solution. The problem persists

Aescleal my algorithm works well with only one parametre!


Have you got any solutions?
   
v3
Comments
M. Mohsen 11-Jan-11 13:11pm
   
Read Answer 4, hope it helps :)
Your code might be a good alternative to me one but I noticed that it run a lot of iterations with the same first best values, namely it keep these value for a long time. For example, in one of my prove, the value 4.91 (the current best) is kept in the list from 8th to 43th iteration, remaining the best point found so far. So does it work well?
   
v2
Comments
M. Mohsen 12-Jan-11 7:58am
   
Yes this uses the elitism. The basic concept is that it keeps the best solutions found so far to prevent them from being lost by random mutation or cross overs. Infact, the line "#define ELITIST 5" is the define statement that determines the number of solutions to preserve from one iteration to the next.
mbistato 5-Apr-11 10:43am
   
Hi! Actually my problem is more complicate than it seems because my work consists in a Hybrid algorithm GA+Tabu Search and maybe the solution that you gave me is just for a simple Ga. Anyway I tried to assemble them together let them work in cascade (as GA finishes TB takes the best value found so far and generate a new population starting from that best) but the program doesn't work well. What are your advises?
M. Mohsen 16-Apr-11 19:01pm
   
I just read this paper http://www.jatit.org/volumes/research-papers/Vol9No1/2Vol9No1.pdf and as I understand, Tabu is something to replace the elitism concept that i have used in this program. Because it keeps the best chromosomes but for a limited number of iterations to keep the program from being stuck in a local optimum solution. Please correct me if I am wrong and have a look at the flow chart in that paper.
mbistato 1-Aug-11 17:16pm
   
What you said about the elitism seems to match with anything in my program, so your intuition was good. The paper is really good and it provide me a better idea to follow. But it also true that it is quite brief and I couldn't understand the concept of tabu list and aspiration list. Do you have some ideas about how can I implement tabu list and aspiration list criteria?
mbistato 17-Sep-11 11:33am
   
Mr Mohsen I really need your help because I can't find a way to implement tabu search and aspiration criteria function in my algorithm cause the pdf file that you provide me is too brief
M. Mohsen 25-Sep-11 19:31pm
   
Actually, I am sorry that is all my information in this topic. You can use Google to search for anything else you need to know.

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




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900