GA(找出f(x，y)的最大值) [英] GA (find Max of f(x,y))
本文介绍了GA(找出f(x，y)的最大值)的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我实现了C代码，以查找具有2个参数的函数的最大值，其源代码如下:
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
}
我在运行时遇到一个问题:实际上，该程序经过一定次数的迭代后，会生成与上次相同的4条染色体，因此我的适应性并没有提高.谁知道告诉我算法中的问题是什么?
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!
推荐答案
函数srand(time(NULL));只能在第一次使用rand()函数之前被调用一次.
The functionsrand(time(NULL));should only be called once before therand()function is used for the first time.
当函数仅依赖一个变量时，代码是否会产生明智的答案?例如尝试使用1-x * x而不依赖于y.如果这样不起作用，则您可以放大-algorithm的实现中的任何错误而无需查看多个维度.
干杯，
Ash
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
您需要查看不同的选择技术，例如轮盘赌选择和锦标赛选择.阅读此文章.我已经编辑了您的代码并更改了chrom结构，以将该点包含为int[2].我在选择中使用了精英主义.您需要增加人口规模，并且要这样做，您需要编辑分频器功能以支持任何人口规模.更改代码中的常量将更改算法的性能.为了改进此算法，我相信使用轮盘赌选择技术会比实现的算法更好.
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 thechromstruct to include the point as anint[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);
}
}
}
}
这篇关于GA(找出f(x，y)的最大值)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
