[PDF] [PDF] LES METAHEURISTIQUES€:

[PDF] Introduction aux métaheuristiques - GERAD

Classification des méthodes pour le résoudre, ou de méthode classique efficace ▻ On va combinant des techniques métaheuristiques `a des algorithmes

[PDF] LES METAHEURISTIQUES€:

Les méthodes de recherche locale sont des algorithmes itératifs qui explorent l' espace X en se déplaçant pas à pas d'une solution à une autre Une méthode de  

[PDF] Les méthodes de résolution approchées pour le - Cedric-Cnam

Heuristique par méthode gloutonne Heuristique par recherche locale 3 Les métaheuristique La métaheuristique Variable Neihborhood Descent (VND)

Métaheuristiques hybrides pour la résolution du - Archipel UQAM

Chapitre 2: Méthodes de résolution de problèmes d'optimisation combinatoire 7 2 2 3 2 L'hybridation de méthodes exactes et de métaheuristiques 27

[PDF] Metaheuristiques et optimisation combinatoire - eCursus - Université

13 fév 2019 · Métaheuristiques Algorithmes évolution- naires Optimisation multi- Objectifs 4/ 33 Méthodes de résolution Différents types de méthodes de 

[PDF] Métaheuristiques pour loptimisation combinatoire - Laure Gonnord

– mimétisme – heuristique – méta heuristique – minimum local / global – méthodes (in)complètes – codage solution – landscape – structure de voisinage – 

[PDF] algorithme heuristique pdf

[PDF] généralités sur les systèmes automatisés de production

[PDF] différence entre heuristique et métaheuristique

[PDF] structure fonctionnelle d'un système automatisé

[PDF] méthodes heuristiques d'optimisation

[PDF] définition d'un système automatisé de production

[PDF] méthodes heuristiques et métaheuristique d'optimisation

[PDF] méthode heuristique optimisation

[PDF] système automatisé de production sap

[PDF] les métaheuristiques en optimisation combinatoire

[PDF] système automatisé de production pdf

[PDF] système automatisé de production ppt

[PDF] cours aide soignante module 1 pdf

[PDF] qcm module 1 aide soignante gratuit

[PDF] cours aide soignante module 2

3 e

Conférence Francophone de MOdélisation et SIMulation "Conception, Analyse et Gestion des Systèmes Industriels"

MOSIM'01 - du 25 au 27 avril 2001 - Troyes (France)

LES METAHEURISTIQUES :

DES OUTILS PERFORMANTS POUR LES PROBLEMES INDUSTRIELS

Marino WIDMER

Université de Fribourg

Département d'informatique

Rue Faucigny 2

CH - 1700 Fribourg (Suisse)

Mél : marino.widmer@unifr.ch

RESUME : Durant ces dernières années, plusieurs métaheuristiques ont prouvé leur efficacité pour la résolution de

problèmes combinatoires, ensemble auquel appartiennent plusieurs problèmes industriels. Ce papier se concentre sur

la description des trois classes principales de métaheuristiques, à savoir les méthodes constructives, celles dites de

recherche locale (comme le recuit simulé, les méthodes d'acceptation à seuil et la méthode tabou) et celles considérées

comme évolutives (comme les algorithmes génétiques, la méthode de recherche distribuée et l'algorithme de la fourmi).

Une réflexion sur l'approche hybride (combinaison de diverses métaheuristiques) est également menée en fin de ce

papier.

MOTS-CLES : Métaheuristiques, méthodes constructives, méthodes de recherche locale, méthodes évolutives.

1. INTRODUCTION

Si les problèmes d'organisation industrielle sont la plu- part du temps relativement simples à énoncer, il ne faut en aucun cas sous-estimer l'effort nécessaire pour leur trouver une solution (Widmer, 1998). Ces problèmes font souvent partie des problèmes d'optimisation combina- toire pour lesquels, dans la majorité des cas, il est très difficile de trouver la solution optimale; en effet, à quel- ques exceptions près, la seule méthode connue pour résoudre le problème de manière exacte serait de faire une énumération complète de toutes les solutions possi- bles ! Les spécialistes parlent dans ce cas de problème NP-complet (Carlier et Chrétienne, 1988), (Garey et Johnson, 1979). Ainsi, dans ces conditions, il est néces- saire de trouver un mode de résolution qui fournisse une solution de bonne qualité dans un laps de temps raison- nable : c'est ce que font les méthodes heuristiques. Ce papier se concentre sur la description des trois classes principales d'heuristiques, à savoir les méthodes cons- tructives, celles dites de recherche locale et celles consi- dérées comme évolutives (Costa, 1995). Ces méthodes étant suffisamment générales pour être appliquées à plusieurs catégories de problèmes d'optimisation combi- natoire, elles portent le nom de métaheuristiques. La structure de ce papier s'articule comme suit : le para- graphe 2 décrit brièvement et de manière générale ce que sont les problèmes d'optimisation combinatoire ainsi que les difficultés rencontrées lors de la résolution de ces

derniers. Le paragraphe suivant offre une présentationrelativement complète des principales métaheuristiques

qui sont le plus couramment utilisées aujourd'hui.

2. L'OPTIMISATION COMBINATOIRE

L'optimisation combinatoire est le domaine des mathé- matiques discrètes qui traite de la résolution du problème suivant : Soit X un ensemble de solutions admissibles. Soit f une fonction permettant d'évaluer chaque solution admissible. Il s'agit de déterminer une solution s* appartenant à X qui minimise f. L'ensemble X des solutions admissibles est supposé fini et est en géné- ral défini par un ensemble C de contraintes. Malgré l'évolution permanente des calculateurs et les progrès fulgurants de l'informatique, il existera certai- nement toujours, pour un problème (P) difficile, une taille critique de X au-dessus de laquelle même une énu- mération partielle des solutions admissibles devient pro- hibitive. Compte tenu de ces difficultés, la plupart des spécialistes de l'optimisation combinatoire ont orienté leur recherche vers le développement de méthodes heu- ristiques. Une méthode heuristique est souvent définie comme une procédure exploitant au mieux la structure du problème considéré, dans le but de trouver une solution de qualité raisonnable en un temps de calcul aussi faible que possible (Nicholson, 1971). Bien que l'obtention d'une solution optimale ne soit pas garantie, l'utilisation d'une méthode heuristique offre de multiples avantages par rapport à une méthode exacte : MOSIM'01 - du 25 au 27 avril 2001 - Troyes (France) - La recherche d'une solution optimale peut être totale- ment inappropriée dans certaines applications pratiques en raison de la dimension du problème, de la dynami- que qui caractérise l'environnement de travail, du man- que de précision dans la récolte des données, de la dif- ficulté de formuler les contraintes en termes explicites ou de la présence d'objectifs contradictoires. - Lorsqu'elle est applicable, une méthode exacte est souvent beaucoup plus lente qu'une méthode heuristi- que, ce qui engendre des coûts informatiques supplé- mentaires et des difficultés au niveau du temps de ré- ponse. - Les principes de recherche qui sont à la base d'une méthode heuristique sont en général plus accessibles aux utilisateurs non expérimentés. Le manque de trans- parence qui caractérise certaines méthodes exactes né- cessite une intervention régulière de la part d'un spé- cialiste voire même du concepteur de la méthode. - Une méthode heuristique peut être facilement adaptée ou combinée avec d'autres types de méthodes. Cette flexibilité augmente considérablement les possibilités d'utilisation des méthodes heuristiques. Dans la suite de ce papier, trois approches fondamenta- lement différentes qui ont déjà été appliquées avec suc- cès ces dernières années sont présentées. Les principes de recherche qui en découlent sont à la base de nombreu- ses méthodes heuristiques connues telles que l'algorith- me glouton, la méthode tabou, le recuit simulé, les algo- rithmes génétiques. Très générales dans leurs concepts, ces méthodes nécessitent toutefois un effort de modélisa- tion important si l'on souhaite en tirer de bons résultats.

3. LES METAHEURISTIQUES

3.1. L'approche constructive

Les méthodes constructives produisent des solutions admissibles en partant d'une solution initiale vide et en insérant, à chaque étape, une composante dans la solution partielle courante. Cette décision n'est jamais remise en question par la suite.

Figure 1. La tournée du voyageur de commerce

Maison M C2

C1 C3 C4 C5 C6 Pour illustrer ce type de méthodes, il suffit d'imaginer un voyageur de commerce qui doit rendre visite à un en-

semble de n clients. Il peut construire sa tournée de lamanière suivante : en partant de chez lui, il va chez le

client le plus proche (disons C1). En quittant C1, il va chez le client le proche de C1 qu'il n'a pas encore ren- contré, en ainsi de suite jusqu'à qu'il ait rendu visite à tous ces clients. En quittant le dernier client (disons Cn), il rentre chez lui. Il a ainsi construit la tournée " M - C1 -

C2 - ... - Cn - M " (figure 1).

Le type de recherche qui est à la base d'une méthode constructive est représenté dans la figure 2. L'idée consiste à diminuer la taille du problème à chaque étape, ce qui revient à se restreindre à un sous-ensemble X k inclus dans X toujours plus petit. Une méthode construc- tive trouve une solution optimale lorsque chacun des sous-ensembles considérés contient au moins une solu- tion optimale s* ? X. Malheureusement, rares sont les cas où une telle condition est remplie avec certitude. La majorité des méthodes constructives sont de type "glouton". A chaque étape, la solution courante est com- plétée de la meilleure façon possible sans tenir compte de toutes les conséquences que cela entraîne au niveau du coût de la solution finale. Dans ce sens, les méthodes de type glouton sont souvent considérées comme myopes. S* X X 1 X 2 Figure 2. Exploration de X par approche constructive Les méthodes constructives se distinguent par leur rapi- dité et leur grande simplicité. On obtient en effet très rapidement une solution admissible pour un problème donné sans avoir recours à des techniques hautement sophistiquées. Le principal défaut de ces méthodes réside malheureusement dans la qualité des solutions obtenues. Le fait de vouloir opérer à tout prix le meilleur choix à chaque étape est une stratégie dont les effets peuvent être catastrophiques à long terme. D'un point de vue théori- que, l'obtention d'une solution optimale est assurée uni- quement pour les problèmes qui admettent une formula- tion en termes de matroïdes (Gondran et Minoux, 1985). Il est donc judicieux, dans le cas général, de mettre au point des procédures anticipant les effets secondaires et les conséquences futures occasionnées par les décisions prises lors de la construction d'une solution admissible.

3.2. L'approche de recherche locale

Les méthodes de recherche locale sont des algorithmes itératifs qui explorent l'espace X en se déplaçant pas à pas d'une solution à une autre. Une méthode de ce type MOSIM'01 - du 25 au 27 avril 2001 - Troyes (France) débute à partir d'une solution s 0 ? X choisie arbitraire- ment ou alors obtenue par le biais d'une méthode cons- tructive. Le passage d'une solution admissible à une autre se fait sur la base d'un ensemble de modifications élémentaires qu'il s'agit de définir de cas en cas. Une solution s' obte- nue à partir de s en appliquant une modification élémen- taire. Le voisinage N(s) d'une solution s ? X est défini comme l'ensemble des solutions admissibles atteignables depuis s en effectuant une modification élémentaire. Un tel processus d'exploration est interrompu lorsqu'un ou plusieurs critères d'arrêt sont satisfaits. Le fonction- nement d'une méthode de recherche locale est illustré de manière générale dans la figure 3. Les passages succes- sifs d'une solution à une solution voisine définissent un chemin au travers de l'espace des solutions admissibles. La modélisation d'un problème d'optimisation et le choix du voisinage doivent être effectués de telle sorte qu'il existe au moins un " chemin " entre chaque solution s ? X et une solution optimale s*. En effet, l'existence de tels chemins permet à la méthode de recherche locale d'atteindre une solution optimale à partir de n'importe quelle solution admissible. s 0 s 1 s 2 s 3 s 4 s*X

Figure 3. Exploration de X une approche

de recherche locale A titre d'exemple, le cas du voyageur de commerce, qui a obtenu une tournée initiale par une méthode construc- tive, peut essayer d'améliorer cette dernière grâce à une méthode de recherche locale. Il lui suffit de définir comme modification élémentaire la permutation de deux clients dans sa tournée (figure 4 : on rend visite d'abord à

C6, puis à C5).

La méthode de descente décrite de manière générique dans l'algorithme 1 est un exemple de méthode de re- cherche locale. Une telle méthode progresse au travers de X en choisissant à chaque étape la meilleure solution voisine de la solution courante. Ce procédé est répété aussi longtemps que la valeur de la fonction objectif diminue. La recherche s'interrompt dès lors qu'un mini- mum local de f est atteint.Historiquement, les méthodes de descente ont toujours compté parmi les méthodes heuristiques les plus populai- res pour traiter les problèmes d'optimisation combina- toire. Toutefois elles comportent deux obstacles majeurs qui limitent considérablement leur efficacité: - suivant la taille et la structure du voisinage N(s) consi- déré, la recherche de la meilleure solution voisine est un problème qui peut être aussi difficile que le problè- me (P) initial; - une méthode de descente est incapable de progresser au-delà du premier minimum local rencontré. Or les problèmes d'optimisation combinatoire comportent ty- piquement de nombreux optima locaux pour lesquels la valeur de la fonction objectif peut être fort éloignée de la valeur optimale.

Initialisation

choisir une solution admissible initiale s?X ; poser s*:=s ;

Processus itératif

quotesdbs_dbs44.pdfusesText_44