Definition
Unlike genetic algorithms that maintain a population, EO works on a single solution. It identifies the component contributing least to the overall fitness and replaces it with a random alternative. This process continues until a satisfactory solution is found. It is particularly effective for NP-hard problems where traditional gradient-based methods fail. The algorithm mimics natural selection at a microscopic level, focusing on local improvements to achieve global optimization.
Summary
Extremal optimization is a heuristic search algorithm inspired by self-organized criticality, designed to solve combinatorial optimization problems by iteratively removing the worst-performing components.
Key Concepts
- Heuristic Search
- Combinatorial Optimization
- Self-Organized Criticality
- Local Improvement
Use Cases
- Graph partitioning problems
- Scheduling tasks in computing clusters
- Optimizing network routing paths