Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

CONSERVATOIRE NATIONAL DES ARTS ET MÉTIERS PARIS MÉMOIRE PRÉSENTÉ EN VUE D’OBTE

CONSERVATOIRE NATIONAL DES ARTS ET MÉTIERS PARIS MÉMOIRE PRÉSENTÉ EN VUE D’OBTENIR L’EXAMEN PROBATOIRE EN INFORMATIQUE PAR BAPTISTE AUTIN Les métaheuristiques en optimisation combinatoire Soutenu le 9 mai 2006 - Jury - Président : M. le Professeur Christophe Picouleau Membres : 1 TABLES DES MATIERES Tables des matieres ................................................................................................................... 2 Introduction ............................................................................................................................... 3 Les métaheuristiques, une réponse aux problèmes d’optimisation difficile ........................ 4 Le cadre de l’optimisation combinatoire ................................................................................. 4 Structure de voisinage et minimum local ................................................................................ 6 Méthode exacte et méthode approchée ................................................................................... 7 Heuristique et métaheuristique ................................................................................................ 8 Analyse des principales métaheuristiques ............................................................................ 11 La méthode de descente ............................................................................................................................................... 11 Avantages et inconvénients ............................................................................................... 11 La méthode du recuit simulé ................................................................................................. 12 Paramétrage ....................................................................................................................... 13 Variante ............................................................................................................................. 14 Avantages et inconvénients ............................................................................................... 14 Applications ...................................................................................................................... 14 La méthode Tabou ................................................................................................................ 15 Mémoire à court terme ...................................................................................................... 15 Application au problème d’ordonnancement de tâches .................................................... 17 Mémoire à long terme ....................................................................................................... 18 Avantages et inconvénients ............................................................................................... 18 La méthode GRASP .............................................................................................................. 19 Avantages et inconvénients ............................................................................................... 20 Les algorithmes génétiques ................................................................................................... 20 Principe de l’algorithme génétique ................................................................................... 21 Opérateurs de sélection ..................................................................................................... 21 Opérateurs de variation ..................................................................................................... 23 Avantages et inconvénients ............................................................................................... 24 Les algorithmes de colonies de fourmi ................................................................................. 25 Principe de l’algorithme .................................................................................................... 26 Paramétrage ....................................................................................................................... 27 Généralisation et variantes ................................................................................................ 28 Avantages et Inconvénients ............................................................................................... 28 Stratégies de recherche ........................................................................................................... 30 Intensification et diversification ............................................................................................ 30 Hybridation des méthodes ..................................................................................................... 32 Choix d’une structure de voisinage ....................................................................................... 33 Quelle métaheuristique utiliser ? ........................................................................................... 33 Conclusion ............................................................................................................................... 35 Références bibliographiques .................................................................................................. 36 2 INTRODUCTION Les métaheuristiques forment un ensemble de méthodes utilisées en recherche opérationnelle pour résoudre des problèmes d’optimisation réputés difficiles. Résoudre un problème d’optimisation combinatoire, c’est trouver l’optimum d’une fonction, parmi un nombre fini de choix, souvent très grand. Les applications concrètes sont nombreuses, que ce soit dans le domaine de la production industrielle, des transports ou de l’économie – partout où se fait sentir le besoin de minimiser des fonctions numériques, dans des systèmes où interviennent simultanément un grand nombre de paramètres. A ces problèmes de minimisation, 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 ; elles se distinguent en cela des méthodes dites exactes, qui garantissent certes la résolution d’un problème, mais au prix de temps de calcul prohibitifs pour nombres d’applications industrielles. Nous nous proposons de fournir un panorama de toutes ces techniques, parfois redoutablement efficaces, qui se développent depuis une vingtaine d’années. Après avoir donné quelques définitions préalables, et rappelé les énoncés de quelques problèmes traditionnels d’optimisation combinatoire, nous replacerons les métaheuristiques dans leur contexte : nous dégagerons leurs principales propriétés, et nous établirons une première classification. Puis nous passerons en revue les métaheuristiques les plus usuelles, en analysant leur mode de fonctionnement, en évoquant les évolutions auxquelles elles ont donné lieu, et en soulignant leurs avantages et leurs inconvénients respectifs. Nous verrons à cette occasion toute la richesse et la variété des procédés mis en jeu dans les métaheuristiques. Enfin, dans un troisième temps, nous nous pencherons sur la question de la stratégie à suivre pour mettre en place une métaheuristique, et nous verrons que, malgré leur dissemblances, les métaheuristiques sont toutes structurées par un petit nombre de concepts, dont la compréhension aide au paramétrage de leurs algorithmes de base. L’examen des techniques d’hybridation et l’association de métaheuristiques avec d’autres méthodes d’optimisation clôtureront notre étude. 3 LES MÉTAHEURISTIQUES, UNE RÉPONSE AUX PROBLÈMES D’OPTIMISATION DIFFICILE Le cadre de l’optimisation combinatoire En mathématiques, l'optimisation recouvre toutes les méthodes qui permettent de déterminer l'optimum d'une fonction, avec ou sans contraintes. En théorie, 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. A chaque instance du problème est associé un ensemble discret de solutions S, un sous-ensemble X de S représentant les solutions admissibles (réalisables), ainsi qu’une fonction de coût f (appelée aussi fonction objectif). 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. Schéma 1 : représentation du chemin le plus court passant par une distribution aléatoire de 1000 points. Dans le schéma ci-dessus, le problème était de trouver le chemin minimal passant une seule fois par un certain nombre de points (problème du voyageur de commerce, voir paragraphe suivant). Ce graphique correspond à une certaine instance du problème. Avec une distribution différente de points, nous aurions eu une autre instance du problème. 4 Il existe une seconde formalisation du problème d’optimisation combinatoire, plus générale, qui inclue la notion de contraintes et d’affectation de valeurs à des variables. En voici la définition. Soit : - un ensemble de variables ) , , , ( 2 1 n x x x  - un ensemble de domaines de définitions n D D D , , , 2 1  - 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) - une fonction objectif f que l’on cherche à minimiser : ℜ → × × × n D D D f  2 1 : L’ensemble S des solutions possibles peut alors se définir comme : S = { { } ) , ( , ), , ( 1 1 n n v x v x s  = tels que i i D v ∈ , 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… 1.1 L’optimisation difficile L’ « optimisation combinatoire » consiste à trouver la meilleure solution entre un nombre fini de choix. Autrement dit, à minimiser une fonction, avec ou sans contraintes, sur un ensemble fini de possibilités. Quand le nombre de combinaisons possibles devient exponentiel par rapport à la taille du problème, le temps de calcul devient rapidement critique. Ce temps de calcul devient si problématique que pour certains problèmes, on ne connaît pas d’algorithme exact polynomial, c'est-à-dire dont le temps de calcul soit proportionnel à n N , où N désigne le nombre de paramètres inconnus du problème, et où n est une constante entière. Lorsqu’on conjecture qu’il n’existe pas une telle constante n telle qu’un polynôme de degré n puisse borner le temps de calcul d’un algorithme, on parle alors d’optimisation difficile, ou de problèmes NP-difficiles (c’est tout l’objet de la théorie de la NP-complétude). Exemples de problèmes L’un des exemples les plus caractéristiques du champ de l’optimisation combinatoire est 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 par exemple, 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 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. 5 Un autre problème classique est celui de l’affectation quadratique, qui, par rapport au PVC, introduit la notion de flot circulant entre les villes, et qui peut s’énoncer ainsi : 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 i n j ij ij d f 1 1 où ij f représente le flot entre l’objet i et l’objet j, et ij d la distance entre l’objet i et l’objet j. La répartition de bâtiments dans un espace donné en fonction du nombre de personnes amenées à circuler entre ces bâtiments, ou 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. Enfin, troisième problème combinatoire caractéristique, l’ordonnancement de tâches, dont l’énoncé classique est le suivant : soit un ensemble uploads/Voyage/ rapport-metaheuristiques-optimisation-combinatoire.pdf