Rappels de Logique

Dans tout problème informatique on a besoin de représenter et manipuler des

données. En intelligence artificielle ces données s’appellent connaissances. La
représentation de la connaissance en IA par de simples moyens traditionnels tels que
tableaux, structures, fichiers etc.... s'avère inefficace et/ou trop difficile. Le calcul des
prédicats est un langage formel au moyen duquel des expressions très diverses
peuvent être représentées. (Il existe d'autres formalismes de représentation de
la connaissance). Avant de définir ce langage d’ordre1 (calcul des prédicats), nous
définissons le langage de calcul d'ordre 0 ( ou logique propositionnelle).

Partie 1 : Logique propositionnelle :

La logique propositionnelle est la plus simple logique symbolique. On s’intéresse à
des expressions dont chacune a la valeur vraie ou fausse mais pas les 2 en même temps.

Syntaxe :
Définition Une proposition est une expression déclarative qui peut avoir la valeur
vraie ou fausse. On représente ces propositions par des symboles P,Q,R,F1,X, ... etc. On
les appelle des atomes ou formules atomiques ou proposition.
Exemple La connaissance «Ali est ingénieur» peut être représentée par une proposition
P.

Définition : On définit un littéral comme étant un atome ou sa négation (P ou ¬P).

Exemple précédent La connaissance «Ali n’est pas ingénieur» peut être représentée
par ¬P
.
Formules : A partir des propositions (littéral) on peut former de nouvelles expressions
appelées formules, en utilisant les connecteurs logiques standards: ¬(négation),
^ (conjonction et), v (disjonction ou),  (implication) et ⇔(l'équivalence).

Définition : Une formule en logique propositionnelle est définie comme suit :

-Tout atome (formule atomique / proposition) est une formule.
-Si P et Q sont des formules alors ¬P, PvQ, P/\Q, PQ, P ⇔ Q sont des formules.

Exemple : la connaissance« Ali est ingénieur et Mohamed est architecte » peut être
représentée par P ∧ Q où P représente « Ali est ingénieur » et Q représente « Mohamed
est architecte »

Il est parfois nécessaire d'insérer des parenthèses pour définir des priorités
entres ces différents connecteurs. L'ordre de priorité de ces connecteurs est donné par
l'ordre décroissant suivant : ¬ ∧ ∨  ⇔. Lorsque le même connecteur se répète

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 2

la priorité est de gauche à droite.
Exemple : P ⇔ Q ∧ R est équivalente à P ⇔ (Q∧R)
P  Q ∧ ¬R ∨ S est équivalente à P ((Q ∧(¬R)) ∨ S)
P ∧ Q ∧ R ∧ S est équivalente à ((P ∧ Q) ∧ R) ∧ S

Sémantique:
La sémantique définit les règles de détermination de la valeur de vérité d'un énoncé
dans le cadre d'un modèle particulier. Dans cette logique, le modèle donne la valeur de
vérité (Vrai ou Faux) de chaque symbole propositionnel.

Valeur de vérité : La valeur de vérité (vraie/fausse) d’une formule dépend des valeurs
de vérité de ses atomes. Cette valeur de vérité est calculée en utilisant le tableau:
G H ¬G G∧H GvH G H G⇔⇔H
V V F V V V V
V F F F V F F
F V V F V V F
F F V F F V V

Définition: L'affectation des valeurs de vérité aux atomes composant une formule est
appelée interprétation. Pour une formule composée de n atomes on peut avoir 2n
interprétations possibles.

Définition : Une formule G est dite vraie sous une interprétation I ssi sa valeur de
vérité est évaluée à Vraie sous cette interprétation I. On dit que I est un modèle de G

Définition : Si une formule est toujours Vraie ∀ l'interprétation I alors cette

formule est dite valide et est appelée une tautologie.

Définition : Si une formule est toujours Fausse ∀ l'interprétation I alors cette

formule est dite inconsistante (ou insatisfiable).

Propriétés :
- Une formule est valide ssi sa négation est inconsistante
- Une formule est inconsistante ssi sa négation est valide
-Une formule est invalide (respectivement consistante) ssi il existe au moins
une interprétation sous laquelle la formule est fausse (respectivement vraie).
- Si une formule est valide alors elle est consistante mais pas vice versa.
- Si une formule est inconsistante alors elle est invalide mais pas vice versa.

Exemple: P ∧ ¬P est inconsistante (donc invalide)

P ∨ ¬P est valide (donc consistante)

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 3

Corollaire :le nombre d'interprétation d'une formule étant fini, on peut
toujours décider si une formule, est valide ou non, en examinant toutes
les interprétations possibles. L'algorithme pour déterminer la valeur de vérité
d'une formule de n atomes a une complexité de l'ordre 0(2 n ). Cet
algorithme est valide et complet puisqu'il a un nombre fini de possibilités.

Forme Normale (FN) en logique propositionnelle

Il est utile de transformer une formule en une autre formule équivalente plus
simple, formée de conjonction de disjonction (ou de disjonction de conjonction)
de littéraux appelée Forme Normale Conjonctive FNC (ou Disjonctive FND
respectivement) .

Définition : 2 formules F et G sont dites équivalentes notée F ≡ G ssi les valeurs

de vérité de F et G sont identiques ∀ l'interprétation I de F et de G.

Propriétés sur les formules :

1) F ⇔ G ≡ (F  G) ∧ (G  F)
2) F  G ≡ ¬F ∨ G
3) F ∨ ( G ∧ H) ≡ (F ∨ G) ∧ (F ∨ H) F ∧ (G ∨ H) ≡ (F ∧ G) ∨ (F ∧ H)
4) ¬(¬G) ≡ G
5) ¬(F ∨ G) ≡ ¬F ∧ ¬G ¬(F ∧ G) ≡ ¬F ∨ ¬G
6) F ∨ Faux ≡ F F ∧ Faux ≡ Faux F ∨ Vraie ≡ Vraie F ∧ Vraie ≡ F
7) F ∨ ⌐F ≡ Vraie F ∧ ⌐F ≡ Faux
8) X1 ∧ X2 ≡ X2 ∧ X1 X1 ∨ X2 ≡ X2 ∨ X1
9) (X1 ∧ X2) ∧ X3 ≡ X1 ∧ (X2 ∧ X3) (X1 ∨ X2) ∨ X3 ≡ X1 ∨ (X2 ∨ X3)
10) X1  X2 ≡ ¬X2  ¬X1

Toute formule peut être transformée sous FN en utilisant les règles 1, 2, 4 , 5, 6

et 7 éventuellement puis une des règles 3(3a pour pour FNC ou 3b pour FND)

Conséquence logique: On a souvent à décider si une connaissance provient

d’autres connaissances. Ceci mène au concept de conséquence logique,

Définition: Soient des connaissances représentées par les formules FI,

F2,..., Fn et G. la formule G est dite conséquence logique de l'ensemble des
formules FI, ... Fn (ou G provient logiquement de l’ensembleF1, F2, …, Fn) ssi toute
interprétation I dans laquelle F1 ∧…∧ Fn est vraie alors G est aussi vraie. Les Fi
sont appelés les prémisses de G. On la note par {F1, . . . , Fn} |= G. Autrement dit tout
modèle de {F1,...,Fn} est un modèle de G.

Théorème1: Soient des formules FI, ... Fn et G. G est une conséquence

logique de FI, F2, ... Fn ssi la formule ((F1 ∧ F2 ∧…∧ Fn)  G) est valide.

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 4

Théorème2: G est conséquence logique de F1,…Fn ssi (F1∧…∧Fn∧¬G) est
inconsistante.
Preuves: exercice

Si G est une conséquence logique de l'ensemble FI, F2,... Fn alors la formule

((F1 ∧ .... ∧Fn) G) est dite un théorème et G est appelé sa conclusion.

Exercice: Montrer que ¬P est conséquence logique de { P Q , ¬Q} (Utiliser la définition

ou l’un des 2 théorèmes précédents)

Partie2 : Logique d’ordre 1- calcul des prédicats d’ordre 1 :

Soit à représenter en logique propositionnelle la déclaration : « si Ali est le père de
Mohamed et Mohamed est le père de Said alors Ali est le grand père de Said ». On peut
la représenter en logique propositionnelle. Supposons qu’on veuille représenter
l’expression « si x est le père de y et y est le père de z alors x est le grand parent de z »
où x, y et z sont des variables pouvant prendre des valeurs de noms de personne, on ne
peut pas la représenter en logique propositionnelle.

Nous allons définir un langage plus expressif que la logique propositionnelle. Il est
construit sur des objets et des relations. Les éléments de base de la logique du 1er ordre
sont les symboles qui représentent les objets, les fonctions et les relations entre objets.

Syntaxe : Les composantes élémentaires dans ce langage sont les prédicats pour
désigner des relations, les variables pour désigner des entités variables, les fonctions
pour désigner des fonctions et les constantes pour désigner des entités constantes,
séparés par des « , » et entourés par des « (, ) » ainsi que les connecteurs logiques et les
quantificateurs.  formules bien formées (fbf)

Définitions: Un Terme: est une expression logique qui renvoie à un objet.

- Une constante est un terme utilisée pour exprimer des objets (entités) constant(e)s,
- Une variable est un terme, utilisée pour représenter des entités variables,
- Si f est un symbole de fonction (foncteur) et t1, ..., tn sont des termes alors f(t1,...,tn)
est un terme. f est appliquée à un ensemble de termes pour donner un nouveau terme.

Une Formule Atomique : Une formule atomique est représentée par p(t1, ...., tn) où p
est un symbole de prédicat et les ti des termes. Un prédicat est utilisé pour représenter
une relation entre des termes dans un certain contexte. N est appelée l’arité du prédicat.
Exemple: La phrase Ali est allé à l’université peut etre représentée par:
est_allé_a(Ali, université), ali et université sont constantes, est_allé_a et une relation.

Remarque : On remarque qu’une formule atomique et le terme fonction ont la même

syntaxe, mais ils auront des sémantiques différentes.

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 5

Théorème2: G est conséquence logique de F1,…Fn ssi (F1∧…∧Fn∧¬G) est
inconsistante.
Preuves: exercice

Si G est une conséquence logique de l'ensemble FI, F2,... Fn alors la formule

((F1 ∧ .... ∧Fn) G) est dite un théorème et G est appelé sa conclusion.

Exercice: Montrer que ¬P est conséquence logique de { P Q , ¬Q} (Utiliser la définition

ou l’un des 2 théorèmes précédents)

Partie2 : Logique d’ordre 1- calcul des prédicats d’ordre 1 :

Soit à représenter en logique propositionnelle la déclaration : « si Ali est le père de
Mohamed et Mohamed est le père de Said alors Ali est le grand père de Said ». On peut
la représenter en logique propositionnelle. Supposons qu’on veuille représenter
l’expression « si x est le père de y et y est le père de z alors x est le grand parent de z »
où x, y et z sont des variables pouvant prendre des valeurs de noms de personne, on ne
peut pas la représenter en logique propositionnelle.

Nous allons définir un langage plus expressif que la logique propositionnelle. Il est
construit sur des objets et des relations. Les éléments de base de la logique du 1er ordre
sont les symboles qui représentent les objets, les fonctions et les relations entre objets.

Syntaxe : Les composantes élémentaires dans ce langage sont les prédicats pour
désigner des relations, les variables pour désigner des entités variables, les fonctions
pour désigner des fonctions et les constantes pour désigner des entités constantes,
séparés par des « , » et entourés par des « (, ) » ainsi que les connecteurs logiques et les
quantificateurs.  formules bien formées (fbf)

Définitions: Un Terme: est une expression logique qui renvoie à un objet.

- Une constante est un terme utilisée pour exprimer des objets (entités) constant(e)s,
- Une variable est un terme, utilisée pour représenter des entités variables,
- Si f est un symbole de fonction (foncteur) et t1, ..., tn sont des termes alors f(t1,...,tn)
est un terme. f est appliquée à un ensemble de termes pour donner un nouveau terme.

Une Formule Atomique : Une formule atomique est représentée par p(t1, ...., tn) où p
est un symbole de prédicat et les ti des termes. Un prédicat est utilisé pour représenter
une relation entre des termes dans un certain contexte. N est appelée l’arité du prédicat.
Exemple: La phrase Ali est allé à l’université peut etre représentée par:
est_allé_a(Ali, université), ali et université sont constantes, est_allé_a et une relation.

Remarque : On remarque qu’une formule atomique et le terme fonction ont la même

syntaxe, mais ils auront des sémantiques différentes.

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 5

Un littéral: Un littéral est défini comme une formule atomique ou sa négation.

Formule Bien Formée (fbf):

- Toute formule atomique est une fbf,
- Toute conjonction avec ∧ (et) de fbf est une fbf,
- Toute disjonction avec ∨ (ou) de fbf est une fbf,
- La négation (¬) d’une fbf est une fbf,
- Si p et q sont 2 fbfs alors p  q, p ⇔ q sont des fbf,
Exemple : Soit la phrase, Ali a un chien et Mohamed aime le chat. Cette phrase peut
être représentée par : a(Ali, chient) ∧ aime(Mohamed,chat).
Les quantificateurs
Une formule atomique P(…x…..), où x est une variable qui apparait dans la formule,
peut avoir la valeur Vraie pour toute valeur prise par x ou pour au moins une valeur
prise par x d’un certain domaine. Ces notions sont exprimées en utilisant les
quantificateur ∀ et ∃. Une formule contenant le quantificateur universel (∀ x) devant
une formule P(….x …..) a la valeur Vraie pour toutes les affectations de x aux valeurs
de ce domaine. Une formule contenant le quantificateur existentiel (∃x) devant une
formule P( ….x…..) a la valeur Vraie pour une affectation de x à au moins une valeur
du domaine. On dit que ces formules sont quantifiées.

Exemple : La phrase « Il y a un enseignant qui assure le cours » peut être représentée

par la formule: (∃ x) [enseignant(x) ∧ assure(x, cours)].

L’ordre des quantificateurs est important:

(∀x) ((∃y) Aime(x, y)) « tout le monde aime quelqu’un »
(∃x) ((∀y) Aime(x, y)) « il y a quelqu’un qui aime tout le monde »
(∀x) ((∃y) Aime(y, x)) « Tout le monde est aimé par quelqu'un »
(∃x) ((∀y) Aime(y, x)) « Il y a quelqu'un qui est aimé par tout le monde »

Définition d’une Variable liée et Variable libre

La variable x dans une formule (∀x)P(..x..) ou (∃x)P(..x..) est une variable quantifiée,
elle est dite liée. La portion de la formule à laquelle le quantificateur s’applique est
appelée portée du quantificateur. Toute variable qui n’est pas liée est libre.

Remarque: On ne s’intéressera qu’aux expressions dont toutes les variables sont liées.

Sémantique:
Définir la sémantique ≡ définir la notion d’interprétation, pour donner un sens à une
formule atomique. Pour définir cette sémantique :
- On définit un domaine d’interprétation (où on interprète les entités syntaxiques):
- A chaque symbole de prédicat on lui attribue une relation dans ce domaine,
- A chaque symbole de fonction (foncteur) on lui attribue une fonction dans ce domaine,

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 6

- A chaque symbole de constante on lui attribue une constante dans ce domaine,
Propriétés des fbf
Soit une interprétation I. Les valeurs de vérité des expressions ne contenant pas de
variables peuvent être calculées en utilisant la table de la partie 1 ci-dessus.

En plus des propriétés ci-dessus de la logique propositionnelle, on a les propriétés :

¬ [(∃ x)P(x)] ≡ (∀ x) ¬ P(x) ¬ [(∀ x) P(x)] ≡ (∃ x) ¬P(x)
(∀ x)[P(x)∧Q(x)] ≡ (∀ x)P(x) ∧ (∀ y) Q(y) (∃x)[P(x)∨Q(x)]≡(∃x)P(x)∨(∃y)Q(y)
(∀ x)P(x) ≡ (∀ y)P(y) (∃ x)P(x) ≡ (∃ y)P(y)

Remarque : Attention
(∀ x)[P(x)∨Q(x)] ≠ (∀ x)P(x) ∨ (∀ y) Q(y) (∃x)[P(x)∧Q(x)] ≠ (∃x)P(x) ∧ (∃y)Q(y)

Définition :
Si une fbf a la valeur de vérité Vraie (respectivement Fausse) pour toutes les
interprétations possibles, alors elle est dite Valide (respectivement inconsistante). Les
fbf (sans variables) valides sont appelées tautologies.

Si une même interprétation fait que chaque fbf dans un ensemble de fbf a la valeur
Vraie alors nous disons que cette interprétation satisfait l’ensemble des fbf.

On avait souligné qu’une fbf peut contenir des quantificateurs, il est parfois impossible
de pouvoir déterminer la valeur de vérité de cette fbf (sur les domaines infinis par
exemple). Il est démontré qu’il est impossible de trouver une méthode générale qui nous
permet de décider de la validité de fbf contenant des quantificateurs. Cependant il est
possible de déterminer la valeur de vérité de certaines fbf quantifiées. On parle de sous-
classes décidables. Le calcul des prédicats est semi-decidable.

Définition d’une conséquence logique: Une fbf X est une conséquence logique d’un
ensemble S de fbf si toute interprétation satisfaisant S satisfait X(idem logique prop).

Règles d’inférence
Dans ce langage des prédicats, il existe des règles d’inférence qui peuvent être
appliquées à certaines fbf pour produire de nouvelle fbf, Comme par exemple:

- Le Modus Ponens: A partir de W1 et W1  W2 on infère W2

- La Spécialisation universelle: A partir de (∀x)W(x) on infère W(A) où A est un
symbole de constante.
- Combinaison des 2 règles précédentes: A partir de (∀ x)[W1(x)  W2(x)] et W1(A)
on infère W2(A)

Les fbf inférées sont appelées des théorèmes. La séquence d’application des règles
d’inférence utilisées dans la dérivation constitue la démonstration de ce théorème.

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 7

Système de Règles d’inférence sain :
Un système de règles d’inférence est dit sain si tout théorème dérivable de tout
ensemble de fbf est conséquence logique de cet ensemble de fbf.

Système de Règles d’inférence complet : Un système de règles est complet si toutes

les fbf qui découlent logiquement de tout ensemble de fbf sont aussi des théorèmes
dérivables de cet ensemble.

Unification :
Dans la règle d’inférence combinée précédente (3eme exemple) il a été nécessaire de
trouver la substitution « la variable x est remplacée par la valeur A » pour rendre W1(x)
et W1(A) identique. Ce processus est appelé Unification. L’unification de 2 entités
syntaxiques consiste à trouver par quoi remplacer des variables de ces 2 entités pour les
rendre identiques syntaxiquement. Il existe des algorithmes d’unification. Avant de
détailler ce processus nous décrivons ce qu’est la substitution.

Définition de la substitution: Une substitution σ est une application σ: terme terme,

qui est l’identité sauf en un certain nombre de variable. Elle est notée par l’ensemble
{<Xi/ti>}. Xi est une variable, ti est un terme. (on la note des fois par <Xi,ti>)

L’instanciation t’ d’un terme t est définie comme étant l’application d’une substitution
σ à t. On la note par t’ = σ(t). Elle consiste à remplacer dans t, xi par ti.
Exemple :
Soit la fbf P(x, f(y), B) où x, y sont des variables, B est une constante et f une
fonction. On peut obtenir les instances suivantes:
P(z, f(w), B) par la substitution {x/z, y/w} (Renommage)
P(x, f(A), B) par la substitution {y/A}
P(C, f(A), B) par la substitution {x/C, y/A} (appelée Instance Close - pas de variable)

Remarque: Dans une substitution {Xi/ti} toutes les variables sont distinctes. On
suppose aussi que la variable Xi n’apparaît pas dans ti.

Composition de substitution :
La composition de deux substitutions σ1={x1/t1, x2/t2,...,xn/tn} et σ2={y1/t'1,...,ym/t'm},
notée σ1oσ2 , est obtenue en 3 étapes:
● appliquer σ2 aux termes ti de σ1
● retirer de σ2 les éléments vi/t'i tels que vi est une variable xj de σ1
● rassembler les couples obtenues en 1 et 2

Exemple : σ1 = {x/f(y) , y/z} et σ2 = {x/a , y/b , z/y}

● la première étape donne {x/f(b) , y/y}
● la deuxième donne σ2={z/y}

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 8

Système de Règles d’inférence sain :
Un système de règles d’inférence est dit sain si tout théorème dérivable de tout
ensemble de fbf est conséquence logique de cet ensemble de fbf.

Système de Règles d’inférence complet : Un système de règles est complet si toutes

les fbf qui découlent logiquement de tout ensemble de fbf sont aussi des théorèmes
dérivables de cet ensemble.

Unification :
Dans la règle d’inférence combinée précédente (3eme exemple) il a été nécessaire de
trouver la substitution « la variable x est remplacée par la valeur A » pour rendre W1(x)
et W1(A) identique. Ce processus est appelé Unification. L’unification de 2 entités
syntaxiques consiste à trouver par quoi remplacer des variables de ces 2 entités pour les
rendre identiques syntaxiquement. Il existe des algorithmes d’unification. Avant de
détailler ce processus nous décrivons ce qu’est la substitution.

Définition de la substitution: Une substitution σ est une application σ: terme terme,

qui est l’identité sauf en un certain nombre de variable. Elle est notée par l’ensemble
{<Xi/ti>}. Xi est une variable, ti est un terme. (on la note des fois par <Xi,ti>)

L’instanciation t’ d’un terme t est définie comme étant l’application d’une substitution
σ à t. On la note par t’ = σ(t). Elle consiste à remplacer dans t, xi par ti.
Exemple :
Soit la fbf P(x, f(y), B) où x, y sont des variables, B est une constante et f une
fonction. On peut obtenir les instances suivantes:
P(z, f(w), B) par la substitution {x/z, y/w} (Renommage)
P(x, f(A), B) par la substitution {y/A}
P(C, f(A), B) par la substitution {x/C, y/A} (appelée Instance Close - pas de variable)

Remarque: Dans une substitution {Xi/ti} toutes les variables sont distinctes. On
suppose aussi que la variable Xi n’apparaît pas dans ti.

Composition de substitution :
La composition de deux substitutions σ1={x1/t1, x2/t2,...,xn/tn} et σ2={y1/t'1,...,ym/t'm},
notée σ1oσ2 , est obtenue en 3 étapes:
● appliquer σ2 aux termes ti de σ1
● retirer de σ2 les éléments vi/t'i tels que vi est une variable xj de σ1
● rassembler les couples obtenues en 1 et 2

Exemple : σ1 = {x/f(y) , y/z} et σ2 = {x/a , y/b , z/y}

● la première étape donne {x/f(b) , y/y}
● la deuxième donne σ2={z/y}

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 8

 ● la troisième étape donne σ1oσ2 ={x/f(b) , z/y} (on supprime y/y qui ne change rien)
Définition unification : 2 littéraux t1 et t2 sont unifiables s’il existe une substitution σ
telle que σ(t1)=σ(t2).

Remarque:
2 littéraux peuvent avoir éventuellement plusieurs unificateurs.
Un unificateur θ de S est appelé unificateur le plus général (UPG) de S si pour tout
autre unificateur σ de S il existe une substitution ξ de S alors on a σ = θ.ξ

Procédure récursive unifier(E1,E2);

1) Si E1 ou E2 est un atome (prédicat, fonction, cte négation ou variable)
alors Échanger E1 et E2 de sorte que E1 soit un atome et faire
2) début
3) Si E1 et E2 sont identiques alors renvoyer Nil
4) Si E1 est une variable
5) alors début Si E1 apparaît dans E2 alors renvoyer Échec (Occur-check)
7) Renvoyer {E1/E2}
8) Fin
9) Si E2 est une variable alors renvoyer {E2/E1}
10) Renvoyer Échec
11) Fin
12) F1 := le premier élément de E1, T1 := le reste de E1
13) F2 := le premier élément de E2, T2 := le reste de E2;
14) Z1 := unifier(F1,F2)
15) Si Z1=Echec alors renvoyer Échec
16) G1 := Z1(T1)
17) G2 := Z1(T2)
18) Z2 := unifier(G1,G2)
19) Si Z2=Echec alors renvoyer Echec

Cet algorithme produit l’upg (l’unificateur le plus général) ou échec lorsque les 2
expressions ne sont pas unifiables.

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 9

Résolution
La résolution est une règle d’inférence importante qui peut être appliquée à une
certaine classe de fbf appelées clauses.

Définition de Clause : Une clause est une fbf formée d’une disjonction de littéraux.

Cette résolution est appliquée à 2 clauses (appelées clauses parentes) pour produire
une clause (appelée clause dérivée). Cette résolution ne pouvant être appliqué qu’aux
clauses, il faut transformer les fbf en clauses par le processus suivant :

Transformation d’une fbf en clauses.

1) Eliminer les implications et les équivalences à l’aide des règles suivantes:
X1⇔ X2 ≡ ( X1  X2) ∧ (X2  X1) X1  X2 ≡ ¬X1 ∨ X2

2) Réduire les portées des négations jusqu ’aux littéraux avec les lois de De Morgan.

3) Standardiser les variables (renommer les variables de telle sorte que chaque
quantificateur ait sa propre variable).
Exemple: (∀ x)P(x)  (∃ x)Q(x) est équivalente à (∀ x)P(x)  (∃ y) Q(y)

4) Eliminer les quantificateurs existentiels par le processus suivant: Remplacer une

variable existentielle par une fonction de Skolem (un nouveau nom de fonction) dont
les arguments sont les variables liées à des quantificateurs universels dont la portée
inclut la portée du quantificateur existentiel à éliminer. S’il n’existe pas de tels
quantificateurs universels alors la fonction de Skolem est une constante de Skolem.
Exemples :
(∀ y)(∃ x) P(x,y) devient (∀ y)P(g(y),y) où g est une nouvelle fonction de Skolem.
(∀x)(∀y)(∃z) P(x,y,z) devient (∀x)(∀y) P(x,y,g(x,y)) où g est une fonction de Skolem
(∃ x)P(x) devient P(A) où A est une constante de Skolem
(∃x)(∀y)(∃z)(∀u)(∃v) P(x,y,z ,u,v) devient (∀y)(∀u) P(A,y,f(y) ,u ,g(y,u)) où A est une
constante de skolem et f,g sont 2 nouvelles fonctions de Skolem

5) Mettre l’expression sous forme normale prenexe. Une fbf sous forme normale
prenexe est de la forme: Préfixe Matrice
Les quantificateurs ∀ Formule sans les quantificateurs
6) Eliminer les quantificateurs universels (effacer la partie préfixe)

7) Mettre la matrice sous forme normale conjonctive en utilisant la règle de

distributivité suivante: X1 ∨ (X2 ∧ X3) ≡ (X1 ∨ X2) ∧ (X1 ∨ X3)
8) Eliminer les symboles ∧ en remplaçant la matrice X1 ∧ X2 ∧ X3 .... ∧ Xn par
l’ensemble de clauses {X1, X2, X3, ....., Xn} Chaque Xi est formée de disjonction de
littéraux qui est une clause.
9) Renommer les variables des clauses Xi

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 10

Exercice: Appliquer ce processus à la fbf suivante:
(∀ x){P(x)  {(∀ y)[P(y) P(f(x,y))] ∧ ¬ (∀ y)[Q(x,y)  P(y)]}}

Résolution dans le cas général :

Pour pouvoir appliquer la règle d’inférence « la résolution », à 2 clauses C1 et C2
(appelées clauses parentes), il faut trouver une substitution qui puisse être appliquée à
ces 2 clauses de telles sorte qu’elles vont contenir 2 littéraux complémentaires
respectivement.

Soient C1 et C2 les 2 ensembles de littéraux représentants les 2 clauses parentes.

Soient l1 et l2 les 2 littéraux appartenant respectivement aux clauses C1 et C2 de
telles sorte qu’elle existe une substitution σ pour que σ(l1) et σ(l2) soient
complémentaires.
En appliquant la résolution à ces 2 clauses parentes C1 et C2, on obtient (infère) la
résolvante (une nouvelle clause) σ({C1-l1} ∨ σ({C2-l2}). (On suppose qu’on a
renommé les variables des 2 clauses parentes). (C1-l1 signifie : enlever l1 de C1)

Remarque: Si 2 clauses se résolvent, elles peuvent avoir un nombre fini de résolvante.

Remarque : Cette règle d’inférence (la résolution) peut être appliquée à la logique
propositionnelle (en enlevant la substitution).

Exemple:
Soient les 2 clauses parentes: P(x,f(A))∨P(x,f(y))∨Q(y) et ¬P(z,f(A))∨ ¬Q(z) elles
peuvent produire 4 résolvantes (Les littéraux complémentaires via une substitution sont
soulignés):
C1 C2
1) P(x, f(A)) ∨ P(x, f(y)) ∨ Q(y) et ¬P(z, f(A)) ∨ ¬Q(z)
x/z
P(z, f(y)) ∨ Q(y) ∨ ¬Q(Z)

2) P(x, f(A)) ∨ P(x, f(y)) ∨ Q(y) et ¬P(z, f(A)) ∨ ¬Q(z)

x/z , y/A
P(z, f(A)) ∨ Q(A) ∨ ¬Q(z)

3) P(x, f(A)) ∨ P(x, f(y)) ∨ Q(y) et ¬P(z, f(A)) ∨ ¬Q(z)

y/A x/z
Q(A) ∨ ¬Q(z)
Dans ce cas les 2 littéraux ont été réduits en un seul littéral avec la substitution.

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 11

4) P(x, f(A)) ∨ P(x, f(y)) ∨ Q(y) et ¬P(z, f(A)) ∨ ¬Q(z)
y/z
P(x, f(A)) ∨ P(x, f(z)) ∨ ¬P(z, f(A))

Propriétés: Il est démontré que la résolution est une règle d’inférence saine

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 12

 Autres logiques
En plus des 2 logiques vues jusqu’à présent (logique propsionnelle et
logique d’ordre 1 (des prédicats)), il existe d’autres logiques plus récentes :
d’ordre 2, Logique de description, logique temporelle, logique floue
(incertain), logique modale, de croyances etc …
Chaque logique a sa propre syntaxe, sa propre sémantique ainsi que ses
propriétés d’inférence. L’étude approfondie de ces logiques nécessite un
chapitre par logique (syntaxe, sémantique, propriétés, inférence etc…)

1)Logique d’ordre 2 :
En logique d’ordre 1, on a vu que les variables sont liées par des
quantificateurs (seules les variables peuvent être liées par les 2
quantificateurs ∀ ∃). Il existe des logiques d’ordre supérieur (d’ordre 2),
dans lesquelles il est possible de quantifier également les relations et les
fonctions. Elles sont utilisées pour formaliser des concepts mathématiques
plus complexes et pour exprimer des propriétés plus riches que ce qui est
possible avec les logiques d'ordre 0 ou 1.

Exemple:
On peut écrire (∀P) (∀x) P(x) \*pour toute propriété P, P(x) est vrai
pour tout x*/, ce qui est une déclaration plus générale.
On peut avoir (∀F)(∃x) F(x) qui signifie /*pour toute fonction F, il
existe un x tel que F(x) est vrai*/.

Les logiques d'ordre supérieur sont un outil puissant pour modéliser et

raisonner sur des systèmes complexes dans un large éventail de disciplines,
bien que leur utilisation doive être équilibrée avec les défis qu'elles posent
en termes de complexité et de décidabilité.

2)Logique temporelle :
Soit à représenter avec la logique proposionnelle la gestion des feux
tricolores du code de la route. On peut exprimer l’état du feu tricolore qui
est en : « V allumé, R éteint et J éteint » par : V ∧ ¬R ∧ ¬J où chaque
proposition représente l’état d’un feu. On peut donc représenter avec la
logique classique les différentes situations d’un feu tricolore. Supposons
qu’on veuille représenter maintenant la situation: « le feu V précède le feu

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 13

 R » ou bien « le feu ne peut pas rester toujours sur R », etc.… il y a
beaucoup de situation qu’on ne peut pas représenter avec la logique
classique : on a besoin de représenter le temps.

On voudrait par exemple aussi exprimer dans une telle logique le fait
« Mohamed est un étudiant maintenant mais un jour il ne sera plus
étudiant » ou « 2 est toujours un nombre pair ». On a besoin d’exprimer la
notion du temps.

D’après son nom, cette logique introduit la notion du temps dans sa

définition. Ces logiques sont obtenues à partir de la logique
propositionnelle en ajoutant un certain nombre de quantificateurs
temporels, comme par exemple : maintenant, dorénavant, toujours,
jusqu’à, etc… qui permettent de parler des propriétés qui sont vraies à
différents moments dans le temps, associant une valeur de vérité non pas à
un état, mais à une séquence d'états, représentant l'évolution du système au
cours du temps.

La vérité (valeur de vérité) peut changer au fil du temps. Elle est

particulièrement utile pour modéliser et vérifier des systèmes dynamiques,
comme les systèmes informatiques, les processus concurrents, et les
comportements dans les systèmes physiques.

La logique Temporelle (LT) = Logique classique + Opérateur dédiés au

temps (Opérateurs temporels)

1. Opérateurs Temporels :
F (Eventually ou "Finalement") :
F(P) signifie "P sera vrai à un moment donné dans le futur".
Exemple : F(il pleuvra) signifie "Il pleuvra à un moment donné dans le
futur".
G (Globally ou "Toujours") :
G(P) signifie "P est toujours vrai, maintenant et dans le futur".
Exemple : G(Le système est stable) signifie "Le système est stable tout
le temps".
X (Next ou "Suivant") :
X(P) signifie "P sera vrai à l'instant suivant".

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 14

 Exemple : X(La lumière s’allumera) signifie "La lumière s'allumera au
prochain instant".
U (Until ou "Jusqu'à ce que") :
P U Q signifie "P sera vrai jusqu'à ce que Q devienne vrai".
Exemple : (L’alarme est sur off) U (l’alarme est déclenchée) signifie
"L'alarme reste éteinte jusqu'à ce qu'elle soit déclenchée".

Exemple d'utilisation : Vous pouvez spécifier qu'une certaine condition

"a" doit toujours être vraie, et qu'une autre condition "b" finira par devenir
vraie, en écrivant G a ∧ F b.
Exemple : G(P)→F(Q) (ou G P  F Q) signifie "Si P est toujours vrai,
alors Q finira par être vrai".

Applications de la Logique Temporelle

o Vérification formelle de logiciels et matériels : vérifier si un
système (comme un programme informatique ou un circuit électronique)
satisfait certaines spécifications temporelles.
Exemple : Utilisation de CTL pour vérifier que "Dans toutes les
exécutions possibles, si le signal de démarrage est activé, alors le système
finit par passer à l'état opérationnel".
o Modélisation des processus concurrents : Elle permet de
modéliser et de raisonner sur le comportement des systèmes réactifs
(systèmes d’exploitation, protocoles de communication) dans le temps.
Exemple : Vérification que "Pour tout processus, s'il demande un accès à
la ressource critique, il finira par l'obtenir".
o Raisonnement temporel en intelligence artificielle : La
logique temporelle est utilisée pour raisonner sur les actions et leurs
conséquences au fil du temps, ce qui est essentiel pour la planification dans
les systèmes d'intelligence artificielle.
Exemple : Dans la planification d'actions, on peut spécifier qu'"Une action
doit être exécutée seulement après qu'une certaine condition soit remplie".
o Modélisation de dynamiques temporelles : Les systèmes
physiques, tels que les systèmes de contrôle, peuvent être modélisés avec
la logique temporelle pour vérifier que leur comportement respecte
certaines contraintes temporelles.
Exemple : Utiliser LTL pour vérifier qu'"un capteur déclenchera une
alarme dans un délai de 5 secondes après la détection d'un seuil critique".

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 15

o Raisonnement stratégique dans les jeux : Dans la théorie
des jeux, la logique temporelle est utilisée pour modéliser les stratégies où
les décisions des joueurs dépendent des événements futurs ou des actions
passées.
Exemple : Un joueur peut être modélisé pour choisir une stratégie qui
garantit que "il gagnera au moins une fois dans tous les futurs possibles".
o Analyse des propositions temporelles : En philosophie, la
logique temporelle est utilisée pour formaliser et analyser des propositions
temporelles, comme des déclarations sur ce qui est possible ou nécessaire à
différents moments.
Exemple : Analyser des arguments concernant le libre arbitre ou la
prédestination en utilisant la logique temporelle pour modéliser des choix
et leurs conséquences futures.

3)Logique floue
Dans les logiques classiques, les propositions sont soit vraies soit
fausses. Néanmoins, il existe des propriétés qui semblent pouvoir être
vraies à un certain degré ou fausses à un certain degré.

Prenons par exemple la propriété « grand" : Il serait un peu bizarre de

séparer les êtres humains entre deux classes, ceux qui sont grands, et ceux
qui ne le sont pas. Si on utilise la logique classique, comment choisir une
hauteur telle que toutes les personnes avec une taille supérieur à cette
hauteur sont grands, et les autres pas ? La logique floue tente de répondre à
ce problème en permettant aux propositions de prendre les valeurs entre 0
et 1, où 0 signifie que la proposition n'est pas satisfaite du tout, et 1
signifie la satisfaction complète de la proposition, et les valeurs entre 0 et 1
signifie des niveaux de satisfaction de la proposition.

Nous pourrions donc dire que quelqu'un est grand à niveau 0.3 (qui veut
dire que la personne n'est pas tellement grande mais pas complètement
petite) ou à niveau 0.8 (la personne est plutôt grande).

Elle est particulièrement utile pour modéliser des phénomènes imprécis,

incertains ou vagues, comme par exemple les notions de "chaud", "grand",
"rapide", qui ne sont pas aisément représentables par des valeurs binaires.

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 16

 Concepts de Base de la Logique Floue
1. Degrés de Vérité :
Contrairement à la logique classique, où une proposition est soit vraie
(1) soit fausse (0), la logique floue permet à une proposition d'avoir un
degré de vérité situé entre 0 et 1.
Exemple : La proposition "Il fait chaud" peut être vraie à 0.7 si la
température est élevée mais pas extrême.

2. Fonctions d'Appartenance :
Une fonction d'appartenance associe chaque élément d'un ensemble à un
degré d'appartenance entre 0 et 1.
Exemple : Pour le concept "chaud", une fonction d'appartenance pourrait
attribuer 0 à 20°C, 0.5 à 25°C, et 1 à 30°C.

3. Opérations Floues :
Les opérations logiques classiques comme ET (conjonction), OU
(disjonction), et NON (négation) sont étendues pour traiter des degrés de
vérité.
ET flou (min) : min(A,B) donne la valeur minimale entre A et B.
 OU flou (max) : max(A,B) donne la valeur maximale
entre A et B.
 NON flou : 1−A donne le complément de A.

4. Règles Floues :
Les systèmes flous utilisent des règles de type "Si... Alors..." où les
conditions et les conclusions peuvent être floues.
Exemple : "Si la température est élevée et l'humidité est faible, alors
l'irrigation doit être modérée."

Applications de la Logique Floue

Contrôle Flou :
Systèmes de contrôle : La logique floue est largement utilisée dans les
systèmes de contrôle où les décisions doivent être prises en fonction de
variables continues et incertaines.
Exemples :
Contrôle de température : Un thermostat flou ajuste la température en
fonction de la température actuelle et de la vitesse de changement.

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 17

Contrôle de vitesse : Un système de régulation de vitesse dans une voiture
pourrait utiliser la logique floue pour ajuster en douceur l'accélération ou
le freinage en fonction de la vitesse actuelle, des conditions routières, et de
la distance au véhicule de devant.

Traitement du Langage Naturel :

Systèmes de dialogue : La logique floue aide à interpréter les
déclarations vagues ou subjectives dans le langage naturel.
Exemple : Un assistant vocal peut utiliser la logique floue pour interpréter
une commande comme "réduit un peu la lumière", en ajustant l'intensité
lumineuse à une valeur intermédiaire plutôt que de simplement l'allumer
ou l'éteindre.
[Link] Médical :
Systèmes d'aide à la décision médicale : Les systèmes flous peuvent
modéliser des symptômes médicaux qui ne sont pas toujours présents
avec certitude, en fournissant des diagnostics basés sur des degrés
d'incertitude.
Exemple : Un système flou pourrait évaluer la probabilité qu'un patient ait
une certaine maladie en fonction de symptômes dont l'intensité varie.

Systèmes Experts :
Modélisation des connaissances humaines : La logique floue est utilisée
pour modéliser des connaissances d'experts qui ne sont pas toujours
précises, comme dans les systèmes de prise de décision basés sur des
règles.
Exemple : Un système expert agricole pourrait recommander des
techniques de culture en fonction de conditions environnementales
incertaines, comme l'humidité du sol et la température.

Analyse d'Images et Reconnaissance de Formes :

Traitement d'images : La logique floue est utilisée pour la segmentation
d'images, la reconnaissance de formes, et l'amélioration d'images, où les
frontières des objets peuvent être floues.
Exemple : Dans une image satellite, la logique floue peut aider à identifier
des zones de végétation ou d'eau en fonction de critères flous comme la
couleur ou la texture.

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 18

 Prévisions et Modèles Financiers :
Analyse des risques : La logique floue est utilisée pour modéliser des
incertitudes dans les prévisions financières et l'évaluation des risques.
Exemple : Un modèle financier flou pourrait estimer la probabilité de
réussite d'un investissement en tenant compte de facteurs économiques
imprécis ou incertains.

4)Logiques de description
Cette famille de logiques se trouve à mi-chemin entre la logique
propositionnelle et la logique du premier ordre, offrant ainsi une
expressivité beaucoup plus importante que celle de la logique
propositionnelle mais avec une complexité du raisonnement moindre que
pour la logique du premier ordre (en particulier, les logiques de description
sont souvent décidables). Ces logiques possèdent deux types de formules :
des axiomes qui décrivent des relations entre des concepts et des assertions
qui expriment les caractéristiques des individus et les relations entre
individus.

Elle est particulièrement utilisée en intelligence artificielle (IA) pour

structurer les connaissances en systèmes complexes, tels que des bases de
connaissances ou des ontologies. Ces logiques de description sont au cœur
des technologies du Web sémantique (représentation de la connaissance)
comme OWL

Par exemple, nous pourrions avoir des axiomes Oiseau ⊆ Animal

(chaque oiseau est un animal) et Oiseau ⊆ ∀ [Link] (les enfants des
oiseaux sont aussi des oiseaux) et des assertions Oiseau(Tweety) (Tweety
est un oiseau) et enfant(Tweety; Paul) (Paul est un enfant de Tweety).
Nous pourrions alors inférer que Paul est un oiseau et que Tweety et Paul
sont tous les deux des animaux. Les logiques de description sont utilisées
dans plusieurs domaines d'application (ex. la médecine, le traitement du
langage naturel, etc.) et sont à la base du web sémantique.

Concepts de Base des Logiques de Description

1. Concepts, Rôles, et Individus :

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 19

o Concepts : Représentent des classes d'objets ou d'entités. Par
exemple, le concept "Personne" pourrait représenter l'ensemble des
personnes.
o Rôles : Représentent des relations entre individus ou entre
individus et concepts. Par exemple, le rôle "aEnfant" pourrait relier un
individu de type "Personne" à un autre individu de type "Personne".
o Individus : Représentent des instances spécifiques de
concepts. Par exemple, "Ali" et "Boualem" pourraient être des individus du
concept "Personne".

2. Constructeurs de Concepts :
o Conjonction (⊓ ⊓) : Combine deux concepts pour former un
nouveau concept qui contient les éléments communs aux deux concepts.
 Exemple : Personne ⊓ Homme représente les hommes
qui sont des personnes.
o Disjonction (⊔ ⊔): Combine deux concepts pour former un
nouveau concept qui contient les éléments appartenant à l'un ou l'autre des
concepts.
 Exemple : Personne ⊔ Animal représente les entités qui
sont soit des personnes, soit des animaux.
o Complément (¬) : Négocie un concept pour former un
nouveau concept qui contient les éléments qui ne sont pas dans le concept
original.
 Exemple : ¬Homme représente toutes les entités qui ne
sont pas des hommes.
o Restriction existentielle (∃
∃) : Spécifie un rôle qui doit avoir
au moins un lien avec un concept donné.
 Exemple : ∃[Link] représente les individus
qui ont au moins un enfant qui est une personne (aEnfant est défini plus
haut).
o Restriction universelle (∀∀) : Spécifie que pour un rôle donné,
toutes les relations doivent pointer vers un concept spécifique.
 Exemple : ∀[Link] représente les individus
dont tous les enfants sont des personnes.

3. TBox et ABox :

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 20

o TBox (Terminological Box) : Contient des axiomes qui
définissent les concepts et les relations entre eux. C'est l'endroit où sont
définies les "règles" du domaine.
 Exemple : Personne ⊑ ∃[Link] pourrait
signifier que toutes les personnes ont potentiellement des enfants.
o ABox (Assertional Box) : Contient des assertions sur les
individus, spécifiant à quel concept appartient un individu ou quelles
relations existent entre les individus.
 Exemple : aEnfant(Ali, Boualem) signifie qu'Ali a un
enfant nommé Boualem.

[Link] des Logiques de Description

a)Ontologies et Web Sémantique :
o Modélisation d'ontologies : Les logiques de description sont
fondamentales pour la création et la gestion d'ontologies dans le Web
sémantique. OWL, un langage de description d'ontologies standardisé par
le W3C, est basé sur les logiques de description. (Une ontologie est une
représentation formelle des connaissances dans un domaine particulier.
Elle définit un ensemble de concepts, leurs propriétés, et les relations qui
existent entre eux. Les ontologies sont utilisées pour structurer et
formaliser les connaissances, facilitant ainsi la communication, le partage,
et le raisonnement sur ces connaissances au sein de systèmes
informatiques).
Exemple : Une ontologie médicale pourrait utiliser la logique de
description pour définir des concepts tels que "Maladie", "Symptôme", et
"Traitement", ainsi que les relations entre eux, comme "une maladie peut
avoir un symptôme" ou "un traitement peut être appliqué à une maladie".

b)Raisonnement Automatique :
o Classification : Les systèmes basés sur les logiques de
description peuvent automatiquement classer des individus sous les
concepts appropriés en fonction des axiomes et des assertions disponibles.
o Exemple : Si un individu est défini comme ayant tous les
attributs d'un "Mammifère" et d'un "Carnivore", le système peut
automatiquement conclure que cet individu est un "Carnivore
Mammifère".

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 21

o Vérification de la cohérence : Les logiques de description
permettent de vérifier si une ontologie est cohérente, c'est-à-dire si elle ne
contient pas de contradictions.
 Exemple : Vérifier que personne ne peut être à la fois
classé sous "Vivant" et "Mort".

c)Requêtes et Recherche Sémantique :
o Interrogation des connaissances : formuler des requêtes
complexes sur une base de connaissances structurée.
Exemple : "Trouver toutes les personnes qui ont un enfant qui est un
médecin"

d)Intégration et Interopérabilité des Données :

o Interopérabilité entre systèmes : intégration des données
provenant de différentes sources en définissant clairement les concepts et
les relations utilisés dans les données.
Exemple : Deux systèmes de santé utilisant des ontologies différentes
peuvent interopérer si leurs ontologies respectives sont alignées via une
logique de description commune.

e)Systèmes Experts :
Support à la décision : Les logiques de description sont utilisées pour
modéliser des règles complexes dans des systèmes experts, permettant des
prises de décisions automatisées basées sur des connaissances formelles.
 Exemple : Un système expert en agriculture pourrait
recommander des actions spécifiques pour un champ en fonction de sa
classification dans une ontologie de gestion des cultures.

Propriétés et Défis
• Complexité et Expressivité : Il existe un compromis entre la
complexité computationnelle et l'expressivité des logiques de description.
Des logiques très expressives, comme celles qui supportent la
quantification ou les cardinalités, peuvent être difficiles à raisonner
automatiquement.
• Décidabilité : Les logiques de description sont conçues pour être
décidables, mais certaines extensions peuvent rendre le raisonnement
indécidable ou très coûteux en termes de ressources.

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 22

• Modélisation Ontologique : Bien que les logiques de description
soient puissantes pour modéliser des domaines complexes, la création
d'ontologies peut nécessiter une expertise significative pour être précise et
utile.

Site dédié à cette logique : [Link]

5)Logique modale :
La logique modale est un outil puissant pour aborder des problèmes où
la simple vérité ou fausseté des énoncés ne suffit pas, permettant de
capturer des nuances complexes dans différents domaines de la
connaissance. Elle a la même syntaxe que la logique de description. La
logique modale est une extension de la logique classique qui introduit des
opérateurs modaux pour exprimer des modalités comme la possibilité, la
nécessité, le temps, la connaissance, l'obligation, et autres concepts
similaires.
Elle est utilisée pour formaliser et raisonner sur des énoncés qui ne
sont pas simplement vrais ou faux, mais qui dépendent de contextes ou
de conditions.
Dans la logique modale, les opérateurs modaux sont souvent interprétés
à travers des "mondes possibles". Un énoncé est évalué comme vrai ou
faux non seulement dans un monde actuel, mais aussi par rapport à d'autres
mondes accessibles depuis celui-ci.

Opérateurs Modaux :
o ◇ (Diamant) : Représente la possibilité. Si ◇P est vrai, cela
signifie que P est possible. ◇(Il pleut) signifie "Il est possible qu'il
pleuve".
o □ (Carré) : Représente la nécessité. Si □P est vrai, cela
signifie que P est nécessaire. □(2+2=4) signifie "Il est nécessaire que 2+2
égale 4"
o L'opérateur K pour la connaissance : Kp signifie "il est
connu que p". Utilisé dans la logique épistémique (branche de la logique
modale qui s'intéresse à la modélisation et à l'analyse des connaissances et
des croyances des agents. Elle permet de formaliser des concepts tels que
"ce que quelqu'un sait", "ce que quelqu'un croit", et "ce que plusieurs
agents savent ou croient en commun").

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 23

o L'opérateur B pour la croyance .Bp signifie "il est cru que
p". Utilisé pour formaliser les croyances dans des contextes épistémiques.
o L'opérateur O pour l'obligation : Op signifie "il est
obligatoire que p". Utilisé dans la logique déontique (logique modale qui
se concentre sur le raisonnement concernant les normes, les obligations, les
permissions, et les interdictions. Elle est principalement utilisée pour
formaliser et analyser les concepts moraux, juridiques, et éthiques pour
raisonner sur les obligations) et les devoirs.
o L'opérateur P pour le permis : Pp signifie "il est permis que
p". Egalement utilisé en logique déontique pour exprimer ce qui est
permis.

Logique Modale Kripkienne :

Elle repose sur la notion de mondes possibles. Un énoncé est évalué par
rapport à un monde possible.
Accessibilité : La relation entre les mondes possibles est cruciale. Par
exemple, si un monde A est accessible à partir d'un monde B, alors ce qui
est possible dans A est considéré comme possible dans B.

Applications de la Logique Modale

La logique modale a de nombreuses applications dans divers domaines
de la science, de la philosophie, et de l'informatique. Grâce à sa capacité à
exprimer des notions telles que la possibilité, la nécessité, la connaissance,
et l'obligation, elle permet de formaliser et d'analyser des situations
complexes. Voici quelques-unes de ses principales applications:
• Vérification de modèles : La logique modale est largement utilisée
dans la vérification de modèles pour analyser les systèmes
informatiques, en particulier les systèmes concurrents ou distribués. La
logique temporelle, une forme de logique modale, est utilisée pour vérifier
si un système respecte certaines propriétés à travers le temps (comme la
sécurité ou la liveness).
• Intelligence artificielle : Elle est utilisée dans le raisonnement
automatique pour modéliser les états de connaissance des agents, les
plans et les croyances dans les systèmes multi-agents.
• Langages de programmation : La logique modale influence le
développement de certains langages de programmation où les types

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 24

 peuvent être interprétés comme des modalités, ce qui permet de gérer des
concepts comme l'incertitude ou les permissions.
• Sémantique des modalités : La logique modale est utilisée pour
analyser la structure sémantique des énoncés modaux dans le langage
naturel. Par exemple, elle aide à comprendre comment les gens utilisent
des expressions comme "il se peut que", "il est nécessaire que", ou "il est
permis de".
• Analyse des énoncés conditionnels : Les conditionnels (du type "Si
P, alors Q") sont souvent interprétés en termes de modalités pour capturer
l'idée de mondes possibles où les conditions sont remplies.
• Logique déontique : La logique modale est utilisée pour formaliser
les concepts juridiques et éthiques tels que l'obligation, la permission, et
l'interdiction. Par exemple, on peut utiliser la logique déontique pour
formaliser les règles légales ou morales et pour analyser leur cohérence et
leur implication.
• Raisonnement juridique : Elle aide à structurer les arguments
juridiques en termes de ce qui est légalement nécessaire ou permis, et à
analyser les conflits entre différentes normes.
• Jeux et Raisonnement stratégique : Dans la théorie des jeux, la
logique modale est utilisée pour modéliser les croyances et les stratégies
des joueurs, ainsi que pour analyser les décisions prises dans des situations
de concurrence ou de coopération.
• Modélisation des préférences : En économie, les préférences des
agents peuvent être modélisées avec des opérateurs modaux pour exprimer
ce qui est souhaité ou nécessaire dans différents scénarios économiques.
• Modélisation du raisonnement humain : La logique modale
permet de modéliser comment les humains raisonnement sur la possibilité,
la nécessité, et d'autres concepts abstraits. Elle est utilisée pour
comprendre les processus cognitifs liés à la prise de décision, à la
résolution de problèmes, et à la compréhension du langage.

Ces applications montrent la polyvalence de la logique modale, qui

s'étend bien au-delà des mathématiques pour toucher des domaines très
variés où la nuance et le contexte jouent un rôle essentiel dans le
raisonnement.

6)Logiques non-monotones

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 25

 Les logiques classiques sont appelées monotones car si une formule G
est conséquence logique de S alors G est toujours conséquence logique de
S ∧ R. Autrement dit, le fait d'ajouter de l'information supplémentaire ne
peut pas causer de perte d'informations. Or cette propriété ne semble pas
toujours être vérifiée dans les raisonnements humains. Ceci nous entraine
à la logique non monotone. Les logiques non monotones sont des
systèmes logiques dans lesquels l'ajout de nouvelles informations peut
entraîner la rétraction ou la modification des conclusions
précédemment acceptées. Ceci nous permet d’avoir une plus grande
flexibilité dans la gestion des connaissances incomplètes ou changeantes.

Pour prendre un exemple classique, supposons qu’on dit que Tweety est
un oiseau, et on vous demande si Tweety vole. Vous allez probablement
dire que oui car les oiseaux volent. Mais si maintenant on ajoute le fait que
Tweety est un pingouin, vous allez maintenant dire que Tweety ne vole
pas. C'est un exemple d'un raisonnement non-monotone car l'ajout d'une
hypothèse (Tweety est un pingouin) fait perdre l'une des conséquences
(Tweety vole).

Ce type de raisonnement ne satisfait pas donc les lois de la logique

classique mais il est rationnel car il nous permet de raisonner en l'absence
d'informations complètes. Les logiques non-monotones essaient de
formaliser ce type de raisonnement. Dans la logique des défauts, par
exemple, nous pourrions traiter l'exemple de Tweety en utilisant une règle
de type \Si X est un oiseau et s'il n'est pas connu que X est un pingouin
alors conclure que X vole". La conclusion que Tweety vole reste valide
tant qu'on ne sait pas que Tweety est un pingouin.

Concepts Clés des Logiques Non Monotones

Non-Monotonie :
Dans une logique monotone, si une conclusion C est dérivée à partir
d'un ensemble de prémisses P, elle reste valide même si on ajoute d'autres
prémisses à P.
Dans une logique non monotone, l'ajout de nouvelles informations peut
entraîner la rétraction ou la modification des conclusions précédentes.

Gestion des Connaissances Incomplètes :

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 26

 Les logiques non monotones sont souvent utilisées pour modéliser et
raisonner avec des connaissances incomplètes ou incertaines. Elles
permettent aux systèmes de réviser leurs croyances à mesure que de
nouvelles informations deviennent disponibles.

Types de Logiques Non Monotones

Logique des Raisons par Défaut :
Concept : Permet de faire des suppositions ou des conclusions provisoires
en l'absence de preuve contraires.
Exemple : Si un animal est généralement un oiseau, on peut conclure qu'il
vole par défaut, sauf preuve du contraire (par exemple, si l'animal est un
pingouin).

Logique des Exceptions :

Concept : Permet d'exprimer des règles générales avec des exceptions
spécifiques.
Exemple : "Les oiseaux volent" est une règle générale, mais les exceptions
comme les pingouins ou les autruches doivent être spécifiées.

Logique de Priorité :
Concept : Permet de résoudre des conflits entre règles ou conclusions en
attribuant des priorités aux différentes règles.
Exemple : Si une règle dit que "Si A est vrai, alors B est vrai" et une autre
dit "Si C est vrai, alors B est faux", la logique de priorité peut déterminer
quelle règle a plus de poids en cas de conflit.

Logique des Modèles Probabilistes :

Concept : Combine des aspects de la logique avec la théorie des
probabilités pour gérer l'incertitude.
Exemple : Un système peut attribuer une probabilité à chaque règle ou
conclusion, permettant une gestion plus nuancée de l'incertitude.

Logique des Réseaux Bayésiens :

Concept : Utilise des graphes probabilistes pour modéliser des relations
conditionnelles entre variables et raisonner sur les probabilités des
événements.

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 27

 Exemple : Un réseau bayésien peut modéliser les probabilités de diverses
maladies en fonction des symptômes observés.

Logique des Programmes à Répétition :

Concept : Permet de modéliser des situations où les conclusions peuvent
changer en raison des interactions entre les règles.
Exemple : Les systèmes de programmation à logique de règles permettent
des ajustements dynamiques des conclusions basées sur des changements
dans les conditions initiales.

Applications des Logiques Non Monotones

1. Systèmes de Raisonnement Automatique :
Utilisés dans des systèmes d'intelligence artificielle pour gérer des
situations où les informations sont partielles ou susceptibles de changer.
Exemple : Les systèmes de gestion des connaissances dans des
applications médicales ou juridiques, où les conclusions peuvent évoluer
avec de nouvelles preuves.

2. Systèmes de Décision :
Permettent de prendre des décisions en fonction des informations
disponibles et des priorités, avec la possibilité de réévaluer ces décisions
lorsque de nouvelles informations arrivent.
Exemple : Les systèmes de recommandation qui ajustent leurs
recommandations en fonction des nouvelles préférences des utilisateurs.

3. Systèmes de Planification et de Logistique :

Aident à gérer les incertitudes et les changements dans les plans ou les
ressources.
Exemple : Les systèmes de planification des ressources d'entreprise qui
réajustent les allocations de ressources en fonction des changements dans
les conditions de production ou de demande.

4. Réseaux Bayésiens :
Utilisés pour la modélisation et le raisonnement en présence
d'incertitude, notamment dans des domaines comme le diagnostic médical,
l'évaluation des risques, et la prévision financière.

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 28

Exemple : Les outils de diagnostic qui évaluent la probabilité de diverses
maladies en fonction des symptômes et des résultats de tests.

Avantages et Défis
Flexibilité : Les logiques non monotones permettent de gérer des
situations complexes et incertaines, offrant plus de flexibilité que les
logiques monotones.
Adaptabilité : Elles permettent aux systèmes de s'adapter et de réviser
leurs conclusions à mesure que de nouvelles informations deviennent
disponibles.
Complexité : Les raisonnements non monotones peuvent devenir
complexes et coûteux en termes de calcul, en particulier lorsqu'il y a de
nombreux conflits ou exceptions à gérer.
Cohérence : Maintenir la cohérence des conclusions dans des systèmes
non monotones peut être difficile, nécessitant des mécanismes sophistiqués
pour gérer les conflits et les révisions.

En conclusion : Les logiques non monotones sont essentielles pour les

systèmes capables de traiter des connaissances incomplètes ou
dynamiques, permettant une prise de décision plus sophistiquée et flexible
dans des environnements complexes et incertains.

8)Logique de connaissances et/ou croyances

L'une des caractéristiques du raisonnement humain est sa faculté de
raisonner sur ses propres connaissances/croyances et sur les
connaissances/croyances des autres. Un certain nombre de logiques ont été
proposées pour formaliser ce type de raisonnement. Dans ces logiques,
nous pouvons exprimer les informations de type \je sais que Meriem a un
enfant, et je crois que c'est une fille, mais je ne suis pas sur" ou bien je
crois qu'il croit que je sais qui a volé le diamant, mais je ne le sais pas".
Le raisonnement sur les connaissances devient un sujet de plus en plus
populaire grâce à son utilité dans de nombreux domaines tels que l'IA, la
linguistique, l'informatique distribuée, et l'économie.

Elle est souvent utilisée dans le cadre de l'intelligence artificielle (IA)

pour représenter et gérer les connaissances que les agents peuvent avoir sur

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 29

 le monde, en prenant en compte que ces connaissances peuvent évoluer ou
être sujettes à des révisions. La logique de croyance traite des situations où
les agents ont des croyances qui peuvent être incomplètes, incertaines ou
révisables.

Concepts Clés de la Logique de Croyance

1. Croyances :
Les croyances sont des propositions ou des assertions que les agents
considèrent comme vraies, mais qui peuvent être sujettes à révision ou à
changement.
Exemple : Un agent peut croire que "Il va pleuvoir demain", mais cette
croyance peut changer si de nouvelles informations météorologiques
deviennent disponibles.
2. Modèles de Croyance :
Un modèle de croyance est une représentation formelle de ce qu'un agent
croit sur un certain sujet ou dans un certain contexte.
Exemple : Dans un modèle de croyance, on peut représenter les croyances
d'un agent sur les faits connus, les hypothèses, et les conjectures.
3. Systèmes de Croyance :
Un système de croyance est un ensemble structuré de croyances qui suit
certaines règles ou principes.
Exemple : Un système de croyance peut inclure des règles de déduction
pour mettre à jour les croyances en fonction de nouvelles preuves.
4. Raisonnement avec les Croyances :
Le raisonnement basé sur les croyances permet de déduire de nouvelles
croyances à partir des croyances existantes.
Exemple : Si un agent croit que "Tous les oiseaux peuvent voler" et que
"Un perroquet est un oiseau", il pourrait en déduire que "Un perroquet peut
voler".
5. Révision des Croyances :
Les croyances peuvent être révisées lorsque de nouvelles informations
deviennent disponibles ou lorsque des contradictions sont découvertes.
Exemple : Si l'agent découvre que certains oiseaux, comme les pingouins,
ne peuvent pas voler, il devra réviser sa croyance précédente.
6. Croyances Conflictuelles :
Les systèmes de croyance doivent gérer les conflits entre croyances et
résoudre les contradictions.

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 30

 Exemple : Si un agent croit à la fois que "Tous les chiens sont des
mammifères" et que "Ce chien est un reptile", il doit résoudre cette
contradiction.

Types de Logiques de Croyance

1. Logique de Croyance Classique :
Concept : Modélise les croyances en utilisant des axiomes et des règles de
déduction similaires à ceux utilisés en logique classique, mais appliqués au
cadre des croyances.
Exemple : Les systèmes de logique de croyance classique peuvent utiliser
des logiques propositionnelles ou des logiques du premier ordre adaptées
pour représenter des croyances.
2. Logique de Croyance Non Monotone :
Concept : Permet des révisions des croyances en réponse à de nouvelles
informations, ce qui peut mener à des changements dans les croyances
précédemment établies.
Exemple : La logique des raisons par défaut est un exemple de logique
non monotone où les croyances sont ajustées en fonction des nouvelles
données.
3. Logique de Croyance Probabiliste :
Concept : Combine les notions de croyance avec des probabilités pour
représenter le degré de confiance dans une croyance.
Exemple : Un agent peut croire avec une probabilité de 0.8 qu'il pleuvra
demain, en fonction des prévisions météorologiques.
4. Logique de Croyance Bayésienne :
Concept : Utilise les réseaux bayésiens pour modéliser les croyances et les
mises à jour des croyances en fonction de nouvelles preuves.
Exemple : Un réseau bayésien peut représenter les croyances d'un agent
sur des variables dépendantes et ajuster ces croyances en fonction des
observations.
5. Logique de Croyance Épistémique :
Concept : Étudie les croyances des agents en tenant compte de la
connaissance et de l'incertitude, souvent utilisée dans les théories de la
connaissance et les jeux.
Exemple : La logique épistémique peut modéliser ce que plusieurs agents
croient ou savent, en tenant compte des connaissances partagées et privées.

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 31

 Applications des Logiques de Croyance
1. Intelligence Artificielle et Systèmes Experts :
Concept : Utilisée pour modéliser le raisonnement et la prise de décision
des agents intelligents en fonction de leurs croyances.
Exemple : Les systèmes experts peuvent utiliser des logiques de croyance
pour adapter leurs recommandations en fonction des connaissances
disponibles.
2. Systèmes de Recommandation :
Concept : Modélise les croyances des utilisateurs pour personnaliser les
recommandations en fonction de leurs préférences et comportements.
Exemple : Un système de recommandation peut ajuster ses suggestions en
fonction des croyances antérieures de l'utilisateur sur ses préférences.
3. Planification et Raisonnement Automatique :
Concept : Les agents peuvent utiliser des logiques de croyance pour
planifier des actions en fonction des croyances sur l'état actuel du monde et
les conséquences des actions.
Exemple : Un robot de service peut planifier ses tâches en fonction de ses
croyances sur l'emplacement des objets et les besoins des utilisateurs.
4. Systèmes de Diagnostic :
Concept : Utilise des croyances pour diagnostiquer des problèmes en
fonction des symptômes observés et des croyances préexistantes.
Exemple : Un système de diagnostic médical peut ajuster ses croyances sur
la maladie d'un patient en fonction de nouveaux résultats de tests.
5. Réseaux Bayésiens pour la Gestion de l'Incertitude :
Concept : Permet de modéliser et de raisonner sur des situations
incertaines en utilisant des croyances probabilistes.
Exemple : Les réseaux bayésiens sont utilisés pour la prévision de risques,
la reconnaissance de formes, et d'autres domaines où l'incertitude est
présente.

Avantages et Défis
• Flexibilité : Les logiques de croyance permettent de gérer des
informations incomplètes ou incertaines et de réviser les croyances en
fonction des nouvelles données.
• Modélisation des Conflits : Elles permettent de gérer les conflits
entre croyances et de résoudre les contradictions de manière structurée.

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 32

• Complexité : La gestion des croyances peut devenir complexe,
surtout lorsqu'il y a de nombreuses croyances interconnectées et des
conflits à résoudre.
• Révision et Cohérence : Maintenir la cohérence des croyances tout
en révisant les connaissances peut être un défi, nécessitant des mécanismes
sophistiqués pour gérer les révisions et les mises à jour.
La logique de croyance est un outil puissant pour modéliser le
raisonnement et la prise de décision en présence d'incertitude et
d'informations changeantes, permettant aux systèmes intelligents d'ajuster
leurs connaissances et leurs actions en fonction des nouvelles preuves.

9)La logique causale :

La logique causale se réfère au processus de compréhension des
relations de cause à effet. Certains événements (les causes) conduisent à
d'autres événements (les effets). Si A provoque B, alors A est la cause et B
est l'effet.

Exemples :
1. Causalité directe : A entraîne directement B.
Par exemple, "Il pleut, donc le sol est mouillé."
2. Causalité indirecte : A entraîne B par l'intermédiaire d'une autre
variable C.
Par exemple, "Fumer (A) cause des dépôts de goudron dans les
poumons (C), ce qui peut causer le cancer du poumon (B)."
3. Corrélation vs causalité : Une corrélation entre deux événements
ne signifie pas nécessairement qu'il y a une relation causale. Par
exemple, il peut y avoir une corrélation entre le nombre de glaces
vendues et les noyades, mais cela ne signifie pas que manger des
glaces provoque des noyades. Ces deux événements sont corrélés
parce qu'ils augmentent tous deux en été.
4. Causalité nécessaire et suffisante :
o Condition nécessaire : Pour que B se produise, A doit se
produire.
Par exemple, pour qu'il y ait du feu, il faut de l'oxygène.
o Condition suffisante : A suffit à provoquer B, mais B
pourrait aussi être causé par autre chose.

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 33

 Par exemple, allumer une allumette dans une atmosphère
riche en oxygène suffit à déclencher un incendie.
5. Contre-exemples : Pour réfuter une relation causale, on peut utiliser
des contre-exemples.
Par exemple, si on dit "tous les cigognes sont blanches", il suffit de
montrer une cigogne noir pour réfuter cette affirmation.

La logique causale est fondamentale dans de nombreuses disciplines,

notamment en science, en économie, en philosophie et en droit, où il est
crucial de comprendre comment les événements sont interconnectés.

IA Ing Soft Eng USTHB 2024/2025 H. AZZOUNE hazzoune@[Link] azzoune@[Link] 34

 Chap Résolution de Pb (Systèmes d’Etats : SE)
Introduction
Pour quel type de problèmes d’IA ?
- Résoudre un casse tête : (jeux, …)
- Trouver un chemin dans un réseau: (route, télécom, réseau,GPS...)
- Trouver un chemin dans un espace avec obstacle (robotique,vidéo,..)
- Trouver la succession d’opération pour passer d’un état initial vers
un but (production mécanique, jeux, etc…)
- Trouver une procédure pour fonction (administration, etc…)
- Trouver une planification (EDT, gestion espace, Robotique….
Comment résoudre un tel problème en IA? Pour répondre, il faut savoir :
- D’où l’on part, c.-à-d. l’énoncé du problème avec son état initial.
- Où on veut aller, c.-à-d. le but à atteindre (ou 1 des buts possibles).
- Comment on avance d’un état vers un autre, comment changer d’état.
- Calculer un chemin de l’état initial à un état but, c.-à-d. faire un plan
(des fois avec un cout minimal)
- Essayer ce plan, pour le vérifier.

Pour faire cette modélisation, on définit ses composants de base :

Définition: Les composantes principales d’un tel système sont:
a) Décrire les données (états/configurations) du problème d’une
manière simple (var, vecteur, matrice..) ou de manière très
complexes (structures indexées…..) : c’est la configuration des
états du problème. Les états intermédiaires, l’état initial et l’état(s)
but(s) peuvent alors être définis.
b) Opérations manipulant les états : Les règles de changement d’états
(succession). Elles ont la forme: Précondition  Action . La pré
condition doit être vérifiée par l’état actuel pour que la règle puisse
être appliquée (l’état actuel doit s’unifier avec la pré condition). Ces
règles permettent de changer d’état. L’action modifie l’état pour
avoir un nouvel état. (La pré condition peut être vide).
c) La stratégie de contrôle :
- choisit la règle applicable à appliquer.
- nous permet de construire l’espace d’états (ensemble des états
atteignables à partir de l’état initial),
- tester si un état vérifie un état but,
- construit la séquence d’actions/états de l’état initial à l’état but,

Cours Fond. IA H. AZZOUNE USTHB 2024/2025 1

 - dispose d’une fonction de coût sur la séquence,
- vérifie si on est déjà passé par un état, ……

La résolution d’un tel problème consiste à trouver donc un chemin

(séquence de règles) de l’état initial à un état but avec des fois une
condition sur les couts des séquences (cout optimal).

On distingue plusieurs types de systèmes, ils différent par le mécanisme

de contrôle, les propriétés des règles, de la structure de l’état, etc…. Les 2
premières étapes précédentes sont les plus difficiles à définir.

Exemple du PB du Taquin à 9 cases

Soit le problème du Taquin à n x n cases, qui consiste en une table n x n
dont une case contient x et les autres cases un chiffre de 1 à n2-1. La case x
peut être échangée avec une case adjacente. Etant dans un état initial, le
problème consiste à transformer cet état pour atteindre un état but par une
séquence de déplacements de la case x. On étudie le cas n=3
2 8 3 ? 1 2 3
1 6 4  8 X 4
7 x 5 7 6 5
Etat Initial Etat But
Pour résoudre ce problème, on spécifie ses 3 composantes (modélisation):
- Décrire la structure des états (configurations) du problème. Une
représentation informatique d’un état de ce problème peut être une matrice
3x3. L'ensemble des états constitue, ce qu’on appelle l’espace du problème
(pour l’exemple le nombre d’états possibles est de l’ordre de 9!=362880
(relativement petit). Pour un Taquin 5x5, ce nombre est de l'ordre 1025.

L’état initial est la matrice correspondante à l’état initial, l’état but

correspond à la matrice de l’état but recherché (Le but peut être aussi :
atteindre un état satisfaisant une certaine configuration (par exemple un état
tel que la somme des éléments d’une certaine ligne est ≤ 6).
- Les règles de changements d’états (succession) sont les déplacements de
la case « x ». Une règle transforme un état en un autre :
Règle Pré condition Action
* ↑ Déplacer la case x vers le haut x n’est pas sur la ligne 1 Permuter la case x
* ↓ Déplacer vers le bas x n’est pas sur la ligne 3 /
* → déplacer vers la droite x n’est pas sur la colonne 3 /

Cours Fond. IA H. AZZOUNE USTHB 2024/2025 2

* ← déplacer vers la gauche. x n’est pas sur la colonne 1 /
L’action de chaque règle est de permuter la case x avec la case adjacente.

La solution à ce problème est une séquence de déplacements de la case x

à partir de l’état initial jusqu’à trouver l’état but, déduit à partir de l’espace
de recherche obtenu suivant une stratégie.

Remarque : Dans certain cas on exige que la solution soit de coût

minimal. Pour cela on associe des coûts aux déplacements.

Procédure de base d’un SE.

L’algorithme de base d'un SE peut être la procédure non-déterministe:
Procédure PRODUCTION
1) Donnée := état initial /*description de l’état initial */
2) Jusqu’à ce que Donnée satisfasse la condition but /* but atteint */
3) Faire début
4) Sélectionner une règle R de l’ensemble des règles applicables
à Donnée /* dont la pré condition est vérifiée */
5) Donnée := R(Donnée) /* appliquer R à Donnée */
6) Fin

« Donnée », variable contenant initialement l’état initial, contiendra au fur

et à mesure l’état obtenu après l’application d’une règle R au niveau 5.

Le Contrôle. Cette procédure est non-déterministe au niveau de la ligne 4

« Sélectionner ». La sélection à ce niveau, l’enregistrement des séquences
des règles essayées ainsi que les états produits etc.. sont contrôlés par la
stratégie de Contrôle. On peut avoir des stratégies qui utilisent d’autres
informations (connaissances) pour produire des solutions optimales. On
distingue plusieurs stratégies de contrôle:

1) Irrévocable: c.-à-d. des stratégies sans que l’on puisse remettre en

question l’application d’une règle. Elle est utilisée uniquement lorsque la
connaissance locale infaible est disponible pour transformer la
connaissance globale. A 1ere vue elle semble inexploitable, pour cela elle
n’est utilisée que dans les cas où l’application d’une règle n’empêche pas
l’utilisation ultérieure des autres règles. Elle n’est pas complète, (se
bloque sans que le but soit atteint même lorsque celui-ci est atteignable).

Cours Fond. IA H. AZZOUNE USTHB 2024/2025 3

2) Retour Arrière chronologique: Un point de retour arrière est établi
lorsqu’une règle est sélectionnée parmi d’autres règles applicables. Lors
d’un blocage, on peut revenir au dernier point de choix pour essayer un
autre choix jusqu’à atteindre le but ou il n’y ait plus de choix. Si aucune
information n’est disponible sur le choix de la règle à appliquer en premier,
la 1ere dans l’ordre d’écriture est choisie.

Exemple:
Supposons que dans notre problème du Taquin à 9 cases, le nombre
maximum d’application de la règle est 6. On suppose que l’ordre des règles
est arbitraire par exemple : gauche, haut, droite et bas. On revient en
arrière chaque fois qu’on produit une description déjà produite, chaque fois
que le nombre maximum (fixé au préalable) de règles est atteint, ou chaque
fois qu’il n’y a plus de règles (de choix) à appliquer.

Pour l’implémentation, on peut utiliser une pile de choix. Dans cette

stratégie on ne mémorise que le chemin de l’état initial à l’état actuel. On
oublie les états intermédiaires lors de retours arrière.
TD/TP : Produire l’arbre de recherche

Le processus de retour arrière est plus efficace si la sélection de la règle

n’est pas arbitraire. On peut utiliser une méthode appelée méthode du
gradient où on attribue une fonction à valeur <=0 (0 - donne le nombre de
cases mal classées par exemple) à chaque point de choix. On choisit la
règle qui croit cette fonction.

3) Recherche avec graphe. On explore l’effet de plusieurs règles

simultanément. On utilise un arbre (un graphe en général) de recherche,
d’où l’explosion de l’arbre puisqu’on garde tous les chemins. A chaque
noeud, avant d’atteindre le but, seront produits tous les chemins possibles.
TD/TP : Produire l’arbre de recherche

Stratégies de contrôle :
Dans la procédure ci-dessus, une caractéristique de la sélection est la quantité
d’informations (de connaissances) sur le domaine pour faire la meilleure sélection
(meilleure règle - la plus prometteuse). La sélection de la règle à appliquer peut être:
 arbitraire: Recherche aveugle (non informée). C'est une recherche sans tenir
compte d’informations disponibles sur le problème.

Cours Fond. IA H. AZZOUNE USTHB 2024/2025 4

 Stratégie guidée: utilise des connaissances disponibles sur le problème pour
guider le choix de la bonne règle (recherche informée).

On peut donc affirmer que l’efficacité d’un système peut dépendre du:
-Coût d’application des règles (nombre de règles pour atteindre le but),
-Coût du contrôle (effort fourni pour avoir une stratégie informée).
Et donc :
- Avec une stratégie arbitraire (aveugle), le coût de contrôle peut être modeste
(car on ne fournit aucun effort pour faire le choix de la règle, le choix est
arbitraire), mais elle entraînera un coût d'application de règles élevé (on essaye
beaucoup de règles avant d’atteindre le but).
- Informer complètement un système nécessite une stratégie de contrôle coûteuse
pour avoir cette information, en revanche on minimise le coût d’application des
règles car on guide le système lors de chaque choix (la stratégie guide le système
vers le but).
On peut dresser les courbes des 2 coûts précédents et de déduire le coût global :

Coût des Processus Coût global =la somme des 2 couts

Coût d’application Coût pour la connaissance

des règles de la stratégie de contrôle

0 Informativité « connaissances » Totale

Il serait intéressant de concevoir des systèmes où on équilibre les 2 coûts. L’efficacité
optimale pourrait être obtenue en utilisant des stratégies qui ne soient pas complètement
informées mais aussi non nullement informée.

Stratégies de Contrôle :
On a vu qu’il existe plusieurs stratégies pour les systèmes d’état:
- Irrévocable (pour les systèmes commutatifs)
- Par essai successifs:
* Retour Arrière (RA) chronologique (simple à implémenter et
nécessitant peu d’espace mémoire)
* Recherche avec graphe.
Remarque : On s’intéressera à la 2eme catégorie des stratégies (par essai successifs)
(1ere catégorie n’est utilisée que pour les SP commutatifs voir la fin du chapitre).

Cours Fond. IA H. AZZOUNE USTHB 2024/2025 5

1. Stratégie de Retour Arrière:
Le principe est qu’à chaque fois qu’on ait plusieurs choix (de règles), on choisit un
choix (une règle) et on mémorise les autres choix (règles). Lors d’un retour arrière
(blocage) on choisit un autre choix (une autre règle) etc…. Cette gestion de choix peut
etre faite soit par une procédure récursive, soit par une pile de choix.

Soit la procédure récursive Retour_arrière qui a en entrée initialement un argument

« Donnée » contenant l’état initial et retourne soit la séquence de règles à appliquer pour
atteindre le but soit ECHEC si cette séquence n’existe pas (but ne peut être atteint).

Procédure Récursive Retour_arierre(Donnée)

Début
1) Si Terminé(Donnée) /*l’état dans Donnée satisfait le but - but atteint*/
Alors renvoyer(Nil) /* sortir de l’appel / ou de l’appel récursif */
2) Si Impasse(Donnée) /* Donnée n’est pas sur le bon chemin du but : Impasse */
Alors renvoyer(échec) /* renvoyer échec à cet appel/ou à l’appel récursif */
3) Règles ← app_regles(Donnée) /* une fonction qui donne les règles applicables */
/*à Donnée et les ordonne arbitrairement ou suivant une heuristique */
4) Boucle: si vide(Règles)
Alors renvoyer(échec) /*pas ou plus de règles à appliquer, renvoyer échec*/
5) R ← première(Règles) /* Première règle est sélectionnée */
6) Règles ← queue(Règles) /* On enlève la règle sélectionnée de la liste des règles */
7) RDonnée ← R(Donnée) /*produire un nouvel état en appliquant R à Donnée*/
8)Chemin← retour_arriere(RDonnée) /*Appel récursif de la procédure avec
Rdonnée*/
9) Si Chemin = Echec /*si chemin retournée par l’appel récursif est ECHEC */
alors Aller à Boucle /* aller essayer une autre règle si il en reste*/
10) Renvoyer ([Link]) /* Concaténation de la règle R choisie au Chemin trouvé par
Fin /* l’appel récursif*/

Remarques: On peut faire les remarques suivantes sur cette procédure:

 Elle ne se termine avec succès (non échec) que lorsqu’elle produit un état satisfaisant
le But (ligne 1).
 La liste des règles à appliquer est construite en ligne 10
 Lorsqu’un échec se produit dans un appel récursif, on fait un Retour arrière au
dernier point de choix (aller à boucle – ligne 9).
 En ligne 3, les règles applicables sont ordonnées. A ce niveau toute connaissance
peut être utilisée. Par définition, si les règles correctes (meilleures règles, règles
prometteuses) sont choisies, il n’y aura aucun retour arrière. Par contre si le choix de
la règle est arbitraire, la procédure devient inefficace.

Cours Fond. IA H. AZZOUNE USTHB 2024/2025 6

Problème: En plus de ces remarques, elle peut ne jamais terminer:
- Produire de nouveaux états indéfiniment,
- Boucler sur un même état.
Une solution envisageable à ces problèmes peut être la suivante:
 Imposer une limite de profondeur des appels récursifs
 Mémoriser les états déjà produites pour éviter de boucler sur un même état.
Il faut donc :
- ajouter une variable globale « limite » qui limite la profondeur (le nombre
d’appels récursifs).
- que tout le chemin de l'état initial à l'état actuel soit un argument de la procédure.

RA Intelligent : Dans la procédure précédente, lorsqu’on effectue un retour arrière, on

le fait au niveau juste inférieur; il existe des systèmes intelligents qui font des retours
arrière directement au bon niveau car en général le meilleur niveau se trouve à un
niveau inférieur. C’est ce qu’on appelle un R.A. intelligent.

Remarque : Dans notre procédure précédente, on ne se souvient pas de tous les états
visités mais uniquement ceux se trouvant sur le chemin de l'état initial à l'état courant.
Le retour arrière implique que tous les états aboutissant à des échecs sont oubliés
(élagués). Pour remédier à cet oubli, d'autres stratégies appelées stratégies de recherche
avec graphe existent.

2. Stratégie de recherche avec graphe

Dans cette stratégie, on suppose que les états produits sont représentés comme les
nœuds d’un graphe ou d’un arbre et les arcs correspondent aux règles. L’inconvénient
est qu’on obtient un graphe volumineux. Une solution est de ne conserver que l’état
initial et les traces des changements incrémentaux à partir desquels tout autre état peut
être obtenu. Une stratégie de recherche avec graphe peut être considérée comme un
moyen de trouver un chemin qui relie l’état initial à un nœud représentant le but.

2.1 Rappel sur les graphes:

Un graphe peut être décrit :
- explicitement en donnant sous forme d’un tableau, les nœuds du graphe (les états)
avec les arcs (règles) ainsi que les couts associés (méthode inutilisable pour les graphes
de taille importante).
- implicitement en donnant le nœud de départ (l’état initial) et une fonction de
succession qui est appliquée à tout nœud pour donner ses successeurs avec les coûts
associés. On introduit un opérateur de succession qui appliqué à un nœud donne tous ses
successeurs avec leur couts associés (c’est le développement du nœud).
Le problème consiste donc à trouver un chemin de l'état initial à l'état But avec des
fois une contrainte que le chemin soit de coût minimal.

Cours Fond. IA H. AZZOUNE USTHB 2024/2025 7

Définition: Une solution (séquence de règles) est optimale s’il n’existe pas une autre
solution de coût strictement inférieur (on doit associer des couts aux règles).

2.2 Une procédure générale de recherche avec graphe

Une procédure qui consiste à développer une partie d’un graphe défini implicitement,
peut être définie comme suit: On utilise 2 variables liste Fermé et Ouvert initialement
vides : Fermé contient les nœuds qui ont été déjà développés et Ouvert les nœuds
feuilles qui ne sont pas encore développés:

Procédure recherche_avec_graphe;
1)Créer un graphe de recherche G qui consiste uniquement en nœud de départ d,
Mettre d sur une liste appelée OUVERT. /* d est à développer */
2) Créer une liste appelée FERME qui est initialement vide.
3) BOUCLE: SI OUVERT est vide alors ECHEC exit /*plus de nœud à développer*/
4) Sélectionner le 1er noeud de OUVERT, l’enlever de OUVERT et le
mettre dans FERME, appeler ce nœud n. /* ce noeud n est à développer */
5) Si n est un noeud But
alors Terminer avec succès. Renvoyer le chemin obtenu le long des
pointeurs (construits en phase 7) de n jusqu’à d dans G.
exit
6) si n n’a pas été déjà développé
Alors
Développer le nœud n, produisant l’ensemble M de ses successeurs et
les mémoriser comme successeurs de n.
7) Mémoriser un pointeur vers n à partir des éléments de M.
Ajouter ces éléments de M à OUVERT /* ces noeuds peuvent être développés */
8) Réordonner OUVERT, soit arbitrairement soit selon une heuristique
fsi
9) Aller à Boucle.
Fin

Remarques:
-Cette procédure produit une famille d'algorithmes, la différence réside dans la
manière de réordonner les nœuds-ligne 8.
-L’arbre de recherche est défini par ses pointeurs établis dans l’étape 7. Chaque noeud
excepté d a un pointeur orienté vers un seul de ses parents dans G, qui définit son parent
-Les nœuds de OUVERT sont les nœuds feuilles de l’arbre de recherche (qui n'ont pas
encore été sélectionnés pour être développés).
-Les nœuds de FERME sont les autres nœuds (soit des feuilles qui n'ont pas produits de
successeurs soit les nœuds qui ne sont pas des feuilles).
-Les nœuds sont ordonnés en phase 8 pour sélectionner les meilleurs pour être
développées en phase 4 : Cet ordre est arbitraire (aveugle) ou suivant une heuristique.

Cours Fond. IA H. AZZOUNE USTHB 2024/2025 8

-Lorsque le nœud sélectionné est un nœud but, le processus se termine avec succès,
auquel cas le chemin inverse est parcouru de l’état courant jusqu’à d suivant les
pointeurs de la phase 4.
-Au contraire un échec peut arriver lorsque le (les) nœud(s) but(s) sont inaccessibles à
partir du nœud de départ (liste OUVERT devient vide sans atteindre le but).

3. Procédures aveugles de recherche avec graphe

Si aucune information sur le domaine n’est disponible dans le classement des nœuds
dans « ouvert », un plan arbitraire doit être utilisé à la phase 8 de l’algorithme: une telle
procédure est dite aveugle (non informée).

Pour calculer la complexité des stratégies, soient les paramètres suivants :

b : facteur de branchement : le nombre max de successeurs à un nœud.
d : la profondeur du nœud but le moins profond.
m : la longueur maximale d’un chemin dans l’espace d’états
la complexité en temps : le nombre de nœuds crées
la complexité en mémoire : le nombre maximum de nœuds en mémoire
optimalité : est ce que la stratégie trouve toujours la solution la moins couteuse ?

3.1 Recherche en profondeur d’abord:

Les nœuds de « Ouvert » sont ordonnés en ordre décroissant suivant leur
profondeur dans l’arbre. Les plus profonds sont placés en 1er. Ceux de même
profondeur sont classés arbitrairement. En général dans cette stratégie On impose une
limite de profondeur pour empêcher que le système boucle sur des chemins infinis.

Ce type de recherche produit de nouveaux états dans un ordre similaire à celui du

retour arrière (ci-dessus). En général, on préfère le retour arrière à la recherche en
profondeur d’abord car il nécessite moins d’espace mémoire, (on ne mémorise que les
nœuds du chemin menant au but).

Exemple : Par exemple, si le nombre de successeur est 2 et limite profondeur 3 :

Cours Fond. IA H. AZZOUNE USTHB 2024/2025 9

 Sol X
L’ordre est : A, B, D, H, I, E, J, K, C, F, L, M, G, N, O
Complétude: non si profondeur infinie, (ou des cycles), oui si espace fini ou
acycliques ou on évite les états répétés
Complexité en temps : b*b...*b m fois donc O(bm) (cas pire en X)
Complexité en espace : b+b+.... +b donc O(bm) (cas où but est sol :2+2+2)
Optimal : Non.
Implémenté à l’aide d’une pile. Les nouveaux nœuds générés vont en sommet de la pile.

3.2 Recherche en Largeur d’abord:

Les nœuds de Ouvert sont triés dans l’ordre croissant de leur profondeur. Les
moins profonds sont placés en premier. Cette recherche garantit la découverte du
chemin le plus court s’il existe. Dans le cas où il n’existe pas elle échouera pour les
graphes finis et boucle pour les graphes infinis.

Complétude : Oui si b fini

Complexité de temps b0 + b1 + b2 + b3 + … + bd = O(bd)
« d’espace b0+b1+b2 +… bd=O(bd) (on garde tous les nœuds en mémoire)
Optimal : non en général, oui si le coût de toutes les actions est le même.
L’ordre est : A, B, C, D, E, F, G, …..
Implémenté à l’aide d’une file; les nouveaux successeurs vont à la fin.

Cours Fond. IA H. AZZOUNE USTHB 2024/2025 10

Exemple: Pour b = 10, une puissance de calcul 10 000 nœuds par seconde et un espace
de 1000 octets de mémoire pour un nœud:
Pour une profondeur 8, il faut 109 nœuds, 31 h de calcul et 1 Téra d'espace.
Pour une profondeur 12, il faut 1013 nœuds, 35 ans de calcul 10 Petaoctets,(1024 Téra)

3.3 Profondeur limitée

C’est le même algorithme que celui de profondeur d’abord, mais avec une limite de l
sur la profondeur.
Complétude : oui, si l ≥ d
Complexité en temps : O(bl)
Complexité en espace : O(bl)
Optimal : Non
3 possibilités: solution, échec ou absence de solution dans les limites de la recherche

3.4 Profondeur itérative

Le problème avec la recherche en profondeur limitée est de fixer la bonne valeur de
la profondeur l. La profondeur itérative est de répéter la méthode de profondeur
limitée pour toutes les valeurs possibles de l = 1, 2, … Elle a les mêmes propriétés
que la précédente. Elle évite le problème de trouver une limite pour la recherche
profondeur limitée et combine les avantages de largeur d’abord (complète et optimale).
Elle a la complexité en espace de profondeur d’abord.
Complétude : oui
Complexité en temps : : (d+1)b0 + db1+ (d‐1)b2 + …..+ bd = O(bd)
Complexité en espace : O(bd)
Optimal : Oui, si le coût de chaque action est de 1.

3.5 Recherche bidirectionnelle

On exécute 2 explorations simultanées: en aval depuis l'état initial et en amont à
partir du but. On arrête les explorations lorsque les deux se rencontrent au milieu.
Applicable si on peut faire une recherche à partir du but. On a besoin d’une vérification
efficace de l’existence d’un nœud commun aux deux arbres. Il faut conserver tous les
nœuds d’au moins un des arbres.
Complétude : oui
Complexité en temps : O(bd/2)
Complexité en espace : O(bd/2)
Optimal : Oui à condition que les couts soient identiques et on utilise l'exploration
en largeur d'abord pour les 2 sens.

4. Procédure Heuristique de recherche avec graphe

Les méthodes de recherche aveugle sont des méthodes exhaustives visant à
découvrir le chemin qui mène à un nœud but. Malgré qu’elles arrivent à trouver un
tel chemin s’il existe, elles ne sont pas utilisées car elles développent trop de nœuds
avant d’arriver au but. Des alternatives plus efficaces que la recherche aveugle existent.

Cours Fond. IA H. AZZOUNE USTHB 2024/2025 11

 On peut utiliser certaines informations dépendantes au domaine appelées
« informations heuristiques » pour choisir le nœud à développer en 1er. Une
heuristique est une connaissance qui sert à nous guider lors d'un non-
déterminisme. Les procédures de recherche utilisant de telles informations sont dites
«heuristiques ».

Certaines heuristiques réduisent considérablement l’effort de recherche mais ne

garantissent pas de trouver le chemin optimal. On essaye de minimiser une combinaison
du coût du chemin et du coût de la recherche requise pour obtenir ce chemin. On
s’intéresse à des méthodes qui minimisent la moyenne de cette combinaison.

Définition: On dit qu’une méthode de recherche 1 a plus de puissance heuristique

qu’une méthode 2, si la combinaison moyenne du coût de recherche de la méthode 1 est
plus basse que celle de la méthode 2.

Les coûts moyens ne sont jamais en réalité calculés, car il est difficile de décider du
moyen de combiner le coût du chemin et le coût de recherche et aussi il est difficile de
définir une distribution statistique sur le problème. Pour cette raison c’est à l’intuition et
l’expérience qu’il appartient de décider si une méthode a plus de puissance heuristique
qu’une autre.

4.1 Utilisation des fonctions d’évaluation.

Comme information heuristique pour ordonner les nœuds dans "ouvert", on peut
utiliser une fonction à valeurs réelles sur les nœuds appelée fonction d’évaluation-
(promesse d’un nœud (exemple : probabilité que le nœud se trouve sur le bon chemin).

Soit une fonction f dont la valeur f(n) au niveau du nœud n donne l’estimation du coût
d’un chemin optimal allant du noud de départ d au nœud but en passant par n. Une fois
cette fonction définie, on ordonne les nœuds, suivant un ordre croissant (si 2 nœuds ont
la même valeur, leur classement est arbitraire en accordant la priorité au nœud but). Un
nœud ayant une évaluation basse a plus de chance d'être sur un chemin optimal.

Exemple: Soit le problème du Taquin. On utilise la fonction d’évaluation: f(n)=p(n) +

w(n), où p(n) est la profondeur du nœud n dans l’arbre de recherche et w(n) compte le
nombre de cases de 1 à 8 mal placées de n par rapport au but. Par exemple la
configuration initiale suivante a une valeur f=0+4=4 (profondeur 0 et 4 cases mal
placées par rapport au but 1, 2, 6 et 8).
2 8 3 ? 1 2 3
1 6 4  8 x 4
7 x 5 7 6 5
Etat Initial But
Exercice: Donnez l’espace de recherche en utilisant cette fonction d’évaluation

Remarque : Si la fonction est f(n)=p(n), on obtient la recherche en largeur d’abord.

Cours Fond. IA H. AZZOUNE USTHB 2024/2025 12

 Le choix de la fonction a un effet déterminant sur les résultats de la recherche. En
effet, l’utilisation d’une fonction qui ne parvient pas à reconnaître certains nœuds
prometteurs peut produire des chemins dont le coût n’est pas minimal. En revanche, une
fonction qui surestime les résultats que promettent tous les nœuds produit un nombre
trop élevé de nœuds développés (exemple recherche en largeur d’abord).

4.2 Recherche avec cout uniforme

On associe des couts aux règles (actions). On développe le nœud ayant le coût le plus
bas de l’état initial à ce nœud. Elle est équivalente à largeur d’abord si le coût des
actions est toujours le même.
Complétude : oui (si le cout >0)
Complexité en temps : O(bd)
Complexité en espace : O(bd)
Optimale : oui
Exemple : en TP

4.3 Recherche Meilleur d’abord (Gloutonne)

_ Sa fonction heuristique h(n) est une estimation du coût du nœud n au but. Dans
cette recherche on minimise le coût estimé pour atteindre le but. Le nœud qui semble
être le plus proche du but sera choisi en priorité.

Complétude : Non, peut rester pris dans une boucle, oui si espace de recherche fini et
si vérification d'absence de boucle.
Complexité en temps: O(bm)(une bonne heuristique peut réduire ce temps)
Complexité en espace: O(bm) garde tous les nœuds en mémoire
optimale : Non, elle s’arrête à la première situation But trouvée

Remarque :
la performance de cette recherche est fonction de la précision de h(n). Avec une
bonne fonction heuristique, les complexités en temps et en espace peuvent être
fortement réduites.

4.4 Algorithme A*
La recherche meilleur d’abord (précédente) minimise le coût estimé h(n) de n au
but réduisant ainsi le coût de la recherche pour atteindre le but, mais elle n’est pas
optimale et n'est pas complète.
La recherche coût uniforme (précédente) minimise le coût g(n) de l'état initial au
nœud n, elle est optimale et complète, mais pas très efficace.

Idée : combiner les deux algorithmes et minimiser le coût total f(n) du chemin
passant par le nœud n: f(n) = g(n) + h(n).

Définition: Définissons la fonction d’évaluation f pour que la valeur f(n) estime la

somme du coût du chemin optimal depuis le nœud initial d au noeud n, plus le coût du

Cours Fond. IA H. AZZOUNE USTHB 2024/2025 13

chemin optimal du nœud n à un nœud but (f(n) est une estimation du coût du chemin
optimal de l’état initial d à un état but passant par n). Le nœud dans « Ouvert » ayant la
plus petite valeur de f est donc le nœud estimé et approprié à être développé en 1er.

Notations: Soit les fonctions k, h* et g* telles que:

k(ni, ni+1) donne le coût réel entre 2 nœuds ni et ni+1 relié par un arc.
k(n, ti) donne le coût du chemin optimal du nœud n à un nœud but ti
h*(n) = min( k(n,ti) ) sur les ti (la fonction h* n’est pas définie
pour les nœuds à partir desquels un but n’est pas atteint)
C’est le cout minimal de n à un nœud but ti
k(d, n) le coût du chemin optimal du nœud de départ d à n.
g*(n)=min k(d, n) pour tous les nœuds n accessibles à partir de d.

f*(n) =g*(n) + h*(n) la somme du coût réel du chemin optimal du nœud

d au nœud n + le coût d’un chemin optimal du nœud n au but.
f*(n) est donc le coût d’un chemin optimal commençant en d, passant par n et atteint un
but.

Nous souhaitons que f soit une estimation de f* . soit f(n)=g(n)+h(n) où g est une
estimation de g* et h une estimation de h* :
- Un choix simple pour g(n) peut être le coût du chemin dans l’arbre de recherche de d à
n donné en additionnant les coûts des arcs traversés de d à n (chemin déjà parcouru).
- Pour l’estimation h(n) de h*(n), nous comptons sur l’information heuristique du
domaine (par exemple similaire à la fonction w(n) du Pb du Taquin). h est appelée la
fonction heuristique.

Nous appelons l’algorithme de Recherche avec Graphe utilisant la fonction

f(n)=g(n)+h(n), l’Algorithme A.

Si h est un minorant de h*(c.-à-d. h(n) ≤ h*(n) ∀n ou h* est le cout optimal réel de n au

but) alors l’algorithme A trouvera un chemin optimal vers un but. Lorsque l’algorithme
A utilise une fonction heuristique h qui est un minorant de h*, nous l’appelons A*.

Admissibilité de A*
On dit qu’un algorithme de recherche (ou une heuristique) est admissible (minorant)
si, pour tout graphe, il se termine toujours par un chemin optimal de d à un noeud but
(lorsqu’un tel chemin existe)
c.-à-d. que pour tout nœud n à partir duquel un nœud but peut être atteint, h(n)
<= au cout du chemin optimal de n à un nœud but.

Théorème :
si A* utilise une fonction heuristique admissible, c.-à-d. qui ne surestime jamais le
coût réel ((∀n) 0≤ h(n) ≤ h*(n) avec h*(n) coût optimal réel de n au but), alors A* est
optimal. Une fonction heuristique admissible est toujours optimiste.

Cours Fond. IA H. AZZOUNE USTHB 2024/2025 14

Preuve d'optimalité de A*
Supposons qu'il existe un état but non optimal G' dans Ouvert et qui n'est pas choisi.
Soit n un nœud non développé sur le chemin le plus court vers un état but optimal G.

d f (G') = g(G') car h(G') = 0 (car G' est un but), qui est
> g(G) (car G' n'est pas optimale), qui est
≥ f (n) car h est admissible
n
et donc f (G') > f (n), donc A* ne va pas choisir G'

G G'
1

Propriété :
Une heuristique est consistante si pour tout nœud ni et tout successeur ni+1 par
l'action ‘a’, nous avons l'inégalité: h(ni) - h(ni+1) ≤ cout(a).

Remarque : h(n)=0 pour tous les nœuds buts n.

Définition : Une heuristique h est consistante (monotone) si h(n1) − h(n2) ≤ k*(n1,

n2), c-à-d la différence entre les fonctions heuristiques de deux nœuds successifs ne doit
jamais dépasser le cout nécessaire pour passer de n1 à son successeur n2.

Les fonctions heuristiques consistantes sont toujours admissibles, mais les

fonctions heuristiques admissibles sont très souvent, mais pas toujours, consistantes.

Propriétés A*
_ Complétude : Oui, sauf si nombre infini de noeuds
_ Complexité en temps : exponentielle O(b m)
_ Complexité en espace : garde tous les noeuds en mémoire O(b m)
_ Optimal : Oui (si h admissible)

4.5 Exemples d’heuristiques pour le Taquin :

- h(n) = nombre de cases (de 1 à 8) mal placées par rapport au but
- h(n) = somme des distances (Manhattan) de chaque case (de 1 à 8) à sa position
finale du but

Comparaison des algorithmes A*

Résultat : Si A1 et A2 sont 2 versions de A* telles que A2 est plus informé que A1 (c-a-
d que ∀ noeud n non but, h2(n) > h1(n)), avec h1 et h2 admissibles, chaque nœud
développé par A2 est développé par A1. Il s’ensuit que A1 développe au moins autant
de nœuds que A2. (avec h2, A* développe moins ou autant de nœud qu'avec h1 et donc
A2 est meilleur que A1).

Cours Fond. IA H. AZZOUNE USTHB 2024/2025 15

Notions de chaînage avant et chaînage arrière :
Lors de la résolution du problème précédent, nous avons travaillé en
chainage avant c-à-d allant de l’état initial vers l’état but. On distingue 3
types de chaînage :
- Le chaînage avant (allant de l’état initial vers l’état but comme l’exemple
précédent)
- Le chaînage arrière (allant du but vers l’état initial). A partir d’un but B
on produit un sous but B’ qui si une règle est appliquée à ce sous but B’
elle nous produit le but B
- Chaînage bidirectionnel (combinaison des 2 chaînages)

Exemples de Problèmes
Exemple 1
Soit le problème du voyageur du commerce qui consiste à minimiser le
chemin pour partir d’une ville A, visiter 4 autres villes B, C, D, E en ne
passant qu’une seule fois et revenir à la ville de départ A. On a les
distances séparant chaque 2 villes.
Exemple 2:
Soit le problème d’analyseur syntaxique et soit une grammaire G. Le but
est de voir si un mot W appartient au langage L généré par G.

Systèmes de Productions spécialisés.

1) SE commutatifs : On dit qu’un SE est commutatif s’il vérifie les 3
conditions suivantes :
a) Chaque règle des règles applicables à un état B est aussi applicable à
l’état résultant de l’application de R à B
b) Si le but est satisfait par B alors il est satisfait par R(B) pour toute
règle R appliquée à B
c) L’état obtenu en appliquant à B toute séquence de règles qui est
appliquée à B ne change pas quelque soit les permutations
effectuées sur la séquence.

Exemple : Soit un SE avec 3 règles R1, R2 et R3 qui sont applicables à

un état EI. Ce SE est commutatif.

Cours Fond. IA H. AZZOUNE USTHB 2024/2025 16

 Rmq : On peut utiliser la stratégie irrévocable pour les SE commutatifs.

2) SE décomposables : Dans certains problèmes il est plus commode et

plus intéressant de décomposer le problème en sous problèmes. On
décompose l’état en sous-états qui peuvent être traitées séparément.
Les règles peuvent être appliquées à ces s/états séparément ou en
parallèle. Il faut aussi être capable de décomposer la condition
d’arrêt. Les SE où on peut décomposer l’état initial et le but sont
appelés des SE décomposables.

Exemples de SE décomposables :
1) Découverte de structures chimiques organique (Dendral)
2) Intégration symbolique

Cours Fond. IA H. AZZOUNE USTHB 2024/2025 17

 Théorie des Jeux
Introduction
En 1997, Deep Blue devient le 1er programme informatique à battre un
champion du monde d'échecs en titre (Kasparov), ce qui fit une sensation.
Aujourd'hui, des programmes informatiques peuvent aussi jouer à un niveau expert
aux dames, au backgammon, ou encore au bridge. En revanche, le jeu de go (jeux
chinois) s'avère être très résistant, et aucun programme informatique ne dépasse
aujourd'hui le niveau d'un joueur de club moyen. (Il reste du travail à faire).

Dans ce chapitre, nous allons décrire cette théorie de jeux. Nous donnons une
description et une formalisation d'une certaine classe de jeux. Puis nous allons
introduire des algorithmes qui permettent d'obtenir les stratégies optimales.

Il existe de nombreux types de jeux avec des propriétés très différentes. En IA, on
s’intéresse à une classe de : jeux finis, déterministes à deux joueurs (ou plusieurs)
avec tours alternés, à information complète et à somme nulle :

Fini : Un jeu est fini si le jeu termine toujours. Dans beaucoup de jeux, exemple les
échecs, les règles du jeu imposent des conditions pour rendre le jeu fini.
Déterministe : Un jeu est déterministe si son déroulement est entièrement
déterminé par les choix des joueurs. (Des jeux utilisant les dés (exemples : le
Monopoly, le backgammon, le poker, ...) sont non-déterministes.
Information complète : Dans les jeux à information complète, les joueurs
connaissent parfaitement la configuration actuelle du jeu. Ce n'est pas le cas, par
exemple, avec la plupart des jeux comme le poker où les joueurs ne connaissent pas
les cartes des autres, (ces derniers sont des jeux à information partielle).
Somme nulle : Un jeu est dit à somme nulle si la valeur gagnée par l'un des
joueurs est la valeur perdue par l'autre. Le poker est un exemple d'un jeu à somme
nulle parce que le montant qui est gagné par un joueur 1 est égal à la somme des
montants perdus par les autres joueurs. Les jeux où il y a toujours un gagnant et un
perdant sont des jeux à somme nulle.

Exemple :
Le tic-tac-toe est un bon exemple. Il est fini parce qu'une partie dure au plus 9
tours, il est déterministe parce que le hasard n'intervient pas, il est à information
complète parce que les deux joueurs connaissent l'état de la grille, et il est à somme
nulle parce que lorsqu'un joueur gagne, c'est l'autre qui perd.
Les échecs et le jeu de dames sont deux autres exemples de jeux de cette classe.

Formalisation :
La formalisation d’un problème de jeux se fait presque de la même manière que les
systèmes d’états dans la résolution de problème à quelques ajouts près :

Etat initial : C'est une configuration du jeu à l‘état initial (comme dans les systèmes
d’états) plus le nom de joueur à jouer en premier.
Fonction de successeur : La fonction définit quelles actions sont possibles pour un
joueur dans une configuration donnée, ainsi que les configurations résultantes des
différentes actions (elle correspond aux règles de changements d’état).

Fondements IA ING 3 Eng Soft USTHB 2024/2025 H. AZZOUNE

Test de terminalité : Ce test définit les configurations terminales du jeu c’est(le but).
Fonction d'utilité : Cette fonction associe une valeur à chaque configuration
terminale. Souvent, les valeurs sont +1, -1, et 0 qui correspondent respectivement à
un gain pour le 1er joueur, une perte pour le 1er joueur et un match nul (parfois +∞ et
-∞ sont utilisés au lieu de +1 et -1 ou autres valeurs). (On ne considére que les jeux à
somme nulle, nous n'avons besoin que d'une seule valeur par configuration : la valeur
attribuée au 2eme joueur est exactement le négatif de la valeur reçue par le 1er joueur).
L'objectif du jeu pour un joueur est de maximiser son gain. Plus spécifiquement, le
1er joueur veut que la valeur d'utilité de la configuration terminale du jeu soit la plus
grande possible (max), et inversement, le 2eme joueur souhaite que cette valeur soit la
plus petite possible (min) (parce que lui reçoit le négatif de cette valeur).

Afin de pourvoir se rappeler de leurs objectifs respectifs, il est courant d'appeler les
deux joueurs par max et min et c’est max qui commence à jouer en 1er.

Exemple de formalisation du jeu Tic-Tac-Toe:

Etat initial La grille 3x3 vide (matrice) et un nom de joueur à jouer, X par exemple.
Fonction de successeur Quand c'est le tour de joueur X, il peut mettre un X dans un
des cases vides de la grille (à condition que la case soit vide). Même chose pour
l’autre joueur O, mettre O.
Test de terminalité Une configuration est terminale s'il y a 3 X (ou 3 O ) sur une
ligne, une colonne, ou une diagonale, ou si la grille est complète.
Fonction d'utilité Exprime la récompense reçue par le joueur X. Nous donnons une
valeur +1 à toute configuration terminale contenant 3 X dans une ligne, colonne, ou
diagonale (c'est X qui gagne), et -1 à toute configuration terminale avec 3 O dans une
même ligne, colonne, ou diagonale (c'est O qui gagne). Les autres configurations
terminales ont pour valeur 0, puisqu'elles correspondent à un match nul.

Arbre de jeu
Un jeu peut être représenté par un arbre de jeu où :
-Les nœuds sont les configurations
-Les arcs les coups possibles.
-Les feuilles de l'arbre sont des configurations terminales, qui sont étiquetées par
leurs valeurs d'utilité. 7
-Un Nœud est appelée un nœud max si c'est à max de jouer, et est appelée un nœud
min dans le cas contraire.

Dans la Figure ci-dessous, on donne une partie de l'arbre de jeu pour le tic-tac-toe.
La racine de l'arbre correspond à la configuration initiale dans laquelle la grille est
vide. Les fils de la racine correspondent aux 9 coups possibles pour le joueur max (qui
joue les X). Chacun de ces nœuds possède 8 fils, qui correspondent aux différentes
façons pour min de répondre, et ainsi suite. 3 des configurations terminales sont
présentées : dans le 1er, c'est min qui gagne (valeur d'utilité = -1), dans le 2eme, c'est
un match nul (valeur 0), et dans le dernier c'est une victoire de max (valeur +1).

Pour les problèmes de recherche classique, nous cherchons une solution, c-a-d une
suite d'actions reliant l'état initial à l'état but. Pour les jeux, une simple suite de coups
n'est pas suffisante parce que nous ne savons pas quels seront les coups de
l'adversaire. Il faut trouver une stratégie qui définit comment le joueur doit jouer dans
toutes les évolutions possibles du jeu. Plus concrètement, une stratégie consiste en un

Fondements IA ING 3 Eng Soft USTHB 2024/2025 H. AZZOUNE

premier coup, puis un choix de coup pour chaque réponse possible de l'adversaire,
puis un choix de coup pour les réponses à notre dernier coup, et ainsi suite.

On dit qu'une stratégie est optimale s'il n'existe pas d'autre stratégie qui
donnerait un meilleur résultat contre un adversaire idéal.

Une partie de l’arbre de recherche pour le jeu du Tic-Tac-Toe.

Etat initial Max(X) joue

Min(O)
X X X
X X X
X X X

Max(X) ……….8 possibilités

X O X O X
O

Min(O) …………………….7 possibilités

X O X X O X O
X X

……….. ……………..

Buts (à diverse profondeurs) ………..

X O X X O X X O X
O X O O X X
O X X O X O O
VU :-1 0 +1 ………….
Min gagne Match nul Max gagne

Algorithme MiniMax
L'algorithme Minimax est un algorithme utilisé dans les jeux à 2 joueurs, (échecs,
tic-tac-toe, …). Un joueur essaie de maximiser ses gains tout en minimisant ceux
de l'adversaire. Cela signifie que chaque joueur suppose que l'adversaire jouera le
meilleur coup possible pour lui-même.

Une stratégie optimale peut être obtenue en examinant les valeurs mini-max
des nœuds de l'arbre de jeux.
La valeur minimax d'un nœud donne la valeur d'utilité qui sera atteinte si chaque
joueur joue de façon optimale à partir de la configuration de ce nœud.
Pour calculer ces valeurs, nous commençons avec les configurations terminales,
dont les valeurs minimax sont leurs valeurs d'utilité. Puis, nous évaluons chaque
nœud non-terminal en utilisant des valeurs minimax de ces fils :

Fondements IA ING 3 Eng Soft USTHB 2024/2025 H. AZZOUNE

 -La valeur minimax d'un nœud max sera le maximum des valeurs minimax de
ces fils, car le joueur max veut maximiser la valeur de la configuration terminale.
-La valeur minimax d’un nœud min, sera le minimum des valeurs minimax de
ces fils, car le joueur min veut minimiser la valeur de la configuration terminale:
Utilité(n) si n est terminal
Minimax(n) = max(s ε successeurs(n)) Minmax(s) si n est un nœud max
min(s ε successeurs(n)) Minmax(s) si n est un nœud min

Exemple1 : Nous illustrons le calcul des valeurs minimax sur l'arbre de jeux suivant :

Les valeurs minimax des nœuds terminaux b, f, h, j, m, n, o, p, q, et r sont

simplement leurs valeurs d'utilité, (rien à calculer au niveau de ces nœuds feuilles).

Les valeurs minimax pour les nœuds intérieurs de l’arbre sont calculées (en rouge) :
Le nœud l est un nœud max donc on prend le maximum de ces fils, ce qui donne 1.
Le nœud i est un nœud min, on prend le minimum de ces fils, obtenant 1.
Le nœud e qui est max, on obtient 1.
Le nœud c de type min a une valeur 1 car ses 2 fils ont des valeurs de 1.
Le nœud k de type min a la valeur -1 car on prend le minimum des valeurs de n et o.
g a une valeur de -1 (c'est le maximum des valeurs de j et k)
d a une valeur de -1(car il n'y a qu'un seul coup possible dans d).
La valeur de a est donc 1 ( le maximum des valeurs de b, c, et d).

Comment déterminer la stratégie optimale à partir des valeurs minimax ?

Si nous sommes le joueur max et c'est à nous de jouer, nous devrons choisir un
coup qui amène à un nœud avec une valeur minimax maximale.
 Inversement, pour le joueur min, le meilleur coup est celui qui a la plus petite
valeur minimax.
Dans cet exemple, la valeur minimax de a est 1, ce qui signifie que le joueur max
peut gagner s'il suit la stratégie optimale, peu importe les coups de l'autre joueur. Quel
est le meilleur premier coup pour max ? Nous voyons que c'est en allant vers c que
nous arriverons à une valeur de 1. Si min choisit ensuite f, max gagne (car valeur de f
est 1 donc max gagne), et si min choisit e, max peut jouer h (et gagne toute de suite
car valeur de h est égale à 1) ou peut jouer i et puis rien (si min joue m) ou q (si min
choisit l).

Dans tous les cas, c'est le joueur max qui gagne à condition qu'il suive bien la
stratégie donnée par minimax c.-à-d. choisir le coup « jouer c ».

En principe, le calcul des valeurs minimax pourrait se faire en parcours en

profondeur ou en parcours en largeur. Il est néanmoins préférable d'utiliser le parcours
en profondeur car nous réduisons ainsi la complexité spatiale du calcul. Voici un
algorithme récursif pour calculer les valeurs minimax (ce qui est rouge dans l’arbre):

fonction minimax(n)
si n est un nœud terminal /* feuille de l’arbre */
alors retourner la valeur d'utilité de n /* donc on prend sa valeur d’utilité */
sinon si n est un nœud de type min /* si le nœud est de type min */
alors v = +∞ /* on prend le min de ses fils */
pour tout fils f de n
faire v = min(minimax(f), v) /* appel récursif */
retourner v /* v contient le min des fils de n */
sinon v = -∞ /* sinon, n est un max, donc on prend le max de ses fils*/
pour tout fils f de n
faire v = max(minimax(f), v) /* appel récursif */
retourner v /* v contient le max des fils de n */
fin si
fin si

Pour un arbre avec un facteur de branchement de b et une profondeur p, cet

algorithme a une complexité spatiale de O(p*b) (il y a au plus p*b nœuds en mémoire
en même temps) mais une complexité temporelle de O(bp) (nous avons besoin de
visiter tous les nœuds de l'arbre).

Exemple 2 : soit l’arbre de jeux suivant avec ses valeurs d’utilité des nœuds feuilles

après calcul des valeurs minimax des nœuds intérieurs (non feuilles), on obtient :
 Le nœud « a » a comme valeur 0 (match nul) et donc nous pouvons conclure que le
joueur max ne peut pas gagner contre un adversaire qui joue de façon optimale, mais
il peut garantir un match nul en choisissant b pour son premier coup.

Extensions : L'algorithme minimax peut être étendu au cas où il y a plus de 2

joueurs (il nous faut un vecteur d'utilités pour en prendre compte les utilités des
différents joueurs). Il est aussi possible de l'étendre aux jeux stochastiques, en
ajoutant les nœuds supplémentaires aux arbres de jeu pour prendre en compte l'aspect
stochastique (nœuds pour représenter les lancers de dés) et en utilisant les probabilités
des différentes configurations résultantes dans le calcul des valeurs minimax. Cette
variation de l'algorithme classique est connue sous le nom expectiminimax.

Algorithme Elagage Alpha-Beta

L'algorithme minimax visite chaque nœud de l'arbre. Dans le pire des cas, un
parcours complet ne peut pas être évité, mais dans beaucoup de cas, on n’a pas besoin
de tout examiner pour déterminer le meilleur coup. On peut élaguer certaines
branches de l’arbre. Soit le 1er exemple:

On remarque qu'après avoir visité h (valeur d’utilité 1), on sait déjà que max peut
gagner depuis l'état e (valeur minimax 1). Nous aurions pu donc donner tout de suite
la valeur 1 à e sans regarder le nœud i (ni ses descendants) car max(1, vali)=1 si
vali=0, 1, -1. De même pour c (valeur 1), inutile de voir d, car on a trouvé une
stratégie gagnante pour max (valeur 1 en c) donc en « a » on est sur d’avoir 1.

Dans ce graphe on a montré la partie de l'arbre qui serait examinée si nous faisions
le calcul des valeurs d'une manière intelligente. On voit qu’avec ce raisonnement,
nous avons réussi à réduire le nombre de nœuds examinés (partie grise élaguée).
 Ces observations sont à la base de l'algorithme alpha-beta, qui est une version plus
sophistiquée de l'algorithme minimax. L'algorithme alpha-beta calcule la valeur
minimax d'un nœud sans nécessairement calculer les valeurs de tous ses descendants.

Le nom de cet algorithme vient des 2 variables α et β qui sont utilisées pour stocker
les valeurs des meilleurs options pour les joueurs max et min respectivement.

Alpha : Représente la valeur maximale que le joueur maximisant (appelé MAX) peut
garantir jusqu'à ce moment. Initialement, c'est -∞.

Bêta : Représente la valeur minimale que le joueur minimisant (appelé MIN) peut
garantir jusqu'à ce moment. Initialement, c'est +∞.

Élagage : Si, à un certain nœud, on voit qu'un choix ne sera jamais pris (parce qu'il est
inférieur à alpha pour MAX ou supérieur à bêta pour MIN), l'algorithme arrête
l'évaluation de cette branche.

Remaques :
Si nous arrivons à un nœud min n qui a un fils dont la valeur est pire (ou égale) à
la valeur α (meilleure possibilité actuelle pour max), on sait que max ne va jamais
choisir une action qui amène à n.
Inversement, si nous sommes à un nœud max n qui a un fils dont la valeur est
supérieure à la valeur β ( la meilleure possibilité examinée pour min), il est inutile de
continuer à explorer cette branche car min ne choisira pas n de toute façon.

L'algorithme :
vmin et vmax sont le maximum et minimum des valeurs d'utilité des nœuds
terminaux (correspondant à α, β). On prend -∞ et +∞ comme valeurs initiales pour α
et β. Mais on peut utiliser les valeurs Min et Max trouvés dans l’arbre au lieu de -∞ et
+∞ (comme par exemple -1 et 1, ou -23 et 16 pour les exemples précédents). Le 1er
appel se fait avec : valeur-alpha(racine).

fonction valeur-alpha-beta(n)
retourner alpha-beta(n, vmin, vmax)
fin

Fondements IA ING 3 Eng Soft USTHB 2024/2025 H. AZZOUNE

fonction alpha-beta(n, α, β)
si n est un nœud terminal
alors retourner la valeur d'utilité de n
sinon si n est un nœud de type min /* n est un nœud min */
alors v = +∞
pour tout fils f de n
faire v = min(v, alpha-beta(f, α, β)) /* appel récursif */
si v ≤ α /* on a trouvé une valeur inferieur ou égale à α */
alors retourner v /* arrêter la recherche sur les fils */
β = min(β, v) /* β va prendre le min de β et de v */
fin pour
retourner v /* retourner v à l’appel « récursif » de alpha-beta*/
sinon v = -∞ /* n est un nœud max */
pour tout fils f de n
faire v = max(v, alpha-beta(f, α, β)) /* appel récursif */
si v ≥ β /* on a trouvé une valeur supérieur ou égale à β*/
alors retourner v /* arrêter la recherche sur les fils*/
α= max(α, v) /* α va prendre le max de α et de v */
fin pour
retourner v /* retourner v à l’appel « récursif » de alpha-beta*/
fin si
fin si

Cet algorithme est proche de celui minimax. Nous gardons en mémoire les valeurs
des meilleures possibilités pour min et max (en utilisant les variables α et β). Quand
nous arrivons à une configuration qui ne sera, quoi qu'il arrive, jamais choisie par un
joueur (car il y a mieux ailleurs) nous arrêtons la recherche sur cette partie de l'arbre.

Il est important de remarquer que les valeurs retournées par alpha-beta (et donc les
choix de coups) sont exactement les mêmes qu'avec l'algorithme minimax. Donc nous
pouvons utiliser alpha-beta sans perdre la garantie de l'optimalité.

Fondements IA ING 3 Eng Soft USTHB 2024/2025 H. AZZOUNE

 Exemple : Essayons d'appliquer l'algorithme alpha-beta à l'arbre de jeu (rempli):

-Appeler la fonction valeur-alpha-beta(a), (voir figure ci-dessous -23 et 16)

-Appeler alpha-beta(a, -23, 16),
-Appeler alpha-beta(b, -23, 16),
-Appel pour son fils e alpha-beta(e, -23, 16), qui est terminal, donc nous renvoyons sa
valeur d'utilité 0, on a maintenant v = 0 et β = 0 (nous sommes dans l'appel de b).
-appeler l'algorithme sur f et g, mais la valeur v de b (qui est min) ne change pas car
les valeurs d'utilité de f et g sont supérieures à 0. Nous renvoyons donc la valeur 0
pour b. Ceci nous permet de mettre à jour la valeur α pour « a » parce que maintenant
nous savons que nous ne pouvons pas faire pires que 0.
-appel pour c (maintenant avec α = 0 et β = 16).
-appel pour son fils h qui nous renvoie sa valeur d'utilité -1. Nous mettons donc v= -1,
et on renvoit cette valeur pour c car on a v= -1 qui est ≤ α qui est = 0.
-on revient donc à l'appel initial de a,
-appeler ensuite la fonction sur le dernier fils « d » de « a ».
-on cherche d'abord la valeur du petit fils k, et nous trouvons v = 16.
-on passe au deuxième fils l dont la valeur est égale à -2.
-On renvoit cette valeur pour d (qui est min) sans regarder le dernier fils m car on a
v = -2 qui est ≤ α = 0.
-On a donc déterminé la valeur de « a » (qui est 0), ce qui est exactement ce que nous
avions trouvé avec l'algorithme minimax sauf que nous n'avons pas visité tous les
nœuds de l'arbre.
 Sur cet exemple, remarquez que nous ne déterminons pas la valeur précise des
nœuds c et d car elles ne sont pas nécessaires pour établir la valeur de la racine a.
Notez également que les nœuds i, j, et m ne sont pas examinés lors de la recherche.

L'algorithme alpha-beta peut réduire le nombre de nœuds examiné pour avoir la

stratégie optimale, mais son efficacité est très dépendante de l'ordre dans lequel les
nœuds de l'arbre sont examinés.
Dans le pire ordre, nous ne réalisons pas de gain de temps car nous explorons tout
l'arbre, comme avec minimax. Si par contre nous suivons l'ordre optimal, l'algorithme
alpha-beta donne une complexité temporelle de O(bp/2) au lieu de O(bp) pour
l'algorithme classique minimax. La complexité reste exponentielle, mais nous
pouvons maintenant examiner un arbre avec une profondeur 2 fois plus grande, ce qui
n'est pas du tout négligeable. Nous ne savons pas déterminer l'ordre idéal, mais en
pratique il est possible de trouver des heuristiques qui permettent à approcher de très
près cette limite théorique.

Autre exemple détaillé

Max

Min Min

Max Max Max Max

3 12 8 2 14 5 0 7
Configuration Initiale
• Max est le joueur racine, qui veut maximiser son score,
• Min veut minimiser le score pour Max.
• Nous utilisons alpha (la meilleure valeur possible pour Max) et beta (la meilleure
valeur possible pour Min).
o Initialement, alpha = -∞ et beta = +∞.
Étapes de l'Alpha-Beta
Étape 1 : Max explore la première branche avec Min
1. Max commence en explorant la première branche à gauche avec Min.
o Max passe la valeur d'alpha = -∞ et beta = +∞ à Min.
Étape 2 : Min explore ses enfants dans la première branche
2. Min explore ses deux enfants, le Max de gauche et le Max de droite dans cette
branche (les plus à gauche).
o Pour la sous-branche gauche de Min, alpha = -∞ et beta = +∞.
Exploration de la branche gauche de Min (Max avec valeurs 3 et 12)
3. Max dans cette sous-branche explore ses enfants, qui sont des feuilles avec 3 et 12.
o Max voit la feuille avec 3 et met à jour alpha = 3.
o Max explore ensuite la feuille avec 12 et met à jour alpha = 12.
4. Min reçoit 12 dans cette sous-branche (il minimise) et met à jour beta =12.
Exploration de la branche droite de Min (Max avec valeurs 8 et 2)
5. Min continue avec sa branche droite, où Max a des feuilles avec des valeurs 8 et 2.
o Max commence avec la feuille de valeur 8, donc alpha = 8.
o Max explore ensuite la feuille avec 2 et met à jour alpha = 2.
6. Min reçoit 2 pour cette branche (il choisit la valeur minimale) et met à jour beta = 2.
Résultat pour la branche gauche de Max

Fondements IA ING 3 Eng Soft USTHB 2024/2025 H. AZZOUNE

7. La meilleure valeur pour Min dans la première branche de Max est 2. Max reçoit
donc un score de 2 pour la première branche.
8. Max met à jour alpha = 2 pour cette branche.
Étape 3 : Max explore la deuxième branche avec Min
9. Max passe maintenant à la deuxième branche avec Min à droite. Ici, alpha = 2 et beta
= +inf.
Exploration de la branche droite de Min (Max avec valeurs 14 et 5)
10. Min commence par explorer la sous-branche gauche, où Max a des feuilles de valeurs
14 et 5.
o Max voit la feuille avec 14 et met à jour alpha = 14.
o À ce stade, Min voit que alpha = 14 est supérieur à beta = 2 (valeur optimale que Max
a déjà). Cela déclenche un élagage.
11. Comme alpha > beta (14 > 2), Min arrête d'explorer cette sous-branche, car elle ne
pourra jamais améliorer la valeur de Max obtenue dans la première branche (score de
2).
Résultat Final
12. L'algorithme s'arrête et Max choisit la première branche avec un score optimal de 2.
Explication de l’élagage
Grâce à l'alpha-beta:
• La sous-branche droite de Min dans la deuxième branche de Max (feuilles avec
valeurs 0 et 7) n'a jamais été explorée, car alpha > beta a été atteint avant.
• L'algorithme a évité d'explorer plusieurs branches, économisant ainsi du temps de
calcul tout en garantissant le meilleur score pour Max.
Dans cet exemple, Alpha-Beta a permis d'ignorer des nœuds inutiles dans l'arbre de
décision, rendant l'exploration plus efficace et rapide.

Fondements IA ING 3 Eng Soft USTHB 2024/2025 H. AZZOUNE

 Les méta heuristiques
Introduction :
Les méta heuristiques sont des méthodes d'optimisation conçues pour résoudre
des problèmes complexes où les techniques traditionnelles d'optimisation
peuvent échouer ou être inefficaces.
Elles sont particulièrement utiles pour les problèmes où la recherche d'une
solution optimale dans un délai raisonnable et difficile en raison de la complexité
du problème ou de la taille de l'espace de recherche.
Elles sont généralement appliquées à des problèmes où les solutions exactes sont
difficiles à obtenir en raison de la nature NP-difficile des problèmes (problèmes où il
n'est pas forcément possible de vérifier une solution en un temps polynomial).

Elles peuvent être définies comme des méthodes algorithmiques 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.

A)Méta heuristiques : recherche locale

C’est une approche (famille) où l'on cherche à améliorer une solution candidate
en explorant son voisinage immédiat.
-On part d'une solution initiale,
-on cherche à l'améliorer en effectuant de petites modifications (mouvements) pour
trouver une meilleure solution.
-Le processus d’amélioration se répète jusqu'à ce qu'aucune amélioration ne soit
possible ou qu'un critère d'arrêt soit atteint.

L’avantage de la recherche locale est sa simplicité car elle est facile à

implémenter ainsi que son efficacité pour les problèmes locaux (optimum local,
convergence prématurée,..): Très efficace pour améliorer des solutions dans des
espaces de recherche relativement petits.

Ses inconvénients est ce qu’on appelle les Minima Locaux pour le cas où elle
peut rester bloquée dans un minimum local, sans trouver la solution optimale.
Autre inconvénient est sa dépendance à la solution initiale (la qualité de la
solution finale peut dépendre fortement de la solution de départ).

Ses applications sont diverses : on peut l’utiliser dans la résolution de problèmes

combinatoires (comme le voyageur de commerce), l'ordonnancement, la conception
de réseaux, etc.

Quelques exemples de méta heuristiques que nous détaillons quelques unes plus tard :

[Link] climbing (sera détaillée plus loin)

La méta heuristique du Hill Climbing (ou montée de colline en français) est une
méthode d'optimisation itérative utilisée pour résoudre des problèmes où l'objectif est
de maximiser ou minimiser une fonction objective.
Cette technique est simple et intuitive. Elle repose sur l'idée de partir d'une solution
initiale et de la modifier progressivement pour l'améliorer jusqu'à ce qu'il ne soit plus

Cours [Link] ING3 Eng Soft USTHB 2024/2025 H. AZZOUNE

possible de trouver une meilleure solution dans le voisinage immédiat. C’est la
méthode la plus simple dans la catégorie de recherche locale

[Link] simulé (Simulated Annealing)

Inspiré par le processus de recuit métallurgique (le recuit métallurgique est un
traitement thermique qui consiste :
-à chauffer un matériau à une certaine température,
-à le maintenir à cette température pendant un certain temps,
-puis à le refroidir lentement.
L'objectif est d'améliorer les propriétés du matériau, comme sa ductilité, sa
résistance, ou encore d'éliminer les contraintes internes).
Le recuit simulé cherche à échapper aux minima locaux en acceptant des
solutions moins bonnes dans l'espoir de trouver un minimum global. On les utilise
dans les problèmes de routage, d'affectation et de placement.

3. Algorithmes génétiques (AG)

Inspirés par la théorie de l'évolution de Darwin, les algorithmes génétiques
utilisent des mécanismes tels que la sélection, le croisement (crossover) et la
mutation pour évoluer vers des solutions optimales.
On les utilise dans les problèmes de planification, optimisation de réseaux,
conception de circuits.

4. Recherche Tabou (Tabu Search)

Cette méthode utilise une mémoire pour éviter les cycles et améliore les
solutions en explorant des solutions voisines tout en interdisant le retour vers des
solutions précédemment visitées. On les utilise dans les optimisation combinatoire,
ordonnancement de tâches et gestion de la chaîne d'approvisionnement, Etc..
etc….

B)Autres Méta heuristiques à base de population de solution :

1)Méta heurstique à base de l’intelligence par essaim :
Optimisation par essaims particulaires (PSO)
Inspirée par le comportement collectif des animaux (comme les essaims d'oiseaux
ou les bancs de poissons), cette méthode utilise une population de "particules" qui se
déplacent dans l'espace de recherche en suivant des règles simples basées sur leur
propre expérience et celle des autres particules. On les utilise dans les problèmes
d'optimisation continue, optimisation de paramètres dans les réseaux neuronaux.

Colonies de fourmis (ACO - Ant Colony Optimization)

Inspirée par le comportement des fourmis dans la recherche de nourriture, cette
méthode utilise une population de fourmis artificielles pour explorer les solutions
possibles et renforcer les bonnes solutions en déposant des "phéromones". On les
utilise dans les problèmes de routage, optimisation de graphes.

Colonies d’abeilles (Artificial Bee Colony ABC)

inspiré par le comportement des abeilles à la recherche de nourriture, cette méta
heuristique simule la manière dont les abeilles butineuses trouvent et exploitent les
meilleures sources de nourriture, tout en permettant l'exploration de nouvelles sources
potentielles.

Cours [Link] ING3 Eng Soft USTHB 2024/2025 H. AZZOUNE

2 Algorithmes de recherche par faisceaux (Beam Search)
Il s'agit d'une technique d'exploration heuristique basée sur l'extension de plusieurs
solutions partielles en parallèle, en conservant un nombre limité de solutions
prometteuses à chaque étape. C’est une version améliorée de l'algorithme de
recherche en largeur, où, au lieu d'explorer toutes les solutions possibles à chaque
étape, on ne conserve que les meilleures solutions selon un critère donné. Il s'agit
d'une stratégie gloutonne qui explore un sous-ensemble des solutions possibles,
limitant ainsi l'explosion combinatoire. On les utilise dans la reconnaissance de la
parole, traduction automatique, résumé automatique, etc….
3. Algorithmes de recherche locale et globaux (GRASP -)
Une approche itérative qui combine des techniques gloutonnes avec des choix
aléatoires pour explorer différentes régions de l'espace de solutions. À chaque étape
de la construction d'une solution, une approche gloutonne est utilisée pour faire des
choix locaux optimaux en maximisant ou minimisant un critère. Pour éviter les
solutions sous-optimales (comme les minima locaux), elle introduit de la
randomisation dans le choix des composants de la solution, permettant ainsi de
diversifier les solutions explorées. Cet algorithme s'adapte au fur et à mesure que de
nouvelles solutions sont générées, en ajustant les probabilités de sélection pour les
prochaines étapes en fonction des résultats précédents.
On les utilise dans les problèmes de graphes, conception de circuits, optimisation
logistique, optimisation des Réseaux, routage, gestion de ressources, planification et
ordonnancement dans les problèmes de scheduling dans l'industrie ou l'informatique,
clustering où l'objectif est de grouper des éléments similaires, etc….
Nous allons détailler quelques méta heuristiques.

Cours [Link] ING3 Eng Soft USTHB 2024/2025 H. AZZOUNE

Détail de la Recherche locale :
Dans l’algorithme A* vu dans les chapitres précédents (méthodes heuristiques), on
peut faire les remarques suivantes :
-On définit un état initial, une fonction de succession et un nœud but à atteindre.
-La solution au problème consiste à trouver un chemin de l’état initial vers un état
but (pas uniquement le but), avec des fois en un temps optimal (solution optimale).
-les nœuds rencontrés sont mémorisés pour éviter de les revisiter.

Pour certains problèmes qui implique une recherche dans un espace d’états très
grand, l’algorithme A* peut ne pas être l’algorithme approprié. Surtout pour les
problèmes qui ont les caractéristiques suivantes :
-On a une fonction objective (objective function) à optimiser (soit à minimiser soit
à maximiser suivant le type de la fonction) (éventuellement en plus avec une fonction
but qui identifie un nœud final). Cette fonction nous permet d’identifier si un nœud
correspond à une bonne solution.
-La solution qu’on cherche est juste un nœud optimal (ou proche) et non le chemin
qui y mène (comme la recherche A*) c.-à-d. un nœud dont la valeur de sa fonction
objective est optimale.
-L’espace de recherche à explorer est trop grand pour pouvoir enregistrer tous les
nœuds visités (et c’est le cas de la plus part des problèmes en IA)

Avec ce constat et pour ce type de problèmes, la méthode de recherche locale peut

être la meilleure alternative.
La recherche locale en méta heuristique est une technique d'optimisation qui
consiste à explorer l'espace des solutions d'un problème pour trouver des
solutions optimales ou quasi-optimales.
Contrairement aux méthodes exactes, ces méta heuristiques ne garantissent pas de
trouver la solution optimale, mais elles sont souvent efficaces pour trouver de bonnes
solutions dans un temps raisonnable, surtout pour les problèmes complexes où les
méthodes exactes sont impraticables.

Exemple :
Placer N reines sur un damier de taille N x N de sorte que 2 reines ne s’attaquent
pas mutuellement (jamais 2 reines sur la même ligne, même colonne ou même
diagonale). Pour N=8

Le but du problème est qu’on s’intéresse à une solution c.-à-d. un nœud qui a
cette configuration). La fonction objective est par exemple le nombre de paires
reines qui s’attaquent mutuellement, qu’il faut minimiser.
Le but est de chercher un nœud qui minimise cette fonction objective (idéal
F(n)=0).
 -On remarque là que pour ce problème, le chemin ne nous intéresse pas mais ce qui
nous intéresse est la solution but (c.-à-d. disposer les 8 reines sur le damier).

Principe de la méthode :
La recherche locale démarre généralement à partir d'une solution initiale et
explore son voisinage immédiat (solutions proches) en espérant améliorer cette
solution. Elle garde juste certains nœuds visités en mémoire.
Le cas particulier est le Hill climbing où on ne garde que le nœud courant et on
l’améliore itérativement jusqu’à convergence à une solution (sera détaillé ci-dessous).
Le cas le plus élaboré est les algorithmes génétiques qui garde en mémoire un
ensemble de nœud (appelé population) et puis on le fait évoluer jusqu’à obtenir une
solution (sera détaillé ci-dessous).

En général, on a une fonction objective F spécifiée par l’utilisateur, à optimiser

(maximiser ou minimiser). Par exemple dans le Hill climbing elle permet de
déterminer quel est le nœud suivant à visiter, et pour les algorithmes génétiques elle
s’appelle fonction de fitness (fonction d’adaptation) qui intervient dans le calcul de
l’ensemble des nœuds successeurs (prochaine génération) à l’ensemble courant.

Remarque : Une recherche locale ne garantie pas de solution optimale, mais

trouver une solution acceptable rapidement.

Propriétés :
-Convient bien aux problèmes où seul l'état final nous intéresse
● On ne conserve qu'un seul état (ou un certain nombre réduit) en mémoire, soit le
nœud courant
● On considère tous les nœuds successeurs du nœud courant, qui constituent le
voisinage. On choisit un de ces nœuds, qui deviendra le nœud courant.
● On répète le processus jusqu'à l'obtention de l'état désiré c.-à-d. fonction objective
optimisée.

Mouvement :
À chaque itération, un mouvement (ou un changement) est appliqué pour passer
d'une solution à une autre dans le voisinage. Si une meilleure solution est trouvée, elle
devient la nouvelle solution courante.

Critère d'arrêt :
Le processus se poursuit jusqu'à ce qu'un critère d'arrêt soit atteint (par exemple, un
nombre maximum d'itérations ou l'absence d'amélioration après plusieurs itérations).

Quelques Applications de la Recherche Locale:

Planification d'horaires, de production, de ressources, Problèmes de voyageur de
commerce, Problèmes d'affectation, de découpe, d'emballage.

Stratégies pour Améliorer la Recherche Locale :

Diversification : Introduire des éléments aléatoires ou changer la méthode de
génération du voisinage pour éviter les pièges locaux.
Hybridation : Combiner différentes méta heuristiques pour profiter des avantages de
chacune.

Cours [Link] ING3 Eng Soft USTHB 2024/2025 H. AZZOUNE

Paramétrage Adaptatif : Adapter dynamiquement les paramètres de l'algorithme
(comme la taille du voisinage ou la température dans le recuit simulé) en fonction des
résultats obtenus au fil du temps.

Cours [Link] ING3 Eng Soft USTHB 2024/2025 H. AZZOUNE

1)Hill climing
La méta heuristique du Hill Climbing (ou montée de colline en français) est une
méthode d'optimisation itérative utilisée pour résoudre des problèmes où l'objectif est
de maximiser ou minimiser une fonction objective.
Cette technique est simple et intuitive. Elle repose sur l'idée de partir d'une solution
initiale et de la modifier progressivement pour l'améliorer jusqu'à ce qu'il ne soit plus
possible de trouver une meilleure solution dans le voisinage immédiat. C’est la
méthode la plus simple dans la catégorie de recherche locale.

Fonctionnement:
Initialisation (entrée):
-On commence par une solution initiale, choisie de manière aléatoire. Au départ de
l’algorithme, le nœud courant est initialisé au nœud initial.
-On spécifie une fonction objective à optimiser (notée F(n))
-On a une fonction générant les nœuds successeurs (les voisins) d’un nœud.

Méthode de Recherche de voisinage) : On génère les solutions voisines de la

solution actuelle (nœud n) en effectuant de petites modifications (par exemple, en
changeant une variable ou un paramètre). On évalue ces solutions voisines à l'aide de
la fonction objective qui mesure la qualité de chaque solution :
-Si une solution d’un nœud n’ voisine est meilleure que la solution actuelle
(courant) du nœud n, on se déplace vers cette nouvelle solution. n’ devient le nœud
courant (n’ remplace n).
-Si aucun voisin n’améliore la fonction objective, on arrête et on sort.

Répétition : On répète les étapes précédentes jusqu'à ce qu'aucune amélioration ne

puisse être trouvée. À ce stade, on dit que l'on a atteint un optimum local.

Voici un exemple pseudo-code de l’algorithme hill-climbing. On suppose que la

fonction objective maximise. (si elle minimise on prend n’ la plus petite valeur).

Algorithme hill-climbing(nœud_initial)
declare 2 noeuds n, n’; /* n noeud courant, n’ noeud voisin */
n = noeud_initial; /* on initialise le noeud courant n au noeud initial */
tant que vraie /* la sortie est dans la boucle tant que */
n’:=noeud_successeur de n ayant la plus grande valeur F(n’) /* ou la plus petite */
si F(n’) ≤ F(n) /* si la fonction objective était « minimiser », on prend ≥*/
alors retourner n /* on n’arrive pas à améliorer, on sort */
n :=n’ ;
fin

Remarque : cet algorithme ne garantie pas de trouver la solution optimale globale.

Dès qu’il n’améliore plus il s’arrete.

justification de la remarque:
Soit le graphe suivant. Si on initialise l’état initial à n1 dans le schéma ci-dessous,
l’algorithme va se déplacer vers la droite pour trouver le maximum local, alors qu’il
existait un autre point où la solution est optimale (maximum global). On aurait atteint
ce maximum global si on avait pris comme état initial le point n2.

Cours [Link] ING3 Eng Soft USTHB 2024/2025 H. AZZOUNE

 On aurait aussi atteint un sommet « plateau » qui n’est pas optimal si on avait
initialisé notre algorithme en n3 ou n4 (l’algorithme serait arrêté aux plateaux sans
pouvoir atteindre la solution optimale) ; Au niveau de l’état n3, on serait arrivé au
point « épaule » qui n’est pas optimal local mais qui aurait arrêté l’algorithme.

Exemple 1:
Soit la fonction objective définie dans le tableau ci-dessous par des nœuds
représentés par des entiers de 1 à 16. (on suppose que la fonction objective maximise)

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
F(n) 4 6 15 5 3 2 4 5 6 7 8 10 9 8 7 3

Quelle est la valeur de n que trouverait l’algorithme hill-climing si on l’initialise à 6

et que les nœuds successeurs (voisins) étaient n-1 et n+1 pour 1 < n < 16 ?

Etat initial : n=6

Voisins : Les nœuds successeurs (voisins) sont n-1 et n + 1 pour 1 < n < 16.

Itérations :
N° itération n Voisins valeurs de F des voisins n’
1 6 5, 7 3, 4 7
2 7 6, 8 2, 5 8
3 8 7, 9 4, 6 9
4 9 8, 10 5, 7 10
5 10 9, 11 6, 8 11
6 11 10, 12 7, 10 12
7 12 11, 13 8, 9 arret

Arrêt :
On arrête l’algorithme car les valeurs de F des voisins 11 et 13 sont 8 et 9 qui sont
inférieur à F(12)=10 (n’améliore plus), et donc l’algorithme rend n=12 (7e itération).
Exemple 2 :
Placer 8 reines sur un damier de taille 8x8 de sorte que 2 reines ne s’attaquent pas
mutuellement (on n’a pas 2 reines sur une même ligne, colonne ou diagonale).

Solution initiale :
Soit n une certaine configuration initiale (un nœud/un état) avec 8 reines (R1,…,
R8) prise aléatoirement (les reines sont sur les lignes (4, 5, 5, 6, 6, 6, 7, 7):

R1
R2 R3
R4 R5 R6
R7 R8

Fonction objective :
On spécifie F(n) qui donne le nombre de paire de reines qui s’attaquent
mutuellement directement ou indirectement dans la configuration n. On veut donc
minimiser cette fonction c.-à-d. minimiser le nombre de paires de reines qui
s’attaquent mutuellement (l’optimum est lorsqu’on obtient un nœud n avec F(n)=0).

Pour cet état initial le nombre de paire de reines qui s’attaquent est F(n)=17 et qui
sont : R1R4 R1R3 R1R5 R1R8 R2R3 R2R4 R2R7 R3R5 R3R7 R3R8
R4R5 R4R6 R4R7 R5R6 R5R8 R6R8 R7R8 (RiRj est la même que RjRi).

Voisinage :
Si on déplaçait une reine Rk dans sa colonne (en haut ou en bas), les chiffres
donnés dans le tableau suivant correspondent aux valeurs de F du nouveau nœud.

18 12 14 13 13 12 14 14
14 16 13 15 12 14 12 16
14 12 18 13 15 12 14 14
15 14 14 R1 13 16 13 16
R2 14 17 15 R3 14 16 16
17 R4 16 18 15 R5 15 R6
18 14 R7 15 15 14 R8 16
14 14 13 17 12 14 12 18

Par exemple pour le chiffre 14 en gras à la case (1,3), il correspond à la valeur de F

lorsque on déplace uniquement la reine R2 vers cette 3e ligne (toutes les autres sont à
leurs anciennes positions) (même chose pour R4 si on la déplace à sa 3e ligne on aura
la valeur 12 pour ce nouveau état,…).. On peut déduire que pour cet état ci-dessus, la
meilleure valeur de F est 12 pour les états voisins (après déplacement d’une reine dans
sa colonne), il y en a plusieurs possibilités (R4↑↑↑, R4↑↑↑↑↑, R3↑↑↑, R3↓↓↓,
R5↑↑↑, R5↑↑↑↑↑, R8↑↑↑↑↑,R8↓). On choisit un déplacement au hasard parmi ces
possibilités.

Cours [Link] ING3 Eng Soft USTHB 2024/2025 H. AZZOUNE

 Après déroulement de l’algorithme on peut arriver à un optimum local avec F(n)=1
correspondant à l’état suivant : (on a une seule paire de reines R1R8 qui s’attaquent).

R8
R3
R4
R1
R5
R6
R7
R2

Exercice : faite un déplacement d’une reine pour avoir l’optimum c-a-d F(n)=0

Quelques Variantes du Hill Climbing :

Hill Climbing simple : On évalue une seule solution voisine à la fois, et si elle est
meilleure, on s'y déplace.
Hill Climbing avec recherche du plus pentu (Steepest-Ascent) : On évalue toutes
les solutions voisines et on choisit celle qui améliore le plus la fonction objectif.
Hill Climbing stochastique : On choisit une solution voisine au hasard, et si elle est
meilleure, on s'y déplace.

Avantages :
Simplicité : Facile à implémenter et à comprendre.
Efficacité : Fonctionne bien pour les problèmes où le paysage de la fonction
objective est relativement lisse et où il existe un seul sommet (optimum global).

Inconvénients :
Optima locaux : Le Hill Climbing peut se bloquer dans un optimum local, c-à-d une
solution qui est meilleure que ses voisines mais qui n'est pas la meilleure solution.
Pas de retour en arrière : Une fois qu'une décision prise, l'algorithme ne revient
pas en arrière, ce qui peut entraîner un manque d'exploration de l'espace des solutions.

Solutions pour contourner ces limitations :

Hill Climbing avec redémarrage aléatoire : On relance l'algorithme plusieurs fois
avec des solutions initiales différentes pour augmenter les chances de trouver
l'optimum global.

Cours [Link] ING3 Eng Soft USTHB 2024/2025 H. AZZOUNE

2)Recuit Simulé (Simulated Annealing)
Le recuit simulé (Simulated Annealing) (IBM-1983) est une technique
d'optimisation méta heuristique inspirée du processus physique de recuit en
métallurgie, où un matériau est chauffé puis refroidi lentement pour minimiser les
défauts et atteindre un état d'énergie minimale. On simule le processus de
refroidissement thermique du métal.
C’est une amélioration de l’algorithme Hill-climbing dans le but est de minimiser
le risque d’être piégé dans un maxima/minima locaux. Au lieu de regarder le
meilleur voisin du nœud courant (comme dans l’algorithme Hill-climbing), avec une
certaine probabilité on va regarder un moins bon voisin immédiat (on souhaite
ainsi s’échapper éventuellement aux optima locaux). Ceci nous permet de pouvoir
visiter des nœuds qui étaient impossible à visiter avec le Hill-climbing.

Au début de la recherche, on prend la probabilité de prendre un moins bon voisin

élevée et au fur et à mesure qu’on avance dans l’algorithme, cette probabilité diminue
graduellement (d’une manière décroissante). Et donc on va converger vers une
solution qui ressemble au hill climbing (probabilités presque 0 de choisir un moins
bon voisinage) et donc éviter le blocage dans un optimum local.

Le nombre d’itérations et la diminution des probabilités graduellement sont

contrôlés à l’aide d’un schéma qui va définir une série de « températures » en ordre
décroissant pour converger vers 0.

Par exemple, le schéma de 100 itérations [2-0, 2-1, 2-2, …., 2-99] est une suite
d’itération qui commence avec 1 (2-0) et converge vers 0 (2-99) (malheureusement il
n’y a pas de standard pour dessiner un schéma, ça dépend du problème.

On peut générer le schéma par une fonction : Tn+1 :=α.Tn avec α<1 (en général
α=0.9 à 0.99). α doit être choisi avec précaution : pour un α trop grand la température
baisse trop rapidement et l’algorithme peut être bloquée dans un optimum local. Si au
contraire α est trop petit le temps de calcul sera très grand car la température baisse
lentement).

Application en Optimisation :
Initial : Le processus commence par une solution initiale n0, qui peut être aléatoire
ou basée sur une heuristique + un schéma contenant une température initiale T0
élevée.

Itération : On va parcourir toutes les températures (données dans le schéma) de la

plus grande température jusqu’à la plus petite ou jusqu’à un optimum global.

Exploration du Voisinage : À chaque étape, une solution voisine n’ du nœud courant

n est générée d’une manière aléatoire.

Fonction d'Énergie (ou Coût) : Calculer la différence ∆E des fonctions objectives de

n et n’ (si on maximise ∆E = F(n’) - F(n), si on minimise ∆E = F(n) - F(n’)).

Acceptation des Solutions (on prend le cas de maximiser):

-Si la solution n’ est meilleure (∆E>0) alors elle est acceptée, on remplace n par n’.

Cours [Link] ING3 Eng Soft USTHB 2024/2025 H. AZZOUNE

 -Si la nouvelle solution est pire (c-a-d ∆E≤0), elle peut encore être acceptée avec
une probabilité qui dépend de la température et de l'écart de coût. Cette probabilité
permet d'échapper aux minima/maxima locaux en autorisant temporairement des
solutions sous-optimales.

Voici un algorithme du recuit simulé qu’on appelle avec un nœud initial et un

schéma de température (cet algorithme maximise ∆E > 0).

Algorithme recuit-simulé(nœud_initial, schéma)

Déclare : 2 nœuds n, n’ /* n nœud courant et n’ nœud voisin */
Déclare : t, T, ∆E, /* autres variables utilisées dans l’algorithme */
n := nœud_initial /* initialiser le nœud courant au nœud initial */
Pour t=1,…, taille(schéma) /* nombre itération=nombre température de schéma */
T := schéma[t] /* consulter les ≠ températures d’une manière décroissante */
n’ := successeur de n choisi au hasard
∆E := F(n’) – F(n) /* pour n’, calculer la différence des fonctions objectives*/
Si ∆E > 0 /* maximiser F, si on veut minimiser F on prenait ∆E=F(n)-F(n’) */
Alors assigner n = n’ /*F(n’) est meilleur que F(n), donc on prend n := n’ */
Sinon assigner n = n’ avec une probabilité de e∆E/T /* ≠ avec hill-climbing*/
Retourner n

Si ∆E≤0, on remplace quand même n par n’ mais avec la probabilité exponentielle

∆E/T
e , qui signifie la probabilité de faire une transition de n vers n’. Plus T est petite,
plus e∆E/T est petite et donc probabilité petite. Si T est très élevée (température =10000
par exemple), avec ∆E≤0 alors ∆E/T serait proche de 0 et donc e∆E/T serait proche de 1
et donc une probabilité proche de 1. Ce qui veut dire qu’une température élevée avec
une différence d’énergies basse, on va avoir une probabilité de transition proche de 1).
On remarque qu’avec des températures basses, on se rapproche de l’algorithme hill
climbing c-a-d on aura des voisins qui améliorent.

Exemple1 :
Minimiser la fonction f(x)=x2+10 sin(x) sur l’intervalle [-1, 10]

-choisir un nœud initial x0 aléatoirement dans l’intervalle [-10, 10]

-Fixer une température initiale T0 et un facteur de décroissance de la température α
pour construire le schéma (par exemple Tn+1 :=α.Tn avec α<1).
-itération : générer un point x’ en ajoutant une petite perturbation à x,
Calculer ∆E = f(x’) - f(x)
-si ∆E < 0
alors accepter le nouveau point x’ (remplacer x par x’, meilleure solution trouvée)
sinon accepter x’ avec une probabilité P=e∆E/T
Passez à l’élément suivant dans le schéma (c-a-d réduire la température)

Exemple 2:
Le problème du voyageur de commerce :
Le recuit simulé peut être appliqué au problème du voyageur de commerce. Un
vendeur doit visiter un certain nombre de villes en minimisant la distance totale
parcourue. Le vendeur doit visiter chaque ville une seule fois et revenir à la ville de
départ. Le but est alors de trouver le circuit de coût minimal dans un graphe.

Cours [Link] ING3 Eng Soft USTHB 2024/2025 H. AZZOUNE

L’énergie représentera la distance totale à parcourir, et un état du système
représentera le chemin entre les villes. L’algorithme va donc tenter de minimiser la
longueur totale du chemin, en modifiant l’ordre des villes à parcourir.

Étapes de l'algorithme :
Initialisation :
- Générer une solution initiale, par exemple, un ordre aléatoire des villes.
- Fixer une température initiale T0, une température finale Tf, et un taux de
refroidissement α.

Boucle principale :
Tant que T > Tf
Générer une nouvelle solution S′ en effectuant une petite modification
sur la solution courante S (par exemple, en permutant deux villes
dans l'ordre de visite).
Calculer la différence de coût entre la nouvelle solution et la solution courante
ΔE = E(S′) − E(S), où E(S) est la longueur totale du trajet pour la
solution S.
Si la nouvelle solution est meilleure (ΔE<0)
Alors accepter S′ comme nouvelle solution courante.
Sinon, accepter S′ avec une probabilité P=e−ΔE/T où T est la
température actuelle.
Réduire la température selon le taux de refroidissement α, T = α × T .

Fin de l'algorithme :
Lorsque la température atteint Tf, arrêter l'algorithme et renvoyer la meilleure
solution trouvée.

Application : Soit le graphe suivant représentant un ensemble de villes :

La solution la plus simple est de parcourir les villes dans l’ordre.

Le résultat donné par l’algorithme glouton (se délacer d’un sommet vers son plus
proche voisin) est donné par :

Le résultat obtenu en échangeant par exemple les sommets 2 et 3 est :

 Dans le résultat obtenu en échangeant les sommets 2 et 3, la distance totale a
augmenté. Pour une heuristique classique, cette solution est rejetée car la distance doit
être minimisée alors que là elle est passée de 21 à 22. Mais le recuit simulé pourra
l’accepter si la température est encore élevée, et cette solution qui est « mauvaise »
par rapport à la première va lui permettre de trouver une solution meilleure (en
permutant 5 et 2):

En résumé : Le recuit simulé, en acceptant une mauvaise solution, à réussi a échapper

au minima local et à obtenir une solution meilleure.
Exemple de données : T0=1000, Tf=0.001, α=0.99, Ville=[….]

Exemple3 :
Problèmes des N reines à placer sur un damier :
Solution initiale La solution initiale est générée en plaçant une reine dans chaque
colonne sur une ligne aléatoire. Cela garantit qu'aucune reine n'est dans la même
colonne.

Coût (ou énergie) : Le coût est calculé en comptant le nombre de conflits entre les
reines. Un conflit survient si deux reines sont sur la même diagonale.

Perturbation : Une nouvelle solution est générée en échangeant les positions de deux
reines. Cela permet d'explorer l'espace des solutions en faisant de petites
modifications.

Acceptation des nouvelles solutions : Si la nouvelle solution est meilleure (moins de

conflits), elle est acceptée. Si elle est pire, elle est acceptée avec une certaine
probabilité, qui diminue à mesure que la température baisse.

Refroidissement : La température diminue progressivement, rendant l'algorithme de

plus en plus conservateur au fil du temps, en acceptant moins souvent des solutions
sous-optimales.

Résultat :L'algorithme retourne une solution possible pour le problème des n reines
ainsi que le nombre de conflits dans cette solution. Avec un bon choix des paramètres
(température initiale, température finale, et taux de refroidissement), l'algorithme peut
souvent trouver une solution sans conflits (une disposition valide des reines).
Exemple de données : N=8, T0=1000, Tf=0.001, α=0.99

Exemple4 :
Résoudre la fonction de Rastrigin (fonction qui présente beaucoup de minima locaux).
Elle est définie comme suit : pour un vecteur x=(x1,…,xn), alors
f(x) = 10n + somme([xi2 – 10 cos(2πxi]) pour i=1..n
Elle a un minimum global à x=(0,0,…,0) avec f(x)=0.

Solution initiale : Une solution initiale est générée en attribuant des valeurs aléatoires
à chaque composante xi du vecteur x, dans les limites spécifiées.

Fonction objectif : La fonction de Rastrigin est utilisée comme fonction de coût.

L'objectif est de minimiser cette fonction.

Perturbation : Une nouvelle solution est générée en ajoutant une petite perturbation à
chaque composante de la solution courante. La perturbation est contrôlée par un
facteur qui détermine l'amplitude de la modification.

Acceptation des nouvelles solutions : une nouvelle solution est acceptée si elle est
meilleure, ou avec une certaine probabilité si elle est pire, pour permettre à
l'algorithme de sortir des minima locaux.

Refroidissement : La température diminue progressivement, ce qui réduit la

probabilité d'accepter des solutions sous-optimales au fil du temps.

Résultat : L'algorithme retourne une solution approximative pour minimiser la

fonction de Rastrigin, ainsi que la valeur de cette fonction pour la solution trouvée.
Avec un bon choix des paramètres (température initiale, température finale, et taux de
refroidissement), l'algorithme peut souvent trouver des solutions proches du minimum
global, même dans des espaces de recherche avec de nombreux minima locaux.
Exemple de données : n=2, intervalle=[-5.12,5.12], T0=1000,Tf=0.001, α=0.99

Avantages et Inconvénients
Échappement des Minima Locaux : En acceptant temporairement des solutions
sous-optimales, le recuit simulé peut échapper aux pièges des minima locaux.
Simplicité : L'algorithme est relativement simple à implémenter et ne nécessite pas de
dérivées ou d'informations supplémentaires sur le problème.
Flexibilité : Applicable à une grande variété de problèmes d'optimisation.

Inconvénients :
Sensibilité aux Paramètres : Les performances dépendent fortement du choix de la
température initiale, du taux de refroidissement et de la fonction de voisinage.
Temps de Calcul : Le processus de refroidissement lent peut être long, surtout si un
grand nombre d'itérations est nécessaire.

Applications du Recuit Simulé

Le recuit simulé est utilisé dans de nombreux domaines pour résoudre des
problèmes d'optimisation complexes, notamment la planification d'horaires ou de
ressources., Résolution du problème du voyageur de commerce, optimisation des
itinéraires de livraison, Optimisation de la disposition des composants sur un circuit
électronique, Affectation de tâches, découpe de matériaux, etc…

Conclusion
Le recuit simulé est une méta heuristique puissante pour l'optimisation de
problèmes complexes où les méthodes exactes sont impraticables. Son approche
stochastique lui permet d'explorer efficacement l'espace des solutions, en évitant les

Cours [Link] ING3 Eng Soft USTHB 2024/2025 H. AZZOUNE

minima locaux, et d'approcher une solution optimale de manière itérative et contrôlée.
Bien qu'il soit sensible aux paramètres et potentiellement coûteux en temps de calcul,
il reste une méthode très utile pour de nombreux types de problèmes.

Exemple d’application pratique : déplacement du bras de Mars Explorer.

Cours [Link] ING3 Eng Soft USTHB 2024/2025 H. AZZOUNE

3)Algorithme Génétique (Genetic Algorithm)
3.1)Introduction
On s’est inspirée de l’évolution naturelle des espèces (Travaux de la théorie de
l’évolution de Darwin 1858, théorie de la sélection naturelle de Weismann et les
concepts de génétiques de Mendel).
On a essayé de simuler l’évolution de l’intelligence humaine (des millions
d’années) sur une machine (intelligence artificielle) pour l’avoir en quelques instants.
C’est un algorithme qui ressemble beaucoup à la recherche local.
Il commence avec un ensemble, appelé population, de k nœuds choisis d’une
manière aléatoire et qu’on va maintenir au fur et à mesure qu’on avance dans la
recherche.
Les nœuds successeur sont générés en combinant 2 parents.

Pour développer un algorithme génétique, on a 3 aspects à définir :

-la sélection (comment sélectionner les 2 parents pour générer un nouveau nœud),
-le croisement (comment on fait le croisement entre ces 2 parents)
-la mutation (comment on applique une mutation sur un enfant).

3.2)Principe :
- On représente l’espace des solutions d’un problème à résoudre par une population
(ensemble de nœuds/ensemble de chromosomes). Chaque solution possible au
problème est représenté sous forme d’un chromosome. Un chromosome est une
chaine de caractères (appelés gènes) de taille fixe (par exemple 101101001 si alphabet
binaire). Il contient les informations sur les gènes du nœud.
- Une population génère des enfants par un ensemble de procédures simples qui
manipule les chromosomes : le croisement de parents,
- suivi d’une mutation appliquée à l’enfant généré.
-Tout ces processus (sélection des parents, application de la mutation à l’enfant
généré ) se fait d’une manière aléatoire.
-Les enfants conservés, vont se reproduire (pour devenir à leur tour des parents) en
fonction de leur adaptation (filteness) déterminée par la fonction donnée F(n). La
fonction d’adaptation va correspondre à la fonction F(n) qu’on essaye d’optimiser.

Fitness (évaluation)
La fonction objective qu’on essaye d’optimiser est appelé la fonction fitness
(fonction d’adaptation). Elle mesure la qualité de la solution qu’il représente. Les
chromosomes (nœuds) ayant une valeur de fitness élevée sont de bonnes solutions.

Selection
Il y a plusieurs méthode sur comment choisir les chromosomes parents :
-Sélection par roulette (Roulette Wheel Selection)
Chaque individu reçoit une probabilité de sélection proportionnelle à sa fitness
(valeur d'adaptation). Plus la fitness est élevée, plus la portion est grande, et donc plus
les chances de sélection sont élevées.

-Sélection par tournoi (Tournament Selection)

Un sous-ensemble d'individus est sélectionné au hasard, puis le plus apte parmi eux
est choisi pour se reproduire. Cette méthode peut être ajustée en modifiant la taille du
tournoi (le nombre d'individus en compétition).

Cours [Link] ING3 Eng Soft USTHB 2024/2025 H. AZZOUNE

-Sélection par classement (Rank Selection)
Les individus sont classés en fonction de leur fitness, et les probabilités de sélection
sont attribuées en fonction de ce classement. Cela permet d'éviter que les individus
avec une très haute fitness dominent trop la sélection.

-Sélection par élitisme

Dans cette méthode, les meilleurs individus d'une génération sont directement
transférés à la génération suivante sans subir de mutation ou de recombinaison. Cela
garantit que les meilleures solutions ne sont pas perdues.

-Sélection uniforme (Uniform Selection)

Tous les individus ont la même probabilité d'être sélectionnés, indépendamment de
leur fitness. Cette méthode est rarement utilisée seule, mais elle peut être combinée
avec d'autres méthodes pour introduire de la diversité.

-Sélection stochastique universelle (Stochastic Universal Sampling)

Variante de la sélection par roulette, où plusieurs individus sont sélectionnés en une
seule fois.

Croisement (crossover):
2 chromosomes sélectionnés (parents) sont croisés pour produire un ou plusieurs
descendants. Le croisement mélange les informations génétiques des parents pour
créer de nouvelles solutions. Les méthodes courantes de croisement incluent :

-Croisement à un point : Un point de croisement est choisi aléatoirement, et les

segments des deux parents sont échangés après ce point (exemple ci-dessous).

-Croisement à plusieurs points : Plusieurs points de croisement sont choisis, et les

segments entre ces points sont échangés.

-Croisement Uniforme (Uniform Crossover) : Les gènes des parents sont échangés
de manière aléatoire, gène par gène, pour créer les enfants.

Exemple:
-Soient 2 nœuds parents n et n’ pour le problème des 8 reines.
-On représente chaque nœuds par un chromosome de 8 chiffres des lignes des 8
reines dans cet état. pour l’exemple ci-dessous, n et n’ sont : 67247588 et 75251448
-Pour le croisement, on choisit le Croisement à un point (voir ci-dessus). On
choisit aléatoirement une séparation dans n et n’ en 2 parties (3, 5 colonnes).
-Une fusion, par exemple, se fait en combinant la partie gauche de n avec la partie
droite de n’. Le nouveau nœud chromosome 67251488 est ajouté à la population.
n n’ enfant (n1-3 n’4-8
R R
R R R

R + R R = R R
R R R R
R R
R R R R R R
R R
67247588 75251448 67251488

Cours [Link] ING3 Eng Soft USTHB 2024/2025 H. AZZOUNE

Mutation
Une petite partie des chromosomes est modifiée aléatoirement pour introduire de la
diversité et éviter la convergence prématurée. La mutation peut consister en un
changement de valeur dans un chromosome :

-Mutation Binaire : Un petit pourcentage de gènes dans les chromosomes des enfants
est modifié de manière aléatoire. Par exemple, un bit 0 peut devenir 1, et vice versa.

-Mutation de Valeur : Dans le cas d'un codage non binaire, les valeurs des gènes
peuvent être légèrement modifiées.
Exemple:
32748552 32748152 (on a changé le premier 5 par 1)

Nouvelle Génération
Les descendants produits par croisement et mutation remplacent tout ou partie de la
population actuelle pour créer une nouvelle génération. Le processus de sélection,
croisement et mutation est répété pour plusieurs générations. Quelques méthodes de
remplacement :

-Remplacement Générationnel : Les nouvelles générations remplacent

complètement les anciennes.

-Stratégie de Mélange (Steady-State) : Les enfants sont insérés dans la population

en remplacement des individus les moins aptes, tout en gardant une partie de la
population actuelle.

Arrêt
L'algorithme se termine lorsqu'un critère de convergence est atteint, par exemple,
après un certain nombre de générations, ou si une solution optimale est trouvée.

Algorithme Génétique
Entrée: Taille_population, Taux_ mutation, Taux_croisement, Nombre_generation,
Fonction_évaluation
-Générer une population initiale de solutions (chromosomes) de manière aléatoire.
-Évaluer la fitness de chaque chromosome dans la population à l'aide de la fonction
d'évaluation
Pour chaque génération jusqu’à Nombre_génération
faire
- Sélectionner une paire de parents dans la population en fonction de leur fitness
(par exemple, sélection par roulette, tournoi, etc….)
- Avec une probabilité égale au taux de croisement, croiser les parents sélectionnés
pour produire deux nouveaux enfants (chromosomes)
- Pour chaque enfant, appliquer la mutation avec une probabilité égale au taux de
mutation (modifier aléatoirement un ou plusieurs bits du chromosome)
- Ajouter les enfants mutants à la nouvelle population
- Remplacer tout ou partie de l'ancienne population par la nouvelle population
- Évaluer la fitness de chaque chromosome dans la nouvelle population
- Optionnel: Conserver le meilleur chromosome (ou les meilleurs) de l'ancienne
population si le remplacement est complet
fin pour
Sortie: Meilleur chromosome trouvé et sa valeur de fitness

Cours [Link] ING3 Eng Soft USTHB 2024/2025 H. AZZOUNE

Paramètres de l’Algorithme :
quelques paramètres sont très importants pour l’algorithme :
Taille de la Population : Une grande population permet une meilleure exploration de
l'espace des solutions, mais augmente le temps de calcul.

Probabilité de Croisement : Contrôle la fréquence à laquelle les croisements se

produisent. Généralement élevée (par exemple, 0,7 à 0,9).

Probabilité de Mutation : Garde la diversité dans la population. Généralement faible

(par exemple, 0,01 à 0,1).

Nombre de Générations : combien de fois le processus d'évolution est répété

Exemple (déroulement à la fin de l’exemple):

-Soit une population à 4 chromosomes : 24748552 32752411 24415124 32543213.
(1 chromosome est une chaine de 8 chiffres contenant les lignes des 8 reines):
24748552 32752411 24415124 32543213
R R R R R
R R R R R R R R
R R R R
R R R R R R R
R R R R R

R R
R

-On définit notre fonction d’adaptation (fitness) comme étant, par exemple, le
nombre de paires de reines qui ne s’attaquent pas (min=0, max=8*7 / 2=28(nombre de
paires maximum, (RiRj est la même paire que RjRi)). Cette fonction est l’inverse de
notre fonction objective (nombre de paire de reines qui s’attaquent) du début du
chapitre. Puisqu’ici on s’intéresse à maximiser, donc on va essayer d’optimiser
(minimiser) le nombre de reines qui ne s’attaquent pas.

-Pour ce qui de la probabilité de la sélection du 1er chromosome, on choisit la

sélection par roulette (Chaque individu reçoit une probabilité de sélection
proportionnelle à sa fitness, voir plus haut). On va prendre une probabilité qui est
proportionnelle à la fonction d’adaptation. Les valeurs de la fonction d’adaptation
(les nombres de paires de reines qui ne s’attaquent pas) pour ces 4 nœuds
chromosomes ci-dessus sont respectivement 24, 23, 20, 11 (à vérifier).

On va normaliser ces valeurs pour avoir des probabilités (les 100%), donc comme
probabilités respectives pour ces 4 nœuds, on obtient 24/(24+23+20+11)=31%,
23/(24+23+20+11)=29%, 20/(24+23+20+11)=26%, 11/(24+23+20+11)=14%. Ces
valeurs vont nous donner la meilleure probabilité pour sélectionner le 1er
chromosome. On a pris par exemple le 2eme chromosome qui a une forte probabilité
(comme on aurait pu choisir le 1er).

-Pour faire le croisement, on choisit de partager les chromosomes en 2 blocs de 3,

5 (et 5, 3) (voir exemple de croisement plus haut).

-Dans la mutation on pourrait changer la valeur avec une certaine probabilité,

choisir un des éléments de la chaine et changer sa valeur aléatoirement (par exemple
ce qui est gras couleur rouge ).

Cours [Link] ING3 Eng Soft USTHB 2024/2025 H. AZZOUNE

24748552 24 31% 32752411 32748552 32748152 (5 en 1)
32752411 23 29% 24748552 24752411 24752411 rien
24415124 20 26% 32752411 32752124 32252124 (7 en 2)
32513213 11 14% 24415124 24415411 24415417 (1 en 7)
Initial Fitness sélection croisement(3,5 et5,3) Mutation (chiffre en rouge)

Avantages :
Exploration Globale : Les AG explorent un large espace de solutions simultanément
grâce à la population de solutions. Utilise la diversité génétique pour explorer
largement l'espace des solutions et éviter le piège des minima locaux.
Robustesse : Ils sont applicables à une grande variété de problèmes, y compris ceux
avec des fonctions d'objectif complexes.
Flexibilité : Les AG peuvent être hybridés avec d'autres algorithmes ou heuristiques.

Inconvénients :
Temps de Calcul : Les AG peuvent être coûteux en termes de temps de calcul,
surtout pour les grandes populations ou les problèmes complexes.
Convergence Lente : Ils peuvent converger lentement vers une solution optimale, et
parfois se bloquer dans des solutions sous-optimales.
Sensibilité aux Paramètres : La performance des AG dépend fortement du choix
des paramètres (taille de la population, taux de croisement, etc.).

Applications des Algorithmes Génétiques

Les algorithmes génétiques sont utilisés dans de nombreux domaines pour résoudre
divers problèmes d'optimisation:
Optimisation Combinatoire : Voyageur de commerce, problèmes d'affectation.
Planification et Ordonnancement : Planification de production, allocation de
ressources.
Conception de Circuits et Réseaux : Optimisation des réseaux, disposition des
composants électroniques.
Apprentissage Automatique : Sélection de caractéristiques, optimisation des hyper
paramètres.

Conclusion
En simulant le processus d'évolution, les AG sont capables de trouver des solutions
de haute qualité en explorant efficacement un large espace de solutions, bien qu'ils
nécessitent un réglage soigneux des paramètres pour obtenir les meilleurs résultats.

Cours [Link] ING3 Eng Soft USTHB 2024/2025 H. AZZOUNE

 Apprentissage Automatique et réseaux de Neurones
-Nous allons introduire les concepts de base du domaine de l’apprentissage
automatique (Machine Learning ML).
-Nous allons voir l’algorithme des k plus proche voisins KNN pour faire la
classification en apprentissage automatique.
-Nous terminons par une introduction aux réseaux de neurones artificiels et
l’algorithme k-means.

1)Partie 1 : Apprentissage automatique

Quelle est la motivation ?
Comment développer une IA capable par exemple de reconnaitre des caractères
manuscrits (comme l’exemple les images manuscrites suivantes) ?:

On veut développer un système qui prend en entrée une image d’un de ces chiffres
par exemple et nous donne à la sortie le chiffre correspondant (l’écriture varie d’une
personne à une autre et donc un programme classique ne marche pas).

C’est quoi le ML ou c’est quoi l’apprentissage?

L'apprentissage automatique, ou "machine learning (ML)", est une sous-discipline
de l’IA qui permet à un système informatique d'apprendre et de s'améliorer
automatiquement à partir de données sans être explicitement programmé pour
chaque tâche.
On dit qu’un agent apprend (en IA) s’il est capable d’améliorer sa performance
sur des taches futures avec l’expérience acquise c.-à-d. qu’au fur et à mesure qu’il
observe de nouvelles données.
Il repose sur des algorithmes capables de détecter des motifs dans des ensembles de
données et d’en tirer des conclusions pour prédire ou/et prendre des décisions.

Pourquoi écrire des programmes qui apprennent ?

Lors de l’écriture des programmes :
- il est trop difficile d’anticiper toutes les entrées à traiter,
- il est possible aussi que la relation entre l’entrée et la sortie évolue dans le
temps (exemple : classification des spam dont l’écriture évolue dans le temps),
- des fois on n’a aucune idée comment programmer la fonction désirée
(exemple : la reconnaissance de visage en traitement d’image, etc….) et donc
l’écriture de programmes classique ne convient pas.

A)Types d'apprentissage
Il existe plusieurs types d’apprentissage. Ils se distinguent par la nature de la
supervision offerte par les données de la sortie (ou la cible).
1.A.1)Apprentissage supervisé :
Supervisé signifie que les classes de sorties possibles sont connues et données par
un superviseur (expert humain). Spécifiquement les algorithmes d’apprentissage
supervisé procèdent comme suit (pour la reconnaissance de caractères par exemple):
 -On fournit à l’algorithme des données d’entrainement, par exemple une séquence
de plusieurs images et un expert humain (superviseur) nous donne la valeur exacte de
chaque image (exemple pour les images suivantes en bleu, le superviseur nous donne
les chiffres, 9, 6, 6, 5, 4, 0)

-Après conception de l’algorithme d’apprentissage (le modèle), cet algorithme

serait normalement capable de nous donner les chiffres correspondants à de nouvelles
images d’un ensemble de test, par exemple:

-Dans cet exemple, on suppose que les sorties possibles sont parmi les chiffres :0,
1,…,9., donc le modèle (s’il est bien fait) devrait nous répondre: 6,3,5,5,6,0.

-Dans l’apprentissage supervisé, on va représenter les données d’entrainement par un

ensemble D de n éléments d’entrainement, D={(x1, t1), (x2, t2), …. (xn, tn)} où xi est la
ieme image par exemple représentée sous une certaine forme informatique (vecteur,
matrice, etc…) et ti la classe correspondante. Pour l’exemple précédent : x1 est
l’image du 9, t1 le chiffre (la classe) 9,….etc. xi est appelé l’entrée et ti la cible.

Définition : On peut définir l’apprentissage supervisé par: Etant donné une

collection de données qui sont des paires (entrées, sorties) appelées exemples
d’apprentissage, comment apprendre une fonction qui peut prédire correctement une
sortie étant donnée une nouvelle entrée qui n’est pas forcément dans les exemples.

Ceci nous ramène à écrire un algorithme (un modèle) qui à partir des ces exemples
d’apprentissage, il nous définit une telle fonction c.-à-d. apprendre la relation entre les
entrés et les sorties pour pouvoir prédire les sorties pour de nouvelles données.

Le modèle est formé sur des données étiquetées, c'est-à-dire que chaque entrée est
associée à une sortie correcte (chaque entrée x lui est associé une sortie y). Chaque
exemple de données d’entrainement comprend des entrées (caractéristiques) et les
sorties correspondantes (étiquette). Le modèle apprend à prédire la sortie à partir des
entrées.

Autre Exemple : Par exemple un modèle de reconnaissance d'image pourrait être

formé sur un ensemble d'images de chats et de chiens avec des étiquettes indiquant
quelle image correspond à quel animal (chat, chien).

En résumé :
-Son principe est simple : Les données d'entraînement sont composées de paires
(entrée, sortie), où l'entrée est un vecteur de caractéristiques et la sortie est l'étiquette
ou la valeur que le modèle doit prédire (sortie connue et est donnée par un expert).
-Le modèle apprend en minimisant une fonction de coût (ou perte) qui mesure
l'écart entre les prédictions du modèle et les sorties réelles. Le but est d'entraîner un
modèle qui généralise bien, c'est-à-dire qui fonctionne non seulement sur les données
d'entraînement mais aussi sur de nouvelles données non vues.
 En général cet apprentissage supervisé nous permet de faire :
-Soit une classification (clustering) c.-à-d. que la cible est un indice de classe t qui
appartient à {1, …, k} où k est le nombre de classes.
Pour l’exemple des chiffres k=10 (les 10 chiffres), l’entrée sera représentée par
exemple par un vecteur (ou matrice) de tous les pixels de l’image, et la sortie est un
numéro de classe.
-Soit une régression où la cible (sortie) est un réel t appartenant à R (par exemple la
prédiction de la valeur d’une action en bourse à partir des données sur les activités
économiques précédentes).
Dans ce cas l’entrée est par exemple un vecteur contenant l’information sur
l’activité économique des dernières journées et la cible est un réel.

Exemples d’algorithmes d’apprentissage supervisé

On a plusieurs algorithme pour l’apprentissage supervisé (KNN à détailler plus loin):
- k-Plus Proches Voisins (KNN) : Un algorithme de classification qui classe
une nouvelle donnée en fonction des classes des k voisins les plus proches.
- Régression Linéaire : Utilisé pour des tâches de régression. L'objectif est de
prédire une valeur continue en fonction d'une ou plusieurs variables d'entrée.
- Régression Logistique : Utilisée pour la classification binaire. L'objectif est
de prédire une probabilité pour 2 classes possibles. Par exemple prédire si un
email est un spam ou non
- Machines à Vecteurs de Support (SVM) : Utilisées pour la classification et
la régression. SVM cherche à trouver l'hyperplan qui sépare les données en
classes distinctes avec une marge maximale.
- Arbres de Décision : Un modèle basé sur une structure d'arbre, où chaque
nœud représente une décision basée sur la valeur d'une variable.
- Forêts Aléatoires (Random Forest) : Une combinaison de plusieurs arbres de
décision pour améliorer la précision et réduire le sur-apprentissage.
- Réseaux de Neurones Artificiels : Modèles inspirés de la structure du
cerveau humain, largement utilisés pour des tâches complexes comme la
reconnaissance d'image et la traduction automatique (sera détaillé plus loin).

Processus d’apprentissage
Le Processus d'Apprentissage Supervisé est le suivant :
- Collecte des Données : Rassembler un ensemble de données étiquetées (entrée,
sortie) représentatives du problème à résoudre (les sorties possibles sont connues).
- Préparation des Données : Nettoyer et prétraiter les données, par exemple en
normalisant les caractéristiques, en gérant les valeurs manquantes, ou en
transformant les données catégorielles en variables numériques.
- Division des Données : Séparer les données en un ensemble d'entraînement (pour
entraîner le modèle généralement 80% de tout l’ensemble) et un ensemble de test
(pour évaluer la performance du modèle 20% restant).
- Choix de l'Algorithme : Sélectionner un algorithme approprié en fonction du
type de problème (classification / régression) et des caractéristiques des données
(par exemple KNN ou régression linéaire ci-dessus).
- Entraînement du Modèle : Utiliser les données d'entraînement pour ajuster les
paramètres du modèle afin de minimiser la fonction de coût.
- Évaluation : Tester le modèle sur des données de l’ensemble de test pour évaluer
sa performance en utilisant des métriques comme la précision, le rappel, la F-

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

 mesure pour la classification, ou l'erreur quadratique moyenne pour la régression
(voir ci-dessous).
- Ajustement du Modèle : Optimiser le modèle si nécessaire, par exemple en
ajustant les hyper paramètres ou en utilisant des techniques de régularisation
pour éviter le sur apprentissage (overfitting).

Métriques utilisées:
Plusieurs Métriques de Performance sont définies pour évaluer cet apprentissage :
- Erreur Quadratique Moyenne (MSE) : c’est une mesure d'évaluation courante
dans les modèles de régression, elle mesure la moyenne des erreurs au carré entre
les valeurs prédites et les valeurs réelles :
n
EQM = (1 / n) * Σ [(yi – y’i)2]
i=1
Où n est le nombre d’observations, yi est la valeur réelle de la ieme observation et
y’i est sa valeur prédite. L'EQM représente la moyenne des carrés des écarts entre
entre les valeurs prédites et les valeurs réelles. Plus l'EQM est faible, plus le
modèle est performant pour la régression (des fois on prend (y’i - yi)2).

Exemple : Soit un modèle pour prédire les prix de maisons. Les prédictions pour
5 maisons sont : Valeurs réelles : [200 000, 250 000, 300 000, 400 000, 500 000]
Valeurs prédites : [210 000, 240 000, 290 000, 410 000, 490 000]
EQM = 1/5 ((200 000−210 000)2 + (250 000−240 000)2 + (300 000−290 000)2 +
(400 000−410 000)2 + (500 000−490 000)2) =
1/5 ((-10 000)2 + (10 000)2 + (10 000)2 + (-10 000)2 + (10 000)2) =100002
L'EQM dans cet exemple est de 100 000 000 unités carrés. Cela représente la
moyenne des carrés des erreurs entre les valeurs réelles et les prédictions du modèle,
exprimée en unités carrées (donc l’écart moyen est de 10 000).
Plus l'EQM est faible, plus le modèle est performant dans la prédiction.

- Précision (Accuracy) : Le pourcentage de prédictions correctes sur l’ensemble de

prédictions réalisées. Souvent utilisée pour la classification,
Précision = (TP + TN) / (TP +TN + FP + FN)
où TP est le true positif (nombre de cas classés positif et qui sont réellement
positifs exemple : nombre de malade classé malade), TN true négatif (exemple les
non-malades correctement prédits non-malades), FP est le faux positif (les non-
malades incorrectement prédits comme malade) et FN les faux négatifs (les
malades incorrectement prédits comme non-malades).

Exemple : Soit l'exemple d’un modèle qui classifie des patients comme malades
(classe 1) ou pas malades (classe 0), avec les résultats des prédictions pour 10
patients.
Prédictions du modèle : [1,0,0,1,0,0,1,1,0,1]
Valeurs réelles : [1,0,1,1,0,0,1,0,0,1]
Matrice de confusion :
Malade (1) Pas malade (0)
Prédit malade (1) Vrai positif (TP) = 4 Faux positif (FP) = 1
Prédit pas malade (0) Faux négatif (FN) = 1 Vrai négatif (TN) = 4
Calcul de l'accuracy : Accuracy=(4+4) / (4 + 4 + 1 + 1) = 8 / 10 = 0.8

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

 L'accuracy est de 0,8 (80 %=. Cela signifie que le modèle a correctement classé 80
% des patients, en incluant à la fois ceux qui sont malades et ceux qui ne le sont pas.
Plus on se rapproche du 100% plus le modèle est bon.

- Rappel (Recall) : C’est une mesure de performance utilisée dans la

classification. Il évalue la capacité du modèle à identifier correctement toutes les
instances pertinentes d'une classe donnée. La métrique :
Recall = TP / (TP + FN).
Où FN sont les faux négatifs (les éléments qui appartiennent à cette classe mais
qui ont été incorrectement classés).

Exemple : Soit un exemple d'un modèle qui classe des patients en fonction d'une
maladie (malade ou non malade). Si le modèle a les résultats suivants : TP=80 (80
patients sont correctement classés comme malades) et FN=20 (20 patients
malades sont incorrectement classés comme non malades) :
Recall = 80 / (80 + 20) = 80 / 100 = 0.8 (soit 80%).
Cela signifie que le modèle identifie correctement 80 % des patients malades,
mais en manque 20 %. Plus le taux se rapproche des 100% plus le modèle est bon.

- F-mesure (F1-Score) : Une combinaison de la précision et du rappel, utilisée

pour évaluer le compromis entre les deux.
F1 = 2 * ((Précision * Recall) / (Precision + Recall))

- Erreur Absolue Moyenne (MAE) : La moyenne des différences absolues entre

les valeurs prédites et les valeurs réelles utilisées lors de la régression.
n
EAM = (1 / n) * Σ [ |y’i – yi |]
i=1
Où n est le nombre d’observations, yi est la valeur réelle de l’observation i et y’i
est sa valeur prédite. Une EAM plus faible indique une meilleure précision du
modèle. On prend la valeur absolue des différences et pas au carrée comme dans
EQM (à remarquer que |y’ - y|=|y - y’|).

Exemple : Prenons un exemple de prédiction du poids de fruits avec un modèle

KNN. Voici les poids réels et prédites :
Poids réels (y) : [150, 200, 250, 300]
Poids prédits (y’) : [140, 210, 240, 310]
EAM= ¼ (∣140−150∣ + ∣210−200∣ + ∣240−250∣ +∣310−300∣) = 40/4=10
Dans cet exemple, l'EAM est de 10 grammes, ce qui signifie que, en moyenne, les
prédictions du modèle s'écartent de 10 grammes des valeurs réelles. L'EAM donne
une idée plus intuitive de l'erreur moyenne du modèle, en utilisant des unités
identiques à celles des données d'origine.

Exemples Applications de l'Apprentissage Supervisé

L'apprentissage supervisé est l'une des méthodes les plus couramment utilisées en
apprentissage automatique en raison de sa simplicité et de son efficacité pour une
large gamme de problèmes. Cependant, il nécessite un grand nombre de données
étiquetées, ce qui peut être une limitation dans certains cas.

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

Classification d'e-mails (Spam/Non-spam) :
- Données d'entrée : Contenu des e-mails (texte).
- Sortie attendue : Spam ou Non-spam.
- Description: modèle formé à partir d'un ensemble d'e-mails étiquetés (spam
ou non-spam). Une fois entraîné, il peut prédire si un nouvel e-mail est un
spam ou non.

Prédiction probabilité de churn (ex : désabonnement Djezzy) :

- Données d'entrée : Données clients (âge, historique d'achats, fréquence
d'utilisation des services, etc.).
- Sortie attendue : Probabilité que le client se désabonne ou non.
- Description : Le modèle est formé sur les comportements passés des clients,
et il apprend à prédire la probabilité de désabonnement.

Reconnaissance d'image (Chats/Chiens par exemple) :

- Données d'entrée : Images de chats et de chiens.
- Sortie attendue : Étiquette de l'animal dans l'image (Chat ou Chien).
- Description : Le modèle est formé avec des images étiquetées, et il apprend à
différencier les deux types d'animaux.

Prédiction du prix d'une maison :

- Données d'entrée : Caractéristiques des maisons (superficie, nombre de
chambres, localisation, etc.).
- Sortie attendue : Prix de vente de la maison.
- Description : Le modèle est formé avec des données historiques de maisons et
leurs prix de vente, et il peut prédire le prix d'une nouvelle maison en fonction
de ses caractéristiques.

Reconnaissance de chiffres manuscrits (exemple plus haut):

- Données d'entrée : Images de chiffres manuscrits (pixels en niveaux de gris).
- Sortie attendue : Le chiffre correspondant (0 - 9).
- Description : Un modèle est entraîné avec des exemples d'images de chiffres
et leurs étiquettes correspondantes. Une fois entraîné, il peut reconnaître de
nouveaux chiffres manuscrits.

Reconnaissance vocale :
- Données d'entrée : Enregistrements audio de la voix humaine.
- Sortie attendue : Texte correspondant à ce qui est dit dans l'audio.
- Description : Le modèle est formé avec des exemples de fichiers audio et
leurs transcriptions correspondantes. Il apprend à transcrire des fichiers audio
non vus auparavant en texte.

Analyse des sentiments :

- Données d'entrée : Commentaires ou avis clients (texte).
- Sortie attendue : Sentiment (positif, négatif ou neutre).
- Description : Le modèle est formé sur des données étiquetées, où chaque
commentaire est associé à un sentiment. Une fois entraîné, il peut déterminer
le sentiment des nouveaux commentaires.

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

Détection de fraude dans les transactions bancaires :
- Données d'entrée : Détails des transactions (montant, lieu, heure, etc.).
- Sortie attendue : Transaction légitime ou frauduleuse.
- Description : Le modèle apprend à partir de transactions historiques
étiquetées (frauduleuses ou non) et peut identifier des anomalies dans les
nouvelles transactions.

Diagnostic médical automatisé :

- Données d'entrée : Résultats de tests médicaux/images médicales (comme les
radiographies).
- Sortie attendue : Diagnostic (exemple : cancer ou non).
- Description : Le modèle est formé sur un ensemble de données médicales
étiquetées avec le diagnostic correspondant et apprend à reconnaître les signes
de maladies dans de nouveaux tests ou images.

Traduction automatique :
- Données d'entrée : Phrase dans une langue source.
- Sortie attendue : Traduction de la phrase dans une autre langue.
- Description : Le modèle est entraîné avec des exemples de paires de phrases
source-cible, par exemple des phrases en français et leurs traductions en
anglais. Il peut traduire de nouvelles phrases.

Prédiction des ventes d’un produit :

- Données d'entrée : Historique des ventes (date, montant, promotions, etc.).
- Sortie attendue : Montant des ventes futures.
- Description : Le modèle apprend à partir de données historiques des ventes et
peut estimer les ventes futures en fonction des tendances passées.

Reconnaissance faciale :
- Données d'entrée : Images de visages.
- Sortie attendue : Identité de la personne.
- Description : Le modèle est formé sur un ensemble de visages étiquetés avec
les identités correspondantes et peut reconnaître les personnes dans de
nouvelles images.

Prédiction du score de crédit :

- Données d'entrée : Informations financières des individus (revenus,
historique de crédit, dettes, etc.).
- Sortie attendue : Score de crédit.
- Description : Le modèle apprend à partir de données historiques pour prédire
la probabilité de remboursement des prêts par les nouveaux demandeurs.

Prédiction de la consommation d'énergie :

- Données d'entrée : Données météorologiques, historiques de consommation
d'énergie.
- Sortie attendue : Consommation d'énergie future.
- Description : Le modèle apprend à partir de l'historique de la consommation
énergétique et des conditions externes (météo, etc.) et prévoit les besoins en
énergie à venir. …..

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

1.A.2)Apprentissage non supervisé :
On a vu que dans l’apprentissage supervisé, les sorties possibles sont connues et
fixées (connues par un superviseur).
Dans l’apprentissage non supervisé, le modèle est formé sur des données non
étiquetées (c-à-d on ne connait pas les sorties possibles au départ) et doit trouver
des structures ou des motifs dans les données. On a des entrées mais on n’a pas de
sorties explicites comme dans le cas supervisé).

L’ensemble D est égal à {x1, x2, …, xn}, (la cible ti n’est pas connue comme dans le
cas supervisé).
L'objectif de l'apprentissage non supervisé est de découvrir des structures ou des
motifs cachés dans les données sans l'aide de labels explicites.

Exemple :
Un exemple serait le regroupement (clustering) où l'on regroupe des données
similaires sans indications préalables (comme par exemple : identifier différents
thèmes d’articles de publications en regroupant les articles similaires, classer des
images de chiffres comme ci-dessous,…. :
Entrées(10 images de 5 et de 6) partitionnement/clustering

L’algorithme d’apprentissage non supervisé doit être capable de détecter qu’on a 2

classes (sans le lui dire) (t classe des 5 et t’ classe des 6) et que l’image1 du 6
appartient à t’, image2 du 5 appartient à t, ….., image10 du 5 appartient à t).

Principe :
-L'algorithme reçoit des données brutes non étiquetées sans savoir à l'avance à quelle
catégorie chaque donnée appartient ou quelle valeur de sortie est correcte.
-L'algorithme doit explorer les relations entre les différentes observations pour trouver
des motifs sous-jacents, comme des regroupements ou des tendances (la découverte
des structures).
-Contrairement à l'apprentissage supervisé, où l'on ajuste le modèle pour minimiser
une erreur spécifique, ici l'algorithme ajuste ses paramètres pour maximiser la
pertinence des structures découvertes (l’ajustement des paramètres).

Exemples Algorithme d’apprentissage non supervisé

Algorithme k-Means (k-moyennes): C’est un algorithme de classification
(clustering) qui regroupe les données en k clusters basés sur des similitudes. C’est
l’outil le plus populaire dans cet apprentissage non-supervisé (sera détaillé plus loin).
Analyse en Composantes Principales (PCA) : Une technique de réduction de
dimension qui transforme les données en un nouvel espace de dimension inférieure
tout en conservant autant que possible la variance des données.
Analyse des Correspondances (CA) : Utilisée pour analyser les relations entre des
variables catégorielles.
Algorithme des Mélanges de Gaussiennes (GMM) : Un modèle probabiliste pour le
clustering basé sur des distributions gaussiennes (probabilités).
Autoencodeurs : Réseaux de neurones utilisés pour apprendre une représentation
(encodage) plus efficace des données, souvent utilisés pour la réduction de dimension
ou la détection d'anomalies.
etc…

Métriques
Les métriques en apprentissage non supervisé varient en fonction du type de
tâche (clustering, réduction de dimension, détection d’anomalies, etc.). Elles
permettent de quantifier la qualité des résultats sans avoir besoin de labels explicites,
et sont essentielles pour affiner les algorithmes et obtenir des résultats pertinents.

Quelques domaines d’utilisation de l’apprentissage non supervisé:

Segmentation clients
Dans une analyse marketing, l'apprentissage non supervisé est utilisé pour
segmenter un groupe de clients en clusters selon leur comportement d'achat (sans
qu'on ait besoin de les étiqueter au préalable). Certains clients pourraient être
regroupés selon des critères comme la fréquence d'achat, les types de produits
achetés, montant dépensé, fréquence des visites, période de l’année où ils font plus
d’achats, etc…. Cela permet aux entreprises de créer des campagnes ciblées pour
chaque groupe (algorithmes k-means).

Réseaux sociaux
Utilisé dans les réseaux sociaux, les utilisateurs interagissent entre eux en suivant
d'autres utilisateurs, en aimant des publications, ou en partageant du contenu. On
souhaite identifier des groupes d'utilisateurs ayant des comportements similaires,
comme ceux qui discutent souvent des mêmes sujets, partagent des intérêts communs
ou interagissent fréquemment les uns avec les autres, les points forts et faibles, etc…

Détection fraude
Détection de fraude (Anomalies) : Une banque cherche à identifier des
transactions suspectes dans son système. Comme les comportements frauduleux ne
sont pas toujours connus à l'avance, elle utilise un algorithme de détection d'anomalies
(comme Isolation Forest ou Local Outlier Factor). Cet algorithme identifie les
transactions qui s'écartent fortement du comportement typique des utilisateurs,
permettant ainsi de signaler les comportements potentiellement frauduleux.

Analyse en composantes principales (ACP)

Réduction de dimensionnalité pour la visualisation (ACP) : Une entreprise
travaille avec un ensemble de données très large et complexe (Big Data) (par
exemple, 10000 caractéristiques par observation). Pour mieux comprendre les
relations dans les données, on utilise l'Analyse en Composantes Principales (ACP),
une technique non supervisée qui réduit les données à quelques (2 ou 3) dimensions.
Cette projection permet à l'entreprise de visualiser les données dans un espace plus
facile à interpréter, tout en conservant l'essentiel de l'information

Pré-traitement d'images (Autoencodeurs)

Reconnaissance d'images par exemple où on souhaite éliminer le bruit des images
avant leur traitement. Elle utilise des autoencodeurs pour apprendre à reconstruire
des images propres à partir de leurs versions bruitées. Les autoencodeurs apprennent

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

des représentations compressées des images et sont capables de "nettoyer" les images
d'entrée sans étiquettes explicites.

Génération de visages réalistes

La génération d'images réalistes à partir de bruit aléatoire. En utilisant des réseaux
antagonistes génératifs (GANs), il peut entraîner un modèle pour générer des
visages humains qui paraissent réalistes. Le générateur produit de nouvelles images,
tandis qu'un discriminateur apprend à différencier les images générées des vraies,
poussant le générateur à améliorer ses résultats.

Recommandation et Association de produits (Algorithme Apriori)

Un supermarché en ligne utilise l'algorithme Apriori pour découvrir des
associations entre les produits que les clients achètent souvent ensemble. Par
exemple, l'algorithme peut détecter que les clients qui achètent du lait achètent
souvent aussi du pain. Cela permet à l'entreprise de proposer des recommandations de
produits connexes aux utilisateurs, améliorant ainsi les ventes croisées.

Détection d'anomalies dans des machines industrielles (RBM)

Identifier des dysfonctionnements dans des machines sans avoir des données
étiquetées sur ce qui constitue un dysfonctionnement. En utilisant une Machine de
Boltzmann Restreinte (RBM), elle peut modéliser les comportements normaux des
machines et identifier les anomalies (comportements déviants) qui peuvent indiquer
des problèmes techniques nécessitant une intervention.

Segmentation d'image (Clustering d'image)

En traitement d'images, l'objectif est souvent de segmenter une image en différentes
régions homogènes (comme identifier des objets ou des surfaces). L’algorithme K-
means ou DBSCAN peut être utilisé pour regrouper des pixels similaires en fonction
de leur intensité de couleur ou de texture. Cela permet, par exemple, de diviser une
image satellite en différentes régions (mer, forêt, zones urbaines, etc…).

Classification de documents (Modèles thématiques)

Dans le domaine du traitement automatique du langage naturel (TALN), des
techniques non supervisées sont utilisées pour identifier des thèmes ou sujets dans un
ensemble de documents.

Compression de données (Autoencodeurs)

Dans le domaine de la compression d'images ou de vidéos, des autoencodeurs
peuvent être utilisés pour apprendre à comprimer des données tout en maintenant leur
qualité visuelle. Par exemple, dans une application de transmission de vidéos en
streaming, un autoencodeur peut être formé pour compresser les vidéos afin de
réduire la bande passante nécessaire à leur transmission, tout en maintenant une
reconstruction précise.

Détection d'objets inhabituels dans l'espace (Détection d'anomalies)

Dans l'astronomie, des algorithmes de détection d'anomalies peuvent être utilisés
pour analyser des données spatiales et identifier des objets ou événements inhabituels,
comme de nouveaux types d'étoiles ou des galaxies. Ces algorithmes peuvent signaler
des objets qui ne correspondent pas aux modèles connus, facilitant la découverte
d'éléments nouveaux ou rares.

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

Clustering génétique (Clustering de séquences ADN)
En bioinformatique, des algorithmes comme l'algorithme de regroupement
hiérarchique peuvent être utilisés pour regrouper des séquences génétiques
similaires. Cela permet de classer différentes espèces ou de comprendre les relations
évolutives entre elles, en identifiant des groupes de gènes qui partagent des motifs
communs.

Apprentissage des représentations dans les jeux vidéo (Réseaux neuronaux auto-
supervisés)
Dans les jeux vidéo, des algorithmes non supervisés peuvent être utilisés pour
apprendre des représentations utiles de l'état du jeu sans avoir besoin d'étiquettes
explicites. Par exemple, dans un jeu de stratégie, un réseau de neurones peut
apprendre à représenter l'état d'un plateau de jeu ou les configurations de joueurs pour
faciliter la prise de décision par une IA.

Regroupement d'animaux (Clustering de mouvements animaux)

Des biologistes utilisent des capteurs pour suivre les mouvements d'animaux
sauvages. En utilisant des techniques de clustering, ils peuvent regrouper des
animaux qui adoptent des comportements similaires (comme la migration, la chasse,
reproduction,…), même sans avoir de labels explicites sur les types de comportement.

Détection de pannes dans des systèmes industriels (Apprentissage par anomalies)

Dans l'industrie, des capteurs sont souvent placés sur des machines pour surveiller
leur fonctionnement. Un algorithme de détection d'anomalies peut identifier des
modèles de fonctionnement anormaux, comme des vibrations inhabituelles, qui
pourraient indiquer un problème ou une panne imminente dans une machine,
permettant ainsi une maintenance prédictive.
etc..

Avantages de l’apprentissage non supervisé :

L’apprentissage non supervisé a plusieurs avantages, surtout lorsqu’il s’agit de
traiter de très grandes quantités de données non étiquetées.
Pas besoin de données étiquetées: qui est particulièrement utile lorsque l'étiquetage
des données est coûteux, difficile ou impossible (exemple des images, du texte, etc…

Volume de données très grand : Traiter des volumes massifs de données sans
intervention humaine pour l’étiquetage (big data).

Exploration de données complexes : Utile pour découvrir des motifs cachés que
l'expert humain n'aurait pas remarqués à l'œil nu.

Réduction de la dimensionnalité : Les techniques non supervisées comme l'analyse

en composantes principales (ACP) permettent de réduire la complexité des données
en diminuant leur dimensionnalité tout en conservant les informations importantes.
Cela facilite la visualisation des données et améliore l'efficacité des algorithmes en
aval. Cela est utile dans des domaines comme la génétique, où les données sont
souvent de très haute dimension, ou en vision par ordinateur.

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

Adaptabilité à des problèmes complexes: L'apprentissage non supervisé est
particulièrement bien adapté aux problèmes complexes et ambigus où les étiquettes de
classe ne sont pas claires ou bien définies. Il peut ainsi être utilisé pour des tâches
exploratoires, comme l'exploration de données dans des domaines scientifiques ou
commerciaux. Par exemple, il permet de modéliser des distributions de données pour
détecter des anomalies, générer des données synthétiques, ou encore identifier des
regroupements naturels dans les données.

Capacité à traiter des données variées : Les algorithmes non supervisés sont
capables de travailler avec des types de données très divers, données numériques,
textuelles, d'images, ou même de données complexes comme les graphes ou les
signaux biologiques. Cela élargit leur champ d'application, allant de l’analyse de texte
et de l’exploration de données génomiques à la reconnaissance d'images ou de sons.

Identification d'anomalies et de valeurs aberrantes : L'un des avantages majeurs

de l'apprentissage non supervisé est sa capacité à détecter des anomalies dans les
données. Ces algorithmes comme Isolation Forest ou Local Outlier Factor,
permettent de trouver des points de données qui se comportent différemment de la
majorité des autres observations. Cela a des applications importantes dans la détection
de fraude financière, le diagnostic industriel, la surveillance de la cyber sécurité.

Génération de nouvelles données : Des techniques comme les réseaux antagonistes

génératifs (GANs) permettent de générer de nouvelles données qui ressemblent à des
données réelles. Cela est utile pour des applications de synthèse d'images,
d'amélioration de la résolution d'images, ou même de création d'art génératif. Les
GANs peuvent aussi être utilisés pour augmenter des ensembles de données lorsqu'il y
a une pénurie de données d'entraînement.

Utilisation dans des systèmes de recommandation : L'apprentissage non supervisé,

via des techniques comme les machines de Boltzmann restreintes (RBM) ou
l'algorithme Apriori, permet d'analyser des comportements d'utilisateurs pour
recommander des produits ou services sans avoir à spécifier des étiquettes de
préférence pour chaque utilisateur. Exemple, des systèmes de recommandation de
produits peuvent détecter des associations cachées et améliorer l'expérience
utilisateur.

Préparation à l'apprentissage supervisé (pré-formation) : L'apprentissage non

supervisé est souvent utilisé pour la pré-formation de modèles avant une phase
d'apprentissage supervisé. Par exemple, des autoencodeurs peuvent être utilisés pour
apprendre des représentations des données qui sont ensuite affinées dans un cadre
supervisé. Cela permet d'améliorer la performance des modèles supervisés, en
particulier lorsqu'il y a peu de données étiquetées disponibles.

Adaptation à des données évolutives : Dans des environnements où les données

évoluent rapidement (par exemple, en finance ou dans les réseaux sociaux),
l'apprentissage non supervisé peut s'adapter aux nouvelles tendances des données sans
nécessiter de ré étiquetage constant. Cela le rend plus flexible pour des tâches
nécessitant une mise à jour fréquente des modèles.

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

B) Algorithme K plus proches voisins (KNN)
L'algorithme des K plus proches voisins (K-Nearest Neighbors, KNN) :
-est un algorithme d'apprentissage automatique supervisé utilisé pour la
classification ou la régression. Un des algorithmes les plus simples en ML.
-classe (en classification) ou prédit (en régression) une valeur pour un nouvel
exemple en fonction de sa proximité avec des exemples connus.
-basé sur la proximité des points de données dans l'espace des caractéristiques et
fait l'hypothèse que les objets similaires se trouvent dans des régions similaires.

Principe de base du KNN

L'idée de base de KNN est qu'un nouvel exemple (ou point) est classé ou prédit en
fonction de la majorité ou de la moyenne des classes (ou valeurs) de ses k voisins
les plus proches dans l'ensemble d'entraînement :
- Pour la classification : KNN attribue à un nouvel exemple la classe majoritaire
parmi ses K voisins les plus proches.
- Pour la régression : KNN prédit une valeur en calculant la moyenne des valeurs
de ses K voisins les plus proches.

Étapes de l'algorithme KNN

-Sélectionner k : Choisir le nombre de voisins k. Il s'agit du nombre de voisins les
plus proches à considérer pour prendre une décision. C’est un hyperparamètre,
souvent déterminé par la validation croisée (voir ci-dessous l’explication) :

-Calculer les distances : Pour chaque point de test (nouvel exemple à prédire ou à
classer), on calcule la distance (généralement la distance euclidienne-distance à vol
d’oiseau) entre ce point et tous les points de l'ensemble d'entraînement. Il existe
d'autres mesures (comme la distance de Manhattan ou la distance de Minkowski) qui
peuvent être utilisées en fonction des besoins.
La formule de la distance euclidienne pour 2 points A(x1,…., xn) et B(y1, y2, …, yn)
pour un espace à n dimensions, est donnée par la formule:

d(A, B)=√(x1 - y1)2 + (x2 - y2)2 + … (xn - yn)2

Exemple de calcul de la distance Euclidienne:

Soient 2 points A(2, 3) et B(5, 7) dans un espace à 2 dimensions, la distance
Euclidienne est donnée par : d(A, B)= √(5-2)2 + (7-3)2 = 5

-Identifier les K voisins les plus proches : Les K points de l'ensemble d'entraînement
ayant les plus petites distances au point de test sont sélectionnés comme ses voisins
les plus proches.

-Attribuer une classe ou une valeur :

En Classification : La classe majoritaire parmi les K voisins est attribuée au point
de test. L'étiquette de l'exemple est déterminée par la majorité des étiquettes de ses k
plus proches voisins. (C'est un vote majoritaire).
En Régression : La moyenne des valeurs des K voisins est utilisée comme
prédiction. La valeur prédite est la moyenne (ou une autre mesure statistique) des
valeurs des k plus proches voisins.

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

Choix du nombre de voisins k (hyperparamétre)
- Petit k (par exemple k=1 ou k=3) : Le modèle sera plus flexible et peut être plus
susceptible de surapprentissage (overfitting), car il est très sensible aux
fluctuations des données locales.
- Grand k (par exemple k=10 ou k=20) : Le modèle sera plus lisse et moins
sensible au bruit, mais il peut sous-apprendre (underfitting) en négligeant des
motifs locaux importants.

Distances utilisées dans KNN

L'algorithme KNN repose sur une mesure de distance pour déterminer quels sont
les voisins les plus proches :
La distance euclidienne (vue ci-dessus) est la plus couramment utilisée, mais
d'autres métriques peuvent également être utilisées, selon le contexte. pour rappel,
pour 2 points A(x1, x2,…., xn) et B(y1, y2, …, yn) pour un espace à n dimensions, la
distance Euclidienne est donnée par la formule:

d(A, B)=√(x1 - y1) 2+ (x2 - y2)2 + … (xn - yn)2

Distance de Manhattan (distance L1, ou distance des blocs). Contrairement à la

distance euclidienne, qui mesure la distance «à vol d'oiseau», la distance de
Manhattan mesure la somme des différences absolues entre les coordonnées des
points, ce qui correspond à une distance suivant une grille (mesure la distance le long
des axes). Pour 2 points A(x1, x2, …., xn) et B(y1, y2, …., yn) dans un espace à n
dimensions, la distance de Manhattan est donnée par la formule:
dManhattan(A, B) = |x1 - y1| + |x2 - y2| + ….. +|xn - yn|
c’est la somme des valeurs absolues des différences d’indice xi et yi
Exemple :
Considérons deux points A(2,3) et B(5,7) dans un espace à deux dimensions, la
distance de Manhattan entre A et B est calculée ainsi :
dManhattan(A,B) = ∣5 − 2∣ + ∣7 − 3∣ = 3+4 = 7

Quand utiliser la distance de Manhattan dans KNN ?

Lorsque les caractéristiques des données sont de nature différente (par exemple,
l'âge, le revenu, et la taille), la distance de Manhattan peut parfois mieux capturer la
différence que la distance euclidienne.
Elle tend à donner plus de poids aux petites différences le long d'un seul axe, ce qui
peut être utile dans des situations où une seule caractéristique dominante est plus
importante que d'autres.

Distance de Minkowski : elle généralise les deux précédentes, et elle est utilisée
dans l'algorithme KNN pour mesurer la similarité entre les points dans un espace de
caractéristiques. Elle introduit un paramètre p qui contrôle la forme de la distance, et
en fonction de la valeur de p, elle peut devenir soit la distance de Manhattan, soit la
distance euclidienne, ou même d'autres types de distances. Elle est définie comme
suit : Pour deux points A(x1, x2, …, xn) et B(y1, y2, …, yn) dans un espace à n
dimensions, la distance de Minkowski est définie par la formule :
DMinkowsky(A, B) = (somme(|xi – yi|p)1/p
(avec p=1, c’est la distance de Manhattan, et avec p=2, c’est la distance euclidienne).

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

Exemple :
Prenons les deux points A(2, 3) et B(5, 7) dans un espace à 2 dimensions (x1,x2).
Si p=3, la distance de Minkowski entre A et B est :
dMinkowski(A, B)=(∣5 − 2∣3+∣7 − 3∣3)1/3=(33 + 43)1/3=(27 + 64)1/3=(91)1/3≈4.4979
Utilisation dans KNN :
Dans l'algorithme KNN, la distance de Minkowski est souvent utilisée car elle
permet de choisir la forme de la mesure de distance en fonction des besoins
spécifiques du problème. La sélection du paramètre p permet de moduler la sensibilité
de l'algorithme à la direction des différences entre les points.
p=1 (distance de Manhattan) : utile lorsque les données sont disposées en grille, ou
lorsque les caractéristiques doivent être évaluées individuellement.
p=2 (distance euclidienne) : idéale pour les situations où toutes les directions sont
également importantes.
p>2 : met plus de poids sur les grandes différences entre les caractéristiques, ce qui
peut être utile dans certains contextes.

Exemples d’utilisation de KNN:

Exemple1 : Soit un ensemble de données avec 2 caractéristiques (exemple, la taille
et le poids) pour prédire si une personne est "sportive" ou "non sportive".
Taille en cm Poids en Kg Sportif (classe) Oui/Non
160 50 oui
170 65 oui
180 80 non
175 75 non
165 55 oui
Etapes de KNN :
Choix du nombre de voisins (k) : Supposons que nous choisissions k = 3.
Distance : Pour prédire la classe d'un nouveau point, on doit calculer la distance (par
exemple, la distance euclidienne) entre ce nouveau point et tous les points existants.
(Formule de la distance euclidienne: d =√(Taille1−Taille2)2+(Poids1−Poids2)2 )
Trouver les 3 voisins les plus proches : Après avoir calculé les distances, on choisit
les 3 points avec les plus petites distances.
Vote majoritaire : On regarde la classe des 3 voisins les plus proches et on effectue
un vote. Par exemple, si 2 sur 3 des voisins sont "Oui" (sportif), alors le point inconnu
sera classé comme "Oui".

Exemple de calcul (pour un nouveau point) : (172 cm, 70 kg)

Distance avec 1er point (160 cm, 50 kg) : d =√(172−160)2+(70−50)2 ≈ 23.32
Distance avec 2eme (170 cm, 65 kg): d =√ (172−170)2+(70−65)2 ≈ 5.39
eme 2 2
Distance avec 3 (180 cm, 80 kg) : d=√(172−180) +(70−80) ≈ 12.81
Distance avec 4eme (175 cm, 75 kg) : d=√(172−175)2+(70−75)2 ≈ 5.83
eme 2 2
Distance avec 5 (165 cm, 55 kg) : d=√(172−165) +(70−55) ≈ 16.55
Les trois voisins les plus proches sont (170 cm, 65 kg), (175 cm, 75 kg) et (180 cm,
80 kg) (en gras), les classes correspondantes sont "Oui", "Non", et "Non", la majorité
des voisins (2 sur 3) indique que le nouveau point est classé "Non".

Exemple2 : Soit un problème de classification de fleurs à partir des données d'une

base appelée Iris dataset, qui contient des informations sur trois espèces de fleurs

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

d'iris (setosa, versicolor, virginica), en se basant sur 4 caractéristiques des feuilles de
la fleur: longueur et largeur des sépales, longueur et largeur des pétales.

Exemple avec le dataset Iris

Long Sépale Larg. Sépale Long. Pétale Larg. Pétale Espèce
5.1 3.5 1.4 0.2 Iris Setosa
4.9 3.0 1.4 0.2 Iris Setosa
6.3 3.3 6.0 2.5 Iris Virginica
5.8 2.7 5.1 1.9 Iris Virginica
6.0 2.9 4.5 1.5 Iris Versicolor
5.5 2.3 4.0 1.3 Iris Versicolor

Le but est de prédire l'espèce d'une fleur inconnue en utilisant ses caractéristiques
(Longueur sépale=5.9, Largeur sépale=3.0, Longueur pétale=5.1, Largeur pétale=1.8).
Étapes de KNN :
Choix du nombre de voisins (k) : Par exemple, choisissons k = 3.
Calcul des distances : Pour prédire l'espèce d'une nouvelle fleur avec les
caractéristiques ci-dessus 5.9 cm, 3.0 cm, 5.1 cm, 1.8 cm, nous devons calculer la
distance (par exemple, la distance euclidienne) entre ce point et les points existants
dans notre ensemble de données.
Trouver les 3 voisins les plus proches parmi les 6 éléments du dataset:
Distance avec Iris Setosa (5.1, 3.5, 1.4, 0.2) :
d= √(5.9−5.1)2+(3.0−3.5)2+(5.1−1.4)2+(1.8−0.2)2 ≈ 4.14
Distance avec Iris Setosa (4.9, 3.0, 1.4, 0.2) :
d= √(5.9−4.9)2+(3.0−3.0)2+(5.1−1.4)2+(1.8−0.2)2 ≈ 4.15
Distance avec Iris Virginica (6.3, 3.3, 6.0, 2.5) :
d= √(5.9−6.3)2+(3.0−3.3)2+(5.1−6.0)2+(1.8−2.5)2 ≈ 1.24
Distance avec Iris Virginica (5.8, 2.7, 5.1, 1.9) :
d= √(5.9−5.8)2+(3.0−2.7)2+(5.1−5.1)2+(1.8−1.9)2 ≈ 0.33
Distance avec Iris Versicolor (6.0, 2.9, 4.5, 1.5) :
d= √(5.9−6.0)2+(3.0−2.9)2+(5.1−4.5)2+(1.8−1.5)2 ≈ 0.69
Distance avec Iris Versicolor (5.5, 2.3, 4.0, 1.3) :
d= √(5.9−5.5)2+(3.0−2.3)2+(5.1−4.0)2+(1.8−1.3)2 ≈ 1.45
Vote majoritaire :
Les 3 voisins les plus proches (puisqu’on a pris k=3) sont :
Iris Virginica (5.8, 2.7, 5.1, 1.9) avec une distance de 0.33,
Iris Virginica (6.3, 3.3, 6.0, 2.5) avec une distance de 1.24,
Iris Versicolor (6.0, 2.9, 4.5, 1.5) avec une distance de 0.69.
2 des voisins les plus proches sont de la classe Iris Virginica et un seul est Iris
Versicolor. Donc, par vote majoritaire, le nouveau point est classé Iris Virginica.
l'algorithme KNN a prédit que la fleur inconnue est de l'espèce Iris Virginica.

Exemple3 avec distance de Manhattan

Soit un exemple d'application de l'algorithme KNN en utilisant la distance de
Manhattan. (La distance de Manhattan est la somme des valeurs absolues des
différences entre les coordonnées des points dans chaque dimension voir ci-dessus.)
Soient des données sur trois types de fruits : Pomme, Orange, et Banane. Les
caractéristiques utilisées pour chaque fruit sont : Poids (en grammes) et la Couleur
(quantifiée par une échelle de 0 à 10 où 0 est vert et 10 est rouge) :

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

 Poids (g) Couleur (0-10) Fruit
180 9 Pomme
200 8 Pomme
150 6 Orange
170 5 Orange
120 4 Banane
130 3 Banane

Etapes de KNN avec Distance de Manhattan :

Choix du nombre de voisins (k) : Par exemple, nous allons choisir k = 3.
Calcul de la distance de Manhattan :
dManhattan(P1, P2) = ∣Poids1 − Poids2∣ + ∣Couleur1 − Couleur2∣
Soit un nouveau fruit avec les caractéristiques suivantes : Poids : 160 g et Couleur :
5. l’objectif est de prédire de quel fruit il s'agit.

Calcul des distances entre ce nouveau fruit et chaque fruit du tableau :

Distance avec Pomme (180g, 9) d = ∣160 − 180∣ + ∣5 − 9∣ = 20 + 4 = 24
Distance avec Pomme (200g, 8) : d = ∣160 − 200∣ + ∣5 − 8∣ = 40 + 3 = 43
Distance avec Orange (150g, 6) : d = ∣160 − 150∣ + ∣5 − 6∣ = 10 + 1 = 11
Distance avec Orange (170g, 5) : d = ∣160 − 170∣ + ∣5 − 5∣ = 10 + 0 = 10
Distance avec Banane (120g, 4) : d = ∣160 − 120∣ + ∣5 − 4∣ = 40 + 1 = 41
Distance avec Banane (130g, 3) : d = ∣160 − 130∣ + ∣5 – 3∣ = 30 + 2 = 32
Trouver les 3 voisins les plus proches :
Orange (170g, 5) : distance = 10,
Orange (150g, 6) : distance = 11
Pomme (180g, 9) : distance = 24
Vote majoritaire :
Parmi les 3 voisins les plus proches, deux sont des Oranges et un est une Pomme.
Par vote majoritaire, le nouveau fruit est classé comme une Orange.

Exemple4 KNN en régression :

Dans un contexte de régression, l'algorithme KNN peut également être utilisé pour
prédire des valeurs numériques continues plutôt que des classes. Contrairement à la
classification où le vote majoritaire est utilisé, en régression, la prédiction est calculée
en prenant la moyenne (ou une autre mesure statistique) des valeurs cibles des k
voisins les plus proches.
Imaginons un scénario où nous souhaitons prédire le prix d'une maison en
fonction de sa surface (en m²).
Voici un petit dataset:
Surface (m²) Prix (dizaines de milliers de DA)
50 200
60 240
80 280
100 350
130 400
Etapes de KNN pour la régression :
1. Choix du nombre de voisins (k) : Supposons que nous choisissons k = 3.

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

2. Calcul des distances : Nous allons prédire le prix d'une maison de 90 m². Pour ce
faire, nous calculons la distance (ici, nous utilisons la distance Manhattan) entre la
surface de cette nouvelle maison et celles des maisons existantes dans notre tableau.
3. Calcul des distances :
Distance avec la maison de 50 m² : d=∣90−50∣=40
Distance avec la maison de 60 m² : d=∣90−60∣=30
Distance avec la maison de 80 m² : d=∣90−80∣=10
Distance avec la maison de 100 m² : d=∣90−100∣=10
Distance avec la maison de 120 m² : d=∣90−130∣=40
4. Trouver les 3 voisins les plus proches :
Maison de 80 m² : distance = 10
Maison de 100 m² : distance = 10
Maison de 60 m² : distance = 30
Calculer la prédiction : Puisque nous utilisons la régression, la prédiction du prix
pour la maison de 90 m² sera la moyenne des prix des 3 voisins les plus proches :
Prix de la maison de 80 m² : 280
Prix de la maison de 100 m² : 350
Prix de la maison de 60 m² : 240
La moyenne est calculée ainsi : Prix prédictif=(280+350+240) / 3 = 290
Prédiction finale : Le KNN prédit que le prix de la maison de 90 m² sera 290.

Dans cet exemple, l'algorithme KNN a été utilisé pour faire une prédiction dans un
contexte de régression. L'algorithme a estimé le prix d'une maison de 90 m² en se
basant sur la moyenne des prix des 3 maisons les plus proches. Contrairement à la
classification, où le vote majoritaire est utilisé, la régression KNN prend la moyenne
des valeurs cibles pour faire la prédiction. Ce type de régression KNN est souvent
utilisé dans des problèmes tels que la prédiction des prix, la prévision de la demande,
ou la prédiction des valeurs numériques en général.

Choix de k : Validation croisée

Le choix optimal de k est souvent déterminé expérimentalement via une validation
croisée qui consiste diviser les données en plusieurs parties ou "folds" (par exemple
10 segments) de manière aléatoire, À chaque itération, l'algorithme est entraîné sur 9
folds et évalué sur le 10e fold restant, Répétez ce processus pour différentes valeurs de
k (de 1 à 20 par exemple). Pour chaque valeur de k, calculez la performance moyenne
(précision, par exemple) et à partir des résultats obtenus pour chaque fold,
sélectionnez la valeur de k qui donne les meilleurs résultats moyens en validation
croisée.
Exemple : Soit le jeu de données (dataset) Breast Cancer. Ce dataset contient des
informations sur les tumeurs et le but est de prédire si une tumeur est bénigne ou
maligne. Le dataset est divisé en 5 sous-ensembles (par exemple). Pour chaque valeur
de k (de 1 à 20 par exemple), on entraîne le modèle sur 4 des sous-ensembles et on
teste sur le 5ème. Ce processus est répété 5 fois et la précision moyenne est calculée
pour chaque k. Pour cet exemple on trouve les différentes valeurs de précisions :
pour k=1, précision moyenne 0.8750
pour k=2, «« 0.8821
pour k=3 , « « 0.8982
pour k=4, « « 0.9043
pour k=5, « « 0.9104
…….

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

 Puis on prend la valeur de k donnant la meilleure précision, exemple k=5 (jusqu’ici).

Avantages de KNN
- Simplicité : KNN est facile à comprendre et à implémenter, ce qui en fait un bon
point de départ pour des tâches de classification et de régression.
- Pas d'entraînement : Contrairement à de nombreux algorithmes, KNN ne
nécessite pas de phase d'apprentissage explicite. Il "apprend" seulement au
moment de la prédiction (on parle d'un algorithme lazy ou paresseux).
- Flexibilité : Il peut être utilisé pour des problèmes de classification et de
régression.

Inconvénients de KNN
- Complexité computationnelle : KNN devient inefficace lorsque la taille de
l'ensemble d'entraînement est grande, car il doit calculer les distances pour chaque
point de l'ensemble d'entraînement à chaque prédiction. Cela rend l'algorithme
lent pour des ensembles de données volumineux.
- Sensibilité à la distance : KNN dépend fortement de la mesure de distance
choisie, ce qui peut poser problème dans des jeux de données avec des échelles
différentes ou des caractéristiques non pertinentes.
- Sensibilité au bruit : KNN est sensible aux points de données bruyants, surtout
lorsque K est petit.
- Curseur de la dimensionnalité : KNN peut souffrir lorsque les données ont un
grand nombre de dimensions. En effet, plus le nombre de dimensions augmente,
plus les distances entre les points deviennent difficiles à interpréter, et cela peut
réduire l'efficacité du modèle (les points deviennent "plus éloignés" en moyenne,
rendant le concept de proximité moins pertinent).

Applications de KNN
L'algorithme KNN est simple et flexible, ce qui le rend adapté à de nombreuses
applications pratiques dans divers domaines. Quelques exemples d'applications:

Reconnaissance d'images et de formes

Objectif : Classer des images en fonction de leur contenu.
Exemple : Dans la reconnaissance de chiffres manuscrits (comme dans le célèbre
ensemble de données MNIST), KNN peut être utilisé pour identifier un chiffre en
comparant une nouvelle image avec d'autres images déjà étiquetées.
Approche : Chaque image est une caractéristique, et la distance (euclidienne,
Manhattan, etc.) est utilisée pour déterminer à quel chiffre l'image ressemble le plus.

Systèmes de recommandation
Objectif : Recommander des produits ou du contenu aux utilisateurs.
Exemple : Dans les systèmes de recommandation pour les films ou les produits, KNN
peut être utilisé pour trouver des utilisateurs ayant des préférences similaires (en
fonction des notations ou comportements passés) et recommander des produits en
fonction de ce que ces utilisateurs similaires ont aimé.
Approche : Les utilisateurs ou les produits sont représentés sous forme de vecteurs de
caractéristiques, et KNN identifie les voisins les plus proches (utilisateurs ou produits
similaires).

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

Détection de fraude
Objectif : Identifier des comportements inhabituels ou frauduleux dans les
transactions.
Exemple : Dans les systèmes de détection de fraude bancaire, KNN peut être utilisé
pour détecter des transactions anormales en comparant les nouvelles transactions à
celles qui sont considérées comme normales.
Approche: Chaque transaction est représentée par un ensemble de caractéristiques
(montant, type de transaction, lieu, ..), et les transactions proches sont analysées pour
vérifier si elles sont similaires à des transactions frauduleuses précédemment
détectées.

Analyse de données médicales

Objectif : Diagnostiquer des maladies ou des conditions médicales.
Exemple : KNN est utilisé pour prédire la présence de certaines maladies (comme le
diabète ou les maladies cardiaques) en fonction des caractéristiques du patient (âge,
poids, pression artérielle, etc.).
Approche : Les patients sont classés en fonction de leurs caractéristiques médicales,
et les k voisins les plus proches d'un nouveau patient sont utilisés pour prédire son état
de santé.

Reconnaissance vocale
Objectif : Identifier ou classer des motifs dans les signaux audio.
Exemple : KNN est utilisé dans des systèmes de reconnaissance vocale pour classer
des segments de parole en fonction de caractéristiques acoustiques comme la
fréquence et l'amplitude.
Approche : Les segments audio sont comparés à un ensemble d'exemples déjà classés
pour identifier la parole.

Analyse de sentiments
Objectif : Déterminer le sentiment (positif, négatif, neutre) d'un texte.
Exemple : Dans l'analyse de commentaires sur les réseaux sociaux ou les avis clients,
KNN peut être utilisé pour classifier un texte selon son sentiment en fonction de la
similarité avec d'autres textes déjà classés.
Approche : Les mots du texte sont représentés sous forme de vecteurs (via des
techniques comme TF-IDF ou les embeddings de mots), et KNN identifie les textes
les plus similaires pour déterminer le sentiment.

Prédiction du prix de l'immobilier

Objectif : Estimer le prix d'un bien immobilier en fonction de ses caractéristiques.
Exemple : Pour prédire le prix d'une maison, KNN peut être utilisé pour comparer les
caractéristiques d'une maison (taille, localisation, nombre de chambres) avec celles de
maisons vendues précédemment dans la même zone.
Approche : KNN effectue une régression en prenant la moyenne des prix des k
maisons les plus similaires.

Détection d'anomalies
Objectif : Identifier des points de données qui diffèrent significativement du reste du
jeu de données.

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

Exemple : KNN peut être utilisé pour la détection d'anomalies dans des systèmes
industriels où des déviations significatives des mesures standards indiquent des
pannes ou des comportements inhabituels.
Approche : Les distances entre les points de données sont calculées, et les points qui
sont loin de tous les autres points peuvent être considérés comme des anomalies.

Classification d'espèces en biologie

Objectif : Classer des organismes ou des espèces en fonction de leurs
caractéristiques.
Exemple : KNN peut être utilisé pour classifier des plantes ou des animaux en
fonction de leurs caractéristiques morphologiques ou génétiques.
Approche : Les espèces sont représentées par un ensemble de caractéristiques (taille,
forme, ADN), et KNN identifie les espèces similaires pour effectuer la classification.

Reconnaissance faciale
Objectif : Identifier des personnes sur la base d'images faciales.
Exemple : KNN peut être utilisé dans les systèmes de reconnaissance faciale pour
identifier des individus en fonction des traits de leur visage.
Approche : Les images sont converties en vecteurs de caractéristiques (par exemple
via des techniques d'extraction de traits comme PCA ou des réseaux de neurones
convolutifs), puis KNN est utilisé pour identifier les visages similaires.

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

C)Algorithme k-Means (k-moyennes):
C’est un algorithme de clustering qui regroupe les données en k clusters basés sur
des similitudes. C’est l’outil le plus populaire dans l’apprentissage non-supervisé.

Fonctionnement de l'algorithme :
Initialisation :
-Choisir le nombre de clusters k (nombre de groupes que l’on souhaite former).
-Initialiser aléatoirement k centroïdes (points représentant les centres des clusters).
Ces centroïdes peuvent être choisis comme des points de données aléatoires ou
générés de manière plus sophistiquée (comme avec l'algorithme K-Means++).

Assignation des clusters :

-Assigner chaque point de données au centroïde le plus proche. La distance est
généralement mesurée par la distance euclidienne (la plus utilisée). Chaque point de
données appartient au cluster dont le centroïde est le plus proche.

Mise à jour des centroïdes :

-Calculer la nouvelle position des centroïdes en prenant la moyenne de toutes les
données assignées à chaque cluster.
-Les nouveaux centroïdes sont les moyennes des points dans chaque cluster.

Répétition :
Répéter les étapes d'assignation et de mise à jour jusqu'à ce que les centroïdes ne
changent plus ou que le changement soit minime. L'algorithme converge lorsque les
centres des clusters ne se déplacent plus de manière significative ou lorsqu'un critère
d'arrêt est atteint.

Exemples général illustratif

Exemple1 :
Imaginons que vous avez un ensemble de données de points dans un espace à 2
dimensions et que vous souhaitez les regrouper en 3 clusters :
Initialisation : Choisir aléatoirement 3 points comme centroïdes initiaux (k=3).
Assignation : Assignez chaque point au centroïde le plus proche, formant 3 clusters.
Mise à jour : Calculez les nouveaux centroïdes en prenant la moyenne des points
dans chaque cluster.
Répétition : Répétez l'assignation et la mise à jour jusqu'à ce que les centroïdes ne
changent plus.
Après convergence, on aura 3 groupes de points dans l'espace à 2 dimensions,
chacun représenté par un centroïde central. Ces groupes refléteront les structures
naturelles des données.

Point x y
1 1.0 2.0
2 1.5 1.8
3 5.0 8.0
4 6.0 9.0
5 8.0 8.0
6 8.5 9.0

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

Initialisation
Choisir le nombre de clusters k (soit par exemple k = 3).
Initialiser aléatoirement 3 centroïdes.
Soit par exemple, les centroïdes initiaux, les points suivants (1er, 3eme et 5eme):
Centroïde 1 : (1.0, 2.0) 1er point
Centroïde 2 : (5.0, 8.0) 3e point
Centroïde 3 : (8.0, 8.0) 5e point

Assignation des clusters Assignez chaque point au centroïde le plus proche en

utilisant la distance euclidienne. La distance euclidienne entre un point (x1, y1) et un
point centroïde (x2, y2) est calculée comme suit:
Deuclidienne = √(x2−x1)2 + (y2−y1)2
Calculons les distances pour chaque point par rapport aux centroïdes et attribuons-
les au cluster le plus proche.
Pt Distance au Centroïde1 au Centroïde2 au Centroïde3 proche du Cluster
1 0.00 8.49 9.43 1
2 0.28 7.21 8.46 1
3 8.49 0.00 5.83 2
4 9.22 1.41 3.16 2
5 9.22 1.41 0.00 3
6 9.90 1.41 1.00 3

Mise à jour des centroïdes : Recalculez les centroïdes en prenant la moyenne des
points assignés à chaque cluster. Pour 2 points du cluster ((x1+x2)/2, (y1+y2)/2))
Cluster 1: Points 1 et 2 Nouveau Centroide1=((1.0+1.5)/2 ,(2.0+1.8)/2)=(1.25 ,1.90)
Cluster 2:Points 3 et 4 Nouveau Centroide2=((5.0+6.0)/2,(8.0+9.0)/2) = (5.50 , 8.50)
Cluster 3:Points 5 et 6 Nouveau Centroide 3=((8.0+8.5)/2,(8.0+9.0)/2)= (8.25 , 8.50)

Répétition Répétez les étapes d'assignation et de mise à jour avec ces nouveaux
centroides jusqu'à ce que les centroïdes ne changent plus significativement. Pour
simplifier, supposons que la convergence a été atteinte après quelques itérations.

Résultats Finaux
Après la convergence, on obtient les clusters suivants avec leurs centroïdes finaux :
Cluster 1 : Points proches du centroïde (1.25, 1.90) Contient : Points 1 et 2
Cluster 2 : Points proches du centroïde (5.50, 8.50) Contient : Points 3 et 4
Cluster 3 : Points proches du centroïde (8.25, 8.50) Contient : Points 5 et 6

Cet exemple démontre comment K-Means regroupe les points en clusters en

fonction de leur proximité aux centroïdes. L'algorithme fonctionne en itérant entre
l'assignation des points aux clusters et la mise à jour des centroïdes jusqu'à ce que les
clusters se stabilisent.

Exemple 2:
La segmentation de clients dans le domaine du marketing. Une entreprise souhaite
comprendre ses clients afin de créer des offres personnalisées. Elle dispose d'un
dataset sans étiquettes contenant des informations sur les habitudes d'achat de ses
clients: (Montant dépensé par an, Fréquence d'achat, Nombre produits achetés, Âge).

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

 L'objectif est de regrouper ces clients en plusieurs segments (clusters) similaires
afin de mieux cibler les campagnes marketing.

-Collecte des données : Le dataset contient des caractéristiques sur chaque client,
mais il n'y a pas de label ou de catégorie prédéfinie (comme « client fidèle » ou «
client occasionnel »).

Client Montant dépensé Fréquence d'achat (fois/an) Nombre de produits Âge

1 2 500 12 30 25
2 10 000 50 100 40
3 3 000 15 40 35
... ... ... ... ...

Utiliser l'algorithme K-Means pour diviser ces clients en k groupes.

Soit par exemple k=3 pour identifier 3 segments de clients.
K-Means commence par initialiser aléatoirement 3 centroïdes (points représentant
les centres des clusters).
Chaque client est ensuite affecté au centroïde le plus proche, créant ainsi 3 clusters.
Les centroïdes sont réajustés à chaque itération, en calculant la moyenne des clients
dans chaque cluster.
Après plusieurs itérations, le modèle K-Means converge.

Un exemple de segmentation obtenue :

Cluster 1 : Jeunes clients occasionnels : Ces clients ont tendance à acheter peu
fréquemment et à dépenser moins (ex : moins de 5000 par an).
Cluster 2 : Clients réguliers : Ces clients achètent fréquemment avec des montants
modérés (entre 5 000 et 10 000 par an).
Cluster 3 : Gros dépensiers : Ces clients achètent très souvent et dépensent
beaucoup (plus de 10 000 par an).

Avec cette segmentation, l'entreprise peut : Créer des offres promotionnelles pour
fidéliser les jeunes clients occasionnels, Proposer des programmes de fidélité pour
les clients réguliers, Offrir des services premium ou exclusifs aux gros dépensiers.

Exemple 3:
Un responsable du marketing, avec une large gamme de produits, souhaite
regrouper les produits en fonction de leurs caractéristiques pour créer des catégories
de produits plus pertinentes et améliorer les recommandations aux clients. Il dispose
de données sur divers produits, comprenant des caractéristiques telles que :
Prix, Nombre de ventes, Évaluation moyenne des clients,Poids)
Produit Prix Nombre de ventes Évaluation moyenne Poids (kg)
1 299 150 4.5 1.2
2 49 500 4.0 0.5
3 150 200 4.8 0.8
... ... ... ... ...
Prétraitement :
Normalisez les caractéristiques pour qu'elles aient des échelles comparables (par
exemple, mettre à l'échelle le prix et le nombre de ventes pour éviter que les
caractéristiques ayant des valeurs plus élevées ne dominent le clustering).

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

Application de K-Means :
Soit par exemple k=4 pour regrouper les produits en 4 catégories.
Initialisation : Sélectionnez aléatoirement 4 centroïdes.
Assignation : Chaque produit est affecté au cluster dont le centroïde est le plus
proche.
Mise à jour : Calculez les nouveaux centroïdes en prenant la moyenne des
caractéristiques des produits dans chaque cluster.
Répétition : Répétez les étapes d'assignation et de mise à jour jusqu'à convergence.

Résultats : Après convergence, vous obtenez 4 clusters de produits. Les produits dans
chaque cluster ont des caractéristiques similaires. Par exemple :
Cluster 1 : Produits de luxe : Articles avec un prix élevé, une évaluation élevée, et
un faible nombre de ventes (produits haut de gamme avec des ventes limitées).
Cluster 2 : Produits populaires à bas prix : Articles avec un prix bas, un grand
nombre de ventes, et une évaluation moyenne (produits bon marché et populaires).
Cluster 3 : Produits de moyenne gamme : Articles avec un prix moyen, un
nombre de ventes moyen, et une évaluation moyenne (produits standard).
Cluster 4 : Produits légers et bon marché : Articles avec un prix bas, un nombre
de ventes moyen, mais un faible poids (petits articles bon marché).

Exemple4 : Supposons que nous avons les points suivants à deux dimensions que
nous voulons classer en groupes similaires :
Points = {(1, 1), (1.5, 2), (3, 4), (5, 7), (3.5, 5), (4.5, 5), (3, 3.5)}

Étapes du K-means
Étape 1 : Initialisation
Choisissons le nombre de clusters K = 2 (on veut diviser les points en 2 groupes).
Initialement, les centroïdes (centres des clusters) sont choisis aléatoirement.
Supposons que nous commençons avec ces deux points comme centroïdes initiaux :
cluster1 = Centroïde 1 : (1, 1) et cluster2 = Centroïde 2 : (5, 7)

Étape 2 : Attribution des points aux clusters

On calcule la distance euclidienne entre chaque point et les centroïdes, puis on
attribue chaque point au centroïde le plus proche.
Pour le point (1, 1) :
Distance au centroïde 1 = √(1−1)2+(1−1)2 =0 x
Distance au centroïde 2 = √(5−1)2+(7−1)2 ≈7.21
Pour le point (1.5, 2) :
Distance au centroïde 1 : √(1−1.5)2+(1−2)2 ≈ 1.12 x
Distance au centroïde 2 : √(5−1.5)2+(7−2)2 ≈ 6.10
Pour le point (3, 4) :
Distance au centroïde 1 : √(1−3)2+(1−4)2 ≈ 3.61 x
Distance au centroïde 2 : √(5−3)2+(7−4)2 ≈ 3.61 x
Pour le point (5, 7)
Distance au centroïde 1 : √(1−5)2+(1−7)2 ≈ 7.21
Distance au centroïde 2 : √(5−5)2+(7−7)2 ≈ 0 x
Pour le point (3.5, 5)
Distance au centroïde 1 : √(1−3.5)2+(1−5)2 ≈ 4.72
Distance au centroïde 2 : √(5−3.5)2+(7−5)2 ≈ 2.5 x

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB

Pour le point (4.5, 5)
Distance au centroïde 1 : √(1−4.5)2+(1−5)2 ≈ 5.32
Distance au centroïde 2 : √(5−4.5)2+(7−5)2 ≈ 2.06 x
Pour le point (3, 3.5)
Distance au centroïde 1 : √(1−3)2+(1−3.5)2 ≈ 3.20 x
Distance au centroïde 2 : √(5−3)2+(7−3.5)2 ≈ 4.03
Nous obtenons la répartition suivante (pour le point (3,4) on a égalité) :
Cluster 1 : {(1, 1), (1.5, 2), (3, 3.5)} Cluster 2 : {(3, 4), (5, 7), (3.5, 5), (4.5, 5)}

Étape 3 : Mise à jour des centroïdes

Pour chaque cluster, nous calculons le nouveau centroïde en prenant la moyenne
des coordonnées de tous les points dans ce cluster.
Nouveau centroïde 1: moyenne des points {(1, 1), (1.5, 2), (3, 3.5)} =
((1+1.5+3)/3, (1+2+3.5)/3) = (1.83, 2.17)
Nouveau centroïde 2 : moyenne des points {(3, 4), (5, 7), (3.5, 5), (4.5, 5)} =
((3+5+3.5+4.5)/4, (4+7+5+5)/4) = (4, 5.25)

Étape 4 : Répétition
Nous répétons à partir de l'étape 2 d'attribution des points aux clusters avec les
nouveaux centroïdes et mettons à jour les centroïdes jusqu'à ce que les positions des
centroïdes cessent de changer (c'est-à-dire qu'il y ait convergence).

Visualisation
Les points sont divisés en deux groupes en fonction de leur proximité avec les
centroïdes, et à chaque itération, les centroïdes se déplacent jusqu'à atteindre une
position stable. Le processus se termine lorsque les centroïdes ne bougent plus ou que
les changements sont négligeables.

Caractéristiques et Propriétés de l’algorithme

Simplicité : L'algorithme K-Means est simple à comprendre et à mettre en œuvre.
Efficacité : Il est relativement rapide pour des ensembles de données de taille
moyenne, bien que sa performance puisse diminuer avec des données de très grande
taille ou des dimensions élevées.
Convergence : K-Means converge vers une solution locale, ce qui signifie qu'il peut
ne pas trouver la solution optimale globale. L'initialisation des centroïdes peut
influencer le résultat final.
Sensibilité aux valeurs aberrantes : Les valeurs aberrantes peuvent affecter les
centroïdes, car K-Means minimise la variance intra-cluster.

Applications de l’algorithme k-means

Segmentation de clients : Regrouper les clients en fonction de leur comportement
d'achat pour des stratégies marketing ciblées.
Classification d'images : Regrouper des images en fonction des caractéristiques
extraites pour organiser des grandes bases d'images ou pour prétraiter des données
pour d'autres algorithmes de classification.
Analyse de texte : Regrouper des documents ou des articles en fonction de leur
contenu, comme dans l'analyse de texte ou le clustering de documents.
Détection de modèles : Identifier des structures ou des motifs sous-jacents dans les
données, comme dans les études exploratoires des données.

Ing 3 Eng soft Fond. IA 2024/2025 H AZZOUNE USTHB