www.gp-field-guide.org.uk
Contents Top Previous Next

6.3 Developmental Genetic Programming

By using appropriate terminals, functions and/or interpreters, GP can go beyond the production of computer programs. In cellular encoding (Gruau1994Gruau and Whitley1993Gruau1994), programs are interpreted as sequences of instructions which modify (grow) a simple initial structure (embryo). Figure  6.4 shows part of the development of an electronic circuit.3 Once the program has finished, the quality of the structure it has produced is measured and this is taken to be the fitness of the program.


PIC
Figure 6.4: Screen shot of an animated gif showing the development of the topology and the sizing of an electrical circuit (from http: //www.genetic-programming.com/gpdevelopment.html).The program is interpreted in parallel. Solid arrows link the active code to the parts of the electronic circuit (lower half) that are being modified. The three-headed arrow from S shows that three new components (Z4) have just been created in series. Their types (e.g., capacitor, inductor or resistor) and values will be determined by the three arguments of the S "function".


Naturally, for cellular encoding to work the primitives of the language must be able to grow structures appropriate to the problem domain. Typical instructions involve the insertion and/or sizing of components, topological modifications of the structure, etc. Cellular encoding GP has successfully been used to evolve neural networks (Gruau1994Gruau and Whitley1993Gruau1994) and electronic circuits (Koza et al.1999Koza, Andre, Bennett, and Keane1996aKoza, Bennett, Andre, and Keane1996c), as well as in numerous other domains. A related approach proposed by Hoang, Essam, McKay, and Nguyen (2007) combines tree adjoining grammars (Section  6.2.3 ) with L-systems (Lindenmayer1968) to create a system where each stage in the developmental process is a working program that respects the grammatical constraints.

One of the advantages of indirect representations such as cellular encoding is that the standard GP operators can be used to evolve structures (such as circuits) which may have nothing in common with standard GP trees. In many of these systems, the structures being "grown" are also still meaningful (and evaluable) at each point in their development. This allows fitness evaluation. Another important advantage is that structures resulting from developmental processes often have some regularity, which other methods obtain through the use of ADFs, constraints, types, etc. A disadvantage is that, with cellular encoding, individuals require an additional genotype-to-phenotype decoding step. However, when the fitness function involves complex calculations with many fitness cases, the relative cost of the decoding step is often small compared with the rest of the fitness function.


www.gp-field-guide.org.uk
Contents Top Previous Next