Gloutons EDA Ant Colony Optimization ACO/Car sequencing ACO/Subset selection Co

Gloutons EDA Ant Colony Optimization ACO/Car sequencing ACO/Subset selection Cours de Master Recherche Sp´ ecialit´ e CODE : R´ esolution de probl` emes combinatoires Christine Solnon LIRIS, UMR 5205 CNRS / Universit´ e Lyon 1 2007 Gloutons EDA Ant Colony Optimization ACO/Car sequencing ACO/Subset selection Rappel du plan du cours 1 - Introduction Qu’est-ce qu’un probl` eme complexe ? Exemples de probl` emes complexes 2 - Approches compl` etes Structuration de l’espace de recherche en Arbre Structuration de l’espace de recherche en Treillis 3 - Approches incompl` etes bas´ ees sur les instances Recherche locale Algorithmes g´ en´ etiques 4 - Approches incompl` etes bas´ ees sur les mod` eles Algorithmes gloutons al´ eatoires Algorithmes par estimation de distribution (EDA) Optimisation par colonies de fourmis (ACO) Gloutons EDA Ant Colony Optimization ACO/Car sequencing ACO/Subset selection Approches bas´ ees sur les mod` eles Principe g´ en´ eral Approches constructives : ⇝constructions incr´ ementales de combinaisons Utilisation d’un “mod` ele” ⇝heuristique de choix du composant ` a ajouter Mod` eles statiques vs dynamiques Mod` eles statiques ⇝Algorithmes gloutons (al´ eatoires) Mod` eles dynamiques ⇝modifier le mod` ele / exp´ erience pass´ ee Algorithmes par estimation de distribution ⇝statistiques sur les exp´ eriences pass´ ees Algorithmes ` a base de colonies de fourmis ⇝exp´ erience pass´ ee compil´ ee sous forme de ph´ eromone Gloutons EDA Ant Colony Optimization ACO/Car sequencing ACO/Subset selection Approches bas´ ees sur les mod` eles Principe g´ en´ eral Approches constructives : ⇝constructions incr´ ementales de combinaisons Utilisation d’un “mod` ele” ⇝heuristique de choix du composant ` a ajouter Mod` eles statiques vs dynamiques Mod` eles statiques ⇝Algorithmes gloutons (al´ eatoires) Mod` eles dynamiques ⇝modifier le mod` ele / exp´ erience pass´ ee Algorithmes par estimation de distribution ⇝statistiques sur les exp´ eriences pass´ ees Algorithmes ` a base de colonies de fourmis ⇝exp´ erience pass´ ee compil´ ee sous forme de ph´ eromone Gloutons EDA Ant Colony Optimization ACO/Car sequencing ACO/Subset selection Principe g´ en´ eral des algorithmes gloutons Construction incr´ ementale d’une combinaison e ∈E e ←combinaison vide Cand ←ensemble des composants de combinaisons tant que Cand ̸= ∅faire Choisir le meilleur composant de Cand et l’ajouter ` a e ⇝Heuristique de choix ≪gloutonne ≫ Mettre ` a jour l’ensemble Cand des composants pouvant ˆ etre ajout´ es ` a e Retourner e Pour certains probl` emes, algorithme optimal ⇝Simplex/probl` emes lin´ eaires, Dijkstra/plus court chemin Gloutons EDA Ant Colony Optimization ACO/Car sequencing ACO/Subset selection Comment concevoir un algorithme glouton ? Soit un probl` eme d’optimisation (E, f) ⇝E = ensemble des combinaisons candidates ⇝f = fonction objectif ` a maximiser 3 points ` a d´ efinir : 1 Identifier les composants des combinaisons 2 D´ efinir une fonction mettant ` a jour l’ensemble des candidats par rapport ` a une combinaison partielle 3 D´ efinir une fonction heuristique ´ evaluant la qualit´ e d’un composant par r apport ` a une combinaison partielle Gloutons EDA Ant Colony Optimization ACO/Car sequencing ACO/Subset selection Exemple 1 : Le voyageur de commerce Choisir al´ eatoirement un sommet si ∈S π =< si > Cand ←S −{si} tant que Cand ̸= ∅faire Choisir sj ∈candidats selon une heuristique gloutonne ajouter sj ` a la fin de π Cand ←Cand −{sj} Quelle heuristique gloutonne ??? Gloutons EDA Ant Colony Optimization ACO/Car sequencing ACO/Subset selection Exemple 2 : Recherche d’une clique maximum C ←∅ Cand ←S tant que Cand ̸= ∅faire Choisir sj ∈candidats selon une heuristique gloutonne C ←C ∪{sj} Cand ←Cand ∩{si/(si, sj) ∈A} Quelle heuristique gloutonne ??? A B C D E F G Gloutons EDA Ant Colony Optimization ACO/Car sequencing ACO/Subset selection Exemple 3 : Coloriage d’un graphe nbCoul ←0 Cand ←S tant que Cand ̸= ∅faire Choisir sj ∈candidats selon une heuristique gloutonne Si ∃i ≤nbCoul tq ∀sk adjacent ` a sj, couleur(sk) ̸= i Alors couleur(sj) ←i Sinon nbCoul ←nbCoul + 1; couleur(sj) ←nbCoul Cand ←Cand −{sj} Quelle heuristique gloutonne ??? [Br´ elaz 79] A B C D E F G Gloutons EDA Ant Colony Optimization ACO/Car sequencing ACO/Subset selection Exemple 3 : Coloriage d’un graphe nbCoul ←0 Cand ←S tant que Cand ̸= ∅faire Choisir sj ∈candidats selon une heuristique gloutonne Si ∃i ≤nbCoul tq ∀sk adjacent ` a sj, couleur(sk) ̸= i Alors couleur(sj) ←i Sinon nbCoul ←nbCoul + 1; couleur(sj) ←nbCoul Cand ←Cand −{sj} Quelle heuristique gloutonne [Br´ elaz 79] A B C D E F G Gloutons EDA Ant Colony Optimization ACO/Car sequencing ACO/Subset selection Exemple 4 : R´ esoudre un CSP (X, D, C) ⇝MaxCSP A ←∅ Cand ←X pour toute variable Xi ∈X, Dfiltr´ e(Xi) ←D(Xi) tant que Cand ̸= ∅faire Choisir Xj ∈Cand tq |Dfiltr´ e(Xj)| soit minimal Choisir v ∈D(Xj) A ←A∪< Xj, v > pour toute variable Xi ∈X telle que Xi ne soit pas affect´ ee dans A, Dfiltr´ e(Xi) ←filtrage(Dfiltr´ e(Xi), < Xj, v >) Cand ←Cand −{Xj} Heuristique de choix d’une valeur ⇝d´ epend du probl` eme Gloutons EDA Ant Colony Optimization ACO/Car sequencing ACO/Subset selection Exemple 5 : Ordonnancement de voitures But : S´ equencer des voitures sur une chaˆ ıne de montage Chaque voiture demande un ensemble d’options Espacer les voitures demandant une mˆ eme option Contraintes ` a respecter pour le s´ equencement : Plus d’infos sur http://www.csplib.org/ voir prob001 Gloutons EDA Ant Colony Optimization ACO/Car sequencing ACO/Subset selection Exemple 5 : Ordonnancement de voitures But : S´ equencer des voitures sur une chaˆ ıne de montage Chaque voiture demande un ensemble d’options Espacer les voitures demandant une mˆ eme option Contraintes ` a respecter pour le s´ equencement : Bleu ≤1/2 Plus d’infos sur http://www.csplib.org/ voir prob001 Gloutons EDA Ant Colony Optimization ACO/Car sequencing ACO/Subset selection Exemple 5 : Ordonnancement de voitures But : S´ equencer des voitures sur une chaˆ ıne de montage Chaque voiture demande un ensemble d’options Espacer les voitures demandant une mˆ eme option Contraintes ` a respecter pour le s´ equencement : Bleu ≤1/2 ; Rouge ≤2/5 ; Vert ≤1/5 Plus d’infos sur http://www.csplib.org/ voir prob001 Gloutons EDA Ant Colony Optimization ACO/Car sequencing ACO/Subset selection Exemple 5 : Ordonnancement de voitures But : S´ equencer des voitures sur une chaˆ ıne de montage Chaque voiture demande un ensemble d’options Espacer les voitures demandant une mˆ eme option Contraintes ` a respecter pour le s´ equencement : Bleu ≤1/2 ; Rouge ≤2/5 ; Vert ≤1/5 ; Cabriolet ≤1/3 Plus d’infos sur http://www.csplib.org/ voir prob001 Gloutons EDA Ant Colony Optimization ACO/Car sequencing ACO/Subset selection Exemple 5 : Ordonnancement de voitures (2) ⇝heuristique bas´ ee sur les taux d’utilisation des options Option i de capacit´ e pi/qi ⇝TU(i) = qi.nb voitures demandant i pi.nb total voitures π ←<> Cand ←ensemble des voitures ` a s´ equencer tant que Cand ̸= ∅faire Soit cj la voiture de Cand telle que l’ajout de cj ` a la fin de π minimise le nb de contraintes viol´ ees et (en cas d’ex-aequo) P i∈options(cj ) TU(i) soit maximal Ajouter cj ` a la fin de la s´ equence π Cand ←Cand −{cj} Gloutons EDA Ant Colony Optimization ACO/Car sequencing ACO/Subset selection Gloutons al´ eatoires (1) Probl` eme En g´ en´ eral, un algorithme glouton retourne une assez bonne solution ... mais (` a peu pr` es) toujours la mˆ eme Id´ ee Introduire un peu d’al´ eatoire pour diversifier la recherche Ex´ ecuter plusieurs fois l’algorithme... et retourner la meilleure solution Gloutons EDA Ant Colony Optimization ACO/Car sequencing ACO/Subset selection Gloutons al´ eatoires (2) Approches pour ≪introduire un peu d’al´ eatoire ≫ Approche “1 parmi les meilleurs” S´ electionner les k meilleurs composants ...ou bien les composants ` a k% de l’optimum Choisir au hasard 1 de ces composants ⇝k = param` etre pour ≪r´ egler ≫le degr´ e d’al´ eatoire Approche probabiliste S´ electionner le prochain composant selon une probabilit´ e Probabilit´ e de choisir ci ∈Cand : p(ci) = h(ci)α P ck ∈Cand h(ck)α Tirer un nombre flottant al´ eatoire x compris entre 0 et 1 Choisir ci tq P j<i p(cj) < x ≤P j≤i p(cj) Gloutons EDA Ant Colony Optimization ACO/Car sequencing ACO/Subset selection Gloutons al´ eatoires (2) Approches pour ≪introduire un peu d’al´ eatoire ≫ Approche “1 parmi les meilleurs” S´ electionner les k meilleurs composants ...ou bien les composants ` a k% de l’optimum Choisir au hasard 1 de ces composants ⇝k = param` etre pour ≪r´ egler ≫le degr´ e d’al´ eatoire Approche probabiliste S´ electionner le prochain composant selon une probabilit´ e Probabilit´ e de choisir ci ∈Cand : p(ci) = h(ci)α P ck ∈Cand h(ck)α Tirer un nombre flottant al´ eatoire x compris entre 0 et 1 Choisir ci tq P j<i p(cj) < x ≤P j≤i p(cj) Gloutons EDA Ant Colony Optimization ACO/Car sequencing ACO/Subset selection Comparaison de Glouton et Glouton al´ eatoire Probl` emes d’ordonnancement de voitures : Al´ eatoire pur Glouton pur Glouton al´ eatoire (α = 0) (α = ∞) (α = 6) 1 35.4 (1.7) 10.4 (1.6) 5.5 (0.6) 2 23.1 (1.1) 7.7 (0.9) 0.8 (0.4) uploads/Ingenierie_Lourd/ cours-4 1 .pdf

Tags
Ingénierie gloutons colony optimization aco/car sequencing
Documents similaires
  • 22
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager