CHAPITRE IV: HEURISTIQUES
ET MÉTA-HEURISTIQUES
Université Blida 1Faculté des Sciences
Département d’InformatiqueMaster GSI (Génie des Systèmes Informatiques)
Semestre 1
Mme AROUSSI
2015-2016
Disponible sur https://sites.google.com/a/esi.dz/s-aroussi/
Problèmes d’Optimisation Combinatoire
Classification des Méthodes de Résolution
Méthodes Exactes Méthode de séparation et d’évaluation
Méthodes Approchées Méthodes par construction (algorithme de glouton)
Méthodes de voisinage (recuit simulé & recherche taboue)2
PLAN DU CHAPITRE IV
3
On qualifié généralement de « combinatoires » les
problèmes dont la résolution se ramène à l'examen d'un
nombre fini de combinaisons (appelée aussi solutions).
Bien souvent cette résolution se heurte à une explosion
du nombre de combinaisons à explorer.
En mathématique, l’optimisation combinatoire recouvre
toutes les méthodes qui permettent de déterminer
l’optimum d’une fonction avec ou sans contraintes.
PROBLÈME D’OPTIMISATION COMBINATOIRE
4
Un Problème d‘Optimisation Combinatoire (POC) peut être définie
comme suit:
Un ensemble de combinaisons ou de solutions X,
Un ensemble de contraintes C (éventuellement vide)
Un sous-ensemble S de X représentant les solutions admissibles (ou
réalisables) qui vérifient les contraintes C
Une fonction de coût f (fonction objectif) qui assigne à chaque
solution s S une valeur f(s).
Il s’agit de trouver une solution optimale (ou optimum global) s* S
qui optimise (minimise ou maximise) la fonction de coût f
PROBLÈME D’OPTIMISATION COMBINATOIRE
5
Soit « Dist » une fonction qui mesure la distance entre deux
solutions: Dist: S x S R (e.g. Distance euclidienne,
Manhattan, Hamming) . La notion de voisinage est définie par
rapport à une distance N(si) = {sk ∈ S / Dist(si,sk) ≤ ε}
Une solution s∈S est un minimum local relativement à la
structure de voisinage N si f(s)≤f(s’) pour tout s’∈N(s).
Une solution s∈S est un minimum global si f(s)≤f(s’) pour
tout s’∈S.
PROBLÈME D’OPTIMISATION COMBINATOIRE
6
PROBLÈME D’OPTIMISATION COMBINATOIRE
S2: Optimum global
S0: Solution de départ
S1: Optimum local
S: Solutions réalisables
F: fonction objectif
7
PROBLÈME D’OPTIMISATION COMBINATOIRE
Résoudre un problème d’optimisation combinatoire nécessite
l’étude des points suivants:
1. Définir l’ensemble des solutions « X »
2. Exprimer l’ensemble des contraintes du problème « C »
afin de définir l’ensemble des solutions réalisables « S »,
3. Exprimer la fonction objectif « f » à optimiser,
4. Choisir la méthode de résolution à utiliser,
Les trois premiers points relèvent de la modélisation du
problème, le dernier point de sa résolution.
8
PROBLÈME D’OPTIMISATION COMBINATOIRE
A chaque problème d'optimisation, on peut associer un
problème de décision dont le but est de déterminer s'il existe
une solution pour laquelle la fonction objectif soit inférieure
(resp. supérieure) ou égale à une valeur donnée.
La complexité d'un problème d'optimisation est liée à celle du
problème de décision qui lui est associé. En particulier, si le
problème de décision est NP-complet, alors le problème
d'optimisation est dit NP-difficile.
9
CLASSIFICATION DES MÉTHODES DE RÉSOLUTION
La majorité des problèmes d'optimisation combinatoire, sont des
problèmes NP-difficiles et donc ils ne possèdent pas à ce jour un
algorithme efficace, i.e. de complexité polynomiale, valable de trouver la
solution optimale en un temps raisonnable.
Ceci a motivé les chercheurs à développer de nombreuses méthodes de
résolution en recherche opérationnelle et en intelligence artificielle:
La recherche s’est d'abord orientée vers des heuristiques spécifiques
aux problèmes,
elle s’est progressivement intéressée aux méthodes plus générales,
c'est à dire les méta-heuristiques.
10
CLASSIFICATION DES MÉTHODES DE RÉSOLUTION
Ces méthodes de résolution peuvent être réparties en deux
grandes classes:
Méthodes exactes (complètes): Elles se basent
généralement sur une recherche complètes de l’espace des
combinaisons afin de trouver une solution optimale.
Méthodes approchées (incomplètes): Elles permettent
de trouver une bonne solution (pas forcément optimale)
dans un temps raisonnable.
11
CLASSIFICATION DES MÉTHODES DE RÉSOLUTION
Méthodes Exactes
Méthodes de séparation et d’évaluation
Méthode avec retour en arrière
Programmation dynamique
Programmation linéaire
Méthodes Approchées
Heuristiques
Méta-heuristiques
12
MÉTHODES EXACTES
Le principe des méthodes exactes consiste
généralement à énumérer, souvent de manière
implicite, l'ensemble des solutions dans le but de
trouver la solution optimale:
Avantage: Certitude de trouver la solution optimale.
Inconvénient: Temps d’exécution prohibitif.
13
MÉTHODES EXACTES
Les algorithmes exacts les plus réussis dans
la littérature appartiennent aux quatre
paradigmes :
Méthodes de séparation et d’évaluation
Méthodes avec retour arrière
Programmation dynamique
Programmation linaire
14
MÉTHODES EXACTESMÉTHODES DE SÉPARATION ET D’ÉVALUATION
L’algorithme de séparation et évaluation, plus connu sous son
appellation anglaise Branch and Bound (B&B), repose sur une
méthode arborescente de recherche d’une solution optimale par
séparations et évaluations, en représentant les états solutions
par un arbre d’états, avec des nœuds, et des feuilles.
Le branch-and-bound est basé sur trois axes principaux :
1. L’évaluation,
2. La séparation,
3. La stratégie de parcours.
15
MÉTHODES EXACTESMÉTHODES DE SÉPARATION ET D’ÉVALUATION
1. L’évaluation permet de réduire l’espace de recherche en éliminant
quelques sous ensembles qui ne contiennent pas la solution
optimale.
Exemple d’un POC cas de minimisation: Le B&B utilise une
élimination de branches dans l’arborescence de recherche de la manière
suivante : mémoriser la solution de plus bas coût rencontré pendant
l’exploration, et à comparer le coût de chaque nœud parcouru à celui de
la meilleure solution. Si le coût du nœud considéré est supérieur au
meilleur coût, on arrête l’exploration de la branche et toutes les
solutions de cette branche seront nécessairement de coût plus élevé que
la meilleure solution déjà trouvée.
16
MÉTHODES EXACTESMÉTHODES DE SÉPARATION ET D’ÉVALUATION
2. La séparation consiste à diviser le problème en
sous-problèmes. Ainsi, en résolvant tous les sous-
problèmes et en gardant la meilleure solution
trouvée, on est assuré d’avoir résolu le problème
initial. Cela revient à construire un arbre
permettant d’énumérer toutes les solutions.
17
MÉTHODES EXACTESMÉTHODES DE SÉPARATION ET D’ÉVALUATION
3. La stratégie de parcours. Il existe trois parcours
possible de l’arbre:
a. La profondeur d’abord: Cette stratégie avantage les sommets les plus éloignés de la
racine en appliquant plus de séparations au problème initial. Cette voie mène rapidement
à une solution optimale en économisant la mémoire,
b. Le meilleur d’abord: Cette stratégie consiste à explorer des sous-problèmes
possédant la meilleure borne. Elle permet aussi d’éviter l’exploration de tous les sous-
problèmes qui possèdent une mauvaise évaluation par rapport à la valeur optimale.
c. La largeur d’abord: Cette stratégie favorise les sommets les plus proches de la racine
en faisant moins de séparations du problème initial. Elle est moins efficace que les deux
autres stratégies présentées,
18
MÉTHODES APPROCHÉES
Les méthodes approchées ont pour but de trouver une solution
admissible en un temps raisonnable, mais sans garantie
l’optimalité de cette solution. L’avantage principale de ces
méthodes est qu'elles peuvent s'appliquer à n'importe quelle
classe de problèmes, faciles ou très difficiles. De plus, elles ont
démontré leurs robustesses et efficacités face à plusieurs
problèmes d’optimisation combinatoires.
Elles englobent deux classes : Heuristiques & Méta-
heuristiques
19
MÉTHODES APPROCHÉESHEURISTIQUES
Les heuristiques sont des règles empiriques simples
basées sur l'expérience, ne fournissant pas
nécessairement une solution optimale.
Exemple: Heuristiques de Choix de Variables du
problème Max-Sat
Du fait de la relation forte entre l’ordre d’affectation des variables et la taille de
l’arbre de recherche développé, une « bonne » heuristique de branchement est
déterminante pour l’efficacité d’un algorithme de recherche. Parmi ces
heuristiques:
20
MÉTHODES APPROCHÉESHEURISTIQUES
Exemple: Heuristiques de Choix de Variables du
problème Max-Sat
1. L’heuristique MOMS (Maximum Occurrences in Clauses of Minimum Size)
est l’une des heuristiques les plus simples. Elle sélectionne la variable
ayant le plus d’occurrences dans les clauses les plus courtes. Ce choix se
justifie par le fait qu’elle favorise la propagation des littéraux unitaires.
2. L’heuristique JW (Jeroslow-Wang) est basée également sur la longueur des
clauses. Elle donne aussi plus de poids aux variables apparaissant dans les
clauses les plus courtes.
21
MÉTHODES APPROCHÉESHEURISTIQUES
Exemple: Heuristiques de Choix de Variables du
problème Max-Sat
3. L’heuristique UP ( Unit Propagation) permet de sélectionner une variable
en prévoyant à l’avance son influence sur le processus de la recherche,
contrairement aux heuristiques MOMS et JW qui sélectionnent une
variable en fonction de l’état courant du processus de recherche. Cette
étude de l’influence de la variable est calculée via la procédure de
propagation unitaire ce qui permet d’estimer son poids. La variable ayant
le poids le plus fort est sélectionnée.
22
MÉTHODES APPROCHÉESMÉTA-HEURISTIQUES
Le mot Méta-Heuristique est dérivé de la composition de
deux mots grecs:
heuristique qui vient du verbe heuriskein (ευρισκειν) et qui
signifie ‘trouver’
meta qui est un suffixe signifiant ‘au-delà’, ‘dans un niveau
supérieur’.
23
MÉTHODES APPROCHÉESMÉTA-HEURISTIQUES
Une Méta-heuristique peut être définie comme une
méthode algorithmique capable de guider et d’orienter le
processus de recherche dans un espace de solution
(souvent très grand) à des régions riches en solutions
optimales dans le but de trouver des solutions, peut-être
pas toujours optimales, en tout cas très proches de
l’optimum, en un temps raisonnable.
24
MÉTHODES APPROCHÉESMÉTA-HEURISTIQUES
Les propriétés fondamentales des Méta-Heuristiques sont
les suivantes:1. Les méta-heuristiques sont des stratégies qui permettent de
guider la recherche d’une solution optimale2. Le but visé par les méta-heuristiques est d’explorer l’espace de
recherche efficacement afin de déterminer des solutions(presque) optimales.
3. Les techniques qui constituent des algorithmes de type méta-heuristique vont de la simple procédure de recherche locale àdes processus d’apprentissage complexes.
4. Les méta-heuristiques sont en général non-déterministes et nedonnent aucune garantie d’optimalité
25
MÉTHODES APPROCHÉESMÉTA-HEURISTIQUES
Les propriétés fondamentales des Méta-Heuristiques sont
les suivantes:5. Les méta-heuristiques peuvent contenir des mécanismes qui
permettent d’éviter d’être bloqué dans des régions de l’espace derecherche.
6. Les concepts de base des méta-heuristiques peuvent être décritde manière abstraite, sans faire appel à un problème spécifique.
7. Les méta-heuristiques peuvent faire appel à des heuristiquesqui tiennent compte de la spécificité du problème traité, maisces heuristiques sont contrôlées par une stratégie de niveausupérieur.
8. Les méta-heuristiques peuvent faire usage de l’expérienceaccumulée durant la recherche de l’optimum, pour mieux guiderla suite du processus de recherche.
26
MÉTHODES APPROCHÉESMÉTA-HEURISTIQUES
On classer les méta-heuristiques selon leur principe de
fonctionnement:
Méthodes par construction (approche gloutonne);
Méthodes de voisinage (recuit simulé, recherche
tabou);
Méthodes évolutives (algorithmes génétiques)
Méthodes biomimétiques (algorithme de colonies de
fourmis & d’essaim de particules)
27
MÉTA-HEURISTIQUESMÉTHODES PAR CONSTRUCTION
Principe:
On démarre d’une solution initiale vide;
A chaque itération, une variable est choisie (aléatoirement ou via
une heuristique) à laquelle est attribuée une valeur du domaine;
Le critère d’arrêt est l’affectation d’une valeur à toutes les
variables du problème.
Avantage et inconvénient: Simples mais performances
médiocres.
Exemple : méthode gloutonne
28
MÉTHODES PAR CONSTRUCTIONMÉTHODE GLOUTONNE
La méthode gloutonne permet de construire une solution
pas à pas
sans jamais revenir sur ses décisions,
en prenant à chaque étape la solution qui semble la
meilleure localement (heuristique),
en espérant obtenir une solution optimale.
29
Exemple 1: Problème du MAX-SAT
A chaque étape, choisir une variable X (aléatoire ou heuristique)
et l’affecter une valeur de vérité VP (vrai ou faux) permettant de
satisfaire le plus grand nombre de clauses non satisfaites.
Exemple 2: Problème du sac à dos
Trier les objets selon un critère donnée (e.g., le rapportvaleur/poids) et sélectionner un objet (e.g., de plus grandrapport) jusqu’à atteindre la capacité maximale de sac à dos
MÉTHODES PAR CONSTRUCTIONMÉTHODE GLOUTONNE
30
MÉTA-HEURISTIQUESMÉTHODES DE VOISINAGE
Les méthodes de voisinage se basent sur la notion devoisinage.
Principe: Une méthode typique de voisinage débute avecune configuration initiale, et réalise ensuite un processusitératif qui consiste à remplacer la configuration courantepar l'un de ses voisins en tenant compte de la fonction de coût.Ce processus s'arrête et retourne la meilleure configurationtrouvée quand la condition d'arrêt est réalisée. Cettecondition d'arrêt concerne généralement une limite pour lenombre d'itérations, le temps d’exécution ou un objectif àréaliser.
31
MÉTA-HEURISTIQUESMÉTHODES DE VOISINAGE
Avantages et inconvénients: Un des avantages desméthodes de voisinage réside précisément dans lapossibilité de contrôler le temps de calcul : la qualité de lasolution trouvée tend à s'améliorer progressivement aucours du temps et l'utilisateur est libre d'arrêterl'exécution au moment qu'il aura choisi. Cependant, lasolution obtenue dépend fortement de la solution initialeet de la stratégie de voisinage et de parcours de cevoisinage.
Exemple: Recuit Simulé, Recherche Tabou, ……
32
MÉTHODES DE VOISINAGERECUIT SIMULÉ
La méthode du Recuit Simulé repose sur une analogie avecla thermodynamique où la fonction à minimiser est l'énergiedu système.
Le recuit est un processus physique de chauffage. Unsystème physique porté à une température assez élevéedevient liquide, et dans ce cas le degré de liberté des atomesqui le composent augmente. Inversement lorsque l'on baissela température le degré de liberté diminue jusqu'à obtenirun solide. Suivant la façon dont on diminue la températureon obtient des configurations d'énergie différentes :
33
MÉTHODES DE VOISINAGERECUIT SIMULÉ
Suivant la façon dont on diminue la température on obtientdes configurations d'énergie différentes : Baisse brutale de la température, la configuration atteinte est le
plus souvent un état métastable, dont l'énergie est supérieure àcelle du minimum absolu. Le système est en quelque sorte piégédans ce minimum local.
Baisse progressive de la température de façon à éviter de piégerle système dans des vallées d'énergie élevée, pour l'envoyer versles bassins les plus importants et les plus profonds, là où lesbaisses ultérieures de température le précipiteront vers les fonds.
34
MÉTHODES DE VOISINAGERECUIT SIMULÉ
35
MÉTHODES DE VOISINAGERECUIT SIMULÉ
Le principe du recuit simulé est de parcourir de manièreitérative l’espace des solutions:
1. On part avec une solution notée s0 initialement générée demanière aléatoire dont correspond une énergie initiale E0, et unetempérature initiale T0 généralement élevée.
2. A chaque itération de l’algorithme, un changement élémentaire esteffectué sur la solution, cette modification fait varier l’énergie dusystème ΔE. Si cette variation est négative (la nouvelle solutionaméliore la fonction objective, et permet de diminuer l’énergie dusystème), elle est acceptée. Si la solution trouvée est moins bonneque la précédente alors elle sera acceptée avec une probabilité Pcalculée suivant la distribution de Boltzmann.
36
MÉTHODES DE VOISINAGERECUIT SIMULÉ
37
MÉTHODES DE VOISINAGERECUIT SIMULÉ
1. Engendrer une configuration initiale S0 de S : SS02. Initialiser la température T en fonction du schéma de
refroidissement3. Répéter
a. Engendrer un voisin aléatoire S’ de Sb. Calculer ΔE = f (S’) - f(S)c. Si Δ E ≤ 0 alors SS’
Sinon accepter S’ comme la nouvelle solution avec la probabilitéP(E, T) = exp (- ΔE/T)
a. Mettre T à jour en fonction du schéma de refroidissement(réduire la température)
4. Jusqu’à la condition d’arrêt
38
MÉTHODES DE VOISINAGERECUIT SIMULÉ
Le choix de la température est primordial pour garantirl’équilibre entre l’intensification et la diversification dessolutions dans l’espace de recherche. En effet, on peutconsidérer une grande augmentation de la température commeun processus de diversification alors que la décroissance de latempérature correspond à un processus d’intensification.
39
MÉTHODES DE VOISINAGERECUIT SIMULÉ
Premièrement, le choix de la température initiale dépend
de la qualité de la solution de départ. Si cette solution est
choisie aléatoirement, il faut prendre une température
relativement élevée.
40
MÉTHODES DE VOISINAGERECUIT SIMULÉ
De manière générale, les schémas de la décroissance (ou réduction)de la température (ou schémas de refroidissement) peuvent êtreclassés en trois catégories : décroissance par paliers: chaque température est maintenue égale
pendant un certain nombre d'itérations, et décroît ainsi par paliers. Décroissance linéaire ou continue: la température est modifiée à chaque
itération. Décroissance non-monotone: la température décroît à chaque itération
avec des augmentations occasionnelles.
41
MÉTHODES DE VOISINAGERECUIT SIMULÉ
Avantages:Souple vis-à-vis des évolutions du problème et facile à
implémenter,Evite le piège des optima locaux,Excellents résultats pour un nombre de problèmes
complexes.Inconvénients:Nombreux tests nécessaires pour trouver les bons
paramètres,Définir les voisinages permettant un calcul efficace de ΔE.
42
MÉTHODES DE VOISINAGERECHERCHE TABOU
La méthode tabou fait appel à un ensemble de règleset de mécanismes généraux pour guider la recherche demanière intelligente au travers de l'espace des solutions.
A l'inverse du recuit simulé qui génère de manièrealéatoire une seule solution voisine s’ ∈ N(s) à chaqueitération, la recherche tabou examine un échantillonnagede solutions de N(s) et retient la meilleure s’ même sis’ est plus mauvaise que s. La recherche tabou nes'arrête donc pas au premier optimum trouvé.
43
MÉTHODES DE VOISINAGERECHERCHE TABOU
Cependant, cette stratégie peut entraîner des cycles, parexemple un cycle de longueur 2 : s→s’→s→s’ ...
Pour empêcher ce type de cycle, la recherche tabou utiliseune liste T (appelée liste tabou) qui mémorise les kdernières solutions visitées et interdit tout mouvementvers une solution de cette liste.
Cette liste permet d'éviter tous les cycles de longueurinférieure ou égale à k. La valeur de k dépend duproblème à résoudre et peut éventuellement évoluer aucours de la recherche.
44
MÉTHODES DE VOISINAGERECHERCHE TABOU
Les solutions ne demeurent dans T que pour un nombrelimité d’itérations. La liste T est donc une mémoire àcourt terme. En effet, quand le nombre k est atteint,chaque nouvelle solution sélectionnée remplace la plusancienne dans la liste. La construction de la liste tabouest basée sur le principe FIFO, c’est-à-dire le premierentré est le premier sorti.
45
MÉTHODES DE VOISINAGERECHERCHE TABOU
46
MÉTHODES DE VOISINAGERECHERCHE TABOU
1. Initialisationa. S0 une solution initialeb. SS0; S*S0; C*f(S0)c. T = (c’est la liste tabou dont la taille maximale est k)
2. Répétera. Générer un sous ensemble de solution au voisinage de s et
garder la meilleure solution s’
b. Ajouter s’ à la liste T
3. Jusqu’à la condition d’arrêt
47
MÉTHODES DE VOISINAGERECHERCHE TABOU
La liste tabou demande typiquement beaucoup de placemémoire et du temps (pour les opérations de mis à joursla liste). Certains préconisent l’utilisation des listes taboues réactives dont
la taille varie selon les résultats de la recherche. Ainsi, si dessolutions sont visitées de manière répétée (à intervalle > |t|)alors on peut augmenter la longueur de la liste, ce qui aura poureffet de diversifier la recherche. Par contre, si la solutioncourante n’est que rarement améliorée, cela peut signifier qu’ilest temps d’intensifier la recherche en évitant d’interdire trop desolutions dans le voisinage de la solutions courante, et endiminuant donc la longueur de la liste taboue.
SOURCES DE CE COURS
Karima Benatchba, Cours de Techniques d’optimisation, ESI, 2009.
S. Le Digabel, Introduction aux métaheuristiques, Ecole Polytechnique deMontréal, 2014.
Sidi Mohamed Douiri, Souad Elbernoussi & Halima Lakhbab. Cours desMéthodes de Résolution Exactes Heuristiques et Métaheuristiques, Facultédes Sciences de Rabat, Université Mohammed V.
Jin-Kao Hao, Philippe Galinier, Michel Habib. Méthaheuristiques pourl’optimisation combinatoire et l’affectation sous contraintes, Revued’Intelligence Artificielle, Vol 1999.
Saïd Jabbour, De la Satisfiabilité Propositionnelle aux FormulesBooléennes Quantifiées, thèse de doctorat, Université d’Artois, 2008.
Nadjib Lazaar, Exploration de techniques de recherche locale pour lagénération automatique de cas de test. Etude bibliographique, 2011.
48