Ottimizzazione globale dell'evoluzione differenziale con Python

Evoluzione differenziale è un algoritmo di ottimizzazione globale.

È un tipo di algoritmo evolutivo ed è correlato ad altri algoritmi evolutivi come l'algoritmo genetico.

A differenza dell'algoritmo genetico, è stato specificamente progettato per operare su vettori di numeri con valori reali anziché su stringhe di bit. Inoltre, a differenza dell'algoritmo genetico, per navigare nello spazio di ricerca utilizza operazioni vettoriali come la sottrazione e l'addizione invece di trasformazioni ispirate alla genetica.

In questo tutorial scoprirai l'algoritmo di ottimizzazione globale di Differential Evolution.

Dopo aver completato questo tutorial, saprai:

• L'ottimizzazione dell'evoluzione differenziale è un tipo di algoritmo evolutivo progettato per funzionare con soluzioni candidate di valore reale.
• Come utilizzare l'API dell'algoritmo di ottimizzazione dell'evoluzione differenziale in Python.
• Esempi di utilizzo dell'evoluzione differenziale per risolvere problemi di ottimizzazione globale con ottimi multipli.

Avvia il tuo progetto con il mio nuovo libro Ottimizzazione per l'apprendimento automatico, che include tutorial passo passo e i file codice sorgente Python per tutti esempi.

Panoramica dell'esercitazione

Questo tutorial è diviso in tre parti; sono:

1. Evoluzione differenziale
2. API di evoluzione differenziale
3. Esempio elaborato di evoluzione differenziale

Evoluzione differenziale

L'evoluzione differenziale, o DE in breve, è un algoritmo stocastico di ottimizzazione della ricerca globale.

È un tipo di algoritmo evolutivo ed è correlato ad altri algoritmi evolutivi come l'algoritmo genetico. A differenza dell'algoritmo genetico che rappresenta soluzioni candidate utilizzando sequenze di bit, Differential Evolution è progettato per funzionare con soluzioni candidate multidimensionali a valori reali per funzioni obiettivo continue.

L'evoluzione differenziale (DE) è senza dubbio uno dei più potenti algoritmi di ottimizzazione stocastica dei parametri reali attualmente in uso.

— Evoluzione differenziale: un'indagine sullo stato dell'arte, 2011.

L'algoritmo non fa uso di informazioni sul gradiente nella ricerca e, come tale, è particolarmente adatto a funzioni obiettivo non lineari non differenziali.

L'algoritmo funziona mantenendo una popolazione di soluzioni candidate rappresentate come vettori a valori reali. Le nuove soluzioni candidate vengono create realizzando versioni modificate di soluzioni esistenti che poi sostituiscono gran parte della popolazione a ogni iterazione dell'algoritmo.

Le nuove soluzioni candidate vengono create utilizzando una "strategia" che implica la selezione di una soluzione base a cui viene aggiunta una mutazione e altre soluzioni candidate dalla popolazione da cui viene calcolata la quantità e il tipo di mutazione, chiamata vettore differenza. Ad esempio, una strategia può selezionare la migliore soluzione candidata come base e le soluzioni casuali per il vettore di differenza nella mutazione.

DE genera nuovi vettori di parametri aggiungendo la differenza ponderata tra due vettori di popolazione a un terzo vettore.

— Evoluzione differenziale: un'euristica semplice ed efficiente per l'ottimizzazione globale su spazi continui, 1997.

Le soluzioni di base vengono sostituite dai loro figli se i bambini hanno una migliore valutazione della funzione obiettivo.

Infine, dopo aver costruito un nuovo gruppo di bambini, confrontiamo ogni bambino con il genitore che lo ha creato (ogni genitore ha creato un solo figlio). Se il figlio è migliore del genitore, sostituisce il genitore nella popolazione originaria.

— Pagina 51, Elementi essenziali di metaeuristica, 2011.

La mutazione viene calcolata come la differenza tra coppie di soluzioni candidate che risulta in un vettore di differenza che viene quindi aggiunto alla soluzione base, ponderato da un iperparametro del fattore di mutazione impostato nell'intervallo [0,2].

Non tutti gli elementi di una soluzione base sono mutati. Questo viene controllato tramite un iperparametro di ricombinazione ed è spesso impostato su un valore elevato come l'80%, il che significa che la maggior parte ma non tutte le variabili in una soluzione di base vengono sostituite. La decisione di mantenere o sostituire un valore in una soluzione di base viene determinata separatamente per ciascuna posizione campionando una distribuzione di probabilità come binomiale o esponenziale.

Per descrivere le strategie differenziali viene utilizzata una terminologia standard nella forma:

• DE/x/y/z

Dove DE sta per “evoluzione differenziale”, x definisce la soluzione di base che deve essere modificata, come “rand” per casuale o “ migliore” per la migliore soluzione nella popolazione. y rappresenta il numero di vettori di differenza aggiunti alla soluzione base, come 1, e z definisce la distribuzione di probabilità per determinare se ciascuna soluzione viene mantenuta o sostituita nella popolazione, ad esempio "bin" per binomiale o "exp" per esponenziale.

La convenzione generale usata sopra è DE/x/y/z, dove DE sta per “evoluzione differenziale”, x rappresenta una stringa che denota il vettore base da perturbare, y è il numero di vettori differenza considerati per la perturbazione di x e z indica il tipo di crossover utilizzato (exp: esponenziale; bin: binomiale).

— Evoluzione differenziale: un'indagine sullo stato dell'arte, 2011.

La configurazione DE/best/1/bin e DE/best/2/bin sono configurazioni popolari poiché funzionano bene per molte funzioni obiettivo.

Gli esperimenti condotti da Mezura-Montes et al. indicano che DE/best/1/bin (utilizzando sempre la soluzione migliore per trovare le direzioni di ricerca e anche il crossover binomiale) è rimasto lo schema più competitivo, indipendentemente dalle caratteristiche del problema da risolvere, in base all'accuratezza finale e alla robustezza dei risultati.

— Evoluzione differenziale: un'indagine sullo stato dell'arte, 2011.

Ora che abbiamo familiarità con l'algoritmo di evoluzione differenziale, diamo un'occhiata a come potremmo utilizzare l'implementazione dell'API SciPy.

API di evoluzione differenziale

L'algoritmo di ottimizzazione globale di Differential Evolution è disponibile in Python tramite la funzione SciPy differenziale_evolution().

La funzione accetta il nome della funzione obiettivo e i limiti di ciascuna variabile di input come argomenti minimi per la ricerca.

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

Esistono numerosi iperparametri aggiuntivi per la ricerca che hanno valori predefiniti, sebbene sia possibile configurarli per personalizzare la ricerca.

Un iperparametro chiave è l'argomento “strategia” che controlla il tipo di ricerca di evoluzione differenziale eseguita. Per impostazione predefinita, è impostato su "best1bin" (DE/best/1/bin), che è una buona configurazione per la maggior parte dei problemi. Crea nuove soluzioni candidate selezionando soluzioni casuali dalla popolazione, sottraendo l'una dall'altra e aggiungendo una versione in scala della differenza alla migliore soluzione candidata nella popolazione.

• nuovo=migliore + (mutazione * (rand1 - rand2))

L'argomento "popsize" controlla la dimensione o il numero di soluzioni candidate mantenute nella popolazione. È un fattore del numero di dimensioni nelle soluzioni candidate e, per impostazione predefinita, è impostato su 15. Ciò significa che per una funzione obiettivo 2D verrà mantenuta una dimensione della popolazione di (2 * 15) o 30 soluzioni candidate.

Il numero totale di iterazioni dell'algoritmo è mantenuto dall'argomento “maxiter” e il valore predefinito è 1.000.

L'argomento “mutazione” controlla il numero di modifiche apportate alle soluzioni candidate ad ogni iterazione. Per impostazione predefinita, è impostato su 0,5. La quantità di ricombinazione è controllata tramite l'argomento "ricombinazione", che è impostato su 0,7 (70% di una determinata soluzione candidata) per impostazione predefinita.

Infine, viene applicata una ricerca locale alla migliore soluzione candidata trovata al termine della ricerca. Questo è controllato tramite l'argomento “polish”, che per impostazione predefinita è impostato su True.

Il risultato della ricerca è un oggetto OptimizeResult in cui è possibile accedere alle proprietà come un dizionario. È possibile verificare l'esito positivo (o meno) della ricerca tramite la chiave "successo" o "messaggio".

È possibile accedere al numero totale di valutazioni delle funzioni tramite "nfev" e l'input ottimale trovato per la ricerca è accessibile tramite il tasto "x".

Ora che abbiamo familiarità con l'API di evoluzione differenziale in Python, diamo un'occhiata ad alcuni esempi pratici.

Esempio elaborato di evoluzione differenziale

In questa sezione, esamineremo un esempio di utilizzo dell'algoritmo di evoluzione differenziale su una funzione obiettivo complessa.

La funzione di Ackley è un esempio di funzione obiettivo che ha un unico ottimo globale e più ottimi locali in cui una ricerca locale potrebbe bloccarsi.

Pertanto, è necessaria una tecnica di ottimizzazione globale. È una funzione obiettivo bidimensionale che ha un ottimo globale in [0,0], che restituisce 0,0.

L'esempio seguente implementa Ackley e crea un grafico di superficie tridimensionale che mostra gli ottimi globali e gli ottimi locali multipli.

# 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'esecuzione dell'esempio crea il grafico della superficie della funzione Ackley che mostra il vasto numero di ottimi locali.

Possiamo applicare l'algoritmo dell'evoluzione differenziale alla funzione obiettivo di Ackley.

Innanzitutto, possiamo definire i limiti dello spazio di ricerca come i limiti della funzione in ciascuna dimensione.

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

Possiamo quindi applicare la ricerca specificando il nome della funzione obiettivo e i limiti della ricerca. In questo caso utilizzeremo gli iperparametri predefiniti.

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

Al termine della ricerca riporterà lo stato della ricerca e il numero di iterazioni effettuate, nonché il miglior risultato trovato con la relativa valutazione.

...
# 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))

Mettendo insieme tutto ciò, l'esempio completo di applicazione dell'evoluzione differenziale alla funzione obiettivo di Ackley è elencato di seguito.

# 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'esecuzione dell'esempio esegue l'ottimizzazione, quindi riporta i risultati.

Nota: i risultati possono variare a causa della natura stocastica dell'algoritmo o della procedura di valutazione o delle differenze nella precisione numerica. Considera l'idea di eseguire l'esempio alcune volte e confrontare il risultato medio.

In questo caso, possiamo vedere che l'algoritmo ha individuato l'ottimale con input uguali a zero e una valutazione della funzione obiettivo uguale a zero.

Possiamo vedere che sono state eseguite un totale di 3.063 valutazioni funzionali.

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

Ulteriori letture

Questa sezione fornisce più risorse sull'argomento se desideri approfondire.

Carte

• Evoluzione differenziale: un'euristica semplice ed efficiente per l'ottimizzazione globale su spazi continui, 1997.
• Evoluzione differenziale: un'indagine sullo stato dell'arte, 2011.

Libri

• Algoritmi per l'ottimizzazione, 2019.
• Elementi essenziali di metaeuristica, 2011.
• Intelligenza computazionale: un'introduzione, 2007.

API

• API scipy.optimize.differential_evolution.
• API scipy.optimize.OptimizeResult.

Articoli

• Evoluzione differenziale, Wikipedia.

Riepilogo

In questo tutorial hai scoperto l'algoritmo di ottimizzazione globale di Differential Evolution.

Nello specifico, hai imparato:

• L'ottimizzazione dell'evoluzione differenziale è un tipo di algoritmo evolutivo progettato per funzionare con soluzioni candidate di valore reale.
• Come utilizzare l'API dell'algoritmo di ottimizzazione dell'evoluzione differenziale in Python.
• Esempi di utilizzo dell'evoluzione differenziale per risolvere problemi di ottimizzazione globale con ottimi multipli.

Hai qualche domanda?
Poni le tue domande nei commenti qui sotto e farò del mio meglio per rispondere.