What should we learn from... Evolutionary Computing

In this series, we introduce topics outside of the signal processing world from which we believe signal processing researchers and practitioners can benefit. This month, we report on a special issue on "Theoretical Foundations of Evolutionary Computation" published  by the IEEE Transactions on Evolutionary Computation.

Evolutionary Computing is the collective name for a range of problem-solving techniques based on principles of biological evolution, such as natural selection and genetic inheritance. These techniques are being increasingly widely applied to a variety of problems, ranging from practical applications in industry and commerce to leading-edge scientific research. Real-world problems, in particular, are difficult to solve using traditional search methods because often they are nonlinear, highly constrained, multiobjective, and can include a number of uncertainties [2].

This picture shows an example of group selection in the group territoriality model. The colored areas show group territories with different genetic compositions [1]

Many different evolutionary computation methods for dealing with complex problems have been proposed over the years. The theoretical analysis of evolutionary computation has made immense progress during the last 10 years. Such analysis provides useful insights into the working principles of evolutionary computation techniques. This insight not only leads to a better understanding of the type of problems suitable for a given type of algorithm, but it also provides design guidelines for developing new more powerful methods in practice.

Previous theoretical studies have shown the runtime behavior of bio-inspired computation methods including evolutionary algorithms, ant colony optimization, and particle swarm optimization. These studies explain, in a strict mathematical way, how these algorithms behave on different problem classes.

The Special Issue on "Theoretical Foundations of Evolutionary Computation" from the IEEE Transactions on Evolutionary Computation published in Oct. 2014 highlights recent advances in the theory of evolutionary computation. The selected four papers illustrate different aspects of theoretical work being conducted in the evolutionary computation field. Each paper describes both mathematical investigations and experimental studies.

The first paper by Mills et al. “Transforming Evolutionary Search into Higher-Level Evolutionary Search by Capturing Problem Structure” provides insight into the working principles of an approach called multiscale search. A particularly remarkable result is that the multiscale approach provably solves a known test problem in polynomial time for which all previous analyses of other evolutionary approaches showed a super-polynomial time.

Hyper-volume based evolutionary algorithms have received increasing attention in multiobjective optimization and are the focus of the second paper by Bringmann and Friedrich, “Convergence of Hypervolume-Based Archiving Algorithms” A central component of such algorithms, which ultimately determines their potential and limitations, is the archiving mechanism. The study is a fundamental contribution to the theory of hypervolume-based multiobjective evolutionary algorithms.

In the third paper, “Asymptotic Properties of a Generalized Cross-Entropy Optimization Algorithm” by Wu and Kolonko repeatedly sample solutions from a probability distribution and use the information gained from these samples to adapt the probability distribution. These results are significant because they not only advance the understanding of cross entropy methods, but also contribute to the understanding of related methods such as estimation of distribution algorithms and ant colony optimization.

In immune-inspired optimization, the use of hypermutations is well established. The fourth paper by Jansen and Zarges, entitled “Reevaluating Immune-Inspired Hypermutations using the Fixed Budget Perspective” shows how hypermutations can greatly reduce the time needed to find a near-optimal solution and demonstrates how to apply this insight in practice. The solution involves applying the immune-inspired algorithm in the traditional way, with hypermutations, but only up to a certain point after which hypermutations should be suppressed.

The four papers in this special issue provide only a subset of the active theoretical research ongoing in the evolutionary computation field today. It is hoped these papers will inspire more readers to enter this dynamic and exciting area of research [3].

References

[1] http://www.agner.org/evolution/groupsel/

[2] A. Eiben, J. Smith. Introduction to Evolutionary Computing. Springer. 2007

[3] Frank Neumann, Benjamin Doerr, Per Kristian Lehre, Pauline C. Haddow. Editorial for the Special Issue on Theoretical Foundations of Evolutionary Computation. IEEE Transactions on Evolutionary Computation. 2014, 18(5), pp. 625-627