Extremal Optimization

Extremal Optimization is inspired by the Bak-Sneppen self-organized criticality model of co-evolution from the field of statistical physics. The self-organized criticality model suggests that some dynamical systems have a critical point as an attractor, whereby the systems exhibit periods of slow movement or accumulation followed by short periods of avalanche or instability. Examples of such systems include land formation, earthquakes, and the dynamics of sand piles. The Bak-Sneppen model considers these dynamics in co-evolutionary systems and in the punctuated equilibrium model, which is described as long periods of status followed by short periods of extinction and large evolutionary change.

The dynamics of the system result in the steady improvement of a candidate solution with sudden and large crashes in the quality of the candidate solution. These dynamics allow two main phases of activity in the system: 1) to exploit higher quality solutions in a local search like manner, and 2) escape possible local optima with a population crash and explore the search space for a new area of high quality solutions.

The objective of the information processing strategy is to iteratively identify the worst performing components of a given solution and replace or swap them with other components. This is achieved through the allocation of cost to the components of the solution based on their contribution to the overall cost of the solution in the problem domain. Once components are assessed they can be ranked and the weaker components replaced or switched with a randomly selected component.

The deterministic selection of the worst component in the SelectWeakComponent function and replacement in the SelectReplacementComponent function is classical EO. If these decisions are probabilistic making use of τ parameter, this is referred to as τ-Extremal Optimization.

Extremal Optimization was designed for combinatorial optimization problems, although variations have been applied to continuous function optimization. The selection of the worst component and the replacement component each iteration can be deterministic or probabilistic, the latter of which is referred to as τ-Extremal Optimization given the use of a τ parameter. The selection of an appropriate scoring function of the components of a solution is the most dicult part in the application of the technique. For τ-Extremal Optimization, low τ values are used (such as τ in [1.2; 1.6]) have been found to be effective for the TSP.