Graph Crossover

author = "Al Globus and Sean Atsatt and John Lawton and Todd Wipke",

title = "Graph Crossover",

howpublished = "www",

year = "2000",

month = "5 " # may,

keywords = "genetic algorithms, genetic programming",

URL = "

http://alglobus.net/NASAwork/papers/JavaGenes2/JavaGenesPaper.html",

broken = "http://people.nas.nasa.gov/~globus/papers/JavaGenes2/JavaGenesPaper.html",

size = "15 pages",

abstract = "Most genetic algorithms use string or tree representations. To apply genetic algorithms to graphs, a good crossover operator is necessary. We have developed a general-purpose, novel crossover operator for directed and undirected graphs, 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 used test the graph crossover operator. JavaGenes has successfully evolved pharmaceutical drug molecules and simple digital circuits. For example, morphine, cholesterol, and diazepam were successfully evolved by 30-60percent of runs within 10,000 generations using a population of 1000 molecules. Since representation strongly affects genetic algorithm performance, adding graphs to the evolutionary programmer's bag-of-tricks should be beneficial. Also, since graph evolution operates directly on the phenotype, genotype to phenotype decoding is eliminated.",

notes = "see \cite{globus:2001:GECCO}",