Scattered research
Dispersed search (SS) is an evolutionary method that has been proposed by (Glover and Laguna 1997). It was proposed within the framework of the resolution of combinatorial problems.
This metaheuristic differs from classical evolutionary algorithms by the use of a procedure of local search and by the generalization of the crossover operator. Just like the genetic algorithms, it is based on a population of solutions that evolves over time using both a selection operator, the linear combination of solutions from the population to create a new provisional solution (not necessarily integer or admissible) , of a projection operator making it possible to make the provisional solution admissible and of elimination operators.
Description of the method
The general concept of dispersed research given by (Glover et al. 1998) is based on the following three foundations:
- Useful information about the optimal solution is typically contained in a diverse collection of elite solutions.
- Solution combination strategies contain mechanisms that incorporate diversification and intensification into the generation of new solutions.
- The use of several combinations of reference solutions increases the opportunity to exploit the information contained in the union of elite solutions.
The dispersed search algorithm model is based on the definition of the following five major components (known as methods):
- Diversification Generation Method: Consists of generating a collection of various starting solutions.
- Improvement method: Points are optimized using local search.
- Method for updating the R reference seti: builds and maintains a reference set obtained by selecting the best b solutions found.
- Method of generating subsets: generates subsets Di from the reference set.
- Combination of solutions method: generates solutions by combining the solutions of each subset Di to produce the set Ci.
Algorithm
