Scaling of program fitness spaces.
We investigate the distribution of fitness of programs concentrating on those represented as parse trees and, particularly, how such distributions scale with respect to changes in the size of the programs. By using a combination of enumeration and Monte Carlo sampling on a large number of problems from three very different areas, we suggest that, in general, once some minimum size threshold has been exceeded, the distribution of performance is approximately independent of program length. We proof this for both linear programs and simple side effect free parse trees. We give the density of solutions to the parity problems in program trees which are composed of XOR building blocks. Limited experiments with programs including side effects and iteration suggest a similar result may also hold for this wider class of programs.
Langdon
W B
WB
Centrum voor Wiskunde en Informatica, Kruislaan 413, NL-1098 SJ, Amsterdam, The Netherlands. W.B.Langdon@cwi.nl
D000465:Algorithms; D003198:Computer Simulation; D016014:Linear Models; D008957:Models, Genetic; D015233:Models, Statistical; D009010:Monte Carlo Method; D012044:Regression Analysis; D013269:Stochastic Processes