Bases des méthodes de recherche locale PDF

Bases des méthodes de recherche locale Maria Zrikem GI2 - RSSP2 ENSA de Marrakech 2022 - 2023 1 Contexte On s’intéresse à résoudre le problème d’optimisation combinatoire suivant : S : un ensemble qui contient toutes les soluti...

Bases des méthodes de recherche locale Maria Zrikem GI2 - RSSP2 ENSA de Marrakech 2022 - 2023 1 Contexte On s’intéresse à résoudre le problème d’optimisation combinatoire suivant : S : un ensemble qui contient toutes les solutions du problème d’optimisation. C’est l’espace des solutions. f : une fonction qui associe une valeur f(s) à chaque s∈S. f correspond à l’objectif à minimiser. l’objectif : l’objectif d’un algorithme d’optimisation est de déterminer un élément dans S qui minimise la fonction f. Il s’agit de déterminer s* ∈ S tel que : f ( s*) = min f ( s ) s∈S 2 Contexte : Optimum local Vs Optimum global On s’intéresse à résoudre le problème d’optimisation combinatoire suivant : S : un ensemble qui contient toutes les solutions du problème d’optimisation. C’est l’espace des solutions. f : une fonction qui associe une valeur f(s) à chaque s∈S. f correspond à l’objectif à minimiser. l’objectif : l’objectif d’un algorithme d’optimisation est de déterminer un élément dans S qui minimise la fonction f. Il s’agit de déterminer s* ∈ S tel que : f ( s*) = min f ( s ) s∈S Optimum local: une solution aussi bonne que toutes les voisines Problème de minimisation : s+ est un optimum local ⇑ f(s+) ≤ f(s), ∀s ∈ N(s+) Optimum global (solution optimale) s* : f(s*) ≤ f(s), ∀s ∈ S 3 ⇓  Méthodes de recherche locale Les méthodes de recherche locale sont des algorithmes itératifs qui explorent l’espace X en se déplaçant pas à pas d’une solution à une autre. Une méthode de ce type débute à partir d’une solution s0 ∈ X choisie arbitrairement ou alors obtenue par le biais d’une méthode constructive. Le passage d’une solution admissible à une autre se fait sur la base d’un ensemble de modifications élémentaires qu’il s’agit de définir de cas en cas. Une solution s' obtenue à partir de s en appliquant une modification élémentaire. Un tel processus d’exploration est interrompu lorsqu’un ou plusieurs critères d’arrêt sont satisfaits. Les passages successifs d’une solution à une solution voisine définissent un chemin au travers de l’espace des solutions admissibles. 4 Méthodes de recherche locale : éléments de base Les algorithmes de recherche locale sont conçus comme une stratégie pour explorer l’espace de recherche Eléments critiques dans la conception d’une méthode de recherche locale : Solution de départ (heuristiques constructives) Représentation des solutions Voisinage Algorithme de descente (Climber) 5 Heuristiques constructives (Solutions de départ) 6 Solution de départ : Heuristiques Constructives Majorité des méthodes constructives de type « glouton »: La solution courante est complétée de la meilleure façon “locale” possible sans tenir compte des conséquences sur la solution finale (Algorithmes myopes) Inconvénients : Peut fournir une très mauvaise solution car n’atteint l’optimum que si chaque sous ensemble contient une solution optimale (est c’est rarement le cas) Avantages : rapidité et simplicité Souvent utilisée comme point de départ d’autres méthodes 7 Heuristiques Constructives Principe : Construction progressive d’une solution s = (x1, x2, …., xn) à partir d’une solution initiale vide s0 en insérant à chaque étape k (k=1 à n) une composante xo(k) dans la solution partielle courante, avec: o(k ) ∈ {1,2,...n}{o(1), o(2),...., o(k − 1)} Décision prise à une étape donnée = indice de la composante à insérer + valeur de la composante Exploration de X par une approche constructive : diminue la taille du problème en se restreignant à des sous ensemble de X. X k = {s = ( x1 , x 2 ,..., x n }∈ X / xo (1) , xo ( 2) ,..., xo ( k ) fixees Pour (k=1,…,n) X S* X2 X1 Solution optimale globale à atteindre :8s* Heuristiques Constructives : Exemples Problème du voyageur de commerce: Données: graphe orienté, longueur cij associée à chaque arc (i,j) Problème: trouver un circuit Hamiltonien (tous les sommets du graphe sont visités exactement une seule fois) de longueur totale minimale. E: ensemble d’arêtes F: sous-ensembles de E qui forment un cycle hamiltonien (CH) c( S ) = ∑c e e∈S ce: coût de l’arête e ALGORITHME DU PLUS PROCHE VOISIN 9 Heuristiques Constructives : Exemples Problème du voyageur de commerce: Algorithme de l’insertion la moins distante pour la construction d’une solution pour le problème du voyageur de commerce: k Choix du sommet Étape 0: Initialiser le cycle avec un seul sommet. Etape 1: Trouver le sommet k parmi ceux qui n’appartiennent pas à la solution courante et dont p l’arête qui le connecte à ce cycle soit la plus courte. Choix des arêtes k Etape 2: Trouver la paire d’arêtes (i,k) et (k,j) qui i j connectent le sommet k au cycle en minimisant cik + ckj - cij Insérer les arêtes (i,k) et (k,j) et éliminer l’arête p (i,j). Etape 3: Retourner à l’étape 1. 10 Heuristiques Constructives : Exemples Arbre couvrant de poids minimum : Etant donné un graphe connexe G=(V,E) et des poids ce associés aux arêtes e ∈ E, déterminer un arbre couvrant T ⊆ E dont le poids c(T) = Σ e∈T ce soit minimum. E: ensemble d’arêtes F: sous-ensembles de E qui forment des arbres couvrants Algorithme glouton pour la construction d’un arbre de poids minimum (Kruskal) Étape 0: Trier les arêtes de E de façon à ce que c1 ≤ c2 ≤...≤ cn T←∅ Étape 1: Pour i de 1 à n faire Si T ∪ {ei} ∈ F La solution T est une solution optimale alors T ← T ∪ {ei} 11 Heuristiques Constructives : Exemples Heuristique constructive pour construire une solution réalisable pour le problème du sac-à-dos 1. Trier les objets par revenus décroissants 2. Évaluer le premier objet de la liste. 3. Si son poids est inférieur ou égal au poids résiduel, choisir cet objet. Sinon, éliminer cet objet et passer au suivant en retournant à l’étape 1. Exemple numérique : objets triés par revenus: 8, 6, 3, 7, 5, 1, 2, 4 n = 8 objets solution = {8, 3} revenu = 15 poids maximum b = 15 revenus des objets: 5, 4, 6, 3, 5, 8, 5, 9 poids des objets: 3, 5, 7, 4, 2, 9, 5, 8 12 Heuristiques Constructives : Exemples Heuristique constructive pour construire une solution réalisable pour le problème du sac-à-dos 1. Trier les objets par revenus décroissants 2. Évaluer le premier objet de la liste. 3. Si son poids est inférieur ou égal au poids résiduel, choisir cet objet. Sinon, éliminer cet objet et passer au suivant en retournant à l’étape 1. Exemple numérique : objets triés par rendement : 5, 1, 8, 7, 6, 3, 2, 4 n = 8 objets solution = {5, 1, 8} revenu = 19 poids maximum b = 15 revenus des objets : 5, 4, 6, 3, 5, 8, 5, 9 poids des objets : 3, 5, 7, 4, 2, 9, 5, 8 rendement des objets : 1.67, 0.8, 0.86, 0.75, 2.5, 0.88, 1, 1.125 13 Heuristiques Constructives : Exemples Entrées : Ensemble {1,2,…,n} d’objets Poids maximum b Revenu cj associé à chaque objet j=1,…,n Poids aj associé à chaque objet j=1,…,n Problème d’optimisation : Trouver un ensemble S* d’objets qui maximise le revenu total et dont la somme des poids soit inférieure à b Exemple numérique : n = 8 objets poids maximum b = 15 revenus des objets: 5, 4, 6, 3, 5, 8, 5, 9 poids des objets: 3, 5, 7, 4, 2, 9, 5, 8 14 Représentations des solutions 15 Représentations des solutions Ensemble F de solutions (réalisables) est un sous-ensemble de E (ensemble de support ou de base) des éléments qui satisfont certaines conditions (contraintes). Représentation d’une solution: indiquer les éléments de E qui appartiennent à la solution et ceux qui n’y appartiennent pas. Problème du sac-à-dos : Entrées : n objets, poids maximum b, revenus cj et poids aj associés à chaque objet j=1,…,n Problème d’optimisation : “trouver un ensemble S* qui maximise ∑j∈S cj parmi tous les sous-ensembles S ⊆ {1,…,n} tels que ∑j∈S aj ≤ b.” Vecteur 0-1 de n éléments, xj = 1 si l’objet j appartient à la solution, xj = 0 sinon 16 Représentations des solutions Problème du voyageur de commerce E: ensemble d’arêtes F: sous-ensembles de E qui forment un circuit hamiltonien (CH) Représentation 1 : Une solution est un vecteur de n = |E| éléments : ve = 1, si l’arête e appartient au CH ve = 0, sinon. a 1 b Solutions réalisables (parmi 64 possibilités): 5 (1,1,1,1,0,0), (1,0,1,0,1,1), (0,1,0,1,1,1) 4 2 6 d c 3 17 Représentations des solutions Problème du voyageur de commerce E: ensemble d’arêtes F: sous-ensembles de E qui forment un circuit hamiltonien (CH) Représentation 2 : Une solution peut être représentée par l’ordre dans lequel les sommets sont visités, c.à.d., comme une permutation circulaire des n sommets (puisque le premier sommet peut être choisi arbitrairement) a 1 b (a)bcd (a)bdc (a)cbd 5 (a)cdb (a)dbc (a)dcb 4 2 6 d c 3 18 Représentations des solutions Indicateurs 0-1 d’appartenance: – Problème du sac-à-dos – Problèmes de recouvrement et de partitionement Indicateurs généraux d’appartenance: – Coloration de graphes Permutations: – Problèmes d’ordonnancement Job/Flow/Open Shop Scheduling – Problème du voyageur de commerce 19 Voisinage d’une solution (mouvement) 20 Voisinage et mouvement Problème combinatoire : f(s*) = minimum {f(s): s ∈ S} S est un ensemble fini de solutions Le Voisinage d’une solution s est un sous-ensemble de solutions qu’il est possible d’atteindre par une modification élémentaire de s. Voisinage : élément qui introduit la notion de proximité entre les solutions de l’espace S Le voisinage d’une solution s ∈ S est un sous-ensemble de S : N(s) = {s1,s2,…,sk} solutions voisines de s s’ est une solution voisine de s : si s’ est obtenue partir de s suite à un mouvement élémentaire. Deux solution voisines sont proche dans le coût. Les bons voisinages permettent de représenter de forme efficace et compacte l’ensemble des solutions voisines à toute solution s 21 Voisinage et espace de recherche Espace de recherche : défini par l’ensemble des solutions S et par un voisinage N 22 Voisinage et espace de recherche Espace de recherche : défini par l’ensemble des solutions S et par un voisinage N 23 Voisinage et espace de recherche Espace de recherche : défini par l’ensemble des solutions S et par un voisinage N 24 Voisinage et espace de recherche Espace de recherche : défini par l’ensemble des solutions S et par un voisinage N 25  Voisinage pour le pb du sac à dos Exemple : problème du sac-à-dos Entrées : Ensemble {1,2,…,n} d’objets Problème d’optimisation : Poids maximum b Trouver un ensemble S* d’objets qui Revenu cj associé à chaque objet j=1,…,n maximise le revenu total et dont la Poids aj associé à chaque objet j=1,…,n somme des poids soit inférieure à b Représentation des solutions : Un vecteurs d’appartenance 0-1 v=(v1,…,vi,…,vn) : vi = 1, si l’objet i est choisi vi = 0, sinon Voisinage : Si s=(v1,…,vi,…,vn) est la solution courante, une voisine de s est la solution (v1,…,1- vi ,…,vn ) : vi ! 1-vi N4(v)={(v1,…,1-vi,…,vn), i=1,..,n} Voisins de (1,0,1,1) = {(0,0,1,1), (1,1,1,1), (1,0,0,1), (1,0,1,0)} 26 Voisinage pour le pb du sac à dos Structuration de l’espace de recherche 100 101 000 001 010 011 110 111 27 Voisinages pour l’espace des permutation Voisinages dans l’espace des permutations : Solution π=(π1,…,πi -1,πi,πi +1,…,πj,…,πn) N1(π)={(π1,…,πi+1,πi ,…,πn): i=1,…, n-1} Voisins de (1,2,3,4) = {(2,1,3,4),(1,3,2,4), (1,2,4,3)} N2(π)={(π1,…,πj,...,πi,…,πn): i=1,…,n-1; j=i+1,…,n} Voisins de (1,2,3,4)= {(2,1,3,4),(1,3,2,4), (1,2,4,3),(3,2,1,4),(1,4,3,2), (4,3,2,1)} N3(π)={(π1,…, πi -1,πi +1,…,πj,πi,…,πn): i=1,…,n-1; j=i+1,…,n} Voisins de (1,2,3,4) = {(2,1,3,4),(2,3,1,4), (2,3,4,1),(1,3,2,4),(1,3,4,2), (1,2,4,3)} 28 Voisinage et espace de recherche Espace des permutations avec le voisinage N1 Solution π=(π1,…,πi -1,πi,πi +1,…,πj,…,πn) N1(π)={(π1,…,πi+1,πi ,…,πn): i=1,…, n-1} Voisins de (1,2,3,4) = {(2,1,3,4),(1,3,2,4), (1,2,4,3)} 1243 1342 1234 1324 2143 2134 3124 3142 2314 3214 2341 3241 2431 3421 4231 4321 2413 4213 4312 3412 4123 4132 29 1423 1432 Voisinages pour le voyageur de commerce Voisinage 2-opt Voisinage 3-opt 30 31 Algorithmes de descente (Climbers) 32  Algorithmes de descente (Climbers) Les algorithmes de recherche locale sont des algorithmes itératif visant à explorer l’espace de recherche. Itération : est stratégie de recherche dans le voisinage visant l’amélioration de la solution courante dans son voisinage Amélioration itérative: à chaque itération, sélectionner dans le voisinage une solution meilleure que la solution courante procedure Amélioration-Itérative(s0) s ← s0; amélioration ←.vrai. while amélioration do amélioration ←.faux. for-all s’∈N(s) et amélioration =.faux. do if f(s’) < f(s) then s ← s’; amélioration ←.vrai. end-if end-for-all end-while return s 33 end Amélioration-Itérative  Algorithmes de descente (Climbers) Les algorithmes de recherche locale sont des algorithmes itératif visant à explorer l’espace de recherche. Itération : est stratégie de recherche dans le voisinage visant l’amélioration de la solution courante dans son voisinage Descente la plus rapide: à chaque itération, sélectionner la meilleure solution du voisinage procedure Descente-Rapide(s0) s ← s0; amélioration ←.vrai. while amélioration do amélioration ←.faux.; fmin ← +∞ for-all s’ ∈ N(s) do if f(s’) < fmin then smin ← s’; fmin ← f(s’) end-if end-for-all if fmin < f(s) then s ← smin ; amélioration ←.vrai. end-if end-while return s end Descente-Rapide 34  Algorithmes de descente (Climbers) Exemple : algorithme de descente la plus rapide appliqué à un problème d’ordonnancement Espace de recherche: permutations des n éléments Solution π = (π1,…,πi -1,πi,πi +1,…,πj,…,πn) Voisinage : N1(π)={(π1,…,πi+1,πi ,…,πn): i=1,…, n-1} Coût d’une permutation : f(π) = ∑i=1,…,n i.πi 35  Algorithmes de descente (Climbers) Exemple : algorithme de descente la plus rapide appliqué à un problème d’ordonnancement procedure RL-Perm-N1(π0) π ← π0; amélioration ←.vrai. while amélioration do Espace de recherche: permutations des n éléments amélioration ←.faux.; fmin ← +∞ for i = 1 to n-1 do Solution π = (π1,…,πi -1,πi,πi +1,…,πj,…,πn) π’ ← π; π’i ← πi+1; π’i+1 ← πi; càd dans chaque voisinage if f(π’) < fmin then Voisinage : (à chaque πmin ← π’ ; fmin ← f(π’) permutation) N1(π)={(π1,…,πi+1,πi ,…,πn): i=1,…, n-1} end-if end-for Coût d’une permutation : f(π) = ∑i=1,…,n i.πi if fmin < f(π) then ici la meilleure solution du voisinage est comparée avec la solution dont on travaille π ← πmin ; amélioration ←.vrai. end-if end-while π+ ← π return π+ end RL-Perm-N1 36  Algorithmes de descente (Climbers) Exemple : algorithme de descente la plus rapide appliqué à un problème d’ordonnancement 1243 1342 1234 1324 2143 2134 3124 3142 2314 3214 2341 3241 2431 3421 4231 4321 2413 4213 4312 3412 4123 4132 1423 1432 37  Algorithmes de descente (Climbers) Exemple : algorithme de descente la plus rapide appliqué à un problème d’ordonnancement 21 23 20 21 22 21 23 25 23 24 26 27 27 29 29 30 25 27 29 28 26 27 23 24 38 Algorithmes de descente (Climbers) Exemple : Voyageur de commerce symétrique 0 6 5 7 8 1 4 14 15 9 10 11 2 3 13 39 Algorithmes de descente (Climbers) Exemple : Voyageur de commerce symétrique 1243 1342 1234 1324 2143 2134 3124 3142 2314 3214 2341 3241 2431 3421 4231 4321 2413 4213 4312 3412 4123 4132 1423 1432 40 Algorithmes de descente (Climbers) Exemple : Voyageur de commerce symétrique 51 50 48 49 49 50 52 50 47 48 46 48 50 51 49 48 50 52 50 49 48 47 48 46 41 Algorithmes de descente (Climbers) Exemple : Voyageur de commerce asymétrique 6 0 65 65 27 24 2 82 45 1 4 0 4 80 79 62 31 96 41 96 16 2 3 7 64 42 Algorithmes de descente (Climbers) Exemple : Voyageur de commerce asymétrique 1243 1342 1234 1324 2143 2134 3124 3142 2314 3214 2341 3241 2431 3421 4231 4321 2413 4213 4312 3412 4123 4132 1423 1432 43 Algorithmes de descente (Climbers) Exemple : Voyageur de commerce asymétrique 161 164 35 113 241 179 170 347 252 271 157 201 305 243 272 328 182 272 306 154 152 236 206 293 44 Algorithmes de recherche locale Différents aspects de l’espace de recherche peuvent influencer la performance d’un algorithme de recherche locale Connexité : il doit y avoir un chemin entre chaque paire de solutions de l’espace de recherche Nombre de solutions voisines : temps de calcul pour évaluer chaque voisin. Distance entre deux solutions : nombre de sommets visités sur le chemin le plus court entre elles. Diamètre : distance entre les deux solutions les plus éloignées (diamètres réduits!) 45 Faiblesse des algorithmes de recherche locale Questions fondamentales : cet algo va être efficace si ces points sont bien traîtés – Définition du voisinage – Stratégie de recherche dans le voisinage – Complexité de chaque itération: Dépend du nombre de solutions dans le voisinage Dépend du calcul efficace du coût de chaque solution voisine Difficultés : – Arrêt prématuré sur le premier optimum local – Sensibles à la solution de départ – Sensibles au voisinage choisi – Sensible à la stratégie de recherche – Nombre d’itération Pour réduire ces difficultés et améliorer les algorithmes : Métaheuristiques 46 GRASP comme une première métaheuristique 47 Greedy Randomized Adaptive Search Procedures (GRASP) Combinaison d’une méthode constructive avec une approche par recherche locale, dans une procédure itérative (multi-départ) où les itérations sont totalement indépendantes les unes des autres (a) construction d’une solution (b) recherche locale Algorithme de base: f(s*) ← +∞ for i = 1,…,N do Construire une solution s en utilisant un algorithme glouton randomisé Appliquer une procédure de recherche locale à partir de s, pour obtenir la solution s’ if f(s’) < f(s*) then s* ← s’ end-for 48 Greedy Randomized Adaptive Search Procedures (GRASP) Recherche locale: amélioration des solutions construites lors de la première phase – choix du voisinage – structures de données efficaces pour accélérer la recherche locale – bonnes solutions de départ permettent d’accélérer la recherche locale Diversification basée sur la randomisation contrôlée: différentes solutions construites lors des différentes itérations du GRASP 49 Greedy Randomized Adaptive Search Procedures (GRASP) Technique d’échantillonage de l’espace de recherche 50 Greedy Randomized Adaptive Search Procedures (GRASP) Implémentation simple : algorithme glouton + recherche locale Algorithmes gloutons: faciles de construire et implémenter Peu de paramètres à régler: restrictivité de la liste de candidats nombre d’itérations Parallélisation: simple et directe N itérations, p processeurs: chaque processeur fait N/p itérations de la méthode A la fin, chaque processeur informe au maître la meilleure solution qu’il a trouvée Dépend de bonnes solutions de départ Désavantage : n’utilise pas de mémoire 51