Scatter search

Scatter search (SS) is a method of evolution that has been proposed by (Glover and Laguna 1997).

This differs from conventional metaheuristic evolutionary algorithms by using a local search and the generalization of the crossover operator. Like genetic algorithms, it is based on a population of solutions that evolves over time using both a selection operator and the linear combination of solutions of the population to create a new provisional solution, and a projection operator to make the temporary solution eligible and elimination operators.


The general concept of SS that has been given by (Glover et al., 1998) is based on the following three foundations:

  1. Useful information about the optimal solution is typically contained in a diverse collection of elite solutions.
  2. Solution combining strategies contain mechanisms that incorporate diversification and intensification into the generation of new solutions.
  3. The use of several combinations of reference solutions increases the opportunity to exploit the information contained in the union of elite solutions..

The SS algorithm model is based on the definition of the following five major components (so-called methods):

  1. Diversification Generation Method: Consists of generating a collection of various starting solutions.
  2. Improvement Method: Points are optimized using a local search.
  3. Reference set update method Ri: constructs and maintains a reference set obtained by selecting the best b found solutions.
  4. Subset Generation Method: generates subsets Di from the reference set.
  5. Méthode de combinaison de solutions : génère des solutions en combinant les solutions de chaque sous ensemble pour produire l’ensemble .
  6. Solution Combination Method: Generates solutions by combining the solutions of each subset Di to produce the set Ci.