Comparison of tree and graph encodings as function of
problem complexity
M. Schmidt, and H. Lipson. GECCO '07: Proceedings of the 9th annual conference on
Genetic and evolutionary computation, 2, page 1674--1679. London, ACM Press, (7-11 July 2007)
Abstract
In this paper, we analyse two general-purpose encoding
types, trees and graphs systematically, focusing on
trends over increasingly complex problems. Tree and
graph encodings are similar in application but offer
distinct advantages and disadvantages in genetic
programming. We describe two implementations and
discuss their evolvability. We then compare performance
using symbolic regression on hundreds of random
nonlinear target functions of both 1-dimensional and
8-dimensional cases. Results show the graph encoding
has less bias for bloating solutions but is slower to
converge and deleterious crossovers are more frequent.
The graph encoding however is found to have
computational benefits, suggesting it to be an
advantageous trade-off between regression performance
and computational effort.
GECCO '07: Proceedings of the 9th annual conference on
Genetic and evolutionary computation
year
2007
month
7-11 July
pages
1674--1679
publisher
ACM Press
volume
2
organisation
ACM SIGEVO (formerly ISGEC)
publisher_address
New York, NY, USA
isbn13
978-1-59593-697-4
notes
GECCO-2007 A joint meeting of the sixteenth
international conference on genetic algorithms
(ICGA-2007) and the twelfth annual genetic programming
conference (GP-2007).
ACM Order Number 910071
%0 Conference Paper
%1 1277288
%A Schmidt, Michael
%A Lipson, Hod
%B GECCO '07: Proceedings of the 9th annual conference on
Genetic and evolutionary computation
%C London
%D 2007
%E Thierens, Dirk
%E Beyer, Hans-Georg
%E Bongard, Josh
%E Branke, Jurgen
%E Clark, John Andrew
%E Cliff, Dave
%E Congdon, Clare Bates
%E Deb, Kalyanmoy
%E Doerr, Benjamin
%E Kovacs, Tim
%E Kumar, Sanjeev
%E Miller, Julian F.
%E Moore, Jason
%E Neumann, Frank
%E Pelikan, Martin
%E Poli, Riccardo
%E Sastry, Kumara
%E Stanley, Kenneth Owen
%E Stutzle, Thomas
%E Watson, Richard A
%E Wegener, Ingo
%I ACM Press
%K algorithms, expression genetic graphs, programming, regression symbolic trees,
%P 1674--1679
%T Comparison of tree and graph encodings as function of
problem complexity
%U http://doi.acm.org/10.1145/1276958.1277288
%V 2
%X In this paper, we analyse two general-purpose encoding
types, trees and graphs systematically, focusing on
trends over increasingly complex problems. Tree and
graph encodings are similar in application but offer
distinct advantages and disadvantages in genetic
programming. We describe two implementations and
discuss their evolvability. We then compare performance
using symbolic regression on hundreds of random
nonlinear target functions of both 1-dimensional and
8-dimensional cases. Results show the graph encoding
has less bias for bloating solutions but is slower to
converge and deleterious crossovers are more frequent.
The graph encoding however is found to have
computational benefits, suggesting it to be an
advantageous trade-off between regression performance
and computational effort.
@inproceedings{1277288,
abstract = {In this paper, we analyse two general-purpose encoding
types, trees and graphs systematically, focusing on
trends over increasingly complex problems. Tree and
graph encodings are similar in application but offer
distinct advantages and disadvantages in genetic
programming. We describe two implementations and
discuss their evolvability. We then compare performance
using symbolic regression on hundreds of random
nonlinear target functions of both 1-dimensional and
8-dimensional cases. Results show the graph encoding
has less bias for bloating solutions but is slower to
converge and deleterious crossovers are more frequent.
The graph encoding however is found to have
computational benefits, suggesting it to be an
advantageous trade-off between regression performance
and computational effort.},
added-at = {2008-06-19T17:35:00.000+0200},
address = {London},
author = {Schmidt, Michael and Lipson, Hod},
biburl = {https://www.bibsonomy.org/bibtex/2dec1552b5d1662eb63c47020eceb88ba/brazovayeye},
booktitle = {GECCO '07: Proceedings of the 9th annual conference on
Genetic and evolutionary computation},
editor = {Thierens, Dirk and Beyer, Hans-Georg and Bongard, Josh and Branke, Jurgen and Clark, John Andrew and Cliff, Dave and Congdon, Clare Bates and Deb, Kalyanmoy and Doerr, Benjamin and Kovacs, Tim and Kumar, Sanjeev and Miller, Julian F. and Moore, Jason and Neumann, Frank and Pelikan, Martin and Poli, Riccardo and Sastry, Kumara and Stanley, Kenneth Owen and Stutzle, Thomas and Watson, Richard A and Wegener, Ingo},
interhash = {c15a19fe641cf8987eea3338064cc46b},
intrahash = {dec1552b5d1662eb63c47020eceb88ba},
isbn13 = {978-1-59593-697-4},
keywords = {algorithms, expression genetic graphs, programming, regression symbolic trees,},
month = {7-11 July},
notes = {GECCO-2007 A joint meeting of the sixteenth
international conference on genetic algorithms
(ICGA-2007) and the twelfth annual genetic programming
conference (GP-2007).
ACM Order Number 910071},
organisation = {ACM SIGEVO (formerly ISGEC)},
pages = {1674--1679},
publisher = {ACM Press},
publisher_address = {New York, NY, USA},
timestamp = {2008-06-19T17:51:07.000+0200},
title = {Comparison of tree and graph encodings as function of
problem complexity},
url = {http://doi.acm.org/10.1145/1276958.1277288},
volume = 2,
year = 2007
}