Optimisation locale versus optimisation globale
L'optimisation fait référence à la recherche de l'ensemble des entrées d'une fonction objectif qui aboutit au résultat maximum ou minimum de la fonction objectif.
Il est courant de décrire les problèmes d'optimisation en termes d'optimisation locale ou globale.
De même, il est également courant de décrire les algorithmes d’optimisation ou les algorithmes de recherche en termes de recherche locale ou globale.
Dans ce tutoriel, vous découvrirez les différences pratiques entre l'optimisation locale et globale.
Après avoir terminé ce tutoriel, vous saurez :
- L'optimisation locale implique de trouver la solution optimale pour une région spécifique de l'espace de recherche, ou l'optima global pour les problèmes sans optimal local.
- L'optimisation globale consiste à trouver la solution optimale à des problèmes contenant des optima locaux.
- Comment et quand utiliser les algorithmes de recherche locaux et globaux et comment utiliser les deux méthodes de concert.
Démarrez votre projet avec mon nouveau livre Optimization for Machine Learning, comprenant des tutoriels pas à pas et les fichiers code source Python pour tous exemples.
Présentation du didacticiel
Ce didacticiel est divisé en trois parties : ils sont:
- Optimisation locale
- Optimisation globale
- Optimisation locale ou globale
Optimisation locale
Un optimal local est l'extrema (minimum ou maximum) de la fonction objectif pour une région donnée de l'espace d'entrée, par ex. un bassin dans un problème de minimisation.
… nous recherchons un point qui n’est que localement optimal, ce qui signifie qu’il minimise la fonction objectif parmi les points réalisables qui lui sont proches…
— Page 9, Optimisation convexe, 2004.
Une fonction objectif peut avoir plusieurs optima locaux, ou elle peut avoir un seul optima local, auquel cas les optima locaux sont également les optima globaux.
- Optimisation locale : localisez les optima pour une fonction objectif à partir d'un point de départ censé contenir les optima (par exemple, un bassin).
L'optimisation locale ou recherche locale fait référence à la recherche des optima locaux.
Un algorithme d'optimisation locale, également appelé algorithme de recherche locale, est un algorithme destiné à localiser un optimal local. Il est adapté pour parcourir une région donnée de l’espace de recherche et se rapprocher (ou trouver exactement) les extrema de la fonction dans cette région.
… les méthodes d’optimisation locale sont largement utilisées dans les applications où il est utile de trouver un bon point, voire le meilleur.
— Page 9, Optimisation convexe, 2004.
Les algorithmes de recherche locale fonctionnent généralement sur une seule solution candidate et impliquent d'apporter de manière itérative de petites modifications à la solution candidate et d'évaluer le changement pour voir s'il conduit à une amélioration et s'il est considéré comme la nouvelle solution candidate.
Un algorithme d'optimisation local localisera l'optimum global :
- Si l'optima local est l'optima global, ou
- Si la région recherchée contient les optima globaux.
Ceux-ci définissent les cas d’utilisation idéaux pour l’utilisation d’un algorithme de recherche locale.
Il peut y avoir un débat sur ce qui constitue exactement un algorithme de recherche locale ; néanmoins, trois exemples d'algorithmes de recherche locale utilisant nos définitions incluent :
- Algorithme de Nelder-Mead
- Algorithme BFGS
- Algorithme d'escalade
Maintenant que nous connaissons l’optimisation locale, intéressons-nous à l’optimisation globale.
Optimisation globale
Un optimal global est l'extrema (minimum ou maximum) de la fonction objectif pour l'ensemble de l'espace de recherche d'entrée.
Optimisation globale, où l'algorithme recherche l'optimum global en employant des mécanismes pour rechercher de plus grandes parties de l'espace de recherche.
— Page 37, Intelligence computationnelle : une introduction, 2007.
Une fonction objectif peut avoir un ou plusieurs optima globaux, et s'il y en a plusieurs, on parle de problème d'optimisation multimodale et chaque optimal aura une entrée différente et la même évaluation de fonction objectif.
- Optimisation globale : recherchez les optima d'une fonction objectif pouvant contenir des optima locaux.
Une fonction objectif a toujours un optimal global (sinon nous ne serions pas intéressés à l'optimiser), bien qu'elle puisse également avoir des optima locaux qui ont une évaluation de fonction objectif qui n'est pas aussi bonne que l'optima global.
Les optima globaux peuvent être les mêmes que les optima locaux, auquel cas il serait plus approprié de qualifier le problème d’optimisation d’optimisation locale plutôt que d’optimisation globale.
La présence des optima locaux est un élément majeur de ce qui définit la difficulté d'un problème d'optimisation globale car il peut être relativement facile de localiser un optima local et relativement difficile de localiser les optima globaux.
L'optimisation globale ou recherche globale fait référence à la recherche des optima globaux.
Un algorithme d'optimisation globale, également appelé algorithme de recherche globale, a pour but de localiser un optimal global. Il est adapté pour parcourir tout l’espace de recherche d’entrée et se rapprocher (ou trouver exactement) les extrema de la fonction.
L'optimisation globale est utilisée pour des problèmes avec un petit nombre de variables, pour lesquels le temps de calcul n'est pas critique et où l'intérêt de trouver la véritable solution globale est très élevé.
— Page 9, Optimisation convexe, 2004.
Les algorithmes de recherche globale peuvent impliquer la gestion d'une seule ou d'une population de solutions candidates à partir desquelles de nouvelles solutions candidates sont générées et évaluées de manière itérative pour voir si elles aboutissent à une amélioration et sont prises comme nouvel état de fonctionnement.
Il peut y avoir un débat sur ce qui constitue exactement un algorithme de recherche global ; néanmoins, trois exemples d'algorithmes de recherche globale utilisant nos définitions incluent :
- Algorithme génétique
- Recuit simulé
- Optimisation des essaims de particules
Maintenant que nous sommes familiers avec l’optimisation globale et locale, comparons les deux.
Optimisation locale ou globale
Les algorithmes d'optimisation de recherche locaux et globaux résolvent différents problèmes ou répondent à différentes questions.
Un algorithme d'optimisation local doit être utilisé lorsque vous savez que vous êtes dans la région des optima globaux ou que votre fonction objectif contient un seul optima, par ex. unimodal.
Un algorithme d'optimisation globale doit être utilisé lorsque vous connaissez très peu la structure de la surface de réponse de la fonction objectif, ou lorsque vous savez que la fonction contient des optima locaux.
Optimisation locale, où l'algorithme peut rester bloqué dans un optimum local sans trouver d'optimum global.
— Page 37, Intelligence computationnelle : une introduction, 2007.
L'application d'un algorithme de recherche locale à un problème qui nécessite un algorithme de recherche global donnera de mauvais résultats car la recherche locale sera capturée (trompée) par les optima locaux.
- Recherche locale : lorsque vous êtes dans la région des optima globaux.
- Recherche globale : quand on sait qu'il existe des optima locaux.
Les algorithmes de recherche locale donnent souvent aux bénéficiaires une complexité de calcul liée à la localisation des optima globaux, tant que les hypothèses formulées par l'algorithme sont valables.
Les algorithmes de recherche globale donnent souvent très peu, voire aucun, aux bénéficiaires de la localisation des optima globaux. En tant que telle, la recherche globale est souvent utilisée sur des problèmes suffisamment difficiles pour que des solutions « bonnes » ou « assez bonnes » soient préférées à aucune solution du tout. Cela pourrait signifier des optima locaux relativement bons au lieu des véritables optima globaux si la localisation des optima globaux est difficile à résoudre.
Il est souvent approprié de réexécuter ou de redémarrer l'algorithme plusieurs fois et d'enregistrer les optima trouvés par chaque exécution pour donner l'assurance que des solutions relativement bonnes ont été trouvées.
- Recherche locale : pour des problèmes précis nécessitant une solution globale.
- Recherche globale : pour les problèmes généraux pour lesquels les optima globaux pourraient être insolubles.
Nous savons souvent très peu de choses sur la surface de réponse pour une fonction objective, par ex. si un algorithme de recherche local ou global est le plus approprié. Par conséquent, il peut être souhaitable d’établir une référence en matière de performances avec un algorithme de recherche local, puis d’explorer un algorithme de recherche global pour voir s’il peut être plus performant. Si ce n’est pas le cas, cela peut suggérer que le problème est effectivement unimodal ou approprié pour un algorithme de recherche locale.
- Meilleure pratique : établissez une base de référence avec une recherche locale, puis explorez une recherche globale sur des fonctions objectives là où on sait peu de choses.
L'optimisation locale est un problème plus simple à résoudre que l'optimisation globale. Ainsi, la grande majorité des recherches sur l’optimisation mathématique se sont concentrées sur les techniques de recherche locale.
Une grande partie de la recherche sur la programmation non linéaire générale s'est concentrée sur les méthodes d'optimisation locale, qui sont par conséquent bien développées.
— Page 9, Optimisation convexe, 2004.
Les algorithmes de recherche globale sont souvent grossiers dans leur navigation dans l’espace de recherche.
De nombreuses méthodes de population fonctionnent bien dans la recherche globale, étant capables d'éviter les minimums locaux et de trouver les meilleures régions de l'espace de conception. Malheureusement, ces méthodes ne fonctionnent pas aussi bien dans la recherche locale que les méthodes de descente.
— Page 162, Algorithmes d'optimisation, 2019.
En tant que tels, ils peuvent localiser le bassin pour un bon optimal local ou un optimal global, mais peuvent ne pas être en mesure de localiser la meilleure solution dans le bassin.
Les techniques d'optimisation locales et globales peuvent être combinées pour former des algorithmes de formation hybrides.
— Page 37, Intelligence computationnelle : une introduction, 2007.
Par conséquent, c’est une bonne pratique d’appliquer une recherche locale aux solutions candidates optimales trouvées par un algorithme de recherche global.
- Bonne pratique : appliquez une recherche locale aux solutions trouvées par une recherche globale.
Lectures complémentaires
Cette section fournit plus de ressources sur le sujet si vous souhaitez approfondir.
Livres
- Optimisation convexe, 2004.
- Intelligence computationnelle : une introduction, 2007.
- Algorithmes d'optimisation, 2019.
Articles
- Recherche locale (optimisation), Wikipédia.
- Optimisation globale, Wikipédia.
Résumé
Dans ce didacticiel, vous avez découvert les différences pratiques entre l'optimisation locale et globale.
Concrètement, vous avez appris :
- L'optimisation locale implique de trouver la solution optimale pour une région spécifique de l'espace de recherche, ou l'optima global pour les problèmes sans optimal local.
- L'optimisation globale consiste à trouver la solution optimale à des problèmes contenant des optima locaux.
- Comment et quand utiliser les algorithmes de recherche locaux et globaux et comment utiliser les deux méthodes de concert.
Avez-vous des questions ?
Posez vos questions dans les commentaires ci-dessous et je ferai de mon mieux pour y répondre.