Plan du cours :

Représentation et résolution de problèmes :

Objectif : Introduire les méthodes de recherches arborescentes
Intelligence artificielle II informées permettant de trouver une "bonne" solution à un problème
à forte combinatoire et ceci en un temps acceptable.
Olivier Gasquet, Philippe Muller
IRIT • Introduction à la recherche opérationnelle et l’intelligence artificielle.
2006
• Calculabilité et complexité algorithmique.

• Représentation de la connaissance : éléments de théorie des

graphes.

• Représentation de problèmes
– espaces d’états (méthodes aveugles, informées (heuristiques)).
– réduction de problèmes en sous-problèmes (arbres ET/OU)...
– recherche locale dans les problèmes à forte combinatoire

Thèmes des bureaux d’étude (en Camel) Ouvrages conseillés :

• Programmation d’une procédure de recherche à stratégie paramétrable • A la recherche de l’intelligence artificielle. Daniel Crevier, Champs
(largeur ou profondeur) Flammarion (Poche).

• Evolution de la procédure précédante en meilleurs d’abord, puis en • Intelligence artificielle et informatique théorique, Alliot et Schiex, Ed.
A*. Cepadues

• Performance du A* pour le problème du voyageur de commerce avec • Recherche heuristiquement ordonnée, Henry Farreny, Ed. Masson.
dix heuristiques et des instances aléatoires.
• Introduction à la calculabilité, Pierre WOLPER, InterEdition
• implémentation de méthodes de recherche “locales”, expérimentation
sur le problème du voyageur de commerce.
 Résolution de problèmes et Intelligence artificielle Le match homme-machine
Les ordis c’est bon pour Les gens sont meilleurs pour
l’arithmétique perception, vision, parole, etc.
c’est quoi ? manipuler des chaînes de l’action
caractères
• une tentative de programmation des ordinateurs pour faire ce que l’humain fait les tâches répétitives comprendre et produire des
mieux (Rich & Knight) phrases en langage naturel
faire ce qu’on leur dit apprendre par exemples,
• une tentative de programmation des ordinateurs pour faire des choses dont on dit
observation,...
qu’elle nécessite de l”’intelligence” quand elles sont faites par des humains
le raisonnement de sens commun
• une étude des calculs qui rendent possible la perception, le raisonnement et les jeux
l’action (Winston) les mathématiques et la logique
• une façon d’étudier le cerveau humain formelle
• une quête du “sens commun” la conception et l’analyse
• une menace pour l’humanité (ingénierie, diagnostic médical,
architecture, planification, etc)

Souvent, ce qui est facile pour l’humain et difficile pour la machine (et
réciproquement).

4 5

Les domaines couverts par l’IA Domaines concernés

raisonnement démonstration
automatique, • problèmes mal posés ou mal définis (langage,...)
planification
jeux • domaines en friche (apprentissage,...)
apprentissage
langage interfaces, recherche • problèmes complexes ou très larges
d’informations
vision extraction, • problèmes pour lesquels on ne connaît pas d’algorithmes “efficaces”
reconnaissances de (rapides) ou ne donnant pas de “bonnes” solutions.
formes, surveillance
diagnostic pannes, diagnostic
médical
base de données base de connaissances
 4. évolution
ou logique)

2. représentation

partie concerne les points 2 et 3.

Une méthodologie commune ?

3. résolution (algorithmique, raisonnement, optimisation)

Un exemple: chercher son chemin

possibilités très grands → “recherche opérationnelle”. La première
partie du cours concernait le point 1 et en partie 2. Cette deuxième
L’étape (3) nécessite des recherches dans des ensembles de

8
1. modélisation d’un domaine ou d’un problème particulier (mathématique

       

       

       

       

       

       

       

       

                            
       
                            
       

                            
       
                            
       

                            
       
                            
       

                            
       
                            
       
Un exemple: chercher son chemin
Un exemple: chercher son chemin

9


       
       

       

       

       

       

       
       

       
       

                                 
                                 

                                 

                                 

                                 

                                 
Un exemple: chercher son chemin

Un autre exemple ? les missionnaires et les cannibales

12

CC
MM

B
C
M

CC
MM

B
C
C
MMM

B
C
MMM
CC
CCC
MMM

CC
CC
B

CCC
MMM C

MMM

B
Un exemple: chercher son chemin

Les missionnaires et les cannibales: exploration

13
 Les missionnaires et les cannibales: solution Les missionnaires et les cannibales: l’espace de
recherche

16 17

Complexité algorithmique Calculabilité et complexité algorithmique

Analyse des algorithmes : évaluation des ressources consommées par Questions :

les algorithmes, en temps d’éxécution et en espace mémoire. • comment l’évaluer indépendemment de la machine ?
• comment tenir compte des données différentes ?
→ moyen de comparaison des algorithmes = “complexité” des
algorithmes.
→ la taille des données d’entrée est un paramètre du temps de calcul.
le temps de calcul d’un programme dépend :
On notera T (n) le temps de calcul d’un algorithme en fonction de la
• des performances du processeur taille des données d’entrées (variable suivant les instances du problème
traité).
• du compilateur notions à retenir:
- l’ordre de grandeur du temps de calcul.
• des données d’entrées du problème - son évolution
- le pire cas
• de l’algorithme
 Taux de croissance Déprimant

On évalue le temps de calcul en ordre de grandeur, notion T(n) / n 10 20 30 40 50 60

mathématique: n 10µs 20 µs 30 µs 40 µs 50 µs 60 µs
log n 1µs 1.3 µs 1.5 µs 1.6 µs 1.7 µs 1.8 µs
n log n 10µs 26 µs 44 µs 64 µs 85 µs 107 µs
T (n) n2 100µs 400 µs 900 µs 1.6ms 2.5 ms 3.5 ms
T (n) = O(f (n)) ssi lim = cte
n→∞ f (n) n3 1ms 8 ms 27 ms 64 ms 125 ms 216 ms
n5 0.1s 3.2s 24.3s 1.7 mn 5.2 mn 13 mn
On dira donc, plutôt que T (n) = O(2n2) ou T (n) = O(n2 + 3n), que 2n 1ms 1s 18mn 13jours 36 ans 366 siècles
T (n) = O(n2). 3n 59ms 58 mn 6 mn 3855 siècles 2.108 siècles 1.3.1013 siècl
NB: l’âge de l’univers est estimé à 108 siècles.
Plus le taux de croissance est d’ordre inférieur, meilleur est l’algorithme,
mais pour des petites tailles de problèmes le temps de calcul peut être
meilleur pour un taux supérieur

20 21

Encore plus déprimant Analyse d’algorithmes : Algorithmes itératifs

• constantes
N=taille du problème qu’on peut résoudre aujourd’hui
• boucles (simples/doubles)
T(n) aujourd’hui si 100 fois plus vite si 1000 fois plus vite
n N 100N 1000N • tests (majorant)
n2 N 10N 32N
n3 N 4.6N 10N
n5 N 2.5N 4N Exemple: tri à bulle.
2n N N+7 N + 10
3n N N+4 N+6
f o r i :=1 t o n−1 do
f o r j : = n downto i +1 do
i f A [ j −1] > A [ j ] then
begin
temp = A [ j − 1 ] ;
a [ j −1] = A [ j ] ;
A [ j ] = temp Résultat = O(n2)
end ;
Exercice : tri par selection: Algorithmes récursifs
procedure t r i s e l ( v a r a : elem ; n : i n t e g e r ) ;
v a r i , j , p , min : i n t e g e r ;
Exemple : le tri par fusion (mergesort) d’une liste de n=2m nombres.
begin
f o r i : = 1 t o n−1 do
begin trifusion (L,n) =
min : = a [ i ] ; si n = 1 retour L
p := i ; s i n o n p a r t a g e r L en deux l i s t e s L1 e t L2 ;
f o r j : = i +1 t o n do r e t o u r f u s i o n ( t r i f u s i o n ( L1 , n / 2 ) ,
i f a [ j ] < min then t r i f u s i o n ( L2 , n / 2 ) )
begin
min : = a [ j ] ;
p := j ;
En supposant que le partage et la fusion sont en O(n), on estime un
end ; majorant :
a [ p ] := a [ i ] ; T (n) ≤ c1 si n = 1
a [ i ] : = min T (n) ≤ 2T (n/2) + c2n si n > 1
end
end

24 25

Pour résoudre les équations récurrentes classiques : la solution Pour les autres cas:
générale de T (n) = anb + c ∗ T (n/2)
• trouver un majorant, preuve par récurrence.
• si c < 2b alors l’algo est en O(nb)
• substitutions/ simplifications
• si c = 2b alors l’algo est en O(nb log n)
(exemple:
• si c > 2b alors l’algo est en O(nlog2 c)
T (n) = 2(T (n − 2)) + 4) => T (n) = 2nT (1) + 4n + a)
Résultat tri fusion: O(n log n)
 Exercices Complexité théorique

Au delà des algorithmes : classification des problèmes. Il peut y

1. fibonacci doublement récursif (indice: a∗(3/2)n ≤ f ib(n) ≤ b∗(5/2)n) avoir plusieurs algorithmes qui résolvent un problème : on va alors
caractériser les problèmes en fonction des algorithmes que l’on peut
2. fibonacci récursif terminal leur appliquer.

3. puissance efficace (avec resursif pair sur n div 2)

→ classement des problèmes.

4. recherche nb occurences chaînes dans sous-chaînes

→ “complexité” d’un problème.

→ “complexité théorique”.

28 29

La machine de Turing
La machine de turing est une idéalisation d’un processus de calcul
Exemples de problèmes : mécanisé. Elle consiste en :

– trier une liste d’entiers. • un ruban consitutée de cellules contenant les données.
– trouver le plus court chemin passant par n villes (voyageur de
commerce).
• une tête qui pointe sur une cellule du ruban
– trouver un modèle d’une formule en logique propositionnelle.
– montrer un thèorème de mathématique.
• un automate qui peut être dans un certain nombres d’états, et qui
peut faire les actions suivantes : se déplacer le long du ruban, lire ou
On peut diviser les problèmes en trois grandes catégories après ce que écrire le ruban, ou s’arrêter.
l’on a déjà vu (n étant la dimension des données d’entrées) :
Un algorithme est la définition exacte du comportement de l’automate
• la classe P : ceux pour lesquels il existe un algorithme en O(nk ). en fonction du ruban. Sa complexité en temps est le nombre
d’opérations qu’il doit effectuer avant de terminer avec succès.
• la classe E : ceux pour lesquels tous les algos sont minorés par an

• la classe I : les problèmes indécidables.

 La machine de Turing Exemple
On distingue deux sortes de machine de Turing:

déterministe à chaque instant il est dans un certain état et l’action qu’il

effectue ne dépend que de cet état. (correspond +/- à l’ordinateur
moderne idéalisé)

non déterministe il existe une instruction de choix non déterministe

entre deux états pour déterminer l’état suivant.

Un algorithme non déterministe accepte un donnée s’il termine avec

succès pour au moins un calcul possible. Sa complexité en temps est
la longueur du plus petit calcul qui accepte la donnée.

32 33

Un autre exemple L’exemple de SAT

– algo déterministe stupide : tester toutes les instanciations des n
variables propositionnelles (O(2n)) et vérifier la formule (en O(m), taille
de la formule)

– algo non déterministe : pour toute variable xi, le choix est entre
affecter la variable à vrai ou l’affecter à faux. Quand c’est fini, on teste
la formule (si vrai alors succès).

Donc l’algo non déterministe est < C1 ∗ n + C2 ∗ m donc en O(m).

En fait l’algo non-dét. est similaire en complexité à celui, déterministe,

consistant à vérifier qu’une instanciation du problème est solution (→
“vérification”).
 Catégories de problèmes

Autre problème: comment ramener un problème d’optimisation à un

problème soluble par la MT ? (la MT résoud des problèmes de La classe P est la classe des problèmes qui admettent un algorithme
“reconnaissance”) déterministe avec un temps d’éxécution polynomial en fonction de la
sur ex. du voyageur de commerce : taille du ruban d’entrée.

reconnaissance existe-t-il un circuit de longueur ≤ c donné. La classe NP est la classe des problèmes qui admettent un algorithme
non-déterministe avec un temps d’éxécution polynomial en fonction de
optimisation trouver le circuit optimal la taille du ruban d’entrée.

Attention: NP veut donc dire “non-deterministe polynomial” et pas “non

valeur optimale trouver seulement la longueur du circuit optimal polynomial”.

témoin trouver un circuit de longeur ≤ c donné La confusion est d’autant plus facile que les ordinateurs étant jusqu’à
présent uniquement déterministes, les problèmes de NP sont résolus
par des algos déterministes non-polynomiaux.
complexité : rec≤ témoin,val. optimale ≤ optimisation
On a donc de façon évidente P ⊆ NP.

La question à 1 million de $ est : a-t-on NP = P ?

36 37

NP complétude Un problème est NP-complet

retour sur SAT : SAT est dans NP s’il est dans NP et si tout problème de NP lui est réductible en temps
pôlynomial.
et il a étémontré (Cook, 1971) que :
P = NP ⇔ SAT ∈ P exemple de pbs NP complets:

SAT est un "prototype" des problèmes de NP.

• le voyageur de commerce (Travelling Salesman Problem)
il a été prouvé en fait que tout problème de NP pouvait se ramener à
SAT en temps polynomial. • le sac à dos (Knapsack problem)

On dit alors que SAT est NP-complet → tout un ensemble de problèmes • le déménageur (Binpacking)
de NP sont NP-complet.
• vehicle routing problem

• ordonnancement (scheduling)

• ...
 Maîtriser l’explosion combinatoire Représentation de la connaissance : éléments de
théorie des graphes

Définition
quand on n’a pas le choix...
Graphe dirigé G = (N, A)
• garder la taille des données petite N est un ensemble de noeuds (ou sommets)
A est un ensemble d’arêtes, A ⊆ N × N
• approximations (quand c’est possible) ex: bin packing (v, w) ∈ A est une arête de v à w (les extrémités de l’arête).
Un graphe est donc une relation binaire sur l’ensemble N. 1.
• approche probabiliste: algo aléatoires + prières + instances a

chanceuses → on évite le pire cas. TSP, SAT c

e

• heuristiques (cf. méthodes locales): proba + approximation

b
d
• méthodes de recherche optimisées (cf résolution de pb.)
Figure 1: Représentation graphique d’un graphe
pourquoi arrive-t-on à cette différence théorie-pratique ? L’ordre du graphe est son nombre de noeuds.
Deux sommets sont dits adjacents s’ils sont reliés par une arête.

40 41

Un graphe simple est le graphe d’une relation irréflexive (aucun noeud Propriétés
n’est relié à lui-même), symétrique.

Graphe non dirigé (i, j) ∈ A → (j, i) ∈ A • Pour un graphe non orienté (N, A) :
c’est un graphe pour lequel l’orientation n’a pas d’importance (on
X
représente tout lien par un lien simple). d(x) = 2|A|
x∈N
Graph complet
On appelle degré d’un sommet le nombre d’arêtes dont ce sommet est
une extrémité. • Pour un graphe orienté (N, A) :
X X
Si tous les sommets d’un graphe ont le même degré k, le graphe est dit d+(x) = d−(x) = |A|
k-régulier. x∈N x∈N

+
Pour un graphe orienté, on définit le degré entrant (d ) et le degré
sortant (d−) d’un noeud. n(n−1)
• Un graphe simple a au plus 2 arêtes.
Un graphe simple d’ordre n qui est (n-1)-régulier est dit complet. Deux
Sous-graphe soit un graphe G = (N, A), N 0 ⊆ N , A0 ⊆ A. G0 =
sommets quelconques sont alors adjacents.
(N 0, A0) est un sous-graphe de G si pour tout arête de A’, les extrémités
de l’arête dans G sont dans N’.
 Parcours dans les graphes
Chemin Un chemin entre deux arêtes v et w d’un graphe (N, A) est
une suite C = (v, u1, . . . , un, w) de noeuds de N tels que (v, u1) ∈ A, composante connexe d’un graphe non dirigé: sous-graphe connecté
(ui, ui+1) ∈ A et (un, w) ∈ A. maximal

Si v = w, le chemin C est fermé. composante fortement connexe idem pour graphe orienté
Si ∀i, jui 6= uj , le chemin est simple.
graphe fortement connexe graphe dirigé connexe : il existe un chemin
Un cycle est un chemin fermé simple. pour toute paire de noeuds (u, v), u et v distincts (de u à v et de v à u).
Fermeture transitive la fermeture transitive d’un graphe dirigé G =
(N, A) est un graphe dirigé G∗ = (N, A∗) tel que : (v, w) ∈ A∗ ↔ il y a
un chemin de v à w dans G

Graphe non dirigé connexe ∀i, j ∈ N, ∃ un chemin de i à j

44 45

Exemple : vérification de la forte connexité d’un Arbres

graphe de rues
3 4
1 2

Un arbre est un graphe connexe sans cycle.

8 9 Un arbre de n noeuds a donc exactement n-1 arêtes.

5
6 7

Tout graphe connexe contient un graphe partiel (N, A0), avec A0 ⊆ A,

qui est un arbre. On dit que l’arbre est un arbre recouvrant du graphe
13
(en anglais spanning tree).
10 11 12 14

Un arbre pointé est un arbre où on a distingué un sommet qcq. Ce

sommet est la racine de l’arbre.
16
15
17 18 Pour un graphe orienté, la racine de l’arbre est un noeud qui n’a pas
d’arcs entrants (il est unique).
Figure 2: Plan de rues
Une feuille est un noeud de degré 1 (graphe orienté : uniquement un
arc entrant)
 Explorations Parcours en profondeur

On appelle exploration ou parcours d’un graphe un procédé Il consiste, à partir d’un noeud à toujours explorer un noeud voisin
déterministe qui permet de choisir un sommet à partir de l’ensemble jusqu’à ce qu’il n’y en ait plus, puis à remonter dans le parcours pour
des sommets déjà visités de manière à passer par tous les sommets du visiter les voisins laissés de côté au fur et à mesure.
graphe.
Pour cela il faut marquer les noeuds déjà visités. Un algorithme type est
Deux types simples de parcours exhaustif : le parcours en profondeur par exemple :
et le parcours en largeur. p r o f o n d e u r (G : graphe , x : p o i n t de dé p a r t )

marquer ( x ) ;
traitement ( x ) ;
P i l e <− ensemble des y t e l s que ( x , y ) e s t une a r e
t a n t que ( P i l e pas v i d e ) f a i r e
e n l e v e r un element y de P i l e
s i y pas marqué a l o r s p r o f o n d e u r (G, y ) ;
f i n t a n t que ;

48 49

Parcours en largeur

Ce parcours trouve donc un arbre recouvrant (il y en a plusieurs l a r g e u r (G : graphe ; x : p o i n t de dé p a r t )

possibles en général). marquer ( x ) ;
m e t t r e x dans une f i l e F ;
1 t a n t que ( f i l e pas v i d e ) f a i r e
e n l e v e r l e premier sommet y de l a f i l e ;
4
traiter (y );
6
2 8 pour t o u t e s l e s a r e t e s ( y , z ) avec z non marq
marquer ( z ) ;
5 3 m e t t r e z dans F ;
7

Figure 3: Un exemple de parcours en profondeur

Complexité ? en espace O(n + m)

En temps : traitement d’un noeud proportionnel à son degré. Le temps

total est proportionnel à la somme des degrés = 2m donc O(m).
 1 Complexité de l’algorithme :
2
7 3 • en espace :
4
O(n + m) pour G,
6 5
8
O(n) pour T (n sommets et n-1 arêtes) et O(n) pour la file (mais
mieux en moyenne) et le marquage.
Figure 4: Parcours en largeur
• en temps : l’exploration du sommet i (le marquage de ses voisins)
Théorème : si G est connexe tous les sommets seront marqués par est fait en parcourant la liste des voisins (d(i) opérations), d’où temps
l’agorithme et toutes les arêtes seront explorées au moins une fois. en 2m = O(m).

Théorème : soit G = (N, A) un graphe connexe non orienté, soit T =

(N, B) un arbre recouvrant en profondeur G, construit par l’algorithme.
Toute arête a ∈ A appartient aussi à B ou bien connecte deux sommets
de G tels que l’un des deux soit un ancête de l’autre.

52 53

Partition des sommets en couches Représentation et résolution de problèmes

Pour résoudre un problème dans sa généralité, il est nécessaire de

Définition : la distance de deux sommets d’un graphe est la longueur suivre une méthodologie assurant que la solution fonctionne dans tous
du plus court chemin reliant les deux sommets, en convenant que cette les cas envisageables du problème.
distance est infinie s’ils ne sont pas reliés.
approche rigoureuse :
on fixe un sommet initial r. Une partition en couches associée à r est la
séquence d’ensembles définie comme suit : 1. poser correctement le problème : définition du problème
C0 = {r}
2. analyser la structure du problème
C1 = {x ∈ N/d(r, x) = 1}
Ci = {x ∈ N/d(r, x) = i}
3. définir une stratégie de résolution à partir de l’analyse.

Algorithme : on visite les sommets en construisant les couches dans

l’ordre en partant de la racine r, et en marquant successivement tous
les sommets des couches. La nouvelle couche est créée en prenant la
liste des voisins non marquée de la liste précédente.
 Résolution sur des graphes d’états simples

On peut diviser les méthodes de résolution en deux grandes classes,

étudiées ici :
On part du principe que tous les problèmes étudiés sont composés
d’un ensemble de situations ou objets que l’on peut décrire de façon
1. les méthodes systématiques univoque à l’aide d’un ensemble de variables appelés variables d’états
du problèmes.
2. les méthodes heuristiques (= empiriques).
l’état d’un problème est alors l’ensemble des valeurs prises par les
variables à un instant donné.

l’espace d’état d’un problème est l’ensemble de tous les états

possibles de ce problème

On peut considérer que la résolution d’un problème est la découverte

d’un état du problème ayant des caractéristiques données (=la
solution).

56 57

L’analyse de la structure du problème va généralement permettre Retour sur les cannibales et les missionaires
d’identifier des liens entre états qui permettent de les visiter tous de
façon systématique. Dans cette optique on va chercher :

• un langage formel (un ensembles de symboles) qui permet de Première étape de résolution : le codage du problème. Plusieurs
représenter le problème. solutions s’avèrent possibles :

• des outils de calcul capables de transformer un état en un autre • Un triplet (X,Y,P) où X est le nombre de missionnaires sur la rive
état et donc de permettre de balayer potentiellement tous les états gauche, Y celui de cannibales, et P la position du bateau (G ou D).
possibles de l’espace d’état.
• une liste des présents sur chaque rive (M, C ou B).
• une méthode d’organisation de ces transformations pour trouver
l’état solution le plus vite possible. Dans le premier cas quels sont les codages des états initiaux et finaux
et les contraintes portant sur les données ?
On peut dire que la dernière partie est la seule partie algorithmique
(c’est la stratégie de contrôle des opérations) alors que la résolution
d’un problème implique aussi fortement les deux premières : la
modélisation des données du problème et les opérateurs sur ces
données.
 Opérateurs sur les données/ système de production

1. 0 ≤ X ≤ 3 et 0 ≤ Y ≤ 3, et P=D ou G Le système de production est la description de l’ensemble des

mécanismes permettant de passer d’un état à un autre du problème.
• état initial = (3,3,G) Chaque état possède un ensemble d’états qui lui sont acessibles dans
• état final = (0,0,D) le problème. Les opérateurs permettent de définir cet ensemble, et c’est
la stratégie de résolution qui donnera la façon de choisir parmi ces états
2. • état initial rg=(M,M,M,C,C,C,B) rd=() accessibles celle menant à une solution.
• état final rg=() rd=(M,M,M,C,C,C,B)
Il y aura deux façons de procéder suivant les opérateurs que l’on définit :
Quelle est :
• soit on définit la liste des états accessibles à partir d’un état antérieur
- la plus compacte ? (1!!) du problème et on tente de passer ainsi de l’état initial à l’état final
(Raisonnement dit en chaînage avant)
- la plus pratique ? (? peut pas savoir avant de définir les opérateurs)
• soit on définit la liste des états à partir desquels on peut accéder à
un état donné du problème et on tente de remonter de l’état final à
l’état initial (Raisonnement dit en chaînage arrière)

60 61

Exemple des M & C: Représentation formelle plus pratique : la représentation par arbre. A
Les opérateurs consistent à faire passer 1 ou 2 personnes à la fois de chaque fois que l’on génère un état on le relie à l’état précédent. (sans
l’autre côté du fleuve en respectant les contraintes du problème : tester si on génère un état déjà rencontré)

– Il faut (Y ≤ X) ou X=0 et 3 − Y ≤ 3 − X ou 3-X=0 (au moins autant (3,3,D)

de M et de C, quand il y a des missionnaires)

Les opérations valides sont donc par exemple : (2,2,G) (3,1,G) (3,2,G)

(X, Y, G) → (X − 2, Y, D) si X ≥ 2 et X − 2 ≥ Y ou X − 2 = 0
(3,3,D) (3,3,D) (3,2,D) (3,3,D)
ou (2, Y, G) → (0, Y, D)
Avec un graphe : même chose avec un test d’occurrence : si un état
a déjà été rencontré on ajoute un arc au graphe, sinon un noeud et un
arc.
(3,3,D)

(2,2,G) (3,1,G) (3,2,G)

(3,2,D)
 Propriétés des systèmes de production Quelques rappels de dénombrement

Monotone un système de production est dit monotone si l’application

d’une règle à l’instant t laisse applicable à l’instant t’>t toutes les • le nombre de parties d’un ensembles à n éléments : 2n
autres règles qui étaient applicables à l’instant t. (M & C ? non)
• le nombre de permutations d’un ensemble à n éléments : n!
Partiellement commutatif un système est partiellement commutatif
s’il vérifie la condition suivante : • le nombre de sous ensembles de p éléments d’un ensemble à n
si X est un état et (s1, s2, ..., sn) une séquence de règles de éléments: Cnp
production telle que
s1
X −→ X1 → ... → Y
alors pour toute permutation σ, la séquence (sσ(1), ..., sσ(n))
transforme l’état X en Y pourvu que les conditions d’applications des
règles soient vérifiées à chaque étape.

Un système est commutatif s’il vérifie cette condition et qu’il est aussi
monotone.

64 65

Exercices Graphes ET/OU

Certains problèmes peuvent être représentés par la technique de

Représenter par un espace d’état les problèmes suivants : réduction de problème, c’est-à-dire que le problème peut être
considéré comme une conjonction de plusieurs sous-problèmes
indépendants les uns des autres, que l’on peut résoudre séparément.
le sac à dos on dispose d’un ensemble d’objets, chacun ayant un
volume, et un prix. On veut les mettre dans un sac de volume fixé. D’autre part, il peut se présenter dans la résolution d’un problème un
On peut se poser les questions suivantes: ensemble de possibilités indépendantes les unes des autres (donc
1. y’a-t-il un moyen de remplir complètement le sac ? exclusives) telles que la résolution d’une seule de ces possibilités suffit
2. comment remplir le sac en maximisant le prix du contenu ? à résoudre le problème.

On peut représenter ces deux possibilités par des arcs différents dans
le déménagement le graphe représentant l’espace de recherche :
- Les arcs qui représentent différentes possibilités dans la résolution
le gardien de musée d’un problème associés au noeud dont ils découlent sont des arcs OU
- Les arcs qui représentent différents sous-problèmes composant la
la couverture d’ensemble résolution d’un problème associés au noeud dont ils découlent sont des
arcs ET.
 Exemple : diagnostic

Un tel graphe est solution d’un problème si :

Problem X

• il contient le sommet de départ (état initial du pb)

• tous les sommets terminaux (feuilles) sont des problèmes primitifs

Batterie Starter
(indécomposables) résolus. Allumage

• s’il contient un arc ET il doit aussi contenir le groupe entier d’arcs ET

qui sont frères de cet arc. pas de lumiere moteur lumieres
essence arrive moteur moteur
tourne pas s’allument
au moteur tourne tourne pas

essence dans le essence dans le carburateur

rservoir

68 69

Stratégies de contrôle

Un sommet d’un arbre d’exploration d’un espace de recherche est dit

résolu si :
On associe à la génération des états une stratégie de contrôle. Elle est
dite systématique si elle vérifie les principes suivants :
• c’est un sommet terminal, ou bien
1. elle permet de générer tous les états sans en oublier.
• c’est un sommet OU non terminal et au moins un de ses axes pointe
sur un sommet résolu, ou bien
2. elle ne génère chaque état qu’une fois. Le premier principe garantit
la complétude de la procédure (on finit par tomber sur une solution si
• c’est un sommet ET non terminal et tous ses arcs pointent sur des
elle existe.
sommets résolus.

Le deuxième évite les calculs répétitifs.

exemples:
Ex: l’algo. suivant parfois appelé "algo du British Museum" (origine ?)
0) M et C que des OU est il systématique:
1) tours de Hanoi, avec n disques. ? que des ET
à partir d’un état qcq on génère au hasard l’état suivant jusqu’à trouver
2) planification
une solution. si on est dans une impasse on recommence au début.
Résumé de vocabulaire: Recherche systématique aveugle (ou non informée)

génération d’un noeud calcul du nouveau code de la représentation

Recherche en profondeur Chaque sommet choisi pour être exploré
d’un noeud à partir d’un noeud qcq l’ancien noeud est alors "exploré",
voit tous ses successeurs générés avant qu’un autre sommet ne soit
le nouveau "généré".
exploré. Dans la liste OUVERTS le sommet le plus profond est celui le
plus récemment généré. Cette ensemble aura donc une structure de
développement d’un noeud génération de tous ses successeurs. pile.

Lors d’une exploration l’ensemble des sommets du graphe de recherche Une recherche en profondeur peut se révéler dangereuse : l’algorithme
peut être divisé en quatre ensembles. risque de développer une branche infinie stérile sans que le mécanisme
de retour en arrière puisse se déclencher.On ajoute dans ce cas une
limite de profondeur.
• les sommets développés déjà vus
Recherche en largeur: Cette stratégie donne une plus grande priorité
• les sommets explorés non encore développés aux sommets les moins profonds du graphe de recherche en explorant
les sommets de même profondeur. L’ensemble OUVERT aura une
• les sommets générés mais pas encore explorés (en attente) structure de file.

• les noeuds toujours pas générés.

72 73

L’exemple du taquin Méthodes informées / Heuristiques

Une heuristique est un critère ou une méthode permettant de

2 8 3 déterminer parmi plusieurs lignes de conduite celle qui promet d’être
1 6 4 la plus efficace pour atteindre un but.
7 5

haut
droite Exemples:
gauche

2 8 3 2 8 3 2 8 3
6 4
Hill-climbing
1 4 1 1 6 4
7 6 5 7 5 7 5
Meilleur d’abord
d h g
h h
b g d

2 3 2 8 3 2 8 3 2 8 3 2 8 3 2 8 3 2 8 3 2 8 3
Coût uniforme
1 8 4 1 6 4 1 4 1 4 6 4 1 6 4 1 6 1 6 4
7 6 5 7 5 7 6 5 7 6 5 1 7 5 7 5 7 5 4 7 5

X X X A∗
Figure 5: Le taquin
 Hill-climbing (méthode de l’escalade)

Cette méthode de recherche en profondeur utilise une fonction 26

25
heuristique pour choisir à chaque étape le noeud à générer. C’est la 22

stratégie de l’alpiniste (soi-disant) qui choisit la direction de la pente la

plus forte pour arriver au sommet le plus vite. 34 35
22
18
24 23
Cette méthode comporte quelques dangers de dévissage : 45
41
40 42 17
50
• les fonctions d’évaluation peuvent être trompeuses, et certaines 17
45 16 15
améliorations peuvent entraîner dans des branches infinies (danger 37 50
du pifomètre).
12 11 10
32
• si on arrive à un maximum local de la fonction d’évaluation (un noeud 30

dont l’évaluation est supérieure à tous ses successeurs), il n’y a plus 8

9
de choix possibles et l’algo s’arrête, sans avoir trouvé la solution.
Il faut alors décider arbitrairement d’une reprise pour relancer la
Figure 6: Escalade et profondeur
recherche au risque de reprendre un sommet déjà visité.

76 77

Stratégie du meilleur d’abord (Best first)

On cherche dans cette stratégie à sélectionner le sommet le plus 26

25
prometteur par rapport à l’heuristique, parmi tous les sommets 22

rencontrés depuis le début, quelle que soit sa positon dans l’arbre

partiellement développé. 34 35
22
18
Le caractère prometteur d’un sommet peut être estimé de diverses 24 23

manières : 45
41
40 42 17
50

- évaluer la difficulté de résolution du sous-problème représenté par 45 16 15

17

le sommet 37 50

- estimer la qualité de la branche entière qui contient le sommet 12 11 10

32 30
- estimer la quantité d’information que l’on s’attend à gagner par
rapport à la solution cherchée. 8
9

Dans tous les cas l’estimation est numérique et elle est calculée Figure 7: Meilleur d’abord
au moyen d’une fonction heuristique d’évaluation f(n) qui peut donc
dépendre de n (le noeud), du but, de l’information de toute la branche.
 Graphes valués Le coût uniforme

chaque arc du graphe est muni d’un poids qui peut correspondre exemple somme colonnes matrices

trouver la colonne de somme minimum

• au coût d’une opération pour passer d’un état à un autre
12 5 7 29
• une distance entre deux noeuds d’un graphe 6 23 45
2
• etc 3

exploration en développant uniquement la colonne minimum courante.

quand on arrive à la fin d’une colonne on peut savoir si c’est le minimum

80 81

Stratégie A∗ (spécialisation du meilleur d’abord) mettre u0 dans OUVERTS

g(u0) ← 0
f(u0) ← 0
• u0 l’état initial. trouve ← faux
tantque OUVERT6=Ø et not(trouve) faire
• T l’ensemble des états terminaux. n ← enlever tete(OUVERTS)
• P = {p1, p2, ..., pn} l’ensemble des opérateurs mettre n dans FERMES
si n∈ T alors
• h(u) h est la fonction heuristique qui estime le coût du passage de trouve←vrai
l’état u à l’état final. sortir en retraçant les pointeurs père de n à u0
• k(u, v) k est la fonction qui donne le coût du passage de l’état u à sinon
l’état v (arc u,v) développer n avec les pi → successeurs de n
pour tout n0 = pi(n) faire
• g(v) est le coût du trajet pour atteindre l’état v
si n’6∈ (OUVERTS ∪ FERMES) ou g(n’)>g(n)+k(n,n’) alors
• f (v) est le coût total estimé calculer h(n’)
• pere(v) est le tableau indexé par les états qui donne pour chaque g(n’) ← g(n)+k(n,n’)
état celui qui l’a généré. f(n’) ← g(n’)+h(n’)
pere(n’) ← n
• OUVERTS= noeuds en attente / FERMES = noeuds déjà vus insere selon f (OUVERTS,n’)
 Cas particuliers :

u11

u4 9
• Si la longueur du chemin n’a pas d’importance on prend k=0
4
12
5
4 6 • Si on veut minimiser le nombre d’étapes, on prend k=1 pour tout arc.
7 3
u1 u14
2
15 3 7 9

4
u3 6 u6
11
La fonction h(n) tente d’estimer le minimum sur tous les chemins de n à
1 16 u15

5 5 12 0 l’état final de la somme des k(n,..) sur le chemin

8 u9
u0 9
6 7
17 u2
15 4 u8 1
La valeur réelle de ce miminum est notée h∗(n)
2 3
7
8 5 9
1
2 u12
3 u5 8 1 6
2 16 10
u7 3
13 2
u13 8 9
u10 2 u16
15
6 6 4 0

84 85

Propriétés formelles des méthodes heuristiques

Plusieurs cas d’heuristiques :

Notations:
nj est un successeur de ni sera noté nj ∈ succ(ni)
heuristique parfaite h est parfaite ssi h(u) = h(v) ↔ h∗(u) = h∗(v)
Γ est l’ensemble des sommets terminaux du graphe de l’espace de
heuristique presque parfaite h(u) < h(v) ↔ h (u) < h (v) ∗ ∗ recherche.

Pni−nj ={ chemins de ni à nj }
heuristique monotone (ou consistante) si pour tout v descendant de
u, h(u) − h(v) ≤ k(u, v) Pn−Γ ={ chemins de n à Γ}

heuristique minorante ou admissible h(u) ≤ h∗(u) de même pni−nj , pn−γ Pn∗i−nj , chemins de coût minimum.

k(ni, nj ) coût d’un chemin minimum de ni à nj .

 Propriétés algorithmiques de A∗
Les coûts de chemin contenant u0 l’état initial où un élément de Γ
portent des noms spéciaux :
Définitions
∗
g (n) = coût minimum des chemins reliant u0 à un sommet n.
Complétude : un algo est dit complet lorqu’il débouche sur une
g ∗(n) = k(u0, n)
solution quand il en existe une.
h∗(n) = coût minimum des chemins allant de n à Γ
Admissibilité : un algorithme est dit admissible lorsqu’il donne une
∗
h (n) = minγ∈Γk(n, γ) solution optimale à chaque fois qu’li en existe une.

Dominance : un algorithme A1 domine un algo A2 si tout sommet

Γ∗ st l’ensemble des buts optimaux γ accessibles depuis u0 par un développé par A1 l’est aussi par A2. A1 domine strictement A2 si
chemin de coût minimum c∗. A1 domine A2 mais A2 ne domine pas A1. (algo plus efficace, car il
c∗ = k∗(u0) développe moins de sommets).

Chaque arc porte une étiquette de coût positif c(ni, nj ) > delta > 0 . Optimalité : un algorithme est optimal dans une classe d’algorithme
s’il domine tous les autres membres de sa classe.

88 89

A∗: recherche optimale d’une solution optimale :

Proposition : Si n∗ est un sommet quelconque sur un chemin optimal
La fonction f de A∗ consiste à ajouter deux parties g(n) et h(n) où :
allant de u0 à γ il doit satisfaire : f ∗(n∗) = c∗.

• g(n)= le coût du chemin courant de u0 à n avec g(u0) = 0 Preuve : soit n∗ ∈ Pn∗−γ , il existe un chemin solution p passant par n
dont le coût est c∗. Sur ce chemin g ∗(n) + h∗(n) ≤ c∗. Si jamais on avait
• h(n)= une estimation du chemin restant h∗(n) avec h(solution)=0 g ∗(n) + h∗(n) < c∗, il existerait un chemin p0 tel que gp0 (n) + h0p(n) < c∗,
ce qui est en contradiction avec l’optimalité de c∗.
Notons γ une solution. Lorsqu’on voudra spécifier les coûts réels de Si n est un sommet qui n’appartient pas à un chemin optimal solution
Pu0−n et de Pn−γ sur un chemin particulier P on écrira gp(n) et hp(n). on a f ∗(n) > c∗
Pour tout chemin p on gp(n) ≥ g ∗(n) et hp(n) ≥ h∗(n)

Lorsque g et h coïncident avec leur valeurs optimales, la fonction f

résultante prend une signification particulière.

Soit f ∗(n) = g ∗(n) + h∗(n), f ∗(n) est le coût optimal pour tous les
chemins solution passant par u0.

En particulier f ∗(u0) = h∗(u0) = g ∗ (γ) = f ∗(γ) = c∗, ∀γ ∈ Γ∗

Terminaison et complétude Preuve optimiste⇒ admissible
A∗ s’arrête toujours sur les graphes finis.

A∗ est complet pour tous les graphes.

les grandes lignes :
∗ ∗
Chaque fois que h(n) est une estimation optimiste de h (n) A retourne
une solution optimale. Cette classe d’heuristiques est dite heuristiques 1. pour toute itération de A∗ il y a un état ouvert qui ∈ à un chemin
admissibles. (cad quand h(n) ≤ h∗(n)). optimal et pour lequel g(u) = g ∗(u)

A∗ est admissible ssi il utilise une heuristique admissible 2. la tête de ouvert û est telle que
Si l’heuristique est parfaite, l’algo convergera immédiatement vers le f (û) ≤ f ∗(u0)
but (sans explorer de branches inutiles).
3. à l’arrêt de l’algorithme, û ∈ Γ, et donc f (û) = f ∗(û)
∗
Si h est minorante alors A trouvera toujours le chemin optimal.
4. f ∗(u0) = minu∈Γ (f ∗(u))
Dans le pire des cas la complexité en temps de A∗ est en 2N , N étant
le nombre de sommets du graphe d’état.
5. à l’arrêt f (û) = f ∗(uˆ0)
2
Si h est minorante la complexité est en N

Si h est monotone la complexité est linéaire en N .

92 93

Détail des preuves Monotone ⇒ admissible

Preuve (1):
monotone: ∀u, vh(u) − h(v) ≤ k(u, v)
soit (u0, u1, ...ut) un chemin optimal. si u1 a été rencontré, il est soit
dans ouvert soit dans fermé. s’il est dans fermé, u2 a été rencontré, il minorante ?: h(u) ≤ h∗(u)
est soit dans ouvert soit dans fermé, .... de même pour les autres ui.
comme ut n’est pas encore développé, il y a un uq avec q < t dans or h∗(u) = k(u, v1) + k(v1, v2) + ... + k(vf −1 , vf ) avec vf ∈ Γ
ouvert. le chemin (u0, ...uq ) est connu, et optimal de u0 à uq . donc et h(u) = h(u) − h(v1) + (h(v1) − h(v2)) + ... + h(vf −1 ) − h(vf ) (car
g(uq ) = g ∗(uq ) h(vf ) = 0)
Preuve (2)
si h monotone, pour tout vi, (h(vi) − h(vi+1)) ≤ k(vi, vi+1)
∗ ∗ ∗ ∗
f (û) ≤ f (uq ) = g(uq ) + h(uq ) ≤ g (uq ) + h (uq ) = f (uq ) = f (u0) d’où h(u) ≤ k(u, v1) + k(v1, v2) + ... + k(vf −1 , vf ) = h∗(u)

cqfd
Preuve (5) à l’arrêt, f (û) ≤ f ∗(uˆ0) (2) et donc d’après (3) f ∗(û) = f (û)
et f ∗(û) ≤ f ∗(uˆ0)
d’après (4) comme û ∈ Γ on a f ∗(uˆ0) ≤ f ∗(û)
d’où (5).
 Monotone ⇒ f toujours croissante Exemple d’application de A∗: le taquin.

On veut minimiser la longueur des solutions. Tous les arcs de l’espace

f (n) = g(n) + h(n) d’état auront donc un coût associé de 1.

n’ successeur de n : L’heuristique h choisie est :

f (n0) = g(n0) + h(n0) = g(n) + k(n, n0) + h(n0) h(n)=distance de manatthan(n)+3*score de déplacement(n).

d’où f (n) − f (n0) = h(n) − h(n0) − k(n, n0) ≤ 0 score de déplacement de n= somme des scores des cases du taquin:
- le pavé central a une valeur de 1
- un pavé non central vaut 0 si son successeur se trouve juste après
lui en tournant dans le sens des aiguilles d’une montre
- tous les autres valent 2

Exemple:

1 3 4
manhattan=4
8 2
score de dep=7
7 6 5

96 97

Arbres de jeux Les jeux d’opposition

Plan: • deux joueurs, chaque joueur à un certain nombre de coups possibles

⇒ arbre de jeux, niveau impair= joueur A, niveau pair=joueur B

• Représentation • on suppose que les joueurs sont rationnels et ont la même stratégie

• Le minmax • Comment trouver le meilleur coup dans une situation donnée ?

Si on peut développer l’arbre en entier, on cherche une suite de
• Amélioration du minmax: alpha-beta coups ("stratégie") qui mène toujours à une situation de victoire.
Si elle existe le premier joueur peut toujours gagner
Si elle n’existe pas, on parle de jeu à somme nulle.

• en pratique on ne peut pas développer l’arbre entier

→ on s’arrête à une profondeur donnée et on évalue les situations
avec une heuristique (encore !)

• On cherche alors à maximiser ses chances d’arriver dans une

"bonne" situation
 Exemple de stratégie: le minmax Un “vrai” jeu : le morpion

MAX
heuristique: h(n)=(nb de lignes faisables par A)-(nb de lignes faisables
par B)

MIN

MAX

MIN
2 3 5 9 0 7 4 2 1 5 6

100 101

Amélioration du minmax: l’alpha-beta Alpha-beta: schéma général

ne pas explorer de branche inutile ... noeud max s (s>=a)

a
s = max(f ils) donc s ≥ a
 Alpha-beta: schéma général Alpha-beta: schéma général

noeud max s (s>=a) noeud max s (s>=a)

a a y<=z noeud min

y<=z noeud min

(coupe si z<=a)

z
z

y = min(f ils) donc y ≤ z si z ≤ a, on a en fait y ≤ z ≤ a ≤ s

⇒ inutile de regarder les autres fils de y

104 105

Alpha-beta: schéma général Alpha-beta: exemple

A chaque niveau on garde 2 valeurs, et l’intervalle [α, β] contraint la exos avec autre arbre, 1) minmax, 2) a-b de G a D 3) a-b de D à G
suite:

• une valeur choisie au niveau max devient la borne sup (le beta) du
niveau min au-dessus

• une valeur choisie au niveau min devient la borne inf (alpha) du

niveau au-dessus.

• si la valeur est en dehors, on peut arreter l’exploration du noeud père

• initialement, α = β = ∞
 Recherche locale dans les problèmes à forte Quelques Problèmes des méthodes exactes/complètes
combinatoire
1. Les méthodes complètes/exactes explorent de façon systématique
l’espace de recherche. → ne marche pas dans de nombreux
problèmes à cause explosion combinatoire.

2. ces méthodes sont généralement à base de recherche arborescente

→ contrainte par l’ordre des noeuds dans l’arbre
→ impossibilité de compromis qualité/temps (6= algo “anytime”)

Or il y a souvent des cas ou on peut se contenter d’une solution

approchée, pourvu qu’elle soit suffisament “bonne”. (ex du TSP, on
ne veut pas forcement le minimum mais quelque chose d’assez court,
par exemple <= distance donnée).

108 109

Un autre principe: les méthodes incomplètes Une famille de méthodes incomplètes: les méthode
“locales”
• si on ne peut prouver que l’on a la meilleure solution,
Le principe d’une recherche locale est de
• et si ce n’est pas grave si on trouve un optimum le plus rapidement
possible, de façon assez bonne / à un critère déterminé. 1. partir d’une solution sinon approchée du moins potentiellement
bonne et d’essayer de l’améliorer itérativement.
Pour améliorer une solution on ne fait que de légers changements
on peux adopter deux types de stratégie : (on parle de changement local, ou de solution voisine).

• garder une méthode complète et stopper après un temps déterminé 2. relancer la méthode plusieurs fois en changeant le point de départ
(mais suivant les problèmes ça n’est pas toujours possible) pour avoir plus de couverture

• plonger dans l’arbre de recherche avec des heuristiques sans jamais 3. tout problème est considéré comme un problème d’optimisation
revenir en arrière (mais: comment être sur qu’on va trouver vite une (même les problèmes de satisfaction : le coût à optimiser est alors le
bonne solution ?) nombre de contraintes insatisfaites).
 Quelques définitions Un algorithme de recherche locale typique

A* := creer une solution()

une solution est une affectation de toutes les variables du problème. pour tout t=1 a max essais faire
A:=nouvelle solution()
une solution optimale est une solution de coût minimal pour tout m=1 a max mouvements faire
A’:=choisir voisin(A)
d := (f(A’)-f(A))
un mouvement est une opération élémentaire permettant de passer
si acceptable(d) alors
d’une solution à une solution voisine (exemple: changer la valeur
A:=A’
d’une variable, échanger deux variables).
si f(A*)>f(A) alors
A*:=A
le voisinage d’une solution est l’ensemble des solutions voisines, c’est retourner A*,f(A*)
à dire l’ensemble des solutions accessibles par un mouvement (et un
seul). f: fonction à optimiser

un essai est une succession de mouvements.

une recherche locale est une succession d’essais.

112 113

Les paramètres à régler Exemples de recherches locales

• max essais : le nombre d’essai à réaliser le hill-climbing Aussi appelé descente en gradient suivant le sens de
l’optimisation (min ou max recherché).
• max mouvements : ... choisir un voisin : choix aléatoire dans le voisinage courant.
acceptable : seulement s’il il y a une amélioration (d ≤ 0).
• creer une solution : génère une solution (en général aléatoirement) méthode opportuniste

• nouvelle solution : même chose la version gloutonne (greedy)

choisir un voisin : après avoir déterminé l’ensemble des meilleures
solutions voisines de la solution courante (exceptée celle-ci), on en
• choisir un voisin : choisit dans le voisinage de la solution courante
choisit une aléatoirement.
(c’est généralement ce qui caractérise principalement une méthode
acceptable : toujours.
de recherche locale)
il peut y avoir des dégradations (provisoires) de solutions.
• acceptable: accepte ou pas la nouvelle solution générée
minimisation de conflits Les classiques en question(s)
choisir un voisin :
1. déterminer l’ensemble des variables en conflit (eg. liées dans un Comportement général :
ensemble de contraintes).
2. choisir une de ces variables au hasard.
1. une majorité de mouvements améliorent la solution courante.
3. déterminer l’ensemble de ses meilleures valeurs (recherche
complète ou pas ?).
2. le nb d’améliorations devient de plus en plus faible.
4. en choisir une au hasard, affecter la variable.
5. retourner la solution.
3. il n’y a plus d’améliorations : on est dans un optimum, qui peut être
acceptable : toujours. local.
il ne peut y avoir de dégradation de solutions (→ attention aux
optimum locaux).

116 117

Les questions à se poser (1) Illustration (1)

• quand faut-il s’arrêter ? 4

g(x)

3
• faut-il être opportuniste ou gourmand ?
2

• comment ajuster les paramètres ? 1

0
• comment comparer les performances de deux méthodes différentes
? (qualité de la solution vs. temps consommé) -1

-2

-3

-4
-5 -4 -3 -2 -1 0 1 2 3
 Illustration (2) Illustration (3)

0.8
f(x)

0.6

0.4

0.2

-0.2

-0.4

-0.6

-0.8
-10 -5 0 5 10

120 121

Illustration (4) Illustration (5)

en montant le plus tôt possible en suivant la pente la plus forte

 Les questions à se poser (2) Exercice: adaptation au TSP

Pour le critère d’arrêt :

• initialisation ?
• pour l’essai en cours : nb de mouvements max ?
comment détecter un optimum local ?
• quel voisinage ? (échange de villes, échange d’arcs)
• pour la recherche elle-même : le nb max d’essai ?
coût de la solution convenable ? • complexité selon le choix opportuniste/gourmand
limite de temps atteinte.

Avidité ou opportuniste :

• si aucune recherche d’amélioration : comment trouver les bonnes

solutions ?

• si recherche d’amélioration, comment éviter optimum local ?

124 125

Amélioration des classiques : l’approche probabiliste Amélioration des classiques : le Tabou

Pour éviter d’être coincé dans un optimum local, on peut ajouter du bruit basée sur une recherche par gradient
: une part de mouvements aléatoires pendant une recherche classique.
• choix dans le voisinage
Principe :

• possibilité de détérioration de la solution courante

• avec une proba p, faire un mouvement aléatoire.
• Pour améliorer la recherche, on mémorise les k dernières solutions
courantes et on interdit le retour sur une de ces solutions.
• avec une proba 1 − p, suivre la méthode originale.
• on autorisera en plus toujours un mouvement conduisant à une
meilleure solution que la meilleure obtenue auparavant.
Reste le problème : comment régler p ?
En pratique, au lieu de mémoriser les k dernières solutions courantes
(parfois trop coûteux en temps et mémoire), on mémorise les k derniers
mouvements (plus restrictif mais peu coûteux en temps)
 L’algorithme Exercice

A ← solution initiale()
Développer l’algorithme avec |T ] = 1, puis |T | = 3, puis en conservant
Am ← A
les mouvements au lieu des états.
T←Ø
tantque non(condition de fin) faire
C ← voisinage(A)-T 0101 0100 1100 1101
0 1 9
Y ← min pour f sur C 4
si f(Y)≥f(A) alors
T ← T ∪{A} 0001 0000 1000 1001
2 8 7 9
si f(Y)<f(Am) alors
Am ← Y 0011 0010 1010 1011
3 9 5 6
A←Y
retourner Am, f(Am) 0111 0110 1110 1111
4 6 3 2
La condition de fin est soit une limite en temps ou en itération, soit une
condition de non amélioration de la solution.

128 129

Amélioration des classiques : le recuit simulé A* := creer une solution()

A := creer une solution()
T := T initiale
méthode inspirée par une analogie avec un phénomène de physique tantque (T > Tmin) faire
statistique, l’obtention d’un état stable d’un métal. pour m:=1 a m:=longueur des plateaux faire
A’:=choisir voisin(A)
En termes de recherches locales, la probabilité d’acceptation d’un
d := (f(A’)-f(A))
mouvement de A à A’ :
si d≤0 alors
p(φ(A0) − φ(A)) = 1 si φ(A0) ≤ φ(A)
−(φ(A0 )−φ(A)) A:=A’
p(φ(A0) − φ(A)) = e T si φ(A0) > φ(A) sinon
(issu de lois thermodynamiques) si vrai avec proba p = e−d/T alors
A:=A’
Principe : on simule le processus de recuit des métaux :
si f(A*)>f(A) alors
A*:=A
• on part d’une température T élevée (instabilité/ loin de l’optimum). T:=T*α
retourner A*,f(A*)
• on refroidit lentement par plateaux (réduction du bruit).
 Réglage des paramètres Avantages des recherches locales

• valeur de T initiale : si la valeur T init permet d’accepter x% des

configurations de départ, alors on la garde sinon on la double et on • méthodes rapides (et temps paramétrable) ;
recommence (x au moins plus de 50, certains auteurs : 80).
• faciles à implémenter ;
• la durée des paliers (longueur du plateau) : le plus simple est
de le borner par le nombre de configurations atteignables en un
mouvement élémentaire. là encore subtilités possibles • donnent souvent de bonnes solutions ;

• la décroissance de la température : le plus simple est facteur • fonctionnement intuitif

constant, de l’ordre de 0.9 / 0.95 (décroissance lente). pour raffiner,
le réglage se joue entre ce paramètre (+/- rapide) et le précédent
(plateau +/- long).

• condition d’arrêt : la température mini ; soit 0 mais pas très efficace,

soit quand améliorations très petites (très empirique).

132 133

Inconvénients des recherches locales Les Algorithmes génétiques

Les algorithmes génétiques sont une forme de recherche locale qui se

• manque de modélisation mathématiques (chaque cas est différent : démarque un peu des méthodes précédentes. Le principe est inspiré
il faut adapter la recherche à chaque problème particulier) d’une analogie biologique : on considère un ensemble de solutions
comme une population d’individus susceptible d’évoluer et de se
• difficiles à paramétrer (=bidouille !) croiser, en suivant certaines règles proches de la sélection naturelle.

• aucune évaluation de la distance à l’optimum (pas une approximation, L’intérêt principal est de couvrir l’espace de recherche plus largement.
trouve au pire un optimum local qui n’a rien à voir)
Trois opérations sont réalisées successivement sur la population :
• la sélection des meilleures solutions/individus en proportion/ de leur
adaptattion ou avec une proba proportionnelle ;

• le croisement d’individus entre eux ;

• la mutation éventuelle d’un ou de plusieurs individus : changements

aléatoires ;
 L’algorithme Quelques caractéristiques des Algorithmes génétiques
– Historiquement, un individu était codé par une chaîne de bits (son
population initiale P avec n solutions “patrimoine génétique”). En pratique chaque problème appelle un
pour g:=1 a max générations faire codage particulier.
C := vide – La sélection se base sur l’adaptation (ou fitness) d’un individu,
pour m:=1 a n par pas de 2 faire donnée par une fonction d’utilité (on cherche à maximiser l’adaptation
parent1 := selection(P) des individus).
parent2 := selection(P)
enfant1,enfant2:=croisement(parent1,parent2) – La sélection permet de focaliser la recherche sur les zones
C:= C + mutation(enfant1) + mutation(enfant2) intéressantes, alors que mutations et croisements permettent de
P := C diversifier la recherche (on retrouve, plus lâchement, le paradigme des
recherches locales).

– Les algorithmes génétiques sont semblables à des recherches locales

effectuées +/- en parallèle.

– Utilité dans le cas de problèmes dont on ignore la structure (espace

de recherche mal connu par exemple

136 137

Quelques inconvénients des algorithmes génétiques Conclusion

Les problèmes techniques importants sont : les méthodes incomplètes fournissent un ensemble de résolutions
empiriques variées, parfois trop, car l’absence de modélisation les rend
• celui du codage des configurations en binaire difficiles à adapter d’un problème à un autre (bricolage...).

Par contre elles sont à peu près indifférentes à la taille du problème,

• celui de la recombinaison de solutions pour garder quelque chose de et donnent de bons résultats (approchés) à condition de bien les
pas trop loin de l’optimum paramétrer.

• performances (temps, mémoire) → peuvent fournir un bon complément aux méthodes complètes.