Chapitre 9 : Introduction aux methodes heuristiques

Publié par

Graphes et Recherche Operationnelle – ESIAL 2A Chapitre 9 : Introduction aux methodes heuristiques J.-F. Scheid 2011–2012 1

  • pieces rectangulaires sans chevauchement

  • pieces

  • placement optimal de pieces

  • introduction aux methodes heuristiques

  • solutions approchees

  • methode du coin nord-ouest pour l'affectation


Publié le : mardi 19 juin 2012
Lecture(s) : 81
Tags :
Source : iecn.u-nancy.fr
Nombre de pages : 19
Voir plus Voir moins
Chapitre
9
:
GraphesetRechercheOp´erationnelle – ESIAL 2A
Introduction aux methodes ´
J.-F. Scheid
2011–2012
heuristiques
1
Plan du chapitre
I. II.
heuristiques
Introduction Quelquesme´thodes 1 Algorithme A 2 RecuitSimul´e 3 Algorithmesg´en´etiques
2
uessiriqsempegle:`resquimplontpines´seesaabssrueutsqidetytionochapestdsemhtiasimitpoorlg:a
3
I. Introduction
Pourlesproble`mes de grandes tailles : pasdetempsdecalculsraisonnablesaveclesme´thodes exactes recherche de ”bonnes” solutions approch´ees .
Heuristiques l’analyse scientifique ( 6 =algorithmes).Ellessontbas´eessurlexpe´rienceet lesr´esultatsde´j`aobtenusetsurlanalogiepouroptimiserlesrecherches suivantes.G´ene´ralement,onnobtientpaslasolutionoptimalemaisune solution approch´ee .
Me´ta-heuristiques combinant plusieurs approches heuristiques.
selodnurne´tuoiablealiseng(deer):ynscouctrontial:rigopl´ementer.htemssmilpsea`mi
4
Onad´ej`tre´desme´thodes heuristiques : a rencon initialisationdubranch-and-boundpourleprobl`emedusac-a`-dos (calcul de F ) m´ethodeducoinNord-Ouestpourlaectation. Cesexemplesfontpartieduneclassedeme´thodesappele´esalgorithmes gloutons”.
Algorithme glouton seramenantaunesuitedede´cisionsquonprend`achaquefoisaumieux ` enfonctionduncrit`erelocalsansremettreenquestionlesd´ecisionsde´ja ` prises.Ge´n´eralement,lasolutionobtenueest approche´e .
Int´erˆet D´efaults :solutionsapproche´esobtenuesplusoumoinsbonnes,crit`ere local (”myopie”).
Exemple:Placementoptimaldepie`ces2D(BinPacking) .
On dispose de plaques rectangulaires toutes identiques dans lesquelles on veutplacerdespie`cesrectangulairessanschevauchement.Lespi`` eces a placerontdesdimensionsdie´rentes.
On veut trouver le placement pour minimiser le nombre de plaques utilise´es.
Algorithme glouton : trierlespie`cesenfonctiondeleurtailleetplacer dabordlespie`ceslesplusgrandes.
5
Quelquesme´thodesapproche´es
1
2
3
4
Me´thodeheuristiqueenprogrammationdynamique
Recuitsimule´
Algorithmesge´ne´tiques
Recherche Tabou, colonies de fourmis, ∙ ∙ ∙
:
Algorithme
A
6
Int´erˆetetdomainesdapplicationsdesm´ethodesheuristiques
Probl`mes d’optimisation de la forme e
min f ( x ) x X s g o(u x s)d es b contraintes
La fonction f peut-eˆtrevectorielle(optimisationmulti-objectifs)etles contraintes g sontg´ene´ralementvectorielles.
Defa¸conge´n´erale,lafonctionobjectif f et les contraintes g sont nonline´aires .
7
Pl:suealcsqisste´medohbleslesauxpossinimilacosueirums
M´ethodesm´eta-heuristiques :capacite´`asextrairedunminimum local pour aller vers un minimum global
8
parfois
Difficultes ´ doptimisationnon-lin´eaire(base´essurlecalculdi´erentiel)sont couˆteusesetincapablesdecapturerlasolution globale .
II.Quelquesm´ethodesheuristiques
1) Algorithme A Propos´eparHart,Nilsson,Raphael(1968).Ilsagitdlgorithme un a heuristique deprogrammationdynamiquequifournitg´en´eralementune solution approch´ee .Algorithmetre`sutilise´poursarapidit´e(jeuxvide´o,...)
C’est un algorithme de recherche d’un plus court chemin dans un graphe allant de x 0 `a x F .
Ilestbas´esurune ´evaluationheuristique `achaquesommetpour estimer le meilleur chemin qui y passe. Lessommetssontparcourusenfonctiondecette´evaluation heuristique:onretientlesommetou`le´valuationestlapluspetite.
9
Recherche d’un plus court chemin dans un graphe allant de x 0 `a x F .
F ( x ) : longueur du plus court chemin allant de x 0 au sommet x . L ( x ) : longueur du plus court chemin allant du sommet x `a x F .
On suppose que pour tout sommet x , on sait calculer une approximation minorante L ( x ) de la longueur minimale L ( x ) (on a donc L ( x ) L ( x )). L estunee´valuationheuristiquede L .
On construit progressivement une liste de sommets S telle que pour tout x S , la longueur F ( x )ad´eja`e´t´ecalcul´ee. Achaquee´tape,onajoute`alaliste S le sommet x tel que x 0 / S F ( x 0 ) + L ( x 0 ) φ ( x ) = F ( x ) + L ( x ) = min
On utilise les successeurs de x pour continuer Onarrˆeted`esquelesommet x F estrencontre´
10
Exemple :
Evaluation
Plus court chemin dans une grille avec obstacle
heuristique
L ( x ) :distance(`avoldoiseau)de x
.
` a x F .
11
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.