Introduction à l’optimisation combinatoire S. Ben Ismail Majeure Informatique –

Introduction à l’optimisation combinatoire S. Ben Ismail Majeure Informatique – INF413 – C5 2e semestre 2012 Objectifs pédagogiques À l'issue de ce cours, vous devriez être capables de : connaitre la diérence entre "heuristique" et "méta-heuristique" comprendre la classi cation générale des méthodes d'optimisation combinatoire et les concepts sous-jacents décrire le fonctionnement des méthodes classiques modéliser un problème et lui appliquer une méthode d'optimisation (cf PC) Avec un peu plus de temps et de pratique : évaluer et comparer plusieurs méthodes d'optimisation sur un problème donné combiner diérentes méthodes de manière performante 1 / 68 S. Ben Ismail Introduction à l'optimisation combinatoire Plan du cours 1 Introduction 2 Méthodes d'optimisation 3 Construction 4 Recherche locale 5 Évolution 6 Hybridation 7 Conclusion 2 / 68 S. Ben Ismail Introduction à l'optimisation combinatoire Sommaire 1 Introduction 2 Méthodes d'optimisation 3 Construction 4 Recherche locale 5 Évolution 6 Hybridation 7 Conclusion 3 / 68 S. Ben Ismail Introduction à l'optimisation combinatoire Optimisation : késako ? Langue française optimiser (v.) : permettre d'obtenir le meilleur résultat possible par une action adaptée synonymes : améliorer, maximiser, mettre au point, optimaliser Mathématiques : la branche optimisation soit f : Ω7→R, trouver x∗∈Ωtel que f (x∗) = minx∈Ωf (x) (notation x∗= arg min(f )) Terminologie Ω(ou S) : espace de recherche, espace des {états, con gurations, solutions, alternatives} f : fonction objectif, coût/perte à minimiser (si gain à maximiser, considérer g = −f ) x∗(ou s∗) : optimum, minimum 4 / 68 S. Ben Ismail Introduction à l'optimisation combinatoire Exemples de problèmes d'optimisation : cas continu Ω= R Ω= Rn, fonction de Ackley f (x) = −20e−0.2 q 1 n Pn i=0 x2 i −e 1 n Pn i=1 cos(2πxi ) + 20 −e n = 2, x∗= (0, 0) optimum global : x∗tq ∀x ∈Ω, f (x∗) ≤f (x) optimum local : x∗tq ∃ϵ∀x ∈Ω, f (x∗) ≤f (x) 5 / 68 S. Ben Ismail Introduction à l'optimisation combinatoire Exemples de problèmes d'optimisation : cas discret Problème du Voyageur du Commerce (Traveling Salesman Problem (TSP)) données : n villes, une matrice de distances D = (dij) problème : trouver un chemin passant une fois et une seule par chaque ville et minimisant la distance totale parcourue Ω≃ensemble des partitions d'un ensemble à n éléments |Ω| = (n−1)! 2 pour un problème symétrique optimisation discrète (vs continue) Optimisation combinatoire minimisation d'une fonction sur un ensemble ni (mais potentiellement très grand) 6 / 68 S. Ben Ismail Introduction à l'optimisation combinatoire Énumération exhaustive 1. générer tous les trajets possibles 2. calculer leurs distances 3. choisir le trajet ayant la distance minimale n |Ω| Temps de calcul 1 5 12 12 microsecondes 10 181 440 0,18 seconde 15 43 milliards 12 heures 20 6 E+16 19 siècles 25 3 E+23 9,8 milliards d'années 30 4 E+30 1,4 millions de millards de siècles 1. un trajet évalué en une microseconde (1 million de solutions par seconde) 7 / 68 S. Ben Ismail Introduction à l'optimisation combinatoire Et avec des machines plus puissantes ? On exécute un algorithme de complexité linéaire/quadratique/cubique/exponentielle sur une machine N : taille maximale de problème pouvant être traité Machine actuelle 100x plus rapide 1000x plus rapide n N1 100 N1 1000 N1 n² N2 10 N2 31.6 N2 n³ N3 4.64 N3 10 N3 2n N4 N4 + 6.64 N4 + 9.97 Puissance de calcul vs avancées algorithmiques écart entre la croissance de la rapidité des machines et la taille des données traitables ne pas compter uniquement sur l'augmentation des capacités matérielles mais surtout sur l'innovation algorithmique 8 / 68 S. Ben Ismail Introduction à l'optimisation combinatoire Et à part le TSP ? sac à dos (Knapsack Problem) : découpage de matière première allocation de fréquences pour les réseaux radio-mobiles positionnement d'antennes pour les réseaux radio-mobiles routage dans les réseaux télécom résolution de con its de tra c aérien, roulage en aéroport (ENAC/Eurocontrol) ordonnoncement de tâches dans un atelier de production (Jobshop Scheduling) (Airbus) aectation de personnel (Air France) répartition des charges dans les camions/conténaires (Bin Packing) ... équipes de R&D à EDF, SNCF, France Télécom etc. ores de travail en optimisation : https ://portail.telecom-bretagne.eu 9 / 68 S. Ben Ismail Introduction à l'optimisation combinatoire Sommaire 1 Introduction 2 Méthodes d'optimisation 3 Construction 4 Recherche locale 5 Évolution 6 Hybridation 7 Conclusion 10 / 68 S. Ben Ismail Introduction à l'optimisation combinatoire Optimisation = modélisation + résolution 1. modélisation d'un problème : espace de recherche, solutions 2. formulation mathématique : fonction objectif, contraintes 3. application d'une méthode d'optimisation 4. obtention d'une solution 11 / 68 S. Ben Ismail Introduction à l'optimisation combinatoire Terminologie méthode complète trouve toujours une solution méthode optimale trouve toujours la meilleure solution (optimum global) méthode exacte (exhaustive) explore l'espace de recherche dans sa totalité (énumération intelligente) => optimale méthode approchée (approximative) explore une sous-partie de l'espace de recherche méthode déterministe exécute toujours la même suite d'opérations méthode probabiliste (ou stochastique) fait des choix probabilistes guidés par des tirages aléatoires 12 / 68 S. Ben Ismail Introduction à l'optimisation combinatoire Classi cation des méthodes d'optimisation combinatoire 1. Les méthodes exactes ne sont e caces que pour les instances de problèmes de petite taille, 2. On ne s'intéressera ici qu'aux méthodes approchées. 13 / 68 S. Ben Ismail Introduction à l'optimisation combinatoire Heuristique étymologie : du grec ancien eurisko,  trouver  méthode approchée conçue pour un problème d'optimisation particulier permettant de trouver des solutions avec un temps de calcul raisonnable traduit une stratégie, une manière de penser, s'appuyant sur notre connaissance du problème indispensable pour les problèmes NP −di ciles car généralement en temps polynomial Heuristique ̸= Algorithme exact algorithme exact : garantit une solution optimale heuristique : pas de garantie d'optimalité 14 / 68 S. Ben Ismail Introduction à l'optimisation combinatoire Métaheuristique (ou méta-heuristique) une heuristique est spécique à un problème et ne peut pas être généralisée méta + heuristique =  au-delà  +  trouver  = ⇒trouver avec un plus haut niveau d'abstraction une méta-heuristique est un ensemble de concepts : voisinage (modi cation d'une solution), utilisation de la mémoire, inspiration de la physique ou la nature ... une méta-heuristique est une heuristique généraliste, pouvant s'appliquer à plusieurs problèmes d'optimisation classi cation habituelle des métaheuristiques : en fonction du nombre de solutions qu'elles manipulent métaheuristiques à solution unique métaheuristiques à population de solutions 15 / 68 S. Ben Ismail Introduction à l'optimisation combinatoire Paradigmes des méthodes approchées (heuristiques et métaheuristiques) Construction solution construite par une suite de choix Recherche locale (ou voisinage) une solution initiale modi ée itérativement Évolution une population de solutions évolue par des opérateurs génétiques (sélection, croisement, mutation) Hybridation mélange des approches précédantes 16 / 68 S. Ben Ismail Introduction à l'optimisation combinatoire Sommaire 1 Introduction 2 Méthodes d'optimisation 3 Construction 4 Recherche locale 5 Évolution 6 Hybridation 7 Conclusion 17 / 68 S. Ben Ismail Introduction à l'optimisation combinatoire Principe des heuristiques constructives Fonction HeuristiqueConstructive() : solution s s : solution, s ←∅; Tant que ( s n'est pas une solution complete) faire choisir un nouvel element de solution e s ←s + e ; Fait Retourner s ; Fin 18 / 68 S. Ben Ismail Introduction à l'optimisation combinatoire Heuristiques constructives gloutonnes Dé nition Un algorithme glouton (greedy) est un algorithme qui, à chaque étape de la résolution d'un problème, fait un choix optimal dans l'espoir que le résultat nal soit optimal. Heuristique constructive gloutonne : à chaque étape, ajouter le meilleur élément de solution e Exemple : rendu de monnaie comment rendre 8¿ avec des pièces de 6¿, 4¿ et 1¿ ? 8 = 6 + 1 + 1 (or 8 = 4 + 4) les valeurs des pièces de monnaie du système monétaire sont choisies pour qu'un algorithme glouton soit optimal 19 / 68 S. Ben Ismail Introduction à l'optimisation combinatoire Problème du sac à dos (Knapsack Problem (KP)) données : sac à dos vide, objets ayant chacun un poids et une valeur objectif : maximiser la valeur totale des objets dans le sac contrainte : poids maximal autorisé dans le sac $4 12 kg $2 2 kg $1 1 kg $2 1 kg $10 4 kg ? 15 kg http ://fr.wikipedia.org/wiki/Problème_du_sac_à_dos 20 / 68 S. Ben Ismail Introduction à l'optimisation combinatoire Heuristique constructive gloutonne pour le KP stratégie : rajouter en priorité les objets ayant le meilleur rapport valeur/poids, jusqu'à ce que le sac soit rempli. objet valeur ($) poids (kg) rapport valeur/poids ($/kg) – 7 12 0.58 — 3 7 0.43 ˜ 10 9 1.11 ™ 1 2 0.5 š 2 5 0.4 valeur=0, poids=0 21 / 68 S. Ben Ismail Introduction à l'optimisation combinatoire Heuristique constructive gloutonne pour le KP stratégie : rajouter en priorité les objets ayant le meilleur rapport valeur/poids, jusqu'à ce que le sac soit rempli. objet valeur ($) poids (kg) rapport valeur/poids ($/kg) – 7 12 0.58 — 3 7 0.43 ˜ 10 9 1.11 ™ 1 2 0.5 š 2 5 0.4 ˜ valeur=10, poids=9 21 / 68 S. Ben Ismail Introduction à l'optimisation uploads/Science et Technologie/ optimisation-combinatoire-2-pdf.pdf

Tags
Science et Technologieintroduction combinatoire ismail l'optimisation recherche
Documents similaires
  • 11
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager