Introduction

Les algorithmes d'optimisation sont des méthodes mathématiques et informatiques utilisées pour trouver la meilleure solution à un problème donné parmi un ensemble de solutions possibles. En général, l'objectif est de maximiser ou de minimiser une fonction appelée fonction objectif, pouvant représenter un coût, une performance ou un autre critère de qualité. Ces algorithmes sont fondamentaux en recherche opérationnelle, en intelligence artificielle, en apprentissage automatique, et dans d'autres domaines scientifiques et industriels.

Les algorithmes d'optimisation se répartissent en plusieurs grandes catégories en fonction de leur méthode et de la nature des problèmes à résoudre :

• Optimisation déterministe : Les algorithmes d'optimisation déterministes utilisent des méthodes précises pour explorer les solutions possibles, garantissant souvent de trouver l'optimum (solution optimale) lorsque cela est mathématiquement possible. Ces algorithmes comprennent :
• Méthodes de gradient : Utilisées pour les fonctions continues et différentiables, elles reposent sur le calcul de la pente pour se rapprocher de l'optimum. Par exemple, la descente de gradient est largement utilisée dans l'apprentissage automatique.
• Programmation linéaire : Utilisée pour optimiser des fonctions linéaires avec des contraintes linéaires. L'algorithme du simplexe est un exemple de technique pour résoudre ces problèmes.
• Programmation quadratique et non linéaire : Optimise des fonctions non linéaires ou quadratiques, ce qui peut être nécessaire dans des contextes plus complexes où les relations entre les variables ne sont pas linéaires.
• Optimisation stochastique : Les algorithmes d'optimisation stochastiques intègrent des éléments aléatoires pour explorer les solutions et sont souvent utilisés pour éviter les minimums locaux (solutions sous-optimales) dans des problèmes complexes. Les principales méthodes incluent :
• Recuit simulé (Simulated Annealing) : Simule le refroidissement des métaux en abaissant progressivement la "température" du système pour explorer les solutions avant de se concentrer sur une solution optimale.
• Recherche tabou : Utilise une liste des solutions récemment visitées pour éviter de revisiter des solutions et échapper aux minimums locaux.
• Optimisation par essaims de particules : Inspirée par le comportement collectif des essaims, cette méthode utilise plusieurs solutions potentielles "naviguant" dans l'espace des solutions en se guidant mutuellement pour converger vers l'optimum global.
• Algorithmes évolutionnaires : Les algorithmes évolutionnaires sont inspirés des processus biologiques de sélection naturelle et d'évolution. Ils génèrent des solutions à partir d'une population initiale et améliorent ces solutions par "croisement" et "mutation". Les exemples les plus connus sont :
• Algorithmes génétiques : Représentent les solutions comme des "chromosomes" et appliquent des opérations de sélection, de croisement et de mutation pour évoluer vers une solution optimale.
• Stratégies évolutionnaires : Similaires aux algorithmes génétiques, mais plus axés sur l'optimisation de problèmes continus en ajustant des paramètres pour atteindre l'optimum.
• Programmation génétique : Évolution de programmes ou d'algorithmes eux-mêmes pour optimiser une tâche spécifique, en modifiant les structures et les fonctions de chaque programme au fil des générations.
• Optimisation multi-objectif : Dans certains problèmes, il est nécessaire d'optimiser plusieurs critères simultanément, souvent avec des objectifs conflictuels (comme maximiser la qualité tout en minimisant les coûts). L'optimisation multi-objectif utilise des techniques pour trouver un compromis acceptable entre ces objectifs, souvent représenté par des solutions de Pareto. Exemples d'algorithmes :
• Méthode de Pareto : Cherche à trouver un ensemble de solutions non dominées, formant le front de Pareto où aucune solution ne peut être améliorée sur un objectif sans détériorer un autre.
• Algorithmes génétiques multi-objectifs (NSGA-II) : Variation des algorithmes génétiques conçue pour explorer plusieurs solutions de compromis dans un problème multi-objectif.
• Optimisation des objectifs pondérés : Attribue des poids aux différents objectifs pour les combiner en une seule fonction, équilibrant les priorités entre eux.
• Optimisation par apprentissage automatique : Les algorithmes d'apprentissage automatique ont aussi développé des méthodes d'optimisation adaptées, comme dans l'optimisation d'hyperparamètres ou pour trouver des solutions optimales dans des problèmes complexes d'apprentissage :
• Optimisation bayésienne : Méthode probabiliste pour optimiser les fonctions coûteuses à évaluer, souvent utilisée pour régler les hyperparamètres des modèles d'apprentissage.
• Recherche de grille et recherche aléatoire : Techniques simples et populaires en apprentissage automatique pour tester diverses combinaisons de paramètres et identifier celles offrant les meilleurs résultats.
• Optimisation par réseaux neuronaux (AutoML) : Application de l'apprentissage automatique à l'optimisation de modèles, où les architectures de réseaux neuronaux et les hyperparamètres sont ajustés automatiquement.

Applications et importance

Les algorithmes d'optimisation sont cruciaux pour résoudre des problèmes dans de nombreux domaines :

• Industrie : Optimisation de la production, des chaînes d'approvisionnement, et de la planification des ressources.
• Finance : Gestion de portefeuille, minimisation des risques et maximisation des rendements.
• Apprentissage automatique et IA : Optimisation des modèles pour de meilleures performances, réduction des coûts de calcul, et sélection des meilleurs paramètres.
• Recherche scientifique : Optimisation des expériences, de la conception des médicaments, et de la simulation dans les sciences physiques et biologiques.

Recuit simulé (Simulated Annealing)

Le recuit simulé (ou simulated annealing en anglais) est un algorithme d'optimisation inspiré du processus de refroidissement des métaux, un procédé appelé recuit en métallurgie. Ce procédé consiste à chauffer un métal jusqu'à une température élevée, puis à le refroidir lentement pour minimiser son énergie interne et lui permettre d'atteindre une structure stable avec moins de défauts. En utilisant cette analogie, le recuit simulé permet de trouver une solution optimale ou quasi-optimale dans un espace de solutions complexe, en évitant de rester bloqué dans des minima locaux.

Principe de base

Le recuit simulé commence avec une "température" initiale élevée, ce qui permet à l'algorithme de faire des explorations aléatoires dans l'espace des solutions. Au début, le système est autorisé à accepter des solutions de moindre qualité (solutions avec un coût ou une "énergie" plus élevée) avec une probabilité élevée, pour explorer un éventail de solutions variées. Puis, au fil des itérations, la température est progressivement réduite. Cette réduction de température diminue également la probabilité d'accepter des solutions de moindre qualité, permettant au système de se concentrer sur les solutions plus optimales.

Fonctionnement par étapes

Voici comment l'algorithme fonctionne étape par étape :

• Étape 1 : Initialisation. Choisir une solution initiale et une température de départ élevée.
• Étape 2 : Génération d'une solution voisine. Une "solution voisine" est obtenue en modifiant légèrement la solution actuelle (par exemple, en changeant une partie de la solution).
• Étape 3 : Calcul de la variation de coût. On évalue si cette nouvelle solution améliore ou dégrade le critère objectif par rapport à la solution actuelle.
• Étape 4 : Décision d'acceptation. Si la nouvelle solution est meilleure, elle est acceptée. Si elle est moins bonne, elle peut tout de même être acceptée avec une probabilité qui dépend de la température et de l'écart de coût entre les deux solutions. Cette probabilité est donnée par une formule basée sur l'équation de Boltzmann :

P = e-ΔE/T

P=e-ΔE/T où ΔE est la différence de coût entre les solutions et T la température actuelle.

• Étape 5 : Réduction de la température. Après chaque itération, la température est abaissée selon un schéma de refroidissement, et le processus est répété jusqu'à ce que la température soit suffisamment basse ou qu'un critère d'arrêt soit atteint.

Avantages du recuit simulé

L'un des grands avantages du recuit simulé est sa capacité à échapper aux minima locaux, grâce à sa possibilité d'accepter des solutions de qualité inférieure au début du processus. Cela en fait une technique puissante pour des problèmes complexes où l'espace de solutions contient de nombreux pics et vallées, par exemple, dans des problèmes de type traveling salesman, la conception de circuits, l'optimisation de portefeuilles financiers, ou la planification de ressources.

Choix des paramètres

La performance du recuit simulé dépend fortement de la température initiale, de la vitesse de refroidissement, et du nombre d'itérations à chaque niveau de température. Un refroidissement trop rapide peut bloquer le système dans un minimum local, tandis qu'un refroidissement trop lent peut rendre l'algorithme trop lent. Ces paramètres sont donc ajustés pour équilibrer vitesse et qualité des solutions.

Applications

Le recuit simulé est utilisé dans divers domaines pour résoudre des problèmes d'optimisation combinatoire, comme :

• Planification : Optimisation des horaires et des ressources dans l'industrie ou les transports.
• Conception électronique : Placement et routage de circuits pour minimiser l'interférence et la consommation d'énergie.
• Logistique : Optimisation de trajets pour les véhicules de livraison, en minimisant les coûts ou le temps de transport.
• Intelligence artificielle et apprentissage automatique : Ajustement de paramètres de modèles ou optimisation des structures neuronales pour obtenir de meilleures performances.

Algorithme

Voici l'algorithme de recuit simulé :