Using Very Small Population Sizes in Genetic Programming

This paper examines the use of very small (4-7) population sizes in genetic programming. When using exploitive operators, this results in hillclimbing; when using exploratory operators this results in genetic drift. The end result is a different way of searching the space which gives insight into the fitness landscape and the nature of the variation operators used. This study compares the use of very small population sizes with the use of population sizes up to 1000 for three genetic programming problems: 4-parity using parse trees, Tartarus using ISAc lists, and several versions of plus-one-recall-store (PORS) using parse trees. For 4-parity and Tartarus with 60 ISAc nodes, algorithms with very small population sizes found more solutions faster. For PORS, the effect was less pronounced: more solutions were found, but the algorithm was faster only than when using slightly larger populations. For Tartarus with 30 ISAc nodes, no effect was detected.