Algoritmi genetici - Crossover

In questo capitolo, discuteremo di cosa sia un operatore di crossover insieme ai suoi altri moduli, i loro usi e vantaggi.

Introduzione a Crossover

L'operatore di crossover è analogo alla riproduzione e al crossover biologico. In questo viene selezionato più di un genitore e una o più discendenti vengono prodotte utilizzando il materiale genetico dei genitori. Il crossover viene solitamente applicato in un GA con un'alta probabilità -p_c .

Operatori di crossover

In questa sezione discuteremo alcuni degli operatori di crossover più comunemente usati. È da notare che questi operatori di crossover sono molto generici e GA Designer potrebbe scegliere di implementare anche un operatore di crossover specifico per il problema.

Crossover a un punto

In questo crossover a un punto, viene selezionato un punto di crossover casuale e le code dei suoi due genitori vengono scambiate per ottenere nuovi discendenti.

Crossover multipunto

Il crossover a più punti è una generalizzazione del crossover a un punto in cui i segmenti alternati vengono scambiati per ottenere nuove molle.

Crossover uniforme

In un crossover uniforme, non dividiamo il cromosoma in segmenti, piuttosto trattiamo ciascun gene separatamente. In questo, essenzialmente lanciamo una moneta per ogni cromosoma per decidere se sarà incluso o meno nella prole. Possiamo anche polarizzare la moneta su un genitore, per avere più materiale genetico nel bambino da quel genitore.

Ricombinazione aritmetica intera

Questo è comunemente usato per rappresentazioni di numeri interi e funziona prendendo la media ponderata dei due genitori utilizzando le seguenti formule:

• Child1 = α.x + (1-α) .y
• Bambino2 = α.x + (1-α) .y

Ovviamente, se α = 0,5, allora entrambi i figli saranno identici come mostrato nell'immagine seguente.

Davis 'Order Crossover (OX1)

OX1 viene utilizzato per crossover basati su permutazioni con l'intenzione di trasmettere informazioni sull'ordinamento relativo alle derivazioni. Funziona come segue:

• Crea due punti di crossover casuali nel genitore e copia il segmento tra di loro dal primo genitore alla prima prole.

• Ora, partendo dal secondo punto di incrocio nel secondo genitore, copia i numeri inutilizzati rimanenti dal secondo genitore al primo figlio, avvolgendo l'elenco.

• Ripeti per il secondo figlio con il ruolo del genitore invertito.

Esistono molti altri crossover come Partially Mapped Crossover (PMX), Order based crossover (OX2), Shuffle Crossover, Ring Crossover, ecc.