Developed by Stefan Boettcher and myself, Extremal Optimization (EO) is a local-search method inspired by principles of self-organized criticality. EO has been applied successfully to problems ranging from image processing to structural prediction of proteins by over a dozen different research groups and in more than 100 publications. Perhaps its most well-known application has been the work by Duch and Arenas, using EO for community detection in social networks.
For more information, see wikipedia.
Much of this work was funded by the DOE Laboratory-Directed Research and Development (LDRD) project ER 2000018 at Los Alamos National Laboratory.
- S. Boettcher and A.G. Percus, “Extremal optimization at the phase transition of the 3-coloring problem,” Physical Review E 69, 066703 (2004).
- S. Boettcher and A.G. Percus, “Optimization with extremal dynamics,” Complexity 8, 57-62 (2003).
- S. Boettcher and A.G. Percus, “Extremal optimization: an evolutionary local-search algorithm,” in: H.K. Bhargava and N. Ye, eds., Computational Modeling and Problem Solving in the Networked World: Interfaces in Computer Science and Operations Research (Kluwer Academic Publishers, Dordrecht, Netherlands, 2003), pp. 61-77.
- S. Boettcher and A.G. Percus, “Optimization with extremal dynamics,” Physical Review Letters 86, 5211-5214 (2001).
- S. Boettcher and A.G. Percus, “Extremal optimization for graph partitioning,” Physical Review E 64, 026114 (2001).
- S. Boettcher and A.G. Percus, “Nature’s way of optimizing,” Artificial Intelligence 119, 275-286 (2000).
- S. Boettcher and A.G. Percus, “Combining local search with co-evolution in a remarkably simple way,” Proceedings of the 2000 Congress on Evolutionary Computation, 1578-1584 (2000).
- S. Boettcher, A.G. Percus and M. Grigni, “Optimizing through co-evolutionary avalanches,” Proceedings of the Sixth International Conference on Parallel Problem Solving from Nature, 447-456 (2000).
- S. Boettcher and A.G. Percus, “Extremal optimization: Methods derived from co-evolution,” Proceedings of the 1999 Genetic and Evolutionary Computation Conference (GECCO ’99), 825-832 (1999).