WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

Techniques hybrides de recherche exacte et approchée: application à  des problèmes de transport

( Télécharger le fichier original )
par Boris BONTOUX
Université d'Avignon et des pays de Vaucluse - Doctorat spécialité informatique 2008
  

précédent sommaire suivant

Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy

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.

précédent sommaire suivant






Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy








"Tu supportes des injustices; Consoles-toi, le vrai malheur est d'en faire"   Démocrite