Recherche dispersée
La recherche dispersée (SS) est une méthode d’évolution qui a été proposée par (Glover et Laguna 1997). Elle a été proposée dans le cadre de la résolution des problèmes combinatoire.
Cette métaheuristique se distingue des algorithmes évolutionnistes classiques par l’utilisation d’une procédure de recherche locale et par la généralisation de l’opérateur de croisement. Tout comme les algorithmes génétiques, elle est basée sur une population de solutions qui évolue dans le temps à l’aide à la fois d’un opérateur de sélection, de la combinaison linéaire de solutions de la population pour créer une nouvelle solution provisoire (non forcément entière ou admissible), d’un opérateur de projection permettant de rendre la solution provisoire admissible et d’opérateurs d’élimination.
Description de la méthode
Le concept général de la recherche dispersée qui a été donné par (Glover et al. 1998) se base sur les trois fondations suivantes :
- L’information utile sur la solution optimale est typiquement contenue dans une collection diverse de solutions élites.
- Les stratégies de combinaison des solutions contiennent des mécanismes qui incorporent la diversification et l’intensification dans la génération des nouvelles solutions.
- L’utilisation de plusieurs combinaisons de solutions de référence augmente l’opportunité d’exploiter l’information contenue dans l’union des solutions élites.
Le modèle de l’algorithme de la recherche dispersée repose sur la définition des cinq composants majeurs (dits méthodes) suivants :
- Méthode de génération de diversification : Consiste à générer une collection de diverses solutions de départ.
- Méthode d’amélioration : Les points sont optimisés à l’aide d’une recherche locale.
- Méthode de mise à jour de l’ensemble de référence Ri: construit et maintient un ensemble de référence obtenu en sélectionnant les b meilleures solutions trouvées.
- Méthode de génération des sous ensembles : génère des sous ensembles Di à partir de l’ensemble de référence.
- Méthode de combinaison de solutions : génère des solutions en combinant les solutions de chaque sous ensemble Di pour produire l’ensemble Ci.
Algorithme
