This thesis principally addresses some problems in genetic programming (GP) and grammar-guided genetic programming (GGGP) arising from the lack of operators able to make small and bounded changes on both genotype and phenotype space. It proposes a new and flexible representation for genetic programming, using a state-of-the-art formalism from natural language processing, Tree Adjoining Grammars (TAGs). It demonstrates that the new TAG-based representation possesses two important properties: non-fixed arity and locality. The former facilitates the design of new operators, including some which are bio-inspired, and others able to make small and bounded changes. The latter ensures that bounded changes in genotype space are reflected in bounded changes in phenotype space. With these two properties, the thesis shows how some well-known difficulties in standard GP and GGGP tree-based representations can be solved in the new representation. These difficulties have been previously attributed to the treebased nature of the representations; since TAG representation is also tree-based, it has enabled a more precise delineation of the causes of the difficulties. Building on the new representation, a new grammar guided GP system known as TAG3P has been developed, and shown to be competitive with other GP and GGGP systems. A new schema theorem, explaining the behaviour of TAG3P on syntactically constrained domains, is derived. Finally, the thesis proposes a new method for understanding performance differences between GP representations requiring different ways to bound the search space, eliminating the effects of the bounds through multi-objective approaches.

Le fichiers qui accompagnent mon document ont été réalisés avec le logiciel Mathematica / Dans cette thèse, nous étudions la théorie des jeux évolutionnaires dans quelques exemples de populations structurées. En particulier, nous analysons l’évolution de la coopération en déterminant des conditions qui la favorisent dans le cas des interactions par paire. On s’intéresse à l’évolution de la coopération dans un espace phénotypique de dimension quelconque. Puis on étudie la coopération dans une population finie, subdivisée en groupes de même quelconques avec une hiérarchie entre les groupes. Finalement, on présente l’effet de l’aspiration sur le processus évolutif dans une population finie répartie sur un cercle où il y a des positions à occuper. / In this thesis, we study some examples of structured populations. In particular, we analyze the evolution of cooperation in the sense of determining conditions that favor it. We study the evolution of cooperation in a phenotype space of any size. We study also the evolution of cooperation in a finite population subdivided into hierarchical groups of any size. Finally, we study the effect of aspiration on the evolutionary process in a finite population distributed on a circle with only a local interaction by pairwise.