As an important practical application resulting from my research on SelfOrganized Criticality (SOC), Allon Percus and I have developed a powerful generalpurpose method to approximate (NP)hard optimization problems. The method is inspired by the farfromequilibrium 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 ecosystems). This "Extremal Optimization" approach provides a new philosophy to optimization in its use of nonequilibrium statistical physics and in merely selecting against the bad instead of favoring the good. In this sense it complements other generalpurpose 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. 

An optimization heuristic base on a nonequilibrium 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 3coloring 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 
Java Applet 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 BakSneppen
model (DEMO), the algorithm proceeds as follows:
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 nearoptimal 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 NPhard 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 MeanField 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 EdwardsAnderson 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 SherringtonKirkpatrick model.  Java Applet Demo: 
©19962002 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: webmaster@physics.emory.edu 