Mise en œuvre de l’algorithme Hill Climbing pour l’IA en Python

Tutoriels

Python

L’algorithme du hill climbing est l’un des algorithmes d’optimisation les plus anciens et les plus simples en intelligence artificielle et en informatique. Il appartient à une catégorie appelée algorithmes de recherche locale, qui trouvent des solutions en apportant des améliorations progressives.

Le nom de l’algorithme provient d’une analogie utile : imaginez un randonneur les yeux bandés essayant d’atteindre le sommet d’une colline. Comme il ne peut pas voir l’ensemble du paysage, il ne peut sentir que le sol immédiatement autour de lui. À chaque pas, il se déplace dans la direction qui monte. Cela reflète le fonctionnement de l’algorithme – il évalue les solutions proches et se déplace de manière itérative vers de meilleures solutions, en tentant de trouver la solution optimale (le sommet de la colline).

Dans cet article, nous explorerons en profondeur l’algorithme du montée de colline, ses variations, et comment vous pouvez l’implémenter en Python. Si vous êtes nouveau dans le domaine de l’IA, assurez-vous de consulter notre parcours de compétences Fondamentaux de l’IA pour couvrir les bases.

Qu’est-ce qu’un algorithme de montée de colline en IA?

La montée de colline est une manière simple pour les ordinateurs de résoudre des problèmes en trouvant la meilleure réponse possible, tout comme un randonneur essayant d’atteindre le sommet d’une montagne. En intelligence artificielle (IA), nous devons souvent trouver la meilleure solution parmi de nombreuses options possibles. Cela s’appelle l’optimisation.

Pensez à essayer de trouver le point le plus élevé en jouant à « chaud et froid ». Dans ce jeu, vous pouvez seulement vérifier si vous vous rapprochez (meilleur) ou vous vous éloignez (pire) en vous déplaçant. L’escalade de colline fonctionne de la même manière, elle regarde les solutions proches et se déplace vers les meilleures.

Voici comment cela fonctionne en quelques étapes simples :

Commencez avec n’importe quelle solution possible
Regardez les solutions proches
Si une solution proche est meilleure, déplacez-vous vers elle
Répétez les étapes 2 à 3 jusqu’à ce qu’aucune solution meilleure ne puisse être trouvée

Par exemple, si vous essayez d’enseigner à un robot à marcher, l’escalade de colline pourrait:

Commencer avec des mouvements de jambe aléatoires
Essayer des mouvements légèrement différents
Garder ceux qui aident le robot à mieux marcher
Répéter jusqu’à ce qu’il trouve le meilleur schéma de marche

Alors que l’escalade de colline n’est pas toujours la méthode la plus avancée en IA, c’est une pierre angulaire importante qui nous aide à comprendre comment les ordinateurs peuvent résoudre des problèmes par eux-mêmes, de manière similaire à l’algorithme minimax.

Types d’algorithmes d’escalade de colline

Il existe trois principaux types d’algorithmes d’escalade de colline, chacun avec sa propre manière de rechercher la meilleure solution :

1. Escalade de colline simple

L’escalade de colline simple consiste à prendre le premier bon pas que vous trouvez. Dans cette version :

L’algorithme examine les solutions proches une par une
Dès qu’il trouve une meilleure solution, il la prend
Il ne vérifie pas les autres options
C’est rapide mais cela pourrait manquer de meilleures solutions qui étaient juste un peu plus loin

2. Escalade de colline la plus raide

Cette version est plus approfondie que l’escalade simple de colline:

Elle examine TOUTES les solutions proches avant de faire un mouvement
Choisis la meilleure option parmi tout ce qu’il a trouvé
Prend plus de temps mais trouve généralement de meilleures solutions
C’est comme vérifier soigneusement chaque chemin avant de faire un pas

3. Escalade de colline stochastique

Ce type ajoute un peu de hasard pour rendre la recherche plus intéressante :

Au lieu de toujours choisir la meilleure solution, il sélectionne aléatoirement parmi les meilleures options
Les meilleures solutions ont plus de chances d’être choisies
Cette aléatoire aide à éviter de rester coincé dans des mauvaises situations
C’est comme parfois prendre un chemin différent juste pour voir où il mène

Chaque type a ses propres forces et fonctionne mieux pour différents types de problèmes. L’escalade de colline simple est rapide mais basique, la montée la plus raide est approfondie mais plus lente, et le stochastique ajoute une aléatoire utile pour éviter de rester bloqué.

Comment fonctionne l’algorithme de l’escalade de colline

L’algorithme de l’escalade de colline fonctionne en apportant de petites améliorations pas à pas jusqu’à ce qu’il trouve la meilleure solution possible. Décortiquons comment cela fonctionne en ses principales parties.

1. Commencer

Chaque algorithme de montée de colline a besoin d’un point de départ. Pensez à choisir où commencer une randonnée en montagne. Vous pourriez commencer au hasard, ou vous pourriez utiliser ce que vous savez sur le problème pour choisir un bon point de départ.

Où vous commencez a vraiment de l’importance – choisissez un bon endroit, et vous pourriez trouver la meilleure solution rapidement. Choisissez un mauvais endroit, et vous pourriez rester bloqué sur une petite colline au lieu de trouver le sommet de la montagne.

Par exemple, dans l’entraînement des réseaux neuronaux, le point de départ signifie choisir des poids initiaux pour les connexions entre les neurones. Vous pouvez initialiser ces poids de manière aléatoire, ce qui revient à commencer votre randonnée à un endroit aléatoire sur la montagne. Ou vous pourriez utiliser des techniques comme l’initialisation de Xavier qui choisissent des poids de départ intelligents en fonction de la structure du réseau.

Une bonne initialisation aide le réseau à apprendre plus rapidement et à trouver de meilleures solutions, tandis qu’une mauvaise initialisation pourrait laisser le réseau bloqué avec une faible précision qui ne s’améliore jamais.

2. Examiner les solutions voisines

Une fois que l’algorithme commence sa recherche, il évalue des solutions voisines qui sont similaires à la position actuelle. Pensez à explorer les environs immédiats en petits pas. Par exemple, si vous essayez d’optimiser un itinéraire de livraison entre des villes, et que votre itinéraire actuel est [A -> B -> C -> D], l’algorithme examinerait des itinéraires similaires tels que [A -> B -> D -> C] ou [A -> C -> B -> D] pour voir s’ils réduisent la distance totale parcourue. Chaque petit changement apporté à l’itinéraire représente une solution « voisine » qui pourrait potentiellement être meilleure que la solution actuelle.

Pour effectuer ces comparaisons, l’algorithme s’appuie sur ce qu’on appelle une fonction objective — une formule mathématique qui attribue un score ou une valeur à chaque solution possible.

Cette fonction agit comme une boussole, aidant l’algorithme à comprendre quelles directions mènent « en montée » vers de meilleures solutions et lesquelles mènent « en descente » vers des solutions moins bonnes. Pour un itinéraire de livraison, la fonction objectif calculerait la distance totale parcourue – une distance totale plus courte signifie une meilleure solution.

Donc, si l’itinéraire X fait 100 miles et l’itinéraire Z fait 90 miles, l’itinéraire B aurait un meilleur score (plus bas). L’algorithme saurait alors se déplacer dans la direction des solutions similaires à l’itinéraire B. La fonction objectif transforme essentiellement le problème complexe de l’optimisation d’itinéraire en un simple nombre qui peut être comparé et minimisé.

3. Choisir la prochaine étape

Après avoir examiné les solutions proches, l’algorithme doit décider où se déplacer ensuite. L’algorithme compare les scores des solutions proches à celle actuelle. S’il trouve une meilleure solution, il s’y déplace. Différentes versions de la montée des collines font ce choix de différentes manières :

La version simple prend la première meilleure solution qu’elle trouve
La version prudente vérifie toutes les solutions voisines avant de choisir la meilleure
La version aléatoire choisit parfois des solutions qui ne sont pas les meilleures, ce qui peut l’aider à éviter de rester bloquée

4. Savoir quand s’arrêter

L’algorithme doit savoir quand cesser de chercher de meilleures solutions. En général, il s’arrête lorsqu’une de ces choses se produit :

Il ne trouve pas de meilleures solutions à proximité
Il tourne depuis trop longtemps
On a trouvé une solution qui est assez bonne

Comme l’algorithme fonctionne, il suit généralement un schéma. Au début, il trouve rapidement de meilleures solutions, comme faire de grands pas sur une colline raide. Ensuite, il ralentit lorsqu’il se rapproche du sommet, apportant de plus petites améliorations jusqu’à ce qu’il s’arrête finalement.

Parfois, le chemin est facile et direct, mais d’autres fois, il peut être difficile avec beaucoup de hauts et de bas.

Avantages et Limitations de l’Escalade de Colline en IA

Regardons ce qui rend l’escalade de colline utile et les problèmes auxquels vous pourriez être confrontés lors de son utilisation.

Avantages

La montée en puissance est l’un des algorithmes d’optimisation les plus simples à comprendre et à programmer. C’est comme suivre une règle de base : « Si quelque chose est meilleur, allez-y ». Cela en fait un excellent point de départ pour résoudre de nombreux problèmes.

Lorsque le problème est simple, la montée en puissance peut trouver rapidement de bonnes solutions. Elle ne perd pas de temps à explorer toutes les solutions possibles, elle suit simplement le chemin vers le haut.

L’algorithme n’a pas besoin de beaucoup de mémoire informatique ou de puissance de traitement. Il doit simplement se souvenir où il se trouve et regarder les solutions voisines, ce qui le rend pratique pour de nombreux problèmes du monde réel.

Limitations

Bien sûr, comme pour toute méthode, il existe quelques inconvénients potentiels :

1. Se coincer sur de petites collines

Le plus grand problème avec l’escalade de colline est qu’elle peut rester bloquée sur ce que nous appelons des « maxima locaux » – ce sont comme de petites collines lorsqu’il y a en réalité une montagne à proximité. Une fois que l’algorithme atteint le sommet d’une petite colline, il s’arrête car tout autour est plus bas, même s’il pourrait y avoir de bien meilleures solutions ailleurs.

2. Le problème du terrain plat

Parfois, l’algorithme se retrouve sur un terrain plat (appelé plateau), où toutes les solutions proches sont également bonnes. Imaginez essayer de trouver le point le plus haut en marchant sur un terrain de football plat – il est difficile de savoir dans quelle direction aller!

3. Le problème de crête

Imaginez essayer de marcher le long du sommet d’une crête de montagne étroite. L’algorithme pourrait perdre du temps en zigzaguant de part et d’autre de la crête au lieu d’avancer vers le sommet. Cela se produit car chaque pas sur le côté semble aussi bon que de rester sur la bonne voie.

4. Le point de départ compte beaucoup

Où vous commencez peut faire une énorme différence dans le fonctionnement de l’algorithme. C’est comme commencer une randonnée – commencez au mauvais endroit, et vous pourriez ne jamais trouver le plus haut sommet.

Ces limitations ne signifient pas que l’escalade de colline est un mauvais choix – elles signifient simplement que nous devons faire attention à quand et comment nous l’utilisons. Parfois, nous pouvons la combiner avec d’autres techniques pour surmonter ces problèmes, que nous aborderons dans la section suivante.

Stratégies pour surmonter les limitations

Lorsque nous utilisons l’escalade de colline, nous pouvons utiliser plusieurs stratégies astucieuses pour résoudre les problèmes que nous avons discutés plus tôt. Explorons deux approches principales qui aident à améliorer le fonctionnement de l’escalade de colline.

Escalade de colline avec redémarrage aléatoire

Une des meilleures façons d’éviter de rester bloqué sur de petites collines est d’essayer de grimper à partir de différents points de départ. Cette approche s’appelle l’escalade de colline avec redémarrage aléatoire, et elle fonctionne exactement comme son nom l’indique – si vous restez bloqué, vous recommencez ailleurs.

Pensez à essayer de trouver la plus haute montagne dans une chaîne de montagnes brumeuse. Si vous commencez à escalader la première colline que vous trouvez et atteignez son sommet, vous pourriez manquer une montagne beaucoup plus haute à proximité. Mais si vous pouviez vous téléporter à différents endroits et recommencer à escalader, vous auriez beaucoup plus de chances de trouver finalement le plus haut sommet.

Voici comment cela fonctionne : Tout d’abord, vous exécutez l’algorithme de montée de colline normal jusqu’à ce qu’il soit bloqué. Au lieu d’abandonner, vous sauvegardez la meilleure solution que vous avez trouvée, puis vous recommencez à un nouveau point aléatoire. Vous continuez à faire cela pour plusieurs tentatives, et à la fin, vous choisissez la meilleure solution parmi toutes vos tentatives.

La beauté du redémarrage aléatoire est qu’il est simple mais efficace. Chaque redémarrage vous donne une nouvelle chance de trouver le plus haut sommet. Bien que cela prenne plus de temps que la montée de colline régulière, il est beaucoup plus probable de trouver la meilleure solution.

Recuit simulé

Bien que ce ne soit pas techniquement de l’escalade de colline, le recuit simulé est une variation astucieuse qui aide à résoudre bon nombre des problèmes de l’escalade de colline. Il est inspiré par la façon dont les métaux refroidissent et durcissent en métallurgie. Lorsque le métal refroidit lentement, ses atomes trouvent de meilleures positions, rendant le métal plus fort.

Dans cette approche, l’algorithme accepte parfois délibérément des solutions moins bonnes, surtout au début. Au fil du temps, il devient plus exigeant quant aux solutions qu’il accepte. C’est comme une balle rebondissant sur une surface cahoteuse – au début, elle a assez d’énergie pour sauter par-dessus des collines, mais en perdant de l’énergie, elle se stabilise dans un bon endroit.

Voici comment ça marche: Au début, l’algorithme peut accepter une solution qui est pire que celle actuelle avec une probabilité assez élevée. Cette probabilité dépend de deux choses : à quel point la nouvelle solution est pire et depuis combien de temps l’algorithme fonctionne. Avec le temps, l’algorithme devient moins susceptible d’accepter de pires solutions, agissant finalement plus comme une montée de colline classique.

La véritable puissance du recuit simulé est qu’il peut échapper à de petites collines et zones plates, en particulier au début de la recherche. En acceptant parfois des solutions pires, il peut :

Sortir de maxima locaux (petites collines)
Traverser des plateaux (zones plates)
Naviguer les crêtes (pics étroits)
Explorer davantage de l’espace de solution

Par exemple, imaginez que vous essayez de disposer des meubles dans une pièce pour maximiser l’espace. Déplacer une chaise pourrait rendre temporairement la pièce plus encombrée, mais cela pourrait vous permettre de déplacer ensuite d’autres pièces dans des positions beaucoup meilleures. Le recuit simulé serait prêt à essayer ces agencements temporairement pires, surtout au début du processus, pour trouver le meilleur agencement global.

Ces stratégies montrent que parfois, la meilleure façon de résoudre un problème n’est pas toujours de faire le pas évident en avant. En ajoutant des éléments de hasard et de chaos contrôlé, nous pouvons souvent trouver de meilleures solutions que si nous suivions toujours le chemin direct.

Mise en œuvre d’un algorithme de montée de colline simple en Python

Maintenant que nous comprenons comment améliorer l’escalade de colline avec des stratégies comme le redémarrage aléatoire et le recuit simulé, appliquons-le à un problème financier réel: l’optimisation de portefeuille.

L’optimisation de portefeuille aide les investisseurs à décider comment répartir leur argent entre différents investissements. Lorsque les investisseurs construisent un portefeuille, ils veulent obtenir les rendements les plus élevés possibles tout en conservant leur risque faible. Trouver cet équilibre est délicat, c’est comme essayer de trouver la recette parfaite avec de nombreux ingrédients.

En 1952, un économiste nommé Harry Markowitz a trouvé une manière intelligente de résoudre ce problème. Il a montré que les investisseurs pouvaient réduire leur risque en mélangeant des investissements qui ne montent pas et ne descendent pas ensemble. Cela s’appelle la diversification, c’est similaire à ne pas mettre tous ses œufs dans le même panier.

Lors de la construction d’un portefeuille, nous devons déterminer trois choses principales :

Combien d’argent nous prévoyons de gagner (Rendement attendu)
Le niveau de risque des investissements (Risque du portefeuille)
Si les profits potentiels valent le risque pris (Rendement ajusté au risque)

La méthode de l’escalade de montagne fonctionne bien pour ce problème car de petits changements dans la répartition de notre argent entraînent généralement de petits changements dans la performance du portefeuille. Imaginez une colline lisse où chaque point représente une manière différente d’investir votre argent. Les points les plus élevés indiquent de meilleurs choix d’investissement.

Pour trouver un bon portefeuille en utilisant la méthode du Hill Climbing, nous allons :

Commencer avec un mélange aléatoire d’investissements
Essayer des mélanges légèrement différents pour voir s’ils fonctionnent mieux
Continuer à apporter de petites améliorations jusqu’à ce que nous ne puissions pas trouver de meilleures options
Utiliser le meilleur mélange que nous avons trouvé

En utilisant le hill climbing de cette manière, nous pouvons aider les investisseurs à trouver de meilleurs portefeuilles parmi des millions de combinaisons possibles. C’est comme avoir un assistant intelligent qui peut rapidement tester de nombreux mélanges d’investissements différents pour trouver ceux qui équilibrent bien le risque et le rendement.

Tout d’abord, définissons notre fonction objectif, qui est une mesure de la performance du portefeuille qui équilibre les rendements attendus par rapport au risque. Elle prend une liste de poids de portefeuille en entrée et renvoie un score, où des scores plus élevés indiquent de meilleurs portefeuilles.

def objective_function(state):
   """
   Portfolio optimization objective function that maximizes expected returns while minimizing risk.
   The state represents portfolio weights for different assets.

   Args:
       state (list): List of portfolio weights for different assets (should sum to 1)

   Returns:
       float: Portfolio score combining returns and risk
   """
   # Rendements annuels attendus pour les actifs (valeurs d'exemple)
   expected_returns = [0.1, 0.12, 0.18, 0.1, 0.15]  # 8%, 12%, etc.

   # Risque (volatilité) pour chaque actif
   volatilities = [0.1, 0.2, 0.3, 0.2, 0.2]  # 10%, 20%, etc.

   # Valider que la longueur de l'entrée correspond aux rendements/volatilités attendus
   if len(state) != len(expected_returns):
       return float("-inf")  # Renvoyer le pire score possible pour les états invalides

   # Calculer le rendement attendu du portefeuille
   portfolio_return = sum(w * r for w, r in zip(state, expected_returns))

   # Calculer le risque du portefeuille (simplifié, sans utiliser de matrice de covariance)
   portfolio_risk = sum(w * v for w, v in zip(state, volatilities))

   # Pénaliser si les poids ne totalisent pas 1 (portefeuille invalide)
   weight_sum_penalty = abs(sum(state) - 1) * 100

   # Pénaliser les poids négatifs (pas de vente à découvert)
   negative_weight_penalty = sum(abs(min(0, w)) for w in state) * 100

   # Combinaison du rendement et du risque avec un facteur d'aversion au risque de 2
   # Un score plus élevé est meilleur : maximiser le rendement, minimiser le risque et les pénalités
   score = (
       portfolio_return
       - 2 * portfolio_risk
       - weight_sum_penalty
       - negative_weight_penalty
   )

   return score

La fonction objective_function ci-dessus nous aide à évaluer la qualité d’un portefeuille d’investissement particulier. Explorons son fonctionnement :

Tout d’abord, elle prend une liste de nombres qui représentent le pourcentage d’argent que nous voulons investir dans différents actifs (comme des actions ou des obligations). Par exemple, si nous avons cinq actifs, nous pourrions investir 20% dans chacun.

La fonction utilise deux informations importantes :

Rendements attendus : Combien d’argent nous prévoyons de gagner avec chaque actif (comme 8% ou 12% par an)
Volatilités : Le niveau de risque de chaque actif – des chiffres plus élevés signifient que la valeur de l’actif change de manière plus imprévisible (comme les cryptomonnaies)

Ensuite, la fonction :

Calcule le rendement attendu total de notre portefeuille en multipliant le rendement attendu de chaque actif par le montant investi dans cet actif
Détermine le risque total en examinant la volatilité de chaque actif
Vérifie si les pourcentages d’investissement totalisent bien 100% (ils devraient !)
Vérifie que nous n’essayons pas de vendre des actifs que nous ne possédons pas (pas de pourcentages négatifs)

Enfin, elle combine toutes ces informations en une seule note. Une note plus élevée signifie un meilleur portefeuille. La note augmente avec des rendements plus élevés mais diminue avec un risque plus élevé. Elle devient également beaucoup moins bonne si nos pourcentages ne totalisent pas 100% ou si nous essayons d’utiliser des pourcentages négatifs.

Cette fonction nous aidera à trouver le meilleur mix d’investissements en utilisant l’algorithme du hill climbing qui suit. Si vous ne comprenez pas pleinement la fonction objective, ne vous inquiétez pas – l’idée clé est qu’elle nous indique à quel point un mélange d’investissements particulier est bon, et nous l’utiliserons pour trouver des combinaisons de plus en plus meilleures.

Maintenant, définissons une nouvelle fonction pour générer des états de portefeuille voisins en apportant de petits ajustements aux pondérations.

def get_neighbors(state):
   """
   Generates neighboring states by making small adjustments to portfolio weights

   Args:
       state (list): Current portfolio weights

   Returns:
       list: List of neighboring portfolio weight configurations
   """
   neighbors = []
   step_size = 0.01  # Petit ajustement des pondérations (1%)

   for i in range(len(state)):
       for j in range(len(state)):
           if i != j:
               # Transférer du poids de l'actif i à l'actif j
               neighbor = state.copy()
               if neighbor[i] >= step_size:  # Ne transférer que si suffisamment de poids est disponible
                   neighbor[i] -= step_size
                   neighbor[j] += step_size
                   neighbors.append(neighbor)

   return neighbors

La fonction get_neighbors est une partie cruciale de notre algorithme du hill climbing qui génère des allocations de portefeuille similaires en apportant de petits ajustements aux pondérations de notre portefeuille actuel. Voici comment cela fonctionne :

Pour chaque paire d’actifs dans notre portefeuille, il crée une nouvelle allocation de portefeuille en transférant une petite quantité (1%) d’un actif à un autre. Par exemple, si nous avons cinq actifs, il essayera :

Transférer 1% de l’Actif 1 à l’Actif 2
Transférer 1% de l’Actif 1 à l’Actif 3
Transférer 1% de l’Actif 1 à l’Actif 4
Transférer 1% de l’Actif 1 à l’Actif 5
Transférer 1% de l’Actif 2 à l’Actif 1 Et ainsi de suite pour toutes les paires possibles.

La fonction inclut une vérification de sécurité pour s’assurer que nous ne transférons du poids que si l’actif source a suffisamment d’allocation (au moins 1%). Cela évite les pondérations négatives, ce qui n’aurait pas de sens dans un vrai portefeuille.

Chacun de ces petits ajustements crée un « voisin » – une allocation de portefeuille très similaire à la nôtre mais légèrement différente. L’algorithme du hill climbing évaluera ensuite ces voisins pour trouver de meilleures allocations de portefeuille.

La taille de pas de 1 % fournit un bon équilibre entre l’exploration de différentes allocations et la réalisation de changements contrôlés. Une taille de pas plus grande pourrait passer à côté de solutions optimales, tandis qu’une plus petite rendrait la recherche trop lente.

Maintenant, implémentons enfin un simple algorithme du hill climbing :

def simple_hill_climbing(initial_state, max_iterations=1000):
   """
   Implements Simple Hill Climbing algorithm
  
   Args:
       initial_state (list): Starting point for the algorithm
       max_iterations (int): Maximum number of iterations to prevent infinite loops
  
   Returns:
       tuple: (best_state, best_value) found by the algorithm
   """
   current_state = initial_state
   current_value = objective_function(current_state)
  
   for _ in range(max_iterations):
       # Obtenir les états voisins
       neighbors = get_neighbors(current_state)
      
       # Indicateur pour vérifier si nous avons trouvé un meilleur voisin
       found_better = False
      
       # Vérifier un par un les voisins (Simple Hill Climbing)
       for neighbor in neighbors:
           neighbor_value = objective_function(neighbor)
          
           # Si nous trouvons un meilleur voisin, passer immédiatement à celui-ci
           if neighbor_value > current_value:
               current_state = neighbor
               current_value = neighbor_value
               found_better = True
               break
      
       # Si aucun meilleur voisin n'a été trouvé, nous avons atteint un sommet
       if not found_better:
           break
  
   return current_state, current_value

La fonction commence à partir d’un état initial et se déplace de manière itérative vers de meilleurs états voisins jusqu’à ce qu’elle atteigne un maximum local ou le nombre maximum d’itérations.

La fonction prend deux paramètres :

initial_state : Le point de départ pour l’optimisation, représenté sous forme d’une liste de valeurs
max_iterations: Un paramètre de sécurité pour éviter les boucles infinies, avec une valeur par défaut de 1000 itérations

L’algorithme fonctionne comme suit:

Il commence à l’état initialinitial_state et calcule sa valeur de fonction objective
À chaque itération, il:

Génère des états voisins en utilisant get_neighbors()
Évalue chaque voisin un par un
Dès qu’il trouve un voisin meilleur (valeur d’objectif plus élevée), il se déplace vers cet état
Si aucun voisin meilleur n’est trouvé, il a atteint un maximum local et se termine

La fonction renvoie un tuple contenant:

Le meilleur état trouvé (liste de valeurs)
La valeur de la fonction objective pour cet état

Cette variante « simple » de la montée de colline est gourmande – elle se déplace vers le premier voisin meilleur qu’elle trouve plutôt que d’évaluer tous les voisins pour trouver le meilleur. Bien que cela le rende plus rapide, il peut manquer de meilleures solutions qui pourraient être trouvées en étant plus approfondi.

L’algorithme est utile pour trouver des optima locaux mais peut rester bloqué à ces maxima locaux, risquant de manquer le maximum global. Malgré cette limitation, il reste populaire en raison de sa simplicité et de son efficacité.

Testons-le sur un portefeuille d’exemple :

# Exemple d'utilisation
initial_state = [0.15, 0.25, 0.1, 0.3, 0.2]
best_state, best_value = simple_hill_climbing(initial_state)
print(f"Initial State: {initial_state}")
print(f"Best State Found: {best_state}")
print(f"Best Value: {best_value}")

[OUT]:

Initial State: [0.15, 0.25, 0.1, 0.3, 0.2]
Best State Found: [0.9700000000000006, 0.009999999999999913, 1.0408340855860843e-17, 0.009999999999999858, 0.009999999999999969]
Best Value: -0.1053000000000444

La sortie montre les résultats de notre algorithme de montée en altitude lors de l’optimisation d’un portefeuille. Partant de poids aléatoires pour cinq actifs, il a trouvé un nouvel ensemble de poids qui a amélioré la valeur de la fonction objective. Bien que cette solution ait amélioré le portefeuille initial, elle peut ne représenter qu’un optimum local puisque l’algorithme s’arrête au premier pic trouvé.

Applications de la montée en altitude en IA

Les algorithmes de montée en altitude trouvent des applications pratiques dans de nombreux domaines de l’intelligence artificielle et de l’apprentissage automatique. Explorons quelques applications clés :

1. Optimisation de modèles d’apprentissage automatique

L’escalade de colline aide à ajuster les modèles d’apprentissage automatique de plusieurs façons :

Sélection des caractéristiques : Trouver le meilleur sous-ensemble de caractéristiques pour un modèle
Ajustement des hyperparamètres : Optimiser les paramètres du modèle comme le taux d’apprentissage ou la profondeur de l’arbre
Entraînement du réseau neuronal : Ajustement fin des poids et de l’architecture du réseau
Compression du modèle : Réduire la taille du modèle tout en maintenant les performances

Par exemple, lors de la sélection des caractéristiques pour un modèle prédictif, la méthode du Hill Climbing peut commencer avec toutes les caractéristiques et les retirer ou les ajouter de manière itérative en fonction des performances du modèle. Cela aide à trouver un ensemble de caractéristiques optimal qui équilibre la précision du modèle avec la complexité.

2. Robotique et planification de trajectoire

En robotique, le Hill Climbing assiste avec :

Planification de mouvement : Trouver des trajectoires efficaces à travers l’espace physique
Optimisation de l’angle articulaire: Détermination des positions optimales pour les bras de robot
Placement de capteurs: Optimisation du placement des capteurs pour une couverture maximale
Gestion de la batterie: Optimisation des schémas de consommation d’énergie

Un aspirateur robotique pourrait utiliser l’escalade de colline pour trouver des trajets de nettoyage efficaces, ajustant continuellement sa route en fonction de la couverture de la pièce et de la durée de vie de la batterie.

3. Traitement du langage naturel

NLP Les applications comprennent:

Résumé de texte: Optimisation de la sélection du contenu du résumé
Encodage de mots: Ajustement des représentations vectorielles de mots
Regroupement de documents: Organisation des documents en groupes optimaux
Optimisation des moteurs de recherche: Amélioration du classement des résultats de recherche

Par exemple, dans la résumé de texte, la montée en puissance peut aider à sélectionner des phrases qui maximisent le contenu d’information tout en minimisant la redondance.

4. Vision par ordinateur En traitement d’image et vision par ordinateur

Segmentation d’image: Recherche des frontières optimales entre les objets
Étalonnage de caméra: Ajustement des paramètres de la caméra pour une meilleure qualité d’image
Détection d’objet: Optimisation des positions des boîtes englobantes
Appariement de caractéristiques: Recherche des points correspondants entre les images

Un système de reconnaissance faciale pourrait utiliser la montée de collines pour optimiser l’alignement des traits du visage lors du prétraitement.

5. Intelligence artificielle dans les jeux et prise de décision

La montée de collines aide à :

Optimisation de la stratégie de jeu : Trouver des coups gagnants dans les jeux de plateau
Allocation des ressources: Optimisation de la distribution des ressources dans les jeux de stratégie
Comportement des PNJ: Amélioration de la prise de décision des personnages non-joueurs
Génération de niveaux: Création de niveaux de jeu équilibrés et intéressants

Les moteurs d’échecs utilisent souvent des variantes de montée en altitude pour évaluer et optimiser les séquences de mouvements pendant le jeu.

6. Business et opérations

Les applications pratiques en entreprise incluent:

Optimisation de la chaîne d’approvisionnement: Recherche de trajets de livraison efficaces
Planification des ressources: Optimisation des plannings du personnel ou de l’utilisation des machines
Gestion de portefeuille: Équilibrage des portefeuilles d’investissement
Gestion des stocks: Optimisation des niveaux de stock

Une entreprise de livraison pourrait utiliser l’escalade de colline pour optimiser en continu les itinéraires de livraison en fonction des modèles de trafic et des priorités des colis.

Alors que l’escalade de colline ne trouve pas toujours la meilleure solution absolue, sa simplicité et son efficacité en font une méthode précieuse pour ces applications du monde réel. Elle est particulièrement utile lorsque :

Des solutions rapides sont nécessaires
L’espace du problème est trop vaste pour une recherche exhaustive
Des solutions approximatives sont acceptables
L’espace des solutions est relativement lisse
L’algorithme peut être combiné avec d’autres techniques pour de meilleurs résultats

Conclusion

L’escalade de colline se présente comme un algorithme fondamental en intelligence artificielle, offrant une approche simple mais puissante pour les problèmes d’optimisation.

À travers notre exploration, nous avons vu comment ce concept simple de se déplacer de manière itérative vers de meilleures solutions peut être appliqué à des défis complexes dans les domaines de l’apprentissage automatique, de la robotique, du traitement du langage naturel et des opérations commerciales.

Bien que l’algorithme ait ses limites, telles que se retrouver coincé dans des optima locaux, des stratégies telles que le redémarrage aléatoire et le recuit simulé ont évolué pour relever efficacement ces défis.

Alors que l’IA continue de progresser, l’escalade de colline reste pertinente non seulement en tant qu’outil pratique, mais aussi comme un tremplin vers la compréhension d’algorithmes d’optimisation plus complexes. Sa nature intuitive en fait un excellent point de départ pour ceux qui entrent dans le domaine de l’IA, tandis que sa polyvalence garantit son utilisation continue dans les applications du monde réel.

Que vous optimisiez les poids des réseaux neuronaux, planifiez des trajectoires de robots ou gérez des portefeuilles d’investissement, les principes de l’escalade de colline fournissent des informations précieuses sur la manière dont les ordinateurs peuvent trouver systématiquement de meilleures solutions à des problèmes complexes.

Si vous souhaitez en savoir plus sur l’IA et les algorithmes qui la sous-tendent, consultez nos ressources :

Source:
https://www.datacamp.com/tutorial/hill-climbing-algorithm-for-ai-in-python