[PDF] [PDF] Chapitre 8 : Introduction aux méthodes heuristiques

View - Download [PDF] Chapitre 8 : Introduction aux méthodes heuristiques

Previous PDF

Next PDF

Graphes et RO- TELECOM Nancy 2AChapitre 8 : Introduction aux méthodes heuristiques

J.-F. Scheid

v2.1 1

Plan du chapitre

I.

Intro duction

II. Quelques métho desheuristiques 1AlgorithmeA2Recuit simulé

3Algorithmes génétiques

4Algorithme de colonies de fourmis

2

I. Introduction

Pour les problèmes

de grandes tailles

: pas de temps de calculs "raisonnables" avec les méthodesexactesrecherche de "bonnes" solutionsapprochées.Heuristiques: règles empiriques simples basées sur l"expérience (résultats

déjà obtenus) et sur l"analogie. Généralement, on n"obtient pas la solution

optimale mais une solutionapprochée.Méta-heuristiques: algorithmes d"optimisation (généralement de type

stochastique) combinant plusieurs approches heuristiques.3

I. Introduction

Pour les problèmes

de grandes tailles

: pas de temps de calculs "raisonnables" avec les méthodesexactesrecherche de "bonnes" solutionsapprochées.Heuristiques: règles empiriques simples basées sur l"expérience (résultats

déjà obtenus) et sur l"analogie. Généralement, on n"obtient pas la solution

optimale mais une solutionapprochée.Méta-heuristiques: algorithmes d"optimisation (généralement de type

stochastique) combinant plusieurs approches heuristiques.3

I. Introduction

Pour les problèmes

de grandes tailles

: pas de temps de calculs "raisonnables" avec les méthodesexactesrecherche de "bonnes" solutionsapprochées.Heuristiques: règles empiriques simples basées sur l"expérience (résultats

déjà obtenus) et sur l"analogie. Généralement, on n"obtient pas la solution

optimale mais une solutionapprochée.Méta-heuristiques: algorithmes d"optimisation (généralement de type

stochastique) combinant plusieurs approches heuristiques.3 Exemple d"heuristique: initialisation du "Branch-and-Bound" pour le

problème du sac-à-dos (calcul deF).Algorithme glouton("greedy") : construction d"une solutionréalisableen

se ramenant à une suite de décisions qu"on prend à chaque fois au mieux en fonction d"uncritère d"optimisation localsans remettre en question les décisions déjà prises. Généralement, la solution obtenue estapprochée. Intérêt: algorithmes simples à implémenter. Défaults: solutions approchées obtenues plus ou moins bonnes, critère local ("myopie").4 Exemple d"heuristique: initialisation du "Branch-and-Bound" pour le

problème du sac-à-dos (calcul deF).Algorithme glouton("greedy") : construction d"une solutionréalisableen

se ramenant à une suite de décisions qu"on prend à chaque fois au mieux en fonction d"uncritère d"optimisation localsans remettre en question les décisions déjà prises. Généralement, la solution obtenue estapprochée. Intérêt: algorithmes simples à implémenter. Défaults: solutions approchées obtenues plus ou moins bonnes, critère local ("myopie").4 Exemple : Placement optimal de pièces 2D (Bin Packing). On dispose de plaques rectangulaires toutes identiques dans lesquelles on veut placer des pièces rectangulaires sans chevauchement. Les pièces à placer ont des dimensions différentes.plaque pièces . . .=)On veut trouver le placement pour minimiser le nombre de plaques utilisées.

Algorithme glouton

: trier les pièces en fonction de leur taille et placer d"abord les pièces les plus grandes. 5

Quelques méthodes approchées

1Méthode heuristique en programmation dynamique : AlgorithmeA2Recuit simulé

3Algorithmes génétiques

4Algorithme de colonies de fourmis, recherche Tabou,6

Quelques méthodes approchées

1Méthode heuristique en programmation dynamique : AlgorithmeA2Recuit simulé

3Algorithmes génétiques

4Algorithme de colonies de fourmis, recherche Tabou,6

Intérêt et domaines d"applications des méthodes heuristiques

Problèmes d"optimisation de la forme

min x2Xf(x)sous des contraintes g(x)b La fonctionfpeut-être vectorielle (optimisation multi-objectifs) et les contraintesgsont généralement vectorielles. De façon générale, la fonction objectiffet les contraintesgsont nonlinéaires. 7 f x Difficultés: Plusieursminima locauxpossibles)les méthodes classiques d"optimisation non-linéaire (basées sur le calcul différentiel) sont parfois coûteuses et incapables de capturer la solutionglobale.

Méthodes méta-heuristiques

: capacité à s"extraire d"un minimum local pour aller vers un minimumglobal 8

II. Quelques méthodes heuristiques

1) AlgorithmeA

Proposé par Hart,Nilsson,Raphael (1968). Il s"agit d"un algorithme heuristiquede programmation dynamique qui fournit généralement une

solutionapprochée. Algorithme très utilisé pour sa rapidité (jeux vidéo, ...)C"est un algorithme de recherche d"un plus court chemin dans un graphe

allant dex0àxF.Il est basé sur uneévaluation heuristiqueà chaque sommet pour estimerle meilleur chemin qui y passe.Les sommets sont parcourus en fonction de cette évaluation heuristique : on retient le sommet où l"évaluation est la plus petite. Dans l"algorithme de Dijkstra, on effectue une recherche exhaustive parmi tous les sommets. Dans l"algorithmeA, on réduit l"ensemble des sommets

à explorer.9

II. Quelques méthodes heuristiques

1) AlgorithmeA

Proposé par Hart,Nilsson,Raphael (1968). Il s"agit d"un algorithme heuristiquede programmation dynamique qui fournit généralement une

solutionapprochée. Algorithme très utilisé pour sa rapidité (jeux vidéo, ...)C"est un algorithme de recherche d"un plus court chemin dans un graphe

allant dex0àxF.Il est basé sur uneévaluation heuristiqueà chaque sommet pour estimerle meilleur chemin qui y passe.Les sommets sont parcourus en fonction de cette évaluation heuristique : on retient le sommet où l"évaluation est la plus petite. Dans l"algorithme de Dijkstra, on effectue une recherche exhaustive parmi tous les sommets. Dans l"algorithmeA, on réduit l"ensemble des sommets

à explorer.9

Recherche d"un plus court chemin dans un graphe allant dex0àxF. F(x): longueur du plus court chemin allant dex0au sommetx. L

(x): longueur du plus court chemin allant du sommetxàxF.Pour tout sommetx, on suppose qu"on sait calculerune app roximation

minoranteL(x)de la longueur minimaleL(x)i.e.L(x)L(x).

Lest une évaluation heuristique deL.On construit progressivement une liste de sommetsStelle que pour

toutx02S, la longueurF(x0)a déjà été calculée.A chaque étape, on ajoute à une autre listeSle sommetxtel que

(x) =F(x) +L(x)= minx02SF(x0) +L(x0)On utilise les successeurs dexpour continuerOn arrête dès que le sommetxFest rencontré10

Recherche d"un plus court chemin dans un graphe allant dex0àxF. F(x): longueur du plus court chemin allant dex0au sommetx. L

(x): longueur du plus court chemin allant du sommetxàxF.Pour tout sommetx, on suppose qu"on sait calculerune app roximation

minoranteL(x)de la longueur minimaleL(x)i.e.L(x)L(x).

Lest une évaluation heuristique deL.On construit progressivement une liste de sommetsStelle que pour

toutx02S, la longueurF(x0)a déjà été calculée.A chaque étape, on ajoute à une autre listeSle sommetxtel que

(x) =F(x) +L(x)= minx02SF(x0) +L(x0)On utilise les successeurs dexpour continuerOn arrête dès que le sommetxFest rencontré10

Exemple : Plus court chemin dans une grille avec obstacle.0x FxExemple d"évaluation heuristiqueL(x): distance (à vol d"oiseau) dexàxF. 11

On construit deux listes :

Sliste ouverte: contient les sommets (successeurs)à examiner.Sliste fermée: contient tous les sommetsdéjà examinés, qui

appartiennent au chemin solution.

On commence par le sommetx=x01On regarde tous les successeurs (voisins)x0dex2Si un sommetx0n"a jamais été rencontré(i.e.x0n"est ni dans la liste

Sni dans la listeS), alors on l"ajoute dansS.3Si un sommetx0a déjà été rencontré(i.e.x0est déjà dansSou bien

dansS) et six0a un nouveau coûtplus petit, alors on met à jour le coût. De plus, six02Salors on l"enlève deSet on l"ajoute àS(pour qu"il soit à nouveau examiné).4On détermine le meilleur sommetxde toute la liste ouverteS(si

S=;alors arrêt, pas de solution).5On metxdans la liste ferméeSet on le supprime de la listeS.6On itère avec le sommet courantx(retour en 1)12

On construit deux listes :

Sliste ouverte: contient les sommets (successeurs)à examiner.Sliste fermée: contient tous les sommetsdéjà examinés, qui

appartiennent au chemin solution.

On commence par le sommetx=x01On regarde tous les successeurs (voisins)x0dex2Si un sommetx0n"a jamais été rencontré(i.e.x0n"est ni dans la liste

Sni dans la listeS), alors on l"ajoute dansS.3Si un sommetx0a déjà été rencontré(i.e.x0est déjà dansSou bien

dansS) et six0a un nouveau coûtplus petit, alors on met à jour le coût. De plus, six02Salors on l"enlève deSet on l"ajoute àS(pour qu"il soit à nouveau examiné).4On détermine le meilleur sommetxde toute la liste ouverteS(si

S=;alors arrêt, pas de solution).5On metxdans la liste ferméeSet on le supprime de la listeS.6On itère avec le sommet courantx(retour en 1)12

On construit deux listes :

Sliste ouverte: contient les sommets (successeurs)à examiner.Sliste fermée: contient tous les sommetsdéjà examinés, qui

appartiennent au chemin solution.

On commence par le sommetx=x01On regarde tous les successeurs (voisins)x0dex2Si un sommetx0n"a jamais été rencontré(i.e.x0n"est ni dans la liste

Sni dans la listeS), alors on l"ajoute dansS.3Si un sommetx0a déjà été rencontré(i.e.x0est déjà dansSou bien

dansS) et six0a un nouveau coûtplus petit, alors on met à jour le coût. De plus, six02Salors on l"enlève deSet on l"ajoute àS(pour qu"il soit à nouveau examiné).4On détermine le meilleur sommetxde toute la liste ouverteS(si

S=;alors arrêt, pas de solution).5On metxdans la liste ferméeSet on le supprime de la listeS.6On itère avec le sommet courantx(retour en 1)12

On construit deux listes :

Sliste ouverte: contient les sommets (successeurs)à examiner.Sliste fermée: contient tous les sommetsdéjà examinés, qui

appartiennent au chemin solution.

On commence par le sommetx=x01On regarde tous les successeurs (voisins)x0dex2Si un sommetx0n"a jamais été rencontré(i.e.x0n"est ni dans la liste

Sni dans la listeS), alors on l"ajoute dansS.3Si un sommetx0a déjà été rencontré(i.e.x0est déjà dansSou bien

dansS) et six0a un nouveau coûtplus petit, alors on met à jour le coût. De plus, six02Salors on l"enlève deSet on l"ajoute àS(pour qu"il soit à nouveau examiné).4On détermine le meilleur sommetxde toute la liste ouverteS(si

S=;alors arrêt, pas de solution).5On metxdans la liste ferméeSet on le supprime de la listeS.6On itère avec le sommet courantx(retour en 1)12

On construit deux listes :

Sliste ouverte: contient les sommets (successeurs)à examiner.Sliste fermée: contient tous les sommetsdéjà examinés, qui

appartiennent au chemin solution.

On commence par le sommetx=x01On regarde tous les successeurs (voisins)x0dex2Si un sommetx0n"a jamais été rencontré(i.e.x0n"est ni dans la liste

Sni dans la listeS), alors on l"ajoute dansS.3Si un sommetx0a déjà été rencontré(i.e.x0est déjà dansSou bien

dansS) et six0a un nouveau coûtplus petit, alors on met à jour le coût. De plus, six02Salors on l"enlève deSet on l"ajoute àS(pour qu"il soit à nouveau examiné).4On détermine le meilleur sommetxde toute la liste ouverteS(si

S=;alors arrêt, pas de solution).5On metxdans la liste ferméeSet on le supprime de la listeS.6On itère avec le sommet courantx(retour en 1)12

On construit deux listes :

Sliste ouverte: contient les sommets (successeurs)à examiner.Sliste fermée: contient tous les sommetsdéjà examinés, qui

appartiennent au chemin solution.

On commence par le sommetx=x01On regarde tous les successeurs (voisins)x0dex2Si un sommetx0n"a jamais été rencontré(i.e.x0n"est ni dans la liste

Sni dans la listeS), alors on l"ajoute dansS.3Si un sommetx0a déjà été rencontré(i.e.x0est déjà dansSou bien

dansS) et six0a un nouveau coûtplus petit, alors on met à jour le coût. De plus, six02Salors on l"enlève deSet on l"ajoute àS(pour qu"il soit à nouveau examiné).4On détermine le meilleur sommetxde toute la liste ouverteS(si

S=;alors arrêt, pas de solution).5On metxdans la liste ferméeSet on le supprime de la listeS.6On itère avec le sommet courantx(retour en 1)12

On construit deux listes :

Sliste ouverte: contient les sommets (successeurs)à examiner.Sliste fermée: contient tous les sommetsdéjà examinés, qui

appartiennent au chemin solution.

On commence par le sommetx=x01On regarde tous les successeurs (voisins)x0dex2Si un sommetx0n"a jamais été rencontré(i.e.x0n"est ni dans la liste

Sni dans la listeS), alors on l"ajoute dansS.3Si un sommetx0a déjà été rencontré(i.e.x0est déjà dansSou bien

dansS) et six0a un nouveau coûtplus petit, alors on met à jour le coût. De plus, six02Salors on l"enlève deSet on l"ajoute àS(pour qu"il soit à nouveau examiné).4On détermine le meilleur sommetxde toute la liste ouverteS(si

S=;alors arrêt, pas de solution).5On metxdans la liste ferméeSet on le supprime de la listeS.6On itère avec le sommet courantx(retour en 1)12

AlgorithmeAS=fx0g;S=;;F(x0) =0.

Tant queS6=;- Déterminerx2Stq(x) =F(x) +L(x) =minx02S((x0))-S=Sn fxg;S=S[ fxg- Six=xFalors arrêt (solution trouvéex)Pour toutx02Successeur(x)Six0=2S[S

S=S[ fx0gF(x0) =F(x) +l(x;x0);(x0) =F(x0) +L(x0)Sinon SiF(x) +l(x;x0) +L(x0)< (x0)F(x0) =F(x) +l(x;x0);(x0) =F(x0) +L(x0)Six02SalorsS=S[ fx0getS=Sn fx0gFin si

Fin pour

Fin tant que13

Un exemple

Recherche d"un plus court chemin dans une grille avec obstacle. Les déplacements autorisés sont horizontaux et verticaux.

Choix de l"heuristique :

L(x) =distance de Manhattan du sommetxau sommet d"arrivéexF. =nombre de déplacements horizontaux et verticaux pour aller dexàxF. 14 x 0 x

Fsommet de dŽpart

x 0 x

Fsommet dÕarrivŽeDŽplacements

horizontaux/verticaux15 x 0 x

Fsommet ˆ

examiner ( S )

1+51+31+5

!(x)=F(x)+L(x)F(x):d ist ancedex 0 `ax

L(x):d ist ancedex`ax

F sommet dŽjˆ examinŽ ( S )16 x 0 x

Fsommet ˆ

examiner ( S )

1+51+31+52+42+4

!(x)=F(x)+L(x)F(x):d ist ancedex 0 `ax

L(x):d ist ancedex`ax

F sommet dŽjˆ examinŽ ( S )17 x

0sommet ˆ

examiner ( S ) !(x)=F(x)+L(x)F(x):d ist ancedex 0 `ax

L(x):d ist ancedex`ax

F sommet dŽjˆ examinŽ ( S ) x F25

Propriétés deA

On notel(x;y)la distance dexà son successeuryetL(x)est la distance minimale dexàxF.Heuristique consistante:Lest une heuristiqueconsistantesi L(x)L(y) +l(x;y)8x;8ysuccesseur dex:Heuristique admissible:Lest une heuristiqueadmissiblesi

L(x)L(x)8x:Propriétés

SiLest admissible alors l"algorithmeAtrouvera toujours le chemin optimal.SiLest consistante alorsLest admissiblel"algorithmeAa une complexité linéaire26

2) Recuit simulé

Proposé par Kirkpatrick et co-auteurs (1983).

Méthode inspirée de la physique statistique (métallurgie). Analogie avec le processus d"alternance de refroisissement lent et de réchauffage (recuit) d"une pièce de métal afin d"obtenir un état d"énergie minimale.27 Principe du recuit simulé: Une solution réalisablex2Xreprésente, par analogie, l"état d"un système avec une certaine distribution de probabilités p. On effectue une petite variation de la solution qui entraine une variation

f(x)de l"énergie du système.Sif(x)<0 (l"énergie du système diminue) alors on accepte cette

variation (p=1).Sinon, elle est acceptée avec une probabilité p=ef(x)T (règle de Metropolis) 28

Recuit simulé

x

0solution initiale

k=0;x=x0(meilleure solution rencontrée). Choisir une suite décroissante de nombrek>0(k=1;2;)

Tant que (condition d"arrêt non vérifiée)Choisir aléatoirementyproche dexk(voisins)Calculerp=min

1;ef(y)f(xk)

kDéfinition dexk+1:x k+1=yavec probabilitépx k+1=xkavec probabilité1pSif(xk+1)Fin tant que 29

Remarques.La fonctionfn"est pas nécessairement linéaire.Sif(y)f(xk)alorsp=1)xk+1=y.En revanche, sif(y)>f(xk)alorsyn"est pas nécessairement rejeté.

pest d"autant plus faible quef(y)f(xk)est grand.Choix courant de la température :k+1=kavec <1 (=0:99).Sikn"est pas trop faible alors la probabilitéppeut être suffisamment

grande pour s"affranchir de l"attraction d"unminimum local. 30

3) Algorithme génétique

Analogie avec la génétique et l"évolution naturelle par croisement, mutation et sélection (Golberg 1989).

Principe de sélection/croisement/mutation

: faire évoluer une population de solutionsen sélectionnant les meilleures solutions à chaque étape (nouvelle génération). Evolution par croisement des solutions sélectionnées avec desmutationspossibles.Croisement: P arexemple, 2 solutions xetysous forme de codage binaire (xi,yi2 f0;1g) : x= (x1;x2;;xn)y= (y1;y2;;yn) On choisit au hasard l"indiceket on engendre 2 nouvelles solutions u= (x1;;xk1;yk;;yn)v= (y1;;yk1;xk;;xn)

Mutation

: P arexemple, changer un ou plusieurs bits au hasa rddans uetv31

3) Algorithme génétique

Analogie avec la génétique et l"évolution naturelle par croisement, mutation et sélection (Golberg 1989).

Principe de sélection/croisement/mutation

: faire évoluer une population de solutionsen sélectionnant les meilleures solutions à chaque étape (nouvelle génération). Evolution par croisement des solutions sélectionnées avec desmutationspossibles.Croisement: P arexemple, 2 solutions xetysous forme de codage binaire (xi,yi2 f0;1g) : x= (x1;x2;;xn)y= (y1;y2;;yn) On choisit au hasard l"indiceket on engendre 2 nouvelles solutions u= (x1;;xk1;yk;;yn)v= (y1;;yk1;xk;;xn)

Mutation

: P arexemple, changer un ou plusieurs bits au hasa rddans uetv31

3) Algorithme génétique

Analogie avec la génétique et l"évolution naturelle par croisement, mutation et sélection (Golberg 1989).

Principe de sélection/croisement/mutation

: faire évoluer une population de solutionsen sélectionnant les meilleures solutions à chaque étape (nouvelle génération). Evolution par croisement des solutions sélectionnées avec desmutationspossibles.Croisement: P arexemple, 2 solutions xetysous forme de codage binaire (xi,yi2 f0;1g) : x= (x1;x2;;xn)y= (y1;y2;;yn) On choisit au hasard l"indiceket on engendre 2 nouvelles solutions u= (x1;;xk1;yk;;yn)v= (y1;;yk1;xk;;xn)

Mutation

: P arexemple, changer un ou plusieurs bits au hasa rddans uetv31 Algorithme génétique (principe général) - Population initiale composée demsolutions : P

0=fx1;x2;;xmg

-k=0

Tant que (condition d"arrêt non vérifiée)- Appliquer un opérateur desélectionpour obtenir despaires de solutions de la populationPk.Paires de solutions sélectionnées :(y1;z1);;(yp;zp)-Pk+1=;.Pourjde1àp- Appliquer l"opérateur decroisementà(yj;zj)pourobtenir(yj;zj)l"ensemble des nouvelles solutions- Pour chaque solutionx2(yj;zj), appliquerl"opérateur demutationpour obtenir(x)-Pk+1=Pk+1[(x)Fin pour

k=k+1

Fin tant que32

Un exemple : Binpack 2D

Placement optimal de rectangles sur des plaques pour minimiser le nombre de plaques utilisées. 33

1Codage

Opérateurs de placement

: placement gauche/droite +: placement haut/bas Notation post-fixée (polonaise inverse) : 143+52+ 34

2Croisement hybride

Parent 1 : 1432+5+

Parent 2 : 514+32+

(a) Partie index 35

2Croisement hybride

Parent 1 : 1432+5+

Parent 2 : 514+32+

(b) Partie opérateur

Finalement, on obtient

Enfant 1 : 154+32+

Enfant 2 : 4132+5+36

3Mutations

rotation d"un rectangle permutation de 2 rectangles déplacement d"un opérateur 37
Remarques.La fonction objectiffpeut être non-linéaire.Temps de calculs souvent importants.

Difficultés de mise en oeuvre.

Fournit généralement une solution approchée.

Problèmes d"extréma locaux.

38

4) Algorithme de colonies de fourmis

Dû à M. Dorigo dans les années 90, s"inspire du comportement collectif des fourmis pour la recherche d"un plus court chemin de la fourmilière à un

point de nourriture.Après avoir trouvé la nourriture, les fourmis rentrent à la fourmilière

(par le même chemin) en déposant desphéromonesau sol.Les phéromones étant attractives, les fourmis qui partent de la

fourmilière seront guidées. 39
Si 2 chemins sont possibles pour atteindre la nourriture, le chemin le + court sera parcouru par + de fourmis.+la piste courte sera renforcée et de + en + attractive. la piste longue finira par disparaître à cause del"évaporation des phéromonesA terme, le chemin le + court sera choisi par la majorité des fourmis. 40
quotesdbs_dbs44.pdfusesText_44

[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

[PDF] module 1 aide soignante résumé

[PDF] les 8 modules aide soignante

[PDF] module 1 aide soignante contenu

[PDF] cours aide soignante gratuit

[PDF] cours aide soignante module 3