ALPS

ALPS - the Age-Layered Population Structure

The Age-Layered Population Structure (ALPS) paradigm is a novel metaheuristic for overcoming premature convergence by running multiple instances of a search algorithm simultaneously.

In the field of optimization algorithms, one type of algorithmic improvement is that of increasing the speed at which problems of solvable difficulty can be solved. This is shown in papers in which the comparison is on which algorithm can find the global optima of a benchmark problem in the fewest number of evaluations. Another type of algorithmic improvement is increasing the robustness of the algorithm. That is, either increasing the reliability of finding the global optima or being able to find better results then other algorithms.

A typical approach to addressing premature convergence is to restart the search algorithm, but one challenge is in deciding when the population is truly stuck. Another problem is that all the information learned from one run is not passed to the next run. An alternative to restarting the entire search algorithm is to run multiple EAs simultaneously and only restart one of them, and this is what is done with ALPS.

The Age-Layered Population Structure (ALPS) paradigm is a novel metaheuristic for overcoming premature convergence by running multiple instances of a search algorithm simultaneously. A novel measure of age is used to segregate individuals into different age-layers and then, at regular intervals, the youngest layer is replaced with randomly generated individuals.

ALPS was developed to be a way to make other search algorithms more robust, especially on hard problems, but at the cost of potentially slowing them down on easier problems. Below is an overview of the key points of ALPS (measuring age and how the age-layers work), for more details refer to the publications.

ALPS Overview

With ALPS, several instances of a search algorithm are run in parallel, each in its own age-layer, and the age of solutions is kept track of. The key properties of ALPS are:

Age: is a measure of how long an individual's family of genotypic material has been in the population. Randomly generated individuals, such as those that are created when the search algorithm are started, start with an age of 1. Each generation that an individual stays in the population (such as through elitism) its age is increased by one. Individuals that are created through mutation or recombination take the age of their oldest parent and add one to it. This differs from conventional measures of age, in which individuals created through applying some type of variation to an existing individual (eg mutation or recombination) start with an age of 1.

Age-Layers: With the ALPS paradigm, multiple searches are run in parallel, each in their own age layer. The search algorithm in a given layer acts somewhat independently of the others, with an exception being that it can use individuals from both its layer and the layer below to generated new candidate solutions. Also, each age layer has an upper limit on the age of solutions it can contain. When an individual is too old for its current layer, it cannot be used to generate new individuals for that layer and eventually is removed from that layer. Optionally, an attempt can be made to move this individual up to the next layer -- in which case it replaces some individual there that it is better than. Finally, at regular intervals the bottom layer is replaced with a new sub-population of randomly generated individuals, each with an age of 1.

ALPS Performance

To intuitively understand the behavior difference betweeen ALPS and other search algorithms here are some animations of combining ALPS with a standard Evolutionary Algorithm (EA). The first animation shows a basic EA, with a large population, in which each individual is a blue cube. In the second animation an automated restarting mechanism is added, and individuals change color from blue to red as they get older and then go back to blue when the search is restarted. The third animation is of an ALPS run, and shows a mix of individuals of different ages.

Basic EA

An EA with Restarts

ALPS-EA

On this problem, only the ALPS-EA found the global optimum.

To demonstrate how well ALPS works, we compare it against the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) and Differential Evolution (DE). For our test problems we use some hard benchmark problems that are fairly standard in the literature (and for which the source code is located online) and these are rotated versions of the Rana, F101, Rosenbrock, F8F2 and Griewangk functions. While CMA-ES and DE outperform ALPS on the unimodal test functions (rotated Griewangk and rotated Rosenbrock), ALPS is much better on multimodal test problems (rotated F101, rotated Rana and rotated F8F2) and on a real-world problem. We show the results of the three multi-modal problems below.

Rotated Rana

Rotated F101

Rotated F8F2

ALPS Source Code

I have written an implementation of ALPS in C++ that compiles on Ubuntu Linux and it should compile fine on other modern unix systems. The ALPS source code is available on GitHub at: https://github.com/ghornby/alps.

For those interested in reproducing my tests, here are links to:

ALPS FAQ

For those implementing their own version of ALPS, here's a FAQ on some implementation details. If you still have a question that's not answered here, please send me an email.

ALPS Publications

Bongard, J. C. and Hornby, G. S. (2010) "Guarding Against Premature Convergence while Accelerating Evolutionary Search", Proc. of the Genetic and Evolutionary Computation Conference, ACM Press.

Hornby, G. S. (2009) "Steady-State ALPS for Real-Valued Problems", Proc. of the Genetic and Evolutionary Computation Conference, ACM Press.

Hornby, G. S. (2009) "A Steady-State Version of the Age-Layered Population Structure EA" , Genetic Programming Theory & Practice VII.

Hornby, G. S. (2006) "ALPS: The Age-Layered Population Structure for Reducing the Problem of Premature Convergence", Proc. of the Genetic and Evolutionary Computation Conference, ACM Press.