%0 Generic %1 globus:2001:GECCOtr %A Globus, Al %A Atsatt, Sean %A Lawton, John %A Wipke, Todd %D 2000 %K algorithms, genetic programming %T Graph Crossover %U http://people.nas.nasa.gov/~globus/papers/JavaGenes2/JavaGenesPaper.html %X 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-60% 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.

@misc{globus:2001:GECCOtr, 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-60% 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.}, added-at = {2008-06-19T17:35:00.000+0200}, author = {Globus, Al and Atsatt, Sean and Lawton, John and Wipke, Todd}, biburl = {https://www.bibsonomy.org/bibtex/227594351fe6e2b04a8121e74d64c8919/brazovayeye}, howpublished = {www}, interhash = {928c81629bd760af142e3c7c47d57684}, intrahash = {27594351fe6e2b04a8121e74d64c8919}, keywords = {algorithms, genetic programming}, month = {5 May}, notes = {see \cite{globus:2001:GECCO}}, timestamp = {2008-06-19T17:40:21.000+0200}, title = {Graph Crossover}, url = {http://people.nas.nasa.gov/~globus/papers/JavaGenes2/JavaGenesPaper.html}, year = 2000 }