Chapitre 2 IA et Machine Learning (Partie 1) 2024-2025 PDF

23/10/2024 Université de Gabes Institut Supérieur D’informatique et Multimédia de Gabes IA et Machine Learning Chapitre II Algorithmes de Recherche pour la Résolution de Problèmes (Part I) Enseignante: Ines NJEH CHAKER Fi...

23/10/2024 Université de Gabes Institut Supérieur D’informatique et Multimédia de Gabes IA et Machine Learning Chapitre II Algorithmes de Recherche pour la Résolution de Problèmes (Part I) Enseignante: Ines NJEH CHAKER Filière: LISI3 2024-2025 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Définition formelle d’un problème Un problème peut être défini par les cinq éléments : 1. un état initial 2. un ensemble d’actions 3. une fonction de successeur, qui définit l’état résultant de l’exécution d’une action dans un état 4. un ensemble d’états buts 5. une fonction de coût, associant à chaque action un nombre non-négative (le coût de l’action) 2  23/10/2024 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Nous pouvons voir un problème comme un graphe orienté ou les nœuds sont des états accessibles depuis l’état initial et où les arcs sont des actions. Nous appellerons ce graphe l’espace des états. Une solution sera un chemin de l’état initial à un état but. Une solution est dite optimale si la somme des coûts des actions du chemin est minimale parmi toutes les solutions du problème. Pour mieux comprendre, nous allons présenter, dans ce qui suit, quelques exemples concrets 3 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Exemple 1: jeu de taquin Nous commençons avec une grille 3×3 de neuf cases ou sont placées huit tuiles étiquetées par les nombres 1 à 8, une des cases restant vide. Une tuile située à côté de la case vide peut être déplacée vers cette case. L’objectif du jeu est d’arriver à obtenir une certaine configuration des tuiles dans la grille : remettre les nombres en ordre. 4  23/10/2024 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Exemple 1: jeu de taquin Formalisation du problème Etats: Ce sont les configurations des huit tuiles dans les neuf cases de la grille Etat initial : N’importe quel état pourrait être choisi comme l’état initial. 5 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Exemple 1: jeu de taquin Actions: Il y aura 3 actions possibles pour changer la position du carré vide : bas, gauche, droite Fonction de successeur: Cette fonction spécifie les états résultants des différentes actions. Actions Fonction de successeur 6  23/10/2024 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Exemple 1: jeu de taquin 7 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Exemple 1: jeu de taquin Test de but: L’état but est unique et fixé au début du jeu Coût des actions: Chaque déplacement d’une tuile a un coût de 1 ( essayer d’obtenir l’état final avec le moins de déplacements). Le taquin est souvent utilisé pour tester les algorithmes de recherche. Les algorithmes d’aujourd’hui arrivent à résoudre les taquins 3 ×3 et 4×4 ,mais les instances du taquin 5 × 5 restent difficiles. 8  23/10/2024 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Exemple 2: jeu des 8 reines Considérons une grille d’échiquier de 8x8. L’objectif de ce jeu est de placer huit reines sur l’échiquier tel qu’ aucune reine attaque une autre reine, c’est à dire qu’il n’y a pas deux reines sur la même colonne, la même ligne, ou sur la même diagonale. Etats: Toute configuration de 0 à 8 reines sur la grille Etat Initial : La grille est vide 9 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Exemple 2: jeu des 8 reines Actions: Ajouter une reine sur n’importe quelle case vide de la grille Fonction de successeur : La configuration qui résulte de l’ajout d’une reine à une case spécifié à la configuration courante. Test de but: Une configuration de huit reines avec aucune reine sous attaque. Coûts des actions : Ce pourrait être 0, ou un cout constant pour chaque action- nous nous intéressons pas du chemin, seulement l’état but obtenu 10  23/10/2024 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Exemple 2: jeu des 8 reines On peut réduire l’espace d’états drastiquement en observant qu’il est inutile de continuer de développer des configurations ou il y a déjà un conflit. On peut effectuer un changement à notre formalisme. Etat initial: Configurations de n reines (0 ≤ n ≤ 8), une reine par colonne dans les n colonnes plus à gauche, avec aucun conflit. Actions: Ajouter une reine à une case vide dans la colonne vide la plus à gauche afin d’éviter un conflit. Ces deux formalisations sont incrémentales car nous plaçons des reines une par une sur la grille nous ne tombons jamais dans un état déjà visité 11 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Exemple 2: jeu des 8 reines Une autre possibilité serait de commencer avec les huit reines sur la grille (une par colonne) et puis de changer la position d’une reine à chaque tour. Etats initiaux: Une configuration de 8 reines telle qu’il n’y a qu’une seule reine par colonne Etat initial : Un état choisi aléatoirement. Actions: Changer la position d’une reine dans sa colonne. Avec cette proposition, nous pouvons tombé dans un état déjà visité car nous pouvons changer la position d’une reine et après la remettre dans sa position d’origine  risque de tourner en boucle ou prendre le même chemin deux fois 12  23/10/2024 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Les deux problèmes traités dans l’exemple 1 et l’exemple 2 sont assez différents: Pour l’exemple 1 (le taquin), nous savons depuis le début quel état nous voulons, et la difficulté est de trouver une séquence d’actions pour l’atteindre  problème de planification Pour l’exemple 2 (huit reines), nous ne sommes pas intéressés au chemin mais seulement par l’état but obtenu problème de satisfaction de contraintes Les problèmes de planifications et les problèmes de satisfaction de contraintes sont deux grandes problèmes étudiés en Intelligence artificielle. Présentons maintenant la formalisation générale de ces deux problèmes: problème de planification et problème de satisfaction de contraintes 13 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Problème de planification Dans ce type de problème, nous cherchons une suites d’actions pour relier l’état initial à un état but (final). La formalisation standard du problème : Etats: Un ensemble d’états du monde qui correspondent aux différentes évaluations d’un ensemble de propositions. Par exemple, considérons un cas très simple avec une seule proposition allumée.Nous avons deux états du monde possibles : allumée=vrai et allumée=faux. 14  23/10/2024 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Problème de planification Etat initial : L’état actuel du monde: allumée=vrai Actions : Un ensemble d’actions autorisées Exp: actionner l′interrupteur Fonction de successeur: Cette fonction va nous dire quelles actions sont possibles dans chaque état du monde et comment les actions changent l’état du monde. Exp: l’action actionner l′interrupteur va faire passer de l’état allumée=vrai à l’état allumée=faux et inversement Test de but : Théoriquement, ça pourrait être n’importe quel ensemble d’états, mais souvent nous définissons le but comme l’ensemble des états satisfaisants une certaine évaluation partielle des propositions. 15 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Problème de planification Coût des actions: Pour essayer de trouver des plans les plus courts, nous pouvons mettre tous les coûts à 1. Nous pouvons aussi définir les coûts des actions en fonction de leur durée, de leur coût en argent, de la quantité de ressources qu’elles consomment, … Les problèmes de planification sont courants dans la vie de tous les jours. Par exemple, considérons le problème de trouver le chemin le plus court pour atteindre une destination. C’est un problème tellement courant qu’il y a maintenant des GPS dédiés à cette tâche. Citons également les systèmes de planification de voyage qui cherchent des itinéraires en transports en commun, en train ou en avion. 16  23/10/2024 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Satisfaction de contrainte Un problème de satisfaction de contraintes (CSP) consiste en un ensemble de variables, des ensembles de valeurs permises pour chaque variable, et un ensemble de contraintes. L’objectif est de trouver une solution telle que chaque contrainte est satisfaite. Voici une formalisation incrémentale d’un CSP : Etats: Des évaluations partielles (c’est à dire, des choix de valeurs pour un sous- ensemble des variables) Etat initial : La valuation est vide (ou nous n’avons pas encore choisi des va leurs) 17 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Satisfaction de contrainte Actions :Choisissez une valeur pour une des variables restantes. Fonction de successeur Nous ajoutons la nouvelle valeur à l’évaluation actuelle. Test de but: Un état but est une évaluation complète telle que chaque contrainte est satisfaite. Coût des actions: Cela peut dépendre du problème en question, mais en général nous devrons donner le même coût pour chaque action comme les solutions sont toutes aussi bonnes. 18  23/10/2024 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Satisfaction de contrainte Nous pouvons également donner une formalisation à partir des états complets : Etats :Une évaluation des variables. Etat initial: Une évaluation quelconque. Actions: Changez la valeur d’une variable. Gérer des pistes d’atterrissage à l’aéroport, trouver un plan de table pour un mariage, créer un emploi du temps à l’université.... ce sont tous des problèmes de satisfaction de contraintes. 19 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Dans tous ces problèmes considères jusqu’`a présent, il n’y avait qu’un seul agent qui pouvait choisir librement ses actions. Mais souvent nos décisions sont conditionnées par les actions des autres. C’est notamment le cas pour les jeux à plusieurs joueurs, que nous considérons maintenant. Jeux à plusieurs joueurs Ce type de problème est plus compliqué vu que l’agent ne peut pas choisir les actions des autres joueurs  Au lieu de chercher un chemin qui relie l’état initial à un état but, nous allons chercher une stratégie, c’est à dire un choix d’action pour chaque état où pourrait se trouver l’agent. 20  23/10/2024 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Voici une formalisation d’un jeu à plusieurs joueurs : Etats :Des configurations du jeu plus le nom de joueur dont c’est le tour Etat initial :La configuration initiale plus le nom du joueur qui commence. Actions :Les coups légaux pour le joueur dont c’est le tour. Fonction de successeur: La nouvelle configuration du jeu, et le nom de joueur dont c’est le tour. Test de but Les configurations gagnantes pour le joueur. Coût des actions Cela dépendra du jeu en question. 21 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Pour le jeu d’échecs, nous aurions la formalisation suivante : Etats :Des états sont compos´ es d’une configuration de l’échiquier plus le nom du joueur dont c’est le tour Etat initial :La configuration standard pour le début d’une partie d’échecs.. Actions :Ce sont des coups qui peuvent être joués par le joueur dont c’est le tour dans la configuration actuelle du jeu (y compris l’action d’abandonner le jeu). Fonction de successeur: La configuration du jeu évolue selon le coup choisi, et c’est maintenant à l’autre joueur de jouer. 22  23/10/2024 Introduction aux Algorithmes de Recherche pour la Résolution de Problèmes Test de but Il y a beaucoup de façons de terminer une partie, la plus connue étant l’échec et mat (je ne vais pas les détailler ici, ceux que cela intéresse pourront se documenter sur le sujet). Coût des actions Nous pouvons les mettre à1 pour chercher les coups qui amènent le plus vite `a une configuration gagnante. 23 Structure générale d’un algorithme de recherche La plupart des algorithmes de recherche suivent à peu près le même schéma : 24  23/10/2024 Structure générale d’un algorithme de recherche nous commençons toujours dans l’état initial et puis nous exécutons les étapes suivantes en boucle jusqu’à terminaison : – s’il n’y a plus d’états à traiter, renvoyez échec – sinon, choisir un des états à traiter (*) – si l’état est un état but, renvoyez la solution correspondante – sinon, supprimer cet état de l’ensemble des états à traiter, et le rem placer par ses états successeurs Ce qui va différencier les différents algorithmes est la manière dont on effectue le choix à l’étape (*) 25 Evaluations des algorithmes de recherches Comment nous pouvons comparer les algorithmes de recherches? Quatre critères pour comparer les différents algorithmes de recherche : Complexité en temps: Combien du temps prend l’algorithme pour trouver la solution? Complexité en espace: Combien de mémoire est utilisée lors de la recherche d’une solution? Complétude: Est-ce que l’algorithme trouve toujours une solution s’il y en a une? Optimalité: Est-ce que l’algorithme renvoie toujours des solutions optimales? 26