Evolutionary knowledge transfer (EKT) has emerged in the past few years as a new genre of strategy for equipping search and optimization algorithms with prior knowledge. Most EKT research, however, has been dominated by a small number of narrow benchmark functions that do not reflect the diversity of ways problems may be related in different domains. In this paper, we present a preliminary step toward good benchmark design for evolutionary knowledge transfer, by examining four simple benchmark task sets. These cover real-valued, modularly varying goals, and Boolean circuit synthesis domains (where we use Cartesian genetic programming for the latter). We perform experiments with different source-task target pairs drawn from these domains, where we measure the degree to which transfer is successful. Results with a basic population-seeding transfer strategy show that these domain benchmarks illustrate a continuum of difficulty for knowledge reuse, and that a many-source transfer approach that uses population seeding as a form of source selection can dramatically reduce the cost of finding the best knowledge source for a given target task. We anticipate that benchmarks such as these can help the community get a stronger understanding of when and why knowledge transfer is useful, and how problem similarities can best be exnloited.

The field of evolutionary knowledge transfer (EKT) has recently begun to systematically develop algorithms that exploit a number of related problem instances to accelerate problem solving on difficult optimization tasks. EKT has the potential to have a major impact on evolutionary computation practice, comparable to the role that neural network pretraining has had on machine learning. But the community has only scratched the surface of the theoretical hurdles that the knowledge-transfer workflow raises. We introduce a three-part collect-select-exploit framework for understanding EKT, which we use to highlight the need for better evaluation and benchmarking approaches for transfer. We then present some of the first analytical results for EKT, proving no-free-lunch theorems for transfer, and proving what is (to our knowledge) the first asymptotic runtime result for transfer optimization. These results can serve as the basis for future research into the strengths and limitations of knowledge transfer as an optimization paradigm, and they serve to emphasize the need for more comprehensive benchmarks to hone progress in the field.

I have had the privilege of involvement in this field from its early days. The result is a rather unique and comprehensive perspective on its development and growth. In this talk I use that perspective to highlight some important milestones, discuss some current issues and suggest some directions for the future.

We reflect on 30 years of the journal Evolutionary Computation. Taking the papers published in the first volume in 1993 as a springboard, as the founding and current Editors-in-Chief, we comment on the beginnings of the field, evaluate the extent to which the field has both grown and itself evolved, and provide our own perpectives on where the future lies.

Abstract Asynchronous evolutionary algorithms are becoming increasingly popular as a means of making full use of many processors while solving computationally expensive search and optimization problems. These algorithms excel at keeping large clusters fully utilized, but may sometimes inefficiently sample an excess of fast‐evaluating solutions at the expense of higher‐quality, slow‐evaluating ones. We have previously introduced a steady‐state parent selection strategy, SWEET (“Selection whilE EvaluaTing”), that sometimes selects individuals that are still being evaluated and allows them to reproduce early. We perform a takeover‐time analysis that confirms that this strategy gives slow‐evaluating individuals that have higher fitnesses an increased ability to multiply in the population. We also find that SWEET appears effective at improving optimization performance on problems in which solution quality is positively correlated with evaluation time. We evaluate our approach on six simulated real‐valued optimization problems and three real‐world applications: an autonomous vehicle controller problem that involves tuning a spiking neural network and two adversarial EA problems. We further evaluate SWEET versus a basic asynchronous process in a simulated setting. We present evidence that SWEET outperforms basic asynchronous processes in a use‐case in which performance is positively correlated with evaluation time, and performs comparably (and often better) than basic asynchronous processes in several use‐cases where performance is negatively correlated with evaluation time. That said, in the cases where performance and evaluation time are negatively correlated the variance of outcomes for SWEET is notably high.

We have long known that characterizing protein structures structure is key to understanding protein function. Computational approaches have largely addressed a narrow formulation of the problem, seeking to compute one native structure from an amino-acid sequence. Now AlphaFold2 is shown to be able to reveal a high-quality native structure for many proteins. However, researchers over the years have argued for broadening our view to account for the multiplicity of native structures. We now know that many protein molecules switch between different structures to regulate interactions with molecular partners in the cell. Elucidating such structures de novo is exceptionally difficult, as it requires exploration of possibly a very large structure space in search of competing, near-optimal structures. Here we report on a novel stochastic optimization method capable of revealing very different structures for a given protein from knowledge of its amino-acid sequence. The method leverages evolutionary search techniques and adapts its exploration of the search space to balance between exploration and exploitation in the presence of a computational budget. In addition to demonstrating the utility of this method for identifying multiple native structures, we additionally provide a benchmark dataset for researchers to continue work on this problem.

It is our pleasure to introduce this special issue on multitask evolutionary computation (MTEC), focusing on novel methodologies and applications of evolutionary algorithms (EAs) crafted to perform multiple search and optimization tasks jointly. EAs are population-based methods inspired by principles of natural evolution that have provided a gradient-free path to solving complex learning and optimization problems. However, unlike the natural world where evolution has engendered diverse species and produced differently skilled subpopulations,in silicoEAs are typically designed to evolve a set of solutions specialized for just a single target task. This convention of problem solving in isolation tends to curtail the power ofimplicit parallelismof a population. Skills evolved for a given problem instance do not naturally transfer to populations tasked to solve another. Hence, convergence rates remain restrained, even in settings where related tasks with overlapping search spaces, similar optimal solutions, or with other forms of reusable information, are routinely recurring.

In rodent navigational studies, spatial responses have been identified in both the hippocampal subregion CA1 and the subiculum (SUB), but these two brain regions appear to encode spatial features differently. Place fields of SUB place cells are larger and less specific than CA1. Additionally, SUB neurons exhibit stronger directional modulation for heading and axes of travel. Based on neural and behavioral data recorded as rats perform a navigational task on a “triple-T” maze, we present a spiking neural network modeling framework to replicate response properties observed in the CA1 and SUB. The parameters of Spike Timing Dependent Plasticity and homeostatic scaling (STDP-H) were evolved such that the response of the two different SNNs resembled recordings from CA1 and SUB when rats traversed the triple-T maze. Our results suggest that positional input may be more influential in forming CA1 place cells, while the SUB appears to integrate both allocentric positional information and self-motion cues to encode “kinds of places”. Furthermore, our results predict that the different spatial responses in these regions may be due in part to different STDP-H learning parameters. The framework presented here could be used as an automated parameter tuning system for replicating responses in other brain regions.

Algorithmic knowledge transfer can make difficult problems easier to solve well. Most existing work on knowledge transfer for optimization relies on humans to manually select source tasks to transfer information from, and attempts to automate the source selection process are few and far apart. In this work, we survey the existing methods that have been devised for knowledge transfer in evolutionary algorithms, and we present an experimental approach to automated source task selection based on a multi-task implementation of Cartesian genetic programming (MTCGP). Our experiments indicate that this strategy outperforms single-task CGP on solving a set of Boolean function synthesis tasks. We further develop a mutation weighting scheme aimed at protecting useful components from destructive mutation.

The emerging view in molecular biology is that molecules are intrinsically dynamic systems rearranging themselves into different structures to interact with molecules in the cell. Such rearrangements take place on energy landscapes that are vast and multimodal, with minima housing alternative structures. The multiplicity of biologically-active structures is prompting researchers to expand their treatment of classic computational biology problems, such as the template-free protein structure prediction problem (PSP), beyond the quest for the global optimum. In this paper, we revisit subpopulation-oriented EAs as vehicles to switch the objective from classic optimization to landscape mapping. Specifically, we present two EAs, one of which makes use of subpopulation competition to allocate more computational resources to fitter subpopulations, and another of which additionally utilizes a niche preservation technique to maintain stable and diverse subpopulations. Initial assessment on benchmark optimization problems confirms that stabler subpopulations are achieved by the niche-preserving EA. Evaluation on unknown energy landscapes in the context of PSP demonstrates superior mapping performance by both algorithms over a popular Monte Carlo-based method, with the niche-preserving EA achieving superior exploration of lower-energy regions. These results suggest that subpopulation EAs hold much promise for solving important mapping problems in computational structural biology.

Many real-world problems involve massive amounts of data. Under these circumstances learning algorithms often become prohibitively expensive, making scalability a pressing issue to be addressed. A common approach is to perform sampling to reduce the size of the dataset and enable efficient learning. Alternatively, one customizes learning algorithms to achieve scalability. In either case, the key challenge is to obtain algorithmic efficiency without compromising the quality of the results. In this article we discuss a meta-learning algorithm (PSBML) that combines concepts from spatially structured evolutionary algorithms (SSEAs) with concepts from ensemble and boosting methodologies to achieve the desired scalability property. We present both theoretical and empirical analyses which show that PSBML preserves a critical property of boosting, specifically, convergence to a distribution centered around the margin. We then present additional empirical analyses showing that this meta-level algorithm provides a general and effective framework that can be used in combination with a variety of learning classifiers. We perform extensive experiments to investigate the trade-off achieved between scalability and accuracy, and robustness to noise, on both synthetic and real-world data. These empirical results corroborate our theoretical analysis, and demonstrate the potential of PSBML in achieving scalability without sacrificing accuracy.

Stochastic search is often the only viable option to address complex optimization problems. Recently, evolutionary algorithms have been shown to handle challenging continuous optimization problems related to protein structure modeling. Building on recent work in our laboratories, we propose an evolutionary algorithm for efficiently mapping the multi-basin energy landscapes of dynamic proteins that switch between thermodynamically stable or semi-stable structural states to regulate their biological activity in the cell. The proposed algorithm balances computational resources between exploration and exploitation of the nonlinear, multimodal landscapes that characterize multi-state proteins via a novel combination of global and local search to generate a dynamically-updated, information-rich map of a protein's energy landscape. This new mapping-oriented EA is applied to several dynamic proteins and their disease-implicated variants to illustrate its ability to map complex energy landscapes in a computationally feasible manner. We further show that, given the availability of such maps, comparison between the maps of wildtype and variants of a protein allows for the formulation of a structural and thermodynamic basis for the impact of sequence mutations on dysfunction that may prove useful in guiding further wet-laboratory investigations of dysfunction and molecular interventions.

Proteins of importance to human biology can populate significantly different three-dimensional (3d) structures at equilibrium. By doing so, a protein is able to interface with different molecules in the cell and so modulate its function. A structure-by-structure characterization of a protein's transition between two structures is central to elucidate the role of structural dynamics in regulating molecular interactions, understand the impact of sequence mutations on function, and design molecular therapeutics. Much wet- and dry-laboratory research is devoted to characterizing structural transitions. Computational approaches rely on constructing a full or partial, structured representation of the energy landscape that organizes structures by potential energy. The representation readily yields one or more paths that consist of series of structures connecting start and goal structures of interest. In this paper, we propose instead to cast the problem of computing transition paths as a multiobjective optimization one. We identify two desired characteristics of computed paths, energetic cost and structural resolution, and propose a novel evolutionary algorithm (EA) to compute low-cost and highresolution paths. The EA evolves paths representing a specific structural excursion without a priori constructing the energy landscape. Preliminary applications suggest the EA is effective while operating under a reasonable computational budget.

Recent work in computational structural biology focuses on modeling intrinsically dynamic proteins important to human biology and health. The energy landscapes of these proteins are rich in minima that correspond to alternative structures with which a dynamic protein binds to molecular partners in the cell. On such landscapes, evolutionary algorithms that switch their objective from classic optimization to mapping are more informative of protein structure function relationships. While techniques for mapping energy landscapes have been developed in computational chemistry and physics, protein landscapes are more difficult for mapping due to their high dimensionality and multimodality. In this paper, we describe a memetic evolutionary algorithm that is capable of efficiently mapping complex landscapes. In conjunction with a hall of fame mechanism, the algorithm makes use of a novel, lineage- and neighborhood-aware local search procedure or better exploration and mapping of complex landscapes. We evaluate the algorithm on several benchmark problems and demonstrate the superiority of the novel local search mechanism. In addition, we illustrate its effectiveness in mapping the complex multimodal landscape of an intrinsically dynamic protein important to human health.

A number of papers have emerged in the last two years that apply and study asynchronous master-slave evolutionary algorithms based on a steady-state model. These efforts are largely motivated by the observation that, unlike traditional (synchronous) EAs, asynchronous EAs are able to make maximal use of many parallel processors, even when some individuals evaluate more slowly than others. Asynchronous EAs do not behave the same as their synchronous counterparts, however, and as of yet there is very little theory that makes it possible to predict how they will perform on new problems. Of some concern is evidence suggesting that the steady-state versions tend to be biased toward regions of the search space where fitness evaluation is cheaper. This has led some authors to suggest a so-called `quasi-generational' asynchronous EA as an intermediate solution that incurs neither idle time nor significant bias toward fast solutions. We perform experiments with the quasi-generational EA, and show that it does not deliver the promised benefits: it is, in fact, just as biased toward fast solutions as the steady-state approach is, and it tends to converge even more slowly than the traditional, generational EA.

Protein function is the result of a complex yet precise relationship between protein structure and dynamics. The ability of a protein to assume different structural states is key to biomolecular recognition and function modulation. Protein modeling research is driven by the need to complement experimental techniques in obtaining a comprehensive and detailed characterization of protein equilibrium dynamics. This is a non-trivial task, as it requires mapping the structure space (and underlying energy landscape) available to a protein under physiological conditions. Existing algorithms invariably adopt a stochastic optimization approach to explore the non-linear and multimodal protein energy landscapes. At the present, such algorithms suffer from limited sampling, particularly in high-dimensional and non-linear variable spaces rich in local minima. In this paper, we equip a recently published evolutionary algorithm with novel evolutionary search strategies to enhance the sampling capability for mapping multi-basin protein energy landscapes. We investigate initialization strategies to delay premature convergence and techniques to maintain and update on-the-fly a sample-based representation that serves as a map of the energy landscape. Applications on three proteins central to human disease show that the novel strategies are effective at locating basins in complex energy landscapes with a practical computational budget.

In many applications of evolutionary algorithms, the time required to evaluate the fitness of individuals is long and variable. When the variance in individual evaluation times is non-negligible, traditional, synchronous master-slave EAs incur idle time in CPU resources. An asynchronous approach to parallelization of EAs promises to eliminate idle time and thereby to reduce the amount of wall-clock time it takes to solve a problem. However, the behavior of asynchronous evolutionary algorithms is not well understood. In particular, it is not clear exactly how much faster the asynchronous algorithm will tend to run, or whether its evolutionary trajectory may follow a sub-optimal search path that cancels out the promised benefits. This paper presents a preliminary analysis of simple asynchronous EA performance in terms of speed and problem-solving ability.

The focus on important diseases of our time has prompted many experimental labs to resolve and deposit functional structures of disease-causing or disease-participating proteins. At this point, many functional structures of wildtype and disease-involved variants of a protein exist in structural databases. The objective for computational approaches is to employ such information to discover features of the underlying energy landscape on which functional structures reside. Important questions about which subset of structures are most thermodynamically-stable remain unanswered. The challenge is how to transform an essentially discrete problem into one where continuous optimization is suitable and effective. In this paper, we present such a transformation, which allows adapting and applying evolution strategies to explore an underlying continuous variable space and locate the global optimum of a multimodal fitness landscape. The paper presents results on wildtype and mutant sequences of proteins implicated in human disorders, such as cancer and Amyotrophic lateral sclerosis. More generally, the paper offers a methodology for transforming a discrete problem into a continuous optimization one as a way to possibly address outstanding discrete problems in the evolutionary computation community.

A variety of real world applications fit into the broad definition of time series classification. Using traditional machine learning approaches such as treating the time series sequences as high dimensional vectors have faced the well known "curse of dimensionality" problem. Recently, the field of time series classification has seen success by using preprocessing steps that discretize the time series using a Symbolic Aggregate ApproXimation technique (SAX) and using recurring subsequences ("motifs") as features.

The scalability of machine learning (ML) algorithms has become a key issue as the size of training datasets continues to increase. To address this issue in a reasonably general way, a parallel boosting algorithm has been developed that combines concepts from spatially structured evolutionary algorithms (SSEAs) and ML boosting techniques. To get more insight into the algorithm, a proper theoretical and empirical analysis is required. This paper is a first step in that direction. First, it establishes the connection between this algorithm and well known density estimation and mixture model approaches used by the machine learning community. The paper then analyzes the algorithm in terms of varioustheoretical and empirical properties such as convergence to large margins, scalability effects on accuracy and speed, robustness to noise, and connections to support vector machines in terms of instances converged to.

Ab-initio structure prediction refers to the problem of using only knowledge of the sequence of amino acids in a protein molecule to find spatial arrangements, or conformations, of the amino-acid chain capturing the protein in its biologically-active or native state. This problem is a central challenge in computational biology. It can be posed as an optimization problem, but current top ab-initio protocols employ Monte Carlo sampling rather than evolutionary algorithms (EAs) for conformational search. This paper presents a hybrid EA that incorporates successful strategies used in state-of-the-art ab-initio protocols. Comparison to a top Monte-Carlo-based sampling method shows that the domain-specific enhancements make the proposed hybrid EA competitive. A detailed analysis on the role of crossover operators and a novel implementation of homologous 1-point crossover shows that the use of crossover with mutation is more effective than mutation alone in navigating the protein energy surface.

Recently Quantitative Genetics has been successfully employed to understand and improve operators in some Evolutionary Algorithms (EAs) implementations. This theory offers a phenotypic view of an algorithm's behavior at a population level, and suggests new ways of quantifying and measuring concepts such as exploration and exploitation. In this paper, we extend the quantitative genetics approach for use with Genetic Programming (GP), adding it to the set of GP analysis techniques. We use it in combination with some existing diversity and bloat measurement tools to measure, analyze and predict the evolutionary behavior of several GP algorithms. GP specific benchmark problems, such as ant trail and symbolic regression, are used to provide new insight into how various evolutionary forces work in combination to affect the search process. Finally, using the tools, a multivariate phenotypic crossover operator is designed to both improve performance and control bloat on the difficult ant trail problem.

Genetic programming (GP) is not a field noted for the rigor of its benchmarking. Some of its benchmark problems are popular purely through historical contingency, and they can be criticized as too easy or as providing misleading information concerning real-world performance, but they persist largely because of inertia and the lack of good alternatives. Even where the problems themselves are impeccable, comparisons between studies are made more difficult by the lack of standardization. We argue that the definition of standard benchmarks is an essential step in the maturation of the field. We make several contributions towards this goal. We motivate the development of a benchmark suite and define its goals; we survey existing practice; we enumerate many candidate benchmarks; we report progress on reference implementations; and we set out a concrete plan for gathering feedback from the GP community that would, if adopted, lead to a standard set of benchmarks.

Associating functional information with biological sequences remains a challenge for machine learning methods. The performance of these methods often depends on deriving predictive features from the sequences sought to be classified. Feature generation is a difficult problem, as the connection between the sequence features and the sought property is not known a priori. It is often the task of domain experts or exhaustive feature enumeration techniques to generate a few features whose predictive power is then tested in the context of classification. This paper proposes an evolutionary algorithm to effectively explore a large feature space and generate predictive features from sequence data. The effectiveness of the algorithm is demonstrated on an important component of the gene-finding problem, DNA splice site prediction. This application is chosen due to the complexity of the features needed to obtain high classification accuracy and precision. Our results test the effectiveness of the obtained features in the context of classification by Support Vector Machines and show significant improvement in accuracy and precision over state-of-the-art approaches.

Segmentation of satellite images is an important step for the success of the object detection and recognition in image processing. Segmentation is the process of dividing the image into disjoint homogeneous regions. There are many segmentation methods and approaches, the most popular are clustering methods and approaches such as Fuzzy C-Means (FCM) and K means. The success of clustering methods depends strongly on the selection of the initial spectral signatures. Normally, this is done either manually or randomly, in either case the outcome is unpredictable. In this paper an unsupervised method based on Multi-Objective Genetic Algorithm (MOGA) for the selection of spectral signature from satellite images is described. The new method works by maximizing the number of the selected pixels (minimize over-segmentation) and by minimizing the difference between these pixels and their spectral signature (maximize homogeneity). Experimental results are conducted using a high resolution SPOT V satellite image, the collected spectral signatures, and the K-means clustering algorithm. The verification of the segmentation results is based on a very high resolution satellite image of type QuickBird. The spectral signatures provided to K-means by MOGA increased the speed of clustering to approximately 4 times the speed of the random based selection of signatures. At the same time MOGA improved the accuracy of the results of clustering using K-means to more than 10%.

Prediction of promoter regions continues to be a challenging subproblem in mapping out eukaryotic DNA. While this task is key to understanding the regulation of differential transcription, the gene-specific architecture of promoter sequences does not readily lend itself to general strategies. To date, the best approaches are based on Support Vector Machines (SVMs) that employ standard "spectrum" features and achieve promoter region classification accuracies from a low of 84% to a high of 94% depending on the particular species involved. In this paper, we propose a general and powerful methodology that uses Genetic Programming (GP) techniques to generate more complex and more gene-specific features to be used with a standard SVM for promoter region identification. We evaluate our methodology on three data sets from different species and observe consistent classification accuracies in the 94 95% range. In addition, because the GP-generated features are gene-specific, they can be used by biologists to advance their understanding of the architecture of eukaryotic promoter regions.

Support vector machines (SVMs) are now one of the most popular machine learning techniques for solving difficult classification problems. Their effectiveness depends on two critical design decisions: 1) mapping a decision problem into an n-dimensional feature space, and 2) choosing a kernel function that maps the n-dimensional feature space into a higher dimensional and more effective classification space. The choice of kernel functions is generally limited to a small set of well-studied candidates. However, the choice of a feature set is much more open-ended without much design guidance. In fact, many SVMs are designed with standard generic feature space mappings embedded a priori. In this paper we describe a procedure for using an evolutionary algorithm to design more compact non-standard feature mappings that, for a fixed kernel function, significantly improves the classification accuracy of the constructed SVM.

This paper proposes a method to improve the recognition of regulatory genomic sequences. Annotating sequences that regulate gene transcription is an emerging challenge in genomics research. Identifying regulatory sequences promises to reveal underlying reasons for phenotypic differences among cells and for diseases associated with pathologies in protein expression. Computational approaches have been limited by the scarcity of experimentally-known features specific to regulatory sequences. High-throughput experimental technology is finally revealing a wealth of hypersensitive (HS) sequences that are reliable markers of regulatory sequences and currently the focus of classification methods. The contribution of this paper is a novel method that combines evolutionary computation and SVM classification to improve the recognition of HS sequences. Based on experimental evidence that HS regions employ sequence features to interact with enzymes, the method seeks motifs to discriminate between HS and non-HS sequences. An evolutionary algorithm (EA) searches the space of sequences of different lengths to obtain such motifs. Experiments reveal that these motifs improve recognition of HS sequences by more than 10% compared to state-of-the-art classification methods. Analysis of these motifs reveals interesting insight into features employed by regulatory sequences to interact with DNA-binding enzymes.

Bloat is a common problem with Evolutionary Algorithms (EAs) that use variable length representation. By creating unnecessarily large individuals it results in longer EA runtimes and solutions that are difficult to interpret. The causes of bloat are still uncertain, but one theory suggests that it occurs when the phenotype (e.g. behaviors) of the parents are not successfully inherited by their offspring. Noting the similarity to evolvability theory, which measures heritability of fitness, we hypothesize that reproductive operators with high evolvability will be less likely to cause bloat.

Our theoretical understanding of island models (IMs) is much worse than of single-population evolutionary algorithms (EAs). As a consequence there is relatively little guidance available to a practitioner for even the most basic aspects of IM design such as choosing the size and number of the islands. In this paper we improve on this situation by showing how a particular two-level perspective can in fact provide guidance for IM design.

There continues to be a growing interest in the use of coevolutionary algorithms (CoEAs) to solve difficult computational problems. In particular, cooperative CoEAs are often used for optimization by means of problem decomposition. In addition to the parameters of traditional evolutionary algorithms (EAs), CoEAs have a set of coevolution specific parameters whose values can greatly influence performance. In this paper we study the effects on optimization performance of a parameter called update timing, which controls whether the CoEA runs its subcomponents sequentially or in parallel. This has been studied in [T. Jansen and R. P. Wiegand. Sequential versus parallel cooperative coevolutionary (1+1) EAs. In Proceedings of the IEEE International Congress on Evolutionary Computation. IEEE Press, 2003.] for pseudo-boolean functions. By contrast, we perform the analysis for functions defined on continuous real-number domains. We show the performance effects to be dependent on a problem property called best-response curves and use dynamics analysis to explain this dependency.

Cooperative coevolution is often used to solve difficult optimization problems by means of problem decomposition. Its performance on this task is influenced by many design decisions. It would be useful to have some knowledge of the performance effects of these decisions, in order to make the more beneficial ones. In this paper we study the effects on performance of the frequency of interaction between populations. We show them to be problem-dependent and use dynamics analysis to explain this dependency.

The task of designing cognitive tests and challenges for robots and intelligent agents is vital for guidance and evaluation of the development of cognitive architectures aimed at the human level of intelligence. In addressing this task, the tremendous store of knowledge of experimental psychology cannot be ignored. At the same time, methods and test paradigms used for evaluation of humans and/or brain models need to be adjusted before they can be used for evaluation of artifacts. The present work is focused on this problem and its possible solutions in one general paradigm of ontogenesis in virtual environment. We propose several test scenarios and metrics that are adequate to assess cognitive features in computational agents.

Co-evolutionary algorithms (CEAs) have been applied to optimization and machine learning problems with often mediocre results. One of the causes for the unfulfilled expectations is the discrepancy between the external problem solving goal and the internal mechanisms of the algorithm. In this paper, we investigate in a principled way the relationships between the internal subjective metric used as fitness by a co-evolutionary algorithm and the external objective metric measuring the algorithm's progress towards the envisioned goal. We point out the complexity of these relationships and explain their causes.

Several researchers have used Price's equation (from biology theory literature) to analyze the various components of an Evolutionary Algorithm (EA) while it is running, giving insights into the components contributions and interactions. While their results are interesting, they are also limited by the fact that Price's equation was designed to work with the averages of population fitness. The EA practitioner, on the other hand, is typically interested in the best individuals in the population, not the average.In this paper we introduce an approach to using Price's equation which instead calculates the upper tails of population distributions. By applying Price's equation to EAs that use survival selection instead of parent selection, this information is calculated automatically.

Any computational approach to design, including the use of evolutionary algorithms, requires the transformation of the domain-specific knowledge into a formal design representation. This is a difficult and still not completely understood process. Its critical part is the choice of a type of design representation. The paper addresses this important issue by presenting and discussing results of a large number of design experiments in which parameterized and generative representations were used. Particularly, their computational and design related advantages and disadvantages were investigated and compared.Evolutionary design experiments reported in this paper considered two classes of structural design problems, including the design of a wind bracing system and the design of an entire structural system in a tall building. Parameterized and generative representations of the structural systems were introduced and their basic features discussed. The generative representations investigated in the paper were inspired by the processes of morphogenesis occurring in nature. Specifically, one-dimensional cellular automata were used to develop, or 'grow,' structural designs from the corresponding 'design embryos.'.The conducted research led to three major conclusions. First, generative representations based on cellular automata proved to scale well with the size of the considered design problems. Second, generative representations outperformed parameterized representations in minimizing weight of the structural systems in our problem domain by generating better designs and finding them faster. Finally, extensive experimental studies showed significant differences in optimal settings for evolutionary design experiments for the two representation types. The rate of mutation operator, the size of the parent population, and the type of the evolutionary algorithm were identified as the evolutionary parameters having the largest impact on the performance of evolutionary design processes in our problem domain.

Cooperative co-evolution is often used to solve difficult optimization problems by means of problem decomposition. Its performance for such tasks can vary widely from good to disappointing. One of the reasons for this is that attempts to improve co-evolutionary performance using traditional EC analysis techniques often fail to provide the necessary insights into the dynamics of co-evolutionary systems, a key factor affecting performance. In this paper we use two simple fitness landscapes to illustrate the importance of taking a dynamical systems approach to analyzing co-evolutionary algorithms in order to understand them better and to improve their problem solving performance.

A number of recent studies introduced meta-evolutionary strategies and successfully used them for solving problems in genetic programming. While individual results indicate possibilities of successes and failures (e.g., Kantschik, Dittrich et al., 1998, 1999), the emerging global picture suggests that the approach may have universal, domain-independent advantages over traditional methods. Trying to develop a general theoretical understanding of this concept, we use Price's theorem to define fitness at a meta-level and show with two simple case studies (two-dimensional optimization and the Eight puzzle) that the ideology based on Price's theorem can work at a meta-level in a similar manner for very different problems. Specifically, Pricean definition of fitness for reproductive operators appears to be practically useful and essential for performance and stability of a certain class of meta-evolutionary algorithms.

A need for solving more and more complex problems drives the Evolutionary Computation community towards advanced models of Evolutionary Algorithms. One such model is the island model which, although the subject of a variety of studies, still needs additional fundamental research. In this paper we have experimentally studied the influence of various migrations sizes and intervals on island models using a set of special functions. One of the surprising observations from these experiments is that the migration interval seems to be a dominating factor, with migration size generally playing a minor role with regard to the best solution found. Additional experiments measuring genetic diversity show that too frequent migrations cause islands to dominate others and lose global diversity before they are able to exchange solutions to produce better results. Also, we observe that even small migrations already make a significant impact on the behavior of an island model and therefore the effects are comparable to those of bigger migrations. On the other hand rare migrations cause a degraded performance due to the slow convergence. Collectively, these observations provide useful guidance for island model applications.

Evolutionary algorithms (EAs) generally come with a large number of parameters that have to be set before the algorithm can be used. Finding appropriate settings is a difficult task. The influence of these parameters on the efficiency of the search performed by an evolutionary algorithm can be very high. But there is still a lack of theoretically justified guidelines to help the practitioner find good values for these parameters. One such parameter is the offspring population size. Using a simplified but still realistic evolutionary algorithm, a thorough analysis of the effects of the offspring population size is presented. The result is a much better understanding of the role of offspring population size in an EA and suggests a simple way to dynamically adapt this parameter when necessary.

This paper provides the initial results of a study on the application of generative cellular, automata-based representations in evolutionary structural design. First, recent developments in evolutionary design representations and an overview of cellular automata are presented. Next, a complex problem of topological design of steel structural systems in tall buildings is briefly described. Further, morphogenic evolutionary design is introduced and exemplified by cellular automata representations. The paper also reports the initial results of several structural design experiments whose objective was to determine feasibility of the proposed approach. Finally, initial research conclusions are provided.

The term "premature convergence" has been used for many years as an explanation as to why an evolutionary algorithm fails to find a global optimum, without providing much insight into how to fix the problem and/or avoid it in the future. In this paper we tie these issues to notions of (lack of) evolvability that have been explored in the population genetics community for many years. In particular, we show how the central equation in Price's theorem can be extended in such a way as to separate out the individual contributions that reproductive operators make to evolvability, paving the way for better designed EAs in the future.

Cooperative coevolutionary architectures provide a framework for solving complex problems by decomposing them into constituent subproblems, solving the subproblems, and then reintegrating the solutions. This paper presents a blended cooperative coevolution model which offers advantages over traditional evolutionary algorithms and currently-used cooperative coevolutionary architectures.

The task of understanding coevolutionary algorithms is very difficult. These algorithms search landscapes which are, in some sense, adaptive. As a result, the dynamical behaviors of coevolutionary systems can frequently be even more complex than traditional evolutionary algorithms (EAs). Moreover, traditional EA theory tells us little about coevolutionary algorithms. One major question that has yet to be clearly addressed is whether or not coevolutionary algorithms re well-suited for optimization tasks. Although this question is equally applicable to competitive, as well as cooperative approaches, answering the question for cooperative coevolutionary algorithms is perhaps more attainable. Recently, evolutionary game theoretic (EGT) models have begun to be used to help analyze the dynamical behaviors of coevolutionary algorithms. One type of EGT model which is already reasonably well understood are multi-population symmetric games. We believe these games can be used to analytically model cooperative coevolutionary algorithms. This paper introduces our analysis framework, explaining how and why such models may be generated. It includes some examples illustrating specific theoretical and empirical analyses. We demonstrate that using our framework, a better understanding for the degree to which cooperative coevolutionary algorithms can be used for optimization can be achieved.

A novel approach to design robust nonlinear control laws for dynamic systems that are not in canonical form or unknown is introduced. A competitive coevolutionary algorithm is used to design a sliding mode controller based on an approximate model of both the system and uncertainties. The power of evolutionary computation leads to a systematic convergence on accurate nominal model based controllers and the use of competitive coevolution offers a new method to handle model uncertainties with a sliding control structure.

With the emergence of standardized problem generators for dynamic problem environments, we are just starting to systematically measure the performance of different evolutionary-algorithm (EA) extensions against standard classes of problems. We revisit triggered hypermutation, one of the early and most successful implementations of EA's for dynamic environments. Using an implementation of this algorithm, we systematically evaluate the performance of triggered hypermutation on specific test problems across a range of values for the environmental change rate relative to the EA "time" measured in generations. We examine the results, identify a probable cause for the algorithm's behavior, and suggest some improvements to the algorithm.

To successfully apply evolutionary algorithms to the solution of increasingly complex problems, we must develop effective techniques for evolving solutions in the form of interacting coadapted subcomponents. One of the major difficulties is finding computational extensions to our current evolutionary paradigms that will enable such subcomponents to "emerge" rather than being hand designed. In this paper, we describe an architecture for evolving such subcomponents as a collection of cooperating species. Given a simple string-matching task, we show that evolutionary pressure to increase the overall fitness of the ecosystem can provide the needed stimulus for the emergence of an appropriate number of interdependent subcomponents that cover multiple niches, evolve to an appropriate level of generality, and adapt as the number and roles of their fellow subcomponents change over time. We then explore these issues within the context of a more complicated domain through a case study involving the evolution of artificial neural networks.

The paper explores the usefulness of adding the notion of tagging to a standard generational genetic algorithm for addressing issues associated with changing landscapes. Tag bits are used to dynamically evolve subpopulations that act as distinct species, in that mating only occurs between individuals with identical tags. Using Morrison's dynamic landscape generator (R. Morrison and K. De Jong, 1999), the interacting effects of population size and the number of available tag bits are studied. Preliminary results suggest that certain tagged population GAs show significant improvements over standard GAs.

There has recently been a growing interest in the study of EA performance in changing environments. Studies of EAs in dynamic environments, however, have used only a few limited fitness functions. As has been shown in the study of EAs in static environments, comparative studies of the effectiveness of various EAs in dynamic environments will require more rigorous and standardized test functions. These functions should have a simple representation mechanism, so that a wide range of complexity and sophisticated dynamics can be unambiguously described in an elementary manner. The paper proposes an initial test function generator with these characteristics to facilitate further understanding of the effectiveness of different EA implementations in different types of dynamic environments.

We compare the traditional, fixed genetic algorithm (GA) representation scheme with a floating representation scheme and examine the differences in building block dynamics and how these differences affect a GA's ability to balance exploration and exploitation of building blocks. This study examines both the overall performance of a GA and the detailed events that contribute to overall behavior. Results indicate that the floating representation allows a GA to maintain a higher-level of construction which results in a more diverse population from which to build solutions.

The non-linear complexity of evolutionary algorithms (EAs) make them a challenge to understand. The difficulty in performing detailed analyses of an EA is in sorting through the large amount of of data that can be generated in a single run. This paper describes a visualization tool that facilitates navigation through the details of an EA run. The visualization tool organizes and displays EA data at various levels of detail and allows for easy transitions between related pieces of data.

The majority of current genetic algorithms (GAs), while inspired by natural evolutionary systems, are seldom viewed as biologically plausible models. This is not a criticism of GAs, but rather a reflection of choices made regarding the level of abstraction at which biological mechanisms are modeled, and a reflection of the more engineering-oriented goals of the evolutionary computation community. Understanding better and reducing this gap between GAs and genetics has been a central issue in an interdisciplinary project whose goal is to build GA-based computational models of viral evolution. The result is a system called Virtual Virus (VIV). VIV incorporates a number of more biologically plausible mechanisms, including a more flexible genotype-to-phenotype mapping. In VIV the genes are independent of position, and genomes can vary in length and may contain noncoding regions, as well as duplicative or competing genes. Initial computational studies with VIV have already revealed several emergent phenomena of both biological and computational interest. In the absence of any penalty based on genome length, VIV develops individuals with long genomes and also performs more poorly (from a problem-solving viewpoint) than when a length penalty is used. With a fixed linear length penalty, genome length tends to increase dramatically in the early phases of evolution and then decrease to a level based on the mutation rate. The plateau genome length (i.e., the average length of individuals in the final population) generally increases in response to an increase in the base mutation rate. When VIV converges, there tend to be many copies of good alternative genes within the individuals. We observed many instances of switching between active and inactive genes during the entire evolutionary process. These observations support the conclusion that noncoding regions serve as scratch space in which VIV can explore alternative gene values. These results represent a positive step in understanding how GAs might exploit more of the power and flexibility of biological evolution while simultaneously providing better tools for understanding evolving biological systems.

Although more than 30 years old, the field of evolutionary computation has experienced a significant growth of interest and activity in the past few years. This has resulted in fresh perspectives and a flurry of new results in both theory and applica

We address the problem of crafting visual routines for detection tasks. Emphasis is placed on both competition and learning to help with specific visual tasks involved in localization and identification. Crafting of visual routines presents difficult optimization problems and leads to evolutionary computation using a hybrid genetic architecture consisting of natural selection, learning, and their beneficial interactions. Base features representations and visual routines for detection represented as decision trees are evolved. The visual routine considered is that of eye detection. The experimental results reported herein prove the feasibility of our approach in terms of feature selection (data compression) and the corresponding eye detection (pattern recognition).

This paper describes a hybrid methodology that integrates genetic algorithms (GAs) and decision tree learning in order to evolve useful subsets of discriminatory features for recognizing complex visual concepts. A GA is used to search the space of all possible subsets of a large set of candidate discrimination features. Candidate feature subsets are evaluated by using C4.5, a decision tree learning algorithm, to produce a decision tree based on the given features using a limited amount of training data. The classification performance of the resulting decision tree on unseen testing data is used as the fitness of the underlying feature subset. Experimental results are presented to show how increasing the amount of learning significantly improves feature set evolution for difficult visual recognition problems involving satellite and facial image data. In addition, we also report on the extent to which other more subtle aspects of the Baldwin effect are exhibited by the system.

Describes the design of a toolkit for implementing evolutionary algorithms which use a simplified model of natural evolution as their core problem-solving technique. Our goal is to identify high-level concepts required to describe a wide range of such algorithms and implement these concepts as an extensible collection of interoperable components. This collection will allow both researchers and practitioners to rapidly create a wide variety of task-specific evolutionary algorithms. Instead of directly coding these algorithms in a programming language, toolkit users can define them by assembling a graph, whose nodes are selected from a pre-defined set of transformations. By using object-oriented techniques, we allow for easy customization or definition of new toolkit components.

This paper describes an approach being explored to improve the usefulness of machine learning techniques to classify complex, real world data. The approach involves the use of genetic algorithms as a "front end" to a traditional tree induction system (ID3) in order to find the best feature set to be used by the induction system. This approach has been implemented and tested on difficult texture classification problems. The results are encouraging and indicate significant advantages of the presented approach.

Selecting a set of features which is optimal for a given task is a problem which plays an important role in wide variety of contexts including pattern recognition, adaptive control and machine learning. Experience with traditional feature selection algorithms in the domain of machine learning leads to an appreciation for their computational efficiency and a concern for their brittleness. The authors describe an alternative approach to feature selection which uses genetic algorithms as the primary search component. Results are presented which suggested that genetic algorithms can be used to increase the robustness of feature selection algorithms without a significant decrease in compuational efficiency.

The findings of a workshop, the goals of which were to identify applications, research problems, and designs of high performance computing and communications (HPCC) systems for supporting applications are discussed. In computer vision, the main scientific issues are machine learning, surface reconstruction, inverse optics and integration, model acquisition, and perception and action. In speech and natural language processing (SNLP), issues were identified statistical analysis in corpus-based speech and language understanding, search strategies for language analysis, auditory and vocal-tract modeling, integration of multiple levels of speech and language analyses, and connectionist systems. In AI, important issues that need immediate attention include the development of efficient machine learning and heuristic search methods that can adapt to different architectural configurations, and the design and construction of scalable and verifiable knowledge bases, active memories, and artificial neural networks.>

An approach being explored to improve the usefulness of machine learning techniques for generating classification rules for complex, real-world data is described. The approach involves the use of genetic algorithms as a front end to a traditional rule induction system in order to identify and select the best subset of features to be used by the rule induction system. This approach has been implemented and tested on difficult texture classification problems. The results are encouraging and indicate that there are significant advantages to the approach in this domain.>

The results of a survey of individuals working in the systems programming and operating systems areas are presented in an attempt to characterize the academic/industry "gap" in this area.The implications of this gap are then presented for both the present curriculum in the Department of Computer Science at the University of Pittsburgh and for college/university curricula in general.