Al Globus
Veridian MRJ Technology Solutions, Inc.
NASA Ames Research Center
Mail Stop T27A-2
Moffett Field, CA 94035-1000
aglobus@mail.arc.nasa.gov

Sean Atsatt
Sierra Imaging, Inc.

John Lawton
University of California at Santa Cruz

Todd Wipke
University of California at Santa Cruz

NAS-00-018
October 2000

Abstract

Many genetic algorithms use binary string or tree representations. We have developed a novel crossover operator for a directed and undirected graph representation, and used this operator to evolve molecules and circuits. Unlike strings or trees, a single point in the representation cannot divide every possible graph into two parts, because graphs may contain cycles. Thus, the crossover operator is non-trivial. A steady-state, tournament selection genetic algorithm code (JavaGenes) was written to implement and test the graph crossover operator. The JavaGenes code has evolved pharmaceutical drug molecules and simple digital circuits. Results to date suggest that JavaGenes can evolve moderate sized drug molecules and very small circuits in reasonable time. Since the representation strongly affects genetic algorithm performance, adding graphs to the evolutionary programmer's bag-of-tricks should be beneficial.

To view the full report:
HTML Version