Méthodes heuristiques en Optimisation Combinatoire Table des
Ces algorithmes heuristiques fournissent donc rapidement des solutions réalisables est inspirée des méthodes d'optimisation continue.
Conception dheuristiques doptimisation pour les problèmes de
5 mars 2012 Dans un deuxième temps nous développons une méthode heuristique de sélection de variables
Chapitre 8 : Introduction aux méthodes heuristiques
Méta-heuristiques : algorithmes d'optimisation (généralement de type Méthode heuristique en programmation dynamique : Algorithme A?.
Méthodes exactes et heuristiques pour loptimisation de l
8 juin 2018 Méthodes exactes et heuristiques pour l'optimisation de l'agencement d'un logement: application aux situations de handicap. Yahya Bouzoubaa.
Méthodes approchées pour la résolution dun problème d
On dit d'une heuristique qu'elle est à la base de population si elle part/construit plusieurs solutions. Quelques heuristiques. Heuristiques. Déterministes
Les Méthodes Hybrides en Optimisation Combinatoire:Algorithmes
28 avr. 2006 2.1 – Heuristique gloutonne pour le KP. 2.2.2 Calcul de bornes supérieures et élément critique. Calculer des bornes supérieures ou inférieures ( ...
Méthodes heuristiques en Optimisation Combinatoire Table des
Ces algorithmes heuristiques fournissent donc rapidement des solutions réalisables est inspirée des méthodes d'optimisation continue.
Les méthodes doptimisation appliquées à la conception de
Dans le milieu de la conception l'optimisation est le fait d'optimiser une fonction. Une méthode heuristique est dite «efficace» si
Modèles et méthodes doptimisation combinatoire pour la
28 mai 2015 2.4.1 Programmation DC et algorithme DCA pour l'optimisation continue . ... méthodes heuristiques basées respectivement sur la relaxation ...
Cours des Méthodes de Résolution Exactes Heuristiques et
En optimisation combinatoire une heuristique est un algorithme ap- proché qui permet d'identifier en temps polynomial au moins une solution réalisable rapide
[PDF] Méthodes exactes et heuristiques pour loptimisation - HAL Thèses
8 jui 2018 · Méthodes exactes et heuristiques pour l'optimisation de l'agencement d'un logement: application aux situations de handicap Yahya Bouzoubaa
[PDF] Cours des Méthodes de Résolution Exactes Heuristiques et
En optimisation combinatoire une heuristique est un algorithme ap- proché qui permet d'identifier en temps polynomial au moins une solution réalisable rapide
[PDF] Techniques doptimisation 431 Métaheuristiques
Heuristique = méthode empirique spécialisée à un problème particulier Métaheuristique = principe général applicable à différents problèmes
[PDF] Chapitre 8 : Introduction aux méthodes heuristiques
Méta-heuristiques : algorithmes d'optimisation (généralement de type Méthode heuristique en programmation dynamique : Algorithme A?
[PDF] HEURISTIQUES DOPTIMISATION
Méthodes de voisinage (une solution courante) : heuristiques classiques métaheuristiques de voisinage : recuit simulé recherche tabou Méthodes à base de
[PDF] Méthode heuristique doptimisation pour la planification à long terme
De plus la prochaine génération de réseau cellulaire la 5G avec ses ondes millimétriques entrainera une prolifération des sites d'antennes à courte portée
[PDF] Les méthodes doptimisation appliquées à la conception de
Quelques algorithmes d'optimisation • Méthodes heuristiques ou approchées (1) – Recherchent à moindre coût une solution dont il n'est pas possible
[PDF] Méthodes doptimisation combinatoire en programmation
23 sept 2019 · 3 Réglage automatique des paramètres des méthodes d'optimisation 1/ Algorithme glouton 2/ heuristique basée sur la relaxation
[PDF] Méthodes exactes et approchées pour loptimisation des systèmes à
Les premiers travaux ont fourni des heuristiques assez simples construisant une seule solution et des bornes inférieures basées sur des modèles de graphes ([
[PDF] Méthodes heuristiques en Optimisation Combinatoire - LIP6
Ensuite suivant la façon de choisir une solution dan le voisinage on obtient différentes méthodes de recherche locale : méthode tabou descente pure
Quelles sont les méthodes d'optimisation ?
La méthode heuristique repose sur une évaluation quasi continue, principalement formative. L'acquisition des notions est évaluée lors des observations de l'enseignant. L'évaluation s'appuie sur des critères explicites et partagés avec les élèves.C'est quoi la méthode heuristique ?
Cet algorithme utilise une heuristique qui calcule pour chaque nœud n le coût chemin g(n) depuis l`état initial jusqu'au nœud n. Le coût chemin g(n) est une fonction croissante le long d`un chemin : chacune n dans E, s dans Successeurs(n), g(n) <= g(s).Comment calculer l'heuristique ?
Une métaheuristique peut être adaptée pour différents types de problèmes, tandis qu'une heuristique est utilisée à un problème donné.
J.-F. Scheid
v2.1 1Plan du chapitre
I.Intro duction
II. Quelques métho desheuristiques 1AlgorithmeA2Recuit simulé3Algorithmes génétiques
4Algorithme de colonies de fourmis
2I. 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 solutionoptimale mais une solutionapprochée.Méta-heuristiques: algorithmes d"optimisation (généralement de type
stochastique) combinant plusieurs approches heuristiques.3I. 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 solutionoptimale mais une solutionapprochée.Méta-heuristiques: algorithmes d"optimisation (généralement de type
stochastique) combinant plusieurs approches heuristiques.3I. 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 solutionoptimale 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 leproblè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 leproblè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. 5Quelques 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 heuristiquesProblè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 8II. 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 unesolutionapproché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 unesolutionapproché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. 11On 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(siS=;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(siS=;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(siS=;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(siS=;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(siS=;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(siS=;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(siS=;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 xFsommet de dŽpart
x 0 xFsommet dÕarrivŽeDŽplacements
horizontaux/verticaux15 x 0 xFsommet ˆ
examiner ( S )1+51+31+5
!(x)=F(x)+L(x)F(x):d ist ancedex 0 `axL(x):d ist ancedex`ax
F sommet dŽjˆ examinŽ ( S )16 x 0 xFsommet ˆ
examiner ( S )1+51+31+52+42+4
!(x)=F(x)+L(x)F(x):d ist ancedex 0 `axL(x):d ist ancedex`ax
F sommet dŽjˆ examinŽ ( S )17 x0sommet ˆ
examiner ( S ) !(x)=F(x)+L(x)F(x):d ist ancedex 0 `axL(x):d ist ancedex`ax
F sommet dŽjˆ examinŽ ( S ) x F25Proprié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 heuristiqueadmissiblesiL(x)L(x)8x:Propriétés
SiLest admissible alors l"algorithmeAtrouvera toujours le chemin optimal.SiLest consistante alorsLest admissiblel"algorithmeAa une complexité linéaire262) 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 variationf(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) 28Recuit simulé
x0solution 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)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. 303) 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 uetv313) 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 uetv313) 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 : P0=fx1;x2;;xmg
-k=0Tant 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+1Fin tant que32
Un exemple : Binpack 2D
Placement optimal de rectangles sur des plaques pour minimiser le nombre de plaques utilisées. 331Codage
Opérateurs de placement
: placement gauche/droite +: placement haut/bas Notation post-fixée (polonaise inverse) : 143+52+ 342Croisement hybride
Parent 1 : 1432+5+
Parent 2 : 514+32+
(a) Partie index 352Croisement hybride
Parent 1 : 1432+5+
Parent 2 : 514+32+
(b) Partie opérateurFinalement, 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 37Remarques.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.
384) 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 à unpoint 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. 39Si 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] 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