Our approach to circuit synthesis using genetic programming draws on an additional analogy from nature — the process by which an embryo develops into a fully grown organism.
A fully developed electrical circuit can be produced by progressively executing circuit-constructing functions from an individual program tree from the population. Each circuit-constructing program tree in the population contains component-creating functions, topology-modifying functions, and development-controlling functions that grow a simple embryo into a fully developed circuit. This process is explained in the text below using an animated gif. The process starts with a very simple embryonic circuit. In this example, the embryo consists of two modifiable wires, Z0 and Z1. The embryo is embedded in a test fixture whose input is the electrical signal VSOURCE and whose output is the voltage VOUT. The text fixture also contains a source resistor and a load resistor. The output produced by these two embryonic wires sitting in their test fixture is always zero, and uninteresting. Execution of the circuit-constructing program tree begins with the capacitor-creating C function associated with modifiable wire Z0 inserting capacitor C3 in lieu of modifiable wire Z0. The seven-point arithmetic-performing subtree of the C function establishes the numerical value of 403 nano-Farads as the sizing of capacitor C3. The next function in the tree — an S function — now becomes associated with C3. The polarity-reversing flip function F now reverses the polarity of modifiable wire Z1. The topology-modifying series, or S, function now creates a series composition consisting of two copies of the capacitor and new modifiable wire Z4. These three new components become associated with an F, S, and L function. The inductor-creating L function inserts inductor L8 into the growing circuit. Its arithmetic subtree establishes .22 micro-Henries as the value of inductor L8. This flip function F reverses the polarity of capacitor C3. The just-flipped capacitor C3 then becomes associated with the E function. The second series function then trifurcates modifiable wire Z4 into three modifiable wires. Another inductor-creating L function converts capacitor C5 into inductor L7 The three-point arithmetic-performing subtree assigns a value of 0.41 micro-Henries to new inductor L7. The end function E at the far right of the screen then ends development of its particular path, as does this end function and other similar end functions later. Modifiable wire Z4 is flipped. Inductor L9 is inserted in lieu of modifiable wire Z6 … and inductor L7 is changed in value to .753 micro-Henries. Continuing in the same fashion, we get a fully developed electrical circuit
Other topology-modifying functions are available, including parallel division. Transistors can also be inserted into a developing circuit by means of a transistor-creating function. Since most present-day electrical circuits are composed of transistors, capacitors, and resistors (on silicon chips), this development process is very general.
Automatic synthesis of the topology and sizing of electrical circuits by means of developmental genetic programming is discussed in detail in Genetic Programming III: Darwinian Invention and Problem Solving (Koza, Bennett, Andre, and Keane 1999) and in Genetic Programming IV: Routine Human-Competitive Machine Intelligence (Koza, Keane, Streeter, Mydlowec, Yu, and Lanza 2003).
A circuit’s placement and routing can be synthesized at the same time as its topology and sizing by using geographically-aware circuit-constructing functions. The geographically-aware functions keep track of the geographic location of each component and wire during the developmental process. This geographically aware developmental process is explained in the text below using an animated gif. This process starts with a modifiable wire, Z, at a particular geographic location on the circuit board or chip, and an incoming signal, V, a source resistor, and a load resistor. The circuit-constructing program tree contains component-creating functions, topology-modifying functions, development-controlling functions, and numerical constants and arithmetic-performing subtrees that establish component values. The process starts with induction-creating function inserting L2 in lieu of a modifiable wire, while appropriately adjusting the locations of preexisting wires and components. Then, a parallel division duplicates inductor L2 and creates two new modifiable wires. Two polarity-reversing FLIP function and one development-controlling END function bring this path through the program tree to an end. A capacitor-creating function converts an inductor into a capacitor, whose component value is established by a seven-point arithmetic-performing subtree. This SERIES function divides a modifiable wire. A capacitor-creating function inserts a capacitor in lieu of a modifiable wire. A topology-modifying function creates a connection to ground, and this inductor-inserting function converts a modifiable wire into a final inductor. The result is the topology, sizing, placement, and routing of a fully developed circuit.
Automatic synthesis of the placement and routing of electrical circuits by means of developmental genetic programming is discussed in detail in Genetic Programming IV: Routine Human-Competitive Machine Intelligence (Koza, Keane, Streeter, Mydlowec, Yu, and Lanza 2003).
· The home page of Genetic Programming Inc. at www.genetic-programming.com.
· For information about the field of genetic programming in general, visit www.genetic-programming.org
· The home page of John R. Koza at Genetic Programming Inc. (including online versions of most papers) and the home page of John R. Koza at Stanford University
· Information about the 1992 book Genetic Programming: On the Programming of Computers by Means of Natural Selection, the 1994 book Genetic Programming II: Automatic Discovery of Reusable Programs, the 1999 book Genetic Programming III: Darwinian Invention and Problem Solving, and the 2003 book Genetic Programming IV: Routine Human-Competitive Machine Intelligence. Click here to read chapter 1 of Genetic Programming IV book in PDF format.
· For information on 3,198
papers (many on-line) on genetic programming (as of June 27, 2003) by over 900
authors, see William
Langdon’s bibliography on genetic programming.
· For information on the Genetic Programming and Evolvable Machines journal published by Kluwer Academic Publishers
· For information on the Genetic Programming book series from Kluwer Academic Publishers, see the Call For Book Proposals
· For information about the
annual Genetic and
Evolutionary Computation (GECCO) conference (which includes the annual
GP conference) to be held on June 26–30, 2004 (Saturday – Wednesday) in Seattle
and its sponsoring organization, the International Society for Genetic and
Evolutionary Computation (ISGEC).
For information about the annual NASA/DoD Conference on
Evolvable Hardware Conference (EH) to be held on June 24-26
(Thursday-Saturday), 2004 in Seattle. For information about the annual Euro-Genetic-Programming
Conference to be held on April 5-7, 2004 (Monday – Wednesday) at the
University of Coimbra in Coimbra Portugal.
Last updated on August 27, 2003
