On the time and space complexity of genetic programming for evolving Boolean conjunctions

摘要: Genetic Programming (GP) is a general purpose bio-inspired meta-heuristic for the evolution of computer programs. In contrast to several successful applications, there little understanding working principles behind GP. In this paper we present performance analysis that sheds light on the behaviour simple GP systems evolving conjunctions of n variables (ANDn). The random local search system with minimal terminal and function sets reveals relationship between number iterations and the expected error evolved program on complete training set. Afterwards consider more realistic system equipped global mutation operator prove that it can efficiently solve ANDn by producing programs linear size fit training set optimality high probability generalise well. Additionally, general problems which extend undesired variables or negated variables. presence undesired variables, that, if non-strict selection used, then the algorithm fits complete while the strict may fail probability unless substitution switched off. presence of negations, show while algorithms fit the set, constructed solutions generalise well. Finally, from problem hardness perspective, reveal the existence small sets allow of the exact conjunctions even in negations of undesired