Evolution of a circuit that sorts four integers

The images above show the results of EvolvaWareTM applied to the problem of automatically evolving a circuit that sorts four integers. What you see are the best circuits that have evolved after every 200 individual evaluations. Each circuit is shown with a fitness metric, which decreases as the circuits improve. Here, after 800 evaluations an optimal circuit has been evolved and no further progress can be made in decreasing the fitness metric. The fitness metric is based on three things: the number of inversions in the output (e.g. (4,1,2,3) has 3 inversions (4,1), (4,2), and (4,3)), the number of components used, and the number of steps. Below the circuit is the input test data and the output of the circuit. Properly sorted inputs are shown in green, improper in red. You can see in the first circuit that one of the input sequences is not sorted correctly. This leads to a high fitness score compared to the succeeding circuits. In the circuit diagrams, the input numbers are shown as signals coming from the left side, labeled bb_in0 through bb_in3, and the output numbers are signals terminating on the right side, labeled bb_out0 through bb_out3.

There are two kinds of component primitives that the Genetic Programming (GP) engine uses. One is labeled compare, which takes two integers and returns them sorted, and one labeled compare_self, which takes two copies of the same integer and returns the integer back. The type of the component is shown at the bottom of each component box.

EvolvaWareTM evolved these circuits using a GP engine paired with an FPGA that did on-chip evaluation of the circuits. Total run time for 2000 evaluations is approximately 20 seconds.

The set of test input combinations was empirically determined to be the minimal set that would produce a circuit that correctly sorts any four integers.

The images above are recorded from an applet that reads successive "snapshot" VHDL files that specify the circuits. These files are translated in real time into the visual representations above. The VHDL files are produced at regular intervals by the GP engine.

A VHDL file is produced by walking the GP parse tree and translating the nodes in the tree into VHDL statements. An example GP parse tree and companion VHDL file are shown below.


Fig.1 Example parse tree and VHDL translation

The nodes labeled "COMPARE" correspond directly to the compare components seen in the images above.


BBN Systems & Technologies 
70 Fawcett Street, Cambridge MA 02138 
Phone: (617) 873-3000  
Fax: (617) 873-2616 
Submit comments on this site to: gvidaver@bbn.com 
Copyright 1996 BBN Corporation