Genetic Programming, Probabilistic Incremental Program
Evolution, and Scalability
R. Ondas, M. Pelikan, and K. Sastry. WSC10: 10th Online World Conference on Soft Computing
in Industrial Applications, page 363--372. On the World Wide Web, (19 September - 7 October 2005)
Abstract
We discuss scalability of standard genetic programming
(GP) and the probabilistic incremental program
evolution (PIPE). To investigate the need for both
effective mixing and linkage learning, two test
problems are considered: ORDER problem, which is rather
easy for any recombination-based GP, and TRAP or the
deceptive trap problem, which requires the algorithm to
learn interactions among subsets of terminals. The
scalability results show that both GP and PIPE scale up
polynomially with problem size on the simple ORDER
problem, but they both scale up exponentially on the
deceptive problem. This indicates that while standard
recombination is sufficient when no interactions need
to be considered, for some problems linkage learning is
necessary. These results are in agreement with the
lessons learned in the domain of binary-string genetic
algorithms (GAs). Furthermore, the paper investigates
the effects of introducing unnecessary and irrelevant
primitives on the performance of GP and PIPE.
WSC10: 10th Online World Conference on Soft Computing
in Industrial Applications
year
2005
month
19 September - 7 October
pages
363--372
organisation
World Federation of Soft Computing (WFSC), European
Neural Network Society (ENNS), North American Fuzzy
Information Processing Society (NAFIPS), European
Society for Fuzzy Logic and Technology (EUSFLAT), and
International Fuzzy Systems Association (IFSA)
%0 Conference Paper
%1 ondas:2005:WSC
%A Ondas, Radovan
%A Pelikan, Martin
%A Sastry, Kumara
%B WSC10: 10th Online World Conference on Soft Computing
in Industrial Applications
%C On the World Wide Web
%D 2005
%E Knowles, Joshua
%K PIPE, algorithms, genetic order problem problem, programming, scalability, scaling, trap
%P 363--372
%T Genetic Programming, Probabilistic Incremental Program
Evolution, and Scalability
%U http://isxp1010c.sims.cranfield.ac.uk/Papers/paper122.pdf
%X We discuss scalability of standard genetic programming
(GP) and the probabilistic incremental program
evolution (PIPE). To investigate the need for both
effective mixing and linkage learning, two test
problems are considered: ORDER problem, which is rather
easy for any recombination-based GP, and TRAP or the
deceptive trap problem, which requires the algorithm to
learn interactions among subsets of terminals. The
scalability results show that both GP and PIPE scale up
polynomially with problem size on the simple ORDER
problem, but they both scale up exponentially on the
deceptive problem. This indicates that while standard
recombination is sufficient when no interactions need
to be considered, for some problems linkage learning is
necessary. These results are in agreement with the
lessons learned in the domain of binary-string genetic
algorithms (GAs). Furthermore, the paper investigates
the effects of introducing unnecessary and irrelevant
primitives on the performance of GP and PIPE.
%@ 3-540-29123-7
@inproceedings{ondas:2005:WSC,
abstract = {We discuss scalability of standard genetic programming
(GP) and the probabilistic incremental program
evolution (PIPE). To investigate the need for both
effective mixing and linkage learning, two test
problems are considered: ORDER problem, which is rather
easy for any recombination-based GP, and TRAP or the
deceptive trap problem, which requires the algorithm to
learn interactions among subsets of terminals. The
scalability results show that both GP and PIPE scale up
polynomially with problem size on the simple ORDER
problem, but they both scale up exponentially on the
deceptive problem. This indicates that while standard
recombination is sufficient when no interactions need
to be considered, for some problems linkage learning is
necessary. These results are in agreement with the
lessons learned in the domain of binary-string genetic
algorithms (GAs). Furthermore, the paper investigates
the effects of introducing unnecessary and irrelevant
primitives on the performance of GP and PIPE.},
added-at = {2008-06-19T17:46:40.000+0200},
address = {On the World Wide Web},
author = {Ondas, Radovan and Pelikan, Martin and Sastry, Kumara},
biburl = {https://www.bibsonomy.org/bibtex/22d9f8f78cdd0b609b4fc59b372eef1a4/brazovayeye},
booktitle = {WSC10: 10th Online World Conference on Soft Computing
in Industrial Applications},
editor = {Knowles, Joshua},
email = {ondasr@umsl.edu pelikan@cs.umsl.edu ksastry@uiuc.edu},
interhash = {499afba369febbcc812f8f60da3e0590},
intrahash = {2d9f8f78cdd0b609b4fc59b372eef1a4},
isbn = {3-540-29123-7},
keywords = {PIPE, algorithms, genetic order problem problem, programming, scalability, scaling, trap},
month = {19 September - 7 October},
notes = {http://www.cranfield.ac.uk/wsc10/ broken Cf
\cite{1068310}.
Experimental, ORDER, TRAP, JOIN, NEG_JOIN, JUNK.
Linkage learning and EDAs should be applied to
GP.
http://isxp1010c.sims.cranfield.ac.uk/Presentations/presentation122.pdf
broken slides (1.3Mbyte)},
organisation = {World Federation of Soft Computing (WFSC), European
Neural Network Society (ENNS), North American Fuzzy
Information Processing Society (NAFIPS), European
Society for Fuzzy Logic and Technology (EUSFLAT), and
International Fuzzy Systems Association (IFSA)},
pages = {363--372},
size = {10 pages},
timestamp = {2008-06-19T17:48:55.000+0200},
title = {Genetic Programming, Probabilistic Incremental Program
Evolution, and Scalability},
url = {http://isxp1010c.sims.cranfield.ac.uk/Papers/paper122.pdf},
year = 2005
}