idesign lab

ALPS

• Projects
• People
• Publications

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:

• Multiple instances of a search algorithm are run in parallel, with each instance in its own age layer and having its own population of one or more candidate solutions (individuals).
• Each age-layer has a maximum age and it may not contain individuals older than that maximum age.
• The age of individuals is based on when the original genetic material was created from random.
• The search algorithm in a given age-layer can look at individuals in its own population and at the populations in younger age layers but it can only replace individuals in its own population.
• At regular intervals, the search algorithm in the first age-layer is restarted.

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.

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.

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. Source code is available here.

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

• The test functions.
• Source code for the Covariance Matrix Adaptation Evolution Strategy (CMA-ES).
• Source code for the Differential Evolution (DE) EA.

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.

• What do you do when an individual in one layer is moved up to the next layer?
  When an individual, A, is being moved up to a layer, Li, then what is done is a check to see if there are any individuals in Li that A can replace. A is only inserted into layer Li if there is an individual in Li that has worse fitness than A or if there is an individual in Li that is too old to be in Li. When I replace an individual (let's call this individual B), then I try to move B up to the next layer (let's call this Li+1).
• Do you always try to move up individuals that are kicked out of their present layer?
  I used to always try to move up an individual. Recently, I've tried only moving up only the best individuals -- that is, those individuals that are in the top n (for whatever your elitism size is) when they become too old for their current layer. I find that sometimes this works better.
• What do you do with individuals that are too old for the last layer?
  The last layer does not have a maximum age value and individuals are never too old to be in it.
  One thing that I have thought of trying is having a dynamic population size by adding layers as individuals become too old for the last layer.

ALPS Publications