BACKGROUND: The clustering of immune repertoire data is challenging due to the computational cost associated with a very large number of pairwise sequence comparisons. To overcome this limitation, we developed Anchor Clustering, an unsupervised clustering method designed to identify similar sequences from millions of antigen receptor gene sequences. First, a Point Packing algorithm is used to identify a set of maximally spaced anchor sequences. Then, the genetic distance of the remaining sequences to all anchor sequences is calculated and transformed into distance vectors. Finally, distance vectors are clustered using unsupervised clustering. This process is repeated iteratively until the resulting clusters are small enough so that pairwise distance comparisons can be performed. RESULTS: Our results demonstrate that Anchor Clustering is faster than existing pairwise comparison clustering methods while providing similar clustering quality. With its flexible, memory-saving strategy, Anchor Clustering is capable of clustering millions of antigen receptor gene sequences in just a few minutes. CONCLUSIONS: This method enables the meta-analysis of immune-repertoire data from different studies and could contribute to a more comprehensive understanding of the immune repertoire data space.

Divide the dollar is a simpler version of a game invented by John Nash to study the bargaining problem. The generalized divide the dollar game is an n-player version. Evolutionary algorithms can be used to evolve players for this game, but it has been previously shown representation has a profound effect on the success of the evolutionary search. Representation defines both the genome and the move (search) operator used by the evolutionary algorithm. This study investigates how well two representations for a 3-player generalized divide the dollar game, one using a differential evolution move operator and the other a CMA-ES move operator, can find good players implemented as neural networks. Our results indicate both representations can evolve very good player trios, but the CMA-ES representation tends to evolve fairer players.

Solving optimization problems is one of the most complex and widespread task in Computer Science. In many scenarios, finding the global optimum of a function is hampered by several features that characterize the fitness landscapes, such as noisiness, multi-modality, non-convexity, non-separability, and non-differentiability. In order to facilitate the optimization process, a variety of methods have been proposed to manipulate either the search space or the fitness landscape. Among these, Dilation Functions (DFs) were introduced to expand regions of the search space that are characterized by promising fitness values. In this work, we extend the family of DFs by introducing Local Bubble Dilation Functions (LBDFs), a novel approach that generates local distortions bounded by hyper-spheres. By performing an appropriate mapping of the search space, LBDFs can improve the optimization performance, since they expand and reveal the promising regions around the global optimum, while leaving the rest of the fitness landscape untouched. The additional advantage of LBDFs, with respect to DFs, is that different dilations can be applied to each dimension of the search space, which is useful in the case of asymmetric landscapes. In order to show the benefits of local dilations, we executed several tests on the Michalewicz benchmark function, with different settings for the LBDFs. Our results show that a properly designed LBDF can lead to statistically significant better results than using vanilla optimization. Finally, we investigated the use of LBDFs to facilitate the solution of the parameter estimation problem in Systems Biology by analyzing the landscape related to a stochastic model of enzyme kinetics.

Optimization problems represent a class of pervasive and complex tasks in Computer Science, aimed at identifying the global optimum of a given objective function. Optimization problems are typically noisy, multi-modal, non-convex, non-separable, and often non-differentiable. Because of these features, they mandate the use of sophisticated population-based meta-heuristics to effectively explore the search space. Additionally, computational techniques based on the manipulation of the optimization landscape, such as Dilation Functions (DFs), can be effectively exploited to either "compress" or "dilate" some target regions of the search space, in order to improve the exploration and exploitation capabilities of any meta-heuristic. The main limitation of DFs is that they must be tailored on the specific optimization problem under investigation. In this work, we propose a solution to this issue, based on the idea of evolving the DFs. Specifically, we introduce a two-layered evolutionary framework, which combines Evolutionary Computation and Swarm Intelligence to solve the meta-problem of optimizing both the structure and the parameters of DFs. We evolved optimal DFs on a variety of benchmark problems, showing that this approach yields extremely simpler versions of the original optimization problems.

As the Covid-19 pandemic of 2020 illustrates, con-trolling the behavior of social agents is a difficult problem. This study examines the potential for an immune-inspired technique called necrosis to steer the behavior of agent populations that are evolving to play the iterated version of the game prisoner's dilemma. A key factor in this is detection of behavioral types. The use of a previously developed technique for fingerprinting the behavior of game playing agents, even complex ones, permits the modelling of control strategies with necrotic behavioral control (NBC). NBC consists of reducing the fitness of agents engaging in an unacceptable behavior. The impact of applying necrosis to a number of agent behaviors is investigated. The strategies always-defect, always-cooperate, and tit-for-two-tats are used as the foci for behavior control by zeroing out the fitness of agents whose behavior is similar to those agents. Our experiments demonstrate that NBC changes the distribution of prisoner's dilemma strategies that arise both when the focal strategy is changed and when the similarity radius used to zero out agent fitness is changed. Filtration focused on the strategy tit-for-two-tats has the largest impact on the evolution of prisoner's dilemma strategies while always cooperate is found to have the least.

This study compares a current representation for evolving networks to model epidemic spread with a novel representation also studied in a companion paper. This study applies a powerful diversity-friendly algorithm called ring optimization to this novel representation. The problem addressed is that the baseline method is found to optimize only locally; use of the novel representation improves the situation, but not much. The use of ring optimization yields similar or better performance for the ability of the evolved networks to model epidemics while substantially increasing the diversity of those networks.

This study introduces a new game that models competition in foraging behavior. Two moose decide, in each time period, which of three foraging areas to visit. Moose in the same foraging area fight, gaining no forage and also damaging some forage during their conflict. Moose alone in a foraging area eat, with the forage in each field being replenished with a logistic growth model. This creates a relatively complex game with a rich strategy space in which the moose try to maximize their forage intake. The game is a coordination game, as the moose try to avoid conflict which does not maximize forage intake. The paper reports the results of two student competitions at Innopolis University and performs agent evolution to verify the existence of a rich strategy space for the game.

Recent work in representation has developed small, evolvable structures called a complex string generator that generate infinite, aperiodic strings of characters. Such a string can be sectioned to provide an arbitrary list of parameters of indefinite length. Other work in evolving networks to model disease transmission has an issue common in many high-dimensional problems, evolution is less efficient when it must get a large number of parameter values correct. Specifying many parameters with a small evolvable object is a potential solution to this problem. In this study we compare three different implementations of representations, two of which employ complex string generators, to specify social contact graphs that plausibly explain the pattern of infection in a small epidemic. Representations that edit a starting network are found to have results that clump in network space while evolving the adjacency matrix provides increased diversity: none of the representations overlap in their results. The adjacency matrix based representation also generated outliers that outperform a baseline representation, probably because of its enhance diversity of solutions.

Divide the Dollar is a two-player simultaneous game derived from the bargaining game invented by John Nash. This game is interesting because its strategy space contains an entire subspace of Nash equilibria. The large number of moves in the game means that it is somewhat challenging to design agents to play the game. This study examines the problem of designing representations for divide the dollar playing agents and tests a number of representations. It was found that representation and resources allotted were significant factors affecting the agents' performance and that fitness and resources used appeared to be negatively correlated during evolution. This study places agents with different representations into direct competition and finds that there are representations with a strong competitive advantage. Both the choice of representation and the allocation of resources to that representation are found to impact the ability of agents to make bargains and to compete with one another.

This study uses necrosis, a technique from the domain of artificial immune systems, to control the evolution of apoptotic cellular automata. These automata generate complex images that require a very small amount of initial data. The genes that yield these images are embedded in an extremely complex adaptive landscape. The process of controlling the type of images located by applying necrosis is found to be a simple and efficient technique, in comparison to writing more complex fitness functions for the original evolutionary computation system. Two kinds of necrosis are tested, a soft shape based system and a crisp entropy based system. Both sorts of necrosis are found to be able to steer evolution effectively, with the shape based necrosis working well, and the entropy based necrosis having some problems when more extreme forms of necrosis driven filtration are employed. Possible generalizations to steering other evolutionary optimization tasks are outlined.

Cities, while exciting in their visualization and permitting several layouts, do not take into account the placement of crucial characters which might be part of the narrative. Narrative graphs, a connected graph of all potential and existing relations within a game, can enable an ability to find a Nonplayer Character (NPC) who is likely to live nearby, under the assumption that those who interact most frequently are also close in distance. We examine the use of an evolutionary graph compression method and a method using simulated diffusion to cluster features based on relational information about players to generate relationally intimate groups. This clustering can be used to generate information about the game world and cities to inform PCG as to how the connectivity of these areas is, and should be, arranged. The algorithms are validated as being human competitive.

This study updates a novel technique for evolving parameters that specify fractal images. Example parameter sets are provided as an information resource to evolution, following an earlier study. Instead of choosing parameters with high average compatibility with all other parameters, this study clusters the parameters using a graph clustering algorithm within a network where the adjacency relation of the network is derived from co-fertility, i.e. genetic compatibility values. The result of using the new types of sets of parameters as information resources is studied and compared to evolution that uses the previous type of information resource. The new technique of selecting information resources presented here yields higher fitness values. The new results are on the high end of the fitness distribution, and so the new information resources tested give similar improvements in fitness. However, their variability vary substantially and the resulting fractals have different appearances.

Personal contact networks that represent social interactions can be used to identify who can infect whom during the spread of an epidemic. The structure of a personal contact network has great impact upon both epidemic duration and the total number of infected individuals. A vaccine, with varying degrees of success, can reduce both the length and spread of an epidemic, but in the case of a limited supply of vaccine a vaccination strategy must be chosen, and this has a significant effect on epidemic behaviour.In this study we consider four different vaccination strategies and compare their effects upon epidemic duration and spread. These are random vaccination, high degree vaccination, ring vaccination, and the base case of no vaccination. All vaccinations are applied as the epidemic progresses, as opposed to in advance. The strategies are initially applied to static personal contact networks that are known ahead of time. They are then applied to personal contact networks that are evolved as the vaccination strategy is applied. When any form of vaccination is applied, all strategies reduce both duration and spread of the epidemic. When applied to a static network, random vaccination performs poorly in terms of reducing epidemic duration in comparison to strategies that take into account connectivity of the network. However, it performs surprisingly well when applied on the evolved networks, possibly because the evolutionary algorithm is unable to take advantage of a fixed strategy.

Global optimization problems can be effectively solved by means of Computational Intelligence methods. However, there are several areas in which the effectiveness of these algorithms can be hampered by the computational costs of the fitness evaluations, or by specific features of the fitness landscape that can be characterized by noise and by the presence of several (even infinite) local optima. These issues bring about the necessity of defining specific techniques to replace the original problem with a surrogate representation. Fourier surrogate modeling represents a novel and effective approach to generate smoother, and possibly easier to explore, fitness landscapes, and to reduce the computational effort. Fourier surrogates require an initial sampling of the search space that must be performed to calculate the Fourier transforms. In this paper we investigate the impact on the quality of the surrogate models of the hyper-parameters of the methodology, and of several methods that can be employed for the initial sampling of the fitness landscape (i.e., pseudorandom numbers, low discrepancy sequences, a logistic map in chaotic regime, true random positions generated by a quantum computer, and point packing). Our results show that semistructured approaches like quasi-random sequences and point packing can outperform the other sampling methods.

This paper introduces a rapid clustering algorithm called anchor clustering. The algorithm was invented to permit clustering of lymphocyte antigen receptor sequences for veterinary diagnostic applications. Anchor clustering has a slow off-line and a rapid on-line phase. The off-line portion consists of locating a set of points, called anchors, by packing points into the data space so that they satisfy a minimum distance constraint. This study addresses a problem in the anchor location phase of anchor clustering. When used on discrete data, like DNA under the Hamming metric, there is a problem with data that exhibit tied minimum distances to anchors. This can be addressed by finding sets of anchors in which as many of the small distances between anchors are odd. This study tests four methods for locating sets of anchors enriched for short, odd distances. One method, which explicitly scores anchor sets on avoiding ties, works very poorly. A method that encourages odd distances is somewhat more effective, but two methods that optimize the ratio of short odd distances to short even distances achieve substantial enrichment of short odd distances. The reasons for the observed performance of different techniques are explored and possible next steps are outlined.

Evolutionary algorithms are used to generate personal contact networks, modelling human populations, that are most likely to match a given epidemic profile. The Susceptible-Infected-Removed (SIR) model is used and also expanded upon to allow for an extended period of infection, termed the SIIR model. The networks generated for each of these models are thoroughly evaluated for their ability to match nine different epidemic profiles. The addition of the SIIR model showed that the model of infection has an impact on the networks generated. For the SIR and SIIR models, these differences were relatively minor in most cases.

It is important to understand how best to apply a limited number of vaccines to a population such that the spread of a disease, like SARS-CoV-2, is minimized. Although intuition provides a number of mitigation strategies that may be effective, they remain largely untested.A system was developed to test a given disease mitigation strategy. It is designed to work with a graph representing a real social network. A Genetic Programming system was used to discover novel mitigation strategies that are easily interpretable by a public health decision maker.Effective strategies were developed by the GP system. The strategies are easily explainable and intuitive. Novel mitigation strategies were compared to simple baseline strategies with varying success using a number of different metrics. Many of these strategies proved effective in general, however the topology of the graph influences the effectiveness of a strategy.The system has been made publicly available and the authors call on the research community to contribute their own mitigation strategies and measure their efficacy.

This study compares a player using Monte Carlo Tree Search (MCTS) against a variety of well-known Prisoner's Dilemma strategies in 2-player tournaments. The MCTS player has a simple structure and a reasonable computation budget. Nevertheless, it is highly competitive against all tested strategies. As the MCTS player constructs its game tree, it updates the probability of cooperation in response to an opponent's cooperation or defection. The trajectories of these updatings over the course of play are found to converge toward optimal counter-strategies against the particular opponent being played. In some cases the speed of progress toward an optimal counter strategy hinders the MCTS player.

A large series of studies on evolving agents to play mathematical games has demonstrated that many factors can significantly impact which agents arise, when those agents arise during evolution, and how robust they are in their play against other agents. Some or all of these factors have been shown to be relevant in the iterated prisoner's dilemma, the snowdrift game, and a fairly complex game called divide-the-dollar. This study demonstrates the impact or representation and agent resource allocation for a new game called coordination prisoner's dilemma. This paper demonstrates protocols from a recently published book for analysis of agent behavior and extends the work to another game, the first three-move game so treated. A new representation for agents playing mathematical games is introduced, a linear genetic programming register machine. New metrics for agent behavior including total exploitation, strategic variability, and action entropy are introduced. It is found that varying the representation and resource levels within a representation changes the types of game playing agents produced by evolution for coordination prisoner's dilemma.

Point packings in the unit square are placements of n points in the unit square that maximize the minimum distance between any two of the points. Such packings are surrogates for the 2D-stock cutting problem. In this study we examine a greedy generative representation for the point packing problem and extend the problem to higher dimensions. This representation uses a greedy algorithm to select points generated as whole-number linear combinations of vectors. This means that sets of vectors are evolved. The lattice generated by the vectors, taken modulo one, yields a set of points that can be greedily filtered to a dense point packing. The focus of evolution is the choice of vector generators for the lattice. A parameter study is performed comparing two mutation operators, different rates of application for mutation, and different population sizes. The generative representation is found to efficiently locate large point packings, while using relatively few real-valued parameters. The number of real parameters used to specify a point packing may be chosen. This novel control value is shown to have a substantial impact on results. A preliminary application of point packings, as population initializers, is demonstrated. Using a point packing as an initial population for an evolutionary optimizer can yield improved performance by providing more even sampling of the optimization domain and, in this study, it is shown that use of a point packing improves performance in a higher dimensional test problem, but not in a lower dimensional one.

This study uses a real-coded representation to encode discrete strategies for playing a simple grid based game. This representation is able to adapt itself on the fly to the local situation in the game. This adaptability makes the representation particularly suitable for finding good play strategies which, in turn, permit us to explore biases in the play strategies and even to compare instances of the game for difficulty. Variability in the best results achieved by the solver can be used to gauge difficulty, while the shape of the distribution of best results can indicate how interesting an instance is. Results indicate that the variety and combination of affordances produce instances of the game with varying degrees of anticipated difficulty and interestingness, and confirm that the solver can be used to evaluate the quality of different affordance combinations for producing good game instances. Design principles may also be discovered through post hoc analysis of instances with high or low average best score.

Performing repetitive tasks in an industrial setting can typically be accomplished in a variety of ways. In this paper we train virtual agents with kinematic constraints to visit a variety of locations in a manner that optimizes their efficiency. The agents are trained in two ways. The first optimizes only the time required to perform the task, while the second also rewards the agents for the degree to which that perform the work in a particular order, representing a standard for the work. This is an instance of an industrial practice called standard work, and this study shows how to use simple virtual agents as a sandbox for experimentation with standard work. Two techniques for encouraging standard work are tested. The system divorces the agent's control parameters, which are the focus of their training, from their performance, simulating the type of training that must be performed on human workers. The virtual agents can be trained to standard work at a very high rate but, in some agents, with a loss of speed. This is analogous to workers that are difficult to train because of preconceptions about the correct technique for performing a task, another good feature for an experimental sandbox system.

Parameter setting is a persistent task in evolutionary computation made more difficult by the potential for non-linear interactions between the parameters. In this paper, a technique for automating the experimental design for a parameter setting study with an enhanced chance of locating non-linear interactions is presented. The technique is to use a point-packing to located a diverse collection of parameter sets that evenly cover the space of reasonable parameter settings. The point packings here address a problem in an earlier study in which high density point packings can have poor distribution properties for individual parameters. An apparent paradox, in which dense point packings have inferior evenness for individual parameters, is resolved and the technique is tested on a peak-fitting algorithm intended for NMR data.

Creating a representation capable of generating personal contact networks that are most likely to exhibit specific epidemic behavior is difficult due to the inherit volatility of an epidemic and the numerous parameters accompanying the problem. To surpass these hurdles, evolutionary algorithms are used to create a generative solution which generates personal contact networks, modeling human populations, to satisfy the epidemic duration and epidemic profile matching problems. This representation is entitled the Local THADS-N representation. Two new operators are added to the original THADS-N system, and tested with a traditional parameter sweep and a parameter selection method known as point packing on nine epidemic profiles. Additionally, a new epidemic model is implemented in order to allow for lost immunity within a population thus increasing the length of an epidemic.

Complex tasks in Computer Science can be reformulated as optimization problems, in which the global optimum of a given function must be identified. Such problems are typically noisy, multi-modal, non-convex and non-separable, and they require the application of population-based global search metaheuristics to effectively explore the search space. In this work, we address the issue of manipulating the search space of these complex optimization problems to the aim of improving the exploration and exploitation capabilities of metaheuristics. In particular, we show that the implicit assumption in global optimization problems, i.e., that candidate solutions are represented by vectors of values whose meaning has a straightforward interpretation, is not always adequate and that the semantics of parameters can be modified by re-mapping their values in the search space by means of user-defined Dilation Functions. Dilation Functions are general purpose transformations that can be applied to any metaheuristics and optimization problem to "compress" or "dilate" some regions of the search space, allowing to improve the quality of the initial population and the exploitation of promising areas, especially in the case of Swarm Intelligence algorithms. The advantages given by the application of Dilation Functions have been observed by running experiments with Fuzzy Self-Tuning Particle Swarm Optimization and Covariance Matrix Adaptation Evolution Strategies, for the optimization of the Ackley benchmark function and for the parameter estimation of a "synthetic" model of a biochemical system.

This study compares an adaptive and a nonadaptive representation for finding long walks on obstructed grids. This process models adaption of a simple plant to an environment where the plant's ability to grow is impeded by obstructions such as resource poor areas like bare rock. The intent of the adaptive representation is to model the biological phenomenon of phenotypic plasticity in which gene regulation is at least partially in response to environmental cues, in this case the obstructions. The adaptive representation is found to have a substantial advantage, with the greatest level of advantage at intermediate levels of obstruction. Agents are asked to solve multiple problem instances simultaneously (i.e. using the same chromosome). The advantage of the adaptive representation is also found to be higher when more boards are used in fitness evaluation.

Dehydrins are a type of modular, disordered stress protein in plants. They are typically defined by the presence of three motifs called Y-, K-, and S-segments. Their disordered structure and relatively free sequence form make identifying dehydrins a difficult problem. Identification of stress proteins is part of the effort to make the food supply secure in the face of climate change. In this study we used a block-matching character based feature finding method on the do-what‘s-possible representation to distinguish dehydrins from synthetic sequences with the same fourth-order statistics. Good separation is achieved and sets the stage for attempting to locate additional dehydrins and dehydrin-like proteins. The minimum block matching size is found to be a critical parameter.

The Graph Evolution Tool (GET)was built to generate personal contact networks representing who can infect whom within a community. The tool is expanded in order to permit an infection scheme which divides the community into different districts, thus permitting within-district and between-district infections. The evolutionary algorithm comprising GET is expanded upon to simulate communities which include 512 individuals in up to eight districts, initially infecting one person in one district and spreading through a community. The overall goal is to generate communities that will maximize the length of an epidemic. The problem associated with adequately exploring the numerous parameters accompanying evolutionary algorithms is addressed using a point packing and insight from previous work. The Susceptible-Infected-Removed (SIR)model of infection was chosen as it provides a sufficient balance of simplicity and complexity for the problem.

This study compares an adaptive and a non-adaptive implementations of Prisoner's Dilemma playing agents. The adaptive agents implement three interlinked strategies and choose which strategy to use based on environmental cues, in this case the mean score of the agents in the previous generation. The hypothesis under test is that phenotypic plasticity can grant a competitive advantage to agents possessing it. The interlinked strategies are implemented as finite state machines with a thread for each environmental condition; the thread corresponding to the current environmental condition generates the agent's response, but all threads are updated throughout play. It is found that agents with phenotypic plasticity can be superior to agents without it but need not be. Three variations of phenotypic plasticity are studied. One outcompetes the control agents while the control agents outcompete the other two types of plastic agents. Two of the agents with phenotypic plasticity are found to exhibit enhanced levels of cooperation. Other possible implementations of phenotypic plasticity are discussed.

At the 2017 Artificial and Computational Intelligence in Games meeting at Dagstuhl, Julian Togelius asked how to make spaces where every way of filling in the details yielded a good game. This study examines the possibility of enriching search spaces so that they contain very high rates of interesting objects, specifically game elements. While we do not answer the full challenge of finding good games throughout the space, this study highlights a number of potential avenues. These include naturally rich spaces, a simple technique for modifying a representation to search only rich parts of a larger search space, and representations that are highly expressive and so exhibit highly restricted and consequently enriched search spaces. We treat the creation of plausible road systems, useful graphics, highly expressive room placement for maps, generation of cavern-like maps, and combinatorial puzzle spaces.

Automatic generation of level maps is a popular form of automatic content generation. In this study, a recently developed technique employing the do what’s possible representation is used to create open-ended level maps. Generation of the map can continue indefinitely, yielding a highly scalable representation. A parameter study is performed to find good parameters for the evolutionary algorithm used to locate high quality map generators. Variations on the technique are presented, demonstrating its versatility, and an algorithmic variant is given that both improves performance and changes the character of maps located. The ability of the map to adapt to different regions where the map is permitted to occupy space are also tested.

The Ultimatum Game (UG) is studied to see how people respond in bargaining situations. In the 2-player version each round a player can be a proposer or a responder. As a proposer an offer is made on how to split a monetary amount. The responder either accepts or rejects the offer. If accepted, the money is split as proposed; if rejected both players get nothing. Studies have found over time the offers decrease but are still accepted (getting something is better than nothing) until a subgame perfect Nash equilibrium is reached where the lowest possible offer is accepted. In the N-player version the object is to see if the population can reach a state of fairness where, on average, offers are accepted. We have previously shown that a (µ/µ,λ) evolution strategy can evolve offers and acceptance thresholds that promote fairness. In this paper we report an extension to this previous work. One player is added to the population who interacts in the same manner with the other N players. However, this new player is rational—i.e., he ignores fairness and instead exploits the other players by maximizing his payoffs. We used three different versions of Monte Carlo Tree Search (MCTS) to adaptively control this rational player’s offer levels during the game. The results indicate payoffs for this player can be as much as 40% higher than the population average payoff. Our MCTS introduces a novel rollout approach making it ideally suited for the play of mathematical games.

Cellular automata can be used to rapidly generate complex images, but controlling the character of those images can be difficult. This study continues experimentation with fashion-based cellular automata that generate cavern-like level maps and provides the beginning of a mathematical theory. Fashion-based automata are defined by a competition matrix with different cell states competing to capture territory. This study co-evolves pairs of competition matrices to permit the evolution of automata rules that can be spatially morphed to provide substantially more diverse types of maps than earlier systems using fashion-based cellular automata. As in earlier studies, the cellular automata rules function in local neighborhoods, meaning that the level generation system scales smoothly to any desired level map size. This reusability also permits variation of the type of morph used: a variety of spatial morphing styles are tested with the evolved rules. The theoretical treatment includes the derivation of a normal form for the cellular automata rules that informs the design of the fitness function and has application to understanding the fitness landscape of fashion based automata.

BACKGROUND: Detection of central nodes in asymmetrically directed biological networks depends on centrality metrics quantifying individual nodes' importance in a network. In topological analyses on metabolic networks, various centrality metrics have been mostly applied to metabolite-centric graphs. However, centrality metrics including those not depending on high connections are largely unexplored for directed reaction-centric graphs. RESULTS: We applied directed versions of centrality metrics to directed reaction-centric graphs of microbial metabolic networks. To investigate the local role of a node, we developed a novel metric, cascade number, considering how many nodes are closed off from information flow when a particular node is removed. High modularity and scale-freeness were found in the directed reaction-centric graphs and betweenness centrality tended to belong to densely connected modules. Cascade number and bridging centrality identified cascade subnetworks controlling local information flow and irreplaceable bridging nodes between functional modules, respectively. Reactions highly ranked with bridging centrality and cascade number tended to be essential, compared to reactions that other central metrics detected. CONCLUSIONS: We demonstrate that cascade number and bridging centrality are useful to identify key reactions controlling local information flow in directed reaction-centric graphs of microbial metabolic networks. Knowledge about the local flow connectivity and connections between local modules will contribute to understand how metabolic pathways are assembled.

The fertility of two structures in an evolutionary computation system is the expected fitness of their potential offspring. The study uses the problem of locating interesting fractals to introduce an application of fertility intended to reduce user fatigue in Interactive Evolutionary Computation with a human-in-the-loop evaluation method. High fertility sets of fractal parameters are shown to substantially increase the performance of evolution using small population size, a surrogate for human-driven selection. The high fertility sets of fractal parameters are a form of automatically generated content that is part of an application intended to permit a user to find pleasing fractals.

A majority of studies training agents to play mathematical games with evolution use a single population. For games with embedded conflict, like iterated prisoner's dilemma, this can yield interesting behavior, but that behavior may be partly the result of genetic collusion. This study implements a two-population agent training model in which all play is between populations, while breeding is within the populations. Results suggest that genetic collusion is at least partially responsible for the emergence of cooperation in evolutionary studies of the iterated prisoner's dilemma. This study implements a novel finite state representation called a binary decision automata that relies only on information about the agent and opponent's scores, not the moves they made, making it easy to study multiple games. The agents are applied to two games in addition to prisoner's dilemma. The first is the graduate school game, which has a beneficial strategy that is unstable and so cannot arise in a single-population training environment. The strategy is found to arise in two-population environments. The system is also tested on a simple coordination game to verify that the agent training system is functioning nominally.

The Ultimate Game (UG) is a two-player, sequential economic game widely used to study how people act in bargaining situation. One player is a proposer who offers a split in an amount of money. The other player is a responder who accepts or rejects the offer. If accepted the money is split as proposed. If rejected both players get nothing. The “rational” outcome is for each player to maximize his own utility. That is, the proposer offers as little as possible and the responder accepts any offer greater than zero (a sub-game perfect Nash equilibrium). However, UG human experiments show people act irrationally by rejecting low offers because they are considered unfair. Why fairness emerges in N-player ultimatum games is an open question. Here we use a (μ/μ, λ) -ES to evolve ultimatum game strategies. In all UG simulations there is a minimum acceptable offer; offers below this level are always rejected. What is unique about our model is the players use a sigmoid function with a parameter α to decide whether offers lower than the minimum acceptable offer should be accepted anyway. This mimics the way humans bargain in real estate transactions. Results show that if α is sufficiently large, fairness emerges in the population without augmenting the model with functions to artificially simulate empathy or punishment as is done elsewhere.

The accurate modeling of epidemics on social contact networks is difficult due to the variation between different epidemics and the large number of parameters inherent to the problem. To reduce complexity, evolutionary computation is used to create a generative representation of the epidemic model. Previous gains from the use of local, verses global, operators are further explored to better balance exploration and exploitation of the genetic algorithm. A typical parameter study is conducted to test this new local operator and the new method of point packing is utilized as a proof of concept to perform a better search of the parameter space. All experiments from both approaches are tested against nine epidemic profiles. The point-packing driven parameter search demonstrates that the algorithm parameters interact substantially and in a non-linear fashion, and also shows that the good parameter settings are problem specific.

Hierarchical clustering via neighbor joining, widely used in biology, can be quite sensitive to the addition or deletion of single taxa. In an earlier study it was found that neighbor joining trees on random data were commonly quite unstable in the sense that large re-arrangements of the tree occurred when the tree was reconstructed after the deletion of a single data point. In this study, we use an evolutionary algorithm to evolve extremely stable and unstable data sets for a standard neighbor-joining algorithm and then check the stability using a novel type of clustering called bubble clustering. Bubble clustering is an instance of associator clustering. The stability measure used is based on the size of the subtree containing each pair of taxa, a quantity that provides an objective measure of a given trees hypothesis about the relatedness of taxa. It is shown experimentally that even in data sets evolved to be stable for a standard neighbor joining algorithm, bubble clustering is a significantly more stable algorithm.

Modern data acquisition has forced the field of large data on the scientific community. This papers gives a rapid technique for clustering data. The technique is based on an off-line process for packing points chosen from a data space. Once the off-line process has been run, the clustering may be re-run on different data sets of the same type in linear time. The clustering takes the form of a Voronoi tiling of the data space with the tile centres being the elements of the point packing. The data items within each tile form the clusters. The evolutionary algorithm is an adaptation of one, based on the Conway crossover operator, that has been used to create error correcting codes over the Levenstein metric; the tile centres are a form of code, but over the Euclidean metric. The technique generalizes smoothly to other metric spaces and may be used on any type of data for which a distance metric can be devised. The data set used in this study captures information about codon usage bias in human genes. The clustering is validated by looking for GO term over- representation in the clusters, with significant results.

Divide the dollar is a two-player simultaneous game derived from a game invented by John Nash because its strategy space contains an entire subspace of Nash equilibria. This study applies a family of generalizations of divide the dollar, called set-based divide the dollar, to the problem of understanding the impact of undependable subsidies. Set based divide the dollar defines a family of games with easily controlled properties making it ideal for this modeling task. These subsidies are intended to encourage deal making but, if abruptly discontinued or funded unreliably, may have different effects from those intended. The study also demonstrates the generalization of the game to three players, something that the set-based formalism makes easy. Agents are encoded using a finite state representation that conditions its transitions on the result of deals. These results fall into three categories, the agent obtains the highest amount, the agent receives a lesser amount, or the agents fail to make a deal. This study compares a situation with no subsidies with dependable and undependable subsidies, using the rate at which deals are made as a assessment statistic. Two sorts of undependability are studied, abrupt cessation of the subsidy and unreliable funding.

A deck-based game is a game derived from a mathematical game by placing instances of its moves on a deck of cards. Initial work on deck-based games demonstrated that imposing the deck formalism can completely change the nature of the game. In this study, an evolutionary algorithm is used to design decks for a deck-based version of John Nash's classic game divide-the-dollar. The deck-based game is called FRAX and is used for helping students learn the arithmetic of fractions. The game includes a version that uses fraction multiplication, but focuses on addition since this is the more difficult of the basic operations with fractions. The deck design algorithm uses a novel evolutionary strategy called the horde of dumb agents technique to compare and evaluate different decks. Evolution, within the horde of dumb agents strategy, is a uniquely valuable tool for understanding how naive players might approach a new game. It is shown that the techniques presented in this study are able to obtain useful information about decks and new design principles for FRAX decks are discovered. These discoveries include an heuristic for deck difficulty based on strategically matching and non-matching subsets of the cards.

This study is the second using real-coded representation for problems usually solved with a discrete coding. The adaptive generative representation is able to adapt itself on the fly to prior parts of the construction of an object as it assembles it. In the initial study the ability of the representation to take user supplied or problem supplied biases that change its behavior was demonstrated but not explored. In this study the bias is used to change the way evolution explores a fitness landscape for both an RFID antenna design problem and small instances of the traveling salesman problem. Addition of a bias to two different generative representations promotes the evolution of longer antenna designs (a heuristic objective associated with good antennas) while leading the algorithm to generate designs with distinctive shape characteristics. For the traveling salesman, a simple inverse-distance bias for the adaptive generative representation causes a large improvement in performance over a random key representation in 99 of 100 instances studied.

This study performs simulations inspired by the reported genome meltdown of a small population of woolly mammoths prior to their extinction. These simulations test the interaction of population size, mutational diameter, and fitness change on two types of fitness landscapes. The first landscape studies a population initialized at a global optimum to assess fitness loss, while the second uses an open-ended function with no global optimum to assess the degree of adaptive radiation possible with different population sizes. Both an age structured non-elitist evolutionary algorithm and a evolution-strategy like biased random walk are used. The simulations demonstrate that small populations are substantially worse at retaining fitness when initialized in a global optimum but also have a substantially greater potential for adaptive radiation and discovery of new niches.

Automatic classification of DNA can be performed in a number of ways using a variety of features. This study introduces a novel technique for generating global features for DNA classification. Based on a new technique, the “do what's possible” representation, infinite string generators are evolved to produce strings with a maximized collection of matching blocks above a critical length in the target DNA. Most global DNA features, such as GC-content or those in spectrum string kernels, capture diffuse statistical information about the target DNA. Infinite string matching is based on multiple loci, and thus finds a different type of global feature than most techniques now in use. It is discovered that the block-matching score for evolved infinite string generators is able to cleanly separate high-entropy synthetic DNA data sets using a single feature threshold classifier. Preliminary evaluation on human endogenous retrovirus sequences shows that evolved infinite string generators locate promising features on biological data as well.

Embeddable biomarkers are short strands of DNA that can be incorporated into genetic constructs to enable later identification. They are drawn from error correcting codes on the DNA alphabet relative to the Levenshtein metric. This study uses three types of evolutionary algorithms to improve the best known size of DNA error correcting codes, improving the bound for nine different code parameters. One of the algorithms is used on only one set of code parameters, correcting an oversight in an earlier study. The other two algorithms are a ring optimizer and a hybridizing evolutionary algorithm that exploits previously known codes. The ring optimizer improves two code size bounds and sets the stage for the hybridizer to improve four more. The hybridizer requires the results of a previous search as a starting point. Starting with known codes from earlier work, it improves a total of six bounds. The best results found by this algorithm used the results of the ring optimizer as a starting point. The paper discusses the issue of building a suite of cooperative code-search algorithms as a good target for future work.

Boolean networks are used to model gene regulatory networks at a relatively high level. Finding Boolean networks with particular properties requires a representation that permits efficient search. In this study a novel representation for Boolean networks is implemented that segments the functioning of the network model that defines the network into discrete pieces. This design is intended to facilitate crossover-based retention of functionality in the networks, i.e. to make properties in an evolving population more heritable. The representation is tested on three different fitness functions and, on one of them, compared to the direct evolution of the entries of a matrix. The fitness function used to compare the novel and direct matrix representation demonstrates substantial superiority of the novel representation. The other two functions demonstrate the effectiveness of the new representation at a diversity of tasks. The representation, while useful for Boolean networks, has a number of potential applications to other domains.

The lac operen in E. coli is one of the earliest examples of an inducible system of genes being under both positive and negative control that is capable of showing bistability. In this paper, we present a methodology to infer synthetic threshold Boolean regulatory networks of a reduced model of the lac operon using evolutionary computation. The formulation consists in a vector representation of the solutions (networks) and a fitness function specially designed to correctly simulate the bistability through the models' fixed points. We compared the effectiveness and efficiency (runtime) of the proposed approach using three evolutionary computation techniques: differential evolution, genetic algorithms, and particle swarm optimization. The results showed that the three algorithms are capable of finding solutions, being differential evolution the most effective, whereas genetic algorithms was the least effective and efficient in terms of runtime. Particle swarm optimization obtained a good trade-off between effectiveness versus efficiency. One of the inferred solutions was analyzed showing some interesting biological insights, as well as correctly being able to model bistability without any spurious attractors. Overall, the proposed formulation was effective to infer bistable lac operon models under the threshold Boolean network paradigm.

The iterated prisoner's dilemma is a simultaneous two-player game widely used in studies on cooperation and conflict. Recent research has demonstrated that a number of factors change the behavior of evolved agents in a manner not consistent with controlled studies. This study extends a preliminary exploration of the impact of changing the level of computational or informational resources available to game playing agents on their ensemble behavior. Both these categories of information are shown to have an impact on agent behavior. Four representations are studied: lookup tables, Markov chains, finite-state machines, and feed-forward neural nets. An assessment tool called the play profile is used to demonstrate that both the cooperativeness and the change in cooperativeness over evolutionary time are substantially different for different resource levels within a representational type. Lookup tables and neural nets are found to change the least when the resource levels they are presented with are varied, while Markov chains vary the most. Available internal resources are also found to change the competitive ability of agents as well as the rate at which they become cooperative as evolution proceeds.

Partitioning regression is the simultaneous fitting of multiple models to a set of data and partitioning of that data into easily modelled classes. The key to partitioning regression with evolution is minimum error assignment during fitness evaluation. Assigning a point to the model for which it has the least error while using evolution to minimize total model error encourages the evolution of models that cleanly partition data. This study demonstrates the efficacy of partitioning regression using two or three models on simple bivariate data sets. Two novel multi-model representations, a simple evolutionary parameters setting algorithm and one based on using directed acyclic graphs representations for genetic programming are used. Possible generalizations to the general case of clustering are outlined.

Divide the dollar is a two-player simultaneous derived from a game invented by John Nash because its strategy space has an entire subspace of Nash equilibria. This study describes and explores a family of generalizations of divide the dollar with easily controlled properties. If we view divide the dollar as modeling the process of making a bargain, then the generalized game makes it easy to model the impact of external subsidies on bargaining. Classical divide the dollar is compared to four generalizations representing a simple subsidy in three different amounts and a more complex type of subsidy. The distribution of simple strategies that arise under replicator dynamics is compared to the bids that arise in populations of evolving, adaptive agents. Agents are encoded using a finite state representation that conditions its transitions on the result of bargains. These results fall into three categories, the first player obtains a higher amount, the second one does, or the agents fail to make a deal. The replicator dynamic results are compared to obtain the naive degree of distortion caused by the subsidies. The results for evolving agents are then examined to figure out the degree to which adaption compensated for or amplifies this distortion.

Point packings in the unit square are placements of n points in the unit square that maximize the minimum distance between any two of the points. Such packings are surrogates for the 2D-stock cutting problem, giving a natural application domain. In this study we examine a unique representation for the point packing problem and extend the problem to higher dimensions and more complex shapes. The representation uses the Conway operator, a k-ary variation operator based on the lexicode algorithm. Three applications of point packings are demonstrated. A parameter study for the Conway operator based algorithm is performed demonstrating that large populations are uniformly desirable but that the part of the operator that corresponds to mutation has a strongly problem dependent value for good performance. The three applications demonstrated are selecting well-spaced RGB color palettes, initialization of populations in an evolutionary optimizer, and fast clustering of codon usage data. Color palettes of different size are presented. The optimization application is found to gain substantial performance by using point packings as initializers. The bioinformatics application demonstrates significantly non-random clustering of a family of intrinsically disordered proteins known as dehydrins.

If the complexity of a string is measured by the number of distinct non-contiguous substrings (those with characters spaced out along the sequence) it has, then complexity increases the probability that one of its substrings will solve a given problem. In this study a collection of representations called Do What's Possible representations are presented. The representations consist of an evolvable module that generates complex strings of arbitrary length together with a generative possibility filter that selects a non-contiguous substring for its ability to solve one of several test problems. The filter acts by rejecting loci that encode an impossible or counterproductive action. Two types of string-generation modules are compared. Initial experiments verify that the string generators can be evolved to find complex strings, as characterized by the entropy of the distribution of fixed-length substrings, and subsequent experiments demonstrate the system solves a number of different problems. Parameter studies are performed to tune the representation. Remarkable performance is achieved on the SAW test problem and the technique also constructs 8-dimensional Gray codes and is able to distinguish classes of DNA sequences.

The iterated prisoner's dilemma is a simultaneous two-player game widely used in studies on cooperation and conflict. Past work has shown that the choice of representation or available resources such as the number of states or neurons of evolving agents has a large impact on the behavior of evolved agents. This study revisits three qualities of the agent training algorithm for finite state agents to examine their impact on agent behavior: population size, elite fraction, and the number of states the agent is permitted. All three of these algorithm parameters are shown to have an impact on the character of evolved agents. Assessment of agent behavior is performed using three tools. The first is play profiles which bin the ranges of score space. The total score assessment, a global characterization of the type of play that occurs over the course of evolution, is the second assessment used. For the third assessment, an analysis of the ability of agents with different numbers of states to compete with one another is performed. High elite fractions in the training algorithm are found to encourage cooperation. Larger populations increase cooperation for populations of agents with small and intermediate numbers of states but have little effect for agents with large numbers of states. As in past studies with fixed population size and elite fraction, agents with large numbers of states are found to have more diverse and less cooperative behavior. Having more states is also found to grant a competitive advantage.

This study introduces a novel generative representation that is able to modify its expression in response to admissibility constraints that unfold as solutions are generated. The effect is that this self-adaptation in expression makes many inadmissible structures impossible to encode. The resulting reduction in the effective size of the search space yields performance increases amounting to several orders of magnitude for some problems. In addition to defining and exploring the capabilities of the self-adaptive representation, a technique for biasing its expression with numerical weights that strongly influences which optima are located is introduced. This both permits enhancement of optima with desirable properties and permits the inclusion of domain knowledge to improve performance. The test problems used are the self-avoiding walk problem, a surrogate for RFID tag antenna design, and the Towers of Hanoi problem.

A polyomino puzzle is a collection of polyominos that can be joined to make a simple shape. The game Ten-Yen was one of the first of these. It has ten polyomino pieces that could be used to make a 6×6 square in a variety of ways. In this study we define representations and fitness functions for generating polyomino puzzles as well as developing a simple solver to compare the evolved puzzles. The solver can be used to approximate the number of solutions and hence the relative difficulty of the puzzles. Two types of fitness functions are compared, the second of which was developed to deal with scaling issues that arose with the first. A parameter study on the algorithm is performed and it is found that simply penalizing bad results is more effective than parameter tuning. This study concludes by discussing potential puzzle variants.

This study extends an earlier generative representation for the evolution of graphs to include a local reconfiguration operator, the hop operator, and a null operator. The hop operator is shown to be more effective in evolving graphs with a particular geometric character (eccentricity sequence). The null operator permits evolution to select the number of active commands used, avoiding a problem with needing to tune a “gene length” parameter. The representation is parametrized by the probability of each command appearing in initial populations and during mutation. A parameter study leads to a number of rules of thumb for using the new representation and it is found that the number of failures to find a solution, in 3000 attempts, varies from 17 in 3000 as the parameters are changed. The representation is tested on 100 instances of the eccentricity sequence matching problem. Use of the null operator has the beneficial side effect of reducing observed variation in problem difficulty.

The traditional method of fitting an approximate cumulative probability distribution to a data set is to bin the data in narrow bins and obtain a step function approximation. This technique suffices for many applications, but the resulting object is not a differentiable function making recovery of the underlying probability distribution function impossible. In this study, a unique group theoretic representation is used to define evolvable data warps that can be used to recover continuous, infinitely differentiable versions of the inverse cumulative distribution function. The use of a group theoretic representation permits a simple calculation to transform the evolved object into a cumulative distribution function and, via differentiation, into a probability distribution function. The group used to define the evolvable data warps is the group of bijections of the unit interval. The generators used by evolution are chosen to be differentiable in order to enable the computation of probability distribution functions. Experiments are run using a simple type of evolutionary algorithm to evolve approximate CDFs on seven data sets. The first data set is used to perform a parameter study on the representation length used to evolve the approximate CDFs and comparing two variations of the representation - one of which uses a representational control called gene expression and one of which does not.

This study revisits the test problem of evolving a network that gives the contact structure of a population so as to maximize the length of epidemics based on the network. A novel feature of the study is to use a new representation for network evolution. The representation consists of a sequence of editing commands that modify a starting network to specify a final network evaluated for its epidemic properties. The representation is parametrized by specifying the probability each editing command will be generated in initial populations and during mutation. The original work on long-epidemic networks required a sophisticated type of evolutionary algorithm, the restarting-recentering evolutionary algorithm, to obtain high-fitness results. Use of the new representation permits superior results and obtains them using a simpler type of evolutionary algorithm. A second novel result is the introduction of a new type of tournament selection, useful for at least some types of evolution that use stochastic fitness functions.

This study introduces a parametrized family of representations for evolving graphs together with a benchmark function that is diagnostic of an important quality of a representation for graph evolution, its natural distribution of edge densities. The new benchmark function, the edge maximization function, is equivalent to the trivial OneMax function for some representations and represents a difficult problem for others. The utility of the edge maximization function lies in the fact that the edge density distribution in a graph is a critical parameter for evolving graphs and so performance of a representation on EdgeMax is diagnostic of an important aspect of its behavior. Three cases of the EdgeMax problem are examined using six different parameterizations of the new representation. The representations presented here are generative and so need not have any particular length. For each problem case and parametrization of the representation two lengths of chromosome are examined, one that is just long enough to solve the benchmark problem and one that is 10% longer. The EdgeMax is found to be diagnostic of representation properties.

Extinction is a natural process that drives biological evolution. In this study the impact of introducing extinction operators into ring optimization was examined. Ring optimizers are spatially structured evolutionary optimizers inspired by the biological phenomenon of a ring species. A small initial population is introduced into a ring-structured space and spreads, using the spatial structure to manage the exploration/exploitation trade-off of the algorithm. Extinction operators eliminate a substantial fraction of the current population, in effect resetting the algorithm to a more exploratory state. Two types of extinction operators are tested and compared. The “deluge operator” removes population members with lower fitness while the “asteroid operator” removes population members in a contiguous block of the ring. Three benchmark functions were used, one a discrete simulation and the other two open-ended continuous real functions. The behavior of the extinction operators are different for each of the benchmark functions. The differences in behavior of the extinction operators are explained in terms of the fitness landscapes of the benchmark functions.

A class of fractals called orbit capture fractals are generated by iterating a function on a point until the point's trajectory enters a capture zone. This study uses a digraph based representation for genetic programming to evolve functions used to generate orbit capture fractals. Three variations on the genetic programming system are examined using two fitness functions. The first fitness function maximizes the entropy of the distribution of capture numbers, while the second places a geometric constraint on the distribution of capture numbers. Some combinations of representation and fitness function generate fractals often, while others yield interesting non-fractal images most of the time.

An apoptotic cellular automata consists of an initial state and an updating rule. These specify an automata that grows for a time and then enters a quiescent state. This study generalizes earlier work on evolving 1D apoptotic automata to evolving 2D automata, producing a type of evolved art. Parameter studies are performed and it is found that the most important factors are algorithm runtime and the symmetry of the initial conditions of the automata. Other parameters such as mutation rate and tournament size are found to be relatively soft, as long as they do not take on extreme values. A collection of examples of renderings of evolved cellular automata are provided and steps for additional work to improve the system are outlined. Examination of automata with asymmetric starting conditions shows that the highest fitness individuals are those that follow a growth pattern that restores symmetry. This strongly suggests that optimizing the size of an apoptotic automata that has a symmetric pattern of states is a substantially easier problem.

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.

Extinction is a natural process that drives biological evolution. In this study, the impact of four different extinction operators on the evolution of side-effect machines with a ring optimizer was investigated. Side-effect machines are an emerging technology used to generate features for DNA classification. Ring optimization is a type of evolutionary algorithm inspired by the biological concept of ring species. Previous work showed that ring optimization was an efficient technique for locating good side effect machines with substantial robustness against parameter choice for the optimizer. This study extends that research by incorporating extinction, which has been shown to substantially improve the performance of the ring optimizer on discrete and numerical test problems. Two of the four extinction operators improved the quality of the best outcome, while all four were able to reset the ring optimizer into a more exploratory state.

Embeddable biomarkers are short strands of DNA that can be incorporated into genetic constructs to enable later identification. They are drawn from error correcting codes on the DNA alphabet relative to the Levenshtein metric. This study revisits the Conway variation operator which can serve as a population initializer, mutation operator, or crossover operator depending on its mode of application. The algorithm is applied to a part of the space of code parameters where it had not previously been tested. A parameter setting study establishes that an evolutionary algorithm using this variation operator requires a small population and an intermediate rate of introduction of new material (mutation). Better values, sometimes more than quadrupling previous code sizes, are found for eighteen different code parameters with relatively large word size and high error correction ability. The table of best known code sizes is updated by this study. The parameter study performs comparison with the novel total maximum fitness statistic and a technique for displaying time of last innovation within evolutionary algorithms is introduced.

A chaos automata is a type of side effect machine that serves as a state-conditioned version of the chaos game used to visualize DNA or other linear sequence data. This study performs a parameter study to tune an evolutionary algorithm for locating chaos automata that make relatively dense renderings of two-class DNA data. Both the number of states and the population size turn out to be relatively soft parameters, but there is benefit to tuning the mutation rate. The fitness landscape is found to be rugose and to possess a large number of optima. A reporting tool called time of last innovation is used to provide additional nuance to the traditional reporting of best fitness values. Topics for additional work are outlined, including a demonstration that chaos automata can be averaged to provide an additional avenue to search for effective visualizations. The system is tested on synthetic and biological data.

Tools for processing biological data often have many parameters, but most users simply use the default settings. Such software often has a large number of controls or user specified parameters. This means that there can be problems with teaching users to use even standard bioinformatic tools effectively. This study prototypes a technique called a show-me-more interface that uses human-in-the-loop evolution to permit an untutored user to operate a complex software tool that designs images of flowers. This task is intended to permit research on managing complex parameters for users that do not understand them without the added complexity of working with biological data. Users are given two specific and two nonspecific tasks and the results of their design efforts are displayed and discussed. The basic concept of show-me-more control has broad applications for permitting casual users to manipulate complex tools in a simple and transparent manner. Careful design can minimize the number of clicks needed for a user to reanalyze data, reducing the potential for user fatigue and attendant error.

Given a set of potential species and a replicator dynamic model of their interaction, the community assembly problem seeks the maximal set of species that can co-exist indefinitely without extinction. In this study we compare a standard model, which assembles a community one species at a time, with an evolutionary algorithm that selects sets of species directly. The comparison is performed using a standard competition model. The system is tested with three different available species pools of one hundred species. The diversity of communities located with the evolutionary algorithm substantially exceeds that of those located by serial addition of single species. In agreement with past research, the serial species addition algorithm located communities that, while not the largest, were highly resistant to invasion by a single additional species. A comparison of the diversity between the communities located by the two algorithms demonstrated that the evolutionary algorithm located a very much larger variety of community types. For all three species pools, the communities found in different runs of the serial species addition algorithm shared large common cores of species.

This study continues an investigation into factors that can modify the emergence of cooperation in the iterated Prisoner's Dilemma. It is part of a project to construct agents that play the Prisoner's Dilemma in a manner similar to biological agents; in this study a representation called a binary decision automata is used. Binary decision automata are finite state machines that are given a selection of Boolean inputs that describe features of the game. Each state both specifies one of the variables and generates transitions and actions based on the value of the variable. The software permits the automata to see a subset of the possible decision variables and the decision variables made available have a strong impact on the way agents trained with an evolutionary algorithm behave. A collection of twenty-two game descriptors are used; six are based on recent information about past play, sixteen are features that are based on long-term information about play. The level of cooperation and other measures of behavior all vary strongly with the set of variables made available to the agent. In this study the level of cooperation is assessed at different evolutionary epochs to permit the evaluation of how cooperation emerges over time. It is found that the most importance variable for the emergence of cooperation was the variable that checks whether a player's opponent cooperated last time; an unexpected development is that the most used variable in evolved automata was one that checks to see if the automata is being exploited.

This study is the third in a series developing an agent based ecological model of the workplace focused on the impact of stress. Stress and stress-related health problems are a serious matter but, prior to this series of studies, quantitative modeling of stress has been substantially neglected. This model builds on earlier work, incorporating a more realistic model of the stress relief caused by time off on weekends. The model also examines drug use as something that can be learned spontaneously or learned from a mentor rather than being present in an endemic, fixed fraction of the population, as it was in earlier studies. In this study a parameter exploration is performed on the agent representation, binary decision automata. It is found that the BDA representation is highly adaptive, responding robustly to parameter changes. Parameters investigated include number internal states in agents, accuracy of imitation of mentors, work requirements, and probabilities of learned and spontaneous drug use. Parameter values are taken beyond reasonable ranges to examine the model's failure modes. This study demonstrates that the model behaves in a reasonable fashion, determines its limits, and established a baseline for further investigation.

Agents for playing iterated prisoner's dilemma are commonly trained using a coevolutionary system in which a player's score against a selection of other members of an evolving population forms the fitness function. In this study we examine instead a version of evolutionary iterated prisoner's dilemma in which an agent's fitness is measured as the average score it obtains against a fixed panel of opponents called an examination board. The performance of agents trained using examination boards is compared against agents trained in the usual coevolutionary fashion. This includes assessing the relative competitive ability of players evolved with evolution and coevolution. The difficulty of several experimental boards as optimization problems is compared. A number of new types of strategies are introduced. These include sugar strategies which can be exploited with some difficulty and treasure hunt strategies which have multiple trapping states with different levels of exploitability. The degree to which strategies trained with different examination boards produce different agents is investigated using fingerprints.

This paper examines evolutionary nonlinear projection (NLP), a form of multidimensional scaling (MDS) performed with an evolutionary algorithm. MDS is a family of techniques for producing a low dimensional data set whose points have a one-to-one correspondence with the points of a higher dimensional data set with the added property that distances or dissimilarities in the higher dimensional space are preserved as much as possible in the lower dimensional space. The goal is typically visualization but may also be clustering or other forms of analysis. In this paper, we review current methods of NLP and go on to characterize NLP as an evolutionary computation problem, gaining insight into MDS as an optimization problem. Two different mutation operators, one introduced in this paper, are compared and parameter studies are performed on mutation rate and population size. The new mutation operator is found to be superior. NLP is found to be a problem where small population sizes exhibit superior performance. It is demonstrated experimentally that NLP is a multimodal optimization problem. Two broad classes of projection problems are identified, one of which yields consistent high-quality results and the other of which has many optima, all of low quality. A number of applications of the technique are presented, including projections of feature vectors for polyominos, of vectors that are members of an error correcting code, of behavioral assessments of a collection of agents, and of features derived from DNA sequences.

This study establishes a framework called ∗-Tego for a situation in which two agents are each given a set of players for a competitive game. Each agent places their players in an order. Players on each side at the same position in the order play one another, with the agent's score being the sum of their player's scores. The planning agents are permitted to simultaneous reorder their players in each of several stages. The reordering is termed competitive replanning. The resulting framework is scalable by changing the number of players and the complexity of the replanning process. The framework is demonstrated using iterated prisoner's dilemma on a set of twenty players. The system is first tested with one agent unable to change the order of its players, yielding an optimization problem. The system is then tested in a competitive co-evolution of planning agents. The optimization form of the system makes globally sensible assignments of players. The co-evolutionary version concentrates on matching particular high-payoff pairs of players with the agents repeatedly reversing one another's assignments, with the majority of players with smaller payoffs at risk are largely ignored.

Evidence of large-scale forest mycorrhizal networks that facilitate plant-to-plant nutrient transfer suggests that plants have the ability to distribute and share resources between individuals. An agent-based model that allows plants to interact with soil nutrients and share resources through a network was designed with the goal of providing fundamental insight on cooperation in a stand of plants. Simulation parameters were varied to determine what conditions promote and discourage cooperative behaviours. Cost of life (energy for basal metabolism), initial (seed) energy, and population size were the most important variables affecting cooperation between plants. This model is intended as a preliminary look at plant networks that will be extended to further address the mycorrhiza context specifically. The model, once fully developed, is intended to support modeling of whole environment modeling of systems of plants.

The Fragment Assembly Problem is a major component of the DNA sequencing process that is identified as being NP-Hard. A variety of approaches to this problem have been used, including overlap-layout-consensus, de Bruijn graphs, and greedy graph based algorithms. The overlap-layout-consensus approach is one of the more popular strategies which has been studied on a collection of heuristics and metaheuristics. In this study heuristics and Genetic Algorithm variations are combined to exploit their respective benefits. These algorithms were able to produce results that surpassed the best results obtained by a collection of state-of-the-art metaheuristics on ten of sixteen popular benchmark data sets.

Biclustering is a data mining technique that performs clustering of the rows and columns of a matrix simultaneously. An associator is a numerical measure of how closely associated two objects should be. Ensemble methods integrate information from multiple solutions to generate superior solutions. A simple evolutionary algorithm to quickly locate multiple biclusterings of synthetic test data. The good submatrices of these biclusterings are then used as associators. Associators are accumulated across many runs of the evolutionary algorithm to create a master association matrix. This matrix is then used, via simultaneous hierarchical clustering, to create a final ensemble biclustering. Results are presenting on tuning the evolutionary algorithm as well as for the overall biclustering algorithm. The algorithm correctly locates planted clusters in the data, providing proof of concept for the ensemble technique. The technique is modular with the evolutionary algorithm, fitness function, and ensemble integration technique all easily swapped for other techniques.

Side effect machines are augmented finite state machines with counters on each state. They are used to convert DNA or other string data into numerical features. In this study we examine the effect of imposing shapes on side effect machines. When a standard finite state device is programmed with an evolutionary algorithm there is no restriction placed on the transition function. A shape for a population of evolving finite state machines is a restriction on the possible transitions. We demonstrate that choosing a shape with expert knowledge yields improved performance on a supervised classification task. The shapes used are designed, induced from evolved side effect machines, and designed based on features of evolved side effect machines. The best performance was exhibited by a shape induced from an evolved side effect machine.

Real parameter optimization is one of the most common applications of evolutionary computation. In this study we define a protocol to understand the exploratory and exploitative behaviors of evolutionary algorithms and evaluate two representations on four test functions. The first representation, storing the real parameters in an array, is a standard representation. The second representation, called the walking triangle representation is introduced in this study. This representation is a generative one which models a set of real parameters as the center of mass of a simplex. The generative rules modify the simplex through reflection, scaling, and deformation. It is shown that this representation behaves in a substantially different manner from the standard one and has very different capabilities. On two of the four test problems, one variation of the walking triangle yields an improvement of hundreds orders of magnitude in fitness. This paper suggests that representations themselves are just as important to consider when optimizing evolutionary algorithms for a balance of exploration and exploitation, and further that our system of open-ended test functions can be used to monitor this balance and adjust these considerations accordingly.

Cellular automata are known to be capable of Turing-complete computation and yet “programming” them to do particular tasks can be quite daunting. In this paper we use single parent crossover as a means of transferring information between successive evolving populations to create rules for cellular automata that have proscribed shapes. The proscription of regions where the automata are permitted to grow is the reason they are called bonsai automata. This work follows earlier work on apoptotic cellular automata that simply exhibit self-limited growth. The correct choice of single parents permits enormous improvement in the performance of evolutionary algorithms searching for automata that satisfy particular bonsai templates. In this study, we demonstrate that single parent techniques make meeting shape constraints on the growth of CAs possible at all in some cases. This study also introduces range niche specialization to control problems with the cloning of ancestors used for single parent crossover in an evolving population. This study demonstrates that different bonsai shapes have highly variable difficulty. It is also shown that automata evolved to satisfy one bonsai template may be needed to enable, via single parent crossover, solutions for another template. The use of bonsai techniques yields many automata not found during studies of apoptotic automata demonstrating that the technique encourages exploration of different parts of the fitness landscape.

Quaternary error-correcting codes defined over the edit metric may be used as labels to track the origin of sequence data. When used in such applications there are typically additional restrictions that are biologically motivated, such as a required GC content or the avoidance of certain patterns. As a result such codes can not be expected to have a regular structure, making decoding particularly challenging. Previous work on decoding edit codes considered the use of side effect machines for decoding, successfully decoding up to 93.86% of error vectors. In this study the recentering/restarting algorithm is used in combination with side effect machines and an alternative representation based upon transpositions. Using the same data as in the previous work, the rate of successful decoding was significantly improved, with many cases obtaining rates very close to 100%.

Woven string kernels are a form of evolvable directed acyclic graph specialized to perform DNA classification. They are introduced in this study and tested on simple and complex synthetic data as well as biological data. The WSKs perform marginally on the simplest synthetic data - based on GC content - for which they are not entirely appropriate. They exhibit perfect classification on the more complex synthetic data and on the biological data. Woven string kernels have a number of parameters including their height, the number of initial strings from which they are built, and the amount of “weaving” used to generate the final structure. A parameter study shows that these parameters must be set based on the type of data under analysis. The paper concludes with comments on possible improvements of the woven string kernel technique.

This study builds on previous work modeling stress in the workplace. It incorporates a new and more sophisticated agent representation called a binary decision automata. Agent training uses inaccurate mimetic behaviour to adopt the successful behaviour of highly productive mentors. There are three tasks an agent can undertake; rest, a base job and a special project. The relative worth of these tasks vary stochastically week-to-week representing the changing priorities of management. Stress is accumulated through working long hours and impacts performance of the agent by decreasing productivity. Covert drug use is implemented into the model through the incorporation of a few individuals with much higher stress tolerance than the base agents. Binary decision automata have substantially greater learning capabilities, reflected in the increased productivity and lower overall monthly firings compared to previous research that used a simple string representation for agents. Moreover, with the inclusion of covet drug use amongst agents, the binary decision automata have the capabilities to learn effective behaviour and adapt to the challenging demands of the high performing drug agent mentors. This is in sharp contradistinction to the string agents.

Evolutionary computation research frequently relies on the analysis of the time, and know solutions or measures of the quality of solutions found as metrics for comparing different selection schemes, representations, and operators. While these are important tools, more nuanced tools are helpful even when trying to understand relatively simple evolutionary optimizers, and can be critical when coevolution or multicriteria optimization is being performed. The range of useful tools is broad, including theorems, visualizations, new metrics, and novel analysis techniques. This Special Issue presents six papers that include all of these. The purpose of this Special Issue is to expand our tool set for understanding the behavior of complex evolutionary systems. In the judgement of this writer, it is a good beginning, giving many examples, surveying known techniques, presenting new techniques, and giving many possible next steps. A brief summary of each article is provided.

This paper introduces agent-case embeddings, a general purpose tool for detecting a variety of solutions produced by an evolutionary algorithm. They can also be used to explore the geometry of the space of problems that agents attempt to solve. Agent-case embeddings permit the comparison of solutions evolved with different representations by directly comparing phenotypes. Use of agent-case embeddings requires that multiple instances of the problems solved by the agent be available or contrivable. Three examples of agent-case embeddings are derived for apoptotic cellular automata, agents playing the iterated prisoner's dilemma, and simple virtual robots performing the Tartarus task. The use of agent-case embeddings is shown to permit visualization of the diversity of evolved agents, demonstrates the impact of changing algorithm parameters, and explores the impact of different representations on evolutionary search. The algorithm parameters explored include population sizes, elite fraction, and choice of variation operators. Agent-case embeddings are used to demonstrate that a novel technique called single-parent crossover can localize evolutionary search in a small part of the adaptive landscape in a controlled manner.

This paper examines the fitness landscape for evolutionary algorithms evolving cellular automata (CA) rules to satisfy an apoptotic fitness function. This fitness function requires the automata to grow as rapidly as possible and to die out by a fixed time step. The apoptotic CA yielded rules that are extremely robust to variation, while utilizing the majority of available positions in the updating rule. Robustness is assessed by a novel technique called fertility. In addition, fitness morphs are adapted for use on discrete fitness landscapes to demonstrate the localization of high fitness rules to small portions of the fitness landscape. The fitness landscape is shown to be rugose and to be populated by many optima. Single-parent techniques are used both to improve evolutionary techniques for locating automata rules, and to generalize rules that are evolved for one case of the fitness function to other cases of that fitness function. In addition to introducing the evolution of apoptotic CA as a test problem and evolved art technique, many of the analysis tools presented are unique and applicable beyond their focus in the current study.

In nature, regulatory genes determine which part of an organism's genome is expressed. In this study a simple regulatory mechanism is used to modify linear representations. The regulatory mechanism substantially enhances exploration at the expense of exploitation. For complex, polymodal fitness landscapes the modification yields a substantial improvement in performance. A negative control example demonstrates the technique yields a remarkable degradation in performance on a unimodal optimization problem designed to interact poorly with the technique. Analysis shows that the regulatory mechanism creates the potential for insertion and deletion mutations within the linear representation. These mutations have the effect of substantially increasing the number of genomes one mutation away from any given genome. This has the effect of decreasing the diameter of any search space where they regulatory technique is implemented.

Generalization is a perennial issue in evolutionary computation. The ability of evolution to find excellent special-purpose solutions to a problem means that, in some cases, evolutionary techniques generalize poorly. In this study we demonstrate a system that generalizes apoptotic cellular automata rules from a small evaluation arena to a larger one. The generalization preserves many of the features of the cellular automata while increasing the size of the automata's time-history. The fidelity of the appearance of the generalized rules to their progenitors is high but varies for different progenitors. The generalization is attained by use of single parent techniques. These techniques employ a set of one or more immortal progenitors that are available for crossover but do not otherwise participate in the population. The form of single parent technique used here is novel and the study includes parameter tuning for its use.

Natural selection acts as a culling force that favors highly fit organisms. There are numerous examples ranging from bacteria through humans showing fitness can sometimes improve if individuals cooperate. Yet despite the widespread evidence of cooperation throughout nature, we still do not fully understand how it evolves. Over the past 10-15 years a large number of theoretical (computer) models have been created, analyzed and published to try and get some answers. Unfortunately, little progress has been made despite all of this time and effort. In this paper we review what has been done and explain why the current directions of research in modeling cooperation in populations is unlikely to provide any insight. We make recommendations on the proper path for future research efforts.

Epidemic models often incorporate contact networks along which the disease can be passed. This study follows up on an earlier one which evolved full general contact networks. This study uses an evolvable network representation inspired by the idea of a social fabric. The resulting representation is based on selecting overlapping groups of agents that interact as if they are well mixed. The groups in this representation are intended to represent groups that are, in fact, well mixed such as schools, families, or workplaces. The new representation permits a substantial improvement in the speed with which a contact model can be fit to an epidemic profile. There is a cost in the form of additional model parameters that must be tuned. A parameter setting study is performed for a simple epidemic profile, providing proof of concept for the evolvable social fabric representation. A number of potential improvements and directions for future work are outlined.

Grid plants are a simple artificial organism that models competitive exclusion in annual plants. Simulated plants that grow only from their tip are placed on a toroidal grid. They grow according to genetic plans that are expressed, limited by both energy and other plants. Once a plant has occupied a cell of the grid, no other may, so that the plants are competing for space. The algorithm simulates reproduction for 1000 model years under differing conditions. The final populations of plants are compared using a variety of tools including agent case embeddings, non-linear projection, and hierarchical clustering. It is found the plants adapt strongly to the differing conditions with higher seed mortality rates corresponding to more aggressive seed production. Performance of the plants is visualized in a number of ways and suggestions are made for generalizing and applying the model.

The Mandelbrot set is a famous fractal. It serves as the source of a large number of complex mathematical images. Evolutionary computation can be used to search the Mandelbrot set for interesting views. This study compares the results of using several different fitness functions for this search. Some of the fitness functions give substantial control over the appearance of the resulting views while others simply locate parts of the Mandelbrot set in which there are complicated structures. All of the fitness functions are based on finding desirable patterns in the number of iterations of the basic Mandelbrot formula to diverge on a set of points arranged in a regular grid near the boundary of the set. It is shown that using different fitness functions causes an evolutionary algorithm to locate difference types of views into the Mandelbrot set.

Many studies have evolved agents to play the iterated prisoner's dilemma. This study models a different situation, called the Shopkeeper model of interaction, in which a state conditioned agent interacts with a series of other agents without resetting its internal state. This is intended to simulate the situation in which a shopkeeper interacts with a series of customers. In a majority of other studies agents either reset their internal state information before each new encounter or have relatively little internal state information. This means they cannot model situations such as being the customer that meets the shopkeeper after an obnoxious customer. We train shopkeeper prisoner's dilemma agents against a variety of distributions of possible customers. The shopkeepers specialize their behavior to their customers but sometimes fail to discover maximally exploitative behaviors. The evolved shopkeeper agents are subject to fingerprint analysis and are shown to differ substantially from agents evolved with a round-robin fitness functions. Evaluation of the behavior of the shopkeeper agents with customers they did not encounter during evolution provides additional evidence that shopkeepers specialized to the customers, but did so incompletely for the more complex sets of customers.

This study prototypes a method of evolving autonomous agents that can act as non-player characters (NPCs) in a game. The agents move based on information about their local environment and have evolved weapons, armor, ability to take damage, and movement factors. The creation of the agent is divided into two phases. In the first, a population of competent movement controllers are evolved. In the second, agents start with a competent movement controller and evolve weapons, levels of armor, number of hitpoints, and numbers of movement factors. The movement controller continues to evolve in the second phase. The evolution of the agent's equipment is constrained by a budget together with a price for each type of object the agent can have. The gene specifying the agent's equipment is in the form of a "wish list" of equipment, traversed left-to-right, with the agent buying items from the list as long as its budget suffices. A agent that is a more dangerous opponent can be evolved by giving it a larger budget. A group of experiment are performed that demonstrate that the budget can be used to control an agent's toughness. Additional experiments show that changing the price list for different items can also be used to control the types of agents that evolve. Pitfalls in the selection of the fitness function for the agents are discussed.

Epidemic models often incorporate contact net works along which the disease can be passed. This study uses a recentering-restarting evolutionary algorithm to locate likely epidemic networks for six different epidemic profiles containing early peaks, late peaks, and multiple peaks in the number of infected individuals. This study demonstrates that the algorithm can fit a broad variety of epidemic profiles. The difficulty of finding a network likely to produce a given epidemic profile varies between profiles, but all six profiles are fitted well in at least some of the evolutionary runs. A pseudometric on pairs of networks based on diffusion characters is used to assess the networks distribution in the space of networks. Both the scatter of networks evolved to match a single epidemic profile and the between-profile distances are evaluated. The diffusion character based pseudometric separates the networks for some pairs of profiles neatly while others apparently overlap to some degree.

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.

We present a novel method for the creation of photographic mosaic images using fractals generated via evolutionary techniques. A photomosaic is a rendering of an image performed by placing a grid of smaller images that permit the original image to be visible when viewed from a distance. The problem of selecting the smaller images is a computationally intensive one. In this study we use an evolutionary algorithm to create fractal images on demand to generate tiles of the photomosaic. A number of images and tile resolutions are tested yielding acceptable results.

Search based procedural content generation uses search techniques to locate high-quality content elements for use in games. This study specifies and tests an evolutionary-computation based system to generate tiles and plans that decompose the problem of assembling large levels. Evolutionary computation is used as an off-line tool to generate libraries of both tiles and assembly plans. Systems for rapidly assembling tile libraries can then be used to generate large levels on demand with combinatorially huge numbers of levels available. The study also introduces new fitness functions, generalizing early work on checkpoint based fitness for the evolution of mazes, that is especially well suited for tile creation. Tiles are generated using two different representations that yield tiles with very different appearances. The study demonstrates assemblies of large levels and outlines several directions for extending the work.

In this paper we investigate two types of artificial organism which have the potential to be useful in biological simulations at the genomic level, such as simulations of speciation or gene interaction. Biological problems of this type are usually studied either with simulations using artificial genes that are merely evolving strings with no phenotype, ignoring the possibly crucial contribution of natural selection, or with real biological data involving so much complexity that it is difficult to sort out the important factors. This research provides a middle ground. The artificial organisms are: gridwalkers (GWs), a variation on the self-avoiding walk problem, and plus-one-recall-store (PORS), a simple genetic programming maximum problem implemented with a context free grammar. Both are known to have rugged multimodal fitness landscapes. We define a new variation operator, a kind of aligned crossover for variable length strings, which we call Smith-Waterman crossover. The problems, using Smith-Waterman crossover, size-neutral crossover (a kind of non-aligned crossover defined in), mutation only, and horizontal gene transfer (such as occurs in biology with retroviruses) are explored. We define a measure called fitness preservation to quantify the differences in their fitness landscapes and to provide guidance to researchers in determining which problem/variation operator set is best for their simulation.

This study constructs and tests an agent-based model of bacterial communities with the goal of modeling the observation that the majority of bacteria in nature cannot be cultured. The new field of metagenomics, the direct, mass sequencing of DNA recovered from the environment, is the source of this observation. The hypothesis tested is that bacteria form interdependent communities so that viable levels of energy production are rare in bacteria when they are grown in monoculture. A new game, the metabolism game is introduced. Agents produce energy by playing this game with one another. Studies are run with different number of bacterial species in the simulation. The energy level for viability is set by running simulations with a single bacterial species and then the hypothesis is tested in simulations with multiple bacterial species. Multiple bacterial species are evolved in a novel type of multi-population evolutionary algorithm called a multiple worlds algorithm. The fraction of culturable bacterial agents recovered from the simulation is larger than that found in nature but still quite low, supporting the hypothesis that bacteria may not be culturable because they require the presence of partner species.

Epidemic models often incorporate contact networks along which the disease can be passed. This study incorporates a restarting-recentering evolutionary algorithm, previously developed to locate extremal epidemic networks, together with a new representation, the toggle-delete representation, for evolvable networks. The goal is to locate networks that were likely to have produced a given epidemic behavior. This goal subsumes a new fitness function for driving selection in network evolution. Earlier representations used networks with a fixed sequence of contact numbers. The new representation can add and remove edges from the network, permitting a search that varies contact numbers within the network. A parameter setting study is performed on an epidemic profile obtained from an random network and then tested on a bimodal profile invented by the researchers. The algorithm succeeds in producing networks that cause epidemics run on them to mimic the specified epidemic profiles.

A correctly designed dynamic programming algorithm can be used as a fitness function to permit the evolution of maze-like levels for use in games. This study compares multiple representations for evolvable mazes including direct, as well as positive and negative indirect representations. The first direct representation simply specifies, with a binary gene, which squares of a grid are obstructed. The second paints the maze grid and passage is allowed only between colors that are the same or adjacent in a rainbow. The positive and negative representations are developmental and evolve directions for adding barriers or digging “tunnels.” These representations are tested with a design space of fitness functions that automatically generate levels with controllable properties. Fitness function design is the most difficult part of automatic level generation and this study gives a simple framework for designing fitness functions that permits substantial control over the character of the mazes that evolve. This technique relies on using checkpoints within the maze to characterize the connectivity and path lengths within the level. Called checkpoint-based fitness, these fitness functions are built on a menu of properties that can be rewarded. The choice of which qualities are rewarded, in turn, specifies within broad limits the characteristics of the mazes to be evolved. Three of the representations are found to benefit from a technique called sparse initialization in which a maze starts mostly empty and variation operators fill in details while increasing fitness. Different representations are found to produce mazes with very different appearances, even when the same fitness function is used. The example fitness functions designed around dynamic programming with checkpoints are found to permit substantial control over the properties of the evolved mazes.

Retroviruses are believed to been important in the evolution of genome organization in biological organisms. This study investigates the impact of virtual retroviruses on the genome organization of an artificial organism using the simulation environment developed in. The artificial organisms, grid walkers, were designed to be a model of biological organisms. They have a complex fitness landscape with many local optima connected by neutral networks, a variable-sized self-organized epistatic genome with analogs to biological exons and introns, and a visible phenotype. This study examines the impact of retroviral insertions on genome organization with two different types of crossover. The choice of crossover type is shown to have a large impact. With one type of crossover, retroviral insertions cause the genome to grow rapidly and become fragmented; with the other, they cause it to grow slowly and to have long exons that cover more of the genome. We also tested the impact of changing the source of the retroviruses from a retroviral bank to within the organism's genome. This change also had a different impact on genome organization depending on which type of crossover was used. With one type of crossover, it caused greater fragmentation; with the other it had little effect.

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.

Side effect machines operate by associating side effects with the states of a finite state machine. The use of side effect machines permits the researcher to leverage information stored in the state transition structure, making machines that might be identical as recognizers behave differently as classifiers. The side effect machines in this study associate a counter with each state so that the number of times each state is visited becomes a numerical feature associated with each state. The key to effective use of these numerical feature is to locate side effect machines for which the count vectors are good feature sets. In this study side effect machines are selected with an evolutionary algorithm. The Rand index of nearest neighbor classification of the count vectors serves as the fitness function for selecting side effect machines. A parameter study is performed on simple synthetic data and then side effect machines are trained to classify two sets of biological sequences. The first set comprises two categories of HLA sequences from the human major histocompatibility complex. The second are positive and negative examples of human endogenous retroviral sequences taken from the human genome. The retroviral sequences are challenging but good results are obtained. The HLA data is classified with complete accuracy.

DNA edit metric codes are used as labels to track the origin of sequence data. This study is the first to treat sophisticated decoders for these error-correcting codes. Side effect machines can provide efficient decoding algorithms for such codes. Two methods for automatically producing decoding algorithms are presented. Side Effect Machines (SEMs), generalizations of finite state automata, are used in both. Single Classifier Machines (SCMs) use a single side effect machine to classify all words within a code. Locking Side Effect Machines (LSEMs) use multiple side effect machines to create a tree structured iterated classification. This study examines these techniques and provides new decoders for existing codes. Presented are ideas for best practises for the creation of these two types of new edit metric decoders. Codes of the form (n,M,d)4are used in testing due to their suitability for bioinformatics problems. A group of (12, 54-56, 7)4codes are used as an example of the process.

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.

This is the second study exploring the creation of evolved art through evolutionary control of a dynamical system. Here 1-dimensional cellular automata rules are evolved to exhibit slow but persistent growth or to undergo planned senescence. These simple constraints encourage the automata to develop complex and visually pleasing behavior. Isotropic automata with a forced quiescent state are used, with rules evolved using a simple string representation; the fitness landscapes for both fitness functions are found to be quite rugged with many local optima. This is a desirable feature in an evolved art system as it yields a rich variety of outputs for the artist to use as image elements. A parameter study is performed and it is found that optimization of the slow-growth fitness function favors the use of large populations.

Retroviruses are RNA viruses whose RNA can be transformed into DNA and inserted in the genome of a host cell. This study prototypes a simulation environment in which a simple artificial organism with a variable-size genome evolves with and without retroviruses. The simulated organisms are called grid walkers. They are evolved to efficiently occupy space on a two-dimensional grid. Grid walkers develop a self-organized genome structure with analogs to biological introns and exons. The introduction of retroviruses is found to cause several significant changes: the rate of genome growth is increased, the number of exons is increased, mean exon size is decreased, and fitness is retarded. The grid walkers are found to evolve heritable fitness in preference to high fitness (ldquosurvival of the flattestrdquo), a process that is enhanced when retroviruses are present.

DNA error correcting codes over the edit metric create embeddable markers for sequencing projects that are tolerant of sequencing errors. When a sequence library has multiple sources for its sequences, use of embedded markers permit tracking of sequence origin. Evolutionary algorithms are currently the best known technique for optimizing DNA error correcting codes. In this study we resolve the question of the utility of the crossover operator used in earlier studies on optimizing DNA error correcting codes. The crossover operator in question is found to be substantially counterproductive. A majority of crossover events produce results that violate minimum-distance constraints required for error correction. A new algorithm, a form of modified evolution strategy, is tested and is found to locate codes with record size. The table of best know sizes for DNA-error correcting codes is updated.

This study presents an evolutionary algorithm for locating DNA sequence characters that are diagnostic between closely related groups of species. The algorithm is developed using synthetic data and then tested on biological data from a species of butterfly recently discovered to be a cryptic complex of species. This technique proved to be successful in locating positions that are diagnostic of the cryptic neotropical skipper butterfly species within the cytochrome c oxidase subunit I (COI) DNA barcode data. The algorithm uses a novel subset representation to select positions within the DNA sequences. A crossover operator that takes pairs of subsets to pairs of subsets is designed. This crossover operator permits the use of a novel mutation operator that disrupts loci showing evidence of convergence, yielding better preservation of diversity in the evolving population of diagnostic character positions. A lexical (tie breaking) fitness function is used to smooth the fitness landscape. The problem of locating diagnostic positions in DNA sequences proved difficult without lexical fitness; with that innovation in place the problem is quite tractable. The evolutionary algorithm developed has the potential for broad application such as in conservation, customs enforcement, and forensics.

This study evolves agents to play iterated prisoners dilemma with choice and refusal. The choice and refusal mechanism causes the agents to self-organize social networks. We then apply a novel technique for inducing a pseudometric on the space of networks using diffusion characters to analyze the resulting social networks, and create an exploratory taxonomy of the social networks. The taxonomy agrees well with features visible in rendered drawing of the networks as well as with similarities in the fitness trajectories of the populations that give rise to those networks.

BACKGROUND: Uncovering subtypes of disease from microarray samples has important clinical implications such as survival time and sensitivity of individual patients to specific therapies. Unsupervised clustering methods have been used to classify this type of data. However, most existing methods focus on clusters with compact shapes and do not reflect the geometric complexity of the high dimensional microarray clusters, which limits their performance. RESULTS: We present a cluster-number-based ensemble clustering algorithm, called MULTI-K, for microarray sample classification, which demonstrates remarkable accuracy. The method amalgamates multiple k-means runs by varying the number of clusters and identifies clusters that manifest the most robust co-memberships of elements. In addition to the original algorithm, we newly devised the entropy-plot to control the separation of singletons or small clusters. MULTI-K, unlike the simple k-means or other widely used methods, was able to capture clusters with complex and high-dimensional structures accurately. MULTI-K outperformed other methods including a recently developed ensemble clustering algorithm in tests with five simulated and eight real gene-expression data sets. CONCLUSION: The geometric complexity of clusters should be taken into account for accurate classification of microarray data, and ensemble clustering applied to the number of clusters tackles the problem very well. The C++ code and the data sets tested are available from the authors.

Fingerprinting is a technique that permits automatic classification of strategies for playing a game. In this paper, the evolution of strategies for playing the iterated prisoner's dilemma (IPD) at three different noise levels is analyzed using fingerprinting and other techniques including a novel quantity, evolutionary velocity, derived from fingerprinting. The results are at odds with initial expectations and permit the detection of a critical difference in the evolution of agents with and without noise. Noise during fitness evaluation places a larger fraction of an agent's genome under selective pressure, resulting in substantially more efficient training. In this case, efficiency is the production of superior competitive ability at a lower evolutionary velocity. Prisoner's dilemma playing agents are evolved for 6400 generations, taking samples at eight exponentially spaced epochs. This permits assessment of the change in populations over long evolutionary time. Agents are evaluated for competitive ability between those evolved for different lengths of time and between those evolved using distinct noise levels. The presence of noise during agent training is found to convey a commanding competitive advantage. A novel analysis is done in which a tournament is run with no two agents from the same evolutionary line and one third of agents from each noise level studied. This analysis simulates contributed agent tournaments without any genetic relation between agents. It is found that in early epochs the agents evolved without noise have the best average tournament rank, but that in later epochs they have the worst.

This paper examines the confluence of two lines of research that seek to improve the performance of evolutionary computation systems through management of information flow. The first is hybridization; the second is using small population effects. Hybridization consists of restarting evolutionary algorithms with copies of best-of-population individuals drawn from many populations. Small population effects occur when an evolutionary algorithmpsilas performance, either speed or probability of premature convergence, is improved by use of a very small population. This paper presents a structure for evolutionary computation called a blender which performs hybridization of many small populations. The blender algorithm is tested on the PORS and Tartarus tasks. Substantial and significant effects result from varying the size of the small populations used and from varying the frequency with which hybridization is performed. The major effect results from changing the frequency of hybridization; the impact of population size is more modest. The parameter settings which yield best performance of the blender algorithm are remarkably consistent across all seven sets of experiments performed. Blender performance is found to be superior to other algorithms for six cases of the PORS problem. For Tartarus, blender performs well, but not as well as the previous hybridization experiments that motivated its development.

Tartarus is a standard AI task for grid robots in which boxes must be moved to the walls of a virtual world. There are 320, 320 fitness cases for the standard Tartarus task of which 297, 040 are valid according to the original statement of the problem. This paper studies different schemes for allocating fitness trials for Tartarus using an agent-based metric on the fitness cases to aid in the design process. This agent-based metric is a tool that permits exploration of the geometry of the space of fitness cases. The information gained from this exploration demonstrates why a scheme designed to yield a superior set of training cases in fact yielded an inferior one. The information gained also suggests a new scheme for allocating fitness trials that decreases the number of trials required to achieve a given fitness of the best agent. This scheme achieves similar fitness to a standard evolutionary algorithm using fewer fitness cases. The space of fitness cases for Tartarus is found, relative to the agent-based metric, to form a hollow sphere with a non-uniform distribution of the fitness cases within the space. The tools developed in this study include a generalizable technique for placing an agent-based metric space structure on the fitness cases of any problem that has multiple fitness cases. This metric space structure can be used to better understand the distribution of fitness cases and so design more effective evolutionary algorithms.

Models of epidemic spread often incorporate contact networks along which the epidemic can spread. The character of the network can have a substantial impact on the course of the epidemic. In this study networks are optimized to yield long-lasting epidemics. These networks represent an upper bound on one type of network behavior. The evolutionary algorithm used searches the space of networks with a specified degree sequence, with degrees representing the number of sexual partners of each member of the population. The representation used is a linear chromosome specifying a series of editing moves applied to an initial network. The initial network specifies the degree sequence of the searched networks implicitly and the editing moves preserve the degree sequence. The evolutionary algorithm uses a non-standard type of restart in which the currently best network in the population replaces the initial network. This restart operator is called a recentering operator. The recentering operator moves the evolving population to successively higher fitness portions of the network space. In this study the algorithm is applied to networks with average degree from 2.5 to 7. In low-degree networks, short epidemics result from failure of the disease to spread through the relatively sparse links of the network. In high-degree networks, short epidemics result from the rapid infection of the entire population. The evolutionary algorithm is able to optimize both high and low degree networks to significantly increase the epidemic duration.

Biological ring species are a population surrounding a geographic obstruction such as a large lake or a mountain range. Adjacent sub-populations are mutually fertile, but fertility drops with distance. This study attempts to create examples of artificial ring species using evolutionary algorithms. ISAc lists, a representation with self-organized and potentially complex genetics, are used to evolve controllers for the Tartarus task. The breeding population of Tartarus controllers are arranged in a ring-shaped configuration with strictly local gene flow. Fertility is defined to be the probability that a child will have fitness at least that of its least fit parent. Fertility is found to drop steadily and significantly with distance around the ring in each of twelve replicates of the experiment. Comparison of fertility at various distances within a ring-shaped population is compared with sampled intra-population fertility. Some populations are found to have significantly higher than background fertility with other populations. This phenomena suggests the presence of aggressive genetics or dominant phenotype in which a creature has an enhanced probability of simply cloning its own phenotype during crossover. In addition to creating examples of artificial ring species this study also achieved a very high level of fitness with the Tartarus task. A comparison is made with another study that uses hybridization to achieve record breaking Tartarus fitness.

Biological ring species theoretically develop when an ancestral population expands around a geographic barrier and differentiates until terminal populations come back into contact. Adjacent populations are fertile; fertility declines with distance, and the terminal populations are not fertile. This study uses evolutionary algorithms to attempt to create artificial ring species using grid robots performing the Tartarus task with ISAc lists and string genes solving the Self Avoiding Walk (SAW) problem. Three experiments are done with the Tartarus robots. Fertility is shown to decrease with distance, but not to the extent that ring species are formed. Two experiments are done with SAW. These experiments produce sub-populations which satisfy all the criteria for biological ring species at the point in time when the ring closes. As evolution continues, the relationship between fertility and distance continues, but the terminal populations do not remain infertile. In addition, on both problems, record scores are achieved, suggesting that this model of evolution is a good optimizer for multi-optima problems like Tartarus and SAW which have many deceptive suboptima.

Epidemic models often incorporate contact networks along which the disease can be passed. The connectivity of the network can have a substantial impact on the course of the epidemic. In this study an evolutionary computation system is used to optimizes networks with a fixed distribution of contacts to yield either long-lasting epidemics or epidemics in which a maximal number of individuals are infected in a given time step. These networks represent extremal cases of network behavior. A novel network analysis tool called the diffusion character matrix, derived from the Leontief inverse of a modified adjacency matrix, is used to demonstrate that the networks located for the two optimizations are substantially different. The diffusion character matrix analysis allows us to place several metric-like dissimilarity measure on the space of graphs with a fixed number of nodes. The evolutionary algorithm used searches the space of networks with a specified degree sequence, with degrees representing the number of contacts for each member of the population. The representation used to evolve networks is a linear chromosome specifying a series of degree-preserving editing moves applied to an initial network that specifies the degree sequence of the searched networks. The evolutionary algorithm uses a non-standard type of restart called recentering in which the currently best network in the population replaces the initial network at intervals. The recentering operator moves the evolving population to successively higher fitness regions of the search space. In this study the algorithm is applied to networks with constant degrees from 3 to 7. The diffusion character matrix analysis also demonstrates that the volume of the search space occupied by networks maximizing the number of individuals that fall sick in one time step is much smaller than that occupied by networks that maximize epidemic length.

This paper adopts the definition ldquoan emotion is a scalar summary of complex environmental circumstancesrdquo in the context of the iterated prisonerpsilas dilemma. Prisonerpsilas dilemma players, represented both as look-up tables and artificial neural nets, are evolved with and without emotion and noise. The availability of emotion is found to have a substantial impact on the evolution of cooperation and interacts with noise in a complex manner. The impact of having a single bit of emotional information on lookup tables is also found to be different from the analogous impact on neural nets. The emotion used in this experiment is a single bit which is set if an agentpsilas opponent has defected into cooperation more often than the agent itself has done so. This simple emotion has an substantial, non-uniform impact on the behavior of evolving populations of prisonerpsilas dilemma agents. The emotion implemented in this study is only one of many possible emotions, suggesting that even this limited and mathematically tractable definition of emotion yields a rich collection of possible research topics. The most recognizable impact of adding emotion to agents in this study is to move their behavior away from the middle of the behavioral spectrum toward either sustained cooperation or defection.

Finite state machines are routinely used to efficiently recognize patterns in strings. The internal state structure of the machine is typically only of peripheral interest, appearing in algorithms only when the number of states is minimized in the interests of efficiency of execution or comparison. A side effect machine saves information about the internal transitions of the state machine. This record of internal state transitions forms an induced feature set for any string run through the side effect machine. In this study the number of times a machine passes though each state is used as a numerical feature set for classification. Finite state machines are trained with an evolutionary algorithm to produce feature sets that are very easy for an unsupervised learning algorithm, k-means clustering, to learn. The system is demonstrated on synthetic and biological data. The biological data are PCR-primers classified by their success at amplification. The parameters, number of states, population size, and mutation rates are explored to characterize their effect on performance. Side effect machines are found to be effective at recognizing classes of DNA sequence data.

Fingerprinting is a technique for generating a representation-independent functional signature for a game playing agent. Fingerprints can be used to compare agents across representations in an automatic fashion. The theory of fingerprints is developed for software agents that play the iterated prisoner's dilemma. Examples of the technique for computing fingerprints are given. This paper summarizes past results and introduces the following new results. Fingerprints of prisoner's dilemma strategies that are represented as finite-state machines must be rational functions. An example of a strategy that does not have a finite-state representation and which does not have a rational fingerprint function is given: the majority strategy. It is shown that theAllD- andAllC-based fingerprints can be derived from the tit-for-tat fingerprint by a simple substitution. Fingerprints for four new probe strategies are introduced, generalizing previous work in which tit-for-tat is the sole probe strategy. A trial comparison is made of evolved prisoner's dilemma strategies across three representations: finite-state machines, feedforward neural nets, and lookup tables. Fingerprinting demonstrates that all three representations sample the strategy space in a radically different manner, even though the neural net's and lookup table's parameters are alternate encodings of the same strategy space. This space of strategies is also a subset of those encoded by the finite-state representation. Shortcomings of the fingerprint technique are outlined, with illustrative examples, and possible paths to overcome these shortcomings are given.

Fingerprinting is a technique that permits the identification of strategies for playing a game without doing detailed hand analysis. In this study the evolution of strategies for playing the iterated prisoner's dilemma in the presence of noise was analyzed using fingerprinting and other techniques. Agents were evolved for 6400 generations taking samples at eight exponentially-spaced epochs with noise levels of 0, 1, and 5 percent. Populations were tested for probability of cooperative play, for competitive ability against agents evolved with different noise levels, for competitive ability against agents from other epochs, and for their distribution of strategy types. The ability of agents in noisy environments to cooperate was significantly enhanced over evolutionary time with substantial gains in cooperation made after the 3000 generation. Also, evolution in the presence of noise was found to significantly improve an agent's competitive ability. Agents evolved for a longer time tended to beat agents evolved for a shorter time, though there were some intriguing exceptions. And, populations evolved in the presence of noise had significantly different strategy distributions than populations evolved without noise.

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.

Multi-clustering is a technique for amalgamating the results of many runs of a standard clustering algorithm to obtain a clustering of data which avoid artifacts introduced by the underlying metric. Multi-clustering also yields an advisory, called a cut plot, as to the number of "natural" clusters present in the data. In order to perform multi-clustering a number of parameters must be chosen. This paper tests evolutionary algorithms that perform parameter setting for multi-clustering on synthetic data set with designed numbers of clusters. A evolutionary algorithm and an evolution strategy are compared. The superior algorithm, the ES, is then used to set parameters for four microarray-like data sets. Evolutionary parameter setting is found to more than double the range in which the cut plot detects the correct number of clusters when compared to hand-chosen parameters arrived at by serial parameter optimization. This paper also presents a new technique for accelerating multi-clustering, iteration limiting, and demonstrates that the technique may be implemented to speed up multi-clustering without impairing performance. The evolutionary results support the use of iteration limiting in multi-clustering

The susceptible, infected, removed model for epidemics assumes that the population in which the epidemic takes place is well mixed. This strong assumption can be relaxed by permitting the epidemic to spread only along the links of a contact network or graph. This study uses evolutionary computation to search for graphs that exhibit one of two extreme behaviors: maximum epidemic duration or maximal number of individuals catching the disease. The focus of the paper is on comparison of two representations for evolvable networks. The first makes local expansions of the network specified by a linear chromosome. The second, a permutation-based representation, joins a large cycle with another cycle specified by the permutation. The linear chromosome representation, based on iterated simplexification, yields inferior results in both fitness measures but creates networks with a structure more like a personal contact network. Location of such behaviorally extreme networks will provide a set of test cases for intervention strategies as well as providing conjectures to focus standard mathematical investigation of the types of networks that yield extreme behavior. This study also proposes a testing protocol for network representations for epidemic modeling

The Mandelbrot set is an infinitely complex fractal defined by a simple iterative algorithm operating on the complex numbers. Views of the Mandelbrot set are a common form of fractal art. Presented here is a collection of fitness functions that permit three-parameter evolutionary search of the Mandelbrot set to locate interesting views. While the system presented is automatic, the hand of the artist can direct the type of views found by modifying the fitness function. Based on an envelope that specifies the character of the fractal landscape desired, the fitness function is easily reconfigured with minimal programming skill and without knowledge of complex arithmetic.

Prisoner's dilemma is a simple game used for studying cooperation and conflict. This study evolves Prisoner's dilemma strategies represented by 20-state finite state machines. The resulting strategies are difficult to analyze. It is not obvious looking at a finite state diagram how a machine will behave, and many different machines can represent the same strategy. This study uses a technique called fingerprinting to characterize the strategies. Thirty runs were done for each of three different population sizes for up to 65,536 generations and saved at different stages of evolution. A large diversity of strategies were found. Using different population sizes resulted in finding different strategies and finding common strategies in different proportions. Four strategies were found much more frequently than any others: tit-for-tat, always-defect, and two strategies defined in the study and named Fortress3 and Fortress4. A neighbor-joining technique was used to characterize the fifty most frequently found strategies, and they were found to fall into five distinct groups. The distribution of strategies was found to change over evolutionary time with tit-for-tat and always-defect found more often than other strategies in early evolution, and Fortress3 and Fortress4 becoming important later.

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.

An L-system or Lindenmayer system consists of a grammar together with an interpreter. The grammar contains an axiom string and rules which are expanded into a longer string. The interpreter then renders the string into an object. The first use of L-systems was to provide morphological models of plants. In this study an evolutionary algorithm is used to perform selection on both the L-system grammar and interpreter parameters. The grammar is encoded in a set of real parameters that also includes the interpreter control parameters. This permits the evolutionary algorithm to acts solely as a real parameter optimizer. The interpreter is a graphic turtle with a stack. The evolutionary algorithm co-evolves the grammar and the turtle's control parameters to cause it to place a virtual plant in a constrained area of the Cartesian plane. Compared to previous studies in which the grammar was left fixed, the simultaneous evolution of grammar and interpretation parameters produces a richer selection of virtual plants. The L-system selection algorithm presented here is a potentially valuable tool for digital artists or virtual environment designers.

Non-photorealistic rendering is a broad class of techniques for creating art from digital pictures. One or more digital filters is applied to create an apparent pencil sketch, watercolor, or in this study a design for stained glass. A collection of points that are the centers of weighted Voronoi tilings are evolved to minimize the variance of the variance in luminance within each tile. The average color within each tile is computed. A fractal model of stained glass is then run to create a stained glass texture with a similar average color to that in the tile. Tile boundaries are rendered black, providing the "lead" enclosing the stained glass panes. The stained glass textures are then applied within their corresponding tiles to yield a final image. Evolution of the tile centers is a challenging problem with an expensive fitness evaluation. On the order of 500-3000 real parameters representing the tile centers and their associated weights are optimized. A modified evolution strategy is used to perform this optimization.

This study presents an evolutionary computation system that can generate grid robot path planning problems. An evolvable cellular representation that specifies how to build a PPP is used. Also presented is a technique for taxonomizing path planning problems so that the vast number of problems that can be generated with the evolutionary computation system can be subsequently winnowed into a collection of substantially different problems of specified size. In this study the most difficult path planning problems, according to three different criteria, are evolved and those results are used to demonstrated the taxonomic technique. The hardness criteria are (i) the minimum number of turns a robot must make, (ii) the minimum number of forward moves it must make, and (iii) the sum of these quantities. A dynamic programming algorithm is used to compute these quantities for a given path planning program. The technique can be generalized to find cases of a specified hardness. The size of the board and maximum number of obstacles used are transparently specifiable.

Graph based evolutionary algorithms (GBEAs) have been shown to have superior performance to evolutionary algorithms on a variety of evolutionary computation test problems as well as on some engineering applications. One of the motivations for creating GBEAs was to produce a diversity of solutions with little additional computational cost. This paper tests that feature of GBEAs on three problems: a real-valued multi-modal function of varying dimension, the plus-one-recall-store (PORS) problem, and an applied engineering design problem. For all of the graphs studied the number of different solutions increased as the connectivity of the graph underlying the algorithm decreased. This indicates that the choice of graph can be used to control the diversity of solutions produced. The availability of multiple solutions is an asset in a product realization system, making it possible for an engineer to explore design alternatives.

The temperature profile across an object can be computed by iterative methods. However, the time required for iterative solutions to converge for multiple objects in a complicated configuration impedes the exploratory analysis of engineering systems. A rapidly computed initial guess could greatly increase the speed of convergence for an iterative thermal solver. This study continues research testing various systems for creating thermal agents that provide such initial guesses. During an off-line training process, genetic programming is used to locate a thermal agent by training in several sets of boundary conditions. It is demonstrated here that thermal agents with two boundary temperatures require only one training case. This study examines thermal agents with three-boundary temperatures conditions using different physical geometries. In addition the first appearance of three-dimensional thermal agents appears here.

Recent advancements in digital imaging systems have provided means for greater definition in photography. These technologies have brought high-resolution pictures that show greater clarity and allow for a 'deeper' analysis of information. This occurs through decreased distortion that may have otherwise resulted in features becoming 'blurred' or 'hidden'. However, this strength is accompanied by a weakness due to the large amount of data needed to display the otherwise non-apparent information; in turn creating massive file sizes which produce troubling or infeasible computation times during image storage and transfer. Therefore methods for handling these giant image files could be of great use in image processing and compression if an adequate amount of information can be maintained. During analysis the degree to which information must be replicated exactly depends on the purpose of the final product and the capability of computational resources. This work uses Graph Based Evolutionary Algorithms (GBEAs) to segment images into balanced-weight Voronoi tessellations which are then modeled by least squares surface fitting techniques using the Adaptive Modeling by Evolving Blocks Algorithm (AMoEBA). This twice optimized process yields new techniques of preserving image quality during image analysis and complex decision making. Methods in this paper begin by breaking an image into numerous components using balanced-weight Voronoi tessellations that are optimized to conform to features and detail in an image. These features are represented by surfaces through the strength and efficiency of the AMoEBA algorithm to find optimal representations that can differ from one tessellation to another.

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.

While prisoner's dilemma has frequently been used in studies of animal behavior, past work in the area fails to address the question of differential utility. As animals needs change, their behavior also changes. A hungry animal may be less likely to cooperate than a full one. In this study an abstract species is modelled using an energy balance computation that assigns a state of hungry, full, or neither to a given animal together with a modified finite state representation for a prisoner's dilemma strategy that implements distinct but linked strategies for each possible state. The strategy used is conditioned on the animal's current hunger state. An evolutionary algorithm is used to generate effective strategies for this deterministic form of differential utility prisoner's dilemma. A tool called fingerprinting is used to document the strategies that arise. It is shown that the strategies that arise for the three possible hunger states have different distributions among known strategies and also differ from a baseline experiment in which agents are evolved to play prisoner's dilemma without any form of differential utility

The geographic distribution of species is of interest in making conservation plans, designating biosphere reserves, and in understanding the different range sizes of species. In this paper, an evolutionary algorithm is used to classify species of freshwater crustacean zooplankton as geographically informative or geographically non-informative. Geographically non-informative species tend to have a broad distribution, while geographically informative species exhibit a locality that suggests a greater degree of ecological vulnerability. The data under analysis were mined from the literature from 1930 to 1992 and are in the form of presence/absence data for each species. An evolutionary algorithm is used to maximize the correlation of the geographic distances between ponds with the Hamming distances between ponds computed from the species presence/absence data. Maximization is over the set of species selected for computation of the Hamming distance. The representation used is a binary-gene evolutionary algorithm that selects which species are used. The evolutionary algorithm has highly consistent results between runs. All the runs select the same large group (meaning those species are geographically informative) and fail to select from another large group (meaning those are geographically non-informative); a small number of species are ambiguous, sometimes selected and sometimes not. A second set of experiments in which a large number of short runs are made demonstrates that the fitness landscape of the optimization problem in this study is not a single multi-dimensional hill. Non-trivial interaction between different loci in the representation is found. This study demonstrates that the scheme presented for searching for a purely biologically-based distance that mimics geographic distance is both practical and a non-trivial evolutionary computation problem

Antibiotics have been given to food animals for several decades as a performance enhancer. For nearly as long there has been a concern that using these antimicrobials in production animals could lead to bacteria developing resistance to antibiotics and eventually escaping into the human population. While this risk is still undefined, it would be of benefit to minimize the ratio of resistant bacteria to susceptible bacteria while still maintaining the benefits of administering performance enhancers. In this study we use graph based evolutionary algorithms to find a variety of antibiotic treatment regimens that maintain the weight gain granted by antibiotic use while minimizing the risk from the presence of resistant bacteria. Previous work investigated the effect on Campylobacter.spp only. This study examines different regimens of Tylosin Phosphate use on all bacteria populations, divided into Gram positive and Gram negative types, with a focus on Campylobacter.spp

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

Evolutionary algorithms use crossover to combine information from pairs of solutions and use selection to retain the best solutions. Ideally, crossover takes distinct good features from each of the two structures involved. This process creates a conflict: progress results from crossing over structures with different features, but crossover produces new structures that are like their parents and so reduces the diversity on which it depends. As evolution continues, the algorithm searches a smaller and smaller portion of the search space. Mutation can help maintain diversity but is not a panacea for diversity loss. This paper explores evolutionary algorithms that use combinatorial graphs to limit possible crossover partners. These graphs limit the speed and manner in which information can spread giving competing solutions time to mature. This use of graphs is a computationally inexpensive method of picking a global level of tradeoff between exploration and exploitation. The results of using 26 graphs with a diverse collection of graphical properties are presented. The test problems used are: one-max, the De Jong functions, the Griewangk function in three to seven dimensions, the self-avoiding random walk problem in 9, 12, 16, 20, 25, 30, and 36 dimensions, the plus-one-recall-store (PORS) problem with n=15,16, and 17, location of length-six one-error-correcting DNA barcodes, and solving a simple differential equation semi-symbolically. The choice of combinatorial graph has a significant effect on the time-to-solution. In the cases studied, the optimal choice of graph improved solution time as much as 63-fold with typical impact being in the range of 15% to 100% variation. The graph yielding superior performance is found to be problem dependent. In general, the optimal graph diameter increases and the optimal average degree decreases with the complexity and difficulty of the fitness landscape. The use of diverse graphs as population structures for a collection of problems also permits a classification of the problems. A phylogenetic analysis of the problems using normalized time to solution on each graph groups the numerical problems as a clade together with one-max; self-avoiding walks form a clade with the semisymbolic differential equation solution; and the PORS and DNA barcode problems form a superclade with the numerical problems but are substantially distinct from them. This novel form of analysis has the potential to aid researchers choosing problems for a test suite

The iterated prisoner's dilemma is a widely used computational model of cooperation and conflict. Many studies report emergent cooperation in populations of agents trained to play prisoner's dilemma with an evolutionary algorithm. This study varies the representation of the evolving agents resulting in levels of emergent cooperation ranging from 0% to over 90%. The representations used in this study are directly encoded finite-state machines, cellularly encoded finite-state machines, feedforward neural networks, if-skip-action lists, parse trees storing two types of Boolean functions, lookup tables, Boolean function stacks, and Markov chains. An analytic tool for rapidly identifying agent strategies and comparing across representations called a fingerprint is used to compare the more complex representations. Fingerprints provide functional signatures of an agent's strategy in a manner that is independent of the agent's representation. This study demonstrates conclusively that choice of a representation dominates agent behavior in evolutionary prisoner's dilemma. This in turn suggests that any soft computing system intended to simulate behavior must be concerned with the representation issue.

The most controversial part of genetic programming is its highly disruptive and potentially innovative subtree crossover operator. The clearest problem with the crossover operator is its potential to induce defensive meta-selection for large parse trees, a process usually termed "bloat." Single parent genetic programming is a form of genetic programming in which bloat is reduced by doing subtree crossover with a fixed population of ancestor trees. Analysis of mean tree size growth demonstrates that this fixed and limited set of crossover partners provides implicit, automatic control on tree size in the evolving population, reducing the need for additionally disruptive trimming of large trees. The choice of ancestor trees can also incorporate expert knowledge into the genetic programming system. The system is tested on four problems: plus-one-recall-store (PORS), odd parity, plus-times-half (PTH) and a bioinformatics model fitting problem (NIPs). The effectiveness of the technique varies with the problem and choice of ancestor set. At the extremes, improvements in time to solution in excess of 4700-fold were observed for the PORS problem, and no significant improvements for the PTH problem were observed.

The temperature profile across an object can be computed by iterative methods. The time spent waiting for iterative solutions to converge for multiple objects in a complex configuration is an impediment to exploratory analysis of engineering systems. A high-quality rapidly-computed initial guess can speed convergence for an iterative algorithm. A system is described and tested for creating thermal agents that supply such initial guesses. Thermal agents are specific to an object but general across different thermal boundary conditions. During an off-line training phase, genetic programming is used to locate a thermal agent by training on several sets of boundary conditions. In use, thermal agents transform boundary conditions into rapidly-converged initial values on a cellular decomposition of an object. In this study, the impact of using single parent genetic programming on thermal agents is tested. Single parent genetic programming replaces the usual sub-tree crossover in genetic programming with crossover with members of an unchanging ancestor set. The use of this ancestor set permits the incorporation of expert knowledge into the system as well as permitting the re-use of solutions derived on one object to speed training of thermal agents for another object. For three types of experiments, incorporating expert knowledge; re-using evolved solutions; and transferring knowledge between distinct configurations statistically significant improvements are obtained with single parent techniques.

Steiner systems are statistical designs that permit the comparison of all pairs of objects in a set in groups of three or more. Graph based evolutionary algorithms are a method of improving evolutionary algorithm performance by imposing a geography, in the form of a combinatorial graph, on the evolving population of solutions. The graph limits mate choice and information flow in the population. The choice of combinatorial graph that yields improved performance is highly problem dependent. This paper demonstrates that performance on the problem of locating difference sets that yield Steiner systems can be improved as much as 9-fold by using the graph based technique. For six different cases of the Steiner difference set problem the same graph yields the best result, suggesting that the problem is one for which the choice of best graph remains the same as the problem scales. Performance for the best graph versus that of a standard evolutionary algorithm is tracked beyond the six cases used and verifies that the improved performance scales. The results of these scaling experiments exhibit increasing many-fold improvement.

An L-system or Lindenmayer system consists of a grammar and an interpreter. The grammar contains an axiom, usually a short string, that the grammar expands into a long, complex string. The interpreter then renders the string into an object. A midpoint L-system is a generalization of L-systems to two-dimensional arrays of characters inspired by midpoint displacement fractals. This study presents a system for simultaneously evolving the rules and interpreter for a midpoint L-system that encodes a desired landscape. Unlike a midpoint displacement fractal a midpoint L-system is deterministic and can be evolved to yield fixed, complex shapes. The fractal character of a midpoint L-system permits the storage of a large complex virtual landscape in a small data object. The level of detail rendered by an L-system can be changed rapidly and, with a fast graphics engine, dynamically. This study introduces midpoint L-systems, gives techniques for evolving them, and demonstrates those techniques on trial landscapes that resemble hills and craters. The application of this work is for virtual reality where midpoint L-systems allow a designer to select from many rugged versions of a landscape without requiring vast amounts of storage or machine time to render them.

It is easy to generate strategies for games such as the iterated prisoner's dilemma using evolutionary computation, but much harder to analyze those strategies. Fingerprints are a functional signatures of game playing agents that capture essential features of an agent's strategy while ignoring implementation details. Using functional fingerprints, it is practical to cluster agents and to rapidly identify common agent types in spite of the representational obfuscation often generated by evolutionary training techniques. In this paper, a set of 1080 agents from 30 evolved populations are subjected to analysis using fingerprint based techniques. Filtration is used to remove first well known and then later common strategies. A novel clustering technique, multi-clustering, is then used to cluster the remaining strategies. Filtration and multiclustering, used together, smooth the analysis of evolved agents. Agents playing known strategies are quickly identified and removed from the agent pool, unknown types are clustered into plausible groupings. A previously unsuspected tendency of evolution to prefer finite state strategies composed of a single communicating class is documented.

Non-local adaptation is the acquisition of general skill at a competitive task. General skill is defined as skill against a broad spectrum of opponents rather than just those an agent encountered during its training or evolution. Biological dogma suggests that evolved creatures should be adapted only to their environment and the opponents they encounter during evolution. If this dogma applies to digital evolution, then we should not observe non-local adaptation in agents trained with evolutionary computation to perform some competitive task. A number of previous studies have found non-local adaptation in prisoner's dilemma, in a model of competitive exclusion in plants, and in a virtual robotics task. This paper examines non-local adaptation in a virtual predator-prey system. One hundred distinct predator-prey lineages are evolved for 250,000 time steps, saving an intermediate population at time step 100,000. Predators and prey from distinct lineages are placed in competition. For the four possible comparisons in which the type of one competitor is held constant and the other is varied from less to more evolved, a statistically significant increase in ability to acquire food is seen in the more-evolved agents.

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.

One consideration in evolutionary algorithms is how the information being manipulated is represented. For nearly every problem studied in evolutionary computation, there are several methods which could be employed to solve the problem and the choice can greatly affect the results. There may not only be different ways of encoding a problem, but also several representations of the problem within a single coding scheme. This study examines the Tartarus task, a standard grid robot test problem. Different methods of encoding the problem have been studied, but also of interest is the effects of sensor placement on both runtime and overall fitness of the robot. Learning to process sensors has a computational cost that grows combinatorial with the number of sensors, so a decrease in the number of sensors with no decrease in fitness would be desirable. This study shows that how the environment is represented to the Tartarus agent also has a major impact on the quality of the final solution. The results of the baseline, 8-sensor bulldozer can be surpassed by at least two different sensor configurations, both of which have fewer sensors placed strategically.

Combinatorial graphs have recently been used to control the rate of information spread in evolutionary algorithms, allowing for the preservation of diversity found necessary as the fitness landscape grows in complexity. This paper examines the combined effect of graph type and population size on the transmittal of a solution using graph based evolutionary algorithms. This study identifies a correlation between population size, graph, and time for a good solution to spread. While no numerical relationships are introduced here, it is readily apparent that the required number of mating events for a solution to spread across an entire graph is proportional to the graph diameter, population size, and the fitness difference of the individuals.

The iterated prisoner's dilemma is a widely used computational model of cooperation and conflict. Many studies report emergent cooperation in populations of agents trained to play prisoner's dilemma with an evolutionary algorithm. Cellular representation is the practice of evolving a set of instructions for constructing a desired structure. This paper presents a cellular encoding for finite state automata and specializes it to play the iterated prisoner's dilemma. The impact on the character and behavior of finite state agents that results from using the cellular representation is investigated. For the cellular representation presented a statistically significant drop in the level of cooperation is found. Other differences in the character of the automaton generated with a direct and cellular representation are reported. This paper forms part of an ongoing study of the impact of representation on evolved agents for playing prisoner's dilemma.

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.

Summary: PathBinderH allows users to make queries that retrieve sentences and the abstracts containing them from PubMed. Another aspect of PathBinderH is that users can specify biological taxa in order to limit searches by mentioning either the specified taxa, or their subordinate taxa, in the biological taxonomy. Although the current project requires this function only for plant taxa, the principle is extensible to the entire taxonomy. Availability: www.plantgenomics.iastate.edu/PathBinderH. Source code and databases on request. Contact: [email protected] Supplementary information: A tutorial is at the tool Website. A longer paper is at class.ee.iastate.edu/berleant/s/paperPathBinderHreport.pdf

An Lsystem or Lindenmayer system consists of a grammar and an interpreter. The grammar contains an axiom, usually a short string that the grammar expands into a long, complex string. The interpreter then renders the string into an object. The first use of Lsystems was to provide morphological models of plants. In this exploratory initial study, we use an evolutionary algorithm to evolve interpreters for Lsystems. The interpreter is a graphics turtle. For a given L-system the evolutionary algorithm tunes the turtle's parameter to cause it to drive in a constrained area of the Cartesian plane. Multiple Lsystems and planar regions are given. In some cases a startlingly small number of optima are located indicating a relatively simple fitness landscape.

Taxonomy is the practice of classifying members of a group based on their measurable characteristics. In evolutionary computation the problem of telling when two problems are similar is both challenging and important. An accurate classification technique would yield large benefits by permitting a researcher to rationally choose algorithm and parameter setting based on past experience. A good classification technique would also permit the selection of diverse test suites that would give a useful sense of the proper domain of application of a new technique. This study uses a standard taxonomic technique, hierarchical clustering, on a set of taxonomic characters derived from a comparative study using graph based evolutionary algorithms. The result is a cladogram that classifies the problems used in a reasonable fashion. Based on this we then argue that the technique given here can be used to provide an objective, automatic, extensible classification tool for any collection of evolutionary problems and discuss possible methods for improving the technique.

Evolutionary computation can create a vast number of strategies for playing simple games. Analysis of these strategies is typically more time-consuming than their production. As a result, analysis of strategies produced by an EC system is often lacking or restricted to the extraction of superficial summary statistics. This study presents a technique for extracting a functional signature from evolved agents. This signature can be used as a visualization of agent behavior in games with two moves and also provides a numerical target for clustering and other forms of automatic analysis. The fingerprint can be used to induce a similarity metric on the space of game playing agents. This study develops fingerprints in the context of the iterated prisoner's dilemma but they can be computed for any two player simultaneous game with a finite set of moves.

Evolutionary programming of many systems has been demonstrated in the literature. In This work we use these techniques to program a virtual robot to build a wall out of blocks that impede progress in one direction across a grid of squares. Specifically, two methods for automatic program induction are compared on this task. Virtual blocks are presented one at a time in a fixed location on the grid. The robot must move the currently presented block to enable presentation of the next block as well as using the blocks to build the wall. An evolutionary algorithm operating on strings of actions for the task is used for baseline performance measurement. Evolutionary algorithms operating on GP-Automata and ISAc lists are then applied to the wall building task. In addition to broadening the palette of virtual robotics task, this permits us to compare these two representations for program induction. We study two versions of the wall building problem. The first, in which there are impenetrable walls at the boundary of the virtual world, is much easier than the second method that takes place on a virtual table-top where blocks and the robot may fall off. In addition to the usual randomized initialization, a technique for initializing evolutionary runs with already evolved solutions is presented for the string baseline and both program induction representations.

In this study the nectar-gathering behavior of population of virtual bees is observed during visits to a field of simulated flowers over several hundred generations. The object of the study is to see if floral constancy evolves in the virtual bees. Floral constancy, observed in real bees, is the tendency to harvest nectar from only one type of flower. Flowers can only reproduce if they have received the proper pollen type from a visiting bee and so floral constancy is potentially of substantial importance to flowering plants. The virtual bees are evolved for 250 generations and evaluated for floral specialization. Floral specialization is defined as the average of the maximum visits to one flower type divided by the total number of flower visits. The initial hypothesis was that populations with flowers that had nearly equal amounts of nectar available to the bee would not specialize, but populations with flowers that had a large difference in obtainable nectar would specialize in the flower with more nectar available. Although populations with a choice between nearly equal returns stabilized at non-specialization, the other populations did not behave as expected. Populations that were given one flower with nearly no available nectar (less than 0.1000) and a flower with a larger amount of nectar available specialized in the flower with nectar, but when given a choice between flowers with any procurable amount of nectar greater than 0.1000, the populations eventually stabilized at non-specialization.

Populations of agents are evolved to perform noisy iterated prisoner's dilemma on a toroidal grid. The agents consist of a finite state machine specialized for playing iterated prisoner's dilemma with a simple tag recognition capability. The populations are allowed to evolve for 10,000 generations and the world is stored every 500 generations. Populations from these samples are placed in competition with populations from generation 10,000. This procedure is repeated for varying levels of overall mutation rate, with and without tags, and varying frequencies of tag related mutations. Non-localized adaptation is seen in these populations, however, tags seem to slow the acquisition of non-localized adaptation. Although the concept of non-localized adaptation is not a widely accepted phenomenon in biology, these results suggest that it does happen and that the effect is persistent in the face of changes in mutation rate and in the face of increased task complexity. Also, the study shows patterns of "tag space" usage by populations with tag recognition enabled. The population tends to have a predominant tag most of the time with punctuated periods of increased tag space usage that most likely correspond to invasion of the population by an opportunistic agent with a new tag identifier. This study serves to provide more evidence for and give a more detailed view of non-localized adaptation.

Coevolution is the process of mutual adaptation of two populations. When a difficult optimization is performed with evolutionary computation, a population of adaptive test cases can strongly affect the progress of evolution. This study applies coevolution to the Tartarus task, a grid robot test problem. If the coevolving test cases are viewed as a form of parasite, then the question of virulence becomes an important feature of the algorithm. This study compares different types of parasites for the Tartarus problem. The impact of coevolution in this study is at odds with intuition and statistically significant. Analysis of the different types of coevolution suggests that disruptive crossover has a key effect. In the presence of disruptive crossover, coevolution may need to be modified to be effective. Examples of these modifications are presented. The key method of dealing with disruptive crossover is tracking the age of the Tartarus agents. The age of an agent is defined to be the number of selection steps the agent has survived. Using only older agents to drive coevolution of test cases substantially enhances the performance of one of the two type of coevolution studied.

A difficult application case of evolutionary algorithms is that in which individual fitness evaluations take several processor-minutes to a few processor-hours. The design of evolutionary algorithms with such expensive fitness evaluation differs substantially from the norm where fitness evaluation is rapid. In this paper we apply evolutionary algorithms to a thermal systems engineering design problem - the design of a biomas cook stove currently in use in Central America. Fitness evaluation involves the use of computational fluid dynamics (CFD) modeling of the flow of hot air and heat transport within the stove to equalize the surface temperature. The goal is to optimize the placement and size of baffles that deflect hot gasses underneath the cook top of the stove. Three techniques are used to permit evolutionary algorithm to function on this challenging problem using a population of relatively small size. First, computations are performed on a Linux cluster machine yielding a large, fixed performance increase. Second, the resolution of the mesh for CFD computations used a minimal; mesh that yields acceptable fidelity of CFD computations. Third, a diversity preserving technique called a graph based evolutionary algorithm (GBEA) is used to retain population diversity during evolution. A usable stove design, subsequently deployed in the field, was located by the evolutionary algorithm. In this paper we demonstrate that GBEAs preserve diversity on this baffle design problem and give evidence that highly connected graphs is a good choice for future work on analogous CFD problems. Diversity preservation is a function of both tournament size and the connectivity (geography) of the graph used.

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.

In this paper the concept of quantitative trait loci (QTL) are used with evolutionary optimisation to solve an inverse problem in radiative heat transfer. A QTL is a positron on the genetic map on a chromosome that is associated with a specific trait of the creature. In this implementation a quantitative trait refers to the temperature profile. QTLs are used to combine useful portions of different candidate solutions in the evolutionary technique. This concept is particularly useful in the design of radiant enclosures with low aspect ratio. It is useful in all situations where QTLs can be identified a priori, such as radiative heat transfer. A planned crossover operator has been designed and a representative radiant heat transfer problem has been solved. This multiple fitness evaluation are required for each chromosome. It was found that this method is not only faster, but also much more accurate when compared to the standard method of using a single fitness functions. This paper demonstrates the effectiveness of QTL's in guiding the evolutionary process.

This presents results on training both finite state classifiers and interpolated Markov models as classifiers for polymerase chain reaction primers. The goal of the study is to find techniques to decrease the number of primers that fail to amplify correctly within a large genomics project. Standard primer design packages already select primers in a manner consistent with current knowledge of the biophysics of DNA. The classifiers trained in this effort are used to capture lab and organism specific features of primer data and are used to postprocess the output of standard primer design packages. The finite state classifiers in this study are trained with a novel evolutionary algorithm that uses an incremental fitness reward system and multipopulation hybridization. This hybridization is akin to population seeding, not the more usual hybridization of evolutionary computation with other techniques. The interpolated Markov model is a form of Markov model that adapts to data rich and data sparse portions of the training set by using a variable order in its modeling. The interpolated Markov models exhibited slightly superior performance and trains with far higher speed. The finite state classifiers provide a substantially different classification, however, and require less training data.

UNLABELLED: Because the bulk of the maize (Zea mays L.) genome consists of repetitive sequences, sequencing efforts are being targeted to its 'gene-rich' fraction. Traditional assembly programs are inadequate for this approach because they are optimized for a uniform sampling of the genome and inherently lack the ability to differentiate highly similar paralogs. RESULTS: We report the development of bioinformatics tools for the accurate assembly of the maize genome. This software, which is based on innovative parallel algorithms to ensure scalability, assembled 730,974 genomic survey sequences fragments in 4 h using 64 Pentium III 1.26 GHz processors of a commodity cluster. Algorithmic innovations are used to reduce the number of pairwise alignments significantly without sacrificing quality. Clone pair information was used to estimate the error rate for improved differentiation of polymorphisms versus sequencing errors. The assembly was also used to evaluate the effectiveness of various filtering strategies and thereby provide information that can be used to focus subsequent sequencing efforts.

The field of quantitative morphology has long been important in biological investigations. Various elements of an organism's morphology, such as size and shape, are easily quantified, and standard methods for the analysis of these components exist (i.e., geometric morphometrics). However, methods for reliably quantifying textures and patterns are currently lacking. We propose a technique for quantifying grayscale images of biological textures and patterns. With our method, the textural properties of an image are represented as a foot pattern of 2-dimensional Cartesian coordinates, obtained via an evolutionary algorithm that minimizes the pattern entropy. The pixels of the foot pattern are then assigned labels using one of two techniques: complete enumeration, or by minimizing the differences between sets of landmarks (using a heuristic search for the optimal assignment). The labelled landmark coordinates are then treated as input data for standard quantitative morphometric analysis. With this approach we were able to statistically distinguish between foot patterns generated from two different textual images drawn from the backs of salamanders. Thus, morphological textures and patterns may be quantified, and sets of textures statistically compared.

The temperature profile across an object is easy to compute by iterative methods. The time spent waiting for iterative solutions to converge for multiple objects in a complex configuration is an impediment to exploratory analysis of engineering systems. A rapidly computed initial guess can speed convergence for an iterative thermal solver. We describe and test a system for creating thermal agents that supply such initial guesses. Thermal agents are specific to an object geometry but general across different thermal boundary conditions. During an offline training phase, genetic programming is used to locate a thermal agent by training on one or more sets of boundary conditions. In use, thermal agents transform boundary conditions into a rapidly converged set of initial values on a cellular decomposition of an object.

A population of virtual robots is evolved to perform the task of competitively painting the floor of a toroidal room. Two robots are present in any given room and paint using distinct colors. The fitness of a robot is the amount of floor painted with its own color, a situation where maximal marginal fitness comes from painting over squares already painted in an opponent's color. The time required for a population to settle to a value close to its final average fitness is estimated experimentally at approximately 50 generations. Evolution is then continued well past this estimated settle-down point. The best robots in a given generation are saved at 500 and 5000 generations. The performance of highly evolved and less highly evolved robots is compared by placing the two types of robots into competition. The more evolved robots outperform the less evolved agents, with the empirical estimates of mean fitness differing by more than seven standard deviations. This occurs in spite of a lack of increased fitness of painting robots within their own populations during extended evolution. This result is somewhat at odds with biological dogma, demonstrating general adaptation to the task of painting against opponents never actually encountered. This experiment demonstrates that the quality of the agents as competitive painters is not completely documented by their own in-population fitness numbers. This sort of general adaptation in a competitive task has been observed before in another context, the iterated prisoner's dilemma. This study serves as additional evidence for a form of general adaptation in evolutionary computation systems using an agent-vs-agent competitive fitness function.

We present a method of using a genetic algorithm to evolve controls for a greedy algorithm. We demonstrate the technique on the location of embeddable DNA markers for genetic libraries. The technique has the potential for broad application and other applications are discussed.

We present preliminary results on training finite state machines (FSMs) as good/bad classifiers for polymerase chain reaction (PCR) primers. Novel features of the work presented include hybridization of multiple populations of FSMs and an incremental fitness function. The system presented here is a post-production add-on to a standard primer picking program intended to compensate for organism and lab specific factors.

Many genetic programming systems have been designed to exploit the use of state information in an indirect fashion. In this article we apply a genetic programming technique that directly incorporates state information to a collection of related optical character recognition tasks. Our recognizers are coded as GP-Automata, finite state machines modified by associating a function, stored as a parse tree, with each state. These functions are called deciders and serve to extract information from a high bandwidth input to drive finite state transitions. The GP-Automata make iterated decisions, requesting additional data in an adaptive fashion. This iterated data processing is a form of "crawling through the data" and so we term the software objects data crawlers. These objects can be thought of as expert systems, produced automatically from data by digital evolution. The states for rules with the deciders supplying the "if" part of these rules. We evolve perfect recognizers for three variations of a character set derived from the set of 4-ominoes.

Tartarus is a standard test problem that is used to evaluate evolutionary computation techniques for solving problems in artificial intelligence. A gap in the Tartarus literature is a lack of systematic baseline studies for standard types of chromosomes in broad use in evolutionary computation. In this paper, we adapt plain finite state automata to serve as controllers for virtual robots in the Tartarus environment. We overcome the bandwidth limitations on finite state automata that have prevented their use in Tartarus thus far by permitting a finite state machine to simultaneously generate a Tartarus action and select which of eight sensors will supply its next input. We show by simulation that our finite-state chromosome outperforms published representations without internal state information but is iself outperformed by some chromosomes that use internal state information as part of a more complex structure. A summary of various technologies used thus far for the Tartarus problem and their best results is given.

We report a technique for using an evolutionary algorithm to select the parameters for a data-driven iterated function system. Such iterated function systems are typically driven with uniform random numbers to produce fractals. We instead drive the iterated function system with a biased source mimicking DNA with and without stop codons. An evolutionary algorithm is used to produce fractals that visually display the reading frame DNA. We perform a second set of experiments using the whole genome of mycobacterium tuberculosis in two different reading frames. The fractals located with our evolutionary algorithm correctly separate the DNA into in-frame and out-of-frame for the simulated data and the mycobacterium DNA. The fractals do not give dramatic visual cues to the differences for the mycobacterium data unless points associated with different members of the iterated function system are shaded. Close examination of the fractals yields insight into DNA structure.

In this paper we describe a solution to the problem of synthesizing textures. We use a pair of genetic algorithms to create fast one-pass generating algorithms for five black-and-white textures. This is done using only examples of those textures as input. The key to success is the use of a pair of genetic algorithms and a special structure called a foot pattern. The first genetic algorithm locates a foot pattern, a set of pixel locations containing important structural information about the texture, in essence a point of view from which the example texture looks relatively non-random. The foot pattern is a kind of basic texture element or texel. The second genetic algorithm then uses this texel as the core of a fitness function that compares two textures so as to tell when one "looks like" the other. With this "looks like" fitness function available, the second genetic algorithms synthesizes a non-parametric partially ordered Markov model for the example texture. The genetic algorithms used are themselves quite standard, but their pairing and the fitness functions used yield a breakthrough in black-and-white texture synthesis. Extending these techniques to gray scale and colored textures is possible, but suffers from combinatorial explosion. Suggestions on overcoming the difficulties of such extension appear in the discussion of future work.

Genetic algorithms use crossover to blend pairs of putative solutions to a problem in hopes of creating novel solutions. At its best, crossover takes distinct good features from each of the two structures involved in the crossover. This creates a conflict: progress results from crossing over distinct types of structures but such crossover produces new structures that are like their parents, reducing the diversity on which successful crossover depends. We describe and test genetic algorithms that use a combinatorial graph to limit choice of crossover partner. This gives a computationally cheap method of picking a level of tradeoff between having heterogeneous crossover (crossover between genetically distinct individuals) and preservation of population diversity. Statistics for estimating the degree to which a given graphical population structure favors population diversity or heterogeneous crossover are given. These statistics are computed for ten example graphs. These graphs are then used as population structures for genetic algorithms of three test problems: a trivial string evolver, the plus-one-recall-store (PORS) test suite for genetic programming (D. Ashlock and M. Joenks, 1998; D. Ashlock and J.L. Lathrop, 1998), and simple string controllers for Astro Teller's Tartarus problem (A. Teller, 1994).