Scatter search: foundations and implementations

• Manuel Laguna ^[1] ; Sergio Cavero ^[2] ; Rafael Martí ^[3]
  1. [1] University of Colorado Boulder

     University of Colorado Boulder

     Estados Unidos

     
  2. [2] Universidad Rey Juan Carlos

     Universidad Rey Juan Carlos

     Madrid, España

     
  3. [3] Universitat de València

     Universitat de València

     Valencia, España

     

  Mostrar afiliaciones +
• Localización: Sort: Statistics and Operations Research Transactions, ISSN 1696-2281, Vol. 50, Nº. 1, 2026, págs. 3-42
• Idioma: inglés
• DOI: 10.57645/20.8080.02.30
• Enlaces
  • Texto completo (pdf)
• Resumen

  • Scatter search is a population-based metaheuristic designed to solve complex optimization problems through structured solution combination and adaptive memory. Unlike traditional evolutionary algorithms, scatter search emphasizes deterministic strategies to balance intensification and diversification. We present a comprehensive review of scatter search and its connection to path relinking, covering their historical development, core methodology, and applications. Key components of scatter search include diversification generation, improvement, reference set updating, subset generation, and solution combination. Advanced strategies such as dynamic reference set updating, tiered memory structures, constructive and destructive neighborhoods, and vocabulary building enhance its performance and scalability. Scatter search has been successfully applied in scheduling, routing, bioinformatics, and software engineering. Hybridizations with other metaheuristics and integration with machine learning further expand its applicability. The review concludes with a tutorial on a scatter search Python implementation for 0-1 knapsack problems that includes a Jupyter Notebook with code, execution traces, visualizations, and didactic analyses.