AI Glossary / AI and machine learning / Advanced

Extremal optimization

Definition

Extremal optimization is a heuristic search method that preferentially changes poorly performing components of a candidate solution. Instead of selecting only moves that immediately improve the whole solution, it uses local fitness information to drive exploration and retains the best solution encountered.

What it means

Some difficult optimization problems contain many interacting parts. A graph partition assigns nodes to groups; a schedule assigns tasks to slots. Assessing which parts currently contribute poorly can suggest where to make changes.

The word extremal refers to attention toward the worse end of a fitness ranking. It does not mean that the method guarantees an extreme or globally optimal answer. The original approach is associated with Stefan Boettcher and Allon Percus and is different from a conventional population-based genetic algorithm.

How it works

The implementation defines local fitness for components, ranks them and chooses components to modify. In a common variant, tau-extremal optimization, rank-based probabilities favor poorly performing components while sometimes selecting others. After a change, affected fitness values are recomputed.

The current solution can become worse temporarily, allowing movement through difficult landscapes. The best-so-far record protects useful discoveries from being lost as the search continues. Defining local fitness and legal moves is problem-specific: a component that looks weak in isolation can have important interactions with the rest of the solution.

Three practical examples

1. A graph-partitioning experiment can target nodes with poor local placement while maintaining required partition sizes.

2. A combinatorial-optimization class can study graph coloring by measuring how individual assignments contribute to conflicts.

3. An operations-research team can investigate a suitable local-fitness formulation for a scheduling problem and compare it with existing search methods. This third example requires a custom design; the name alone does not supply a ready-made scheduler.

Think of it this way

Imagine revising a complicated seating arrangement by focusing on the most troublesome placements. Moving one guest may create new problems elsewhere, so you reassess and keep a copy of the best arrangement found.

The analogy captures targeted change and interaction. A numerical local-fitness measure is still needed; the algorithm does not understand social relationships or practical requirements unless they are represented explicitly.

Worked example

Suppose four components are ranked from worst to best. In a toy rank-based selection rule with exponent one, their unnormalized weights are 1, 1/2, 1/3 and 1/4. The weights sum to 25/12.

Their selection probabilities are therefore 12/25, 6/25, 4/25 and 3/25: 48%, 24%, 16% and 12%. The worst component is most likely to be chosen, but it is not always chosen. This gives the process some freedom to explore.

The example illustrates rank-biased selection only. A full optimization experiment also needs the component fitness definition, a valid change operation, constraint handling and a stopping rule. The chosen exponent is a teaching setting, not a recommended default.

Illustrative case study

Fictional network-design group MeshWorks wants to divide a simulated network into balanced sections with few crossing links. Its researchers compare an extremal-optimization experiment with a simpler local search using the same evaluation budget.

Some runs find strong partitions; others vary substantially. The team reports both best results and the distribution across repeated runs. It also checks balance constraints after each move. A promising single run becomes a candidate for further testing, rather than evidence that the method reliably achieves the same result every time.

Common misconceptions and mistakes

Changing a weak component is not guaranteed to improve the total objective. Interactions can make the immediate result worse, and accepting such changes is part of the search behavior. Confusing it with greedy improvement obscures this distinction.

Extremal optimization is also not identical to simulated annealing: the mechanisms for proposing and accepting exploration differ. Avoid comparing methods only by their best run or ignoring the cost of maintaining rankings. A local fitness definition can be misleading if it does not align sufficiently with the global objective or constraint structure.

Business use

This is a specialist option for hard combinatorial search when a meaningful local-fitness decomposition is available. A proposal should explain that decomposition in terms the problem owner can inspect, rather than presenting the algorithm name as a reason to expect improvement.

Measure solution quality, feasibility, computation and run-to-run variation. Compare against a credible baseline under the same budget. If the final answer affects operations, independently verify its constraints. Keep the best discovered feasible solution separate from the current search state, since exploration may deliberately pass through less attractive states.

People also ask

Does it use a population?

Classical extremal optimization typically changes components of a current solution, unlike many population-based evolutionary algorithms.

Why sometimes choose a better-ranked component?

Rank-biased randomness can help exploration avoid becoming trapped by always changing exactly the same worst component.

Does it prove optimality?

No. A heuristic result needs a separate bound or proof if global optimality is required.

Check your understanding

The current solution becomes worse after a move, but an earlier better solution was saved. Does that automatically mean the implementation is broken?

Answer: No. Temporary deterioration can be part of extremal optimization. Check the specified search procedure, constraint handling and best-so-far record before judging the move as an error.

Related terms

• Local search
• Fitness function
• Graph partitioning
• Simulated annealing
• Evolutionary computation
• heuristic optimization
• combinatorial optimization
• best-so-far solution

Learn next

Choose a small graph problem and identify a local score for each component. Examine a move that improves one local score but worsens another. Then distinguish current-solution quality from the best feasible result found across the search.

More in AI and machine learning

• Expectation propagation - Expectation propagation, or EP, is an approximate Bayesian inference method that replaces difficult probability factors with simpler approximations and...
• Experience replay - Experience replay is a training technique where a reinforcement learning agent stores its past experiences and repeatedly trains on random samples of them...
• Extremal Ensemble Learning - Extremal Ensemble Learning, or EEL, is a research approach that iteratively updates an ensemble of candidate solutions using their relative quality.
• Factor graph - A factor graph represents how a function of several variables can be written as a product of smaller functions called factors.
• Farthest-first traversal - Farthest-first traversal orders points by repeatedly selecting the point whose distance to its nearest previously selected point is greatest.
• Feature - A feature is one measurable input field a model learns from, such as a customer's age, an order's total or the hour a call arrived.

Sources

Boettcher and Percus, Extremal Optimization: an Evolutionary Local-Search Algorithm: https://arxiv.org/abs/cs/0209030. Original graph-partitioning study: https://journals.aps.org/pre/abstract/10.1103/PhysRevE.64.026114. The rank-probability calculation and MeshWorks scenario are original teaching examples; no universal performance claim is made.

Previous: Extremal Ensemble Learning Next: Extrinsic evaluation