gac.txt

一个用MATLAB编写的优化控制工具箱

/* ga.c                       */
/* Genetic Algorithm Program  */
/* By Will Lennon             */
/* Started 1-28-95            */
/* Updated 10-4-95             */


/* Note to new users:

   A GENETIC ALGORITHM is a a parallel search method that manipulates a
     string of numbers (a chromosome) in a manner similar to the laws of
     evolution and biology.  In this software, that string of numbers 
     represents parameters of a mathematical function, called a "fitness
     function."  In this sense, chromosomes (parameters) which correspond
     to a large function value are deemed "more fit" than chromosomes which
     correspond to smaller function values.

   Some GA Definitions:
     
   A GENE is a single-digit number.  (Ex: 1,2,3, etc )
     (In this program we use the Base-10
     number system, so a gene is any number between 0 and 9.  A lot of
     GAs use the binary number system, in which case a gene is either 1 or 0)

   A CHROMOSOME is a string of genes.
     (Ex: 12345678901 could be a chromosome of length 11)

   A TRAIT is a decimal number (Ex: 56.0, 0.002, -600.0 )

   An INDIVIDUAL is the object that the GA is attempting to optimize.
     An individual is described by its chromosome.  The chromosome determines
     an individual's traits.  The individual's traits determine its fitness.

   A POPULATION is a set of individuals.

   A CHROMOSOME SECTION is a substring of a chromosome that corresponds to
     a particular trait.  If there are N traits on a chromosome, there must
     be N chromosome sections.
     In this software, use the constant Trait_Start[] to specify how to 
     separate a chromosome into sections.

     Example: if a chromosome of length 11 is: 12345678901
              and there are 2 traits on that chromosome, then the following
	      are possible chromosome sections:

	      Chrom. Sect. 1 Chrom. Sect. 2   Trait_Start[] values:
	      12             345678901        {0,2,11}
	      123            45678901         {0,3,11}
	      1234           5678901          {0,4,11}
	      12345          678901           {0,5,11}
	            etc...

     Basically, you pick points on the chromosome where to end one section
     and begin the next.  If you had 3 traits on the chromosome, you would
     pick 2 locations on the chromosome to separate the sections.  

     Note: Chromosome sections should be at least 2 genes long.  The first
     gene in each section is used to determine the sign of the trait, and
     the remaining terms determine the size of the trait.  If you have a
     section of size 1, you will have a trait that has no value, only a 
     positive or negative sign.
     


   DECODING A CHROMOSOME SECTION INTO A TRAIT:

     If the constant "negative" is set to one:
     The first gene of each chromosome section determines the sign of the
     trait.  If this gene is 0-4, the trait is negative.  If this gene is
     5-9, the trait is positive.  The remaining genes determine the size
     of the trait.  The second gene is the most significant digit, while the 
     last gene is the least significant digit.  

     If the constant "negative" is set to zero:
     No gene is used for the sign.  All genes are used for magnitude.

     To determine the relative magnitude of a trait, this software uses the
     Decimal[] constant.  This number determines how many digits to the left
     of the decimal to place the first digit of the trait (=second gene on the
     chrom. section).  

     Finally, the constant Offset_Trait is added to this trait value to get the
     final trait value.

     Ex:  For Chromosome section #i = 123456  (negative = 1)

                        Offset_Trait = 0        Offset_Trait = -10.0
     If Decimal[i] =     Then Trait[i]=         Then Trait[i] =
     
     -2                  -0.0023456           -10.0023456  
     -1                  -0.023456            -10.0234560
      0                  -0.23456             -10.2345600
      1                  -2.3456              -12.3456000 
      2                 -23.456               -33.4560000
         etc...

     Offset_Trait is used to shift the traits up or down.  This is helpful
     if you want at trait to lie, e.g., between 800 and 1799.  You could set:

     Offset_Trait = 800, Low_Trait = 0, and High_Trait=999. 

     Likewise you could set:

     Offset_Trait = 0, Low Trait = 800, and High Trait = 1799. 

     The advantage of the first method is that your chromsome would be 1 gene
     fewer because you could define it for 3 genes, 000-999, as opposed to
     4 genes, 0800-1799. 

     The High_Gene[] and Low_Gene[] are arrays that limit the possibilities 
     that each gene may take.  For example, if you have a chromosome with 1 
     trait that is limited to between 1000 and 2499, you could set:
     High_Gene{2,4,9,9}
     Low_Gene{1,0,0,0}
     This makes the GA more effecient because it doesn't try to mutate the
     first gene into any number other than 1 or 2, which are the only two 
     'legal' possibilities.  Naturally, if you are allowing negative numbers,
     the first gene should range 0-9.  

     If you don't know what you're doing, just set all Low_Genes to 0 and all 
     High_Genes to 9.

    CROSSOVER TYPES:
    Right now you have two choices for crossover.  If cross_type=1, then the
    GA selects a single crossover site and swaps all the genes before that
    site.  If cross_type=0, then the GA swaps each gene with a probability
    of 50%.  In other words, there is no one site, but rather each gene is
    crossed-over individually.

    Ex.  If you have two genes xxxxxxxxxx and yyyyyyyyyy that crossover,
    some possible results are:

    cross_type = 1    cross_type = 0

    xxxxxyyyyy        yyxxyyxxyyxy
    yyyyyxxxxx        xxyyxxyyxxyx
                -or-
    xxyyyyyyyy        xyyyyyxyxyxy
    yyxxxxxxxx        yxxxxxyxyxyx
                -or-
    xxxxxxxyyy        xxxyyyxxxxyx
    yyyyyyyxxx        yyyxxxyyyyxy
               etc...

              
   RUNNING THIS PROGRAM:

   Compile this program by typing: gcc ga.c -o ga -lm 
   Then run the program by typing: ga

   This program creates the following data files:
   stats.out       : A complete list of every generation and the 
                     fitness of every member in the population.
   best.out        : A list of the "most fit" member of each 
                     generation. 
   generation.data : A list of all the information of every member of
                     the last generation.  

   
   TO CHANGE THIS GENETIC ALGORITHM to optimize a different fitness function,
   you only need to change the following areas:
   1) The #define definitions 
   2) The global constants
   3) The Get_Fitness() function (This is the first function defined below)
   
   You may also like to modify the Fit_params structure to allow for
   a fitness function that varies with passing generations (this is not
   necessary for a simple GA, but is useful with a GMRAC).  Presently
   this structure contains only an example that is not being used.

   Note:  The #define ZERO is necessary to compensate for numerical error.  
   It is sufficiently small for most applications.  However, if you have a 
   trait that has significant digits smaller than ZERO, you should reduce 
   ZERO until it is smaller than your least significant digit.  


   IMPORTANT: Depending on the computer system you compile this on, you
   may need to change the MaxRandom constant in the function Rand_Num().
   If you run this software in the Control Research Lab (CL343)
   you will be OK with the present MaxRandom value.   
   For the EE HP's (er4hp site), change this number to 32767.  
   For other machines, check the manual pages for the function rand() in 
   <stdlib.h> and change MaxRandom to the maximum integer value rand() 
   returns. 
*/


/******************* INCLUDE FILES ***************************************/
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>

/***************** DEFINITIONS *******************************************/
#define NUM_TRAITS      2    /* Number of Traits on the Chromosome */
#define CHROM_LENGTH   14    /* Total Length of Chromosome */
#define MAX_POPULATION 20    /* Maximum population size */
#define MIN_POPULATION 10    /* Minimum population size */
#define ZERO  0.00000000001  /* Compensate for roundoff error in Encode_Chrom*/

/****************** GLOBAL CONSTANTS **************************************/
const int max_generation = 100;     /* Number of Generations */
const double cross_prob  = 0.9;     /* Probability of Crossover */
const double mutat_prob  = 0.1;    /* Probability of Mutation */
const int elitism        = 1;       /* elitism ON/OFF 1/0 */
const int output         = 1;       /* Save stats.out to file? 1=yes 0=no*/
const int negative       = 0;       /* Negative traits possible? 1=yes 0=no */
const int cross_type     = 0;       /* Method of crossover */

/* High_Trait & Low_Trait indicate the max/min allowable value of each trait 
   on the chromosome.
*/
const double High_Trait[NUM_TRAITS] = {+7.0, +5.0};
const double Low_Trait[NUM_TRAITS]  = {0.0, 0.0};

const double Offset_Trait[NUM_TRAITS] = {-1.0, 1.0};

const int High_Gene[CHROM_LENGTH] = {6,9,9,9,9,9,9,4,9,9,9,9,9,9};
const int Low_Gene[CHROM_LENGTH]  = {0,0,0,0,0,0,0,0,0,0,0,0,0,0};

/* Decimal[] describes how to decode a chromosome section into a trait.
   It tells the function Decode_Chrom() how many genes of the chromosome
   section to place to the left of the decimal point.
   For example, if a chromosome section [i] is "45678", and Decimal[i] = 2,
   the corresponding trait would equal -56.78.  If Decimal[i] = -1, the
   corresponding trait would equal -0.05678.  Note that the first gene of each 
   chromosome section indicates + or -, (see Decode_Chrom()).
*/  
const int Decimal[NUM_TRAITS] = {1, 1};


/* Trait_Start[] represents the gene on the chromosome where each trait
   starts. This array must always begin with '0' and end with
   CHROM_LENGTH.  The number of intermediate terms is dependent on NUM_TRAITS.
   In effect, this determines the length of each chromosome section 
   and hence determines the precision of the corresponding trait.
*/
const int Trait_Start[NUM_TRAITS+1] = {0,7,CHROM_LENGTH};

/*********************** TYPES *******************************************/

/* CREATE FITNESS PARAMETERS TO PASS TO FITNESS FUNCTION */
typedef struct
{
  double example;   /* Change/add/delete this structure as desired */
} Fit_params;


/* CREATE TYPE CHROMOSOME: STRING OF GENES */
typedef struct
{
  int gene[CHROM_LENGTH];
} Chromosome;


/* CREATE TYPE TRAITS */
typedef struct
{
  double num[NUM_TRAITS];
} Traits;

  
/* CREATE TYPE INDIVIDUAL */
/* A complete description of every member of the population, including
   the members of the previous population (parents) who produced it.
*/
typedef struct
{ 
  Chromosome chrom;
  Traits trait;
  double fitness;
  int parents[2];
} Individual;


/* CREATE TYPE SURVIVORS */
/* "Survivors" are those members of the current population that are 
    selected to reproduce into the next generation 
*/
typedef struct
{
  int bestmember;
  int size;
  int number[MAX_POPULATION+1];
  Chromosome chrom[MAX_POPULATION+1];
} Survivors;


/* CREATE TYPE POPULATION */
/* A complete description of the entire population, including the population 
   size, the generation number (count), and number of mutations, etc 
*/
typedef struct
{
  Individual member[MAX_POPULATION+1];
  double sumfitness;
  int bestmember;
  int worstmember;
  int size;
  int count;
  int crossovers;
  int mutations;
} Population;

/**************************************************************************/
void Get_Fitness(Individual *member, Fit_params *params)
{
  /* Get_Fitness determines the fitness of one individual 
     This is the only function (besides maybe main()) that needs to be
     modified.  I moved it up front so you can find it more easily. */

  double fitness;
  double error;
  double x,y,z;
  int i=0;

  /* Change of variables to something simpler */
  x = member->trait.num[0];
  y = member->trait.num[1];

  z = params->example;  /* This could be  used in the fitness evaluation */

  /* This fitness function will be maximized at x=0, y= 3.14159 */
  fitness = pow(cos(x) + sin(y/2.0),6.0);
  
/*  fitness = pow(3.0*(1.0-x),2.0) * exp(-x*x - y*y-2.0*y-1.0) - 
    10.0*(0.5*x-x*x*x-y*y*y*y)*exp(-x*x-y*y) - 
      0.3333333*exp(-x*x-2.0*x-1.0-y*y);
  */


  /* Make certain fitness is non-negative */
  /* REMEMBER: The best individuals have the highest fitness. */
  if (fitness<0.0) fitness = 0.00;
  member->fitness = fitness;
} 

/********************* FUNCTION DEFINITIONS **********************************/

/* GA.C */

void Statistics(Population *pop);
void Save_Generation(Population *pop);

/* REPRODUCTION.C */

Population First_Generation(int pop_size); 
void Next_Generation(Population *pop, int pop_size); 
Survivors Select_Parents(Population *pop, int pop_size);
Population Make_Offspring(Survivors parents);
void Reproduce(Chromosome parent1, Chromosome parent2,
	       Chromosome *child1, Chromosome *child2,
	       int *crossovers, int *mutations);
void Crossover(Chromosome *child1, Chromosome *child2);
void Mutate(Chromosome *child, int site);
int Check_Chrom(Chromosome chrom);
void Create_Chrom(Chromosome *chrom, int flag);
double Power(int x, int y);

/* FITNESS.C */

void Find_Fitness(Population *pop, Fit_params *params); 
Traits Decode_Chrom(Chromosome chrom);
Chromosome Encode_Traits(Traits trait);
void Get_Fitness(Individual *member, Fit_params *params); 


/* RANDOM.C */

double Rand_Num(void);
int Flip(double chance);
int Rand_Int(int high, int low);