Perché il valore di crossover non è 0,5?

Question

Perché il valore di crossover non è 0,5?

#1 da (5 voti)
#2 da (1 voti)

8

La maggior parte della letteratura che ho letto su GAs suggerisce di usare un valore di crossover di circa 0,7, quindi prendi il primo 70% dei geni di un cromosoma e l'ultimo 30% dell'altro per produrre un nuovo cromosoma.

Se stai selezionando i cromosomi dei genitori prendendo i primi due (classificati per idoneità), allora posso vedere la logica qui, dato che stai dando più peso ai geni del cromosoma più alto. Tuttavia, se stai usando un metodo stocastico (come una ruota della roulette) per scegliere i genitori, allora qual è il punto di usare qualcosa di diverso da 0.5 come valore di crossover? Dato che hai scelto i cromosomi A e B come genitori, hai la stessa probabilità di scegliere A prima e B secondo prima B e A secondo no?

In realtà ho scritto solo una GA fino ad ora (ancora in basso nella parte inferiore della curva di apprendimento, ma salendo velocemente grazie ad un grande aiuto qui!), ma gli esperimenti su questo mostrano che 0.5 dà una convergenza più veloce a la soluzione rispetto a qualsiasi altro valore.

O mi manchi qualcosa?

genetic-algorithms

posta Avrohom Yisroel 22.12.2016 - 18:01

fonte

2 risposte

1

In modo confuso, la frequenza di crossover e il tasso di mutazione, pur essendo nominati allo stesso modo, sono tipicamente interpretati in modo diverso.

Tasso di mutazione di x% == > Si esegue l'operatore di mutazione con probabilità 1.0 e ciascuna applicazione di tale operatore cambierà x% dei bit dell'individuo mutato.

Tasso di crossover di x% == > Scegli di eseguire il crossover affatto con probabilità x.

Quindi un tasso di crossover del 70% non significa che prendi il 70% dei bit dal genitore 1 e il 30% dal genitore 2. Significa che eseguirai qualsiasi operatore di crossover che hai scelto il 70% delle volte. Il restante 30% delle volte passerai i genitori non modificati nella piscina della prole.

risposta data 23.12.2016 - 18:33

fonte

Leggi altre domande sui tag genetic-algorithms

Quale tecnologia è necessaria per creare un servizio di streaming video live? [chiuso] Google App Engine, quali sono i vantaggi e le limitazioni?

score 5 · Accepted Answer

L'operazione di crossover ideale dipende molto dallo spazio del problema. Le ipotesi sottostanti agli algoritmi evolutivi e genetici sono che a volte due buone soluzioni possono essere combinate in una soluzione migliore - le buone soluzioni sembrano simili ad altre buone soluzioni. Questo ha un senso intuitivo se lo spazio del problema ha un unico ottimale a cui convergerà ogni generazione successiva.

Quando ci sono più optima, lo spazio tra questi optima è per definizione non ottimale. Se prendiamo un cromosoma A vicino all'ottimale e lo combiniamo con un cromosoma B vicino a un altro ottimale, atterreremo in mezzo e probabilmente il cromosoma risultante è peggio dei suoi genitori. Stare vicino all'uno o all'altro dei genitori aumenta la probabilità di ottenere un cromosoma d che sia migliore o almeno non molto peggio dei genitori.

     _                d         ^ fitness
    / \              d \        |
   /   A            B   \       |
__/     \___ccc___dd     \____  |
-----------------------------------> chromosome space
     |                |
     |     valley     |
     |     of "meh"   |
1. optimum         2. optimum

Il valore di crossover è solo un parametro dell'algoritmo che puoi accordare per adattarsi alla tua struttura dei problemi. A volte vedrai una convergenza più veloce con un basso valore di crossover, a volte con un valore di crossover molto alto. Ma per valori molto alti, questo sarebbe meno simile a un crossover ma solo un piccolo cambiamento come una mutazione. Quindi, invece di usare un valore vicino a 1.0, preferiresti ridurre la velocità di crossover e aumentare il tasso di mutazione.