movpeaks.cpp

多目标优化进化算法目前公认效果收敛性最好的算法NSGA2c++源码,具有一般性

/* Moving Peaks Function --- 10/99 */



/* movpeaks.c
 * Copyright (C) 1999 Juergen Branke.
 * This is free software; you can redistribute it and/or modify it under the
 * terms of the GNU General Public License.
 *
 * This module generates the Moving Peaks Evaluation Function, a
 * dynamic benchmark problem changing over time.
 */

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include "movpeaks.h"

/***** PARAMETER SETTINGS *****/

int change_frequency = 0; /* number of evaluations between changes. change_frequency
		       =0 means that function never changes (or only if function change_peaks is called)*/

unsigned long int movrandseed = 1; /* seed for built-in random number generator */

int geno_size = 5;  /* number of dimensions, or the number of double 
                          valued genes */
double vlength = 1.0; /* distance by which the peaks are moved, severity */

double height_severity=15.0; /* severity of height changes, larger numbers
                               mean larger severity */
double width_severity = 3.0; /* severity of width changes, larger numbers
                               mean larger severity */

/* lambda determines whether there is a direction of the movement, or whether
   they are totally random. For lambda = 1.0 each move has the same direction,
   while for lambda = 0.0, each move has a random direction */
double lambda=0.0;

int number_of_peaks = 50; /* number of peaks in the landscape */

int use_basis_function=1; /* if set to 1, a static landscape (basis_function) is included in the fitness evaluation */

int calculate_average_error=1; /* saves computation time if not needed and set to 0 */
int calculate_offline_performance = 1; /* saves computation time if not needed and set to 0 */
int calculate_right_peak = 1; /* saves computation time if not needed and set to 0 */

/* minimum and maximum coordinate in each dimension */
double mincoordinate = 0.0, maxcoordinate = 100.0;
/* minimum and maximum height of the peaks          */
/* height chosen randomly when standardheight = 0.0 */
double minheight = 30.0, maxheight = 70.0, standardheight = 50.0;
/* width chosen randomly when standardwidth = 0.0 */
double minwidth = 1.0, maxwidth = 12.0, standardwidth = 0.0; 


/* Functions */
/* evaluation function */
double eval_movpeaks (double *gen);

/* the following basis functions are provided :*/
double constant_basis_func(double *gen);
double five_peak_basis_func(double *gen);
/* the following peak functions are provided: */
double peak_function1(double *gen, int peak_number);
double peak_function_cone (double *gen, int peak_number);
double peak_function_hilly (double *gen, int peak_number);
double peak_function_twin (double  *gen, int peak_number);


/* allows to set the basis function used */
double (*basis_function) (double *gen)= constant_basis_func;
/* defines the form of a single peak */
double (*peak_function) (double *gen, int peak_number)=peak_function_cone;


/****** END OF PARAMETER SECTION *******************/

void change_peaks();   /* preliminary declaration of function change_peaks()*/
int recent_change = 1; /* indicates that a change has just ocurred */
int current_peak;      /* peak on which the current best individual is located */
int maximum_peak;       /* number of highest peak */
double current_maximum; /* fitness value of currently best individual */ 
double offline_performance = 0.0;
double offline_error = 0.0;
double avg_error=0;    /* average error so far */ 
double current_error=0;/* error of the currently best individual */
double global_max;     /* absolute maximum in the fitness landscape */
int evals = 0;         /* number of evaluations so far */
double **peak;         /* data structure to store peak data */
double *shift;
double *coordinates;
int *covered_peaks;    /* which peaks are covered by the population ? */

double **prev_movement;/* to store every peak's previous movement */


double movrand();
double movnrand();

double dummy_eval (double *gen); 

/* initialize all variables at the beginning of the program */
void init_peaks ()
{
  int i,j;
  double dummy;
  
recent_change = 1; /* indicates that a change has just ocurred */
offline_performance = 0.0;
offline_error = 0.0;
avg_error=0;    /* average error so far */ 
current_error=0;
evals = 0;   
movrandseed = 1;

  shift = (double *) calloc(geno_size, sizeof(double));
  coordinates = (double *) calloc(geno_size, sizeof(double));
  covered_peaks = (int *) calloc(number_of_peaks, sizeof(int));
  peak = (double **) calloc(number_of_peaks, sizeof(double*));
  prev_movement = (double **) calloc(number_of_peaks, sizeof(double*));
  for (i=0; i< number_of_peaks; i++){
    peak[i]= (double *) calloc(geno_size+2, sizeof(double));
    prev_movement[i] = (double *) calloc(geno_size, sizeof(double));
  }
  for (i=0; i< number_of_peaks; i++)
    for (j=0; j< geno_size; j++){
      peak[i][j] = 100.0*movrand();
      prev_movement[i][j] = movrand()-0.5;
    }
  if (standardheight <= 0.0)
    for (i=0; i< number_of_peaks; i++)
      peak[i][geno_size+1]= (maxheight-minheight)*movrand()+minheight;
  else
    for (i=0; i< number_of_peaks; i++)
      peak[i][geno_size+1]= standardheight;
  if (standardwidth <= 0.0)
    for (i=0; i< number_of_peaks; i++)
      peak[i][geno_size]= (maxwidth-minwidth)*movrand()+minwidth;
  else
    for (i=0; i< number_of_peaks; i++)
      peak[i][geno_size]= standardwidth;
  if(calculate_average_error){
    global_max = -100000.0;
    for (i=0;i<number_of_peaks; i++){
      for (j=0; j<geno_size; j++)
        coordinates[j]=peak[i][j];
      dummy = dummy_eval(coordinates);
      if (dummy>global_max)
        global_max = dummy;
    }
  }
}



/* free disc space at end of program */
void free_peaks()
{
  int i;

  for (i=0; i< number_of_peaks; i++){
    free(peak[i]);
    free(prev_movement[i]);
  }
}

/* current_peak_calc determines the peak of the current best individual */
void current_peak_calc (double *gen)
{
  int i;
  double maximum = -100000.0, dummy;

  current_peak = 0;
  maximum = peak_function(gen, 0);
  for(i=1; i<number_of_peaks; i++){
    dummy = peak_function(gen, i);
    if (dummy > maximum){
      maximum = dummy;
      current_peak = i;
    }
  }
}


/* evaluation function */
double eval_movpeaks (double *gen)
{
  int i;
  double maximum = -100000.0, dummy;

  if ((change_frequency > 0)&&(evals%change_frequency==0))
    change_peaks();

  for(i=0; i<number_of_peaks; i++)
    {
    dummy = peak_function(gen, i);
    if (dummy > maximum)
      maximum = dummy;
    }

  if (use_basis_function) {
    
    dummy = basis_function(gen);
    /* If value of basis function is higher return it */
    if (maximum < dummy)
      maximum = dummy;
  }
  if (calculate_average_error){
    avg_error+=global_max - maximum;
  }
  if (calculate_offline_performance){
    if(recent_change||(maximum > current_maximum)){
      current_error = global_max - maximum;
      if (calculate_right_peak)
	current_peak_calc(gen);
      current_maximum = maximum;
      recent_change = 0;
    }
    offline_performance += current_maximum;
    offline_error += current_error;
  }
  evals ++;     /* increase the number of evaluations by one */
  return(maximum);
}

/* dummy evaluation function allows to evaluate without being counted */
double dummy_eval (double *gen)
{
  int i;
  double maximum = -100000.0, dummy;

  for(i=0; i<number_of_peaks; i++)
    {
    dummy = peak_function(gen, i);
    if (dummy > maximum)
      maximum = dummy;
    }

  if (use_basis_function) {
    
    dummy = basis_function(gen);
    /* If value of basis function is higher return it */
    if (maximum < dummy)
      maximum = dummy;
  }
  return(maximum);
}

/* simple random number generator solely for the test function */
/* movrand creates random number between 0 and 1 */
/* This RNG is taken from the book by Kernighan/Ritchie, maybe it would */
/* be worth to try a better one. */

double movrand ()
{
  /*  static unsigned long int next;*/
  movrandseed = movrandseed* 1103515245 + 12345;
  return (double)((unsigned int)(movrandseed/65536)%32768)/32767;
}

/* this function produces normally distributed random values */ 
double movnrand() 
{ static int backup=0;
  static double x2;
  double x1, w;
 
  if (backup){
    backup = 0;
    return (x2);
  }  else {
    do
    { x1 = 2.0 * movrand() - 1.0;
      x2 = 2.0 * movrand() - 1.0;
      w = x1*x1 + x2*x2;
    } while ( w>=1.0 );
    w = sqrt( (-2.0*log(w) ) / w );
    x2 = w*x2;
    backup = 1;
    return (x1*w);
  }
}


/* whenever this function is called, the peaks are changed */ 
void change_peaks() 
{
  int i,j;
  double sum, sum2, offset, dummy;

  for(i=0; i<number_of_peaks; i++)
    {
      /* shift peak locations */
    sum = 0.0;
    for (j=0; j<geno_size; j++){
      shift[j]=movrand()-0.5;
      sum += shift[j]*shift[j];
      }
    if(sum>0.0)                 
      sum = vlength/sqrt(sum);
    else                           /* only in case of rounding errors */
      sum = 0.0;
    sum2=0.0;
    for (j=0; j<geno_size; j++){
      shift[j]=sum*(1.0-lambda)*shift[j]+lambda*prev_movement[i][j];
      sum2 += shift[j]*shift[j];
    }
    if(sum2>0.0)                 
      sum2 = vlength/sqrt(sum2);
    else                           /* only in case of rounding errors */
      sum2 = 0.0;
    for(j=0; j<geno_size; j++){
      shift[j]*=sum2;
      prev_movement[i][j]= shift[j];
      if ((peak[i][j]+prev_movement[i][j]) < mincoordinate){
        peak[i][j] = 2.0*mincoordinate-peak[i][j]-prev_movement[i][j];
        prev_movement[i][j]*=-1.0;
      }
      else if ((peak[i][j]+prev_movement[i][j]) > maxcoordinate){
        peak[i][j]= 2.0*maxcoordinate-peak[i][j]-prev_movement[i][j];
        prev_movement[i][j]*=-1.0;
      }
      else
        peak[i][j] += prev_movement[i][j];    
      }
    /* change peak width */
    j = geno_size;
    offset = movnrand()*width_severity;
    if ((peak[i][j]+offset) < minwidth)
      peak[i][j] = 2.0*minwidth-peak[i][j]-offset;
    else if ((peak[i][j]+offset) > maxwidth)
      peak[i][j]= 2.0*maxwidth-peak[i][j]-offset;
    else
      peak[i][j] += offset;
   /* change peak height */
    j++;
    offset = height_severity*movnrand();
    if ((peak[i][j]+offset) < minheight)
      peak[i][j] = 2.0*minheight-peak[i][j]-offset;
    else if ((peak[i][j]+offset) > maxheight)
      peak[i][j]= 2.0*maxheight-peak[i][j]-offset;
    else
      peak[i][j] += offset;    
  }
  if(calculate_average_error){
    global_max = -100000.0;
    for (i=0;i<number_of_peaks; i++){
      for (j=0; j<geno_size; j++)
        coordinates[j]=peak[i][j];
      dummy = dummy_eval(coordinates);
      if (dummy>global_max){
        global_max = dummy;
        maximum_peak = i;
      }
    }
  }
  recent_change = 1;
}


/* Basis Functions */

/* This gives a constant value back to the eval-function that chooses the max of them */
double constant_basis_func(double *gen)
{
  return 0.0;
}

double five_peak_basis_func(double *gen)
{
  int i,j;
  double maximum = -100000.0, dummy;
  static double basis_peak [5] [7] = 
  {
    8.0,  64.0,  67.0,  55.0,   4.0, 0.1, 50.0,
   50.0,  13.0,  76.0,  15.0,   7.0, 0.1, 50.0,
    9.0,  19.0,  27.0,  67.0,  24.0, 0.1, 50.0,
   66.0,  87.0,  65.0,  19.0,  43.0, 0.1, 50.0,
   76.0,  32.0,  43.0,  54.0,  65.0, 0.1, 50.0,
  };
  for(i=0; i<5; i++)
    {
      dummy = (gen[0]-basis_peak[i][0])*(gen[0]-basis_peak[i][0]);
      for (j=1; j< geno_size; j++)
	dummy += (gen[j]-basis_peak[i][j])*(gen[j]-basis_peak[i][j]); 
      dummy = basis_peak[i][geno_size+1]-(basis_peak[i][geno_size]*dummy);
      if (dummy > maximum)
        maximum = dummy;
    }
  return maximum;
}
  


/* Peak Functions */

/* sharp peaks */
double peak_function1 (double *gen, int peak_number)
{
  int j;
  double dummy;

  dummy = (gen[0]-peak[peak_number][0])*(gen[0]-peak[peak_number][0]); 
  for (j=1; j< geno_size; j++)
    dummy += (gen[j]-peak[peak_number][j])*(gen[j]-peak[peak_number][j]); 
  return peak[peak_number][geno_size+1]/(1+(peak[peak_number][geno_size])*dummy);
}

double peak_function_cone (double *gen, int peak_number)
{
  int j;
  double dummy;

  dummy =  (gen[0]-peak[peak_number][0])*(gen[0]-peak[peak_number][0]); 
  for (j=1; j< geno_size; j++)
    dummy += (gen[j]-peak[peak_number][j])*(gen[j]-peak[peak_number][j]); 
  return peak[peak_number][geno_size+1]-(peak[peak_number][geno_size]*sqrt(dummy));
}

double peak_function_hilly (double *gen, int peak_number)
{
  int j;
  double dummy;

  dummy =  (gen[0]-peak[peak_number][0])*(gen[0]-peak[peak_number][0]); 
  for (j=1; j< geno_size; j++)
    dummy += (gen[j]-peak[peak_number][j])*(gen[j]-peak[peak_number][j]); 
  return peak[peak_number][geno_size+1]-(peak[peak_number][geno_size]*dummy)-0.01*sin(20.0*dummy);
}

double peak_function_twin (double  *gen, int peak_number) /* two twin peaks moving together */
{
  int j;
  double maximum = -100000.0, dummy;
  static double twin_peak [7] = /* difference to first peak */
  {
    1.0,  1.0,  1.0,  1.0,   1.0, 0.0, 0.0,
  };
  
  dummy = pow(gen[0]-peak[peak_number][0],2);
  for (j=1; j< geno_size; j++)
     dummy += pow(gen[j]-peak[peak_number][j],2); 
  dummy = peak[peak_number][geno_size+1]-(peak[peak_number][geno_size]*dummy);
  maximum = dummy;
  dummy = pow(gen[j]-(peak[peak_number][0]+twin_peak[0]),2);
  for (j=1; j< geno_size; j++)
     dummy += pow(gen[j]-(peak[peak_number][j]+twin_peak[0]),2); 
  dummy = peak[peak_number][geno_size+1]+twin_peak[geno_size+1]-((peak[peak_number][geno_size]+twin_peak[geno_size])*dummy);
  if (dummy > maximum)
    maximum = dummy;
  
  return maximum;
}  

/* The following procedures may be used to change the step size over time */


void change_stepsize_random () /* assigns vlength a value from a normal distribution */
{ 
  vlength = movnrand();
}
  
void change_stepsize_linear() /* sinusoidal change of the stepsize, */
{
  static int counter = 1;
  static double frequency = 3.14159/20.0;  /* returns to same value after 20 changes */

  vlength = 1+ sin((double)counter*frequency);
  counter ++;
}

double get_avg_error() /* returns the average error of all evaluation calls so far */
{
  return (avg_error/(double)evals);
}

double get_current_error() /* returns the error of the best individual evaluated since last change */
     /* To use this function, calculate_average_error and calculate_offline_performance must be set */
{
  return current_error;
}

double get_offline_performance() /* returns offline performance */
{
  return (offline_performance/(double)evals);
}

double get_offline_error() /* returns offline error */
{
  return (offline_error/(double)evals);
}


int get_number_of_evals() /* returns the number of evaluations so far */
{
  return evals;
}

int get_right_peak()  /* returns 1 if current best individual is on highest peak, 0 otherwise */
{
  if (current_peak == maximum_peak)
    return 1;
  else
    return 0;
}