Optimisation globale de l'évolution différentielle avec Python

Differential Evolution est un algorithme d'optimisation global.

C'est un type d'algorithme évolutif et est lié à d'autres algorithmes évolutifs tels que l'algorithme génétique.

Contrairement à l’algorithme génétique, il a été spécialement conçu pour fonctionner sur des vecteurs de nombres à valeur réelle plutôt que sur des chaînes de bits. Contrairement à l'algorithme génétique, il utilise des opérations vectorielles telles que la soustraction et l'addition de vecteurs pour naviguer dans l'espace de recherche au lieu de transformations inspirées de la génétique.

Dans ce tutoriel, vous découvrirez l’algorithme d’optimisation globale Differential Evolution.

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

• L'optimisation de l'évolution différentielle est un type d'algorithme évolutif conçu pour fonctionner avec des solutions candidates à valeur réelle.
• Comment utiliser l'API de l'algorithme d'optimisation Differential Evolution en python.
• Exemples d'utilisation de l'évolution différentielle pour résoudre des problèmes d'optimisation globale avec plusieurs optima.

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:

1. Evolution différentielle
2. API d'évolution différentielle
3. Exemple concret d'évolution différentielle

Evolution différentielle

Differential Evolution, ou DE en abrégé, est un algorithme d'optimisation de recherche globale stochastique.

C'est un type d'algorithme évolutif et est lié à d'autres algorithmes évolutifs tels que l'algorithme génétique. Contrairement à l'algorithme génétique qui représente les solutions candidates à l'aide de séquences de bits, l'évolution différentielle est conçue pour fonctionner avec des solutions candidates multidimensionnelles à valeur réelle pour des fonctions objectives continues.

L'évolution différentielle (DE) est sans doute l'un des algorithmes d'optimisation stochastique de paramètres réels les plus puissants actuellement utilisés.

— Évolution différentielle : une étude de l'état de l'art, 2011.

L'algorithme n'utilise pas d'informations de gradient dans la recherche et, en tant que tel, est bien adapté aux fonctions objectives non linéaires non différentielles.

L'algorithme fonctionne en maintenant une population de solutions candidates représentées sous forme de vecteurs à valeurs réelles. De nouvelles solutions candidates sont créées en créant des versions modifiées de solutions existantes qui remplacent ensuite une grande partie de la population à chaque itération de l'algorithme.

De nouvelles solutions candidates sont créées à l'aide d'une « stratégie » qui implique la sélection d'une solution de base à laquelle une mutation est ajoutée, ainsi que d'autres solutions candidates de la population à partir de laquelle la quantité et le type de mutation sont calculés, appelées solutions candidates. vecteur de différence. Par exemple, une stratégie peut sélectionner une meilleure solution candidate comme solution de base et des solutions aléatoires pour le vecteur différence dans la mutation.

DE génère de nouveaux vecteurs de paramètres en ajoutant la différence pondérée entre deux vecteurs de population à un troisième vecteur.

— Evolution différentielle : une heuristique simple et efficace pour l'optimisation globale sur des espaces continus, 1997.

Les solutions de base sont remplacées par leurs enfants si les enfants ont une meilleure évaluation fonctionnelle objective.

Enfin, après avoir constitué un nouveau groupe d'enfants, nous comparons chaque enfant avec le parent qui l'a créé (chaque parent a créé un seul enfant). Si l'enfant est meilleur que le parent, il remplace le parent dans la population d'origine.

— Page 51, Essentiels de la métaheuristique, 2011.

La mutation est calculée comme la différence entre des paires de solutions candidates qui aboutit à un vecteur de différence qui est ensuite ajouté à la solution de base, pondéré par un hyperparamètre de facteur de mutation défini dans la plage [0,2].

Tous les éléments d’une solution de base ne sont pas mutés. Ceci est contrôlé via un hyperparamètre de recombinaison et est souvent défini sur une valeur élevée telle que 80 %, ce qui signifie que la plupart des variables d'une solution de base, mais pas toutes, sont remplacées. La décision de conserver ou de remplacer une valeur dans une solution de base est déterminée pour chaque position séparément en échantillonnant une distribution de probabilité telle qu'une distribution binomiale ou exponentielle.

Une terminologie standard est utilisée pour décrire les stratégies différentielles sous la forme :

• DE/x/y/z

Où DE signifie « évolution différentielle », x définit la solution de base qui doit être muté, comme « rand » pour aléatoire ou « best » pour la meilleure solution au sein de la population. Le y représente le nombre de vecteurs de différence ajoutés à la solution de base, par exemple 1, et z définit la distribution de probabilité pour déterminer si chaque solution est conservée ou remplacée dans la population, comme « bin » pour binomial ou « exp » pour exponentiel.

La convention générale utilisée ci-dessus est DE/x/y/z, où DE signifie « évolution différentielle », x représente une chaîne désignant le vecteur de base à perturber, y est le nombre de vecteurs de différence pris en compte pour la perturbation de x et z. représente le type de croisement utilisé (exp : exponentiel ; bin : binomial).

— Évolution différentielle : une étude de l'état de l'art, 2011.

Les configurations DE/best/1/bin et DE/best/2/bin sont des configurations populaires car elles fonctionnent bien pour de nombreuses fonctions objectives.

Les expériences réalisées par Mezura-Montes et al. indiquent que DE/best/1/bin (en utilisant toujours la meilleure solution pour trouver les directions de recherche et également le croisement binomial) reste le schéma le plus compétitif, quelles que soient les caractéristiques du problème à résoudre, sur la base de l'exactitude finale et de la robustesse des résultats.

— Évolution différentielle : une étude de l'état de l'art, 2011.

Maintenant que nous sommes familiers avec l'algorithme d'évolution différentielle, voyons comment nous pourrions utiliser l'implémentation de l'API SciPy.

API d'évolution différentielle

L'algorithme d'optimisation globale Differential Evolution est disponible en Python via la fonction SciPy différentiel_evolution().

La fonction prend le nom de la fonction objectif et les limites de chaque variable d'entrée comme arguments minimaux pour la recherche.

...
# perform the differential evolution search
result = differential_evolution(objective, bounds)

Il existe un certain nombre d'hyperparamètres supplémentaires pour la recherche qui ont des valeurs par défaut, bien que vous puissiez les configurer pour personnaliser la recherche.

Un hyperparamètre clé est l'argument « stratégie » qui contrôle le type de recherche d'évolution différentielle effectuée. Par défaut, celui-ci est défini sur « best1bin » (DE/best/1/bin), ce qui constitue une bonne configuration pour la plupart des problèmes. Il crée de nouvelles solutions candidates en sélectionnant des solutions aléatoires dans la population, en soustrayant les unes des autres et en ajoutant une version mise à l'échelle de la différence à la meilleure solution candidate dans la population.

• nouveau=meilleur + (mutation * (rand1 - rand2))

L'argument « popsize » contrôle la taille ou le nombre de solutions candidates conservées dans la population. Il s'agit d'un facteur du nombre de dimensions dans les solutions candidates et par défaut, il est défini sur 15. Cela signifie que pour une fonction objectif 2D, une taille de population de (2 * 15) ou 30 solutions candidates sera maintenue.

Le nombre total d'itérations de l'algorithme est maintenu par l'argument « maxiter » et est par défaut de 1 000.

L'argument « mutation » contrôle le nombre de modifications apportées aux solutions candidates à chaque itération. Par défaut, cette valeur est définie sur 0,5. Le degré de recombinaison est contrôlé via l'argument « recombinaison », qui est défini par défaut sur 0,7 (70 % d'une solution candidate donnée).

Enfin, une recherche locale est appliquée à la meilleure solution candidate trouvée à l'issue de la recherche. Ceci est contrôlé via l'argument « polish », qui est défini par défaut sur True.

Le résultat de la recherche est un objet OptimizeResult dont les propriétés sont accessibles comme un dictionnaire. Le succès (ou non) de la recherche est accessible via la touche 'succès' ou 'message'.

Le nombre total d'évaluations de fonctions est accessible via « nfev » et l'entrée optimale trouvée pour la recherche est accessible via la touche « x ».

Maintenant que nous connaissons l’API d’évolution différentielle en Python, examinons quelques exemples concrets.

Exemple concret d'évolution différentielle

Dans cette section, nous examinerons un exemple d'utilisation de l'algorithme d'évolution différentielle sur une fonction objectif difficile.

La fonction Ackley est un exemple de fonction objectif qui a un seul optimal global et plusieurs optima locaux dans lesquels une recherche locale peut rester bloquée.

Une technique d’optimisation globale est donc nécessaire. Il s'agit d'une fonction objectif bidimensionnelle qui a un optimal global à [0,0], qui est évalué à 0,0.

L'exemple ci-dessous implémente Ackley et crée un tracé de surface tridimensionnel montrant les optima globaux et plusieurs optima locaux.

# ackley multimodal function
from numpy import arange
from numpy import exp
from numpy import sqrt
from numpy import cos
from numpy import e
from numpy import pi
from numpy import meshgrid
from matplotlib import pyplot
from mpl_toolkits.mplot3d import Axes3D

# objective function
def objective(x, y):
	return -20.0 * exp(-0.2 * sqrt(0.5 * (x**2 + y**2))) - exp(0.5 * (cos(2 * pi * x) + cos(2 * pi * y))) + e + 20

# define range for input
r_min, r_max = -5.0, 5.0
# sample input range uniformly at 0.1 increments
xaxis = arange(r_min, r_max, 0.1)
yaxis = arange(r_min, r_max, 0.1)
# create a mesh from the axis
x, y = meshgrid(xaxis, yaxis)
# compute targets
results = objective(x, y)
# create a surface plot with the jet color scheme
figure = pyplot.figure()
axis = figure.gca(projection='3d')
axis.plot_surface(x, y, results, cmap='jet')
# show the plot
pyplot.show()

L'exécution de l'exemple crée le tracé de surface de la fonction Ackley montrant le grand nombre d'optimums locaux.

Nous pouvons appliquer l'algorithme d'évolution différentielle à la fonction objectif d'Ackley.

Premièrement, nous pouvons définir les limites de l’espace de recherche comme les limites de la fonction dans chaque dimension.

...
# define the bounds on the search
bounds = [[r_min, r_max], [r_min, r_max]]

On peut alors appliquer la recherche en précisant le nom de la fonction objectif et les limites de la recherche. Dans ce cas, nous utiliserons les hyperparamètres par défaut.

...
# perform the differential evolution search
result = differential_evolution(objective, bounds)

Une fois la recherche terminée, il indiquera l'état de la recherche et le nombre d'itérations effectuées, ainsi que le meilleur résultat trouvé lors de son évaluation.

...
# summarize the result
print('Status : %s' % result['message'])
print('Total Evaluations: %d' % result['nfev'])
# evaluate solution
solution = result['x']
evaluation = objective(solution)
print('Solution: f(%s) = %.5f' % (solution, evaluation))

En reliant cela ensemble, l'exemple complet d'application de l'évolution différentielle à la fonction objectif d'Ackley est répertorié ci-dessous.

# differential evolution global optimization for the ackley multimodal objective function
from scipy.optimize import differential_evolution
from numpy.random import rand
from numpy import exp
from numpy import sqrt
from numpy import cos
from numpy import e
from numpy import pi

# objective function
def objective(v):
	x, y = v
	return -20.0 * exp(-0.2 * sqrt(0.5 * (x**2 + y**2))) - exp(0.5 * (cos(2 * pi * x) + cos(2 * pi * y))) + e + 20

# define range for input
r_min, r_max = -5.0, 5.0
# define the bounds on the search
bounds = [[r_min, r_max], [r_min, r_max]]
# perform the differential evolution search
result = differential_evolution(objective, bounds)
# summarize the result
print('Status : %s' % result['message'])
print('Total Evaluations: %d' % result['nfev'])
# evaluate solution
solution = result['x']
evaluation = objective(solution)
print('Solution: f(%s) = %.5f' % (solution, evaluation))

L'exécution de l'exemple exécute l'optimisation, puis rapporte les résultats.

Remarque : Vos résultats peuvent varier en raison de la nature stochastique de l'algorithme ou de la procédure d'évaluation, ou des différences de précision numérique. Pensez à exécuter l’exemple plusieurs fois et comparez le résultat moyen.

Dans ce cas, nous pouvons voir que l'algorithme a localisé les optima avec des entrées égales à zéro et une évaluation de fonction objectif égale à zéro.

Nous pouvons constater qu’un total de 3 063 évaluations fonctionnelles ont été réalisées.

Status: Optimization terminated successfully.
Total Evaluations: 3063
Solution: f([0. 0.]) = 0.00000

Lectures complémentaires

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

Papiers

• Evolution différentielle - Une heuristique simple et efficace pour l'optimisation globale sur des espaces continus, 1997.
• Évolution différentielle : une étude de l'état de l'art, 2011.

Livres

• Algorithmes d'optimisation, 2019.
• Essentiels de la métaheuristique, 2011.
• Intelligence computationnelle : une introduction, 2007.

Apis

• API scipy.optimize.différential_evolution.
• API scipy.optimize.OptimizeResult.

Articles

• Evolution différentielle, Wikipédia.

Résumé

Dans ce tutoriel, vous avez découvert l'algorithme d'optimisation globale Differential Evolution.

Concrètement, vous avez appris :

• L'optimisation de l'évolution différentielle est un type d'algorithme évolutif conçu pour fonctionner avec des solutions candidates à valeur réelle.
• Comment utiliser l'API de l'algorithme d'optimisation Differential Evolution en python.
• Exemples d'utilisation de l'évolution différentielle pour résoudre des problèmes d'optimisation globale avec plusieurs optima.

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