Une métaheuristique est un algorithme d'optimisation visant à résoudre des problèmes d'opti- misation On peut modifier les poids wi au cours de l' algorithme
Les métaheuristiques représentent alors une alternative intéressante pour trouver une solution de qualité acceptable dans des délais très courts Toutefois, il est
LAboratoire de Mathématiques, Informatique et Applications (LAMIA)
Université des Antilles et de la Guyane
Campus de Fouillole, Guadeloupe
13 février 2019
Introduction
Problèmes
d"optimisa- tion et
Métaheuris-
tiques
Algorithmes
évolution-
naires
Optimisation
multi-
Objectifs2/33
Plan1Introduction2Problèmes d"optimisation et Métaheuristiques3Algorithmes évolutionnaires4Optimisation multi-Objectifs
Introduction
Problèmes
d"optimisa- tion et
Métaheuris-
tiquesProblèmes d"optimisation
Heuristiques
Métaheuristiques
Algorithmes
évolution-
naires
Optimisation
multi-
Objectifs3/33
Problèmes d"optimisationCouple(S;f)
S: Espace de recherche
f:S!Y 8s2S; f(s0)>f(s)(respf(s0)Introduction
Problèmes
d"optimisa- tion et
Métaheuris-
tiquesProblèmes d"optimisation
Heuristiques
Métaheuristiques
Algorithmes
évolution-
naires
Optimisation
multi-
Objectifs4/33
Méthodes de résolution
Différents types de méthodes de résolution I
Méthodes exactes
Trouvent toujours la meilleure solution.
Exemple : Parcours exhaustif de l"espace de recherche. I
Méthodes approchées
Explorent un sous-ensemble de l"espace de recherche.
Se rapprochent de la solution optimale.
I
Méthodes déterministes
Exécutent toujours la même suite d"opérations I
Méthodes stochastiques
Guidées par des choix probabilistes (tirages aléatoires)
Introduction
Problèmes
d"optimisa- tion et
Métaheuris-
tiquesProblèmes d"optimisation
Heuristiques
Métaheuristiques
Algorithmes
évolution-
naires
Optimisation
multi-
Objectifs5/33
Méthodes de résolution
Introduction
Problèmes
d"optimisa- tion et
Métaheuris-
tiques
Problèmesd"optimisationHeuristiques
Métaheuristiques
Algorithmes
évolution-
naires
Optimisation
multi-
Objectifs6/33
Heuristiques
Heuristiques
I
Grec ancien :eurisko, je trouve
I
Méthodes approchées
I Stratégie : Connaissance du problème considéré I
Bon sens
I
Réduction de la complexité : Polynomial
Introduction
Problèmes
d"optimisa- tion et
Métaheuris-
tiques
Problèmesd"optimisation
HeuristiquesMétaheuristiques
Algorithmes
évolution-
naires
Optimisation
multi-
Objectifs7/33
Métaheuristiques
I
Méthodes approchées
I meta: a un niveau supérieur, non spécifiques à un problème particulier I
Guident la recherche de solutions optimales
I
Exploration efficace de l"espace de recherche
I
Métaphores/Bio-inspiration
I Mécanismes d"intensification/diversification (extraction des optimums locaux)1Solution unique :
Recherche tabou
Recuit simulé
GRASP 2
P opulationde solutions
Algorithmes évolutionnaires
Algorithmes de colonies de
fourmis
Optimisation par essaims
particulaires
Introduction
Problèmes
d"optimisa- tion et
Métaheuris-
tiques
Problèmesd"optimisation
HeuristiquesMétaheuristiques
Algorithmes
évolution-
naires
Optimisation
multi-
Objectifs8/33
Méthodes à solution unique
Recuit simulé(Kirkpatrick et al., 1983)
I Simulation du processus de refroidissement d"un métal I Température T : probabilité choix voisin x" de x selon f(x") (fonction objectif)
P(E;T) =ef(x0)f(x)T
I
Schéma de refroidissement par palliers
Introduction
Problèmes
d"optimisa- tion et
Métaheuris-
tiques
Problèmesd"optimisation
HeuristiquesMétaheuristiques
Algorithmes
évolution-
naires
Optimisation
multi-
Objectifs9/33
Méthodes à population de solutions
Algorithmes de colonies de fourmis(Dorigo et al., 1991)I
Initialement proposé pour le
TSP I
Problèmes à solutions
partielles (construction) I
Phéromones : Renforcement
des solutions optimales I
Paramètres :;,
évaporation de la piste
Introduction
Problèmes
d"optimisa- tion et
Métaheuris-
tiquesAlgorithmes
évolution-
naires
Exemples
d"utilisation
Métaheuristiques
enclassificationsupervisée
Optimisation
multi-
Objectifs10/33
Méthodes à population de solutions
Algorithmes évolutionnaires:I
J. Holland 1975 :
travaux sur les mécanismes d"auto adaptativité I
Evolution naturelle :survie du plus adapté
brassage génétique mutations I
Evaluation
=Fonction objectif =Fitness I
Largement utilisés depuis
(Goldberg 1989)
Introduction
Problèmes
d"optimisa- tion et
Métaheuris-
tiquesAlgorithmes
évolution-
naires
Exemples
d"utilisation
Métaheuristiques
enclassificationsupervisée
Optimisation
multi-
Objectifs11/33
Algorithmes évolutionnaires : représentation et variationReprésentation I
Caractérisation d"une solution sous une
forme appréhendable par l"AG I
Complète : toute solution doit etre
représentable I problem dependant I
Exemples : chaines binaires, tableau
d"entiers, ensembles de var,...
Opérateurs de variation
I
Faire varier la population en créant de
nouveaux individus à partir des existants I problem dependant (representation) I doivent générer des individus viables I Opérateurs de diversificationCroisement (crossover) I
Recombinaison de l"information
génétique, hérédité I
2 parents!2 enfants
I stratégiequotesdbs_dbs16.pdfusesText_22
×
if you Get No preview available Click on (Next PDF) Next PDF
[PDF] Métaheuristiques - GERAD