Questa pagina è stata tradotta con la traduzione automatica. Fai clic qui per vedere l'ultima versione in inglese.

Algoritmo di ottimizzazione dello sciame di particelle

Schema dell'algoritmo

particleswarm si basa sull'algoritmo descritto in Kennedy e Eberhart [1], utilizzando le modifiche suggerite in Mezura-Montes e Coello Coello [2] e in Pedersen [3].

L'algoritmo dello sciame di particelle inizia con la creazione delle particelle iniziali e con l'assegnazione delle loro velocità iniziali.

Valuta la funzione obiettivo in ogni posizione delle particelle e determina il valore della funzione migliore (il più basso) e la posizione migliore.

Sceglie nuove velocità in base alla velocità attuale, alle migliori posizioni delle singole particelle e alle migliori posizioni dei loro vicini.

Quindi aggiorna iterativamente le posizioni delle particelle (la nuova posizione è quella vecchia più la velocità, modificata per mantenere le particelle entro i limiti), le velocità e i vicini.

Le iterazioni procedono finché l'algoritmo non raggiunge un criterio di arresto.

Ecco i dettagli dei passaggi.

Inizializzazione

Per impostazione predefinita, particleswarm crea particelle in modo casuale e uniforme entro i limiti. Se è presente una componente illimitata, particleswarm crea particelle con una distribuzione casuale uniforme da –1000 a 1000. Se è presente un solo limite, particleswarm sposta la creazione in modo che il limite sia un punto finale e l'intervallo di creazione sia largo 2000. La particella i ha posizione x(i), che è un vettore riga con elementi nvars. Controlla l'estensione dello sciame iniziale utilizzando l'opzione InitialSwarmSpan.

Allo stesso modo, particleswarm crea velocità iniziali delle particelle v in modo casuale e uniforme all'interno dell'intervallo [-r,r], dove r è il vettore degli intervalli iniziali. L'intervallo del componente k è min(ub(k) - lb(k),InitialSwarmSpan(k)) .

particleswarm valuta la funzione obiettivo per tutte le particelle. Registra la posizione corrente p(i) di ciascuna particella i. Nelle iterazioni successive, p(i) sarà la posizione della migliore funzione obiettivo trovata dalla particella i. E b è la migliore tra tutte le particelle: b = min(fun(p(i))) . d è la posizione tale che b = fun(d) .

particleswarm inizializza la dimensione del vicinato N a minNeighborhoodSize = max(2,floor(SwarmSize*MinNeighborsFraction)).

particleswarm inizializza l'inerzia W = max(InertiaRange) oppure, se InertiaRange è negativo, imposta W = min(InertiaRange) .

particleswarm inizializza il contatore di stallo c = 0 .

Per comodità di notazione, impostare le variabili y1 = SelfAdjustmentWeight e y2 = SocialAdjustmentWeight, dove SelfAdjustmentWeight e SocialAdjustmentWeight sono opzioni.

Passaggi di iterazione

L'algoritmo aggiorna lo sciame come segue. Per la particella i, che si trova nella posizione x(i):

Scegli un sottoinsieme casuale S di particelle N diverse da i.
Trova fbest(S), la migliore funzione obiettivo tra i vicini, e g(S), la posizione del vicino con la migliore funzione obiettivo.
Per u1 e u2 vettori casuali uniformemente (0,1) distribuiti di lunghezza nvars, aggiornare la velocità
v = W*v + y1*u1.*(p-x) + y2*u2.*(g-x) .
Questo aggiornamento utilizza una somma ponderata di:
- La velocità precedente v
- La differenza tra la posizione attuale e la posizione migliore che la particella ha visto p-x
- La differenza tra la posizione attuale e la posizione migliore nel quartiere attuale g-x
Aggiorna la posizione x = x + v .
Rispettare i limiti. Se un componente di x è al di fuori di un limite, impostarlo uguale a tale limite. Per quei componenti che sono stati appena impostati su un limite, se la velocità v di quel componente punta all'esterno del limite, imposta quel componente di velocità su zero.
Valutare la funzione obiettivo f = fun(x) .
Se f < fun(p), allora imposta p = x . Questo passaggio garantisce che p abbia la migliore posizione mai vista dalla particella.
I passaggi successivi dell'algoritmo si applicano ai parametri dell'intero sciame, non alle singole particelle. Consideriamo la più piccola f = min(f(j)) tra le particelle j nello sciame.
Se f < b, allora imposta b = f e d = x. Questo passaggio garantisce che b abbia la migliore funzione obiettivo nello sciame e che d abbia la migliore posizione.
Se nel passaggio precedente è stato abbassato il valore della funzione migliore, allora impostare flag = true . Altrimenti, flag = false . Il valore di flag viene utilizzato nel passaggio successivo.
Aggiorna il quartiere. Se flag = true:
1. Imposta c = max(0,c-1) .
2. Imposta N su minNeighborhoodSize .
3. Se c < 2, allora imposta W = 2*W .
4. Se c > 5, allora imposta W = W/2 .
5. Assicurarsi che W rientri nei limiti dell'opzione InertiaRange.
Se flag = false:
1. Imposta c = c+1 .
2. Imposta N = min(N + minNeighborhoodSize,SwarmSize) .

Criteri di arresto

particleswarm esegue un'iterazione finché non raggiunge un criterio di arresto.

Opzione di arresto	Test di arresto	Bandiera di uscita
`MaxStallIterations` e `FunctionTolerance`	La variazione relativa del miglior valore della funzione obiettivo `g` nelle ultime `MaxStallIterations` iterazioni è inferiore a `FunctionTolerance`.	`1`
`MaxIterations`	Il numero di iterazioni raggiunge `MaxIterations` .	`0`
`OutputFcn` o `PlotFcn`	`OutputFcn` o `PlotFcn` possono interrompere le iterazioni.	`-1`
`ObjectiveLimit`	Il miglior valore della funzione obiettivo `g` è inferiore a `ObjectiveLimit`.	`-3`
`MaxStallTime`	Il valore della funzione obiettivo migliore `g` non è cambiato negli ultimi `MaxStallTime` secondi.	`-4`
`MaxTime`	Il tempo di esecuzione della funzione supera `MaxTime` secondi.	`-5`

Se particleswarm si arresta con il flag di uscita 1, dopo l'uscita richiama facoltativamente una funzione ibrida.

Riferimenti

[1] Kennedy, J., and R. Eberhart. "Particle Swarm Optimization." Proceedings of the IEEE International Conference on Neural Networks. Perth, Australia, 1995, pp. 1942–1945.

[2] Mezura-Montes, E., and C. A. Coello Coello. "Constraint-handling in nature-inspired numerical optimization: Past, present and future." Swarm and Evolutionary Computation. 2011, pp. 173–194.

[3] Pedersen, M. E. "Good Parameters for Particle Swarm Optimization." Luxembourg: Hvass Laboratories, 2010.