Extremum optimization

Extremum optimization

The optimization of the extremes is inspired by the Bak-Sneppen model of self-organized criticality of the co-evolution of the field of statistical physics. The self-organizing criticality model suggests that some dynamic systems have a critical point as an attractor, where the systems exhibit periods of slow motion or accumulation followed by short periods of avalanche or instability. Examples of such systems include land formation, earthquakes, and sand pile dynamics.

The Bak-Sneppen model accounts for these dynamics in coevolutionary systems and in the punctuated equilibrium model, which is described as long periods of state followed by short periods of extinction and large evolutionary changes.

The dynamics of the system are reflected in the constant improvement of a candidate solution with sudden and significant crashes in the quality of the candidate solution. These dynamics allow two main phases of activity in the system: 1) exploit better quality solutions locally, and 2) escape possible local optima with a population crash and explore the search space for a new domain. high quality solutions.

The objective of the information processing strategy is to iteratively identify the worst performing components of a given solution and to replace or swap them with other components. This is achieved by allocating costs to solution components based on their contribution to the overall cost of the solution in the domain. Once the components are evaluated, they can be classified and the weaker components replaced or replaced with a component selected at random.

here is the pseudo code optimization of extremums:

extremum optimization

The deterministic selection of the worst component in the SelectWeakComponent function and the replacement in the SelectReplacementComponent function is a classic EO. If these decisions are probabilistic using the parameter τ, then we speak of τ-Extremal optimization.

Extremum optimization was designed for combinatorial optimization problems, although variations have been applied to continuous optimization of functions. The selection of the worst-case component and of the replacement component at each iteration can be deterministic or probabilistic, the latter being called τ -extremal optimization or extremum-τ optimization given the use of a τ parameter. Selecting an appropriate scoring function of the components of a solution is the most difficult part to apply to the technique. For the τ-Extremal optimization, low τ values (such as τ in [1.2; 1.6]) have been shown to be efficient for the TSP.