UCL  IRIS
Institutional Research Information Service
Please report any queries concerning the funding data grouped in the sections named "Externally Awarded" or "Internally Disbursed" (shown on the profile page) to your Research Finance Administrator. Your can find your Research Finance Administrator at http://www.ucl.ac.uk/finance/research/post_award/post_award_contacts.php by entering your department
Please report any queries concerning the student data shown on the profile page to:

Email: portico-services@ucl.ac.uk

Help Desk: http://www.ucl.ac.uk/ras/portico/helpdesk
Publication Detail
Scaling of Program Functionality
• Publication Type:
Journal article
• Publication Sub Type:
article
• Authors:
Langdon WB
• Publication date:
03/2009
• Pagination:
5, 36
• Journal:
Genetic Programming and Evolvable Machines
• Volume:
10
• Article number:
1
• Print ISSN:
1389-2576
• Notes:
keywords: genetic algorithms, genetic programming, search landscapes, evolutionary computation size: 32 pages
Abstract
The distribution of fitness values (landscapes) of programs tends to a limit as the programs get bigger. We use Markov chain convergence theorems to give general upper bounds on the length of programs needed for convergence. How big programs need to be to approach the limit depends on the type of the computer they run on. We give bounds (exponential in $N$, $N\log N$ and smaller) for five computer models: any, average or amorphous or random, cyclic, bit flip and 4 functions (AND, NAND, OR and NOR). Programs can be treated as lookup tables which map between their inputs and their outputs. Using this we prove similar convergence results for the distribution of functions implemented by linear computer programs. We show most functions are constants and the remainder are mostly parsimonious. The effect of ad-hoc rules on genetic programming (GP) are described and new heuristics are proposed. We give bounds on how long programs need to be before the distribution of their functionality is close to its limiting distribution, both in general and for average computers. The computational importance of destroying information is discussed with respect to reversible and quantum computers. Mutation randomizes a genetic algorithm population in \frac14(l+1)(\log(l)+4) generations. Results for average computers and a model like genetic programming are confirmed experimentally.
Publication data is maintained in RPS. Visit https://rps.ucl.ac.uk
More search options
UCL Researchers
Author
Dept of Computer Science
University College London - Gower Street - London - WC1E 6BT Tel:+44 (0)20 7679 2000