paes.c

多目标优化算法PAES的c语言源代码,q希望对你有用.

// (1+1)-PAES skeleton program code 
/* 
   Copyright (C) 2000, Joshua Knowles and David Corne

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version. 

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details. 

   The GNU General Public License is available at:
      http://www.gnu.org/copyleft/gpl.html
   or by writing to: 
        The Free Software Foundation, Inc., 
        675 Mass Ave, Cambridge, MA 02139, USA.  

*/
//
// PAES is described in several refereed publications. All of them are available 
// for download from Joshua Knowles' website at The University of Reading:
// http://www.reading.ac.uk/~ssr97jdk
//
// Please contact the authors if you have any comments, suggestions or questions
// about this file or the Pareto Archived Evolution Strategy (PAES).
// We are at:
// [e-mail]  and  [e-mail] 
//
/*********************************************************************************************************
 * To compile : gcc paes.cc -o paes -lm                                                                  *
 * To run :                                                                                              * 
 *  ./paes [problem] [depth] [objectives] [genes] [alleles] [archive] [iterations] [minmax] [pm] [seed]  *
 *                                                                                                       *
 * where all parameters MUST be specified correctly (none are optional) following the instructions below:*
 *                                                                                                       *
 * [problem] - at present there are 3 problems included with this code. They are max, T1, and F5. See    *
 *             below for further details on each of these problems.                                      *
 * [depth] - this is the number of recursive subdivisions of the objective space carried out in order to *
 *           divide the objective space into a grid for the purposes of diversity maintenance. Values of *
 *           between 3 and 6 are useful, depending on number of objectives. //目标空间划分...            * 
 * [objectives] - the number of objectives to the problem.                                               *
 * [genes] - the number of genes in the chromosome. (Only integer genes can be accepted).                *
 * [alleles] - the number of values that each gene can take. //等位基因                                  *
 * [archive] - the maximum number of solutions to be held in the nondominated solutions archive.         *
 * [iterations] - the program terminates after this number of iterations.  //循环次数                    *
 * [minmax] - set this to 0 (zero) for minimization problems, 1 for maximization problems.  //最小、最大 *
 * [pm] - the per gene mutation probability. Mutations always change the current allele. Any other       *
 *        viable allele is chosen, with uniform probability.   // 变异概率                               *
 * [seed] - any integer value, to be used as the program's random seed.                                  *
 *                                                                                                       *
 * Example command lines:                                                                                *
 * ./paes max 4 3 20 4 50 10000 1 0.05 3434324   - a valid command line for the max problem              *
 * ./paes T1 5 2 900 2 100 20000 0 0.002 6764421 - a valid command line for the T1 problem               *
 * ./paes F5 4 2 16 16 25 50000 0 0.06 764542    - a valid command line for the F5 problem               *
 *                                                                                                       *
 * The objective function for 3 multiobjective test functions is included in the code.                   *
 *                                                                                                       *
 * The first test function, "max", is a k-objective problem taking a chromosome of k+1 alleles per gene. *
 * It returns, for each objective, the fraction of the chromosome consisting of allele values            *
 * corresponding to the particular objective. i.e. objective 1 counts the number of 1's in the chromosome*
 * and returns this normalized wrt to the length of the chromosome. Similarly for objectives 2, 3, ...   *
 * Zeros in the chromosome do not contribute to any of the objectives. When using the max problem the    *
 * number of alleles must be set to the number of objectives + 1. The problem is a maximization problem  *
 * hence the parameter minmax must be set to 1.                                                          *
 *                                                                                                       *
 * The second objective function, "T1", has been taken from Eckart Zitzler's PhD thesis,                 *
 * Diss. ETH No. 13398 currently available from http://www.tik.ee.ethz.ch/~zitzler/                      *
 * The function is a simple 2-objective minimization                                                     * 
 * problem. The Pareto optimal front is given by 1-sqrt(x) with 1<=x<=0. The code has been written so    *
 * that a chromosome of 900 binary genes is expected, encoding for 30 real numbers between zero and 1.   *
 *                                                                                                       *
 * The third objective function, "F5", was described in "Joshua Knowles and David Corne, The Pareto      *
 * Archived Evolution Strategy: A New Baseline Algortihm for Multiobjective Optimisation, in Proceedings *
 * of the 1999 Congress on Evolutionary Computation (CEC99), pages 98-105, IEEE Service Centre".         *
 * It is a 2-objective problem which accepts a chromosome of k-genes each having k alleles. Briefly the  *
 * function counts the number of adjacent genes having consecutive alleles, reading the chromosome       *
 * forwards (objective 1) and backwards (objective 2). There are k distinct optima in objective space    *
 * but the disribution of these optima in parameter space is highly nonuniform i.e. there are many ways  *
 * of obtaining some of the optima (they are easy to find) and very few ways of finding others.          *
 * The problem is cast as a minimization problem. For a chromosome of 16 genes with 16 alleles the       *
 * problem is already very difficult.                                                                    *
 *                                                                                                       *
 * In the code presented here, maintenance of diversity is carried out in the objective space. i.e.      *
 * solutions which are genetically different but which give rise to the same objective values are not    *
 * allowed to co-exist in the archive. The grid used for maintaining diversity also takes into account   *
 * objective values only. Parameter-space, and genotypic measures of diversity may also be used with     *
 * PAES but they have not been included in this skeleton code.                                           *              
 *                                                                                                       *
 ********************************************************************************************************/
 

# include <stdlib.h>
# include <stdio.h>
# include <math.h>
# include <string.h>

# define MAX_GENES 1000  // change as necessary
# define MAX_OBJ 10     // change as necessary 
# define MAX_POP 10     // change as necessary
# define MAX_ARC 200    // change as necessary
# define MAX_LOC 32768  // number of locations in grid (set for a three-objective problem using depth 5)
# define LARGE 2000000000 // should be about the maximum size of an integer for your compiler 

FILE *fp;

typedef struct solution
{
  int chrom[MAX_GENES];
  double obj[MAX_OBJ];
  int grid_loc;       //
}sol;

sol *c; // current solution
sol *m; // mutant solution
sol *arc; // archive of solutions

int compare_min(double *first, double *second, int n);
int compare_max(double *first, double *second, int n);
int equal(double *first, double *second, int n);
void init();
void print_genome(sol *s);
void print_eval(sol *s);
void evaluate(sol *s, char *problem);
void max(sol *s);
void T1(sol *s);
void F5(sol *s);
void add_to_archive(sol *s);
void mutate(sol *s);
int compare_to_archive(sol *s);
void update_grid(sol *s);
void archive_soln(sol *s);
int find_loc(double *eval);

double pm;  // mutation rate as a decimal probability per bit (zero probability of generating current allele, uniform probability of generating all other allele values. i.e. for binary chromosomes this is the "flip" mutation rate.) 
int seed, depth, genes, alleles, archive, objectives, iterations, minmax; // command line parameters 
int arclength=0; // current length of the archive

double gl_offset[MAX_OBJ];   // the range, offset etc of the grid 
double gl_range[MAX_OBJ];
double gl_largest[MAX_OBJ];
int grid_pop[MAX_LOC];   // the array holding the population residing in each grid location


char problem[50];


int main(int argc, char *argv[])
{

  int i, j;
  int result;

  if (argc!=11)
    {
      printf("See paes.cc for command line parameters. Exiting.\n");
      exit(-1);
    }

  //get command line parameters

  sprintf(problem, "%s", argv[1]);
  depth = atoi(argv[2]);
  objectives = atoi(argv[3]);
  genes = atoi(argv[4]);
  alleles = atoi(argv[5]);
  archive = atoi(argv[6]);
  iterations = atoi(argv[7]);
  minmax = atoi(argv[8]);
  pm = atof(argv[9]);
  seed = atoi(argv[10]);

  srand(seed); // seed system random number generator

  // begin (1+1)-PAES
  
  init();

  //  print_genome(c);    // Uncomment to check genome is correct 

  evaluate(c, problem);

  //  print_eval(c);      // Uncomment to check objective values generated

  //  getchar();  

  add_to_archive(c);
  
  // begin main loop
  for (i = 0; i < iterations; i++)
    {
      if (i%100==0)            // just print out the number of iterations done every 100
		  printf("%d\n", i);
      *m = *c;   // copy the current solution 
      mutate(m);  // and mutate using the per-bit mutation rate specified by the command param pm

      //   print_genome(m);
      evaluate(m, problem);
 
      //print_eval(m);

      // print_genome(m);

      //  printf("Comparing ");
      //print_eval(c); 
      // printf("and ");
      //print_eval(m);
      
      //MINIMIZE MAXIMIZE
      if (minmax==0)
		  result = compare_min(c->obj, m->obj, objectives);
      else
		  result = compare_max(c->obj, m->obj, objectives);

      // printf("RESULT = %d\n", result);
      // printf("arclength = %d\n", arclength);
      
      if (result != 1)  // if mutant is not dominated by current (else discard it)
	  {
		  if (result ==-1)  // if mutant dominates current
		  {
			  //printf("m dominates c\n");
			  update_grid(m);           //calculate grid location of mutant solution and renormalize archive if necessary
			  archive_soln(m);          //update the archive by removing all dominated individuals
			  *c = *m;                    // replace c with m
		  }
		  else if(result == 0)  // if mutant and current are nondominated wrt each other
		  {
			  result = compare_to_archive(m);
			  if (result != -1)  // if mutant is not dominated by archive (else discard it)
			  {
				  update_grid(m);
				  archive_soln(m);
				  if((grid_pop[m->grid_loc] <= grid_pop[c->grid_loc])||(result==1)) // if mutant dominates the archive or 
				  {                                                               // is in less crowded grid loc than c  
					  *c = *m; // then replace c with m
				  }
			  }
		  }      
	  } 
      
	  /*  printf("\nArchive = \n");
      for (j = 0; j < arclength; j++)
      print_eval(&arc[j]);
	  getchar();*/
  }
  printf("\nThe Archive is now... \n");
  for (i = 0; i < arclength; i++)
	  print_eval(&arc[i]);
 
  /*  printf("\nThe genetic material in the archive is now... \n");
   for (i = 0; i < arclength; i++)
	 print_genome(&arc[i]);
    */

}

int compare_to_archive(sol *s)  // compares a solution to every member of the archive. Returns -1 if 
                                //dominated by any member, 1 if dominates any member, and 0 otherwise
{                          
  int i=0;                      //只要找到支配或被支配的就跳出
  int result=0;

  while((i<arclength)&&(result!=1)&&(result!=-1))
  {
	  //MINIMIZE MAXIMIZE
      if (minmax==0)
		  result = compare_min(m->obj, (&arc[i])->obj, objectives);
      else
		  result = compare_max(m->obj, (&arc[i])->obj, objectives);
      i++;
  }
  return(result);
}
      
void init()  
{
  int i;
  int val;

  // allocate memory for solutions
  c = (sol *)malloc(MAX_POP*sizeof(sol));
  m = (sol *)malloc(MAX_POP*sizeof(sol));
  arc = (sol *)malloc(MAX_ARC*sizeof(sol));

  if((!c)||(!m)||(!arc))
  {
      printf("Out of memory. Aborting.\n");
      exit(-1);
  }

  // initialize c with a uniform distribution of values from 0 to alleles-1
  for (i = 0; i < genes; i++)
  {
      val = (int)(alleles*(rand()/(RAND_MAX+1.0)));   
      c->chrom[i] = val;
  }
}

void add_to_archive(sol *s)
{
  arc[arclength] = *s;
  arclength++;
}

void mutate(sol *s)  // apply mutation to chromosome s using per-gene mutation probability pm.  
{
  int i;
  int var;

  for (i = 0; i < genes; i++)   //对每一基因都变异
  {
      if ((rand()/(RAND_MAX+1.0))<pm)
	  {
		  var = 1+(int)((alleles-1)*(rand()/(RAND_MAX+1.0)));  // generate var between 1 and alleles-2 ...
		  s->chrom[i]=(s->chrom[i]+var)%alleles;  // add var to allele value of current gene and mod.  
	  }
  }
}

void print_genome(sol *s)
{
  int i;
  for (i = 0; i < genes; i++)
	  printf("%d ", s->chrom[i]);
  printf("\n");    
}

void print_eval(sol *s)
{
  int i;
  for (i = 0; i < objectives; i++)
	  printf("%lf ", s->obj[i]);
  printf("\n");
}

void evaluate(sol *s, char *problem)
{
  if (!strcmp(problem, "T1"))
    { 
      T1(s);    // this is a function described in 
                // Diss. ETH No. 13398 (Eckart Zitzler's PhD Thesis) 
                // available from http://www.tik.ee.ethz.ch/~zitzler/
    }
  else if (!strcmp(problem, "max"))
    {
      max(s);
    }

  else if (!strcmp(problem, "F5"))
    {
      F5(s);
    }
  // else if (!strcmp(problem, "*&^%*%"))
  // call your other evaluation functions from here

  else
    {
      printf("Invalid argument for test problem given. Exiting.\n");
      exit(-1);
    }
}

void max(sol *s)
{
  int i, j;
  double sc[MAX_OBJ+1];

  if (alleles != objectives+1)
    {
      printf("You've given invalid command line parameters for function max. Check paes.c for details. Exiting.\n");
      exit(-1);
    }
  
  for (i = 0; i < objectives; i++)
    sc[i]=0;

  for (i = 0; i < genes; i++)    //目标1放1出现的次数...依次类推
    sc[s->chrom[i]]++; 
  
  for (i = 1; i <= objectives; i++)
    {
      sc[i] /= (double)genes;    //除于基因总数 比例
      s->obj[i-1] = sc[i];
    }
}

void T1(sol *s)
{
  // test function T1 described in Eckart Zitzler's PhD thesis. See notes at top for further details 
  int i, j;
  int mul;
  double var[30];

  double sum = 0;
  double f1, f2, g, h;
  
  if ((genes!=900)||(alleles!=2)||(objectives!=2))    
    {