Research on Extremal Optimization:

As an important practical application resulting from my research on Self-Organized Criticality (SOC), Allon Percus and I have developed a powerful general-purpose method to approximate (NP-)hard optimization problems. The method is inspired by the far-from-equilibrium dynamics often found in nature where extremely bad adapted components of a system are selectively driven to extinction, leaving behind complex and highly adapted structures (such as eco-systems). This "Extremal Optimization" approach provides a new philosophy to optimization in its use of non-equilibrium statistical physics and in merely selecting against the bad instead of favoring the good. In this sense it complements other general-purpose methods such as "Simulated Annealing" or "Genetic Algorithms," both of which it can dominate computationally in quality, speed, and memory requirements. Mimicking the dynamics of slowly driven dissipative systems, it is free of tunable parameters such as temperature schedules or selection criteria.

EO-optimized Graph Partition

The generality of the EO method has recently been demonstrated by Meshoul and Batouche who used the EO algorithm as described above successfully on a standard cost function for aligning natural images.

An optimization heuristic base on a non-equilibrium process such as EO appears to be capable to elucidate the properties of phase transitions in combinatorial optimization problems. We have demonstrated these properties so far for graph partitioning and the 3-coloring problem. EO has received grant support by Los Alamos and the NSF. There are also a number of studies on EO by other groups. A Wikipedia blog on EO has been started by J. Brownlee.

EO has found a large number of applications by other
researchers, e.g. in pattern recognition (Meshoul), signal filtering (Yom-Tov, Svenson), transport problems (Sousa), molecular dynamics simulations (Zhou), artificial intelligence (Menai), social modeling (Duch, Danon, Neda), and 3d spin glass models (Dall, Onody). There are also a number of studies of EO's extensions (Middleton, Iwamatsu, Sousa) and of rigorous
performance properties (Hoffmann).

Java Applet Demo:

Extremal Optimization Demo

Most generally, "Extremal Optimization" operates on a "fitness" defined for each variable in a system which takes the place of the usual cost function. This fitness is a local measure of how well each particular variable fits into a solution. In close similarity to SOC models such as the Bak-Sneppen model (DEMO), the algorithm proceeds as follows:

  1. Order all fitness values in a list.
  2. Select the variable with the worst fitness for a random change (for better or for worse!!!).
  3. Update the fitness of this and any other variable effected by the change.
  4. Repeat at (1), if a set time limit has not been past.

While the state of the system may fluctuate widely ("avalanching"), the bias against badly adapted elements of the solution pushes the system repeatedly in the neighborhood of near-optimal solutions. Only the best of those solutions will have to be remembered along the way and is returned at the end of a "run."

This algorithm applied to Graph Partitioning performs at least as well as Simulated Annealing. In particular, Extremal Optimization does well near critical points inherent to many NP-hard problems, where Simulated Annealing (and many other methods) fail. Such a heuristic is very useful in physics as a tool to explore the ground state properties disorder systems such as Spin Glasses. In particular, Extremal Optimization helped to confirm predictions for Mean-Field Spin Glasses obtained with Replica Symmetry Breaking (RSB) and to obtain the stiffness exponent y=0.24(1) governing thermal "droplet" excitations in the d=3 Edwards-Anderson model (EA). As a consequence, we were able to predict the lower critical dimension for EA to be d=5/2. More recently, we have shown that EO produces excellent results also for highly connected variables, such as in the Sherrington-Kirkpatrick model.

Java Applet Demo:

EO for Spin Glasses Demo

Emory CollegeGraduate School of Arts and Sciences 
Emory University | Search | Index | Help

©1996-2002 Physics Department, Emory University.
These pages may be freely distributed if unmodified.
Last Update: 9/26/02; 2:55:53 PM
For more information, contact: