ga.m

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%   Genetic Algorithm (GA)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%   Kevin Passino
%   Version: 7/21/98
%
% Notes: This program has evolved (hopefully to achieve a higher fitness!)
% over time using programming ideas from several persons including 
% LaMoyne Porter, Will Lennon, Jonathan Cook, and Jim Gremling.  
% 
% This program simulates the optimzation of a simple function with
% a base-10 genetic algorithm.  First, we outline some background 
% information on GAs and define some terminology.  Following this,
% we explain how to use the program for your own purposes and as an
% example we show how to solve an optimization problem.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Background Information on GAs:
%
%    A genetic algorithm is an optimization method that
% manipulates a string of numbers in a manner similar to how chromosomes  
% are changed in biological evolution.  An initial population made up of 
% strings of numbers is chosen at random or is specified by the 
% user. Each string of numbers is called a "chromosome" or an 
% "individual," and each number slot is called a "gene." A 
% set of chromosomes forms a population.  Each chromosome 
% represents a given number of traits which are the actual 
% parameters that are being varied to optimize the "fitness function".  
% The fitness function is a performance index that we seek to maximize.  
%
%    The operation of the GA proceeds in steps. Beginning with the initial 
% population, "selection" is used to choose which chromosomes 
% should survive to form a "mating pool."  Chromosomes are chosen based on 
% how fit they are (as computed by the fitness function) relative
% to the other members of the population.  More fit individuals end up 
% with more copies of themselves in the mating pool so that they
% will more significantly effect the formation of the next 
% generation.  Next, several operations are taken on the mating
% pool.  First, "crossover" (which represents mating, the exchange
% of genetic material) occurs between parents.
% To perform crossover, a random spot is picked 
% in the chromosome, and the genes after this spot are switched 
% with the corresponding genes of the other parent.  Following this, 
% "mutation" occurs.  This is where some genes are randomly changed 
% to other values.  After the crossover and mutation operations
% occur, the resulting strings form the next generation
% and the process is repeated.  A termination criterion
% is used to specify when the GA should end (e.g., the maximum 
% number of generations or until the fitness stops increasing).
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Some GA Definitions for this Program:
%  
% A GENE is a digit position that can take on certain values
%   Ex: In a base-10 algorithm a gene can hold any number between 0 and 9.
%
% A CHROMOSOME is a string of genes.
%   Ex: In base-10 1234567890 could be a chromosome of length 10.
%
% A TRAIT is a decimal number which is decoded from a chromosome.
%   Normally, a chromosome is a concatenation of several TRAITS.
% 
% An INDIVIDUAL is the object that the GA is attempting to optimize.
%  An individual is described by its chromosome.
%  The individual's traits determine its fitness.
%
% A POPULATION is a set of individuals (set of chromosomes).
% 
% FITNESS FUNCTION is the objective function to be optimized which provides
%  the mechanism for evaluating each string (we maximize the fitness 
%  function).
% 
% SELECTION: a fitter string receives a higher number of offspring 
%  and thus has a higher chance of surviving in the subsequent generation.
%
% CROSSOVER is an operation which swaps genes between two chromosome.
% 
% MUTATION is flipping a digit in the chromosome after crossover.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%   How to use the program for your own purposes:
%
% The main thing that needs to be changed in ga.m is the fitness function 
% and a few parameters.  It is now set to minimize a function z=f(x,y)
% that is a sum of scaled translated Gaussian distributions with x and y 
% between 0 and 30 (specified by the elements of HIGHTRAIT and LOWTRAIT).
% The function to be optimized must be changed in the section specified 
% in the program below.
%
%    In addition, the following parameters should be modified according
% to your needs:
%
% 1. NUM_TRAITS - the number of traits represented by each chromosome
%                  (e.g. if we were trying to optimize the above function
%				   we could have NUM_TRAITS=2).
%                   Example: Chromosome: 123456789012
%                        Possible two traits: 123456, 789012
%
% 2. HIGHTRAIT,LOWTRAIT -  arrays with NUM_TRAITS elements with each element
%                 specifying the upper (lower) limit on each trait (often
% 			      known a priori for an optimization problem).
%                 For example, we may only want to find the optimum values
%				  of a function over a certain region.  For instance, 
%				  we could choose HIGHTRAIT=[30 30] and LOWTRAIT=[0 0]
%				  for the above optimization problem.
%
% 3. SIG_FIGS - an array with NUM_TRAITS elements with each element 
%                specifying the number of significant figures in each 
%                trait (there must be at least one significant figure).
%                Example: SIG_FIGS=[6 6] with above possible traits.
%
% 4. DECIMAL - an array with NUM_TRAITS elements with each element
%               specifying the number of digits to the left of the decimal
%               point for each trait.  Choose DECIMAL to be the 
%               largest number integer part in HIGHTRAIT or LOWTRAIT
%               to avoid saturation.
%               (Example: HIGHTRAIT=[12.9 9.9], LOWTRAIT=[5.5 -5.5],
%                    DECIMAL=[2 1] so for our optimization problem 
%                    let DECIMAL=[2 2])
%
%   With this we can explain how to "decode" a chromosome:
%
%    The first gene of each trait determines the sign of the
% trait.  For our base-10 algorithm if this gene is 0-4, the trait is
% negative and 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.
%
%   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 trait).
%     Ex:  Suppose trait #i = 123456
%
%     If DECIMAL[i] =       Then Trait[i]=
%
%                 -2                       -0.0023456
%                 -1                       -0.023456
%                  0                       -0.23456
%                  1                       -2.3456
%                  2                      -23.456
%                      etc...
%
% Note also that you must set LOWTRAIT, HIGHTRAIT, DECIMAL, and SIG_FIGS
% so that if we saturate a trait at the value of LOWTRAIT or HIGHTRAIT 
% then the genes on the trait must be able to represent LOWTRAIT or
% HIGHTRAIT.  For example you would not choose HIGHTRAIT(1)=100
% and DECIMAL(1)=-2 with SIG_FIGS(1)=1.  Why?  Hence, you must choose
% the elements of LOWTRAIT and HIGHTRAIT so that they have the same
% decimal position and number of significant figures as their
% corresponding traits.
%
%
% 5.  MUTAT_PROB - the probability that a mutation will occur in any given
%                  gene (i.e., that a gene will be switched to another
%                  element of the alphabet that is being used).  Note that 
%                  for base 10 we randomly choose a number between 0-9, 
%				   with the exception of the number that was being mutated.
%
% 6.  CROSS_PROB - the probability that a crossover will occur between two
%                  parents (standard swapping of genes is used).
%
% 7.  SELF_ENTERED - if this flag is set to 1, an initial 
%                    population can be entered by the user.  If it is 0, 
%                    a random initial population is created.  We enter the 
%                    initial population in a special convenient way for 
%					 the user.
%
% 8. POP_SIZE - the number of individuals in a population (fixed). 
%				 This should be an even number - since pairs mate.
%
% 9. ELITISM - if this flag is set to one, the most fit individual in each
%               generation will be carried over to the next generation
%               without being modified in any way by the genetic operators.
%
% 10. DELTA, EPSILON - these are for the termination criterion.  
%                         The program is terminated if the fitness 
%                         changes less than EPSILON over DELTA
%                         generations.
%
% 11. MAX_GENERATION - the number of generations that the program will 
%                      produce before stopping.  This indicates the length 
%                      of the program will run. If it takes too long 
%                      to run, this number can be lowered.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Next, we provide some ideas on how to run to the program to illustrate
% its operation.  Proceed as follows:
% 
% (1) Experiment with the intial population.  Enter your own initial 
%     population (to do this you modify the code and let SELF_ENTERED = 1).
%     Currently, the code sets the intial population to be all zeros if
%     you let SELF_ENTERED = 1.  Another choice you may want to consider
%     is to place the initial members of the population on some type of
%     uniform grid to try to make sure that at least one of the intial 
%     points is in the proximity of the final point.  Currently, if you let
%     SELF_ENTERED = 0, the program automatically generates a random initial
%     population with a uniform distribution on the allowable range of each 
%     trait.
% (2) Next, you can experiment with the settings for the crossover and
%     mutation probabilities.  First, try MUTAT_PROB=0.05; CROSS_PROB=0.8.
%     If you lower the crossover probability you will generally find that 
%     there will be less local search near the best individuals (i.e., 
%     it will tend to less often interpolate between good individuals to
%     try to find a solution).  If you raise the mutation probability it
%     will tend to cause more random excursions into possibly unexplored 
%     regions.  Too high of a mutation probability can cause degradation
%     to random search, where too low of a mutation probability can cause
%     the GA to lock in on a local minima and never find the global one (at
%     least in a reasonable amount of time).  
% (3) Next, you can experiment with the population size.  Larger population
%     sizes require more computation time but they can speed convergence.
%     For instance, for a larger population size you will have more guesses
%     of where the global maximum is for the intial population and hence
%     it is more likely that there will be at  least one good intial guess.
%     There are similar effects as the algorithm runs.
% (4) Next, turn on elitism.  You will find that elitism removes some of the 
%     effects of having a higher mutation rate since it makes sure that 
%     the best candidate is not disturbed.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

clear           % Initialize momery
rand('state',0) % Reset the random number generator so each time you re-run
                % the program with no changes you will get the same results.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% User: Input your own parameters below (the ones given are for the
%       optimization problem given above):
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  NUM_TRAITS=2;          % Number of traits in each individual
  HIGHTRAIT=[30 30];  	 % Upper limit of a trait
  LOWTRAIT=[0 0]; 	     % Lower limit of a trait
  SIG_FIGS=[6 6]';       % Number of genes in each trait
  DECIMAL=[2 2];         % Order of magnitude the trait
  MUTAT_PROB=0.05;       % Probability of mutation (typically <.1)
  CROSS_PROB=0.8;        % Probability of crossover (typically near 1)
  SELF_ENTERED=0;        % "0": a random initial population.
                         % "1": a specified initial population 
                         % If you choose "1", enter it in the program.
  POP_SIZE=20;           % Number of individuals in the population
  ELITISM=0;             % Elitism ON/OFF, 1/0
  DELTA=100;             % Number of generations to be counted 
                         % for the termination criteria.
  EPSILON = 0.01;  	     % Range that the fitness must change 
                         % in the termination criteria.
  MAX_GENERATION=1000;   % Number of times the loop will run before 
  						 % giving up on the EPSILON-DELTA termination cond.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Next, we want to make the initial population of size = POP_SIZE called pop.
% Each column represents a chromosome and each element in that column
% representing a gene.  There will be POP_SIZE chromosomes with each of
% them having CHROM_LENGTH genes.  Now, rather than directly create this
% matrix we allow the user to enter the more easily specified values of the
% traits (pop is coded to be operated on by a genetic algorithm while trait is
% a matrix with each of actual values of the parameters).  Taking this approach 
% you can easily enter an intial population of parameter guesses on the domain
% of the function to be maximized and the first iteration in the GA will
% convert the values to a form (stored in pop) that the genetic operators can 
% work on.