addmp_eval.cpp

Multi-objective evolutionary algorithm - an application

/*

   addmp_eval.cc --- The evaluation function for the Adaptive Distributed 
                   Database Management Problem (ADDMP) for use in a 
                   multiobjective EA or other optimization algorithm.

                   See J. Knowles, M. Oates, and D. Corne  "Advanced Multiobjective Evolutionary
                   Algorithms Applied to two Problems in Telecommunications", BT Technology
                   Journal, 2000,18(4), pp. 51-65, October for further details.

        To test:   gcc addmp_eval.cc -o addmp_eval.o
                   ./addmp_eval.o

                   should return: 25.681260 13.968652 9.127496

		   Edit the main function to call the evaluation function with 
		   different genotypes. Recompile and run.

	To use:	   1. Remove "main".
                   Then compile this source file and use a Makefile to build the resulting
                   object file into your optimization algorithm. Or simply cut and paste
                   this file (with main removed) into your existing optimization algorithm source code. 

                   2. The program uses separate files for reading in the
                   particular database scenario. Edit the function 
                   read_adb_data() so that it calls the correct database
                   scenario. It is currently setup to read scenario "sc10".
                   The other scenarios used in the above journal article
                   are also available from the authors.

                   3. The program can calculate a 2-objective evaluation or
                   a 3-objective evaluation.  
                   Call the function addmp(int num_genes, int num_obj, int *genotype, double *eval) from
                   your optimization algorithm with the arguments:
                   
                   num_genes = number of genes = number of client/servers
                   num_obj = number of objectives = 2 or 3  
                   *genotype = pointer to an array storing the genotype
                   *eval = pointer to an array storing the evaluation vector

                   The function will update the values of the eval array appropriately.
                   --------------------------------------------------------------------------


   Copyright (C) 2000, Martin Oates, David Corne and Joshua Knowles

/*
 *
 * The program Uses Peter Ross' getint etc functions.
 */


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

#define GDTRUE 1
#define GDFALSE 0

int nodes;                  /* number of nodes in the comms network */
double *btt;                /* array of base transaction times in ms */
double *crt;                /* client retrieval rates */
double *cur;                /* client update rates */
double *col;                /* client overlaps */
double *bcomms;             /* base comms table */
double *otr;                /* overall transaction rate per client */
double *acomms;             /* active comms table */
double *cod;                /* communication overhead delays */
double scr;                 /* server contention rate */
double mrr;                 /* maximum retrieval rate */
int geno_size;
int biggest_allele;

char datafilename[50];

int read_adb_data();  // reads the data  == datafile at the end 
double getdouble(FILE *, double *, int); // used by read_adb_data 
double eval_adb(int *, double *one, double *two); //  the eval function 
double min(double,double); // used in eval_adb 
double max(double,double);
void addmp(int num_genes, int num_obj, int *genotype, double *eval);
double eval_adb3(int *genotype, double *one, double *two, double *third);
void shell_sort(double *ptr, int count);

void main()
{
  int ng=10;
  int g[20];
  int nobj=3;
  double obj[3];
 
  g[0]=1;
  g[1]=2;
  g[2]=0;
  g[3]=1;
  g[4]=2;
  g[5]=8;
  g[6]=3;
  g[7]=9;
  g[8]=5;
  g[9]=1;

  addmp(ng, nobj, g, obj);
  
  printf("%f %f %f\n", obj[0], obj[1], obj[2]);
}

void addmp(int num_genes, int num_obj, int *genotype, double *eval)
{
  static int j = 0;
  double first, second, third;

  if(!j)
      read_adb_data();

  if (num_obj==2)
    eval_adb(genotype, &first, &second);
  else if (num_obj==3)
    eval_adb3(genotype, &first, &second, &third);
  if (first>1000)
      {  
	 first = 1000.0;
	 second = 1000.0;
	 third = 1000.0;
      }
  eval[0] = first;
  eval[1] = second;
  if (num_obj==3)
    eval[2] = third;
 
  j++;
}

/***************************************************************/
/* Get the next number from the input: put it in the location  */
/* addressed by second argument. This function returns 0 on    */
/* EOF. If stopateol is true, it returns -1 when it hits \n    */
/* (after which some other procedure has to read past the \n), */
/* otherwise it continues looking for the next number.         */
/* A number has an optional sign, perhaps followed by digits,  */
/* perhaps followed by a decimal point, perhaps followed by    */
/* more digits. There must be a digit somewhere for it to count*/
/* as a number. So it would read any of:                       */
/*  -.5                                                        */
/*  -0.5                                                       */
/*  -.5.7                                                      */
/* as minus-a-half. In the last case, it would read .7 next    */
/* time around.                                                */
/*   There doesn't seem to be a neat and reliable way to do    */
/* all this, including stopateol, using scanf?                 */
/***************************************************************/

double getdouble(FILE * file, double *valaddr, int stopateol)
{
  int c;
  int found = GDFALSE, indecimal = GDFALSE;
  int sign = +1;
  double n = 0.0, p = 1.0;

  do 
	{
    c = fgetc(file);
    if (c == EOF)
      return (0);
    else if (stopateol && c == '\n')
      return (-1);
    else if (c == '+' || c == '-') 
		{
      sign = (c == '+') ? +1 : -1;
      c = fgetc(file);
      if (c == EOF)
				return (0);
      else if (stopateol && c == '\n')
				return (-1);
    }
    if (c == '.') 
		{
      indecimal = GDTRUE;
      c = fgetc(file);
      if (c == EOF)
				return (0);
      else if (stopateol && c == '\n')
				return (-1);
    }
    if (c >= '0' && c <= '9') 
		{
      found = GDTRUE;
    } else {
      sign = +1;
      indecimal = GDFALSE;
    }
  } while (!found);
  do 
	{
    n = 10.0 * n + c - '0';
    p = 10.0 * p;
    c = fgetc(file);

    if ((c < '0') || (c > '9')) 
		{
      found = GDFALSE;
      if (indecimal) 
			{
				if (c != EOF)
					ungetc(c, file);
				*valaddr = sign * n / p;
				return (1);
      } 
			else
				p = 1.0;
    }
  }while (found);

  if (c != '.') 
	{
    if (c != EOF)
      ungetc(c, file);
    *valaddr = sign * n;
    return (1);
  } else 
	{
    /* It is. Step past it, carry on hoping for more digits */
    c = fgetc(file);
    while (c >= '0' && c <= '9') 
		{
      n = 10.0 * n + c - '0';
      p = p * 10.0;
      c = fgetc(file);
    }
    if (c != EOF)
      ungetc(c, file);
    *valaddr = sign * n / p;
    return (1);
  }
}

// Use getdouble() above but convert result to int.
int getint(FILE * f, int *valaddr, int stopateol)
{
  int r;
  double x;
  r = (int)getdouble(f, &x, stopateol);
  *valaddr = (int) x;
  return (r);
}

// For adaptive database problem 
int read_adb_data(void)
{
   FILE *f;
   int i,j;
   double in;

	if ((f = fopen("sc10", "r")) != (FILE *) NULL) 
	{
		getint(f,&nodes,GDFALSE);
	}
	else 
	{
		fprintf(stderr, "can't open data file\n"); exit(0);
	}
  btt = (double *)malloc(nodes*sizeof(double));

	for(i=0;i<nodes;i++)
  {
		getdouble(f,&in,GDFALSE); btt[i]=in;
  }
	crt =  (double *)malloc(nodes*sizeof(double));
	cur =  (double *)malloc(nodes*sizeof(double));
	col =  (double *)malloc(nodes*sizeof(double));
  for(i=0;i<nodes;i++)
  {
		getdouble(f,&in,GDFALSE); crt[i]=in;
    getdouble(f,&in,GDFALSE); cur[i]=in;
    getdouble(f,&in,GDFALSE); col[i]=in;
  }
  /* now for the base comms table */
	bcomms = (double *)malloc(nodes*nodes*sizeof(double));

	for(i=0;i<nodes;i++)
  for(j=0;j<nodes;j++)
  {
		getdouble(f,&in,GDFALSE); bcomms[nodes*i + j]=in;
	}
  getdouble(f,&scr,GDFALSE);
  fclose(f);
  getdouble(f,&mrr, GDFALSE);
  /* do some book-keeping and set up arrays to be used in evaluation */
  otr = (double *) malloc(nodes*sizeof(double));
  acomms = (double *) malloc(nodes*nodes*sizeof(double));
  cod = (double *) malloc(nodes*nodes*sizeof(double));
  geno_size = nodes;
  biggest_allele = nodes-1;
	return 1;
}

double eval_adb(int *genotype, double *one, double *two)
{
	int i,j, nservers, serv[2000];
  double respr, tserv[2000], worst, median, htr, str, ttr;

			      
  /* calculate overall transaction rate per client */
  
  /* otr[i] will hold the overall transaction rate of client i */