Cours1 meta 4gi 2013 inro mc
Les métaheuristiques Pour L ? optimisation di ?cile Maria ZRIKEM ENSA de Marrakech Les métaheuristiques COptimisation combinatoire L ? homme envisage di ?cilement la multiplicité des combinaisons qui se présentent même dans les moindres faits de la vie lorsque plusieurs variables peuvent prendre chacune des états di ?érents Exemple Combien faut-il de temps à une famille de personnes prenant en commun deux repas journaliers pour épuiser toutes les possibilités de se grouper autour de la table familiale ENSA de Marrakech Les métaheuristiques COptimisation combinatoire ? f X ? R ?? fonction objectif ? X ?? ensemble de solutions possibles réalisables X est un ensemble ?ni mais de taille énorme ENSA de Marrakech Les métaheuristiques CProblèmes faciles et problèmes di ?ciles ? Algorithme polynomial le temps d ? exécution cro? t de façon polynomiale avec la taille du problème O nd ? Problèmes faciles classe P il existe des algorithmes polynomiaux ? Problèmes NP-dif ?ciles - on ne conna? t pas d ? algorithmes polynomiaux - on n ? arrive pas à démontrer la non-existence de tels algorithmes - s ? il existe un algorithme polynomial pour un de ces problèmes alors il existe des algorithmes polynomiaux pour toute la classe ENSA de Marrakech Les métaheuristiques CProblèmes faciles et problèmes di ?ciles L ? optimisation combinatoire ? consiste à trouver la meilleure solution entre un nombre ?ni de choix Autrement dit à minimiser une fonction avec ou sans contraintes sur un ensemble ?ni 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 ENSA de Marrakech Les métaheuristiques CProblèmes faciles et problèmes di ?ciles O n O n O n O n O lg n ENSA de Marrakech Les métaheuristiques CExemple de problème facile Trouver le plus court chemin entre deux sommets dans un graphe ? Quelle est la taille de l ? espace des solutions ? Faut-il parcourir toutes les solutions pour trouver la meilleure ENSA de Marrakech Les métaheuristiques COptimisation combinatoire Problème d ? a ?ectation n t? ches doivent être a ?ectées à n machines t? che par machine Le coût d ? exécution de la t? che i par la machine j est cij Trouver l ? a ?ectation qui minimise le coût total ENSA de Marrakech Les métaheuristiques COptimisation combinatoire Problème du voyageur de commerce Un voyageur de commerce doit visiter n villes La distance entre les villes i et j est cij Trouver le plus court trajet cycles di ?érents pour le même ensemble de villes ENSA de Marrakech Les métaheuristiques COptimisation combinatoire begin input n number of cities C n x n non negative integer distance matrix min su ?ciently large number say n times the maximum element of C for all possible tours i e cyclic permutations of n ?nd length of tour if length min then min length store tour endif next tour end Les solutions possibles sont n Pour n l ? énumération des a ?ectations trajets
Documents similaires
-
28
-
0
-
0
Licence et utilisation
Gratuit pour un usage personnel Aucune attribution requise- Détails
- Publié le Apv 09, 2022
- Catégorie Management
- Langue French
- Taille du fichier 58.3kB