AlgorithmeGenetique.rar_genetic algorithm_genetic wsn_genetic+ws

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Genetic Algorithm (GA) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Kevin Passino % Version: 7/21/98, latest change 10/22/03 with correction from % Phan Tran Ho Truc, Mr., B. Eng., lecturer in HCM City University of Technology % to lines 379-384 of old program (lines 380-381 of this program) % % 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