test.cpp

简单的遗传算法与模式搜索算法结合

				++first;
				if (first % 2 == 0)
					  Xover(one, mem);
				else
					  one = mem;
				}
		  }
}
/**************************************************************/
/* Crossover: performs crossover of the two selected parents. */
/**************************************************************/

void Xover(int one, int two)
{
	int i;
	int point; /* crossover point */

	/* select crossover point */
	if(NVARS > 1)
	   {
	   if(NVARS == 2)
			 point = 1;
	   else
			 point = (rand() % (NVARS - 1)) + 1;

	   for (i = 0; i < point; i++)
			swap(&population[one].gene[i], &population[two].gene[i]);

	   }
}

/*************************************************************/
/* Swap: A swap procedure that helps in swapping 2 variables */
/*************************************************************/

void swap(double *x, double *y)
{
	double temp;

	temp = *x;
	*x = *y;
	*y = temp;

}

/**************************************************************/
/* Mutation: Random uniform mutation. A variable selected for */
/* mutation is replaced by a random value between lower and   */
/* upper bounds of this variable                              */
/**************************************************************/

void mutate(void)
{
	int i, j;
	double lbound, hbound;
	double x;

	for (i = 0; i < POPSIZE; i++)
		  for (j = 0; j < NVARS; j++)
				{
				x = rand()%1000/1000.0;
				if (x < PMUTATION)
					  {
					  /* find the bounds on the variable to be mutated */
					  lbound = population[i].lower[j];
					  hbound = population[i].upper[j];  
					  population[i].gene[j] = randval(lbound, hbound);
					  }
				}
}

/***************************************************************/
/* Report function: Reports progress of the simulation. Data   */
/* dumped into the  output file are separated by commas        */
/***************************************************************/

void report(void)
{
	int i;
	double best_val;            /* best population fitness */
	double avg;                 /* avg population fitness */
	double stddev;              /* std. deviation of population fitness */
	double sum_square;          /* sum of square for std. calc */
	double square_sum;          /* square of sum for std. calc */
	double sum;                 /* total population fitness */

	sum = 0.0;
	sum_square = 0.0;

	for (i = 0; i < POPSIZE; i++)
		  {
		  sum += population[i].fitness;
		  sum_square += population[i].fitness * population[i].fitness;
		  }

	avg = sum/(double)POPSIZE;
	square_sum = avg * avg * POPSIZE;
	stddev = sqrt((sum_square - square_sum)/(POPSIZE - 1));
	best_val = population[POPSIZE].fitness;

	fprintf(galog, "\n%5d,      %6.9f, %6.9f, %6.9f ", generation, 
										  best_val, avg, stddev);
}


double f(double x[]){
    int i;
	double t[VAR];
	double fit;
	for(i = 0; i < NVARS; i++){
		t[i+1] = x[i];
		fit = 21.5+t[1]*sin(4*3.1415926536*t[1]) + t[2]*sin(20*3.1415926536*t[2]);
	return fit;
	}
}

double best_nearby(double delta[], double point[], double prevbest)
{
	   double	   z[VAR];
	   double	   maxf, ftmp;
	   int		   i;
	   maxf = prevbest;
	   for (i = 0; i < NVARS; i++)
		   z[i] = point[i];
	   for (i = 0; i < NVARS; i++) {
		   z[i] = point[i] + delta[i];
           //
		   if((z[i] < population[0].lower[0])||(z[i] > population[0].upper[0])) continue;
		   //
		   ftmp = f(z);
		   if (ftmp > maxf)
			   maxf = ftmp;
		   else {
			   delta[i] = 0.0 - delta[i];
			   z[i] = point[i] + delta[i];
			   ftmp = f(z);
			   if (ftmp > maxf)
				   maxf = ftmp;
			   else
				   z[i] = point[i];
		   }
	   }
	   for (i = 0; i < NVARS; i++)
		   point[i] = z[i];
	   return (maxf);
}




void  hook(double startpt[], double thefitness, int men)
{
	double delta[VAR];
	double newf, fbefore,steplength,tmp;
	double xbefore[VAR], newx[VAR];
	int i,j,keep;
	int iters,iadj;
	double *best;
	int themen;

	themen = men;

	for (i = 0; i < NVARS; i++) {
		   newx[i] = xbefore[i] = startpt[i];
		   delta[i] = fabs(startpt[i] * rho);
		   if (delta[i] == 0.0)
			   delta[i] = rho;
	   }
	   iadj = 0;
	   steplength = rho;
	   iters = 0;
	   fbefore = thefitness;
	   newf = fbefore;
	  while((iters < itermax)&&(steplength > epsilon) )
	   {
		   iters++;
		   iadj++;

		   /* find best new point, one coord at a time */
		   for (i = 0; i < NVARS; i++) {
			   newx[i] = xbefore[i];
		   }
		   newf = best_nearby(delta, newx, fbefore);
		   /* if we made some improvements, pursue that direction */
		   keep = 1;
		   while((newf > fbefore) && (keep == 1)) {
			   iadj = 0;
			   for (i = 0; i < NVARS; i++) {
				   /* firstly, arrange the sign of delta[] */
				   if (newx[i] <= xbefore[i])
					   delta[i] = 0.0 - fabs(delta[i]);
				   else
					   delta[i] = fabs(delta[i]);
				   /* now, move further in this direction */
				   tmp = xbefore[i];
				   xbefore[i] = newx[i];
				   newx[i] = newx[i] + newx[i] - tmp; //模移
				   if((newx[i] < population[0].lower[0])||(newx[i] > population[0].upper[0])) continue;
			   }
			   fbefore = newf;
			   newf = best_nearby(delta, newx, fbefore);
			   /* if the further (optimistic) move was bad.... */
			   if (newf <= fbefore)
				   break;
			   /* make sure that the differences between the new */
			   /* and the old points are due to actual */
			   /* displacements; beware of roundoff errors that */
			   /* might cause newf < fbefore */
			   keep = 0;
			   for (i = 0; i < NVARS; i++) {
				   keep = 1;
				   if (fabs(newx[i] - xbefore[i]) >
				       (0.5 * fabs(delta[i])))
					   break;
				   else
					   keep = 0;
			   }
		   }
		   if ((steplength >= epsilon) && (newf <= fbefore)) 
		   {
			   steplength = steplength * rho;
			   for (i = 0; i < NVARS; i++) {
				   delta[i] *= rho;
			   }
		   }
	 }

	   for (i = 0; i < NVARS; i++) {
		  population[themen].gene[i] = xbefore[i];
	   }
	   population[themen].fitness = fbefore;
	   
}

void patternsearch() {

	int men, i, j;
	double x;
	double thefitness;
	double thebest[VAR];

	for(men = 0; men < POPSIZE; men++) {
		x = rand()%1000/1000.0;
		if (x > PSA) {
				thefitness = population[men].fitness;
				/*printf("before PS :\n");
				for(i = 0; i < NVARS; i++){
					printf("%f", population[men].gene[i]);
				}
				printf("\n");*/
				hook(population[men].gene,thefitness,men);

			/*	printf("after PS :\n");
				for(i = 0; i < NVARS; i++){
					printf("%f", population[men].gene[i]);
				}
				printf("\n");*/
				
		}

	}
}

/**************************************************************/
/* Main function: Each generation involves selecting the best */
/* members, performing crossover & mutation and then          */
/* evaluating the resulting population, until the terminating */
/* condition is satisfied                                     */
/**************************************************************/

void main(void)
{
int i;
if ((galog = fopen("galog.txt","w"))==NULL)
      {
      exit(1);
      }
srand((unsigned)time(0));

	generation = 0;
fprintf(galog, "\n generation  best  average  standard \n");
fprintf(galog, " number      value fitness  deviation \n");

initialize();
evaluate();
keep_the_best();
while(generation<MAXGENS)
      {
      generation++;
      select();
      crossover();
      mutate();
	  patternsearch();
      report();
      evaluate();
      elitist();
	  printf("\n%d",generation);
      }
fprintf(galog,"\n\n Simulation completed\n");
fprintf(galog,"\n Best member: \n");

for (i = 0; i < NVARS; i++)
   {
   fprintf (galog,"\n var(%d) = %3.9f",i,population[POPSIZE].gene[i]);
   }
fprintf(galog,"\n\n Best fitness = %3.9f",population[POPSIZE].fitness);
fclose(galog);
printf("Success\n");

//
}
/***************************************************************/