Traditional flow of control for linear genetic programming includes structures such as if-then-else statements combined with gotos. In this study we examine additional classes of flow of control structures. The first is called the alternator. This is a deterministically variable flow of control that executes a goto every other time it is accessed. We demonstrate that evolution can use alternators that jump past one another to create solutions with significantly more complexity than those created by solutions without alternators for a simple binary string generation problem. The alternator, while clearly useful, would be difficult for human programmers to use effectively. The alternator thus demonstrates a strong disjunction between human-friendly and evolution-friendly programming languages. Domain specific flow of control structures tailored to the environment being studied are also examined. These are statements carefully designed for the problems being solved. Allowing controllers solving the Tartarus task to change the flow of control based on knowledge of their position in the interior boundary of a world substantially enhances the performance of the controllers. Comparison of the three different fitness functions used demonstrates that the benefit of the alternate flow-of-control is domain specific.

The genetic code that maps triples of DNA onto amino acids, is a central part of the biochemistry of life. In this study we incorporate an analogous code, called a translation table, into the self-avoiding walk test problem. Use of a translation table permits evolution of both the distribution of commands and the behavior of the mutation operator. It thus can evolve to encode two types of domain knowledge about the test problem. The translation tables are shown to specialize to specific cases of the test problem but yield no significant improvement in performance. The emergence of encoded problem-specific knowledge in the translation tables is demonstrated. A translation table constructed from extrapolation of the evolutionary trend yields a performance improvement, suggesting that the current algorithm would require more time than that allocated in the experiments to locate translation tables that would enhance performance. A tentative technique for overcoming this limitation is outlined.

Many games have a collection of boards with the difficulty of an instance of the game determined by the starting configuration of the board. Correctly rating the difficulty of the boards is somewhat haphazard and required either a remarkable level of understanding of the game or a good deal of play-testing. In this study we explore evolutionary algorithms as a tool to automatically grade the difficulty of boards for a version of the game sokoban. Mean time-to-solution by an evolutionary algorithm and number of failures to solve a board are used as a surrogate for the difficulty of a board. Initial testing with a simple string-based representation, giving a sequence of moves for the sokoban agent, provided very little signal; it usually failed. Two other representations, based on a reactive linear genetic programming structure called an ISAc list, generated useful hardness-classification information for both hardness surrogates. These two representations differ in that one uses a randomly initialized population of ISAc lists while the other initializes populations with competent agents pre-trained on random collections of sokoban boards. The study encompasses four hardness surrogates: probability-of-failure and mean time-to-solution for each of these two representations. All four are found to generate similar information about board hardness, but probability-of-failure with pre-evolved agents is found to be faster to compute and to have a clearer meaning than the other three board-hardness surrogates.

Cytochrome c oxidase subunit 1 (cox1) is unusual among mitochondrial genes in that instead of using AUG or one of the recognized alternative start codons it often appears to use an unknown means for initiating translation. However, the frequency of this unusual behavior as well as the underlying molecular mechanism are unknown. In this paper we use side effect machines to probe for signal in the sequence. Evolved side effect machines were able to correctly classify cox1 genes with ambiguous start codons 80.1% of the time. Side effect machines are finite state machines that have side effects associated with their states. In this study a simple side effect, a counter for the number of times the state was entered, is used. The problem is found to be challenging, a substantial majority of replicates found no signal, but some classifiers with statistically significant classification ability were located.

This study explores the ability of dynamic polyominos to acquire different types of robustness in a variety of environments. A polyomino is a collection of identical squares joined along their sides to form a connected shape. This study introduces a cellular encoding for polyominos that grow in a manner that adapts to environmental obstructions. Fitness evaluation places polyominos in competition to occupy space with each square of a grid occupiable by only a single individual. Evolved polyomino genomes are studied for their robustness to choice of opponent and environment. This study is part of a series studying the evolution of robustness, enlarging the scope of the series to include robustness against choice of opponent and environment. Polyomino fitness is evaluated in monoculture, multiculture, and obstructed environments. It is found that in all cases added time evolving grants a greater degree of robustness than the other possible sources of robustness. When polyomino genomes have been evolved for comparable amounts of time it is found those with competitive fitness evaluation are superior. When the impact of environmental obstructions are considered it is found that being in your home environment grants a competitive advantage, though not as strong of an advantage as added evolution, with a single exception.

We attack the problem of game balancing by using a coevolutionary algorithm to explore the space of possible game strategies and counter strategies. We define balanced games as games which have no single dominating strategy. Balanced games are more fun and provide a more interesting strategy space for players to explore. However, proving that a game is balanced mathematically may not be possible and industry commonly uses extensive and expensive human testing to balance games. We show how a coevolutionary algorithm can be used to test game balance and use the publicly available continuous state, capture-the-flag CaST game as our testbed. Our results show that we can use coevolution to highlight game imbalances in CaST and provide intuition towards balancing this game. This aids in eliminating dominating strategies, thus making the game more interesting as players must constantly adapt to opponent strategies.

The chaos game, in which a moving point is repeatedly averaged toward randomly selected vertices of a triangle, is one method of generating the fractal called the Sierpinski triangle. The sequence of vertices, called generators, used to reach a given point of the Sierpinski triangle yields a map from strings over a three-character alphabet to points in the plane. This study generalizes that representation to give a character-string representation for points in R". This is a novel representation for evolutionary optimization. With the correct generating points the method is proven to search its entire target domain at an easily controlled resolution. The representation can be used to achieve the same goals as niche specialization at a far lower computational cost because the optima located are specified by strings which can be stored and searched in standard string dictionaries. An implementation of the algorithm called the multiple optima Sierpinski searcher (MOSS) is found to be substantially faster at locating diverse collections of optima than a standard optimizer. The Sierpinski representation has a nummultipleber of natural mathematical properties that are described in the paper. These include the ability to adapt both its search domain and its resolution on the fly during optimization.

This paper investigates the role of selection in the acquisition of mutational robustness for two test problems: rONEMAX and SAW. Three different selection methods: tournament, fitness proportionate, and ranking, were implemented in a geerational genetic algorithm and applied to both problems. The effect of altering the selection pressure for the tournament selection method was investigated by varying the tournament size. For the rONEMAX problem the tournament and ranking selection based algorithms found optimal solutions which were significantly more robust to point mutation than those found by either the fitness proportionate selection algorithm or random sampling of the optimal solution space. Altering the selection pressure had no significant effect on the robustness of the solutions located by tournament selection algorithm for the rONEMAX problem. For the SAW problem, however, tournament selection with a tournament size of four found solutions which were significantly more robust than those located by larger tournament sizes. For the majority of the problem variants explored here the tournament and ranking selection methods proved more effective at locating robust optimal solutions than fitness proportionate selection.

This paper investigates the ability of a tournament selection based genetic algorithm to find mutationally robust solutions to a simple combinatorial optimization problem. Two distinct algorithms (a stochastic hill climber and a tournament selection based GA) were used to search for optimal walks in several variants of the self avoiding walk problem. The robustness of the solutions obtained by the algorithms were compared, both with each other and with solutions obtained by a random sampling of the optimal solution space. The solutions found by the GA were, for most of the problem variants, significantly more robust than those found by either the hill climbing algorithm or random sampling. The solutions found by the hill climbing algorithm were often significantly less robust than those obtained through random sampling. .

Graph based evolutionary algorithms use combinatorial graphs to impose a topology or "geographic structure" on an evolving population. It has been demonstrated that, for a fixed problem, time to solution varies substantially with the choice of graph. This variation is not simple with very different graphs yielding faster solution times for different problems. Normalized time to solution for many graphs thus forms an objective character that can be used for classifying the type of a problem, separate from its hardness measured with average time to solution. This study uses fifteen combinatorial graphs to classify 40 evolutionary computation problems. The resulting classification is done using neighbor joining, and the results are also displayed using non-linear projection. The different methods of grouping evolutionary computation problems into similar types exhibit substantial agreement. Numerical optimization problems form a close grouping while some other groups of problems scatter across the taxonomy. This paper updates an earlier taxonomy of 23 problems and introduces new classification techniques.

This paper extends an earlier study which outlined a bioinformatic pipeline for exploratory search for RNA motifs incorporating both primary and secondary structure. The pipeline is applied to three data sets, one of which is a larger version of that used in the earlier study. Instead of a single method of estimating the distance between RNA folds four distance measures were tested. The data sets are: a set of random control sequences, a set of synthetic sequences with simple designed folds, and the iron response element data set for which actual biological RNA folds are available. The pipeline demonstrates the ability to produce clusters that contain known motifs in the biological data and those designed into the synthetic data. The results for the distance measures varies substantially and one of the measures, difference in energy, is found to be too simplistic to be useful for differentiating motifs. The other three distance measures all demonstrate some degree of merit. At the heart of the pipeline is a non-linear projection algorithm that uses evolutionary computation to display the intra-RNA-fold distances so that the various distance measures can be visually compared. While the performance of this algorithm is acceptable, suggestions for improving it are made.

This study presents a strategy for reducing the effects of noise on the location of RNA motifs in the context of a previously developed analysis pipeline. The pipeline was developed to search for novel RNA motifs incorporating both primary and secondary structure. The ability of the pipeline to detect motifs in the presence of a relatively large amount of sequence not containing a target motif is examined in three different experiments. The first demonstrates the impact of increasing the number of sequences without a particular motif in a synthetic data set. The second experiment looks at how well a known motif, the iron response element, clusters in biological data sets with various amounts of non-IRE motif containing sequence. The final experiment applies and analyzes the effects of a number-near-neighbors filter to winnow data and highlight the presence of the clusters representing motifs. The filter is found to help substantially

Display and visualization of high dimensional data are typically performed with a well-chosen linear projection of the data or by displaying many linear projections to form an animation. This study presents an evolutionary algorithm for producing nonlinear projections of high dimensional data with cues, in the drawing of the projection, as to the types of distortions introduced. Such projections can provide drawings closer to the true high dimensional distances of the displayed data than any single linear drawing. This permits a researcher to view a good analog to a scatter plot for high dimensional data. The system is demonstrated on a synthetic four dimensional fitness landscape and on distance data derived from RNA folds. Because fitness landscapes often have more dimensions than can be easily visualized it is difficult to gain an intuitive understanding of a fitness landscape. The nonlinear projection algorithm is applied to an abstraction of the fitness landscape called a fitness web. Fitness webs can be used to display the relative quality of optima, the frequency with which they were found by different evolutionary runs, or other factors of interest. In addition to displaying the relative position of optima in a fitness landscape, a graph of the fitness function along the edges a fitness web displays important slices of the fitness landscape. Called fitness morphs these plots can provide intuition about the fitness landscapes as well as direction for subsequent evolutionary searches. The second demonstration of the nonlinear projection algorithm is to data generated from an ad hoc metric on RNA folds. The algorithm yields drawings that permit a researcher to correctly distinguish two different types of folds for iron response elements.

Given an evolutionary optimization problem with many possible genotypes for each phenotype this study investigates if the evolved genes for a given phenotype are more robust to point mutation than randomly sampled genes for the same phenotype. This question is addressed using a cellular representation for polyominos in the plane. The evolutionary computation system optimizes for shapes which pack well onto the surface of a torus when dropped at random. For the majority of the evolved phenotypes the evolved genes for a given shape proved to be significantly more robust to point mutation than those sampled at random for that same shape. A few evolved genotypes, however, were not significantly more robust than those sampled at random and in some cases were less robust. These observations are placed in the context of the fitness landscape for the representation.

Evolution and robustness are thought to be intimately connected. Are solutions to optimization problems produced by evolutionary algorithms more robust to mutation than those produced by other classes of search algorithms? We explore this question in a model system based on bivariate real functions. Bivariate real functions serve as a well understood model systems that are easy to visualize. Both the number and robustness of optimal solutions found in multiple trials with several typical optimization algorithms were compared. In the majority of the function landscapes explored the tournament selection evolutionary algorithm found optimal solutions which were significantly more robust to mutation than those discovered by the other algorithms.

Is it possible to achieve some of the benefits of formal testing within the informal programming conventions of the spreadsheet paradigm? We have been working on an approach that attempts to do so via the development of a testing methodology for this paradigm. Our “What You See Is What You Test” (WYSIWYT) methodology supplements the convention by which spreadsheets provide automatic immediate visual feedback about values by providing automatic immediate visual feedback about “testedness”. In previous work we described this methodology; in this paper, we present empirical data about the methodology's effectiveness. Our results show that the use of the methodology was associated with significant improvement in testing effectiveness and efficiency even with no training on the theory of testing or test adequacy that the model implements. These results may be due at least in part to the fact that use of the methodology was associated with a significant reduction in overconfidence.