文档介绍：plexity Analysis of Simple ic
Programming On Two Problems Modeling Isolated
Program Semantics
Greg Durrett Frank Neumann Una-May O’Reilly
MIT CSAIL School puter Science MIT CSAIL
32 Vassar Street University of Adelaide 32 Vassar Street
Cambridge, MA 02139 Adelaide, SA 5005, Australia Cambridge, MA 02139
******@ ******@ ******@
ABSTRACT ning trees (see e. g. [9]). These studies have contributed
Analyzing plexity of evolutionary al- substantially to our theoretical understanding of evolution-
gorithms (EAs) for binary search spaces has significantly ary algorithms for binary representations. Poli et al. [13]
informed our understanding of EAs in general. With this state, “we expect to plexity techniques
paper, we start plexity analysis of being used to model simpler GP systems, perhaps GP sys-
ic programming (GP). We set up several simplified GP tems based on mutation and stochastic hill-climbing.” This
algorithms and analyze them on two separable model prob- contribution is a fulfillment of this prediction: its goal is
lems, ORDER and MAJORITY, each of which captures a to show a GP variant that identifies optimal solutions in
relevant facet of typical GP problems. Both analyses give provably low numbers of fitness function evaluations for two
first rigorous insights into aspects of GP design, highlighting much simplified, but still insightful, problems that exhibit a
in particular the impact of accepting or rejecting neutral few simple aspects of program structure.
moves and the importance of a local mutation operator.
The simple parameterized GP algorithm we analyze can
Categories and Subject Descriptors inctly be described as both a hill climber and a random-
ized algorithm. It has four parametric instantiations we call
[Theory putation]: Analysis of algorithms and
(1+1) GP-single, (1+1) GP-multi, (1+1) GP*-single, and
plexity
(1+1) GP*-multi that differ in the acceptance criterion and
the siz