Questo è un buon candidato per Evoluzione differenziale .
DE è un minimizzatore / ottimizzatore di funzione stocastico molto semplice (ma potente) basato sulla popolazione.
Un punto chiave per l'integrazione di DE nel tuo schema è la funzione fitness:
double fitness(Agent_k)
fit = 0
repeat M times
randomly extract an individual Agent_i (i <> k)
switch (result of Agent_k vs Agent_i)
case Agent_k wins: fit = fit + 1
case Agent_i wins: fit = fit - 2
case draw: fit doesn't change
return fit
vale a dire. un agente gioca contro M avversari selezionati casualmente dalla popolazione (con la sostituzione ma evitando l'auto-partita).
Il parametro M è importante: valori grandi danno una misura precisa, valori piccoli potrebbero impedire la convergenza. Vorrei iniziare con M=5 (un valore utilizzato in alcuni esperimenti relativi agli scacchi).
Uno schizzo della ricerca è:
Create a population of N agents with random weights
While (Brendan hasn't stopped the program and
population diversity is greater than a given threshold)
randomly select Agent_b
randomly select Agent_i (i <> b)
randomly select Agent_j (j <> i and j <> b)
randomly select Agent_k (k <> j and k <> i and k <> b)
Agent_m = Agent_i + F (Agent_j - Agent_k)
Agent_child = crossover(Agent_b, Agent_m)
if (fitness(Agent_child) > fitness(Agent_b)
replace Agent_b with Agent_child
Questo è un approccio di popolazione a stato stazionario (l'alternativa è un approccio generazionale; ulteriori informazioni in Elementi essenziali della metaeuristica di Sean Luke).
Per maggiori dettagli su come DE dà un'occhiata a:
DE guiderà la ricerca verso aree promettenti dello spazio possibile (senza eseguire una ricerca sistematica come nel tuo codice).
In ogni caso questo tipo di ottimizzazione potrebbe facilmente richiedere diversi giorni.
La pagina ufficiale di DE ha implementazioni in molte lingue (anche Java ).
I would expect "crossover" to average out the parent function weightings, but how does the variation arise?
In DE c'è una "miscela" di mutazione e crossover.
(nell'immagineAgent_j=Xa,Agent_k=Xb,Agent_i=Xc.SchemadimutazionediDE,crossovernonmostrato)
Strategieevolutivetradizionalihannomutatoivettoriaggiungendolorounrumoregaussianoallozero,ma,perrimanereefficienti,loschemadimutazionehadovutoregolareladeviazionestandarddelrumoregaussianoperadattarsiaciascunparametro(anchequestaèunafunzionedeltempo).
DEusaunvettoredifferenzialeXa-Xb,alpostodelrumoregaussiano,per"perturbare" un altro vettore Xc :
Xc_ = Xc + F * (Xa - Xb)
F (peso differenziale) è un fattore di scala fornito dall'utente nell'intervallo [0.1, 1.2] .
Questa forma di mutazione (con rumore derivato dalla popolazione) assicura che lo spazio di ricerca venga cercato in modo efficiente in ogni dimensione.
For example, if the population becomes compact in one dimension, but remains widely dispersed along another, the differentials sampled from it will be small in one dimension yet large in the other. Whatever the case, step sizes will be comparable to the breadth of the region they are being used to search, even as these regions expand and contract during the course of evolution.
(da Dr.Dobb's Journal # 264 aprile 1997 p.22, "Differential Evolution" di K. Price e R. Storn)
Xc_ ( Agent_m nello pseudo-codice) viene utilizzato per produrre un vettore di prova tramite crossover con un individuo casuale ( Xi di seguito, Agent_b nello pseudo-codice ):
Xt = crossover(Xi, Xc_)
L'operatore crossover produce una prole da una serie di esperimenti binomiali: in questo modo viene stabilito quale genitore contribuisce quale parametro del trial vector.
Il migliore tra Xt e Xi ( Agent_child e Agent_b ) sopravvive.