Ants
 

 


Genetic Algorithm Viewer 1.0  

Please wait while loading (50k)



GAV is now used as an introduction to genetic algorithms in many universities computer sciences dpt. all around the world.

GAV
QuickStart
GAV Functioning
Introduction to Genetic Algorithms


  


   GAV is a demonstration applet of the functioning of a Genetic Algorithm (GA). It aims at showing the power of GA and of the main mechanisms used while permitting a certain form of visualization of the general functioning.

    The problem set is to find the genome of a given biomorph (for more info on biomorphs see Biomorph Viewer).

    A biomorph is a graphic configuration generated from nine genes. The height first genes each encode a length and a direction. The ninth one encodes the depth of branching. In GAV, each gene is encoded on five bits. The four first represent the value, the fifth its sign. Each gene can then get a value from -15 to +15. Concerning gene nine, its value is limited to 2-9.

    Then there are : 8 (number of possible depth) x 240 (the 40 bits encoding basic genes) = 8.8 x1012 possible biomorphs, i.e. about 8 800 billions combinations. If we were able to test 1 000 genomes every second, we would need about 280 years to fulfill the whole search.

    A- Quickstart

    Using GAV is very simple. A first sample of 25 biomorphs is presented. Just select one of them as the searched subject. You also can generate a new sample with the random button.

      1- The buttons :

From left to right :

  1. Random generation of a new sample. If you use this button when a search is running it will be restarted with a new population. This allows to start a new search in case of a too fast convergence, or if the starting population was too far from the objective.
  2. Step by step search.
  3. Run/Stop.
  4. Increases the number of visible subjects.
  5. Adjusts the number of visible subjects to the population.
  6. Decreases the number of visible subjects. This is particularly useful in case of a large population and/or search of a biomorph with great number of branches. The speed of the algorithm will be widely increased.
  7. Reset parameters.
  8. About !

      2- The basic parameters :

  1. Population : GA must work with large populations. In our case, you may launch a search from 8 or 24 biomorphs but the functioning is then special. Note that each size of population is associated to a default mutation rate.
  2. Mutation rate : one divided by the chosen value. Note how high the default values are when the populations are small.
  3. Speed : corresponds to the time of pause between two generations in milliseconds.

      3- The functioning parameters :

Downwards :

  1. The five radio buttons permit to set the scaling method for fitness values.
    1. Windowing : Decrease fitness to set the smallest one at 0.
    2. Exponential : Use square roots of fitness.
    3. Linear Transfo. : Realize a linear transformation on each value.
    4. Linear Normalization : applies a linear normalization to the fitness distribution.
    5. None.
  2. Elitist permits to keep the best subject of each generation. It's essential, mainly for small populations.
  3. The two following radio buttons set the type of computing used. Is the genetic proximity to be computed in relation with the phenotype (i.e. the appearance) of the biomorphs, or in relation with their genotypes ? This last case is obviously theoretically forbidden since it is the genotype we are looking for. We nevertheless kept this function for a demonstration purpose.
  4. The last two buttons permit to choose between an improved mutation function (since it works on a gene basis). It's once again necessary for small populations.

      4- Information elements :

  1. Gen : Generation counter.
  2. Under the keys used to choose the mutation type, there are 3 times 9 stripes of colors. The upper one represents the genome (9 genes) of the demanded biomorph, the second corresponds to the best current individual and the third correspond to the worst one.
  3. Down left there are twice 45 stripes of colors. The represent the genome (bit by bit) of the demanded biomorph and of the best current subject. Blue corresponds a 1 bit, black is 0. Every five stripes there is the sign bit. + is yellow, - is gray. It allows to visualize easily the genes value.
  4. Down in the middle are the fitness of the best subject and the average fitness in %.
  5. In front of them are the gauges expressing these same values.

    When the search is stopped, you can select any subject which will be blue. Its genome will appear on the second line representing bit genes.

    You can also zoom any subject (only if stopped) with a Ctrl-click. Its genome and fitness will then appear.

    B- Functioning of GAV

    At the beginning, the drawing algorithm being known, we get the image of a biomorph. The only informations directly measurable are the positions of branching points and their number. The basic algorithm simulates the collecting of these informations.

    When it starts the search GAV computes the distance separating each generated biomorph from the target one. This distance corresponds to the fitness. Then a roulette wheel selection picks up those who will mate and the process of reproduction, crossover and mutation starts. The "roulette wheel" selection is a process in which a subject representing x % of total fitness has x % chances to be selected for mating. Since a same subject can be selected twice during one cycle, it's both father and mother, and therefore if there is no mutation, the offspring won't present any difference from its parent.

    Parameters setting ensures to test the GA in various conditions :

      1- Population : the minimum is 8, the maximum 1599. Actually, under 500, the algorithm doesn't work properly. If you lead the search step by step you will notice it converges very quickly.

      2- Mutation rate : Any newborn undergoes a process of mutation. In case of success a gene is modified. The type of modification depends on the mode of mutation selected. You'll notice that the rate of mutation is very high for small population. The aim is to get round the process of convergence.

      3- Elitist mode : For each reproduction cycle, a new generation replaces the former one. The best subject of each generation can be kept so as to improve the efficiency of the GA. The best genome ever generated is always preserved.

      4- Mutation type : The genome uses 45 bits stored in a long integer. The classical mode of mutation consists in transforming a unique bit. Even if this method plays its role, it can be improved. Since the basic algorithm is known, it is possible to write a function of mutation that acts on the whole gene rather than on a single bit. In this case, the value of the mutant gene varies of plus or minus one. Associated to the elitist mode, it allows the algorithm to follow automatically a whole of steps leading to the target.

      5- Fitness mode :

      5.1 - PTYPE Mode : To compute the fitness, we first generate for each biomorph a table containing the x and y offsets of each of its branches. The fitness is then the distance between the biomorph's table and the target's table. In this case, there may be a difference between the computed solution and the target's genome (you can see it in the graphical gene display). When the gene's value is 0, the sign can be either + or - (0 or 1).

      5.2 - GTPYE Mode : As a demonstration, it is possible to compute the fitness by a direct comparison of both genomes.

    The use of different scaling methods (see part 1) permits to check the efficiency of these various process. Note you can change them during the search.

    GAV permits to visualize the functioning of a GA and to test the influences of various parameters. Take time to test, see the capability of the algorithm to find the solution, or its inability to get out of a local optimum. This type of algorithm has too wide implementations to be restrained to Artificial Life, and we'll see with other applets how the GA can permit the evolution of very diverses virtual populations. In a way, and for example in the case of Data, we could not build this android ex-nihilo, but it might be considered as the result of the long evolution of ancestral robots.

 

    Jean-Philippe Rennard.  May 2000



Copyright ©rennard.org. 2000, 2001, 2002.

Last Update : 29 June, 2003