nsgaorig.c

原始非支配多目标遗传算法

   fprintf(fp,"\n======================== Generation # : %3d =================================",num);
   if (BINGA) fprintf(fp,"\n  No.   Rank         x   Obj. Fun. Values (f1,f2, etc.) Parents   String");
   else fprintf(fp,"\n  No.   Rank         x   Obj. Fun. Values (f1,f2, etc.   Parents  ");
   fprintf(fp,"\n-----------------------------------------------------------------------------");
   for (k=0; k<= pop_size-1; k++)
   {
     fprintf(fp,"\n %3d.   %3d   [%7.3f ] ",k+1,oldpop[k].front,oldpop[k].x[0]);
     for (j= 1; j<=num_var-1; j++)
       fprintf(fp,"\n              [%7.3f ] ",oldpop[k].x[j]);
     for (j=0;j<num_obj;j++) fprintf(fp," %9.3f ", oldpop[k].fitness[j]);
     fprintf(fp," (%3d %3d)", oldpop[k].parent1, oldpop[k].parent2);
     if (BINGA) 
     {  
	fprintf(fp,"     ");
        writechrom(oldpop[k].chrom,fp); 
     }
   }
   fprintf(fp,"\n-----------------------------------------------------------------------------");
   fprintf(fp,"\nAverage Dummy Fitness = %8.3f", dum_avg);
   for(iobj=0; iobj < num_obj; iobj++)
     fprintf(fp,"\nObj. Function #%2d: Max. Fitness = %8.3f  Min. Fitness = %8.3f  Avg. Fitness = %8.3f",iobj+1,maxf[iobj],minf[iobj],avgfitness[iobj]);
   fprintf(fp,"\nNo. of mutations = %d ;  No. of x-overs = %d",
				no_mutation,no_xover);

   fprintf(fp,"\n=============================================================================");
   fprintf(fp,"\n\n");
   
  app_report();
}

/*====================================================================
Reporting the statistics of current population ( gen. no. 'num'):
  fp is file pointer to output file.
====================================================================*/
result(fp,num)
FILE *fp;
int num;
{
  int k,j; 
  char string[30];


  if (fp == NULL) error_ptr_null(" file fp in report()");

   /* --------------------------------------*/
   /* WRITING IN THE OUTPUT FILE FOR RESULTS*/
   /* --------------------------------------*/
   fprintf(fp,"\n#============== Generation # : %3d ===========================================",num);
   if (BINGA) 
      fprintf(fp,"\n#  No.          x         Obj. Fun. Values (f1,f2,etc.)     String");
   else 
      fprintf(fp,"\n#  No.          x         Obj. Fun. Values (f1,f2,etc.)  ");
   fprintf(fp,"\n#=============================================================================");
   for (k=0; k<= pop_size-1; k++)
   {
     /* for now deb 14/8/98
    fprintf(fp,"\n %3d. x%d = [%10.3f ]  ",k+1,1,oldpop[k].x[0]);
     for (j= 1; j<=num_var-1; j++)
       fprintf(fp,"\n      x%d = [%10.3f ]   ",j+1,oldpop[k].x[j]);
       */
     for (j=0; j<num_obj; j++)
       fprintf(fp," %10.3f ", oldpop[k].fitness[j]);
     /*  if (BINGA) 
       {
	 fprintf(fp,"        ");
	 writechrom(oldpop[k].chrom,fp);
       }
     */
     fprintf(fp,"\n");
   }
   fprintf(fp,"\n#=============================================================================");
   fprintf(fp,"\n\n");
   
   app_report();
}

/*====================================================================
Releases the memory for all mallocs
====================================================================*/
free_all()
{
  int i; 
   
  for(i = 0; i < pop_size; i++) 
  {   
      free(oldpop[i].chrom); 
      free(newpop[i].chrom); 
  } 
  free(oldpop);
  free(newpop);
  select_free();
  app_free();
}

/*====================================================================
Population Fronts Created Here 

     Classifying entire population into different fronts 
     and assigning dummy fitness(dumfitness) accordingly.     

     flags as follows  :  flag = 0  for untouched
                                 1      dominated
                                 2      non-dominated
                                 3      exhausted             
====================================================================*/
MakeFronts(void)
{
  int i,j,front_index,pop_count,ijk, iobj, flagobj;
  
  for(i=0; i<pop_size; i++)                /* initializing */
    {
      oldpop[i].flag = 0;   /* making all indivs. untouched */
      oldpop[i].dumfitness = 0.0;
    }
  
  pop_count = 0;   /* for checking if all individuals are 
		      assigned a front */
  
  front_index = 1; /* first front */
  while(pop_count < pop_size)
    {
      for(j=0; j<pop_size; j++)
	{
	  if(oldpop[j].flag == 3) continue;/* already assigned
					      a front, do not consider*/
	  
	  for(i=0; i<pop_size; i++)
	    {
	      if(i == j) continue; /* one is not compared with the same */
	      
	      else if(oldpop[i].flag == 3) continue; /* already assigned*/
	      
	      else if(oldpop[i].flag == 1) continue; /* marked dominated*/
	      
	      else   /* check for domination */
		{
		  flagobj = 0;
		  for (iobj=0; iobj<num_obj && !flagobj; iobj++) 
		    if(minmax[iobj] * oldpop[j].fitness[iobj] <= minmax[iobj] * oldpop[i].fitness[iobj])
		      flagobj = 1;
		  if (flagobj == 0)
		    { oldpop[j].flag = 1; break; }
		}		  
	    }                       /*End of For loop --i--*/
	  
	  if(oldpop[j].flag == 0)  /* non-dominated solutions */
	    {
	      oldpop[j].flag = 2 ;
	      pop_count++ ;
	    }
	}                           /*End of For loop --j--*/
      
      if(front_index == 1)
	{                      /* all in first front are assigned a
                                  dummy fitness = popsize */
	  for(i=0; i<pop_size; i++)
	    if(oldpop[i].flag == 2) 
	      {
		oldpop[i].dumfitness = init_dum;
	        oldpop[i].front = front_index;
	      }
	  
	  phenoshare();  /*Phenotypic sharing of non-dominated strings*/
	  
	  minimum_dum();        /* Finding minimum dummy-fitness 
				   among shared strings*/
	  
	  front_index++ ;   /* incremented for next front */
	} 
      
      else {      /* for all other fronts 2, 3, ... */
	for(i=0; i<pop_size; i++)
	  if(oldpop[i].flag == 2) /* member of current front */
	    {  
	      oldpop[i].front = front_index ;
	      if(min_dum > delta_dum) 
		oldpop[i].dumfitness = min_dum-delta_dum;
	      /* smaller than the smallest dummy fitness in 
		 previous front */
	      else adjust(front_index);
	    }
	
	phenoshare();
	
	minimum_dum(); 
	
	front_index++ ;
	
      }                                /* --if else-- */
      
      for(i=0; i<pop_size; i++)
	{
	  /* call members of current front exhausted */ 
	  if(oldpop[i].flag == 2) oldpop[i].flag =  3;
	  
	  /* and ummark all current dominated solutions */
	  else if(oldpop[i].flag == 1) oldpop[i].flag = 0;
	}
      
    }                                    /*End of while loop */
  
}

adjust(index)
     int index;
{      /* jack up the fitness of all solutions assigned in a front
          to accomodate remaining ones */
  int i;
  double diff;
  
  diff = 2.0 * delta_dum - min_dum ;
  for(i=0; i<pop_size; i++)
    if(oldpop[i].flag == 1 || oldpop[i].flag == 0) continue;
    else oldpop[i].dumfitness += diff ;
  
  minimum_dum();
}

/*====================================================================
  Sharing in a front.  oldpop.dumfitness is divided by nichecount.
  =====================================================================*/
phenoshare()
{
  
  int i,j;
  float  dvalue,d,nichecount;
  double pow();
  float  distance();
  
  for(j=0; j<pop_size; j++)
    {
      nichecount = 1.0;
      if(oldpop[j].flag == 2)
	{
	  for(i=0; i<pop_size; i++)
	    {
	      if(i == j) continue;
	      
	      if(oldpop[i].flag == 2)
		{
		  /** distance() returns the phenotypic distance between
		    two individuals **/
		  d = distance(&(oldpop[j]),&(oldpop[i]));
		  if (d < 0.0) d = (-1.0)*d ;
		  if (d <= 0.000001) nichecount++ ;
		  else if(d < dshare) 
		    nichecount += (1.0-(d/dshare))*(1.0-(d/dshare));
	        }
	    }   /* for i loop */
	}    /* for oldpop[j].flag==2 loop */
      oldpop[j].dumfitness /= nichecount ;
      
    } /* j loop */
}

/*======================================================
  distance() returns the phenotypic distance
  between two individuals :  
  o in n-dimensional space. (number of variables = nx)
  o in fitness space.       (fitness1 - fitness2 space)   
  =======================================================*/
float  distance(critter1,critter2)
     INDIVIDUAL *critter1;
     INDIVIDUAL *critter2;
{
  int i, iobj;
  double dst,sqrt();
  
  dst = 0.0;
  if (FITNESS)             /* Sharing on fitness space */
    {
      for(iobj=0; iobj<num_obj; iobj++)
        dst += weightage[iobj]*square(critter1->fitness[iobj] - critter2->fitness[iobj])/square(afmax[iobj]-afmin[iobj]);
    }
  else if (PARAM)         /* Sharing on parameter space */
    {
      for (i=0;i<num_var;i++)
	dst += square(critter1->x[i]-critter2->x[i])/square(x_upper[i]-x_lower[i]);
    }
  dst = sqrt(dst);
  return(dst);
}

minimum_dum()
{    /* finding the minimum dummy fitness in the current front */
  int i;
  
  min_dum = 1000000000.0 ;
  
  for(i=0; i<pop_size; i++)
    {
      if(oldpop[i].flag == 2)
	{
	  if(oldpop[i].dumfitness < min_dum) min_dum = oldpop[i].dumfitness;
	}
    }
}

/*====================================================================
  MAIN PROGRAM ;
  ====================================================================*/
main()
{
  FILE *fp_out;      	/* File pointer for output file  	*/ 
  FILE *fp_report;     /* File pointer for report */ 
  int j,k,k1;
  POPULATION 	temp;	/* A temporary pointer of population 	*/
  
  /*---------------------------*/
  /* Program starts here :     */ 
  /*---------------------------*/
  printf("**********************************************************************\n");
  printf("***             MULTI-OBJECTIVE OPTIMIZATION SOFTWARE              ***\n");
  printf("***                                                                ***\n");
  printf("***        Developed by : Kalyanmoy Deb and Mayank Goyal           ***\n");
  printf("***           The Department of Mechanical Engineering             ***\n");
  printf("***        Indian Institute of Technology, Kanpur - INDIA          ***\n");
  printf("***................................................................***\n");
  printf("***  This software gives a set of solutions to a multi-objective   ***\n");
  printf("***  optimization problem.  The parameters can be represented as   ***\n");
  printf("***  any of the following following type (or their combination) :  ***\n");
  printf("***              o BINARY STRING TYPE                              ***\n");
  printf("***              o INTEGER TYPE                                    ***\n");
  printf("***              o ENUMERATED DATA TYPE                            ***\n");
  printf("***              o REAL/CONTINUOUS TYPE                            ***\n");
  printf("***                                                                ***\n");
  printf("***  For Multiobjective optimization, two strateies are there :    ***\n");
  printf("***              o Share on FITNESS SPACE                          ***\n");
  printf("***              o Share on PARAMETER SPACE                        ***\n");
  printf("***  Sigma-share value should be chosen accordingly.               ***\n");
  printf("***                                                                ***\n");
  printf("***  You can also assign importance of one fitness function over   ***\n");
  printf("***  other by giving them weightages.                              ***\n");
  printf("\n***  All rights reserved. Not to be used for commercial purposes.  ***\n");
  printf("\n***  Please send bug information and your comments to              *** ");
  printf("\n***    [e-mail] or [e-mail]    ***");
  printf("\n**********************************************************************");
  
  input_parameters();
  
  fp_out = fopen("result.out","w+");
  fp_report = fopen("report","w+");
  
  select_memory(); 
  //  initreport(fp_out);   
  initreport(fp_report);   
  
  gen_no=0;
  initialize();
  MakeFronts();
  statistics(oldpop,gen_no);
  
  // result(fp_out,gen_no);  
  if (REPORT) report(fp_report,gen_no);  
  
  printf("\n =====================================");
  printf("======================================== ");
  printf("\n Please Wait ");
  
  for(gen_no = 1; gen_no<=max_gen; gen_no++)
    {
      printf("."); if (gen_no%60==0) printf("\n");
      fflush(stdout);
      
      generate_new_pop();
      
      temp   = oldpop; 
      oldpop = newpop; 
      newpop = temp  ; 
      
      MakeFronts();
      statistics(oldpop,gen_no);
      
      if (gen_no==max_gen) result(fp_out,gen_no);  
      if (REPORT) report(fp_report,gen_no);  
    };                        /* One GA run is over  */
  printf("\n ============================================================================= ");
  
  free_all();
  
  fclose(fp_out);
  fclose(fp_report);
  app_closure();
  printf("\n Results are stored in file 'result.out' ");
  puts("\n O.K Good bye !!!"); 
}

/**************** End of Main Program ***************************/

/*-------------------------------------------------------  */ 
/* random.c - contains random number generator and related */
/* utilities,                                              */
/* Source : sga.c  (c) E.Goldberg 1986
   /*-------------------------------------------------------  */ 

/* variables are declared static so that they cannot       */
/* conflict with names of other global variables in other  */
/* files.  See K&R, p 80, for scope of static              */