Metaheuristique et Optimisation :
Fondements
Objectifs du cours
Cette leçon va vous aider à :
Comprendre l’optimisation exacte et approchée
Différences entre Heuristique et Metaheuristique
Comprendre le concept des problèmes NP-Hard
Connaître les différentes catégories d’optimisation
Systèmes d’information
Le Plan du cours :
Introduction
Les catégories d’optimisation
Les méthodes d’optimisation
Le concept d’heuristique et metaheuristique
Analyse de performance
Systèmes d’information
Définition :
Heuristique :?
l'art de découvrir de nouvelles stratégies (règles) pour
résoudre des problèmes
Metaheuristique :?
Le suffixe méta, également un mot grec, signifie :
méthodologie de niveau supérieur
Le terme métaheuristique a été introduit par F. Glover
Les méthodes de recherche métaheuristiques peuvent être définies
comme des méthodologies générales (modèles) qui peuvent être
utilisées comme stratégies d'orientation dans la conception
d'heuristiques sous-jacentes pour résoudre des problèmes
d'optimisation.
Systèmes d’information
Définition :
Métaheuristiques…
peut résoudre à la fois les problèmes
d’optimisation de domaines discrets et continus
sont des stratégies qui « guident » le
processus de recherche
vont des simples procédures de recherche
locale aux processus complexes
d’apprentissage adaptatif
Définition :
Métaheuristiques…
explorer efficacement l’espace de recherche afin de trouver les bons
solutions réalisables (presque optimales)
ne fournissent aucune garantie d’optimalité globale ou locale
sont agnostiques par rapport à l’espace des possibles inexploré (c’est
àdire, aucune information « liée »)
il manque une métrique de « qualité » de la solution (souvent arrêtée
en raison de une limite de temps ou d'itération externe)
ne sont pas basés sur un modèle algébrique
Systèmes d’information
Définition :
Considérons le problème de trouver la
meilleure
séquence de visite (itinéraire) pour servir 14
clients.
Combien d'itinéraires possibles ?
– 14!= 8,7178 X 1010 = 88 milliards solutions
– Si un PC peut vérifier environ 1 million de solutions
par seconde, alors nous avons besoin de 8,8*1010
routes /106 routes/s = 88.000 sec ou environ 24,44
heures pour toutes les vérifier et trouver la
meilleure !
Définition : NP Hard Problem
13509 villes avec
299400
Systèmes d’information
Définition :
Systèmes d’information
Définition :
Systèmes d’information
CLASSEMENT
#5
Trajectoire Basé sur la population
(S-métaheuristiques) (P-métaheuristiques)
MÉTHODES DE TRAJECTOIRE
MÉTHODES DE TRAJECTOIRE
C(s0 )
s0
MÉTHODES DE TRAJECTOIRE
C(s0 )
s0
s1
C(s1 )
MÉTHODES DE TRAJECTOIRE
C(s0 )
s0
s1
C(s1 )
s2
C(s2 )
Arrêt car aucune amélioration
dans la région C(s2 )
MÉTHODES DE TRAJECTOIRE
C(s0 )
s0
s1
C(s1 )
s2
C(s2 )
Il s'avère qu'il y a deux optima globaux
dans ce problème, mais aucun n'a été
identifié. • Un a été manqué lors de la
recherche de région
C(s1 )
MÉTHODES BASÉES SUR LA
POPULATION
MÉTHODES BASÉES SUR LA
POPULATION 0 ème population
MÉTHODES BASÉES SUR LA
POPULATION Obtenez de nouveaux points
MÉTHODES BASÉES SUR LA
POPULATION
Abandonnez quelques vieux
points
MÉTHODES BASÉES SUR LA
POPULATION
1ère
population _
MÉTHODES BASÉES SUR LA
POPULATION
2 ème population
MÉTHODES BASÉES SUR LA
POPULATION
Tous les points échantillonnés
Encore une fois, l'optimum peut avoir ou non été
échantillonné
En règle générale, le titulaire du poste reste
toujours dans la population, il suffit donc de se
concentrer uniquement sur la dernière
CLASSEMENT
#5
Trajectoire
(Smétaheuristiques)
Recuit simulé (1983)
Recherche tabou (1986)
Recherche locale guidée
(1997)
Recherche locale itérée (1999)
RECHERCHE LOCALE DE BASE
Amélioration itérative
1 Quarti
2 er
dix
0 12 4 567 9 10 11 12 13 14
3 8 15
Améliorer() peut être implémenté en tant que « première amélioration » ou « meilleure amélioration » ou quoi que
ce soit entre les deux.
RECHERCHE LOCALE DE BASE
Amélioration itérative
1 Quar
2 tier
d
i
x
0
12 4 5678 9 10 11 12 13
3 14 15
RECHERCHE LOCALE GUIDÉE
Au lieu de modifier dynamiquement la
recherche directions, GLS change (augmente)
dynamiquement l'objectif
L'idée principale est de rapprocher la solution
actuelle de moins en moins attrayant
1
4
1
2
dix
1 2 3 5 6 7 8 9 dix 1
2
4 11 2
0
RECHERCHE LOCALE GUIDÉE
Au lieu de modifier dynamiquement la
recherche directions, GLS change (augmente)
dynamiquement l'objectif
L'idée principale est de rapprocher la solution
actuelle de moins en moins attrayant (
, )= ( 1
) +
toute fonctionnalité
de solution
(par exemple, un
composant
de solution
particulier)
′ ( )= ( )+ (
∑ )
=1 est présente
, si la fonctionnalité
dans
( )={ 1,
dont
0solution
MÉTHODES BASÉES SUR LA
POPULATION
MÉTHODES BASÉES SUR LA
POPULATION
0 ème
population
MÉTHODES BASÉES SUR LA
POPULATION
Obtenez de nouveaux
points
MÉTHODES BASÉES SUR LA
POPULATION
Abandonnez quelques vieux
points
MÉTHODES BASÉES SUR LA
POPULATION
1ère
population _
MÉTHODES BASÉES SUR LA
POPULATION
2 ème
population
MÉTHODES BASÉES SUR LA
POPULATION
Tous les points
échantillonnés
Encore une fois, l'optimum peut avoir ou non été
échantillonné
En règle générale, le titulaire du poste reste
toujours dans la population, il suffit donc de se
concentrer uniquement sur la dernière
CLASSEMENT
#5
Basé sur la Calcul évolutif
population (P Programmation évolutive
métaheuristiques) (1962)
Stratégies évolutives (1973)
Algorithmes génétiques (1975)
Estimation de la distribution
Algorithme (1996)
Intelligence en essaim
Optimisation des colonies de
fourmis (1992)
Optimisation des essaims de
particules (1995)
Accouplement des abeilles
(2005)
Évolution différentielle (1995)
CALCUL
ÉVOLUTIONNAIRE
Les populations évoluent en « générations »
• De nouveaux individus (progéniture) sont créés en combinant
les caractéristiques des individus actuels (parents) ;
– généralement, deux parents s'associent pour donner une
progéniture
• Les individus évoluent à l'aide d'opérateurs de variation (par
exemple,
« mutation », « recombinaison ») agissant
directement sur leurs représentations solutions
• La population suivante est composée d'un mélange de
CALCUL
ÉVOLUTIONNAIRE
CALCUL
ÉVOLUTIONNAIRE
CALCUL
ÉVOLUTIONNAIRE
La taille de la population est (presque toujours) fixe
La sélection peut impliquer plusieurs copies d'un parent donné.
individuel
Le meilleur individu est (presque toujours) transmis à la
génération suivante
Le hasard joue un rôle important dans la génération de la
progéniture (contrairement à d'autres méthodes nonEC)
Les solutions sont souvent représentées sous une forme compacte et
« facilement modifiable », par exemple des chaînes de bits ou des
permutations d'e
CALCUL
ÉVOLUTIONNAIRE
0 ème
population
1
2
di
x
0
1 2 3 4 5 6 7 8 9 11 12 13 14 15 16
10 17 18
CALCUL
ÉVOLUTIONNAIRE
Nième
population
1
2
di
x
0
1 2 3 4 5 6 7 8 9 11 12 13 14 15 16
10 17 18
ALGORITHME GÉNÉTIQUE
Algorithme de calcul évolutif de base –
Représentation des individus en code
binaire (par exemple, « 01101 » = 13, «
11010 » = 26)
Utilisation de l’opérateur de recombinaison «
crossover »
Mutation par « bitflipping »
La progéniture survit toujours
EXEMPLE
Population initiale pour le
TSP
(5,3,4,6,2 (2,4,6,3,5 (4,3,6,5,2
) ) )
(2,3,4,6,5 (4,3,6,2,5 (3,4,5,2,6
) ) )
(3,5,4,6,2 (4,5,3,6,2 (5,4,2,3,6
) ) )
(4,6,3,2,5 (3,4,2,6,5 (3,6,5,1,4
) ) )
Sélectionnez les
parents
(5,3,4,6,2) (2,4,6,3,5) (4,3,6,5,2)
(2,3,4,6,5) (4,3,6,2,5) (3,4,5,2,6)
(3,5,4,6,2) (4,5,3,6,2) (5,4,2,3,6)
(4,6,3,2,5) (3,4,2,6,5) (3,6,5,1,4)
Essayez de choisir les
meilleurs.
Créer une progéniture – 1
point
(5,3,4,6,2 (2,4,6,3,5 (4,3,6,5,2
) ) )
(2,3,4,6,5 (4,3,6,2,5 (3,4,5,2,6
) ) )
(3,5,4,6,2 (4,5,3,6,2 (5,4,2,3,6
) ) )
(4,6,3,2,5 (3,4,2,6,5 (3,6,5,1,4
) ) )
(3,4,5,6,
2)
Créer plus de
progéniture
(5,3,4,6,2 (2,4,6,3,5 (4,3,6,5,2
) ) )
(2,3,4,6,5 (4,3,6,2,5 (3,4,5,2,6
) ) )
(3,5,4,6,2 (4,5,3,6,2 (5,4,2,3,6
) ) )
(4,6,3,2,5 (3,4,2,6,5 (3,6,5,1,4
) ) )
(3,4,5,6, (5,4,2,6,
2) 3)
Subir une
mutation
(5,3,4,6,2 (2,4,6,3,5 (4,3,6,5,2
) ) )
(2,3,4,6,5 (4,3,6,2,5 (3,4,5,2,6
) ) )
(3,5,4,6,2 (4,5,3,6,2 (5,4,2,3,6
) ) )
(4,6,3,2,5 (3,4,2,6,5 (3,6,5,1,4
) ) )
(3,4,5,6, (5,4,2,6,
2) 3)
Subir une
mutation
(5,3,4,6,2 (2,4,6,3,5 (4,3,6,5,2
) ) )
(2,3,4,6,5 (2,3,6,4,5 (3,4,5,2,6
) ) )
(3,5,4,6,2 (4,5,3,6,2 (5,4,2,3,6
) ) )
(4,6,3,2,5 (3,4,2,6,5 (3,6,5,1,4
) ) )
(3,4,5,6, (5,4,2,6,
2) 3)
Éliminer
(5,3,4,6,2) (2,4,6,3,5) (4,3,6,5,2)
(2,3,4,6,5) (2,3,6,4,5) (3,4,5,2,6)
(3,5,4,6,2) (4,5,3,6,2) (5,4,2,3,6)
(4,6,3,2,5) (3,4,2,6,5) (3,6,5,1,4)
(3,4,5,6,2)
(5,4,2,6,3)
On a tendance à tuer les
Intégrer
(5,3,4,6,2 (2,4,6,3,5 (5,4,2,6,3
) ) )
(3,4,5,6,2 (2,3,6,4,5 (3,4,5,2,6
) ) )
(3,5,4,6,2 (4,5,3,6,2 (5,4,2,3,6
) ) )
(4,6,3,2,5 (3,4,2,6,5 (3,6,5,1,4
) ) )
Redémarrage
(5,3,4,6,2 (2,4,6,3,5 (5,4,2,6,3
) ) )
(3,4,5,6,2 (2,3,6,4,5 (3,4,5,2,6
) ) )
(3,5,4,6,2 (4,5,3,6,2 (5,4,2,3,6
) ) )
(4,6,3,2,5 (3,4,2,6,5 (3,6,5,1,4
) ) )
Pause-réflexion
Avez-vous des questions ?
53
