Frontiers of Evolutionary Computation

We present 14 challenging problems of evolutionary computation, most of them derived from unfinished research work of outstanding scientists such as Charles Darwin, John von Neumann, Anatol Rapaport, Claude Shannon, and Alan Turing. The problems have one common theme: Can we develop a unifying theory or computational model of organisms (natural and artificial) which combines the properties structure, function, development, and evolution? There exist theories for each property separately as well as for some combinations of two. But the combination of all four properties seems necessary for understanding living organisms or evolving automata. We discuss promising approaches which aim in this research direction. We propose stochastic methods as a foundation for a unifying theory.

The field of evolutionary computation has developed and matured significantly over the past 40 years. As with other disciplines attempting to understand complex adaptive systems, this progress has raised as many new and interesting questions as it has answered. In this chapter I describe some of the key open questions by organizing them in the form of two grand challenges: unification and expansion.

Evolutionary Computation (EC) is now a few decades old. The impressive development of the field since its initial conception has made it one of the most vigorous research areas, specifically from an applied viewpoint. This should not hide the existence of some major gaps in our understanding on these techniques. In this essay we propose a number of challenging tasks that -according to our opinion- should be attacked in order to fill some of these gaps. They mainly refer to the theoretical basis of the paradigm; we believe that an effective cross-fertilization among different areas of Theoretical Computer Science and Artificial Intelligence (such as Parameterized Complexity and Modal Logic) is mandatory for developing a new corpus of knowledge about EC.

The dynamics of evolution can be completely characterized by the spectra of the operators that define the dynamics, under broad classes of selection and genetic operators, in both infinite and finite populations. These classes include frequency-independent selection, uniparental inheritance, and generalized mutation. Several open questions exist regarding these spectra:

Metaheuristics - general search procedures whose principles allow them to escape the trap of local optimality using heuristic designs-have been successfully employed to address a variety of important optimization problems over the past few years. Particular gains have been achieved in obtaining high quality solutions to problems that classical exact methods (which guarantee convergence) have found too complex to handle effectively. Typically a metaheuristic method is crafted to suit the particular characteristics of the problem at hand, exploiting to the extent possible the structure available to enable a fruitful and efficient search process. An alternative to this problem specific solution approach is a more general methodology that recasts a given problem into a common modeling format, permitting solutions to be derived by a common, rather than tailor-made, heuristic method.

The optimization folklore strongly emphasizes the unproductive consequences of converting problems from a specific class to a more general representation, since the “domain-specific structure” of the original setting then becomes invisible and can not be exploited by a method for the more general problem representation. Nevertheless, there is a strong motivation to attempt such a conversion in many applications to avoid the necessity to develop a new method for each new class. We demonstrate the existence of a general problem representation that frequently overcomes the limitation commonly ascribed to such models. Contrary to expectation, when a specially structured problem is translated into this general form, it often does not become much harder to solve, and sometimes becomes even easier to solve provided the right type of solution approach is applied. The model with this appealing property is the Quadratic Unconstrained Integer Programming (QUIP) problem in binary variables, accompanied by the device of introducing quadratic infeasibility penalty functions to handle constraints. Not only is the model capable of representing a wide range of “special case” problem classes, but it can be advantageously exploited by adaptive memory (tabu search) metaheuristics and associated evolutionary (scatter search) methods. Computational outcomes disclose the effectiveness of this combined modeling and solution approach for problems from a diverse collection of challenging settings.

A series of problems and challenges is posed to help guide future work in optimization.

We present a personal overview of EC theory. In particular, we try to show that recent theoretical developments have pointed the way to a grand unification of different branches of EC, such as Genetic Algorithms and Genetic Programming, and also different theoretical models, such as the Vose model and Holland’s Schema theorem. We give a broad outline of this unification program showing how the different elements above are related to each other via changes of representation on the space of EC models. Based on our work we pose a series of challenges which if met, we believe, will lead to a much deeper understanding of EC and the various types of evolutionary algorithm.

We present a self-contained theoretical framework for a scaled genetic algorithm over the alphabet {0,1} which converges asymptotically to global optima as anticipated by Davis and Principe in analogy to the simulated annealing algorithm. The algorithm employs multiple-bit mutation, single-cut-point crossover and power-law scaled proportional fitness selection based upon an arbitrary fitness function. In order to achieve asymptotic convergence to global optima, the mutation and crossover rates have to be annealed to zero in proper fashion, and power-law scaling is used with logarithmic growth in the exponent. Our analysis shows that a large population size allows for a particularly slow annealing schedule for crossover. For the foremost described setting, a detailed listing of theoretical aspects is presented including prerequisites on inhomogeneous Markov chains. In particular, we focus on: (i) The drive towards uniform populations in a genetic algorithm. (ii) Weak and strong ergodicity of the inhomogeneous Markov chain describing the probabilistic model for the scaled algorithm. (iii) Convergence to globally optimal solutions. We discuss various generalizations and extensions of the core framework presented in this exposition such as larger alphabets or other versions of the mutation-crossover operator, in particular, the Vose-Liepins version of mutation-crossover. This refers to recent work by the author in [Theoretical Computer Science 259 (2001), 1–61] and [Technical Report 2002-2-002, Aizu University] where similar types of algorithms are considered over an arbitrary-size alphabet and convergence for arbitrary fitness function under more general conditions is shown. Finally, we present an outlook on further developments of the theory.

Human-competitive results include those equivalent to new scientific results published in peer-reviewed scientific journals, solutions to long-standing or indisputably difficult problems, patented inventions, and results that tie or beat human contestants in regulated competitions. We argue that the pursuit of human-competitive results is not only a worthy goal in itself, but a useful compass for guiding the future growth of the field. We say this for reasons of utility, objectivity, complexity, and interminability. We believe that the continuing generation of evermore important human-competitive results relies on progress in three areas of research: multiobjective optimization, parallel computing, and the development and perfection of competent genetic and evolutionary search methods. Addressing the characteristics of human-competitive problems is one way to expand the theoretical underpinnings of the field of genetic and evolutionary computation.

Case-Based Reasoning (CBR) is the model of human problem solving using prior experiences (calledcases). A case memory is a learning environment where new cases are being injected, existing cases getting purged and yet others adapted to fit situations in response to environmental pressures. As experience accumulates, case memories ideally progress incrementally towards expertise. At present however there is the lack of a framework to understand the nature of this progression and how various factors influence it. In this essay, using the analogy with natural selection, we cast case memories as evolutionary systems to see whether the perspective affords us any insights. We examine case memory processes in the light of their evolutionary role and enquire into the nature of search in evolutionary case memories (ECM). We show that while there are several unresolved questions, the perspective affords us interesting speculations and observations. As an extended application of the ECM perspective we examine whether the evolution of cases can lead to abstract knowledge levels. There is evidence that experiential knowledge may not suffice to achieve higher levels of task expertise but may require abstract knowledge structures such as schema. However, little is currently known about how schema come into existence. We explore the intriguing possibility that schema may evolve from cases as an evolutionary operation. The essay also raises a number of research problems that can be attempted by both CBR and Evolutionary System communities.

In this chapter we discuss the challenge provided by the problem of evolving large amounts of computer code via Genetic Programming. We argue that the problem is analogous to what Nature had to face when moving to multi-cellular life. We propose to look at developmental processes and there mechanisms to come up with solutions for this “challenge of complexity” in Genetic Programming.