Implémenter l’algorithme de hill climbing pour l’IA en Python

L’algorithme de hill climbing compte parmi les premiers et les plus simples algorithmes d’optimisation en intelligence artificielle et en informatique. Il appartient à la famille des algorithmes de recherche locale, qui trouvent des solutions par améliorations incrémentales.

Son nom vient d’une analogie parlante : imaginez un randonneur aux yeux bandés qui cherche le sommet d’une colline. Comme il ne voit pas le paysage, il ne peut sentir que le sol autour de lui. À chaque pas, il se dirige vers la pente qui monte. C’est exactement ainsi que fonctionne l’algorithme : il évalue les solutions voisines et progresse itérativement vers de meilleures, pour tenter d’atteindre la solution optimale (le sommet).

Dans cet article, nous allons explorer en profondeur l’algorithme de hill climbing, ses variantes, et comment l’implémenter en Python. Si vous débutez en IA, consultez notre parcours de compétences AI Fundamentals pour couvrir les bases.

Qu’est-ce que le hill climbing en IA ?

Le hill climbing est une façon simple pour un ordinateur de résoudre des problèmes en cherchant la meilleure réponse possible, à l’image d’un randonneur qui tente d’atteindre un sommet. En intelligence artificielle (IA), il faut souvent choisir la meilleure solution parmi de nombreuses options : c’est l’optimisation.

Pensez au jeu du « chaud/froid ». Vous ne savez qu’une chose : si vous vous rapprochez (« plus chaud ») ou si vous vous éloignez (« plus froid »). Le hill climbing procède de même : il observe les solutions voisines et se dirige vers les meilleures.

Voici les étapes, simplement :

1. Démarrer avec n’importe quelle solution possible
2. Examiner les solutions voisines
3. Si une voisine est meilleure, s’y déplacer
4. Répéter les étapes 2–3 jusqu’à ce qu’on ne trouve plus mieux

Par exemple, pour apprendre à un robot à marcher, le hill climbing pourrait :

• Commencer par des mouvements de jambes aléatoires
• Essayer des variations légères
• Conserver celles qui améliorent la marche
• Répéter jusqu’à trouver une allure optimale

Même si le hill climbing n’est pas toujours la méthode la plus avancée en IA, c’est un jalon essentiel pour comprendre comment les ordinateurs peuvent résoudre des problèmes de manière autonome, un peu comme l’algorithme minimax.

Les types de hill climbing

On distingue trois variantes principales, chacune ayant sa manière de chercher la meilleure solution :

1. Simple hill climbing

Le simple hill climbing revient à saisir la première bonne opportunité rencontrée. Concrètement :

• L’algorithme examine les solutions voisines une à une
• Dès qu’il en trouve une meilleure, il l’adopte
• Il n’examine pas les autres options
• C’est rapide, mais cela peut passer à côté d’options encore meilleures un peu plus loin

2. Steepest-ascent hill climbing

Cette version est plus exhaustive :

• Elle évalue TOUTES les solutions voisines avant d’avancer
• Elle choisit la meilleure parmi celles examinées
• C’est plus long, mais généralement plus performant
• C’est comme comparer soigneusement chaque sentier avant de faire un pas

3. Stochastic hill climbing

Cette variante ajoute une part d’aléatoire pour enrichir la recherche :

• Au lieu de toujours choisir la meilleure voisine, elle en sélectionne une au hasard parmi les meilleures
• Les meilleures options ont plus de chances d’être choisies
• Cette aléa aide à éviter les impasses
• C’est comme prendre parfois un autre sentier pour voir où il mène

Chaque type a ses forces et se prête à des problèmes différents. Simple hill climbing est rapide mais basique, steepest-ascent est plus fouillé mais plus lent, et la version stochastique introduit une utile dose d’aléatoire pour éviter de se bloquer.

Comment fonctionne l’algorithme de hill climbing

Le hill climbing progresse par petites améliorations successives jusqu’à trouver la meilleure solution accessible. Décomposons ses éléments clés.

1. Le point de départ

Tout algorithme de hill climbing a besoin d’un point de départ. Comme choisir où commencer l’ascension. Vous pouvez partir au hasard, ou tirer parti de vos connaissances du problème pour choisir un bon point de départ.

Ce choix compte beaucoup : bien démarrer peut accélérer la convergence vers la meilleure solution. Un mauvais départ peut vous coincer sur une collinette au lieu du sommet.

Par exemple, lors de l’entraînement de réseaux de neurones, le point de départ correspond aux poids initiaux entre neurones. On peut les initialiser aléatoirement, comme démarrer la randonnée n’importe où, ou utiliser des techniques comme l’initialisation de Xavier pour des poids mieux adaptés à l’architecture.

Une bonne initialisation accélère l’apprentissage et mène à de meilleures solutions, tandis qu’une mauvaise initialisation peut bloquer le réseau avec une faible précision.

2. Explorer les solutions voisines

Une fois la recherche lancée, l’algorithme évalue les solutions « voisines », proches de la position actuelle. C’est comme explorer les alentours à petits pas. Par exemple, si vous optimisez un itinéraire de livraison entre villes et que votre trajet actuel est [A -> B -> C -> D], l’algorithme examinera des variantes proches telles que [A -> B -> D -> C] ou [A -> C -> B -> D] pour voir si elles réduisent la distance totale. Chaque petite modification représente une solution « voisine » potentiellement meilleure.

Pour comparer, l’algorithme s’appuie sur une fonction objectif : une formule mathématique qui attribue une note à chaque solution possible.

Cette fonction sert de boussole, indiquant les directions « montantes » (meilleures) et « descendantes » (pires). Pour l’itinéraire, la fonction calcule la distance totale : plus elle est courte, meilleure est la solution.

Ainsi, si l’itinéraire X fait 100 miles et le Z 90 miles, le Z a un meilleur score (plus bas, si l’on minimise). L’algorithme sait alors explorer dans la direction de solutions semblables à Z. La fonction objectif ramène ainsi un problème complexe à un nombre facile à comparer et à optimiser.

3. Choisir la prochaine étape

Après avoir examiné les voisines, l’algorithme doit décider du prochain mouvement. Il compare les scores des voisines au score courant et se déplace si une meilleure est trouvée. Les variantes diffèrent sur ce choix :

• La version simple adopte la première meilleure voisine rencontrée
• La version « prudente » évalue toutes les voisines puis choisit la meilleure
• La version « aléatoire » peut choisir une voisine non optimale pour éviter de se bloquer

4. Savoir s’arrêter

L’algorithme doit savoir quand cesser de chercher. En général, il s’arrête lorsque :

1. Aucune meilleure voisine n’est trouvée
2. Le temps d’exécution devient trop long
3. Une solution « suffisamment bonne » est atteinte

Typiquement, la progression est rapide au début, puis ralentit à l’approche du sommet, avec des gains plus petits jusqu’à l’arrêt.

Parfois la montée est fluide, parfois le relief est accidenté.

Avantages et limites du hill climbing en IA

Voyons ce qui rend le hill climbing utile, et les écueils à anticiper.

Avantages

C’est l’un des algorithmes d’optimisation les plus simples à comprendre et à coder. Suivre la règle « si c’est mieux, j’y vais » en fait un excellent point de départ pour de nombreux problèmes.

Sur des problèmes bien structurés, il trouve rapidement de bonnes solutions. Il ne perd pas de temps à tout explorer : il grimpe.

Il consomme peu de mémoire et de calculs : il garde la position courante et regarde autour, ce qui le rend pratique en production.

Limites

Comme toute méthode, il présente des inconvénients :

1. Coincé sur des petites collines

Le principal risque, ce sont les maxima locaux : de « petites collines » alors qu’une vraie montagne est à proximité. Arrivé au sommet local, tout autour est plus bas, l’algorithme s’arrête, même si une meilleure solution existe ailleurs.

2. Le plateau

Parfois, l’algorithme se retrouve sur un terrain plat (plateau), où toutes les voisines se valent. Comme chercher le point le plus haut sur un terrain de football : difficile de savoir où aller.

3. L’arête

Sur une arête étroite, il peut zigzaguer au lieu d’avancer vers le pic, car chaque pas latéral semble aussi bon que rester sur la trajectoire.

4. Le point de départ est crucial

Comme en randonnée, un mauvais départ peut vous éloigner du meilleur sommet.

Ces limites n’invalident pas le hill climbing : elles invitent à l’employer avec discernement, ou à le combiner à d’autres techniques, comme ci-dessous.

Stratégies pour dépasser les limites

Pour pallier ces écueils, plusieurs stratégies efficaces existent. Voyons deux approches clés.

Random-restart hill climbing

Une des meilleures façons d’éviter de rester sur une petite colline est de redémarrer depuis différents points. C’est le random-restart hill climbing : si vous êtes bloqué, vous repartez ailleurs.

Dans une chaîne de montagnes embrumée, commencer à grimper la première colline trouvée peut vous faire rater un sommet plus haut. En « téléportant » vos départs à divers endroits, vous augmentez vos chances d’atteindre le plus haut pic.

Fonctionnement : exécutez d’abord le hill climbing classique jusqu’au blocage. Plutôt que d’abandonner, conservez la meilleure solution trouvée et redémarrez depuis un point aléatoire. Répétez plusieurs fois, puis gardez la meilleure solution parmi tous les essais.

Simple et efficace : chaque redémarrage offre une nouvelle chance d’atteindre le sommet global. Cela prend plus de temps, mais augmente sensiblement la probabilité de trouver la meilleure solution.

Recuit simulé (simulated annealing)

Sans être à proprement parler du hill climbing, le recuit simulé corrige nombre de ses limites. Inspiré de la métallurgie, un refroidissement progressif permet aux atomes d’adopter de meilleures positions, rendant le métal plus résistant.

Ici, l’algorithme accepte volontairement des solutions moins bonnes au début. Puis il devient de plus en plus exigeant. Comme une balle qui rebondit sur un relief irrégulier : au début, elle a l’énergie pour franchir des bosses, puis elle se stabilise dans un bon creux.

Fonctionnement : au départ, l’algorithme peut accepter une solution plus mauvaise avec une probabilité assez élevée, dépendant de l’écart de qualité et du temps écoulé. Cette probabilité décroît, et l’algorithme se rapproche d’un hill climbing classique.

Sa force : il peut s’extraire des collines locales et des plateaux, surtout au début, en acceptant parfois le pire pour mieux progresser ensuite :

• Sauter hors des maxima locaux
• Traverser des plateaux
• Suivre des arêtes étroites
• Explorer davantage l’espace de solutions

Par analogie, aménager une pièce peut nécessiter de déplacer temporairement un fauteuil au mauvais endroit pour libérer l’espace et mieux réorganiser l’ensemble. Le recuit simulé accepte ces détours, surtout au début, pour atteindre une configuration optimale.

Moralité : ne pas toujours choisir le pas « évident ». En introduisant un peu d’aléa maîtrisé, on découvre souvent de meilleures solutions que par une progression trop directe.

Implémenter un simple hill climbing en Python

Maintenant que nous avons vu comment améliorer le hill climbing avec des stratégies comme le random-restart et le recuit simulé, appliquons-le à un problème financier concret : l’optimisation de portefeuille.

L’optimisation de portefeuille aide les investisseurs à répartir leur capital entre différents actifs. L’objectif : maximiser le rendement attendu tout en maîtrisant le risque. Trouver cet équilibre, c’est comme ajuster une recette avec de multiples ingrédients.

En 1952, l’économiste Harry Markowitz a proposé une approche élégante : en combinant des actifs peu corrélés, on réduit le risque. C’est la diversification : ne pas mettre tous ses œufs dans le même panier.

Pour construire un portefeuille, il faut estimer trois éléments clés :

• Le rendement attendu (Expected Return)
• Le risque du portefeuille (Portfolio Risk)
• Le rendement ajusté du risque (Risk-Adjusted Return)

Le hill climbing est bien adapté ici, car de petites variations de pondérations entraînent de petits changements de performance. Imaginez une colline régulière où chaque point représente une répartition différente : plus on monte, meilleure est la combinaison.

Pour trouver un bon portefeuille avec le hill climbing, nous allons :

1. Partir d’un panachage aléatoire d’actifs
2. Tester des répartitions légèrement différentes
3. Itérer ces petites améliorations jusqu’à ne plus trouver mieux
4. Conserver la meilleure répartition

De cette manière, on aide les investisseurs à identifier de meilleurs portefeuilles parmi des millions de combinaisons. Comme un assistant qui teste rapidement de multiples répartitions pour équilibrer risque et rendement.

Définissons d’abord la fonction objectif, qui mesure la performance du portefeuille en arbitrant rendement et risque. Elle prend une liste de poids en entrée et renvoie un score : plus il est élevé, meilleur est le portefeuille.

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
   """
   # Expected annual returns for assets (example values)
   expected_returns = [0.1, 0.12, 0.18, 0.1, 0.15]  # 8%, 12%, etc.

   # Risk (volatility) for each asset
   volatilities = [0.1, 0.2, 0.3, 0.2, 0.2]  # 10%, 20%, etc.

   # Validate input length matches expected returns/volatilities
   if len(state) != len(expected_returns):
       return float("-inf")  # Return worst possible score for invalid states

   # Calculate expected portfolio return
   portfolio_return = sum(w * r for w, r in zip(state, expected_returns))

   # Calculate portfolio risk (simplified, not using covariance matrix)
   portfolio_risk = sum(w * v for w, v in zip(state, volatilities))

   # Penalize if weights don't sum to 1 (invalid portfolio)
   weight_sum_penalty = abs(sum(state) - 1) * 100

   # Penalize negative weights (no short selling)
   negative_weight_penalty = sum(abs(min(0, w)) for w in state) * 100

   # Combine return and risk with risk aversion factor of 2
   # Higher score is better: maximize return, minimize risk and penalties
   score = (
       portfolio_return
       - 2 * portfolio_risk
       - weight_sum_penalty
       - negative_weight_penalty
   )

   return score

La fonction objective_function ci-dessus évalue la qualité d’un portefeuille donné. En bref :

Elle reçoit une liste de nombres représentant le pourcentage investi dans chaque actif (actions, obligations, etc.). Par exemple, pour cinq actifs, on peut allouer 20 % à chacun.

Elle utilise deux informations clés :

1. Rendements attendus : combien chaque actif devrait rapporter (8 %, 12 % par an, etc.)
2. Volatilités : le risque de chaque actif — plus la valeur est élevée, plus l’actif est imprévisible (comme la crypto)

Ensuite, la fonction :

• Calcule le rendement attendu du portefeuille (somme des rendements pondérés)
• Estime le risque total à partir des volatilités
• Vérifie que la somme des poids fait 100 % (impératif)
• S’assure qu’il n’y a pas de poids négatifs (pas de vente à découvert)

Enfin, elle agrège le tout en un score unique. Plus le score est élevé, meilleur est le portefeuille. Le score augmente avec le rendement et diminue avec le risque et les pénalités (somme des poids ≠ 100 % ou poids négatifs).

Cette fonction nous sert de boussole pour trouver le meilleur mix d’investissements avec l’algorithme de hill climbing. Si certains détails vous échappent, retenez l’essentiel : elle nous dit si une répartition est bonne, et nous l’utiliserons pour progresser vers de meilleures combinaisons.

Définissons maintenant une fonction qui génère des « voisins » en ajustant légèrement les poids.

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  # Small adjustment to weights (1%)

   for i in range(len(state)):
       for j in range(len(state)):
           if i != j:
               # Transfer weight from asset i to asset j
               neighbor = state.copy()
               if neighbor[i] >= step_size:  # Only transfer if enough weight available
                   neighbor[i] -= step_size
                   neighbor[j] += step_size
                   neighbors.append(neighbor)

   return neighbors

La fonction get_neighbors est essentielle : elle génère des répartitions voisines en modifiant légèrement les poids actuels. Son principe :

Pour chaque paire d’actifs, elle crée une nouvelle allocation en transférant 1 % de l’un vers l’autre. Par exemple, avec cinq actifs, elle essaiera :

• Déplacer 1 % de l’actif 1 vers l’actif 2
• Déplacer 1 % de l’actif 1 vers l’actif 3
• Déplacer 1 % de l’actif 1 vers l’actif 4
• Déplacer 1 % de l’actif 1 vers l’actif 5
• Déplacer 1 % de l’actif 2 vers l’actif 1, etc., pour toutes les paires.

Une vérification évite de transférer si l’actif source n’a pas au moins 1 % à donner, ce qui prévient les poids négatifs.

Chaque ajustement produit un « voisin » — une allocation très proche mais distincte. L’algorithme évaluera ces voisins pour trouver de meilleures répartitions.

Un pas de 1 % offre un bon compromis entre exploration et contrôle. Un pas plus grand peut rater des optima, un pas plus petit ralentit la recherche.

Implémentons maintenant un simple 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):
       # Get neighboring states
       neighbors = get_neighbors(current_state)
      
       # Flag to check if we found a better neighbor
       found_better = False
      
       # Check neighbors one by one (Simple Hill Climbing)
       for neighbor in neighbors:
           neighbor_value = objective_function(neighbor)
          
           # If we find a better neighbor, move to it immediately
           if neighbor_value > current_value:
               current_state = neighbor
               current_value = neighbor_value
               found_better = True
               break
      
       # If no better neighbor was found, we've reached a peak
       if not found_better:
           break
  
   return current_state, current_value

La fonction part d’un état initial et se déplace itérativement vers de meilleurs voisins jusqu’à atteindre un maximum local ou la limite d’itérations.

Elle prend deux paramètres :

• initial_state : le point de départ, représenté par une liste de valeurs
• max_iterations : sécurise contre les boucles infinies, 1000 par défaut

Le déroulé :

1. On commence à initial_state et on calcule sa valeur via la fonction objectif
2. À chaque itération :

• On génère des voisins avec get_neighbors()
• On évalue les voisins un par un
• Dès qu’un voisin a une meilleure valeur, on s’y déplace
• S’il n’y a pas de meilleur voisin, on a atteint un maximum local et on s’arrête

La fonction renvoie :

• Le meilleur état trouvé (liste de valeurs)
• La valeur de la fonction objectif associée

Cette variante « simple » est gloutonne : elle adopte le premier voisin meilleur sans comparer tous les voisins. C’est plus rapide, mais cela peut manquer des solutions supérieures qui exigeraient une exploration plus complète.

Utile pour trouver des optima locaux, l’algorithme peut s’y bloquer et rater l’optimum global. Malgré cela, sa simplicité et son efficacité en font un choix populaire.

Testons-le sur un portefeuille d’exemple :

# Example usage
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 illustre le résultat de l’optimisation : à partir de poids initiaux pour cinq actifs, l’algorithme a trouvé une nouvelle répartition qui améliore la valeur de la fonction objectif. Cette solution peut toutefois n’être qu’un optimum local, l’algorithme s’arrêtant au premier « sommet » atteint.

Applications du hill climbing en IA

Les algorithmes de hill climbing s’appliquent à de nombreux domaines de l’IA et du machine learning. Exemples :

1. Optimisation de modèles de machine learning

Le hill climbing aide à régler les modèles de plusieurs façons :

• Sélection de variables : trouver le meilleur sous-ensemble de caractéristiques
• Ajustement d’hyperparamètres : optimiser taux d’apprentissage, profondeur, etc.
• Entraînement de réseaux de neurones : affiner poids et architecture
• Compression de modèles : réduire la taille tout en préservant la performance

Par exemple, en sélection de variables, le hill climbing peut partir de l’ensemble complet et ajouter/retirer des variables au fil des améliorations de performance, pour concilier précision et simplicité.

2. Robotique et planification de trajectoires

En robotique, il aide à :

• Planifier les mouvements : trouver des trajectoires efficaces
• Optimiser les angles des articulations de bras robotisés
• Placer les capteurs pour une couverture maximale
• Gérer la batterie : optimiser la consommation

Un robot aspirateur peut l’utiliser pour ajuster en continu son parcours, selon la zone déjà couverte et l’autonomie restante.

3. Traitement du langage naturel

NLP : exemples d’usages

• Résumé automatique : sélectionner le contenu optimal
• Word embedding : affiner les représentations vectorielles
• Clustering de documents : organiser en groupes pertinents
• Optimisation pour moteurs de recherche : améliorer les classements

En résumé automatique, par exemple, le hill climbing aide à choisir des phrases maximisant l’information et minimisant la redondance.

4. Vision par ordinateur et traitement d’images

• Segmentation d’images : trouver les frontières optimales
• Calibration de caméra : ajuster les paramètres pour une meilleure qualité
• Détection d’objets : optimiser les boîtes englobantes
• Appariement de caractéristiques : retrouver les points correspondants entre images

Un système de reconnaissance faciale peut l’utiliser pour optimiser l’alignement des traits lors du prétraitement.

5. IA de jeux et prise de décision

Le hill climbing sert à :

• Optimiser des stratégies de jeu : trouver des séquences gagnantes
• Allouer des ressources dans les jeux de stratégie
• Améliorer le comportement des PNJ (personnages non joueurs)
• Générer des niveaux équilibrés et intéressants

Les moteurs d’échecs exploitent des variantes de hill climbing pour évaluer et optimiser des séquences de coups.

6. Business et opérations

Des usages concrets en entreprise :

• Optimisation de la supply chain : itinéraires de livraison efficaces
• Planification des ressources : plannings d’équipes et d’équipements
• Gestion de portefeuille : équilibrer les investissements
• Gestion des stocks : optimiser les niveaux

Un transporteur peut l’utiliser pour ajuster en continu ses tournées selon le trafic et les priorités de colis.

Le hill climbing ne trouve pas toujours la solution absolue, mais sa simplicité et son efficacité en font un atout pour ces cas d’usage. Il est particulièrement utile lorsque :

• Il faut une solution rapide
• L’espace de recherche est trop vaste pour une exploration exhaustive
• Des solutions approximatives sont acceptables
• L’espace de solutions est relativement « doux »
• On peut le combiner à d’autres techniques pour de meilleurs résultats

Conclusion

Le hill climbing est un algorithme fondamental de l’IA, offrant une approche à la fois simple et puissante pour les problèmes d’optimisation.

Nous avons vu comment ce principe — avancer pas à pas vers de meilleures solutions — s’applique à des défis complexes en machine learning, robotique, traitement du langage et opérations.

Malgré ses limites (optima locaux), des stratégies comme le random-restart et le recuit simulé permettent d’en atténuer efficacement les effets.

À mesure que l’IA progresse, le hill climbing reste pertinent : outil pratique et tremplin pour comprendre des méthodes d’optimisation plus avancées. Son intuitivité en fait un excellent point d’entrée, et sa polyvalence assure son utilité en production.

Que vous optimisiez des poids de réseaux de neurones, planifiiez des trajectoires robotiques ou gériez des portefeuilles, les principes du hill climbing éclairent la manière dont les ordinateurs améliorent systématiquement des solutions à des problèmes exigeants.

Pour aller plus loin sur l’IA et ses algorithmes, explorez nos ressources :

• Comprendre l’algorithme de recherche A*
• Implémenter l’algorithme Minimax pour l’IA en Python
• Cas d’usage et algorithmes en machine learning
• Guide du Gradient Boosting
• Parcours Developing AI Applications
• Parcours AI Fundamentals