Reliability of performance measures in tree-based genetic programminga study on Koza's computational effort

Resumo

The measure of computational effort was proposed by John R. Koza in his book Genetic Programming: On the Programming of Computers by Means of Natural Selection, as a method to assess algorithm performance. This measure estimates the minimum number ofindividuals that have to be processed by a generational Evolutionary Algorithm in order toachieve at least one success with a certain given probability. Computational effort has hada strong influence in the Genetic Programming community, and has been widely used as aperformance measure.Several researchers have shown some concerns, through informal channels, about thebehaviour of this measure, but there is little evidence in the literature to support this perception. This PhD thesis is an attempt to determine whether the concerns about the reliabilityof Koza's computational effort are solid and therefore it is a unreliable measure, or, on thecontrary, these concerns have no sound support. In order to answer whether computationaleffort is reliable or not, the goal of the dissertation is to model the error associated to theestimation of this measure. The developed model is essentially theorerical, but some partsare based on empirical evidence.The main conclusion of the thesis is that there are sound reasons to doubt the reliability of Koza's computational effort and should therefore no longer be used. Other simpler measures,such as the success probability or the average number of evaluations to a solution should beused instead.Futher contributions include the proof that the success rate in Evolutionary Computationis binomially distributed; a characterization of some binomial con¿dence interval methods; anew method to estimate the success probability; and a run-time analysis of tree-based GeneticProgramming. In addition, some methods to solve real world problems in the domains oflanguage induction, RFID and logistics are developed.