1.2.6 Métaheuristiques combinées à la
recherche arborescente
Frenc et al. (2001) proposent une méthode
hybride qui combine un algorithme génétique et un Branch
& Bound pour un problème de MAX-SAT. Les algorithmes
génétiques appartiennent à la famille des
métaheuristiques; ils utilisent la notion de sélection naturelle
et l'appliquent à une population de solutions potentielles au
problème donné. Il y a trois aspects dans les algorithmes
génétiques : la sélection, le croisement et la mutation
(voir le chapitre 4 pour plus de détails sur les algorithmes
génétiques). Dans cette configuration, chaque
élément de chromosome correspond à une variable binaire de
l'instance du problème. L'hybridation proposée dans cet article
montre de meilleurs résultats que l'utilisation seule d'un Branch and
Bound ou d'un algorithme génétique.
Pessan et al. (2007) présentent une
méthode d'hybridation entre une approche de Branch & Bound et un
algorithme génétique. Leur idée est d'utiliser
l'algorithme génétique pour améliorer la borne
supérieure et ainsi accélérer la résolution par
Branch & Bound, tandis que l'algorithme génétique utilise les
noeuds non instanciés de la méthode de Branch & Bound afin de
réduire l'espace de recherche. Les deux méthodes sont
utilisées en parallèle et collaborent ensemble.
D'autres métaheuristiques sont basées sur la
coopération. On peut citer notamment les algorithmes d'Optimisation par
Colonie de Fourmis (Dorigo et al., 1991) dans lesquels des fourmis
construisent des solutions et déposent des quantités de
phéromone dépendant de la qualité des solutions
trouvées (voir le chapitre 3 pour plus de détails sur les
algorithmes d'Optimisation par Colonie de Fourmis). Cette phéromone est
ensuite utilisée par les fourmis afin de les diriger vers un espace de
recherche. Un processus d'évaporation permet de ne garder qu'un ensemble
de solutions jugées intéressantes. Khichane et al.
(2008) proposent une méthode qui utilise un langage de
programmation par contraintes pour décrire un problème et
remplace la procédure de recherche arborescente par une recherche par
Optimisation par Colonie de Fourmis. Chaque fourmi construit une affection ne
violant aucune contrainte, cette affectation
pouvant être partielle. La qualité des affectations
construites dépend du nombre de variables affectées.
La plupart des métaheuristiques sont utilisées
davantage pour des problèmes d'optimisation combinatoire pour lesquels
le nombre de solutions est important. En effet, ces métaheuristiques
étant pour certaines basées sur la coopération entre les
solutions, le nombre de solutions détermine en partie
l'efficacité de la méthode.
| 
