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?
#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++">