A New Schema and Landscape for Programs: The Santa Fe Ant Case Study

By yours truly and Dr Kaur.http://fav.me/d34dke5

Full paper available at: http://arxiv.org/abs/1312.1858

Abstract: This paper introduces a new schema and a landscape analysis based on executed instruction sequences, and showcases their capabilities by analyzing the structures and evolutionary dynamics of the Santa Fe Ant Problem. The textbook Santa Fe Ant model problem is particularly appropriate for this exercise because after two decades of extensive use and analyses with more conventional schema and landscape analyses, it still lacks a clear narrative of the program structures that are systematically used for fitness improvement, the geometries of those structures and their dynamics during optimization. We use our new schema and landscapes to detail systematic structural features that are the key to high fitness of ant programs. For the first time we detail the evolutionary dynamics of high fitness structures that takes place during Genetic Programming on the problem. We develop a new phenotypic variation method that tests our understanding of the landscape. We also develop a modified function set that tests our understanding of synchronization constraints we identify. We obtain favorable computational efforts compared to those in the literature, on testing the new variation and function set on both the Santa Fe Trail, and the more computationally demanding Los Altos Trail.