03 IA Heuristique

Intelligence Artificielle
Algorithmes et recherches heuristiques
Elise Bonzon
http://web.mi.parisdescartes.fr/vbonzon/
elise.bonzon@mi.parisdescartes.fr
Licence 3 Informatique
UFR Mathématiques et Informatique
Université Paris Descartes
Intelligence artificielle
1 / 23
N
Recherche meilleur d’abord

Recherche gloutonne
L’algorithme A∗
Algorithmes de recherche locale
2 / 23
N

Recherche gloutonne
L’algorithme A∗
3 / 23
N
Rappel : Une stratégie est définie en choisissant un ordre dans lequel les
états sont développés
Idée : Utiliser une fonction d’évaluation f pour chaque noeud
→ mesure l’utilité d’un noeud
→ introduction d’une fonction heuristique h(n) qui estime le coût du chemin
le plus court pour se rendre au but
InsertAll insère le nœud par ordre décroissant d’utilité
Cas spéciaux :
Recherche gloutonne (un choix n’est jamais remis en cause)
A∗
4 / 23
N

Recherche gloutonne
L’algorithme A∗
5 / 23
N
Recherche gloutonne
Fonction d’évaluation f (n) = h(n) (heuristique)

h(n) : estimation du coût de n vers l’état final
Par exemple, hdd (n) est la distance à vol d’oiseau entre la ville n et
Bucharest
La recherche gloutonne développe le nœud qui paraı̂t le plus proche de
l’état final
6 / 23
N
Le voyage en Roumanie
Ligne droite jusqu’à Bucharest

Neamt Arad 366
Oradea Bucharest 0
87 Lasi
71 Craiova 160
92 Dobreta 242
Zerind 151 Vaslui
Eforie 161
75 Fagaras 176
Sibiu 142
Arad 140 Giurgiu 77
99 Urziceni Hirsova 151
118 80 Fagaras
Lasi 226
Timisoara Rimnicu Vilcea 98 Lugoj 244
111 211 85 Mehadia 241
Hirsova
Lugoj 97 Neamt 234
Bucharest Oradea 380
70 101
146 80 Pitesti 100
Mehadia Rimnicu Vilcea 193
Pitesti
90
75 138 Sibiu 253
Timisoara 329
Dobreta 120 Eforie Urziceni 80
Craiova Vaslui 199
Giurgiu
Zerind 374
7 / 23
N
Recherche gloutonne
Complétude : Incomplet (peut rester bloqué dans des boucles)

Exemple : Arad → Zerind → Arad → . . .
Complet si on ajoute un test pour éviter les états répétés
Temps : O(b m )
Une bonne heuristique peut améliorer grandement les performances
Espace : O(b m ) : Garde tous les nœuds en mémoire
Optimale : Non
8 / 23
N

Recherche gloutonne
L’algorithme A∗
9 / 23
N
Algorithme A∗
Idée : Eviter de développer des chemins qui sont déjà chers

Fonction d’évaluation : f (n) = g (n) + h(n)
g (n) est le coût de l’état initial à l’état n
h(n) est le coût estimé pour atteindre l’état final
f (n) est le coût total estimé pour aller de l’état initial à l’état final en
passant par n
A∗ utilise une heuristique admissible
h(n) ≤ h∗ (n) où h∗ (n) est le coût réel pour aller de n jusqu’à l’état final
Une heuristique admissible ne surestime jamais le coût réel pour atteindre
le but. Elle est optimiste
Par exemple hdd ne surestime jamais la vraie distance
Si h(n) = 0 pour tout n, alors A∗ est équivalent à l’algorithme de Dijkstra
de calcul du plus court chemin
Théorème : A∗ est optimale
10 / 23
N
Le voyage en Roumanie
Ligne droite jusqu’à Bucharest

Neamt Arad 366
Oradea Bucharest 0
87 Lasi
71 Craiova 160
92 Dobreta 242
Zerind 151 Vaslui
Eforie 161
75 Fagaras 176
Sibiu 142
Arad 140 Giurgiu 77
99 Urziceni Hirsova 151
118 80 Fagaras
Lasi 226
Timisoara Rimnicu Vilcea 98 Lugoj 244
111 211 85 Mehadia 241
Hirsova
Lugoj 97 Neamt 234
Bucharest Oradea 380
70 101
146 80 Pitesti 100
Mehadia Rimnicu Vilcea 193
Pitesti
90
75 138 Sibiu 253
Timisoara 329
Dobreta 120 Eforie Urziceni 80
Craiova Vaslui 199
Giurgiu
Zerind 374
11 / 23
N
Preuve d’optimalité de A∗
Supposons qu’il y ait un état final non optimal G 0 généré dans la liste des
nœuds à traiter
Soit n un nœud non développé sur le chemin le plus court vers un état
final optimal G
start
f (G 0 ) = g (G 0 ) car h(G 0 ) = 0
> g (G ) car G 0 n’est pas optimale
n ≥ f (n) car h est admissible
G G0
f (G 0 ) > f (n), donc A∗ ne va pas choisir G 0
12 / 23
N
Algorithme A∗
Complétude : Oui, sauf s’il y a une infinité de nœuds tels que f ≤ f (G )

Temps : exponentielle selon la longueur de la solution
Espace : exponentielle (garde tous les nœuds en mémoire)
Habituellement, on manque d’espace bien avant de manquer de temps
Optimale : Oui
13 / 23
N
Que faire si f décroı̂t?
Avec une heuristique admissible, f peut décroı̂tre au cours du chemin

Par exemple, si p est un successeur de n, il est possible d’avoir
n g = 4, h = 8, f = 12
p g = 5, h = 4, f = 9
On perd de l’information
f (n) = 12, donc le vrai coût d’un chemin à travers n est ≥ 12
Donc le vrai coût d’un chemin à travers p est aussi ≥ 12
⇒ Au lieu de f (p) = g (p) + h(p), on utilise f (p) = max(g (p) + h(p), f (n))
→ f ne décroı̂t jamais le long du chemin
14 / 23
N
Que faire si f décroı̂t?
Avec une heuristique admissible, f peut décroı̂tre au cours du chemin

Par exemple, si p est un successeur de n, il est possible d’avoir
n g = 4, h = 8, f = 12
p g = 5, h = 4, f = 9
On perd de l’information
f (n) = 12, donc le vrai coût d’un chemin à travers n est ≥ 12
Donc le vrai coût d’un chemin à travers p est aussi ≥ 12
⇒ Au lieu de f (p) = g (p) + h(p), on utilise f (p) = max(g (p) + h(p), f (n))
→ f ne décroı̂t jamais le long du chemin
14 / 23
N
Exemple d’heuristiques admissibles: le

taquin
h1 (n) = le nombre de pièces mal placées

→ h1 (S) = 8
h2 (n) = la distance de Manhattan totale (la distance de chaque pièce
entre sa place actuelle et sa position finale en nombre de places)
→ h2 (S) = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18
15 / 23
N

taquin

→ h1 (S) = 8
→ h2 (S) = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18
15 / 23
N

taquin

→ h1 (S) = 8
→ h2 (S) = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18
15 / 23
N

taquin

→ h1 (S) = 8
→ h2 (S) = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18
15 / 23
N
Dominance
h1 domine h2 si h1 et h2 sont admissibles et que h1 (n) ≥ h2 (n) pour tout n

h1 est alors meilleure pour la recherche
Exemple :
d = 12 IDS: 3, 644, 035 nœuds
A∗ (h1 ): 227 nœuds
A∗ (h2 ): 73 nœuds
d = 24 IDS: trop de nœuds
A∗ (h1 ): 39, 135 nœuds
A∗ (h2 ): 1, 641 nœuds
16 / 23
N
Comment trouver des heuristiques ad-

missibles?
Considérer une version simplifiée du problème

Le coût exact d’une solution optimale du problème simplifié est une
heuristique admissible pour le problème original
Exemple : simplification des règles du taquin
une pièce peut être déplacée partout
→ h1 (n) donne la plus petite solution
une pièce peut être déplacée vers toutes les places adjacentes
→ h2 (n) donne la plus petite solution
17 / 23
N

Recherche gloutonne
L’algorithme A∗
18 / 23
N
Dans de nombreux problèmes d’optimisation, le chemin qui mène vers une

solution n’est pas important
L’état lui-même est la solution
Idée : Modifier l’état en l’améliorant au fur et à mesure
Espace d’états : ensemble des configurations possible des états
Besoin de définir une fonction qui mesure l’utilité d’un état
19 / 23
N
Exemple : les n reines
Placer n reines sur un plateau de taille n × n, sans que deux reines se

trouvent sur la même ligne, colonne ou diagonale
Déplacer une reine pour réduire le nombre de conflits
h=5 h=2 h=0
20 / 23
N

On cherche un maximum global
objective function global maximum
shoulder
local maximum
"flat" local maximum
state space
current
state
21 / 23
N

Algorithme d’ascension du gradient:
22 / 23
N
On peut aussi considérer la descente du gradient

On peut être bloqué dans un maximum local
Problème : les plateaux
Solution : on admet des mouvements de côté
23 / 23
N

03 IA Heuristique

Transféré par

Informations du documentcliquez pour développer les informations du document

Droits d'auteur :

Formats disponibles

03 IA Heuristique

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

03 IA Heuristique

Transféré par

Droits d'auteur :

Formats disponibles

Intelligence Artificielle

Algorithmes et recherches heuristiques

Algorithmes et recherches heuristiques

Recherche meilleur d’abord

Algorithmes et recherches heuristiques

Recherche meilleur d’abord

Recherche meilleur d’abord

Algorithmes et recherches heuristiques

Recherche meilleur d’abord

Fonction d’évaluation f (n) = h(n) (heuristique)

Ligne droite jusqu’à Bucharest

Complétude : Incomplet (peut rester bloqué dans des boucles)

Algorithmes et recherches heuristiques

Recherche meilleur d’abord

Idée : Eviter de développer des chemins qui sont déjà chers

Ligne droite jusqu’à Bucharest

f (G 0 ) > f (n), donc A∗ ne va pas choisir G 0

Complétude : Oui, sauf s’il y a une infinité de nœuds tels que f ≤ f (G )

Que faire si f décroı̂t?

Avec une heuristique admissible, f peut décroı̂tre au cours du chemin

Que faire si f décroı̂t?

Avec une heuristique admissible, f peut décroı̂tre au cours du chemin

Exemple d’heuristiques admissibles: le

h1 (n) = le nombre de pièces mal placées

Exemple d’heuristiques admissibles: le

h1 (n) = le nombre de pièces mal placées

Exemple d’heuristiques admissibles: le

h1 (n) = le nombre de pièces mal placées

Exemple d’heuristiques admissibles: le

h1 (n) = le nombre de pièces mal placées

h1 domine h2 si h1 et h2 sont admissibles et que h1 (n) ≥ h2 (n) pour tout n

Comment trouver des heuristiques ad-

Considérer une version simplifiée du problème

Algorithmes et recherches heuristiques

Recherche meilleur d’abord

Algorithmes de recherche locale

Dans de nombreux problèmes d’optimisation, le chemin qui mène vers une

Exemple : les n reines

Placer n reines sur un plateau de taille n × n, sans que deux reines se

h=5 h=2 h=0

Algorithmes de recherche locale

Algorithmes de recherche locale

Algorithmes de recherche locale

On peut aussi considérer la descente du gradient

Vous aimerez peut-être aussi