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.

A New Schema and Landscape for Programs

Dr Kaur and I sent a paper on a new schema and landscape for IEEE TEC peer review two weeks ago.

In the paper we showcase the new schema and landscape analyses by applying it to the Santa Fe ant problem. This caused us to discover for the first time the relationship between program structures and program fitness. Traditionally the Santa Fe ant problem is well known for presenting a random fitness relationship when analyzed by any other method.

We also show for the first time the systematic approaches to fitness improvement that programs make during genetic programming runs, thereby showing that the process is very different from what a random search does. We test a new variation and representation method that were designed based on our findings and obtained more efficient evolutionary search.

Please send me an email if you would like a copy for personal review.

We are currently undecided on whether we should post the pre-review paper to Arxiv.org. Any advice?

Making It To The Most Read Articles Lists in 2009

The Paper “Search, Neutral Evolution, and Mapping in Evolutionary Computing: A Case Study of Grammatical Evolution” Wilson, D.   Kaur, D.,  appeared in the July 2009 Top 10 Downloads of the IEEE Transactions on Evolutionary Computing ranked #1.

It also appeared (ranked #27) in the Top 100 Downloads of the entire IEEExplore site for July 2009!

Not bad!

Complete Genotype to Phenotype Tables and Maps Now Online

The Maps and complete Genotype to Phenotype tables for Hierarchical If-and-only-if, as well as the Cartesian Genetic Programming maps and tables are now posted as web-pages on this blog. Please click on the links above to access them. The complete tables were not included in the Neutral Evolution and Mapping paper because of space considerations.

For Your Viewing Pleasure

Below is the first of a series of lectures on Evolution, Ecology and Behavior by Professor Stearns of Yale University.

It has a lot of material that should be of interest to anyone interested in Evolutionary Computing. The fourth video in the series is on neutral evolution and genetic drift.

This series is going to make up a good portion of my holiday viewing.