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 2⁴⁰ (the 40 bits encoding basic genes) = 8.8 x10¹² 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 :

2- The basic parameters :

3- The functioning parameters :

Downwards :

4- Information elements :

    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