ga_approx.m

人工免疫算法基于遗传MATLAB代码很有用哦

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%   Approximate Genetic Algorithm
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%   Kevin Passino
%   Version: 3/12/99
% 
% This program simulates the optimzation of a simple function with
% an approximation to the genetic algorithm (which we call AGA).  
% First, we outline some background 
% information on the AGA 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 and the AGA:
%
%    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).
%
%    Normally, the GA is implemented using a base-2 or base-10
% representation.  If you use a base-2 representation generally you will
% have to convert the problem from its base-10 representation in the 
% real-world to a base-2 representation and to get data about program
% operation you will have to convert the base-2 strings that the GA
% operates on back to base-10.  So, what is an "approximate" GA?  In a computer
% it takes time to convert numbers between different bases and even if
% a base-10 representation is used in a computer you normally have to 
% change the numbers into sequences of digits that can be independently
% manipulated by genetic operators (e.g., for crossover, to swap digits
% on a string).  AGA is a version of a genetic algorithm that seeks
% to avoid encoding and decoding in traditional GAs by working with the
% real number system that is used in the computer.  Significant 
% computational savings can be obtained and AGA has been used to 
% study the use of GAs in on-line real-time optimization.  
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  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 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.  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.
%
% 4.  CROSS_PROB - the probability that a crossover will occur between two
%                  parents (standard swapping of genes is used).
%
% 5.  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.
%
% 6. POP_SIZE - the number of individuals in a population (fixed). 
%				 This should be an even number - since pairs mate.
%
% 7. 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.
%
% 8. DELTA, EPSILON - these are for the termination criterion.  
%                         The program is terminated if the fitness 
%                         changes less than EPSILON over DELTA
%                         generations.
%
% 9. 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
  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 make the initial population of size = POP_SIZE 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

popcount=1;         	% Initialize the generation count, 
						% set it to one, the first population

if SELF_ENTERED == 0            % Make a random initial population for
								% base-10 operation by specifying the 
								% matrix of initial traits
for pop_member = 1:POP_SIZE
      for current_trait = 1:NUM_TRAITS,
 		trait(current_trait,pop_member,popcount)=...
		(rand-(1/2))*(HIGHTRAIT(current_trait)-LOWTRAIT(current_trait))+... 
		(1/2)*(HIGHTRAIT(current_trait)+LOWTRAIT(current_trait));
			    % This starts the population off with numbers chosen randomly 
				% on the allowed range of variation, for this example.  
      end
end 

else
								
for pop_member = 1:POP_SIZE
        for current_trait = 1:NUM_TRAITS,
            trait(current_trait,pop_member,popcount)=0;  
			% To start with a guess where all the population members are zero				
		end
end 
	
end


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% In this next loop the fitness is calculated, the children are 
% created and it repeats until the EPSILON-DELTA termination condition
% is satisfied or MAX_GENERATION is reached.  This is the main
% loop of the RGA.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

while popcount <= MAX_GENERATION,
	 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% USER: Below is where you change the fitness function that is to be
% maximized.  This may involve changing several lines of code below.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% In the example below we want to *maximize* the function z=f(x,y).
% Important: When defining the fitness function you must remember that 
% it is a function that you are *maximizing* and that it must always be 
% positive (the selection mechanism depends on this).  For our example, 
% we are maximizing the function f.  Below, we include some ideas about
% what to do if you seek to minimize a function.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

sumfitness = 0; 		% Re-initialize for each generation

% First, determine the values of the function to be minimized for 
% each chromosome.

   for chrom_number = 1:POP_SIZE,       % Test fitness

fitness_bar(chrom_number)=...
+5*exp(-0.1*((trait(1,chrom_number,popcount)-15)^2+...
   (trait(2,chrom_number,popcount)-20)^2))...
-2*exp(-0.08*((trait(1,chrom_number,popcount)-20)^2+...
   (trait(2,chrom_number,popcount)-15)^2))...
+3*exp(-0.08*((trait(1,chrom_number,popcount)-25)^2+...
   (trait(2,chrom_number,popcount)-10)^2))...
+2*exp(-0.1*((trait(1,chrom_number,popcount)-10)^2+...
   (trait(2,chrom_number,popcount)-10)^2))...
-2*exp(-0.5*((trait(1,chrom_number,popcount)-5)^2+...
   (trait(2,chrom_number,popcount)-10)^2))...
-4*exp(-0.1*((trait(1,chrom_number,popcount)-15)^2+...
   (trait(2,chrom_number,popcount)-5)^2))...
-2*exp(-0.5*((trait(1,chrom_number,popcount)-8)^2+...
   (trait(2,chrom_number,popcount)-25)^2))...
-2*exp(-0.5*((trait(1,chrom_number,popcount)-21)^2+...
   (trait(2,chrom_number,popcount)-25)^2))...
+2*exp(-0.5*((trait(1,chrom_number,popcount)-25)^2+...
   (trait(2,chrom_number,popcount)-16)^2))...
+2*exp(-0.5*((trait(1,chrom_number,popcount)-5)^2+...
   (trait(2,chrom_number,popcount)-14)^2));

   end

% Next, compute the fitness function (this loop is only kept 
% separate from the next one in case you need to implement 
% some of the options discussed in the comments).  

   for chrom_number = 1:POP_SIZE,       % Test fitness

% The fitness function must be chosen so that it is always positive.
% To ensure this for our example we assume that we know that the value
% of f will never be below -5; so we simply add 5 to every fitness_bar value.
% Another approach would be to simply find the minimum value 
% of the fitness_bar function for every element in the population 
% and then add on its absolute value so that all the resulting 
% values will be positive

 fitness(chrom_number)= fitness_bar(chrom_number) + 5;
 
% Notice that when we turn a minimization problem into a maximization
% problem we often use 
% fitness(chrom_number)= -fitness_bar(chrom_number) + max(fitness_bar);
% as the above line.  Here, the minus sign is
% for turning the minimization problem into a maximization problem
% and max(fitness_bar) is used to make the fitness function positive.
% Another option would be to use the fitness function:
% fitness(chrom_number)=(1/(fitness_bar(chrom_number) + .1));
% The 1/fitness_bar function switches it to a maximzation problem.  
% The +.1 is to make sure that there is no divide by zero. Note that you can