Tout sur la recherche informée dans l'intelligence artificielle

La recherche informée est un type d'algorithme de recherche qui utilise des connaissances spécifiques à un domaine pour guider sa recherche dans un espace de problèmes. Des systèmes de navigation aux jeux, du traitement du langage naturel à la gestion de la chaîne d'approvisionnement et à la recherche plus éclairée dans l'intelligence artificielle, a considérablement réduit le temps et les ressources informatiques nécessaires pour résoudre différents problèmes.

En utilisant des connaissances spécifiques au domaine pour guider la recherche, des algorithmes de recherche informés peuvent rapidement éliminer les chemins non pertinents ou moins prometteurs, permettant à la recherche de se concentrer sur les options les plus prometteuses. Pour ce faire, ces types d'algorithmes de recherche en IA utilisent des heuristiques pour améliorer l'efficacité et la rapidité de la recherche.

Inscrivez-vous au cours d'apprentissage automatique des meilleures universités du monde. Gagnez des programmes Master, Executive PGP ou Advanced Certificate pour accélérer votre carrière.

Cet article abordera le concept de recherche informée en intelligence artificielle, ses fonctions heuristiques, des exemples d'algorithmes, ainsi que leurs avantages et inconvénients.

Fonction heuristique

En termes simples, une fonction heuristique est une approche de résolution de problèmes qui utilise une règle empirique ou une « meilleure estimation » pour estimer la distance ou le coût par rapport à un état cible dans un problème de recherche. La fonction heuristique estime à quelle distance l'état d'objectif est de l'état actuel, ce qui peut être utilisé pour guider un algorithme de recherche vers l'objectif.

Les algorithmes de recherche informés utilisent ces fonctions comme source d'informations supplémentaire pour prendre des décisions éclairées sur le chemin à emprunter. Pour cette raison, les fonctions heuristiques sont essentielles dans les algorithmes de recherche informés.

Exemples concrets de fonction heuristique

Pour mieux comprendre les fonctions heuristiques, voici quelques exemples concrets :

• Dans le jeu classique du "puzzle à tuiles coulissantes", une simple fonction heuristique pourrait être de compter le nombre de tuiles déplacées dans la configuration actuelle par rapport à la configuration de l'objectif. Plus il y a de tuiles déplacées, plus l'état actuel est éloigné de l'état d'objectif.
• Aux échecs, une fonction heuristique pourrait être d'attribuer une valeur à chaque pièce sur le plateau en fonction de sa force et de sa position relatives et d'utiliser la somme de ces valeurs pour estimer l'avantage ou le désavantage du joueur actuel. Cette fonction heuristique peut être utilisée pour guider un algorithme de recherche vers des déplacements susceptibles d'aboutir à une meilleure position.

Ceci étant réglé, allons maintenant de l'avant et comprenons certains des exemples les plus utilisés d'algorithmes de recherche informés en intelligence artificielle.

Exemples d'algorithmes de recherche informés

Deux des algorithmes de recherche informés les plus couramment utilisés sont la meilleure première recherche et la recherche A*. Comprenons ces deux algorithmes ainsi que quelques exemples, avantages, inconvénients et leur implémentation Python :

1. Meilleure première recherche

La meilleure première recherche est un algorithme de recherche qui développe d'abord le nœud le plus prometteur, selon une fonction heuristique. L'algorithme commence au nœud initial et examine tous ses nœuds enfants, en choisissant l'enfant avec la valeur heuristique la plus faible comme prochain nœud à explorer. Ce processus se poursuit jusqu'à ce que le nœud cible soit trouvé ou que tous les nœuds aient été explorés.

Meilleure première recherche – un exemple illustré

Voici un exemple simple pour illustrer la meilleure première recherche :

Supposons que vous essayez de trouver le chemin le plus court entre votre domicile et une épicerie à proximité. Vous connaissez la distance jusqu'à l'épicerie à partir de quelques endroits à proximité, mais vous ne connaissez pas l'itinéraire exact à suivre. Pour résoudre ce problème à l'aide de la meilleure recherche en premier, vous pouvez :

1. Commencez à votre domicile et calculez la valeur heuristique de chaque emplacement à proximité en fonction de sa distance par rapport à l'épicerie.
2. Choisissez l'emplacement à proximité avec la valeur heuristique la plus faible comme prochain nœud à explorer.
3. Calculez la valeur heuristique pour chacun des emplacements de ses enfants à partir de cet emplacement à proximité et choisissez celui qui a la valeur heuristique la plus faible comme prochain nœud à explorer.
4. Répétez ce processus jusqu'à ce que vous atteigniez l'épicerie.

Meilleure première recherche – Implémentation Python

Voici comment implémenter le meilleur algorithme de première recherche en Python :

importer heapq

def best_first_search(start_state, goal_state, heuristic_func, actions_func, cost_func):

# initialise la frontière et l'ensemble exploré

frontière = [(heuristic_func(start_state, goal_state), start_state)]

exploré = set()

# initialise le chemin et le coût

chemin = {}

coût = {}

chemin[start_state] = Aucun

coût[start_state] = 0

tandis que frontière:

# obtenir le nœud avec la valeur heuristique la plus faible de la frontière

(h, état_actuel) = heapq.heappop(frontière)

si état_courant == état_objectif :

# renvoie le chemin si l'état du but est atteint

chemin de retour

exploré.add(état_actuel)

# générer des actions possibles à partir de l'état actuel

pour l'action dans actions_func(current_state):

état_suivant = action (état_actuel)

# calculer le coût du nouveau chemin

new_cost = cost[current_state] + cost_func(current_state, action, next_state)

if next_state not in explored and next_state not in [state for (h, state) in frontier] :

# ajouter le nouvel état à la frontière

heapq.heappush(frontière, (heuristic_func(next_state, goal_state), next_state))

chemin[prochain_état] = état_actuel

coût[next_state] = nouveau_coût

# renvoie Aucun si l'état du but n'est pas atteignable

retour Aucun

Comme vous pouvez le voir, vous devrez définir les fonctions suivantes :

• heuristic_func(current_state, goal_state) : cette fonction prend l'état actuel et l'état d'objectif comme entrées et renvoie une estimation du coût pour atteindre l'état d'objectif à partir de l'état actuel.
• actions_func(current_state) : cette fonction prend l'état actuel en entrée et renvoie une liste d'actions pouvant être effectuées à partir de l'état actuel.
• cost_func(current_state, action, next_state) : cette fonction prend l'état actuel, une action et l'état suivant comme entrées et renvoie le coût de l'action de l'état actuel à l'état suivant.

Exemple de meilleure première recherche

état_début = (0, 0)

état_but = (4, 4)

def heuristic_func(current_state, goal_state):

retourner abs(état_actuel[0] – état_objectif[0]) + abs(état_actuel[1] – état_objectif[1])

def actions_func(état_actuel):

gestes = []

si état_courant[0] > 0 :

actions.append(état lambda : (état[0]-1, état[1]))

si état_courant[0] < 4 :

actions.append(état lambda : (état[0]+1, état[1]))

si état_courant[1] > 0 :

actions.append(état lambda : (état[0], état[1]-1))

si état_courant[1] < 4 :

actions.append(état lambda : (état[0], état[1]+1))

actions de retour

def cost_func(état_actuel, action, état_suivant) :

retour 1

path = best_first_search(start_state, goal_state, heuristic_func, actions_func, cost_func)

si chemin :

# construire le chemin de l'état de départ à l'état d'arrivée

état_actuel = état_objectif

tandis que current_state != start_state :

imprimer (état_actuel)

état_actuel = chemin[état_actuel]

impression (état_début)

autre:

print("L'état de l'objectif n'est pas accessible.")

Avantages de la meilleure première recherche

• Par rapport à la recherche en largeur d'abord, la complexité temporelle de la recherche en premier est plus faible.
• La meilleure première recherche obtient et implémente les avantages des algorithmes BFS et DFS

Inconvénients de la meilleure première recherche

• Il peut parfois couvrir plus de distance que prévu.
• Les chances de rester coincé dans une boucle sont très probables.

Une recherche

Une recherche* est un algorithme de recherche qui utilise à la fois le coût pour atteindre un nœud à partir du nœud de départ et une estimation du coût restant pour atteindre le nœud cible pour guider sa recherche. L'algorithme commence au nœud initial et examine tous ses nœuds enfants, en choisissant l'enfant avec le coût combiné le plus bas et le coût restant estimé comme prochain nœud à explorer. Ce processus se poursuit jusqu'à ce que le nœud cible soit trouvé ou que tous les nœuds aient été explorés.

Recherche A* – un exemple illustré

Reprenons l'exemple précédent où vous essayez de trouver le chemin le plus court entre votre domicile et une épicerie à proximité. Maintenant, vous pourriez :

1. Commencez par votre domicile et calculez le coût total pour atteindre chaque emplacement à proximité comme la somme de la distance entre votre domicile et cet emplacement et le coût restant estimé pour atteindre l'épicerie à partir de cet emplacement.
2. Choisissez l'emplacement à proximité avec le coût total le plus bas comme prochain nœud à explorer.
3. À partir de cet emplacement à proximité, calculez le coût total pour chacun de ses emplacements enfants comme la somme de la distance entre cet emplacement et l'emplacement enfant, le coût pour atteindre cet emplacement à partir du nœud de départ et le coût restant estimé pour atteindre l'épicerie. à partir de cet emplacement enfant. Choisissez l'emplacement enfant avec le coût total le plus bas comme prochain nœud à explorer.
4. Répétez ce processus jusqu'à ce que vous atteigniez l'épicerie.

Une chose importante à noter ici est que A * Search est un algorithme de recherche optimal qui garantit de trouver le chemin le plus court vers l'état cible. Il est efficace dans les problèmes avec un grand espace de recherche et est largement utilisé dans les jeux vidéo, la robotique et la planification d'itinéraire. Cependant, il nécessite une fonction heuristique bien définie pour être efficace. Pour cette raison, l'algorithme peut être gourmand en mémoire et ralentir dans des problèmes complexes avec de nombreux nœuds.

Recherche A* – Implémentation Python

Voici comment implémenter l'algorithme de recherche A* en utilisant la programmation Python :

importer heapq

def astar_search(start_state, goal_state, heuristic_func, actions_func, cost_func):

# initialise la frontière et l'ensemble exploré

frontière = [(heuristic_func(start_state, goal_state), start_state)]

exploré = set()

# initialise le chemin et le coût

chemin = {}

coût = {}

chemin[start_state] = Aucun

coût[start_state] = 0

tandis que frontière:

# obtenir le nœud avec la valeur f la plus basse à partir de la frontière

(f, état_actuel) = heapq.heappop(frontière)

si état_courant == état_objectif :

# renvoie le chemin si l'état du but est atteint

chemin de retour

exploré.add(état_actuel)

# générer des actions possibles à partir de l'état actuel

pour l'action dans actions_func(current_state):

état_suivant = action (état_actuel)

# calculer le coût du nouveau chemin

new_cost = cost[current_state] + cost_func(current_state, action, next_state)

if next_state not in explored and next_state not in [state for (f, state) in frontier] :

# ajouter le nouvel état à la frontière

heapq.heappush(frontière, (new_cost + heuristic_func(next_state, goal_state), next_state))

chemin[prochain_état] = état_actuel

coût[next_state] = nouveau_coût

elif next_state in [state for (f, state) in frontier] et new_cost < cost[next_state] :

# mettre à jour le coût de l'état existant à la frontière

index = [i for (i, (f, state)) in enumerate(frontier) if state == next_state][0]

frontière[index] = (new_cost + heuristic_func(next_state, goal_state), next_state)

chemin[prochain_état] = état_actuel

coût[next_state] = nouveau_coût

# renvoie Aucun si l'état du but n'est pas atteignable

retour Aucun

Meilleurs cours d'apprentissage automatique et cours d'IA en ligne

Exemple de recherche A*

Voici un exemple d'utilisation de la fonction astar_search avec ces fonctions :

état_début = (0, 0)

état_but = (4, 4)

def heuristic_func(current_state, goal_state):

retourner abs(état_actuel[0] – état_objectif[0]) + abs(état_actuel[1] – état_objectif[1])

def actions_func(état_actuel):

gestes = []

si état_courant[0] > 0 :

actions.append(état lambda : (état[0]-1, état[1]))

si état_courant[0] < 4 :

actions.append(état lambda : (état[0]+1, état[1]))

si état_courant[1] > 0 :

actions.append(état lambda : (état[0], état[1]-1))

si état_courant[1] < 4 :

actions.append(état lambda : (état[0], état[1]+1))

actions de retour

def cost_func(état_actuel, action, état_suivant) :

retour 1

path = astar_search(start_state, goal_state, heuristic_func, actions_func, cost_func)

si chemin :

# construire le chemin de l'état de départ à l'état d'arrivée

état_actuel = état_objectif

tandis que current_state != start_state :

imprimer (état_actuel)

état_actuel = chemin[état_actuel]

impression (état_début)

autre:

print("L'état de l'objectif n'est pas accessible.")

Avantages de la recherche A*

• C'est l'une des principales techniques heuristiques.
• La recherche A* peut être utilisée pour résoudre des problèmes de recherche complexes

Compétences d'apprentissage automatique à la mode

Inconvénients de la recherche A*

• Les performances de recherche A* dépendent fortement de la précision des algorithmes heuristiques.
• A une faible efficacité de recherche.

Blogs et cours gratuits populaires sur l'IA et le ML

Emporter

Les algorithmes de recherche informés sont essentiels en intelligence artificielle car ils permettent à l'ordinateur de rechercher un état d'objectif de manière efficace et efficiente. Ces algorithmes utilisent des fonctions heuristiques pour estimer le coût de chaque mouvement possible et guider le processus de recherche vers l'état cible. Best First Search et A* Search sont des exemples d'algorithmes de recherche informés largement utilisés dans divers domaines. Cependant, une fonction heuristique bien définie est essentielle au succès des algorithmes de recherche informés.

Si vous souhaitez en savoir plus sur l'intelligence artificielle et l'apprentissage automatique, consultez le programme de maîtrise en apprentissage automatique et en intelligence artificielle d'upGrad proposé par l'Université John Moores de Liverpool . Ce programme couvre divers sujets d'apprentissage automatique et d'IA, y compris des algorithmes comme la recherche informée. En suivant ce programme, vous pouvez acquérir les compétences et les connaissances dont vous avez besoin pour réussir dans une variété de carrières liées à l'IA.

Vous pouvez également consulter noscours gratuitsproposés par upGrad en gestion, science des données, apprentissage automatique, marketing numérique et technologie.Tous ces cours ont des ressources d'apprentissage de premier ordre, des conférences hebdomadaires en direct, des missions dans l'industrie et un certificat de fin de cours - le tout gratuitement !