Méthodes émergentes pour Problèmes d’Optimisation Combinatoire (PCO) PDF

Module : Méthodes émergentes pour Problèmes D’optimisation Combinatoire (PCO) 1. Introduction 2. Conexte de l’explosion combinatoire 3. Exemples de problèmes d’explosion combinatoire 4. Formulations mathématiques 5. Notion de voisinage, minimum local, munimum global 6. Mé...

Module : Méthodes émergentes pour Problèmes D’optimisation Combinatoire (PCO) 1. Introduction 2. Conexte de l’explosion combinatoire 3. Exemples de problèmes d’explosion combinatoire 4. Formulations mathématiques 5. Notion de voisinage, minimum local, munimum global 6. Méthode de résolution - Méthodes exactes - Heuristiques - Métaheuristiques 7. Strategies de recherche - Intensification - Diversification - Mouvement 8. Conclusion References Bibligraphiques Questions Pr.Yahyaoui Khadidja  1. INTRODUCTION Les méthodes émergentes pour l’optimisation combinatoire sont des méthodes qualifiées comme des nouvelles strategies pour la résolution des problèmes d’optimisation combinatoires. Les métaheuristiques sont réputées comme des méthodes déstinées pour la résolution des problémes d’optimisation soufrant d’une explosion combinatire. Pour quoi les métaheuristiques ?? - les métaheuristiques permettent, dans des temps de calcul raisonnables, de trouver des solutions, peut-être pas toujours optimales, en tout cas très proches de l’optimum ; - pour nombres d’applications, les métaheuristiques se distinguent des méthodes exactes, qui garantissent certes la résolution d’un problème, mais au prix de temps de calcul très grand. - 2. LE CONTEXTE DE L’OPTIMISATION COMBINATOIRE l'optimisation concerne toutes les méthodes qui permettent de déterminer l'optimum d'une fonction, avec ou sans contraintes. Un problème d'optimisation combinatoire se définit par l’ensemble de ses instances, souvent infiniment nombreuses. Dans la pratique, le problème se ramène à résoudre numériquement l’une de ces instances, par un procédé algorithmique. 3. Exemples de problème d’optimisation combinatoire : le problème du voyageur de commerce : dans lequel un représentant doit visiter un certain nombre de villes, avant de retourner à son point de départ : la question est de déterminer le trajet le plus court traversant chaque ville une seule fois, c'est-à- dire la succession de villes qui minimise la tournée du représentant. De nombreux problèmes d’ingénierie peuvent se ramener au problème du voyageur de commerce (PVC), d’où son intérêt. On le retrouve dans le domaine des réseaux informatiques avec les algorithmes de routage. Par ailleurs, le PVC est un cas particulier d’un problème plus général, celui des tournées de véhicules, qui consiste à calculer 2  les meilleurs parcours pour une flotte de véhicules devant livrer un ensemble de produits dans plusieurs destinations à partir d'un entrepôt. Chaque véhicule a une capacité limitée. Le problème des tournées de véhicules trouve ses applications dans le domaine de la distribution bien sûr, mais aussi dans les télécoms. représentation du chemin le plus court passant par une distribution aléatoire de 12 villes. Ce graphique correspond à une certaine instance du problème. le problème était de trouver le chemin minimal passant une seule fois par un certain nombre de villes. 3  50 villes -> 49! solutions possibles, i.e. 6,08.1062 tournées possibles.Explosion combinatoire Problème de collecte des déchets : CARP But : Collecter les déchets sur les rues Objectif : Au moindre coût Contraintes : Capacité limitée des camions Problème de collecte des déchets : CARP avec 3 Camions l’affectation quadratique : il s’agit de déterminer comment placer n objets dans n emplacements de manière à minimiser la somme des produits flots par distances. Mathématiquement, cela revient à minimiser : n n  f ij  dij où fij représente le flot entre l’objet i et l’objet j, et dij la distance i=1 j =1 entre l’objet i et l’objet j. la façon de répartir des modules électroniques sur une carte en fonction du nombre de connexions les liant les uns aux autres, reviennent à résoudre le problème de l’affectation quadratique. 4  l’ordonnancement de tâches, dont l’énoncé classique est le suivant : soit un ensemble m de machines, un ensemble t de tâches à réaliser, chaque tâche étant composée d’une certaine suite d’opérations. Une machine ne peut réaliser qu’une seule opération à la fois. Comment ordonner l’exécution des opérations sur les différentes machines de telle façon que le temps mis à faire tout le travail soit fait soit minimal ? 4. Formulations mathématiques Deux Formulations mathématiques d’un problème d’optimisation se présentent : Formulation 1 : A chaque instance du problème est associée : - un ensemble discret de solutions S, - un sous-ensemble X de S représentant les solutions admissibles (réalisables), - fonction de coût f (appelée aussi fonction objectif). Avec : f assigne à chaque solution s  X le nombre f(s). Résoudre un problème d’optimisation combinatoire consiste alors à trouver une solution s  X optimisant la valeur de la fonction de coût f. Formellement, on cherche donc : s*  X tel que f(s*) ≤ f(s) pour tout s  X. Une telle solution s* s'appelle une solution optimale, ou un optimum global. Remarque : on peut tout aussi bien résoudre des problèmes de maximisation, les principes de résolution restant naturellement les mêmes. Formulation 2 Avec contraintes et d’affectation de valeurs à des variables. un ensemble de variables (x1 , x2 ,…, xn ) - un ensemble de domaines de définitions D1 , D2 ,…, Dn - un ensemble de contraintes C sur les variables (par exemple, des inéquations, ou bien l’obligation que toutes les variables prennent des valeurs différentes) 5  - une fonction objectif f que l’on cherche à minimiser : f : D1  D2 … Dn →  L’ensemble S des solutions possibles peut alors se définir comme : S = { s = (x1, v1 ),…,(xn , vn ) tels que vi  Di , et tels que s satisfasse toutes les contraintes C} Les problèmes d'affectation sous contraintes possèdent de nombreuses applications pratiques, comme l'affectation de ressources, le groupement, la classification, la planification, l'emploi du temps et l'ordonnancement, dans des domaines très variés… 5. Notion de voisinage, minimum local, minimum global Soit : - S un ensemble de solutions à un problème d’optimisation, et - f la fonction objectif. Un voisinage est une fonction N qui associe un sous-ensemble de S à toute solution s S. Une solution s’ N(s) est dite voisine de s. Une solution s  S est un minimum local relativement au voisinage N si f(s) ≤ f(s’)  s’ N(s). Une solution s  S est un minimum global si f(s) ≤ f(s’)  s’ S. 6  Schéma 2 : analogie entre une fonction numérique à une variable, et la fonction de coût d’un problème combinatoire A retenir : 1. Certaines méthodes d’optimisation, qui partent d’une solution initiale et qui l’améliorent en explorant son voisinage immédiat, présentent l’inconvénient de s’arrêter au premier minimum local trouvé. 2. les métaheuristiques évitent d’étre piègé dans ces minima locaux contiennent en explorant davantage tout l’espace des solutions. en pratique, le voisinage est obtenu par l’ensemble des modifications élémentaires que l’on peut appliquer à une solution s donnée, par exemple l’ensemble des permutations (si les solutions peuvent s’écrire sous la forme d’une séquence finie d’éléments, comme le cas se présente fréquemment en optimisation combinatoire) Si cet ensemble est trop grand, on pourra toujours le réduire à un sous- ensemble, aléatoirement, ou en fonction d’un critère précis. 7  Exemples de structures de voisinage Exemple de calcul de voisinage E est couramment appelé "espace de recherche". On cherche l'optimum de f, i.e. l'élément x de E minimisant (ou maximisant) f. On suppose que l'espace E est de grande taille Notion de voisinage : l'espace est structuré A chaque élément x de E, on associe un voisinage. Un voisinage est un ensemble d'éléments de E 8  6. Méthodes de résolution Méthodes exactes : 1. Les méthodes exactes ont permis de trouver des solutions optimales pour des problèmes de taille raisonnable. 2. Les méthodes complétes/exactes explorent de façon systèmatique l’espace de recherche. → ne marche pas dans de nombreux probl`emes `a cause explosion combinatoire. 3. Ces mèthodes sont gènèralement à base de recherche arborescente → contrainte par l’ordre des noeuds dans l’arbre → exemples : les techniques de séparation et évaluation (branch-and-bound), ou les algorithmes avec retour arrière (backtracking). Or il y a souvent des cas ou on peut se contenter d'une solution approchée, pourvu qu'elle soit suffisament \bonne". (ex du TSP, on ne veut pas forcement le minimum mais quelque chose d'assez court, par exemple