TEACH GA Riccardo Poli Nov 1995 How to use LIB GA - The simple library to run Genetic Algorithms (Note: this is a very preliminary, incomplete version.) CONTENTS - (Use g to access required sections) -- Introduction -- A simple genetic algorithm -- A simple problem -- Preparing to use genetic algorithms -- Using LIB GA to solve the problem -- Note -- Further reading -- Introduction ----------------------------------------------------- Genetic algorithms (GAs) are optimisation and search procedures inspired by genetics and the process of natural selection. In order to do so in GAs the following nature-to-computer mapping is used: +-----------------------+--------------------------------------+ ! Nature ! Computer ! +-----------------------+--------------------------------------+ ! Individual ! Solution to a problem ! ! ! ! ! Population ! Set of solutions ! ! ! ! ! Fitness ! Quality of a solution ! ! ! ! ! Chromosome ! Representation for a solution ! ! ! (e.g. set of parameters) ! ! ! ! ! Gene ! Part of the representation of ! ! ! a solution (e.g. parameter) ! ! ! ! ! Growth ! Decoding of the representation of ! ! ! solutions ! ! ! ! ! Crossover or ! Main search operator ! ! recombination ! ! ! ! ! ! Mutation ! Secondary search operator ! ! ! ! ! Natural Selection ! Reuse of good (sub-)solutions ! +-----------------------+--------------------------------------+ In GAs there is a strong distinction between adult individuals (i.e. solutions) and chromosomes (i.e. representations for the solutions). Chromosomes are strings of symbols (e.g. 0s and 1s). Adult individuals can be anything as long as there is a way of encoding/decoding them using a string of symbols (chromosomes). Examples are vectors of parameters or lists of choices. As GAs (like nature) act on genotypes only, a genotype-to-phenotype decoding process is required ("generalised" growth). -- A simple genetic algorithm ---------------------------------------- A typical GA includes the following steps: 1. Randomly generate a population of chromosomes 2. DECODE each chromosome to get an individual 3. EVALUATE the fitness of each individual 4. Generate a new population partly by CLONING (copying), partly by RECOMBINING and partly by MUTATING the chromosomes of the fittest individuals 5. Repeat steps 2, 3 and 4 until a stop condition is true. Note: Cloning is used to simulate the survival of parents for more than one generation. -- A simple problem -------------------------------------------------- Let us start with a simple example. The problem is to find the number in {0,1,...,255} whose binary representation has the maximum number of 0-to-1 transitions. The solution to this problem is quite easy to find for us, it is 85 (01010101) which has 7 transitions. However, it is not easy to find with a computer if not by using brute force (the domain is discrete, so we cannot use most of the methods from numerical analysis). -- Preparing to use genetic algorithms ------------------------------- There are some decisions to be made before starting the GA. REPRESENTATION: First we need to decide how many bits to use in our chromosomes. We can use chromosomes with eight bits (byte), which are are sufficient to represent any value in {0,1,...,255}. DECODING: As we want the solution as a decimal number, we will decode our solutions by using the normal binary to decimal conversion. FITNESS: The quality of our adult individuals (decimal numbers) depends on the the number of 0/1 transitions in their binary representation. Our fitness function will have to transform back the adult individuals into binary form and count the transitions. (Of course, for this particular problem we can increase efficiency by avoiding to convert the chromosomes in decimal form in the first place.) POPULATION: Given the extreme simplicity of the problem we use a very small population of 10 individuals. SELECTION: We will select individuals for reproduction and cloning on with a probability proportional to their fitness. CLONING: 30% of the selected individuals will be just copied. RECOMBINATION: We will apply recombination to 70% of the selected strings. To recombine two strings we cut them at a random position and swap their left hand sides. MUTATION: We flip random bits of the chromosome with a very low probability. -- Using LIB GA to solve the problem --------------------------------- In order to run this example we have to load the GA library with lib ga; then we have to define an appropriate fitness function which receives as argument a chromosome and returns the fitness of the adult individual represented by such chromosome (the decoding phase, if necessary, will have to take place inside the fitness function). Here is a procedure that evaluates the number of 0/1 transitions in the bit string of a chromosome and stores it. define test_fitness_function( chrom ); lvars chorm, bit_str = bit_string(chrom), fit = 0, counter; for counter from 2 to bit_number(chrom) do if ( bit_str(counter-1) /= bit_str(counter) ) then fit + 1 -> fit; endif; endfor; fit -> fitness(chrom); enddefine; It is possible to check whether the function performs the correct computation by creating a chromosome using the procedure conschromosome( , , ) and then running test_fitness_function on it. E.g. vars c = conschromosome( undef, { 1 0 1 0 }, 4 ); test_fitness_function( c ); fitness(c) ==> Once the fitness function is defined we can run the procedure genetic_algorithm( , , , , , , 0, false, , undef ) which will return the best individual found. E.g. the following code will run a GA with the characteristics outlined above, print some statistics for each generation (average fitness, best fitness, etc.) and return the best individual in the variable "best". vars best = genetic_algorithm( "test_fitness_function", 30, 8, 50, 0.7, 0.01, 0, false, true, undef ); bit_string(best) ==> fitness(best) ==> -- Note ---------------------------------------------------------------- Normally genetic_algorithm() will save the population on disk every ten generations. You can prevent this by enclosing inside a list before passing it to genetic_algorithm(). E.g. genetic_algorithm( "test_fitness_function", [30], ....) It is also possible to restart a run saved on disk by passing the corresponding filename (a string) instead of a number or a list (in ). -- Further reading --------------------------------------------------- SHOWLIB * GA The source code of the library TEACH * GA_DEJONG.p The source code of a small set of more interesting examples on how to use LIB GA for function optimisation (minimisation or maximisation) --- $poplocal/local/teach/ga --- The University of Birmingham 1995. --------------------------------