Remerciez-le!

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

ENSA de Marrakech, Les métaheuristiques 1 Les métaheuristiques Pour L’optimisat

ENSA de Marrakech, Les métaheuristiques 1 Les métaheuristiques Pour L’optimisation difficile Maria ZRIKEM ENSA de Marrakech, Les métaheuristiques 2 Optimisation combinatoire L’homme envisage difficilement 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 différents. Exemple : Combien faut-il de temps à une famille de 8 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 3 Optimisation combinatoire • f : X → R – fonction objectif • X – ensemble de solutions possibles (réalisables). X est un ensemble fini, mais de taille énorme. ENSA de Marrakech, Les métaheuristiques 4 Problèmes faciles et problèmes difficiles • 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 5 Problèmes faciles et problèmes difficiles 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. ENSA de Marrakech, Les métaheuristiques 6 Problèmes faciles et problèmes difficiles O(n) O(n2) O(n3) O(2n) O(lg n) ENSA de Marrakech, Les métaheuristiques 7 Exemple 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 8 Optimisation combinatoire Problème d’affectation : n tâches doivent être affectées à n machines (1 tâche par machine). Le coût d’exécution de la tâche i par la machine j est cij . Trouver l’affectation qui minimise le coût total. ENSA de Marrakech, Les métaheuristiques 9 Optimisation 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. 2 cycles différents pour le même ensemble de villes ENSA de Marrakech, Les métaheuristiques 10 Optimisation combinatoire Les solutions possibles sont n!. Pour n = 20 l’ énumération des affectations (trajets) possibles, à vitesse d’un million par seconde, prendrait 77 000 ans ! begin input n (number of cities), C(n x n) (non negative integer distance matrix) min = sufficiently large number (say, n times the maximum element of C) for all possible tours, i.e. cyclic permutations of {1,2,...,n} find length of tour if length < min then min=length, store tour endif next tour end ENSA de Marrakech, Les métaheuristiques 11 Optimisation combinatoire représentation du chemin le plus court passant par une distribution aléatoire de 1000 points. ENSA de Marrakech, Les métaheuristiques 12 Problème NP-Difficiles célèbres •Problème SAT et variante 3SAT (mais 2SAT est polynomial) ; •Problème du voyageur de commerce •Problème du cycle hamiltonien •Problème de la clique maximum •Problèmes de colorations de graphes •Problème d'ensemble dominant dans un graphe •Problème de couverture de sommets dans un graphe •Le problème Reach (ou Accessibilité) qui consiste à savoir s’il existe un chemin entre deux sommets d'un graphe ENSA de Marrakech, Les métaheuristiques 13 Méthodes de résolution Deux classes de méthodes pour résoudre les problèmes d’optimisation difficiles :  Méthodes exactes qui garantissent l’optimalité de la résolution mais qui perdent en efficacité pour les applications de grande taille (le cas du Branch- and-bound).  Méthodes approchées qui gagnent en efficacité et permettent de trouver des solutions de bonnes qualité en un temps de calcul raisonnable sans garantir l’optimalité (c’est le cas des méthodes heuristiques) ENSA de Marrakech, Les métaheuristiques 14 Heuristiques Du grec heuriskien : Trouver/découvrir (heureka) Définition : Heuristique : algorithme de résolution ne fournissant pas nécessairement une solution optimale. Toutefois, on désire : Une complexité “raisonnable” Le plus souvent possible une solution proche de l’optimum Le moins souvent possible une mauvaise solution De la simplicité d’implémentation Heuristiques et métaheuristiques Heuristiques : algorithmes approchés spéciﬁques pour certain type de problème Métaheuristiques : méthodes génériques pouvant optimiser une large gamme de problèmes différents, sans nécessiter de changements profonds dans l’algorithme employé ENSA de Marrakech, Les métaheuristiques 15 Métaheuristiques Les métaheuristiques forment une famille d'algorithmes d’optimisation visant à résoudre des problèmes d'optimisation difficile issus de la recherche opérationnelle pour lesquels on ne connaît pas de méthode classique plus efficace. Les métaheuristiques sont généralement des algorithmes stochastiques, qui progressent vers un optimum par échantillonnage d'une fonction objectif. Elles essayent d’apprendre les caractéristiques du problème à ﬁn de trouver une approximation de la meilleure solution Elles utilisent un haut niveau d’abstraction leur permettant d’ être adaptées aux problèmes diff érents ENSA de Marrakech, Les métaheuristiques 16 Métaheuristiques •En 1996, I.H. Osman et G. Laporte définissaient la métaheuristique comme « un processus itératif qui subordonne et qui guide une heuristique, en combinant intelligemment plusieurs concepts pour explorer et exploiter tout l’espace de recherche. Des stratégies d’apprentissage sont utilisées pour structurer l’information afin de trouver efficacement des solutions optimales, ou presque-optimales ». ENSA de Marrakech, Les métaheuristiques 17 Métaheuristiques •En 2006, le réseau Metaheuristics (metaheuristics.org) définit les métaheuristiques comme « un ensemble de concepts utilisés pour définir des méthodes heuristiques, pouvant être appliqués à une grande variété de problèmes. On peut voir la métaheuristique comme une « boîte à outils » algorithmique, utilisable pour résoudre différents problèmes d’optimisation, et ne nécessitant que peu de modifications pour qu’elle puisse s’adapter à un problème particulier ». ENSA de Marrakech, Les métaheuristiques 18 Techniques de résolution pratique Face à un problème d’optimisation : • l’étape la plus importante est l’étape de la modélisation, • preuve de l’appartenance du problème à la classe NP-Difficile, • transformation du problème en un problème de programmation mathématique, • utilisation du programme mathématique pour l’obtention de bornes sur le problème, • obtention de quelques solutions par heuristiques, • mise en œuvre des métaheuritiques pour améliorer les solutions initiales En bref, De Un aveu d’impuissance à Des techniques performantes de résolution ENSA de Marrakech, Les métaheuristiques 19 Avantages des métaheuristiques • La recherche d’une solution optimale peut être totalement inappropriée dans certaines applications pratiques. • Lorsqu’elle est applicable, une méthode exacte est souvent beaucoup plus lente qu’une méthode heuristique, ce qui engendre des coûts informatiques supplémentaire et des difficultés au niveau du temps de réponse. • Les principes de recherche qui sont à la base d’une heuristiques sont en général plus accessibles aux utilisateurs non expérimentés. • une méthode heuristique peut être facilement adaptée ou combinée avec d’autres types de méthodes, ce qui augmente considérablement la possibilité d’utilisation des métaheuristiques ENSA de Marrakech, Les métaheuristiques 20 Organisation générale D'une manière générale, les métaheuristiques s'articulent autour de trois notions : • La diversification/exploration désigne les processus visant à récolter de l'information sur le problème optimisé. Elle met en place des stratégies qui permettent d’explorer un grand espace de solutions et d’échapper à des minima locaux. • L'intensification/exploitation vise à utiliser l'information déjà récoltée pour définir et parcourir les zones intéressantes de l'espace de recherche. Elle permet de rechercher des solutions de plus grande qualité en s’appuyant sur les solutions déjà trouvées • La mémoire est le support de l'apprentissage, qui permet à l'algorithme de ne tenir compte que des zones où l'optimum global est susceptible de se trouver, évitant ainsi les optima locaux. ENSA de Marrakech, Les métaheuristiques 21 Parcours contre population • Les métaheuristiques les plus classiques sont celles fondées sur la notion de parcours (b). Dans cette optique, l'algorithme fait évoluer une seule solution sur l'espace de recherche à chaque itération. La notion de voisinage est alors primordiale. Les plus connues dans cette classe sont le recuit simulé, la recherche avec tabous, la recherche à voisinage variable, la méthode GRASP ou encore les méthode de bruitage. • L'autre approche utilise la notion de population (a). La métaheuristique manipule un ensemble de solutions en parallèle à chaque itération. On peut citer les algorithmes génétiques, l'optimisation par essaims particulaires, les algorithmes de colonies de fourmis. ENSA de Marrakech, Les métaheuristiques 22 Liste de métaheuristiques Les métaheuristiques les plus connues sont : • les algorithmes génétiques, • le recuit simulé, • la recherche avec tabous, • les algorithmes de colonies de fourmis, • les algorithmes de recherche a voisinage variable, • les algorithmes d'optimisation par essaims particulaires, • les algorithmes à estimation de distribution. Il existe un grand nombre d'autres métaheuristiques, plus ou moins connues : • l'algorithme du kangourou, • la méthode de Fletcher et Powell, • la méthode GRASP, • la méthode du bruitage, • les systèmes immunitaires artificiels, • les algorithmes à évolution différentielle, • la tunnelisation stochastique, • l'escalade de collines à recommencements aléatoires, uploads/Management/ cours1-meta-4gi-2013-inro-mc.pdf