Optimisation stochastique fait référence à l’utilisation du caractère aléatoire dans la fonction objectif ou dans l’algorithme d’optimisation.

Des algorithmes d’optimisation difficiles, tels que des problèmes d’objectifs non linéaires de grande dimension, peuvent contenir plusieurs optima locaux dans lesquels les algorithmes d’optimisation déterministes peuvent rester bloqués.

Les algorithmes d’optimisation stochastique offrent une approche alternative qui permet de prendre des décisions locales moins optimales dans le cadre de la procédure de recherche, ce qui peut augmenter la probabilité que la procédure localise les optima globaux de la fonction objectif.

Dans ce tutoriel, vous découvrirez une introduction douce à l’optimisation stochastique.

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

• Les algorithmes d’optimisation stochastique utilisent le caractère aléatoire dans le cadre de la procédure de recherche.
• Exemples d’algorithmes d’optimisation stochastique tels que le recuit simulé et les algorithmes génétiques.
• Considérations pratiques lors de l’utilisation d’algorithmes d’optimisation stochastique tels que des évaluations répétées.

Commençons.

Présentation du didacticiel

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

1. Qu’est-ce que l’optimisation stochastique?
2. Algorithmes d’optimisation stochastique
3. Considérations pratiques pour l’optimisation stochastique

Qu’est-ce que l’optimisation stochastique?

L’optimisation fait référence aux algorithmes d’optimisation qui recherchent les entrées d’une fonction qui aboutissent au minimum ou au maximum d’une fonction objectif.

L’optimisation stochastique ou la recherche stochastique fait référence à une tâche d’optimisation qui implique le caractère aléatoire d’une certaine manière, par exemple à partir de la fonction objectif ou dans l’algorithme d’optimisation.

La recherche et l’optimisation stochastiques concernent les problèmes où il y a un bruit de hasard dans les mesures fournies à l’algorithme et / ou il y a un caractère aléatoire (Monte Carlo) injecté dans l’algorithme lui-même.

– Page xiii, Introduction à la recherche et à l’optimisation stochastiques, 2003.

Le caractère aléatoire de la fonction objectif signifie que l’évaluation des solutions candidates implique une certaine incertitude ou du bruit et il faut choisir des algorithmes capables de progresser dans la recherche en présence de ce bruit.

Le caractère aléatoire de l’algorithme est utilisé comme stratégie, par exemple des décisions stochastiques ou probabilistes. Il est utilisé comme alternative aux décisions déterministes dans le but d’améliorer la probabilité de localiser les optima globaux ou de meilleurs optima locaux.

Les méthodes d’optimisation stochastique standard sont fragiles, sensibles au choix des étapes et à d’autres paramètres algorithmiques, et elles présentent une instabilité en dehors des familles d’objectifs bien comportés.

– L’importance de meilleurs modèles dans l’optimisation stochastique, 2019.

Il est plus courant de faire référence à un algorithme qui utilise le caractère aléatoire qu’une fonction objective qui contient des évaluations bruyantes lors de l’examen de l’optimisation stochastique. En effet, le caractère aléatoire de la fonction objectif peut être traité en utilisant le caractère aléatoire dans l’algorithme d’optimisation. En tant que telle, l’optimisation stochastique peut être appelée «optimisation robuste. »

Un algorithme déterministe peut être induit en erreur (par exemple “trompé” ou “embrouillé“) Par l’évaluation bruyante de solutions candidates ou de gradients de fonction bruyants, provoquant un rebond de l’algorithme ou un blocage (par exemple, ne parvient pas à converger).

Les méthodes d’optimisation stochastique fournissent un moyen de faire face au bruit inhérent au système et de faire face à des modèles ou des systèmes qui sont hautement non linéaires, de haute dimension ou qui ne conviennent pas aux méthodes d’optimisation déterministes classiques.

– Optimisation stochastique, 2011.

L’utilisation du caractère aléatoire dans un algorithme d’optimisation permet à la procédure de recherche de bien fonctionner sur des problèmes d’optimisation difficiles qui peuvent avoir une surface de réponse non linéaire. Ceci est réalisé par l’algorithme prenant des étapes localement sous-optimales ou se déplaçant dans l’espace de recherche qui lui permettent d’échapper aux optima locaux.

Le caractère aléatoire peut aider à échapper aux optima locaux et augmenter les chances de trouver un optimum global.

– Page 8, Algorithmes d’optimisation, 2019.

Le caractère aléatoire utilisé dans un algorithme d’optimisation stochastique ne doit pas nécessairement être le vrai hasard; au lieu de cela, le pseudo-aléatoire est suffisant. Un générateur de nombres pseudo-aléatoires est presque universellement utilisé dans l’optimisation stochastique.

L’utilisation du caractère aléatoire dans un algorithme d’optimisation stochastique ne signifie pas que l’algorithme est aléatoire. Au lieu de cela, cela signifie que certaines décisions prises au cours de la procédure de recherche impliquent une partie du caractère aléatoire. Par exemple, nous pouvons conceptualiser cela comme le passage du point courant au point suivant dans l’espace de recherche effectué par l’algorithme peut être effectué selon une distribution de probabilité relative au déplacement optimal.

Maintenant que nous avons une idée de ce qu’est l’optimisation stochastique, regardons quelques exemples d’algorithmes d’optimisation stochastique.

Algorithmes d’optimisation stochastique

L’utilisation du caractère aléatoire dans les algorithmes signifie souvent que les techniques sont appelées «recherche heuristique» car elles utilisent une procédure empirique approximative qui peut ou non fonctionner pour trouver les optima au lieu d’une procédure précise.

De nombreux algorithmes stochastiques sont inspirés d’un processus biologique ou naturel et peuvent être appelés «métaheuristiques» en tant que procédure d’ordre supérieur fournissant les conditions d’une recherche spécifique de la fonction objective. Ils sont également appelés «boîte noire”Algorithmes d’optimisation.

La métaheuristique est un terme plutôt malheureux souvent utilisé pour décrire un sous-domaine majeur, voire le sous-domaine primaire, de l’optimisation stochastique.

– Page 7, Essentials of Metaheuristics, 2011.

Il existe de nombreux algorithmes d’optimisation stochastique.

Voici quelques exemples d’algorithmes d’optimisation stochastique:

• Recherche locale itérée
• Escalade stochastique
• Descente de gradient stochastique
• Recherche Tabu
• Procédure de recherche adaptative aléatoire gloutonne

Voici quelques exemples d’algorithmes d’optimisation stochastique inspirés de processus biologiques ou physiques:

• Recuit simulé
• Stratégies d’évolution
• Algorithme génétique
• Évolution différentielle
• Optimisation de l’essaim de particules

Maintenant que nous connaissons quelques exemples d’algorithmes d’optimisation stochastique, examinons quelques considérations pratiques lors de leur utilisation.

Considérations pratiques pour l’optimisation stochastique

Il y a des considérations importantes lors de l’utilisation d’algorithmes d’optimisation stochastique.

La nature stochastique de la procédure signifie que chaque exécution d’un algorithme sera différente, étant donné une source différente de caractère aléatoire utilisée par l’algorithme et, à son tour, des points de départ différents pour la recherche et les décisions prises pendant la recherche.

Le générateur de nombres pseudo-aléatoires utilisé comme source d’aléa peut être amorcé pour garantir que la même séquence de nombres aléatoires est fournie à chaque exécution de l’algorithme. C’est bon pour les petites démonstrations et les didacticiels, bien que cela soit fragile car cela va à l’encontre du caractère aléatoire inhérent à l’algorithme.

Au lieu de cela, un algorithme donné peut être exécuté plusieurs fois pour contrôler le caractère aléatoire de la procédure.

Cette idée d’exécutions multiples de l’algorithme peut être utilisée dans deux situations clés:

• Comparaison d’algorithmes
• Évaluation du résultat final

Les algorithmes peuvent être comparés en fonction de la qualité relative du résultat trouvé, du nombre d’évaluations de fonctions effectuées ou d’une combinaison ou d’une dérivation de ces considérations. Le résultat d’une exécution dépendra du caractère aléatoire utilisé par l’algorithme et ne peut à lui seul représenter de manière significative la capacité de l’algorithme. Au lieu de cela, une stratégie d’évaluation répétée devrait être utilisée.

Toute comparaison entre les algorithmes d’optimisation stochastique nécessitera l’évaluation répétée de chaque algorithme avec une source d’aléatoire différente et le résumé de la distribution de probabilité des meilleurs résultats trouvés, tels que la moyenne et l’écart type des valeurs objectives. Le résultat moyen de chaque algorithme peut alors être comparé.

Dans les cas où plusieurs minima locaux sont susceptibles d’exister, il peut être avantageux d’incorporer des redémarrages aléatoires une fois nos conditions de terminaison remplies, lorsque nous redémarrons notre méthode de descente locale à partir de points initiaux sélectionnés au hasard.

– Page 66, Algorithmes d’optimisation, 2019.

De même, toute exécution unique d’un algorithme d’optimisation choisi seul ne représente pas de manière significative les optima globaux de la fonction objectif. Au lieu de cela, une stratégie d’évaluation répétée devrait être utilisée pour développer une distribution de solutions optimales.

Le maximum ou le minimum de la distribution peut être considéré comme la solution finale, et la distribution elle-même fournira un point de référence et de confiance que la solution trouvée est “relativement bon” ou “assez bien»Compte tenu des ressources dépensées.

• Redémarrage multiple: Une approche pour améliorer la probabilité de localisation des optima globaux via l’application répétée d’un algorithme d’optimisation stochastique à un problème d’optimisation.

L’application répétée d’un algorithme d’optimisation stochastique sur une fonction objectif est parfois appelée stratégie multi-redémarrage et peut être intégrée à l’algorithme d’optimisation lui-même ou prescrite plus généralement comme procédure autour de l’algorithme d’optimisation stochastique choisi.

Chaque fois que vous effectuez un redémarrage aléatoire, le grimpeur se retrouve alors dans un optimum local (éventuellement nouveau).

– Page 26, Essentials of Metaheuristics, 2011.

Lectures complémentaires

Cette section fournit plus de ressources sur le sujet si vous souhaitez approfondir.

Tutoriels connexes

Papiers

Livres

Des articles

Résumé

Dans ce didacticiel, vous avez découvert une introduction douce à l’optimisation stochastique.

Plus précisément, vous avez appris:

• Les algorithmes d’optimisation stochastique utilisent le caractère aléatoire dans le cadre de la procédure de recherche.
• Exemples d’algorithmes d’optimisation stochastique tels que le recuit simulé et les algorithmes génétiques.
• Considérations pratiques lors de l’utilisation d’algorithmes d’optimisation stochastique tels que des évaluations répétées.

Avez-vous des questions?
Posez vos questions dans les commentaires ci-dessous et je ferai de mon mieux pour y répondre.