Remerciez-le!

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

Optimisation combinatoire 2 pdf

Introduction à l ? optimisation combinatoire S Ben Ismail Majeure Informatique ?? INF ?? C e semestre CObjectifs pédagogiques À l'issue de ce cours vous devriez être capables de B connaitre la di érence entre heuristique et méta-heuristique comprendre C 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 B méthodes d'optimisation sur un problème donné combiner di érentes méthodes de manière performante S Ben Ismail Introduction à l'optimisation combinatoire CPlan du cours Introduction Méthodes d'optimisation Construction Recherche locale Évolution Hybridation Conclusion S Ben Ismail Introduction à l'optimisation combinatoire CSommaire Introduction Méthodes d'optimisation Construction Recherche locale Évolution Hybridation Conclusion S Ben Ismail Introduction à l'optimisation combinatoire COptimisation 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 s oniottafti on x ? ? Ra rgtromuivne rf x ? ?? tel que f x ? minx f ?? x Terminologie ou S espace de recherche espace des états C con gurations solutions alternatives f fonction objectif coût perte à minimiser si gain à maximiser considérer g ??f x ? ou s ? optimum minimum S Ben Ismail Introduction à l'optimisation combinatoire CExemples de problèmes d'optimisation cas continu R Rn fonction de Ackley e ?? ?? n f x e e n i x i ?? n n i cos ?xi ?? optimum global x ? tq ??x ?? f x ? ? n f x x ? optimum local x ? tq ?? ??x ?? f x ? ? f x S Ben Ismail Introduction à l'optimisation combinatoire CExemples 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 d ij 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 ?? pour un problème symétrique optimisation discrète vs continue C Optimisation combinatoire minimisation d'une fonction sur un ensemble ni mais potentiellement très grand S Ben Ismail Introduction à l'optimisation combinatoire CÉnumération exhaustive générer tous les trajets possibles calculer leurs distances choisir le trajet ayant la distance minimale n Temps de calcul microsecondes seconde milliards heures E siècles E milliards d'années E millions de millards de sièclesun trajet évalué en une microseconde million de solutions par seconde S Ben Ismail Introduction à l'optimisation combinatoire CEt 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 x plus rapide x plus rapide n n ? n ? n N N N N N NN N N N NN Puissance de calcul vs avancées algorithmiques écart entre la croissance de la rapidité des machines et la