Il presente articolo è stato tradotto automaticamente.
Esecuzione di test
FAO (Fireworks Algorithm Optimization)
Scaricare il codice di esempio
.jpg)
Macchina molti software ottimizzazione sistemi numerici di uso di apprendimento. Ad esempio, nella classificazione di regressione logistica, il classificatore di formazione è il processo di individuazione di un insieme di valori per i pesi associati alle variabili di ingresso così che per un insieme di dati di addestramento, i valori di output computata strettamente corrispondono ai valori di variabile di uscita noto. In altre parole, l'obiettivo è quello di ottimizzare (ridurre) l'errore fra calcolata e voluta valori di output.
Esistono molti algoritmi di ottimizzazione numerica differente. Retro-propagazione si basa su tecniche di calcolo classico e viene spesso utilizzato con reti neurali. Ottimizzazione sciame di particelle imita il comportamento del gruppo come il floccaggio di uccelli. Modelli di ottimizzazione algoritmo evolutivo, una forma di ottimizzazione algoritmo genetico, i processi biologici di replicazione del cromosoma.
Questo articolo descrive un relativamente nuovo (pubblicato nel 2010) tecnica di ottimizzazione chiamata ottimizzazione algoritmo di fuochi d'artificio (FAO). La tecnica non esplicitamente modellare o simulare il comportamento di fuochi d'artificio, ma quando l'algoritmo viene visualizzata graficamente, l'immagine risultante ricorda la geometria di esplodere fuochi d'artificio.
Il modo migliore per vedere dove è diretto questo articolo e per avere un'idea di ciò che la FAO, è quello di dare un'occhiata al programma demo in Figura 1. L'obiettivo del programma demo è utilizzare FAO per trovare il valore minimo della funzione di Ackley con 10 variabili. Funzione di Ackley è un benchmark standard per valutare l'efficacia degli algoritmi di ottimizzazione numerica. La versione demo ha un valore minimo pari a 0.0, situato a (0, 0, 0, 0, 0, 0, 0, 0, 0, 0). Funzione di Ackley è difficile perché ha molte soluzioni di minimi locali che possono intrappolare algoritmi di ricerca prima di trovare un minimo globale. È mostrato un grafico di funzione di Ackley di due variabili Figura 2.
.png "Fireworks ottimizzazione di algoritmo in azione")
Figura 1 Fireworks ottimizzazione di algoritmo in azione
.png "Funzione di Ackley di due variabili")
Funzione di figura 2 Ackley di due variabili
Il programma demo imposta il numero di fuochi d'artificio a 5. Fuochi d'artificio più aumenta le possibilità di trovare una vera soluzione ottima, a scapito delle prestazioni. FAO in genere funziona bene con i fuochi d'artificio 3 a 10. La FAO è un processo iterativo e richiede un valore di contatore ciclo massimo. Una variabile contatore di ciclo nell'ottimizzazione di apprendimento macchina spesso è denominato "epoca" e la demo imposta il valore massimo di 1.000 iterazioni. Questo è un po ' piccolo, destinate a scopo dimostrativo, ed in scenari realistici, valori da 10.000 a 100.000 sono tipici.
Nella demo eseguito Figura 1, migliore (più piccolo) errore associato alla posizione migliore finora trovata viene visualizzato ogni 100 epoche. Si noti che la FAO inizia molto rapidamente convergenti. Dopo 1.000 epoche, è la posizione migliore trovata (0,034 0,098 0,003 0,132-0.054-0.018 0,181 0.051-0.023 0,004) e l'errore associato è 0,41. Se il numero massimo delle epoche è aumentato a 10.000, la FAO infatti troveranno la soluzione ottimale. FAO, come la maggior parte degli algoritmi di ottimizzazione numerica, non è garantita per trovare una soluzione ottimale in scenari realistici, dove la soluzione ottimale non è noto.
Questo articolo presuppone che hai almeno intermedio competenze di programmazione, ma non si assume che nulla si sa di ottimizzazione numerica o FAO. Il programma demo è codificato utilizzando c#, ma non dovreste avere troppe difficoltà refactoring del codice per un'altra lingua, come JavaScript o Python.
Il codice demo è un po' troppo lungo per presentare nella sua interezza, ma il codice sorgente completo è disponibile nel download del codice che accompagna questo articolo. Il codice demo ha rimosso per mantenere piccole le idee più chiaro possibile e la dimensione del codice di controllo degli errori più normali.
Struttura generale del programma
La struttura generale del programma, con alcune modifiche minori per risparmiare spazio, è presentata Figura 3. Per creare la demo, ho lanciato Visual Studio e creato una nuova applicazione console c# denominata fuochi d'artificioalgoritmo. La demo non ha significative .NET dipendenze, quindi ogni versione recente di Visual Studio funzionerà.
Figura 3 struttura generale del programma
using System;
using System.Collections.Generic;
namespace FireworksAlgorithm
{
class FireworksProgram
{
static void Main(string[] args)
{
Console.WriteLine("\nBegin fireworks algorithm demo\n");
Console.WriteLine("Goal is to solve Ackley's function");
Console.WriteLine("Function has min value = 0.0 at (0, .. ))");
int dim = 10;
int n = 5; // Number of fireworks
int maxEpochs = 10000;
Console.WriteLine("\nSetting Ackley's dimension to " + dim);
Console.WriteLine("Setting number fireworks to " + n);
Console.WriteLine("Setting maxEpochs to " + maxEpochs);
Console.WriteLine("\nBegin algorithm\n");
double[] bestPosition = Solve(dim, n, maxEpochs);
Console.WriteLine("\nAlgorithm complete");
Console.WriteLine("\nBest solution found: ");
for (int i = 0; i < dim; ++i)
Console.Write(bestPosition[i].ToString("F3") + " ");
Console.WriteLine();
double error = Error(bestPosition);
Console.WriteLine("\nError of best solution found = " +
error.ToString("F5"));
Console.WriteLine("\nEnd fireworks algorithm demo\n");
Console.ReadLine();
} // Main
public static double Error(double[] position) { . . }
public static double[] Solve(int dim, int n, int maxEpochs) { . . }
private static int[] PickDimensions(int dim, int z, int seed) { . . }
private static double YMax(Info[] fireworks) { . . }
private static double YMin(Info[] fireworks) { . . }
private static int[] NumberSparks(Info[] fireworks, int m,
double a, double b) { . . }
private static double[] Amplitudes(Info[] fireworks, int A,
int epoch, int maxEpochs, double minX, double maxX) { . . }
private static double MinAmplitude(int epoch, int maxEpochs,
double minX, double maxX) { . . }
private static void AddGaussianSparks(Info[] fireworks,
List<Info>[] sparksList, int dim, int mHat, int epoch, double minX,
double maxX, double[] bestPosition, ref double bestError, Random rnd)
}
public class Info
{
public double[] position;
public double error;
}
} // ns
Dopo il codice del modello caricato nell'editor Visual Studio , in Esplora soluzioni finestra rinominato il file Program.cs al FireworksProgram.cs più descrittivo e Visual Studio automaticamente rinominato classe programma per me. All'inizio del codice sorgente, ho eliminato tutti utilizzando le istruzioni che puntava a spazi dei nomi non necessari, lasciando solo i riferimenti al sistema e Collections.Generic.
Ho codificato il demo utilizzando un approccio di metodo statico piuttosto che un approccio (OOP) programmazione orientati agli oggetti. La demo ha tutta la logica di controllo nel metodo Main, che chiama due metodi pubblici, Solve ed errore. Le dichiarazioni del chiamante essenziali sono:
int dim = 10;
int n = 5;
int maxEpochs = 1000;
double[] bestPosition = Solve(dim, n, maxEpochs)
double error = Error(bestPosition);
Dim variabile contiene il numero di dimensioni del problema. Nel caso di formazione di apprendimento macchina, questo sarebbe normalmente il numero di pesi modello per determinare. Variabile n è il numero di fuochi d'artificio. Io uso quanto più possibile i piuttosto laconico nomi di variabili, come n, che vengono utilizzati sui giornali di ricerca della FAO per poter usare quelle carte come risorsa più facilmente. La tecnica FAO è contenuta nel metodo Solve. Errore del metodo accetta una posizione (una matrice di 10 valori), calcola il valore della funzione di Ackley per quei valori e restituisce la media della somma delle differenze al quadrato tra le uscite calcolate e il noto minimo pari a 0.0.
Il programma demo ha una classe di utilità denominata Info che encapsulates una posizione e il suo errore associato. La classe non ha nessun metodi associati, ad esempio un costruttore esplicito, al fine di rendere più facile per voi per il refactoring del codice demo per lingue con supporto limitato OOP.
Capire l'algoritmo
Il processo di algoritmo di fuochi d'artificio è illustrato nel grafico in Figura 4. L'immagine rappresenta un problema di minimizzazione fittizio semplificata, non di Ackley funzione del programma demo. L'obiettivo del problema fittizio è minimizzare qualche funzione arbitraria che ha due variabili di input, X e Y, dove la funzione ha un minimo valore di 0.0 situato a X = 0 e Y = 0.
.png "l'algoritmo di fuochi d'artificio")
Figura 4 l'algoritmo di fuochi d'artificio
L'immagine in Figura 4 utilizza tre fuochi d'artificio. Ogni fuoco d'artificio ha cosiddetto scintille. Ci sono due tipi di scintille, regolari e gaussiana. Figura 5 Mostra l'algoritmo di fuochi d'artificio in pseudocodice molto alto livello.
Figura 5 l'algoritmo di fuochi d'artificio in alto livello pseudo-codice
initialize 3 fireworks to random positions
loop until done
for each firework
calculate the amplitude of the firework
calculate the number of regular sparks
generate the regular sparks
end for
generate special Gaussian sparks
evaluate each spark
from the list of sparks,
select 3 to act as positions of new fireworks
create 3 new fireworks
end loop
return the position of the best spark found
Per l'immagine in Figura 4, le posizioni dei tre fuochi d'artificio sono indicate con i marcatori di punto colorato a (-6, 2), (3, 4) e (3, -3). Si noti che il primo fuoco d'artificio è il peggiore, perché è più lontano possibile dalla posizione di destinazione di (0, 0) e che il terzo fuoco d'artificio è il migliore perché è più vicina. Le ampiezze sono indicate dai cerchi tratteggiati intorno ogni fuoco d'artificio. Fuochi d'artificio buon hanno ampiezze minori e fuochi d'artificio male hanno ampiezze più grandi.
Ogni fuoco d'artificio genererà un numero diverso di normali (non-Gaussian) scintille. Fuochi d'artificio cattivo genererà meno scintille di fuochi d'artificio buon. In Figura 4, fuochi d'artificio [0] genera tre scintille, fuochi d'artificio [1] genera quattro scintille e fuochi d'artificio [2] genera cinque scintille. Ogni scintilla regolare sarà situato all'interno di ampiezza di suo padre fuoco d'artificio. Perché buona fuochi d'artificio hanno piccola ampiezza e relativamente molte scintille, la ricerca dell'algoritmo si concentrerà vicino buona fuochi d'artificio. Fuochi d'artificio male non dovrebbe essere trascurato interamente perché potrebbe portare a una soluzione ottimale che si trova fuori dalla portata di correnti fuochi d'artificio. Le scintille gaussiane sono generate in modo tale che essi tendono ad essere situati tra un fuoco d'artificio e la posizione più nota di qualsiasi scintilla incontrata durante la ricerca.
Dopo tutte le scintille gaussiane e regolari sono stati generati, ognuno viene valutato. Nuovi fuochi d'artificio per la prossima tornata di esplosioni è selezionati tra le scintille corrente. La posizione della migliore scintilla è mantenuta come uno dei nuovi fuochi d'artificio per intensificare la ricerca in buone posizioni. La posizione della scintilla peggiore è trattenuta per mantenere la ricerca diversità e impedire che l'algoritmo rapidamente crollando su una soluzione che potrebbe non essere ottima. Le posizioni dei rimanenti fuochi d'artificio, fuochi d'artificio solo un semplice esempio in Figura 4, sono selezionati in modo casuale da scintille corrente.
Il processo di generazione di fuochi d'artificio e poi scintille viene iterato fino a quando non vengono soddisfatte alcune condizioni di arresto. La condizione di arresto è solo un valore di contatore ciclo massimo nel caso il programma demo. Quando si utilizza la FAO per la formazione di apprendimento macchina, le condizioni di arresto potrebbero includere anche una soglia di errore affinché quando errore scende sotto qualche piccolo valore specificato che dipende dal particolare problema risolto, termina il ciclo di elaborazione.
Implementare l'algoritmo di fuochi d'artificio
La definizione del metodo Solve inizia come:
public static double[] Solve(int dim, int n, int maxEpochs)
{
int m = n * 10;
int mHat = 5;
double a = 0.04;
double b = 0.8;
int A = 40;
double minX = -10.0;
double maxX = 10.0;
...
Variabile m è il numero totale di scintille regolari, che saranno assegnati ai fuochi d'artificio n. Variabile mHat (così chiamato perché il paper di ricerca utilizzare una m minuscola con un accento circonflesso sopra esso) è che il numero di speciale gaussiana scintille per generare. Variabili un e b controllano il numero minimo e massimo di scintille per qualsiasi particolare fuoco d'artificio. Variabile A è l'ampiezza massima per ogni fuoco d'artificio. MaxX e variabili minX tenere i valori minimi e massimi per ogni singolo valore nella matrice di posizione di un oggetto Info.
Metodo risolvere crea n fuochi d'artificio iniziali, in questo modo:
Random rnd = new Random(3);
Info[] fireworks = new Info[n];
for (int i = 0; i < n; ++i)
{
fireworks[i] = new Info();
fireworks[i].position = new double[dim];
for (int j = 0; j < dim; ++j)
fireworks[i].position[j] = (maxX - minX)
* rnd.NextDouble() + minX;
fireworks[i].error = Error(fireworks[i].position);
}
Oggetto Random rnd è inizialmente utilizzando un valore di inizializzazione di 3 solo perché tale valore ha dato una demo rappresentanza eseguire. Ciascuno dei fuochi d'artificio n vengono memorizzati come oggetti di informazioni in una matrice. Il codice di inizializzazione raccoglie valori casuali tra minX e maxX per ogni cella della matrice posizione. Per alcuni specifico scenari di formazione di apprendimento automatico, è preferibile per inizializzare i fuochi d'artificio iniziali quindi sono distanti tra loro.
Metodo risolvere continua stabilendo variabili per tenere la posizione migliore trovata da qualsiasi scintilla e quella posizione associato errore. A differenza di fuochi d'artificio, che hanno un numero fisso, il numero di scintille al fuoco d'artificio varia in ogni iterazione del ciclo di elaborazione principale, quindi scintille sono memorizzati in un insieme di elenco anziché una matrice:
double[] bestPosition = new double[dim];
for (int k = 0; k < dim; ++k)
bestPosition[k] = fireworks[0].position[k];
double bestError = fireworks[0].error; // arbitrary
List<Info>[] sparksList = new List<Info>[n];
for (int i = 0; i < n; ++i)
sparksList[i] = new List<Info>();
Inizia il ciclo di elaborazione principale:
int epoch = 0;
while (epoch < maxEpochs)
{
if (epoch % 100 == 0) // Show progress every 100 iterations
{
Console.Write("epoch = " + epoch);
Console.WriteLine(" error at best known position = " +
bestError.ToString("F4"));
}
...
Qui, il progresso viene visualizzato ogni 100 epoche. Si potrebbe prendere in considerazione di passare una variabile flag booleano denominata "progresso" per controllare se vengono visualizzati messaggi di progresso:
int[] numberSparks = NumberSparks(fireworks, m, a, b);
double[] amplitudes =
Amplitudes(fireworks, A, epoch, maxEpochs, minX, maxX);
for (int i = 0; i < n; ++i)
sparksList[i].Clear(); // Number of sparks changed
Successivamente, il numero di scintille per ogni fuoco d'artificio e l'ampiezza massima per ogni fuoco d'artificio, sono calcolati utilizzando i metodi di supporto NumberSparks e ampiezze. Il numero di scintille di un fuoco d'artificio è proporzionale all'errore del fuoco d'artificio che fuochi d'artificio buon riceve una più grande proporzione di scintille regolari totale m. Analogamente, ogni ampiezza è proporzionale all'errore, affinché buona fuochi d'artificio hanno ampiezze minori.
Successivamente, ogni scintilla viene creata un'istanza:
for (int i = 0; i < n; ++i)
{
double amp = amplitudes[i]; // Amplitude for curr firework
int ns = numberSparks[i]; // Number of sparks for curr firework
for (int j = 0; j < ns; ++j) // Each spark for curr firework
{
Info spark = new Info(); // A spark has a position and error
spark.position = new double[dim]; // Allocate space (ctor doesn't)
for (int k = 0; k < dim; ++k) // Spark position based on its parent firework
spark.position[k] = fireworks[i].position[k];
Posizione di scintilla è basato sulla posizione di suo padre fuoco d'artificio. Prossimo, pochi (z) delle dimensioni della matrice posizione sono scelti a caso, e uno spostamento casuale viene aggiunto all'array di posizione:
int z = (int)Math.Round(dim * rnd.NextDouble());
int[] dimensions = PickDimensions(dim, z, epoch);
for (int ii = 0; ii < dimensions.Length; ++ii)
{
double h = amp * 2 * rnd.NextDouble() - 1;
int k = dimensions[ii]; // convenience
spark.position[k] += h; // displace from parent
if (spark.position[k] < minX || spark.position[k] > maxX)
spark.position[k] = (maxX - minX) * rnd.NextDouble() + minX;
}
spark.error = Error(spar.position);
sparksList[i].Add(spark);
Dopo la generazione di una scintilla, il metodo Solve controlla per vedere se la nuova scintilla ha la posizione migliore trovato finora:
if (spark.error < bestError)
{
bestError = spark.error;
for (int k = 0; k < dim; ++k)
bestPosition[k] = spark.position[k];
}
} // Each new regular spark
} // Each firework
Prossimi, speciale scintille gaussiane sono generati:
AddGaussianSparks(fireworks, sparksList, dim, mHat,
epoch, minX, maxX, bestPosition, ref bestError, rnd);
Metodo di supporto AddGaussianSparks genera scintille speciali loro posizioni tendono ad essere tra un fuoco d'artificio selezionato casualmente e la posizione più nota. Metodo risolvere conclude di trovare le migliore e peggio scintilla generata e utilizzando le loro posizioni per due dei nuovi fuochi d'artificio per l'iterazione successiva. I restanti n-2 fuochi d'artificio vengono creati utilizzando selezionati casualmente scintille:
...
// Find best, worst spark
// Create 2 new fireworks
// Create remaining n-2 fireworks
++epoch;
} // main loop
return bestPosition;
} // Solve
Vedere il codice di download per i dettagli di implementazione.
Alcuni commenti
La carta originale che ha presentato l'algoritmo di fuochi d'artificio è "Fuochi d'artificio algoritmo di ottimizzazione," di Y. Tan e Y. Zhu (2010). Quel libro conteneva diversi errori e fattori che ha reso impraticabile per la vita reale ottimizzazione algoritmo. Questi difetti sono stati rapidamente notati da altri ricercatori. Il mio articolo è basato principalmente sulla carta ricerca 2013, "Migliorato algoritmo di fuochi d'artificio," di S. Zheng, A. Janecek e Y. Tan. Potete trovare entrambi documenti in diverse posizioni su Internet. Ho fatto un bel semplificazioni e modifiche minori per gli algoritmi presentati in due documenti di ricerca. A mio parere, non c'è abbastanza prove di ricerca ancora di rispondere alla domanda se ottimizzazione di fuochi d'artificio è meglio o peggio di altri algoritmi di ottimizzazione. Ma è sicuramente interessante.
Dr. James McCaffrey lavora per la ricerca di Microsoft di Redmond, WA Ha lavorato su diversi prodotti Microsoft, inclusi Internet Explorer e Bing. Dr. McCaffrey può essere raggiunto a jammc@microsoft.com.
Grazie ai seguenti esperti tecnici Microsoft per la revisione di questo articolo: Todd Bello, Kenneth Griffin, Yong Liu, Brian Mellinger ed Esin Saka