AI - Algorithmes de recherche populaires

La recherche est la technique universelle de résolution de problèmes en IA. Il existe des jeux solo tels que les jeux de tuiles, le Sudoku, les mots croisés, etc. Les algorithmes de recherche vous aident à rechercher une position particulière dans de tels jeux.

Problèmes de recherche de chemin d'agent unique

Les jeux tels que les puzzles 3X3 à huit tuiles, 4X4 à 15 tuiles et 5X5 à 24 tuiles sont des défis de recherche de chemin à agent unique. Ils se composent d'une matrice de tuiles avec une tuile vierge. Le joueur doit disposer les tuiles en faisant glisser une tuile verticalement ou horizontalement dans un espace vide dans le but d'atteindre un objectif.

Les autres exemples de problèmes de recherche de chemin d'agent unique sont le problème du vendeur itinérant, le Rubik's Cube et la vérification du théorème.

Rechercher la terminologie

  • Problem Space- C'est l'environnement dans lequel la recherche a lieu. (Un ensemble d'états et un ensemble d'opérateurs pour changer ces états)

  • Problem Instance - C'est l'état initial + l'état de l'objectif.

  • Problem Space Graph- Il représente l'état du problème. Les états sont représentés par des nœuds et les opérateurs par des arêtes.

  • Depth of a problem - Longueur du chemin le plus court ou de la séquence d'opérateurs la plus courte de l'état initial à l'état cible.

  • Space Complexity - Le nombre maximum de nœuds stockés en mémoire.

  • Time Complexity - Le nombre maximum de nœuds créés.

  • Admissibility - Une propriété d'un algorithme pour toujours trouver une solution optimale.

  • Branching Factor - Le nombre moyen de nœuds enfants dans le graphe d'espace de problème.

  • Depth - Longueur du chemin le plus court de l'état initial à l'état d'objectif.

Stratégies de recherche Brute-Force

Ils sont les plus simples, car ils ne nécessitent aucune connaissance spécifique au domaine. Ils fonctionnent bien avec un petit nombre d'états possibles.

Exigences -

  • Description de l'état
  • Un ensemble d'opérateurs valides
  • Etat initial
  • Description de l'état de l'objectif

Recherche en largeur d'abord

Il part du nœud racine, explore d'abord les nœuds voisins et se déplace vers les voisins de niveau suivant. Il génère un arbre à la fois jusqu'à ce que la solution soit trouvée. Il peut être implémenté en utilisant la structure de données de file d'attente FIFO. Cette méthode fournit le chemin le plus court vers la solution.

Si branching factor(nombre moyen de nœuds enfants pour un nœud donné) = b et profondeur = d, puis nombre de nœuds au niveau d = b d .

Le nombre total de nœuds créés dans le pire des cas est b + b 2 + b 3 +… + b d .

Disadvantage- Étant donné que chaque niveau de nœuds est enregistré pour en créer le suivant, il consomme beaucoup d'espace mémoire. L'espace requis pour stocker les nœuds est exponentiel.

Sa complexité dépend du nombre de nœuds. Il peut vérifier les nœuds en double.

Recherche en profondeur d'abord

Il est implémenté en récursivité avec la structure de données de la pile LIFO. Elle crée le même ensemble de nœuds que la méthode Breadth-First, uniquement dans un ordre différent.

Comme les nœuds sur le chemin unique sont stockés à chaque itération de la racine au nœud feuille, l'espace requis pour stocker les nœuds est linéaire. Avec un facteur de branchement b et une profondeur égale à m , l'espace de stockage est bm.

Disadvantage- Cet algorithme peut ne pas se terminer et continuer indéfiniment sur un chemin. La solution à ce problème est de choisir une profondeur de coupure. Si le seuil idéal est d , et si le seuil choisi est inférieur à d , cet algorithme peut échouer. Si le seuil choisi est supérieur à d , le temps d'exécution augmente.

Sa complexité dépend du nombre de chemins. Il ne peut pas vérifier les nœuds en double.

Recherche bidirectionnelle

Il recherche en avant depuis l'état initial et en arrière depuis l'état de l'objectif jusqu'à ce que les deux se rencontrent pour identifier un état commun.

Le chemin depuis l'état initial est concaténé avec le chemin inverse depuis l'état cible. Chaque recherche n'est effectuée que jusqu'à la moitié du chemin total.

Recherche de coût uniforme

Le tri se fait en augmentant le coût du chemin vers un nœud. Il étend toujours le nœud le moins coûteux. Elle est identique à la recherche Breadth First si chaque transition a le même coût.

Il explore les chemins par ordre croissant de coût.

Disadvantage- Il peut y avoir plusieurs longs chemins avec le coût ≤ C *. La recherche de coût uniforme doit tous les explorer.

Recherche itérative en profondeur d'approfondissement d'abord

Il effectue une recherche en profondeur d'abord jusqu'au niveau 1, recommence, exécute une recherche complète en profondeur d'abord jusqu'au niveau 2 et continue de cette manière jusqu'à ce que la solution soit trouvée.

Il ne crée jamais de nœud tant que tous les nœuds inférieurs ne sont pas générés. Il enregistre uniquement une pile de nœuds. L'algorithme se termine lorsqu'il trouve une solution à la profondeur d . Le nombre de nœuds créés à la profondeur d est b d et à la profondeur d-1 est b d-1.

Comparaison de diverses complexités d'algorithmes

Voyons les performances des algorithmes basés sur différents critères -

Critère La largeur d'abord Profondeur d'abord Bidirectionnel Coût uniforme Approfondissement interactif
Temps b d b m b j / 2 b d b d
Espace b d b m b j / 2 b d b d
Optimalité Oui Non Oui Oui Oui
Complétude Oui Non Oui Oui Oui

Stratégies de recherche informées (heuristiques)

Pour résoudre de gros problèmes avec un grand nombre d'états possibles, des connaissances spécifiques au problème doivent être ajoutées pour augmenter l'efficacité des algorithmes de recherche.

Fonctions d'évaluation heuristique

Ils calculent le coût du chemin optimal entre deux états. Une fonction heuristique pour les jeux de tuiles coulissantes est calculée en comptant le nombre de mouvements que chaque tuile effectue à partir de son état de but et en ajoutant ce nombre de mouvements pour toutes les tuiles.

Recherche purement heuristique

Il développe les nœuds dans l'ordre de leurs valeurs heuristiques. Il crée deux listes, une liste fermée pour les nœuds déjà développés et une liste ouverte pour les nœuds créés mais non développés.

À chaque itération, un nœud avec une valeur heuristique minimale est développé, tous ses nœuds enfants sont créés et placés dans la liste fermée. Ensuite, la fonction heuristique est appliquée aux nœuds enfants et ils sont placés dans la liste ouverte en fonction de leur valeur heuristique. Les chemins les plus courts sont enregistrés et les plus longs sont supprimés.

Une recherche

C'est la forme la plus connue de la meilleure première recherche. Cela évite d'étendre les chemins déjà coûteux, mais élargit d'abord les chemins les plus prometteurs.

f (n) = g (n) + h (n), où

  • g (n) le coût (jusqu'ici) pour atteindre le nœud
  • h (n) coût estimé pour aller du nœud au but
  • f (n) coût total estimé du chemin passant par n jusqu'à l'objectif. Il est implémenté en utilisant la file d'attente prioritaire en augmentant f (n).

Première recherche gourmande

Il étend le nœud estimé le plus proche de l'objectif. Il développe les nœuds en fonction de f (n) = h (n). Il est implémenté en utilisant la file d'attente prioritaire.

Disadvantage- Il peut rester coincé dans des boucles. Ce n'est pas optimal.

Algorithmes de recherche locale

Ils partent d'une solution prospective et passent ensuite à une solution voisine. Ils peuvent renvoyer une solution valide même si elle est interrompue à tout moment avant la fin.

Recherche d'escalade

C'est un algorithme itératif qui commence par une solution arbitraire à un problème et tente de trouver une meilleure solution en modifiant un élément unique de la solution de manière incrémentielle. Si le changement produit une meilleure solution, un changement incrémentiel est considéré comme une nouvelle solution. Ce processus est répété jusqu'à ce qu'il n'y ait plus d'améliorations.

function Hill-Climbing (problème), retourne un état qui est un maximum local.

inputs: problem, a problem
local variables: current, a node
                 neighbor, a node
current <-Make_Node(Initial-State[problem])
loop
   do neighbor <- a highest_valued successor of current
      if Value[neighbor] ≤ Value[current] then
      return State[current]
      current <- neighbor				  
	
end

Disadvantage - Cet algorithme n'est ni complet, ni optimal.

Recherche de faisceau local

Dans cet algorithme, il contient k nombre d'états à un instant donné. Au début, ces états sont générés aléatoirement. Les successeurs de ces k états sont calculés à l'aide de la fonction objectif. Si l'un de ces successeurs est la valeur maximale de la fonction objectif, alors l'algorithme s'arrête.

Sinon, les (k états initiaux et k nombre de successeurs des états = 2k) états sont placés dans un pool. Le pool est ensuite trié numériquement. Les k états les plus élevés sont sélectionnés comme nouveaux états initiaux. Ce processus se poursuit jusqu'à ce qu'une valeur maximale soit atteinte.

function BeamSearch ( problem, k ), retourne un état de solution.

start with k randomly generated states
loop
   generate all successors of all k states
   if any of the states = solution, then return the state
   else select the k best successors
end

Recuit simulé

Le recuit est le processus de chauffage et de refroidissement d'un métal pour changer sa structure interne afin de modifier ses propriétés physiques. Lorsque le métal refroidit, sa nouvelle structure est saisie et le métal conserve ses propriétés nouvellement obtenues. Dans le processus de recuit simulé, la température est maintenue variable.

Nous avons initialement réglé la température élevée, puis nous l'avons laissée «refroidir» lentement au fur et à mesure que l'algorithme avance. Lorsque la température est élevée, l'algorithme est autorisé à accepter les pires solutions à haute fréquence.

Début

  • Initialiser k = 0; L = nombre entier de variables;
  • À partir de i → j, recherchez la différence de performance Δ.
  • Si Δ <= 0 alors accepter autrement si exp (-Δ / T (k))> aléatoire (0,1) alors accepter;
  • Répétez les étapes 1 et 2 pour les étapes L (k).
  • k = k + 1;

Répétez les étapes 1 à 4 jusqu'à ce que les critères soient remplis.

Fin

Problème de vendeur itinérant

Dans cet algorithme, l'objectif est de trouver un circuit à faible coût qui part d'une ville, visite toutes les villes en route exactement une fois et se termine dans la même ville de départ.

Start
   Find out all (n -1)! Possible solutions, where n is the total number of cities.
   Determine the minimum cost by finding out the cost of each of these (n -1)! solutions.
   Finally, keep the one with the minimum cost.
end