Stratégies d’exploration informées
Stratégies d’exploration non informées
Ne sont pas très efficaces dans la plupart des
cas.
Elles ne savent pas si elles approchent du but.
Stratégies d’exploration informées
Elles utilisent une fonction d’estimation
Fonction heuristique.
Pour choisir les nœuds à visiter.
39
Stratégies d’exploration informée
Meilleur d’abord (BFS - Best-first)
Meilleur d’abord gloutonne (Greedy best-first)
A* (A-Star)
Algorithmes heuristiques à mémoire limitée
IDA*, RDFS et SMA*
Par escalade (Hill-climbing)
Par recuit simulé (Simulated annealing)
Exploration locale en faisceau (Local beam)
Algorithmes génétiques
40
Exemple d’exploration:
Voyage en Roumanie (avec coûts en km)
41
Meilleur d’abord
A
L’idée principale
Utiliser une fonction d’évaluation f(B)
Estimer l’intérêt des nœuds g(B)
Développer le nœud le plus intéressant. B
Le nœud à développer est choisi selon une
fonction d’évaluation f(n) h(B)
Une composante importante de ce type .
.
d’algorithme est une fonction heuristique h(n) .
Elle estime le coût du chemin le plus court pour se
rendre au but.
Deux types de recherche meilleur d’abord
but
Meilleur d’abord gloutonne.
A*
42
Meilleur d’abord gloutonne
A
f(n) = h(n) g(B)
f(B) = h(B)
Donc on choisit toujours de B
développer le nœud le plus h(B)
.
proche du but.
.
.
but
43
Exemple meilleur d’abord gloutonne
366 Arad
253 Sibiu 329 Timisoara 374 Zerind
366 Arad 176 Fagaras 380 Oradea 193 Rimnicu Vilcea
253 Sibiu 0 Bucharest
44
Propriétés - Meilleur d’abord gloutonne
Complétude : Non
Car elle peut être prise dans des cycles.
Mais oui, si l’espace de recherche est fini avec vérification des
états répétés.
Complexité en temps : O(bm)
Mais une bonne fonction heuristique peut améliorer grandement
la situation.
Complexité d’espace : O(bm)
Elle retient tous les nœuds en mémoire.
Optimale : Non
Elle s’arrête à la première solution trouvée.
45
A* (A-star)
Fonction d’évaluation: f(n) = g(n) + h(n)
g(n) : coût du nœud de départ jusqu’au nœud n
h(n) : coût estimé du nœud n jusqu’au but
f(n) : coût total estimé du chemin passant par n pour se rendre
au but.
A* utilise une heuristique admissible
c’est-à-dire h(n) ≤ h*(n)
h*(n) est le véritable coût pour se rendre de n au but.
Demande aussi que :
h(n) ≥ 0, et que
h(G) = 0 pour tous les buts G.
46
Exemple A*
366 = 0 + 366 Arad
393 = 140 + 253 Sibiu 447 = 118 + 329 Timisoara Zerind
449 = 75 + 374
Arad 415 = 239 + 176 Fagaras Oradea 413 = 220 + 193 Rimnicu Vilcea
646 = 280+ 366 671 = 291 + 380
Craiova 417 = 317 + 100 Pitesti Sibiu
Sibiu Bucharest 526 = 366 + 160 553 = 300 + 253
591 = 338 + 253 450 = 450 + 0
Bucharest Craiova Rimnicu Vilcea
418 = 418 + 0 615 = 455 + 160 607 = 414 + 193
But atteint, la recherche arrête.
47
Propriétés de A*
Complétude : Oui
À moins qu’il y est une infinité de nœuds avec f ≤ f(but).
Complexité de temps : Exponentielle
Selon la longueur de la solution.
Complexité en espace : Exponentielle
Selon la longueur de la solution.
Elle garde tous les nœuds en mémoire.
Optimale : Oui
Habituellement, on manque d’espace longtemps avant de
manquer de temps.
48
Optimalité de A*
A* développe les noeuds en ordre croissant de valeur f
Ajoute graduellement des “f-contours” aux noeuds
Le contour i a tous les noeuds avec f=fi, tel que fi < fi+1
49
Exploration heuristique à mémoire limitée
A* est parfois trop gourmand en mémoire.
Il existe des algorithmes pour surmonter ce
problème dont:
IDA*;
RBFS;
SMA*.
Ces algorithmes permettent de préserver
l’optimalité et la complétude.
L’augmentation du temps d’exécution est
raisonnable.
50
Exploration heuristique à mémoire limitée
IDA* (Iterative-deepening A*)
C’est un algorithme de profondeur itérative
Utilise la valeur f(n) comme limite
Contrairement à la profondeur pour IDS.
À chaque itération :
On fixe la limite à la plus petite valeur f(n) de tous
les nœuds qui avaient une valeur plus grande que
la limite au tour précédent.
51
Exemple IDA*
366 = 0 + 366 Arad Limite: 366
393 = 140 + 253 Sibiu 447 = 118 + 329 Timisoara Zerind
449 = 75 + 374
52
Exemple IDA*
366 = 0 + 366 Arad Limite: 393
393 = 140 + 253 Sibiu 447 = 118 + 329 Timisoara Zerind
449 = 75 + 374
Arad 415 = 239 + 176 Fagaras Oradea 413 = 220 + 193 Rimnicu Vilcea
646 = 280+ 366 671 = 291 + 380
53
Exemple IDA*
366 = 0 + 366 Arad Limite: 413
393 = 140 + 253 Sibiu 447 = 118 + 329 Timisoara Zerind
449 = 75 + 374
Arad 415 = 239 + 176 Fagaras Oradea 413 = 220 + 193 Rimnicu Vilcea
646 = 280+ 366 671 = 291 + 380
Craiova 417 = 317 + 100 Pitesti Sibiu
526 = 366 + 160 553 = 300 + 253
54
Exemple IDA*
366 = 0 + 366 Arad Limite: 415
393 = 140 + 253 Sibiu 447 = 118 + 329 Timisoara Zerind
449 = 75 + 374
Arad 415 = 239 + 176 Fagaras Oradea 413 = 220 + 193 Rimnicu Vilcea
646 = 280+ 366 671 = 291 + 380
Craiova 417 = 317 + 100 Pitesti Sibiu
Sibiu Bucharest 526 = 366 + 160 553 = 300 + 253
591 = 338 + 253 450 = 450 + 0
55
Exemple IDA*
366 = 0 + 366 Arad Limite: 417
393 = 140 + 253 Sibiu 447 = 118 + 329 Timisoara Zerind
449 = 75 + 374
Arad 415 = 239 + 176 Fagaras Oradea 413 = 220 + 193 Rimnicu Vilcea
646 = 280+ 366 671 = 291 + 380
Craiova 417 = 317 + 100 Pitesti Sibiu
Sibiu Bucharest 526 = 366 + 160 553 = 300 + 253
591 = 338 + 253 450 = 450 + 0
Bucharest Craiova Rimnicu Vilcea
418 = 418 + 0 615 = 455 + 160 607 = 414 + 193
56
Exemple IDA*
366 = 0 + 366 Arad Limite: 418
393 = 140 + 253 Sibiu 447 = 118 + 329 Timisoara Zerind
449 = 75 + 374
Arad 415 = 239 + 176 Fagaras Oradea 413 = 220 + 193 Rimnicu Vilcea
646 = 280+ 366 671 = 291 + 380
Craiova 417 = 317 + 100 Pitesti Sibiu
Sibiu Bucharest 526 = 366 + 160 553 = 300 + 253
591 = 338 + 253 450 = 450 + 0
Bucharest Craiova Rimnicu Vilcea
418 = 418 + 0 615 = 455 + 160 607 = 414 + 193
But atteint, la recherche arrête.
57
Exploration heuristique à mémoire limitée
RBFS (Recursive best-first search)
Ressemble au meilleur d’abord.
Idée:
Conserve en mémoire la valeur f(n) de la meilleure
alternative d’un des ancêtres.
Si le nœud courant excède cette valeur :
on garde en mémoire la valeur f(n) du meilleur descendant
on essaie une autre branche.
Optimal : comme A* si f(n) est admissible.
Complexité d’espace : linéaire -- O(bd).
Plus efficace que IDA*.
58
Exemple RBFS
infini
366 Arad
447
393 Sibiu 447 Timisoara 449 Zerind
417 447
415
646 Arad 671 Oradea 417 413 Rimnicu Vilcea
450 415 Fagaras
447
526 Craiova 417 Pitesti 553 Sibiu
591 Sibiu 450 Bucharest
418 Bucharest 615 Craiova 607 Rimnicu Vilcea
But atteint, la recherche arrête.
59
Algorithme RBFS
60
Recherche à mémoire limitée
SMA* (Simplified memory bounded A*)
Exactement comme A*, mais avec une limite sur la mémoire.
S’il doit développer un nœud et que la mémoire est pleine, il
enlève le plus mauvais nœud et comme RBFS, il enregistre au
niveau du père la valeur du meilleur chemin.
Complétude : Oui
S’il y a une solution atteignable
Optimale : Oui
Si la solution optimale est atteignable
Complexité en temps : Peut être très long
S’il doit souvent regénérer des nœuds.
Complexité en espace : C’est la mémoire allouée.
61
Fonctions heuristiques
7 2 4
h1(n) = nombre de tuiles mal placées.
h2(n) = distance Manhattan totale 5 6
(nombre de cases pour se rendre à la 8 3 1
position désirée pour chaque tuile).
État initial
h1(n) = 8
1 2
h2(n) = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2
3 4 5
= 18
6 7 8
État but
62
Facteur de branchement effectif
Si N nœuds traités avec une solution de profondeur d
Alors le facteur de branchement effectif (b*) est le facteur de
branchement d’un arbre uniforme de profondeur d contenant N
nœuds.
N = 1 + b* + (b*)2 + … + (b*)d
Plus la valeur de b* s’approche de 1, plus l’heuristique
est efficace.
Pour déduire la valeur de b*, il suffit de faire des tests de
complexité variable et de calculer la valeur moyenne.
b* donne une bonne idée de l’utilité de l’heuristique et
permet aussi de comparer des heuristiques.
63
Comparaison
64
Dominance
Si h2(n) ≥ h1(n) pour tout n (les deux étant admissibles)
Alors h2(n) domine h1(n)
Et par conséquent h2(n) est meilleure que h1(n).
Il est toujours préférable de choisir l’heuristique
dominante, car elle va développer moins de noeuds
Tous les nœuds avec f(n) < C* vont être développé.
Donc, tous les nœuds avec h(n) < C* - g(n) vont être développé.
Par conséquent, tous les nœuds développé par h2(n) vont aussi
être développé par h1(n).
Et h1(n) peut aussi développé d’autres nœuds.
65
Inventer une heuristique
Simplifier le problème
La solution exacte du problème simplifié peut
être utilisée comme heuristique.
h1(n) est exacte, si une tuile peut être déplacée
à tout endroit.
h2(n) est exacte, si une tuile peut être déplacée
dans toute cellule adjacente.
Le coût de la solution optimale pour le problème
simplifié n’est pas plus grand que le coût de la
solution optimale du vrai problème.
66
Algorithmes d’amélioration itérative
Dans plusieurs problèmes d’optimisation, le chemin n’est
pas important, l’état but est la solution.
Avec ce type d’algorithme, l’espace de recherche est
l’ensemble des configurations complètes et le but est
soit:
De trouver la solution optimale
Ou de trouver une configuration qui satisfait les contraintes
On part donc avec une configuration complète et, par
amélioration itérative, on essaie d’améliorer la qualité de
la solution.
67
Exemple
Le problème des n reines
Mettre n reines sur une planche de jeu de n x
n sans qu’il y ait deux reines sur la même
colonne, ligne ou diagonale.
68
Algorithmes d’amélioration itérative
Par escalade (Hill-climbing)
Par recuit simulé (Simulated annealing)
Exploration locale en faisceau (Local beam)
Algorithmes génétiques
69
Algorithmes d’amélioration itérative
Par escalade (Hill-climbing)
À chaque tour, on choisit le successeur ayant la
meilleure évaluation
Si celle-ci est meilleure que l’évaluation du noeud courant.
Condition d’arrêt
Quand aucun des successeurs n’a une meilleure valeur que le
nœud courant.
Avantage:
Pas d’arbre de recherche à maintenir
Pas de retour en arrière.
C’est comme escalader le mont Everest en
plein brouillard en souffrant d’amnésie!
70
Algorithmes d’amélioration itérative
Par escalade (Hill-climbing)
71
Algorithmes d’amélioration itérative - Par escalade
Exemple 8-reines
h: le nombre de pairs de
reines qui s’attaquent
Pour cet état : h = 17
On détermine la valeur
des successeurs
possibles
c.-à-d. le coup qui permet
de minimiser le nombre
d’attaques
72
Algorithmes d’amélioration itérative - Par escalade
Problèmes de Hill-climbing
Reste pris souvent :
Maximum local
Plateaux
Crêtes (Ridges)
73
Algorithmes d’amélioration itérative - Par escalade
Exemple minimum local
Pour cet état : h = 1
Tous les successeurs
ont une valeur plus
grande.
74
Algorithmes d’amélioration itérative - Par escalade
Redémarrage aléatoire
Lorsque l’on obtient aucun progrès :
Redémarrage de l’algorithme à un point de départ différent.
Sauvegarde de la meilleure solution à date.
Avec suffisamment de redémarrage, la solution optimale sera
éventuellement trouvée.
Très dépendant de la surface d’états :
Si peu de maxima locaux
La réponse optimale sera trouvée rapidement.
Si la surface est dentelée
On ne peut espérer mieux qu’un temps exponentiel.
Habituellement, on peut espérer une solution
raisonnable avec peu d’itérations.
75
Algorithmes d’amélioration itérative
Recuit simulé (simulated annealing)
L’idée est de permettre de mauvais déplacements dans le but d’échapper
aux maxima locaux.
Principe :
On sélectionner un déplacement aléatoire.
S’il améliore la situation, il est exécuté.
Sinon il est exécuté avec une probabilité inférieure à 1.
Plus le mouvement empire la situation, plus la probabilité que le
mouvement soit choisi est faible.
Un paramètre T
Il tend vers zéro avec le temps.
Il est utilisé pour déterminer la probabilité d’un mauvais mouvement.
Plus la valeur de T est grande, plus un mauvais mouvement a des chances
d’être exécuté.
L’algorithme se comporte comme hill-climbing lorsque T tend vers zéro.
76
Algorithmes d’amélioration itérative
Recuit simulé
77
Algorithmes d’amélioration itérative
Recherche locale en faisceau
Fonctionnement:
Commence avec k états aléatoires
À chaque étape, l’algorithme génère tous les
successeurs des k états.
Si on trouve un but, on arrête.
Sinon, on choisit les k meilleurs successeurs et on
recommence.
Recherche en faisceau stochastique
Les k successeurs sont choisis aléatoirement
Selon une probabilité proportionnelle à la valeur de la
fonction d’évaluation.
78
Algorithmes d’amélioration itérative
Algorithmes génétiques
Les AG utilisent certains principes de l'évolution
naturelle:
Un individu fort a plus de chance de survivre
Deux individus forts donnent généralement des
enfants forts
Si l’environnement évolue lentement, les organismes
évoluent et s’adaptent.
Occasionnellement, des mutations surviennent,
certaines sont bénéfiques et d’autres mortelles.
Les AG utilisent ces principes pour gérer une
population d'hypothèses (ou individus).
79
Algorithmes génétiques :
Fonctionnement
Les individus sont souvent décrits par des chaînes de
bits
Mais elles peuvent aussi être décrites par des entiers, des
expressions symboliques ou des programmes informatiques.
Fonctionnement:
On commence avec une population initiale.
La reproduction et la mutation donnent naissance à la
génération suivante.
À chaque génération, les individus sont évaluées selon une
certaine fonction d‘adaptation et les meilleures sont celles qui
ont le plus de chance de se reproduire.
80
Algorithmes génétiques :
Algorithme
Initialiser:(P ← p individus aléatoires)
Évaluer (Calculer la valeur d’adaptation de chaque hypothèse h)
Tant que max Fn-Adaptation(h) < Borne utilité
Créer une nouvelle génération Ps
Sélectionner:
Choisir (1-r)p individus de P et les ajouter à Ps selon la probabilité prob(h)
Reproduire:
Choisir r*p/2 paires d’individus selon la probabilité prob(h).
Pour chaque paire produire deux enfants et les ajouter à Ps
Muter:
Choisir m% individus de Ps avec une probabilité uniforme
Modifier un gêne choisi aléatoirement
Mettre à jour: P ← Ps
Évaluer: Calculer la valeur d’adaptation de chaque individu
Retourner l‘individu avec la meilleure valeur d’adaptation
fn _ adaptation(h) p : le nombre d’individus dans la population
prob(h) = p r : le taux de reproduction
∑ j =1
fn _ adaptation(h j )
m : le taux de mutation
81
Algorithmes génétiques :
Algorithme
82
Algorithmes génétiques :
Illustration de l’algorithme
Exemple de construction de population pour le problème des 8-reines
83
Algorithmes génétiques :
Illustration du croisement
84
Algorithmes génétiques :
Exemple
Voyageur de commerce
Trouver le chemin le plus court en passant par toutes
les villes et en revenant au point de départ
1 Gêne: ville
4 5 Individu: liste de villes
2
7
4
Population: ensemble de
5 parcours
6 2
3
http://wwwsi.supelec.fr/yb/projets/algogen/VoydeCom/VoyDeCom.html
85
Algorithmes génétiques :
Exemple: Reproduction
On choisit aléatoirement deux points de coupe.
On intervertit, entre les deux individus, les
parties qui se trouvent entre ces deux points.
On supprime, à l’extérieur des points de coupes,
les villes qui sont déjà placées entre les points
de coupe.
On recense les villes qui n’apparaissent pas
dans chacun des deux parcours.
On remplit aléatoirement les trous dans chaque
parcours.
86
Algorithmes génétiques :
Exemple: Reproduction
87
Algorithmes génétiques :
Exemple: Mutation
Quand une ville doit être mutée, on choisit
aléatoirement une autre ville dans ce
parcours et on intervertit les deux villes.
88
Algorithmes génétiques :
Exemple: Fonction d’adaptation
Si le parcours est invalide, c'est l'opposée
du nombre de chemin inexistant
3 chemins inexistants => Utilité = -3
Si le parcours est valide, c'est l'inverse de
la somme de la distance
Chemin de longueur 100 => Utilité = 0.01
89
Algorithmes génétiques :
Paramétrage
Combien d’individus dans une population ?
Trop peu et tous les individus vont devenir semblables;
Trop grand et le temps de calcul devient prohibitif.
Quel est le taux de mutation ?
Trop bas et peu de nouveaux traits apparaîtront dans la
population;
Trop haut et les générations suivantes ne seront plus
semblables aux précédentes.
Taux de reproduction, nombre maximum de générations,
etc.
Habituellement déterminé par essai et erreur.
90
Algorithmes génétiques parallèles
Séparer la population en sous-populations
Appliquer les algorithmes génétiques indépendamment
sur chacune des sous-populations
On effectue des migrations entre les sous-populations
(copie d'individus d'une population à une autre)
Permet une certaine diversité entre les individus
Permet d'éviter que le système tombe dans un maximum local
dû à l'apparition trop hâtive d'un individu dominant
91
Recherche « online »
Tous les algorithmes précédents sont des algorithmes
« offline ».
Ils calculent une solution complète avant de l’exécuter et à
l’exécution ils ne font qu’appliquer la solution trouvée.
Un agent de recherche « online » doit entrelacer les
temps de calculs et d’exécution
Il fait une action;
Il observe l’environnement;
Il choisit sa prochaine action.
Les algorithmes « online » sont assez différents, parce
qu’il faut tenir compte que l’agent se déplace
Par exemple, A* ne fonctionne pas « online »
92
Exercice
• Largeur d’abord
A • Coût uniforme
1 • Profondeur d’abord
4
• Profondeur limitée
h=2 B • Profondeur itérative
C h = 10 • Recherche bidirectionnelle
3 2 • Meilleur d’abord avare
2 8 • A*
h=7 D E h=3 F h=5 G h=0
1 7
H h = 11 I h=9
93
