Abstract:
Genetic programming is a machine learning technique to automatically create computer programs from high-level specifications of a problem. It achieves this goal by genetically breeding a population of computer pro-grams using the principles of Darwinian natural selection and biologically inspired operations. Selection is obtained by attaching to each program a fitness value, which quantifies how well it solves the problem. In spite of the numerous practical successes of genetic programming and the good quality of theory that has been developed until nowadays, some unsolved problems persist. In synthesis: metodologies to predict, or to measure, the difficulty of problems have not been developed yet (i.e. no technique to measure the capability of genetic programming to find good solutions for a given problem exists) and genetic programming is, in general, a slow and resource consuming process. Proposing solutions to these problems is the guiding thread of this thesis.
Two measures of problem difficulty are presented: fitness distance cor-relation (based on the idea that what makes a problem difficult or easy for genetic programming is the relationship between fitness and distance to the goal) and negative slope coefficient (which quantifies some aspects of evolvability, i.e. the ability of genetic operators to produce offsprings that are fitter than their parents). These measures are based on statistical sampling of the search space. Both of them succeed in correctly measuring the dif-ficulty of a wide range of different problems. Advantages and drawbacks of these measures are discussed in depth. Furthermore, a discussion of the concept of fitness landscape, on which these two measures are inspired, is proposed.
Among the main causes of inefficiency of genetic programming, one may mention: premature convergence (or the tendecy to produce populations in which all the individuals have similar characteristics), bloat (or progressive individuals' code growth) and the fact that fitness evaluation often requires
the execution of programs on many different input data (known as fitness cases). This thesis shows how distributing individuals into separate communicating subpopulations naturally counteracts premature convergence and bloat, allowing genetic programming to find solutions of better quality, more quickly. The advantage of parallelizing genetic programming is twofold: on the one hand it enables to achieve time savings by distributing the computational effort on a set of calculating agents, on the other hand, the parallel setting offers benefits from the algorithmic point of view, in analogy with the natural parallel evolution of spatially distributed populations. Furthermore, techniques to dynamically tune the size of populations, and to limit the number of fitness cases to be tested, in order to save computational effort, are proposed.
Version Abrégée
La programmation génétique est une technique du domaine de l'apprentissage artificiel ("machine learning"). Elle permet de créer automatiquement des programmes à partir d'une spécification de haut niveau d'un problème. Elle réalise cet objectif à l'aide d'une population de programmes qui évolue en utilisant les principes de la sélection naturelle darwinienne et des opérateurs inspirés par la Biologie. La sélection est obtenue en attachant à chaque programme une valeur de fitness, qui mesure à quel point ce programme résout le problème. Malgré les succès indéniables de la programmation génétique, quelques problèmes non résolus demeurent. En résumé: aucune méthodologie permettant de prévoir ou de mesurer la difficulté des problèmes n'a encore été développée (ce qui signifie qu'aucune technique n'existe à l'heure actuelle pour mesurer la capacité de la programmation génétique à trouver de bonnes solutions pour un problème donné). Par ailleurs, la programmation génétique reste, en général, un processus lent qui utilise beaucoup de ressources. Ce travail vise à apporter des solutions à ces problèmes.
Deux mesures de difficulté des problèmes sont présentées: la corrélation distance-fitness (basée sur l'idée que ce qui rend un problème difficile ou facile pour la programmation génétique c'est le rapport entre le fitness et la distance au but) et le coefficient de pente négative (qui mesure quelques aspects du processus de l'évolution, c'est-à-dire la capacité des opérateurs génétiques à produire des fils qui ont un fitness meilleur que leurs parents). Ces mesures sont basées sur des échantillons statistiques de l'espace de recherche. Elles réussissent toutes deux à mesurer correctement la difficulté de problèmes de nature différente. Les avantages et les inconvénients de ces mesures sont discutés en détails. En outre, la thèse présente une discussion sur le concept de paysage de fitness, sur lequel ces deux mesures sont basées.
Parmi les principales causes de l'inefficacité de la programmation génétique, on peut mentionner: la convergence prématurée (ou la tendance à produire des populations dans lesquelles tous les individus ont des caractéristiques semblables), le "bloat" (ou croissance progressive du code des individus) et le fait que l'évaluation du fitness exige souvent l'exécution de programmes sur des données d'entrée très différentes (connues sous le nom de "cas de fitness"). Cette thèse montre que la répartition des individus en sous-populations qui communiquent entre elles empêche naturellement la convergence prématurée et le "bloat", permettant ainsi à la programmation génétique de trouver des solutions de meilleure qualité et plus rapidement. L'avantage consistant à paralléliser la programmation génétique est double: il permet un gain de temps en distribuant l'effort de calcul sur un ensemble de processeurs différents, par ailleurs, les systèmes de programmation génétique parallèles offrent des avantages du point de vue algorithmique. Il suffit de se référer à l'évolution naturelle des populations d'êtres vivants, dans lesquelles le parallélisme est implicite. Enfin, cette thèse propose des techniques pour ajuster dynamiquement la taille des populations et pour limiter le nombre de cas de fitness à examiner, afin d'économiser du temps de calcul.