Optimisation locale et optimisation globale

Actualités de de l'Intelligence Artificielle - Machine Learning - Objets connectés

Optimisation locale et optimisation globale


L’optimisation fait référence à la recherche de l’ensemble des entrées d’une fonction objectif qui aboutit à la sortie maximale ou minimale de la fonction objectif.

Il est courant de décrire les problèmes d’optimisation en termes de optimisation locale vs globale.

De même, il est également courant de décrire des algorithmes d’optimisation ou des algorithmes de recherche en termes de recherche locale ou globale.

Dans ce didacticiel, vous découvrirez les différences pratiques entre l’optimisation locale et globale.

Après avoir terminé ce tutoriel, vous saurez:

  • L’optimisation locale consiste à trouver la solution optimale pour une région spécifique de l’espace de recherche, ou les optima globaux pour les problèmes sans optima locaux.
  • L’optimisation globale consiste à trouver la solution optimale aux 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.

Commençons.

Optimisation locale et optimisation globale

Optimisation locale et optimisation globale
Photo de Marco Verch, certains droits réservés.

Présentation du didacticiel

Ce tutoriel est divisé en trois parties; elles sont:

  1. Optimisation locale
  2. Optimisation globale
  3. Optimisation locale ou globale

Optimisation locale

Un optima local est l’extrema (minimum ou maximum) de la fonction objectif pour une région donnée de l’espace d’entrée, par exemple un bassin dans un problème de minimisation.

… Nous cherchons un point qui n’est optimal que localement, ce qui signifie qu’il minimise la fonction objectif parmi les points réalisables qui en sont proches…

– Page 9, Optimisation convexe, 2004.

Une fonction objectif peut avoir de nombreux 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 la recherche locale fait référence à la recherche des optima locaux.

Un algorithme d’optimisation local, également appelé algorithme de recherche locale, est un algorithme destiné à localiser un optima 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, sinon 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 la modification pour voir si elle conduit à une amélioration et est considérée comme la nouvelle solution candidate.

Un algorithme d’optimisation local localisera l’optimum global:

  • Si les optima locaux sont les optima globaux, ou
  • Si la région recherchée contient les optima globaux.

Celles-ci définissent les cas d’utilisation idéaux pour l’utilisation d’un algorithme de recherche locale.

Il peut y avoir 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 Nelder-Mead
  • Algorithme BFGS
  • Algorithme d’escalade

Maintenant que nous sommes familiarisés avec l’optimisation locale, jetons un coup d’œil à l’optimisation globale.

Optimisation globale

Un optimum global est les extrema (minimum ou maximum) de la fonction objectif pour tout l’espace de recherche d’entrée.

Optimisation globale, où l’algorithme recherche l’optimum global en utilisant 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 optimum aura une entrée différente et la même évaluation de fonction objective.

  • Optimisation globale: Localisez les optima pour une fonction objectif qui peut contenir des optima locaux.

Une fonction objective a toujours un optima 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 objective qui n’est pas aussi bonne que les optima globaux.

Les optima globaux peuvent être les mêmes que les optima locaux, auquel cas il serait plus approprié de désigner le problème d’optimisation comme une optimisation locale, plutôt que comme une optimisation globale.

La présence des optima locaux est une composante majeure 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, est destiné à localiser un optima 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 les problèmes avec un petit nombre de variables, où le temps de calcul n’est pas critique, et la valeur de trouver la vraie solution globale est très élevée.

– 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 considérées comme le nouvel état de fonctionnement.

Il peut y avoir un débat sur ce qui constitue exactement un algorithme de recherche globale; néanmoins, trois exemples d’algorithmes de recherche globale utilisant nos définitions incluent:

  • Algorithme génétique
  • Recuit simulé
  • Optimisation de l’essaim de particules

Maintenant que nous sommes familiarisés avec l’optimisation globale et locale, comparons et opposons les deux.

Optimisation locale ou globale

Les algorithmes d’optimisation de la recherche locale et globale 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 exemple unimodal.

Un algorithme d’optimisation globale doit être utilisé lorsque vous en savez très peu sur la structure de la surface de réponse de la fonction objective, 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 un optimum global.

– Page 37, Intelligence computationnelle: une introduction, 2007.

L’application d’un algorithme de recherche local à 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 vous savez qu’il existe des optima locaux.

Les algorithmes de recherche locaux donnent souvent des subventions de complexité de calcul liées à la localisation des optima globaux, tant que les hypothèses faites par l’algorithme sont valables.

Les algorithmes de recherche globale donnent souvent très peu ou pas de bénéficiaires pour localiser les optima globaux. En tant que telle, la recherche globale est souvent utilisée sur des problèmes suffisamment difficiles pour que « bien » ou « assez bien«Les solutions sont préférables à aucune solution. Cela peut signifier des optima locaux relativement bons au lieu des vrais optima globaux si la localisation des optima globaux est insoluble.

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 s’assurer que des solutions relativement bonnes ont été localisées.

  • Recherche locale: Pour des problèmes étroits où la solution globale est requise
  • Recherche globale: Pour des problèmes généraux où 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 exemple si un algorithme de recherche local ou global est le plus approprié. Par conséquent, il peut être souhaitable d’établir une ligne de base des performances avec un algorithme de recherche local, puis d’explorer un algorithme de recherche global pour voir s’il peut fonctionner mieux. 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 local.

  • Meilleur entrainement: Établissez une base de référence avec une recherche locale puis explorez une recherche globale sur des fonctions objectives où on en sait peu.

L’optimisation locale est un problème plus simple à résoudre que l’optimisation globale. En tant que tel, la grande majorité de la recherche sur l’optimisation mathématique s’est concentrée 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, permettant d’éviter les minima 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 de bons optima locaux ou pour les optima globaux, mais peuvent ne pas être en mesure de localiser la meilleure solution dans le bassin.

Les techniques d’optimisation locale et globale peuvent être combinées pour former des algorithmes d’entraînement hybrides.

– Page 37, Intelligence computationnelle: une introduction, 2007.

Par conséquent, il est recommandé d’appliquer une recherche locale aux solutions optima candidates trouvées par un algorithme de recherche globale.

  • Meilleur entrainement: Appliquer 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

Des articles

Sommaire

Dans ce didacticiel, vous avez découvert les différences pratiques entre l’optimisation locale et globale.

Plus précisément, vous avez appris:

  • L’optimisation locale consiste à trouver la solution optimale pour une région spécifique de l’espace de recherche, ou les optima globaux pour les problèmes sans optima locaux.
  • L’optimisation globale consiste à trouver la solution optimale aux 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.