Utente:Scardax88/Sandbox

Una strategia evolutiva (SE) è una tecnica di ottimizzazione stocastica basata su principi di adattamento ed evoluzione. Fa parte della più ampia classe di algoritmi evolutivi, come gli algoritmi genetici e la programmazione genetica. Si differenzia da questi ultimi essendo usata principalmente in problemi definiti su variabili continue.

Formulazione

Le strategie evolutive risolvono problemi di ottimizzazione del tipo:

$\min _{\mathbf {x} }f(\mathbf {x} )$

dove $\mathbf {x} \in \mathbb {R} ^{n}$, ed $f(\cdot )$ è una generica funzione scalare definita su $\mathbf {x}$, detta funzione di fitness o funzione obiettivo. L'unico requisito imposto a tale funzione è che sia possibile valutarne il valore in ogni punto. Una SE è una tecnica evolutiva, iterativa, per risolvere tale problema senza fare uso di informazioni sul gradiente di $f(\cdot )$.

Ad ogni iterazione, viene mantenuta una popolazione ${\mathcal {P}}$ di $\mu$ possibili soluzioni al problema (dette individui), le quali vengono ricombinate e mutate per generare la popolazione successiva. Più nello specifico, ad ogni iterazione si seguono i seguenti passi:

1. Vengono selezionati $\rho$ elementi dalla popolazione. In generale, quindi, si ha $\rho \leq \mu$.
2. Da questi $\rho$ elementi viene generato un nuovo individuo, tramite un processo detto di 'ricombinazione'. Sono possibili tre alternative:
   • Nella ricombinazione 'discreta', ciascun elemento del nuovo individuo è estratto con probabilità uniforme da uno dei suoi $\rho$ genitori.
   • Nella ricombinazione 'intermedia', il nuovo individuo è dato dalla media aritmetica dei genitori.
   • Nella ricombinazione 'pesata', il nuovo individuo è dato da una media pesata dei genitori. I pesi dipendono dal valore di fitness di ciascun genitore.
3. Il nuovo individuo subisce un processo detto di 'mutazione' (vedi sezione successiva).
4. I punti (1)-(2) vengono ripetuti $\lambda$ volte. I nuovi $\lambda$ individui vengono aggiunti alla popolazione esistente, o la sostituiscono completamente. Dalla nuova popolazione, vengono selezionati i $\mu$ migliori individui.

Variando i parametri $\mu$, $\rho$ e $\lambda$ è possibile ottenere diverse categorie di SE. È uso comune la notazione $(\mu /\rho ,\lambda )$-SE per riferirsi ad una particolare istanza dei parametri, nel caso in cui al punto (4) la nuova popolazione sostituisce quella presente. Nel caso opposto, si usa la notazione $(\mu /\rho +\lambda )$-SE. Nel caso $\rho =\mu$, è comune scegliere un metodo di selezione deterministico. In questo caso, la ricombinazione al passo (2) produce sempre lo stesso centroide, che può essere creato una sola volta per iterazione. Un altro caso degenere di interesse (soprattutto per analisi teoriche) è $\lambda =\rho =\mu =1$, detto uno scenario di 'steady-state'.

Bibliografia

• Back, T., Fogel, D. B., & Michalewicz, Z. (1997). Handbook of evolutionary computation. IOP Publishing Ltd..
• Beyer, H. G., & Schwefel, H. P. (2002). Evolution strategies–A comprehensive introduction. Natural computing, 1(1), 3-52.
• Hansen, N., Arnold, D. V., & Auger, A. (2013). Evolution Strategies. Handbook of Computational Intelligence. Springer.