Algoritmi di ottimizzazione della popolazione: Sciame di particelle (PSO)
436
0
Formano sciami distinti per fluttuare nei raggi di sole
o seguire nubi temporalesche. È possibile che traggano energia dalle scariche atmosferiche.
Ma nel momento del pericolo o, più in generale, di un cambiamento improvviso che minaccia la loro esistenza, si uniscono...
Stanisław Lem "L'invincibile"
Contenuto
- Introduzione
- Principi dell’algoritmo
- Implementazione classica
- Versione modificata
- Risultati del test
1. Introduzione
Ci sono probabilmente parecchie persone che hanno letto il meraviglioso bestseller di fantascienza di Stanisław Lem "L’Invincibile". Sorprendentemente,una delle prime descrizioni di "sciame" di intelligenza è nata proprio con l'uscita di questo romanzo di fantascienza. La storia parla di robot sopravvissuti senza controllo centralizzato. In particolare, sono sopravvissuti gli esemplari più semplici e numerosi, piuttosto che quelli più complessi, intelligenti e potenti.
Nel corso di migliaia di anni di necroevoluzione, queste macchine hanno imparato a trattare efficacemente con i concorrenti che li hanno superati sia nell'intelligenza che in termini di disponibilità di energia. Hanno dovuto combattere non solo con altri robot, ma anche con il mondo vivente del pianeta. Gli elementi di fantasia in questo lavoro possono essere confrontati in modo affidabile con l'evoluzione e la natura stessa.
Sin dai tempi più antichi, le persone si sono interessate al comportamento degli animali all'interno di un gruppo (il cosiddetto comportamento dello sciame) - come fanno gli uccelli quando uno stormo migra in paesi caldi, come uno sciame di api produce cibo, come una colonia di formiche sopravvive durante la creazione di strutture complesse, come si comportano i pesci quando curvano e perché il loro comportamento è così sincronizzato. L'organizzazione degli individui nella società mostrando alcuni modelli di un organismo integrale ben coordinato incoraggia nuove idee nel campo dell'ottimizzazione algoritmica.
L'intelligenza dello sciame descrive la simulazione del comportamento collettivo di un sistema auto-organizzante. Esiste un numero abbastanza elevato di questi algoritmi. Nella versione canonica, scritta nel 1995 da J.Kennedy e R.Eberhart, il modello alla base di questo metodo è stato ottenuto semplificando il modello di Reynolds. Come risultato di questa semplificazione, individui distinti della popolazione hanno cominciato ad apparire come oggetti separati che non hanno dimensione, ma hanno una certa velocità.
A causa dell'estrema somiglianza con le particelle materiali, gli oggetti semplici risultanti furono chiamati particelle e la loro popolazione fu chiamata sciame. In ogni momento di tempo (ad ogni iterazione), le particelle hanno una certa posizione e velocità vettoriale nello spazio. Per ogni posizione della particella, viene calcolato il valore corrispondente della funzione obiettivo e su questa base, secondo determinate regole, la particella cambia la sua posizione e velocità nello spazio di ricerca. Nel determinare la posizione successiva della particella, vengono prese in considerazione le informazioni sulla posizione migliore tra tutte le altre particelle vicine, corrispondenti ai compiti della funzione di fitness.
Esempi di algoritmi di sciame:
- Metodo dello sciame di particelle
- Algoritmo della formica
- Algoritmo delle api
- Sistema immunitario artificiale
- Algoritmo del lupo grigio
- Algoritmo del pipistrello
- Algoritmo di ricerca gravitazionale
- Algoritmo dell'altruismo
- e molti altri
Il passaggio dalla modellazione del comportamento collettivo all'ottimizzazione collettiva è basata sulla seguente idea biologica: gli organismi si uniscono in colonie per migliorare le loro condizioni di vita. Ogni organismo della colonia, in media, ha maggiori possibilità di sopravvivere nella lotta contro i predatori, la colonia può cercare, trattare e conservare il cibo più efficientemente rispetto ai singoli organismi, ecc. In altre parole, qualsiasi colonia di organismi durante l'intero periodo della sua esistenza risolve vari problemi di ottimizzazione con vari gradi di efficienza, ad esempio massimizzando la quantità di cibo riducendo le perdite dai predatori. Queste considerazioni hanno costituito le basi per la costruzione di vari metodi di ottimizzazione matematica.
Lo sciame di particelle è uno degli algoritmi di ottimizzazione più famosi e popolari sin dal suo inizio. Molti autori delle sue varie implementazioni affermano che l'algoritmo è molto efficace nell'ottimizzazione di funzioni complesse con molti argomenti ed è adatto anche per l'addestramento di reti neurali.
In questo articolo, cercherò di scoprire se l'algoritmo è effettivamente buono per risolvere problemi complessi. Nella versione classica dell'algoritmo e in molte delle sue varianti, ci sono limitazioni significative associate al fatto che la funzione ottimizzata deve essere fluida e continua, il che vuol dire che è completamente inadatta per funzioni discrete. Tuttavia, in linea con la serie di articoli, tutti gli algoritmi in esame saranno modificati in modo tale (se ci sono restrizioni) da eliminare le carenze, almeno per far funzionare gli algoritmi se non altro tecnicamente. In altre parole, tutti gli algoritmi devono essere indifferenti all'uniformità delle funzioni (come nei problemi dei trader) e non avere restrizioni sul passo dell'argomento.
2. Principi dell’algoritmo
Mentre l'articolo precedente era un'introduzione al mondo dell'ottimizzazione, non copriva il principio dell'interazione del programma principale (EA, script, indicatore) con il nucleo dell'algoritmo di ottimizzazione. È importante prestare attenzione, perché in ogni caso un lettore attento avrà una domanda: perché algoritmi e programmi di esempio sono scritti in questo modo? Le versioni esistenti degli algoritmi di ottimizzazione sono costruite in modo tale che l'algoritmo faccia riferimento alla funzione di fitness come ad un oggetto esterno, mentre l'algoritmo è il programma eseguibile principale.
La Figura 1 seguente mostra un diagramma in cui l'algoritmo passa i parametri ottimizzati alla funzione di fitness e ottiene il valore di fitness (criterio di valutazione). Questo sistema è scomodo per la creazione di un programma per la risoluzione dei problemi da parte degli utenti, compresi i trader. Perché è scomodo? Ad esempio, non possiamo chiamare un tester eseguito nel corso della cronologia.
Fig. 1. Interazione tra PSO e funzione di fitness
La struttura mostrata in Fig. 2 è molto più comoda. L'algoritmo di ottimizzazione qui non è un programma indipendente, ma un modulo separato o una "scatola nera". Questo modulo ha i parametri 'min', 'max' e 'step' per ogni argomento ottimizzato. Il programma MQL riceve su richiesta gli argomenti ottimizzati e restituisce i valori di fitness o, in altre parole, i valori della funzione di fitness. Questa struttura consente di creare una gamma di soluzioni molto flessibili, dall'utilizzo dell'ottimizzazione automatica in Expert Advisors alla scrittura di un gestore di ottimizzazione personalizzato.
Figura 2. Interazione tra programma MQL e PSO
Vale anche la pena ricordare che l'organizzazione delle chiamate ai metodi degli algoritmi di ottimizzazione (blocco MQL in Fig. 2) può essere rappresentata da uno schema generale uguale per tutti gli algoritmi di ottimizzazione (AO):
Inizializzazione_АО_0
Ciclo di iterazioni (periodi)
{
1) Metodo_АО_1
2) Ottenere i valori di fitness per ogni variante dei parametri ottimizzati
3) Metodo_АО_2
}
Pertanto, vediamo che vengono utilizzati solo tre metodi pubblici: Inizializzazione_АО_0, Metodo_АО_1 e Metodo_АО_2. Questo è sufficiente per organizzare il processo di ottimizzazione in progetti utente di qualsiasi complessità.
Il flusso di lavoro PSO stesso è mostrato in Figura 3 e include i seguenti passaggi logici:
- Generazione casuale di particelle (prima iterazione)
- Ottenimento del valore di fitness per ogni particella
- Ottenimento del valore di fitness per tutte le particelle in generale
- Regolazione della velocità delle particelle
- Punto di interruzione o andare al passaggio 2
- Completamento del programma.
Fig. 3. Flusso di lavoro PSO
Consideriamo l'algoritmo Sciame di Particelle in modo più dettagliato.
Il sistema di intelligenza dello sciame è costituito da molte particelle che interagiscono sia tra loro che con l'ambiente. Ogni particella segue regole semplici, sebbene non ci sia un sistema di controllo del comportamento centralizzato che dica a ciascuna di esse cosa fare. Le interazioni locali e casuali tra loro portano all'emergere di un comportamento di gruppo intelligente che non è controllato dagli individui.
Se tracciamo un'analogia con uno stormo, allora possiamo dire che tutte le particelle devono svolgere compiti semplici:
- evitare l'intersezione con altre particelle;
- regolare la loro velocità in base alla velocità delle particelle circostanti;
- provare a mantenere una distanza abbastanza piccola tra loro e l'ambiente.
L'algoritmo PSO inizia con un'inizializzazione della popolazione. Il secondo passaggio consiste nel calcolare i valori di fitness di ciascuna particella, dopodiché vengono aggiornati i migliori punteggi individuali e globali, quindi vengono aggiornate la velocità e la posizione delle particelle. Quando si utilizza PSO, una possibile soluzione a un problema di ottimizzazione numerica è rappresentata dalla posizione della particella. Inoltre, ogni particella ha una velocità corrente che riflette la sua magnitudine assoluta e la sua direzione verso una nuova soluzione/posizione, presumibilmente migliore.
La particella memorizza anche il suo valore di fitness, la posizione corrente, la posizione più nota (una posizione precedente con il valore di fitness più noto) e il valore di fitness della posizione più nota. I passaggi da due a quattro vengono ripetuti finché non viene soddisfatta la condizione di completamento. Nella prima iterazione, tutte le particelle vengono disperse per trovare la migliore soluzione (esplorazione). Ogni particella viene valutata. Vengono trovate le migliori soluzioni per la topologia del vicinato e vengono aggiornate le migliori particelle personali e globali per ciascun membro dello sciame. La convergenza si ottiene attraverso l’attrazione di tutte le particelle verso la particella con la soluzione migliore.
Sebbene l'algoritmo PSO sia abbastanza semplice al suo interno, dobbiamo comprenderlo per essere in grado di modificare il codice in questo articolo per soddisfare le nostre esigenze. PSO è un processo iterativo. Ad ogni iterazione nel ciclo di elaborazione principale, la velocità corrente di ciascuna particella viene prima aggiornata. Vengono prese in considerazione la velocità attuale della particella, le sue informazioni locali e le informazioni globali dello sciame. La posizione di ciascuna particella viene poi aggiornata utilizzando il valore della nuova velocità di quella particella.
Matematicamente, queste due equazioni di aggiornamento delle coordinate delle particelle si presentano così:
v(t+1) = w * v(t) + c1 * rp * (p(t) – x(t)) + (c2 * rg * (g(t) – x(t))
x(t+1) = x(t) + v(t+1)
Il processo di aggiornamento della posizione è in realtà molto più semplice delle equazioni suggerite. La prima equazione serve per aggiornare la velocità della particella.
Il termine v(t+1) denota la velocità al tempo t+1. La nuova velocità dipende da tre termini.
- Il primo: w * v(t). Il fattore w è chiamato frazione di peso dell'inerzia ed è semplicemente una costante; v(t) è la velocità attuale al tempo t.
- Il secondo termine: c1 * rp * (p(t) – x(t)). Il fattore c1 è una costante chiamata frazione di peso cognitiva (o personale o locale). Il moltiplicatore rp è una variabile casuale nell'intervallo [0, 1]. La quantità vettoriale p(t) è la migliore posizione della particella trovata finora, e la quantità vettoriale x(t) è la posizione corrente della particella.
- Il terzo termine: aggiornamento della velocità c2 * rg * (g(t) – x(t). Il fattore c2 è una costante chiamata frazione di peso sociale (o globale). Il moltiplicatore rg è una variabile casuale nell'intervallo [0, 1]. Il valore del vettore g(t) è la posizione più conosciuta trovata finora di una qualsiasi delle particelle nello sciame. Una volta determinata una nuova velocità, v(t+1), viene utilizzata per calcolare la nuova posizione della particella x(t+1).
3. Implementazione classica
Un'unità logica che descrive un insieme di coordinate nello spazio (parametri ottimizzati) è una particella, che può essere rappresentata come una struttura, dove c[] sono le coordinate della particella, cB[] sono le coordinate migliori della particella per tutte le iterazioni , v[] è la velocità per ciascuna delle coordinate della particella, ff - l'attuale valore di fitness della particella, ffB - il miglior valore di fitness della particella per tutte le iterazioni. Nel costruttore della struttura particellare, inizializziamo i valori di ff e ffB utilizzando il minimo valore possibile che può essere rappresentato dal tipo 'double', poiché l'algoritmo è progettato per trovare il massimo della funzione (per trovare il minimo, è sufficiente aggiungere un segno "-" prima del valore di fitness risultante).
//—————————————————————————————————————————————————————————————————————————————— struct S_Particles { public: double c []; //coordinates double cB []; //best coordinates double v []; //velocity double ff; //the value of the fitness function double ffB; //best value fitness function S_Particles () { ff = -DBL_MAX; ffB = -DBL_MAX; } }; //——————————————————————————————————————————————————————————————————————————————
Implementiamo l'algoritmo PSO come una classe con solo tre metodi pubblici InitPS (), Preparation () e Dwelling () (Initialization_АО_0, Method_АО_1 e Method_АО_2). Tra i metodi privati, GenerateRNDparticles () e ParticleMovement () sono gli unici per PSO, mentre il resto è già stato considerato nel precedente articolo. La struttura array p [] è uno sciame di particelle. Oltre al fatto che ogni particella ha valori di fitness, le proprie coordinate e le migliori coordinate, lo sciame nel suo insieme ha le migliori coordinate cB e il miglior valore di fitness ffB.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_PSO { public: //---------------------------------------------------------------------------- S_Particles p []; //particles double rangeMax []; //maximum search range double rangeMin []; //manimum search range double rangeStep []; //step search double cB []; //best coordinates double ffB; //FF of the best coordinates void InitPS (const int params, //number of opt. parameters const int size, //swarm size const double inertiaP, //inertia const double selfBoostP, //boost const double groupBoostP); //group boost void Preparation (); void Dwelling (); private: //---------------------------------------------------------------------------- int swarmSize; //swarm size int parameters;//number of optimized parameters double inertia; double selfBoost; double groupBoost; bool dwelling; void GenerateRNDparticles (); void ParticleMovement (); double SeInDiSp (double in, double inMin, double inMax, double step); double RNDfromCI (double min, double max); }; //——————————————————————————————————————————————————————————————————————————————
Il metodo InitPS() serve per inizializzare l'algoritmo prima dell'inizio dell'ottimizzazione (Initialization_АО_0). I valori dell'argomento del metodo vengono assegnati ai membri privati nel metodo, così come la dimensione viene assegnata allo sciame e ai parametri interni di ogni particella nello sciame.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_PSO::InitPS (const int paramsP, const int sizeP, const double inertiaP, const double selfBoostP, const double groupBoostP) { ffB = -DBL_MAX; parameters = paramsP; swarmSize = sizeP; ArrayResize (rangeMax, parameters); ArrayResize (rangeMin, parameters); ArrayResize (rangeStep, parameters); dwelling = false; inertia = inertiaP; selfBoost = selfBoostP; groupBoost = groupBoostP; ArrayResize (p, swarmSize); for (int i = 0; i < swarmSize; i++) { ArrayResize (p [i].c, parameters); ArrayResize (p [i].cB, parameters); ArrayResize (p [i].v, parameters); } ArrayResize (cB, parameters); } //——————————————————————————————————————————————————————————————————————————————
Il metodo Preparation () viene chiamato prima ad ogni iterazione (periodo) (Method_АО_1). Il metodo è semplice ma molto importante. A seconda che il metodo venga chiamato nel primo periodo o nei periodi successivi (determinato dal flag abitazione ), il valore di fitness dello sciame verrà ripristinato e verrà creata una popolazione di sciame casuale, oppure le particelle si sposteranno verso nuove coordinate.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_PSO::Preparation () { if (!dwelling) { ffB = -DBL_MAX; GenerateRNDparticles (); dwelling = true; } else ParticleMovement (); } //——————————————————————————————————————————————————————————————————————————————
Una popolazione di sciame casuale viene generata nel metodo GenerateRNDparticles() . Le particelle hanno coordinate casuali nell'intervallo specificato per ciascuna di esse e una velocità casuale per ciascuna delle coordinate.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_PSO::GenerateRNDparticles () { for (int s = 0; s < swarmSize; s++) { for (int k = 0; k < parameters; k++) { p [s].c [k] = RNDfromCI (rangeMin [k], rangeMax [k]); p [s].c [k] = SeInDiSp (p [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]); p [s].cB [k] = p [s].c [k]; p [s].v [k] = RNDfromCI (0.0, (rangeMax [k] - rangeMin [k]) * 0.5); } } } //——————————————————————————————————————————————————————————————————————————————
Il metodo ParticleMovement() attiva l'algoritmo per spostare le particelle in nuove posizioni. Per ottenere ciò, è necessario calcolare la velocità per ogni coordinata secondo l'equazione di cui sopra. Non so perché venga utilizzato il termine "velocità", in quanto è fondamentalmente un valore di spostamento, o in altre parole, la differenza tra dove si trova la particella in quel momento e dove dovrebbe muoversi. Dopo aver calcolato questa differenza per ciascuna delle coordinate, la aggiungiamo semplicemente ai valori correnti. Successivamente, controlla se è inaccettabile andare oltre i limiti min/max dei parametri ottimizzati (per una particella, queste sono coordinate) con un dato passo.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_PSO::ParticleMovement () { double rp; //random component of particle movement double rg; double velocity; double posit; double positBest; double groupBest; for (int i = 0; i < swarmSize; i++) { for (int k = 0; k < parameters; k++) { rp = RNDfromCI (0.0, 1.0); rg = RNDfromCI (0.0, 1.0); velocity = p [i].v [k]; posit = p [i].c [k]; positBest = p [i].cB [k]; groupBest = cB [k]; p [i].v [k] = inertia * velocity + selfBoost * rp * (positBest - posit) + groupBoost * rg * (groupBest - posit); p [i].c [k] = posit + p [i].v [k]; p [i].c [k] = SeInDiSp (p [i].c [k], rangeMin [k], rangeMax [k], rangeStep [k]); } } } //——————————————————————————————————————————————————————————————————————————————
Il metodo Dwelling() è il terzo metodo pubblico dell'algoritmo utilizzato per l'ottimizzazione (Method_АО_2). Lo scopo del metodo è aggiornare le migliori coordinate e i migliori valori di fitness di ciascuna particella rispetto alle sue prestazioni precedenti, nonché aggiornare il fitness dello sciame e le migliori coordinate dello sciame, se necessario. Il metodo viene chiamato dopo aver ottenuto i valori di fitness nel ciclo di iterazione.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_PSO::Dwelling () { for (int i = 0; i < swarmSize; i++) { //remember the best position for the particle if (p [i].ff > p [i].ffB) { p [i].ffB = p [i].ff; for (int k = 0; k < parameters; k++) p [i].cB [k] = p [i].c [k]; } if (p [i].ff > ffB) { ffB = p [i].ff; for (int k = 0; k < parameters; k++) cB [k] = p [i].c [k]; } } } //——————————————————————————————————————————————————————————————————————————————
La funzione per la discretizzazione del numero 'double' con un dato passo nell'intervallo specificato.
//—————————————————————————————————————————————————————————————————————————————— // Choice in discrete space double C_AO_PSO::SeInDiSp (double in, double inMin, double inMax, double step) { if (in <= inMin) return (inMin); if (in >= inMax) return (inMax); if (step == 0.0) return (in); else return (inMin + step * (double)MathRound ((in - inMin) / step)); } //——————————————————————————————————————————————————————————————————————————————
La funzione per ottenere un numero "double" casuale in un intervallo specificato.
//—————————————————————————————————————————————————————————————————————————————— // Random number generator in the custom interval double C_AO_PSO::RNDfromCI (double min, double max) { if (min == max) return (min); double Min, Max; if (min > max) { Min = max; Max = min; } else { Min = min; Max = max; } return (double(Min + ((Max - Min) * (double)MathRand () / 32767.0))); } //——————————————————————————————————————————————————————————————————————————————
La teoria è finita. Passiamo alla pratica.
Poiché utilizzo la stessa struttura per la costruzione degli algoritmi come nel primo articolo della serie (e continuerò a farlo in futuro) descritto in Fig. 2, allora non sarà difficile per noi collegare l'algoritmo al banco di prova .
Durante l'esecuzione del banco, vedremo animazioni simili a quelle mostrate di seguito. In questo caso, possiamo vedere chiaramente come si comporta uno sciame di particelle. Lo sciame si comporta davvero come uno sciame in natura. Sulla mappa termica della funzione, si muove sotto forma di una nuvola densa.
Come ricorderete, il cerchio nero indica l'ottimo globale (max) della funzione, mentre il punto nero indica le migliori coordinate medie dell'algoritmo di ricerca ottenute al momento dell'iterazione corrente. Lasciatemi spiegare da dove provengono i valori medi. La mappa termica è bidimensionale nelle coordinate e la funzione ottimizzata può includere centinaia di variabili (misurazioni). Pertanto, il risultato è mediato dalle coordinate.
PSO sulla funzione test Skin .
PSO sulla funzione di test Forest .
PSO sulla funzione di test Megacity .
Come puoi vedere nell'animazione, i test hanno dimostrato che PSO gestisce abbastanza bene e fluidamente la prima funzione, ma solo quando si ottimizzano due variabili. Con un aumento della dimensione dello spazio di ricerca, l'efficienza dell'algoritmo diminuisce drasticamente. Ciò è particolarmente evidente sulla seconda e discreta sulla terza funzione. I risultati sono notevolmente peggiori dell'algoritmo casuale descritto nell'articolo precedente. Torneremo sui risultati e li discuteremo in dettaglio quando formeremo una tabella comparativa dei risultati.
Guardando a come il famoso algoritmo PSO perde vergognosamente contro uno casuale, si potrebbe voler dare all'algoritmo una seconda possibilità. Nella prossima sezione proverò a modificare l'algoritmo PSO.
4. Versione modificata
A mio parere, i punti deboli di PSO sono:
1) Ognuna delle coordinate sarà necessariamente cambiata con una probabilità quasi uguale a 1. Ciò significa che ogni particella dello sciame, ad ogni iterazione, oscilla, nel migliore dei casi, da qualche parte nell'estremo locale della regione globale, mentre nel peggiore dei casi non raggiunge mai esattamente il punto dell'estremo globale. Ciò implica una caratteristica dell'algoritmo: rimanere bloccati negli estremi locali, ovvero una cattiva convergenza.
2) L'algoritmo non funziona bene con le funzioni discrete, in parte a causa del primo difetto. Le coordinate delle particelle saltano alle "aree" più vicine della superficie della funzione da ottimizzare, non riuscendo a studiare in dettaglio le aree vicine di qualsiasi estremo locale.
3) Scarsa capacità dell'algoritmo di esplorare nuove aree. Lo sciame si concentra da qualche parte in un punto senza cercare di sfuggire al "buco" locale. Alcuni autori menzionano i tentativi di creare un'implementazione di una modifica multi-sciame, ma le questioni relative all'ottimizzazione di funzioni multivariabili complesse rimangono aperte, poiché il principio della distanza reciproca non è chiaro, perché non solo deve essere soddisfatto il principio del movimento articolare, ma anche la possibilità di reciproca repulsione. Altrimenti, non ha senso tale implementazione perché i singoli sciami convergeranno semplicemente in un'area o in un punto. Allo stesso tempo, l'ottimizzazione di semplici funzioni a una o due variabili viene eseguita con i metodi più semplici con un'eccellente convergenza.
Quindi cosa possiamo fare per migliorare l'algoritmo?
È ovvio (anche se non necessariamente vero) che dobbiamo passare le migliori coordinate individuali alle particelle da altre particelle. Migliori sono le coordinate complessive della particella "donatrice", maggiore è la probabilità di passaggio delle coordinate. Lo spostamento nella probabilità di scegliere una particella è mostrato schematicamente in Fig. 4. Generiamo un numero casuale da 0 a 1, trasformiamo il numero risultante con una funzione parabolica e quindi lo ridimensioniamo nell'intervallo di numeri seriali di particelle nello sciame da 0 a SwarmSize-1. Per fare questo, dobbiamo introdurre un parametro aggiuntivo per PSOm (l'algoritmo modificato) - la probabilità di copiare la coordinata, e dobbiamo anche ordinare lo sciame in modo che la particella migliore più vicina è all'indice 0.
Fig. 4. Probabilità di selezione delle particelle spostate
Cambiamo leggermente il metodo ParticleMovement() . Genera un numero casuale [0;1]. se il numero risulta essere maggiore del parametro 'copia', allora eseguiremo le consuete operazioni con la particella descritta in dettaglio sopra, altrimenti copieremo la coordinata di un'altra particella con l'indice scelto secondo la regola mostrata graficamente in Fig. 4.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_PSOm::ParticleMovement () { double rp; //random component of particle movement double rg; double velocity; double posit; double positBest; double groupBest; for (int i = 0; i < swarmSize; i++) { for (int k = 0; k < parameters; k++) { rp = RNDfromCI (0.0, 1.0); rg = RNDfromCI (0.0, 1.0); double rC = RNDfromCI (0.0, 1.0); if (rC > copy) { velocity = p [i].v [k]; posit = p [i].c [k]; positBest = p [i].cB [k]; groupBest = cB [k]; p [i].v [k] = inertia * velocity + selfBoost * rp * (positBest - posit) + groupBoost * rg * (groupBest - posit); p [i].c [k] = posit + p [i].v [k]; p [i].c [k] = SeInDiSp (p [i].c [k], rangeMin [k], rangeMax [k], rangeStep [k]); } else p [i].c [k] = p [GetPartcileAdress ()].cB [k]; } } } //——————————————————————————————————————————————————————————————————————————————
Anche il metodo Dwelling() dovrebbe essere modificato. Aggiungere la chiamata alla funzione di ordinamento SortParticles() .
//—————————————————————————————————————————————————————————————————————————————— void C_AO_PSOm::Dwelling () { for (int i = 0; i < swarmSize; i++) { //remember the best position for the particle if (p [i].ff > p [i].ffB) { p [i].ffB = p [i].ff; for (int k = 0; k < parameters; k++) p [i].cB [k] = p [i].c [k]; } if (p [i].ff > ffB) { ffB = p [i].ff; for (int k = 0; k < parameters; k++) cB [k] = p [i].c [k]; } } SortParticles (); } //——————————————————————————————————————————————————————————————————————————————
La funzione GetParticleAdress() fornisce una scelta dell'indirizzo di una particella con una probabilità spostata verso la particella migliore.
//—————————————————————————————————————————————————————————————————————————————— //shift of probability in the smaller party (to an index 0) int C_AO_PSOm::GetParticleAdress () { double x = RNDfromCI (-1.0, 0.0); x = x * x; x = Scale (x, 0.0, 1.0, 0, swarmSize - 1); x = SeInDiSp (x, 0, swarmSize - 1, 1); return ((int)x); } //——————————————————————————————————————————————————————————————————————————————
La funzione SortParticles() è un ordinamento a bolla convenzionale.
//—————————————————————————————————————————————————————————————————————————————— //Sorting of particles void C_AO_PSOm::SortParticles () { //---------------------------------------------------------------------------- int cnt = 1; int t0 = 0; double t1 = 0.0; //---------------------------------------------------------------------------- // We will put indexes in the temporary array for (int i = 0; i < swarmSize; i++) { ind [i] = i; val [i] = p [i].ffB; //ffPop [i]; } while (cnt > 0) { cnt = 0; for (int i = 0; i < swarmSize - 1; i++) { if (val [i] < val [i + 1]) { t0 = ind [i + 1]; t1 = val [i + 1]; ind [i + 1] = ind [i]; val [i + 1] = val [i]; ind [i] = t0; val [i] = t1; cnt++; } } } // On the received indexes create the sorted temporary population for (int u = 0; u < swarmSize; u++) pT [u] = p [ind [u]]; // Copy the sorted array back for (int u = 0; u < swarmSize; u++) p [u] = pT [u]; } //——————————————————————————————————————————————————————————————————————————————
La funzione per ridimensionare un numero da un intervallo numerico a un altro.
//—————————————————————————————————————————————————————————————————————————————— double C_AO_PSOm::Scale (double In, double InMIN, double InMAX, double OutMIN, double OutMAX) { if (OutMIN == OutMAX) return (OutMIN); if (InMIN == InMAX) return (double((OutMIN + OutMAX) / 2.0)); else { if (In < InMIN) return (OutMIN); if (In > InMAX) return (OutMAX); return (((In - InMIN) * (OutMAX - OutMIN) / (InMAX - InMIN)) + OutMIN); } } //——————————————————————————————————————————————————————————————————————————————
5. Risultati del test
Finalmente, riassumiamo i risultati della ricerca in corso. Sfortunatamente, l'algoritmo PSO non si è giustificato, non importa quanto mi piacerebbe sperare in buoni risultati. Gli studi hanno mostrato la sua debole convergenza per funzioni discrete con break e con un gran numero di argomenti. Il tentativo di modificare l'algoritmo non ha avuto successo, i risultati si sono rivelati anche peggiori di quelli dell'implementazione classica.
Aumentando il parametro di copy a valori prossimi a 0,8 nei test è ancora in grado di mostrare convergenza istantanea ma solo per la prima funzione e con solo due argomenti. Per altri test, questo parametro peggiora solo i risultati. L'implementazione classica di PSO è riuscita a mostrare qualcosa di interessante solo sulla funzione Skin con 1000 argomenti. Altri test si sono rivelati mediocri.
Il risultato finale del test è rispettivamente 0,47695 per l'algoritmo classico e 0,45144 per quello modificato. I risultati sono mostrati nella tabella sottostante. Il banco di prova ci consente di selezionare il numero di cicli di prova nelle impostazioni (il valore predefinito è 5), in modo che i lettori possano ottenere risultati statisticamente più accurati impostando questo parametro ad un valore più alto se consentito dalla potenza di calcolo.
| AO | Cicli | Skin | Forest | Megacity (discreto) | Risultato finale | ||||||
| 2 parametri (1 F) | 40 parametri (20 F) | 1000 parametri (500 F) | 2 parametri (1 F) | 40 parametri (20 F) | 1000 parametri (500 F) | 2 parametri (1 F) | 40 parametri (20 F) | 1000 parametri (500 F) | |||
| RND | 1000 | 0,98744 | 0,61852 | 0.49408 | 0,89582 | 0.19645 | 0.14042 | 0,77333 | 0.19000 | 0.14283 | 0,51254 |
| 10.000 | 0,99977 | 0,69448 | 0,50188 | 0.98181 | 0.24433 | 0.14042 | 0,88000 | 0.20133 | 0.14283 | ||
| POS | 1000 | 0,98436 | 0.72243 | 0,65483 | 0.71122 | 0.15603 | 0,08727 | 0,53333 | 0,08000 | 0.04085 | 0,47695 |
| 10.000 | 0,99836 | 0,72329 | 0,65483 | 0,97615 | 0.19640 | 0.09219 | 0,82667 | 0,10600 | 0.04085 | ||
| PSOm | 1000 | 0,96678 | 0,64727 | 0,57654 | 0.80616 | 0.13388 | 0,06800 | 0,53333 | 0,08067 | 0.04211 | 0.45144 |
| 10.000 | 0,99505 | 0,64986 | 0,57654 | 0.90401 | 0.18194 | 0.07104 | 0,74667 | 0.10400 | 0.04211 | ||
Riassumendo tutto quanto sopra, PSO tende a portare a una convergenza rapida e prematura in punti ottimali medi oltre a rallentare la convergenza nell'area di ricerca rifinita (con scarsa capacità di ricerca locale). In poche parole, l'algoritmo è molto debole e non è adatto per le ottimizzazioni complesse e ancor più per le funzioni discrete, in particolare funzioni di più argomenti.
Esistono diversi approcci che possono essere utilizzati per migliorare PSO in generale. La dimensione dello sciame è uno dei fattori importanti. Una dimensione dello sciame maggiore può aumentare la probabilità di una convergenza più rapida e accurata. Tuttavia, nei problemi pratici c'è spesso una soglia sul numero di esecuzioni della funzione fitness, e l'aumento della dimensione dello sciame ridurrà solo proporzionalmente il numero di periodi, perciò ridurrà la possibilità di evoluzione dello sciame.
Il secondo approccio è trovare un equilibrio tra esplorazione e sfruttamento. All'inizio delle iterazioni, l'alto grado di esplorazione darebbe un'alta possibilità di trovare una soluzione vicina all'ottimo globale. Nel frattempo, entro la fine dell'iterazione, un alto grado di sfruttamento darebbe alla particella la possibilità di trovare la soluzione più accurata nell'area promettente. La pre-ottimizzazione prima della fase dello sciame con altri metodi è un'altra tecnica che può essere utilizzata per migliorare le prestazioni sottostanti di PSO, che è abbastanza comunemente usata al giorno d'oggi. L'assegnazione di compiti o obiettivi diversi ad ogni sottogruppo può anche aumentare l'efficacia di PSO nei problemi multi-task.
Un altro approccio per migliorare le prestazioni di PSO consiste nello stabilire i componenti costitutivi dell'equazione della velocità (controllo dinamico della velocità). Un tale approccio può inviare particelle in direzioni differenti e portare a una convergenza più rapida verso l'ottimo globale, ma questa è solo un'ipotesi.Pro:
- L'algoritmo è molto semplice e poco impegnativo per le risorse di calcolo, il codice funziona molto velocemente, poiché l'implementazione classica non ordina nemmeno gli array.
- L'algoritmo fa un buon lavoro con funzioni fluide. Finora, PSO è il chiaro leader nella tabella per l'ottimizzazione di funzioni fluide con più argomenti.
Contro:
- La bassa qualità dello studio della funzione ottimizzata. L'algoritmo non può essere applicato per risolvere problemi in cui è richiesto un insieme di diverse soluzioni uniche.
- Bassa velocità e precisione di convergenza.
- Inidoneità all'ottimizzazione di funzioni discrete.
- Quasi completa non scalabilità.
Tradotto dal russo da MetaQuotes Ltd.
Articolo originale: https://www.mql5.com/ru/articles/11386
Sviluppare un Expert Advisor per il trading da zero (Parte 18): Nuovo sistema di ordini (I)
Algoritmi di ottimizzazione della popolazione
Sviluppare un Expert Advisor per il trading da zero (Parte 19): Nuovo sistema di ordini (II)
Impara come progettare un sistema di trading tramite Chaikin Oscillator
- App di trading gratuite
- Oltre 8.000 segnali per il copy trading
- Notizie economiche per esplorare i mercati finanziari
Accetti la politica del sito e le condizioni d’uso