Résumer IA

Formulation de problème :

Recherche de solutions :

Arbre :
Graphe :

Mesure de la performance de la résolution de problèmes :

Stratégie d’exploration :
Non informée :

Exploration en largeur d’abord :

Niveau de performance :
 Complétude : complète
 Optimalité : le nœud n’est pas nécessairement le nœud optimal
 Complexité en temps : O(bd)
 Complexité en espace : O(bd)

Exploration en profondeur d’abord :

Le code est la même comme que l’exploration en largeur sauf sa frontière est une pile LIFO au lieu
d’un file FIFO.

Niveau de performance :
 Complétude : complète
 Optimalité : le nœud n’est pas nécessairement le nœud optimal
 Complexité en temps : O(bm)
 Complexité en espace : O(bm)

Exploration en profondeur limitée :

Parfois, à partir de la connaissance du problème, on peut connaitre au préalable de déterminer la
limite de profondeur de la nœud but.

Niveau de performance :
mi : est la limite de profondeur estimée selon le problème et n’est pas la limitée réelle du problème.

 Complétude : complète
 Optimalité : le nœud n’est pas nécessairement le nœud optimal
 Complexité en temps : O(bmi)
 Complexité en espace : O(bmi)

Exploration en itérative en profondeur :

Niveau de performance :
 Complétude : complète
 Optimalité : le nœud n’est pas nécessairement le nœud optimal
 Complexité en temps : O(bd)
 Complexité en espace : O(bd)

Exploration à cout uniforme :

Niveau de performance :
C* : est le cout de la solution optimale et on suppose que le cout au minimum de chaque
action est ɛ.
 Complétude : complète pourvu que le cout de chaque étape dépasse une petite
constante positive ɛ.
 Optimalité : Optimal
Complexité en temps : O ( b1 +[ c ∕ ε ] )
¿

Complexité en espace : O ( b1 +[ c ∕ ε]
)
¿

informée :

Son implémentation est identique à celle pour l’exploration à cout uniforme,

hormis l’utilisation de f au lieu de g pour ordonner la file de priorité.
f est déterminé selon la stratégie d’exploration, mais pour la plupart des
algorithmes par le meilleur d’abord, on incluent un fontion heuristique notée
h(n) comme composante de f, qui est un cout estimé du chemin le moins
couteux de l’état au nœud n à un état but.
Exploration gloutonne par le meilleur d’abord :

Niveau de performance :
m : est le profondeur maximum de l’espace d’exploration
 Complétude : incomplète car l’heuristique peut suggérer de développer une
impasse et l’algorithme ne trouvera jamais de solution
 Optimalité : le nœud n’est pas nécessairement le nœud optimal
 Complexité en temps : O(bm)
 Complexité en espace : O(bm)

Exploration A* par le meilleur d’abord :

Niveau de performance :
m : est le profondeur maximum de l’espace d’exploration
 Complétude : complète si un nombre fini de nœuds dont le coût est inférieur ou
égal à C* (vraie si tous les coûts d’étape dépassent un certain ɛ>0 et
si b est fini tel que A* ne développe aucun nœud pour lequel
f(n) > C)*.

 Optimalité : optimal si ces 2 conditions sont vérifiés :

1. h(n) est admissible (= ne surestime jamais le coût pour
atteindre le but).
2. Consistance (ou parfois monotonie) : pour chaque nœud n et
chaque successeur n’ de n produit par n’importe quelle action a,
le coût estimé pour atteindre le but à partir n n’est pas supérieur
au coût de l’étape pour aller de n et n’ plus le coût estimé pour
atteindre le but à partir de n’ :

 Complexité en temps : O(bd) dans le pire cas et O(b*d) dans le meilleurs des cas.
 Complexité en espace : O(bd) (A* n’est pas pratique pour beaucoup de problèmes à grande
échelle.

Exploration heuristique à mémoire limitée - IDA*:

Niveau de performance :
m : est le profondeur maximum de l’espace d’exploration
 Complétude : complète.
 Optimalité : optimal
 Complexité en temps : O(bd) dans le pire cas et O(b*d) dans le meilleurs des cas.
 Complexité en espace : O(b*d)

Le choix entre IDA* et A* dépend fortement du problèmes.

Méthodes approchées (métaheuristiques) :
Métaheuristique est un algorithme d’optimisation visant à résoudre des problèmes d’optimisation
difficile pour lesquels on ne connait pas de méthode classique plus efficace.

Pour les méthodes précédents portait sur une (seule) catégorie de problèmes qui concernent les
environnements observables, déterministes et connus, où la solution est une séquence d’actions, où
seul importe est l’état solution, et non le cout du chemin pour l’atteindre.

Métaheuristiques d’exploration locale :

Problème du voyageur de commerce :

Etant donné n points (des villes ).

Les distances séparant chaque point

But : Trouver un chemin de longueur totale minimale qui passe exactement une fois par chaque
point et revienne au point de départ == cycle hamiltonien de longueur minimale de graphe de villes.

 Il s’agit d'un problème d’optimisation pour lequel on ne connait pas d’algorithme

permettant de trouver une solution exacte en temps polynomial raisonnable pour de
grandes instances (grand nombre de villes) du porblème.
 Graphe complet possédant n sommets tous reliés 2 à 2 par une arête.
 Pour N villes, le nombre de parcours possibles (graphe complet non orienté) est égal à
(N-1)!/2.
Plus proche voisin :
Exploration par escalade :
Il s’agit simplement d’une boucle qui se déplace continuellement dans le sens des valeurs croissantes
– autrement dit vers le haut, et elle s’arrête quand elle atteint un pic où aucun voisin n’a de valeur
supérieure.

La structure de données du nœud courant n’a besoin d’enregistrer que l’état et la valeur de la
fonction objectif.

Escalade ne regarde pas au-delà des voisins immédiats de l’état courant.

2-opt :
On qualifie parfois l’escalade d’exploration locale par gloutonne.

Incovénients :
L’escalade échoue souvent pour les raisons suivantes :

 Maxima locaux : il atteigne le voisinage d’un maximum local seront « attirés » vers le pic,
mais y resteront coincés, n’ayant nulle part ailleurs où aller.
 Plateaux : le coincage sur un plateau qui est région plate du paysage de l’espace des états
dans laquelle la fonction d’évaluation est plate, qui peut s’agir d’un maximum local plat,
auquel cas il n’y a plus rien à escalader, ou d’un plaier à partir duquel il est possible de
progresser.
 Crêtes : qui provoquent une séquence de maxima locaux dans lesquels l’exploration a
beaucoup de mal à naviguer.

Remarque : Ce serait une bonne idée de continuer de permettre un déplacement latéral dans l’espoir
que le plateau soit en réalité un palier, mais il convient d’être prudent, car si on autorise toujours des
mouvements latéraux quand il n’y a plus de progression possible, on obtiendra une boucle sans fin
(déplacement fini entre la gauche et la droite du plateau) chaque fois que l’algorithme atteindra un
maximum local plat qui ne sera pas un palier == c’est pour cela un remède courant développer à
imposer une limite au nombre de déplacements latéraux consécutifs permis.
Exploration par recuit simulé :
Elle est un algorithme de type qui combine escalade et parcours aléatoire afin d’obtenir à la fois
efficaité et complétude.

 Température intiale : correspond à cette expression

Tel que pinit = 0.5 et delta0moy = la moyenne des écarts absolues entre n (grand si possible)
aléatoire solution initiales f(S0) et voisins f(S0‘).
 Fonction de décroissance de température : Tk+1 = ɑTk où souvent 0.8 < ɑ < 1

 Critères d’arrêt : limite sur le temps – limite sur le nombre d’itérations sans amélioration de
la solution courante – température minimale.
 Réglages des paramètres : par expérience :
Algorithmes génétiques :
AG est un algorithme itératif de recherche globale dont le but est d’optimiser une fonction définie
par l’utilisateur appelée fonction d’adaptation (fonction cout ou fonction objectif ou fonction
d’adequation, où il travaille en parallèle sur une population de candidats, appelés individus ou
chromosomes, distribués sur tout l’espace de recherche pour atteindre cet objectif.

Chaque chromosome est constitué d’un ensemble d’éléments appelés caractéristiques ou gènes,
pouvant prendre plusieurs valeurs (allèles) appartenant à un alphabet non nécessairement
numérique.

Dans l’algorithme génétique de base, le chromosome est une chaine binaire, où l’objectif est de
chercher la combinaison optimale de ces éléments qui donne lieu au maximum d’adaptation.

Pour chaque génération (itération), crée une nouvelle population avec souvent le même nombre
d’individus.

Tel que chaque nouvelle population contient généralement des individus miuex adaptés à
l’environnement au fur et à mesure des générations, ainsi les individus tendent à se ressembler de
plus en plus.

Ses étapes fondamentales :

 Initialisation :
Commencer par une population aléatoire de manière la plus uniforme possible. ( on peut
prendre en compte certains types de connaissances a priori de l’utilisateur et possible
d’inclure dans la population initiale certains individus dans le cas lorsqu’on dispose déjà de
solutions qu’on désire améliorer).
 Evaluation avec ses 3 opérateurs :
Calculer les qualités des différents chromosomes composant une population par des
opérateurs d’évaluation qui permettent de modifier la composition génétique des individus
entre deux générations afin de parcourir l’espace de recherche, qui ont une double mission :
Permettre au processus génétique d’exploiter le voisinage des individus + Explorer d’autre
part les zones encore inconnues.

et des opérateurs d’évaluation de base sont :

- Séléction :
Elle est orientée vers l’exploitation seule, et permet de choisir quel(s) individu(s)
vont se reproduire en fonction des valeurs de la fonction objectif.
Elle consiste à donneraux individus ayant une adaptation plus grande de plus
grandes chances d’engendrer un ou plusieurs descendants.
Elle utilisela technique de sélection par roue de loterie = tirage aléatoire où
chaque individu se voit attribuer une place plus ou moins grande selon sa
performance tq on définit pour chaque individu Vi une probabilité de sélection
(ps(Vi) = taux de surface qui lui sera réservé sur la roue)
- Croisement (ou reproduction) :
Il utilise un opérateur qui permet de générer 2 individus enfants en faisant
croiser 2 individus parents, en cumulant leurs bons cotés par une probabilité
(taux de croisement) entre 0.6 et 1.

Le croisement des individus porches de 2 optima distincts conduit à obtenir des

individus hybrides qui sont souvent peu performants et ralentissent l’évolution.

- Mutation :
L’opérateur d’évolution le plus important du point de vue de l’exploration de
l’espace de recherche, qui permet d’accéder à tout l’espace de recherche.
Pratiquement, elle consiste à remplacer chaque bit de chaque individu par son
complémentaire avec une probabilité pm, appelée taux de mutation.

Où λ = taille de la population et l = longueur de la représentation génétique des

individus
  Stratégie de remplacement :
Construire nouvelle population à partir des parents et des enfants de la génération courante
par plusieur méthodes :
- Engendrer autant d’enfants qu’il y a de parents et tous les enfants remplacent
leurs parents à chaque génération = ‘’Stratégie est dite générationnelle’’.
- Conserver une proportion de parents qui sont remplacés par des enfants, d’une
façon stochastique ou selon la performance des individus.
- Chaque étape de sélection le meilleur chromosome est automatiquement
sélectionné = politique d’élitisme.

 Critère d’arrêt :
Puisque on ne sait jamais si l’on trouvé l’optimum.
- Déclarer un nombre de générations maximum, à compter du début de
l’évolution ou de la dernière amélioration trouvée.
- Stoppée lorsque tous les individus d’une meme population sont des copies d’un
meme individu (ou de quelques individus).

Adaptation au PVC :
Réseaux de neurones :

Le neurone formel sommateur est constitué de 2 opérateurs :

- Opérateur de sommation qui élabire un « potentiel » p égal à la somme
pondérée du neurone.

Où Wi sont les poids synaptiques,

p est la fonction d’entrée totale du neurone,
- Opérateur qui calcule l’état de sortie ‘’s’’ du neurone en fonction de son
potentiel p.

f la fonction d’activation du neurone (ou la fonction de neurone), qui définit le

comportement du neurone, et qui prend différentes formes selon l’utilisation du
réseau, et la nature continue ou discrète, voire binaire de l’état s du neurone.
Elle présente généralement un seuil, et elle peut être :

 Fonction linéaire (identité) : f(p) = p

 Fonction non linéaire (saturation) : se rapprochant de la caractéristique

entrée/sortie des neurones réels, décrite par un seuil θ, et une partie
linéaire à pente A, et une valeur de saturation :
f(p) = Min[Smax, Max(0,A.p)]

 Fonction signe : f(p) = Sign(p - θ)

 Fonction échelon : f(p) = U(p - θ)

  Fonction sigmoïde = tangente hyperbolique avec des valeurs comprises
entre -1 et +1 :

ou avec des valeurs coomprises entre 0 et +1 :

 Réseaux entièrement connectés (ou bouclés) : Chaque neurone est relié à tous
les autres et possède même un retour sur lui.
 Réseaux à couches (ou non bouclés) :
- Les neurones appartiennent à même couche ne sont pas connectés entre eux, et
chacune des couches recevant des signaux de la couche précédente et
transmettant le résultat de ses traitements à la couche suivante (pas de
connexion vers l’arrière).
- La première couche reçoit ses entrées du milieu extérieur d’une part,
- La dernière couche fournit le résultat des traitements effectués.

On distingue deux modèles :

Réseaux monocouches :
Elle est constituée d’une couche de neurones (de sortie) connectés à un ensemble d’entrées par
l’intermédiaire de connexions modifiables (poids) wik.

L’évolution du réseau se fait en parallèle, tq tous les neurones calculent, en même temps, la somme
des entrées pondérées par des coefficients (poids) et déterminent leur sortie, où ces coefficients sont
déterminés par un apprentissage qui consiste à les calculer à l’aide d’un algorithme approprié, à
partir d’un ensemble de forme à apprendre

A chaque pas d’apprentissage l’erreur quadratique E à minimiser est pour un seul neurone :

E = (p – pd)2
Rétro – propagation du gradient :
Qui permet modifier les poids selon la contribution de chaque poids dans l’erreur globale du réseau.

1. Propagation de l’entrée jusqu’à la sortie.

2. Calcul de l’erreur en sortie.
3. Rétropropagation de l’erreur jusqu’aux entrées

Rq : il faut une fonction d’activation dérivable car on a besoin du dérivé pour rétro - propager l’erreur

Les poids sont modifiés selon la règle suivante :

Pour Perceptron :

Limites :
 - Il n’est possible de résoudre que des problèmes linéairement séparables.

Pour un apprentissage efficace, il faut que le seuil θ puisse être ajusté.

Si pour cela en pratique, chaque neurone avec un seuil θ est remplacé par un neurone ayant un seuil
nul mais possédant un poids W0 supplémentaire de valeur -θ relié à une entrée constante égale à 1.

Réseaux multicouches :

 Avec 2 neurones (dans la 1ère couche) : On définit 2 droits séparatrices qui sépare le plan en
2 régions dont la frontière est constituée par 2 segments droite (les droites séparatrices de
chaque neurones) et définit 4 frontières différentes.
 Avec 3 neurones (dans la 1ère couche) : On définit 3 droits séparatrices qui sépare le plan en
2 régions dont la frontière est constituée par 3 segments droite (les droites séparatrices de
chaque neurones).
Ce qui permet d’augmenter la résolution de la frontière entre les 2 classes. Cependant, les
régions définies par cette frontière restent convexes.
 Avec 3 couches de neurones : il devient possible de séparer des classes mêmes non
convexes car on peut décomposer en deux sous-réseaux de 2 couches en sélectionnant
chacun une région de plan à partir de 3 droites séparatrices associés aux 3 neurones de 1ère
couche. A partir des décisions de ces sous-réseaux la neurone de la couche de sortie effectue
une décision de synthèse
Constituée :

 Couche d’entrée : reçoit les informations provenant de l’extérieur

 Une ou plusieurs couches intermédiaires (couches cachées) : chacune reçoit des signaux de
la couche précédente et transmettent les résultats de ses traitements à la couche suivante.
 Couche sortie : présente les résultats définitifs de traitements.
 Chaque neurone est connecté à l’ensemble des neurones de la couche suivante par des
connexions dont les poids sont des nombres réels quelconques.
 Il n’y a pas de connexions à l’intérieur d’une même couche.
Valeurs initiales des poids :
 Les poids et seuils doivent être différentes de zéro pour ne rester pas toujours nul au cours
de l’apprentissage.
 Ils doivent être choisit aléatoirement dans [-M1,+M2] où le choix de M1 et M2 dépend de
la dynamique des signaux d’entrée.
 Pour conserver une vitesse de convergence acceptable, on choisit les poids initiaux en
fonction des entrées.

Choix du pas d’adaptation :

 Le pas d’adaptation doit s’ajuster avec soin après chaque passage de la base
d’apprentissage complète afin d’avoir une décroissance régulière de l’erreur quadratique
moyenne et non pas des paramètres pour par la suite avoir une vitesse de convergence
suffisante, sans toutefois entrainer de risque d’instabilité de l’algorithme.

Test d’arrêt :
 On cherche à arrêter l’algorithme si l’erreur E est minimale (inférieure à un seuil fixé)
 Ou fixer un nombre d’itérations mais moins performant.
 Pratiquement il faut calculer un indice de convergence.