Cross-over due interi bit a bit

Question

Attualmente sto cercando di realizzare un esempio molto semplice di algoritmi genetici.

A un certo punto, devi fare un "Cross-Over" (biologia) con due numeri (genitori) per ottenere un "bambino".

Potete trovare una spiegazione di Cross-Over qui: (. La seconda illustrazione, il "one-point" più facile Cross-Over è quello che sto cercando di fare)

How to "crossover" two strings (1234 & abcd -> 12cd & ab34)

I cromosomi (genitori e figlio) sono numeri ma il "Cross-Over" sarà un'operazione un po '.

ho trovato una soluzione per uno dei "cromosomi", che è la seguente:

• movimento l'importo bit X a destra (>>> operatore)
• e quindi spostare i bit nuovamente X posizioni ma questa volta a sinistra (operatore <<)

Quindi questo manterrebbe la fine di uno dei cromosomi e riempirà l'inizio con 0s.

Ma io non so davvero come risolvere il problema dell'altro cromosoma e poi faccio anche il Cross-Over.

(Probabilmente un XOR una volta ho tenuto l'inizio/fine dei cromosomi e riempito il resto con 0s.)

o forse dovrei anche affrontare questo problema da un'altra angolazione?

Answer 1

Se la frazione del Cross-Over è p (per esempio, p = 0,25), allora questo dovrebbe funzionare:

mask1 = ((0xffff >> 16*p) << 16*p) 
mask2 = 0xffff^mask1 
output1 = (input1 & mask1)^(input2 & mask2) 
output2 = (input1 & mask2)^(input2 & mask1) 

Un paio di note:

• questo è solo pseudocodice . Potresti volere dei calchi lì dentro.
• Questo tratta p diversamente da come lo tratti nel tuo commento sopra. (Basta sostituire p con 1-p per raggiungere la vostra definizione di p.)

Answer 2

Un approccio più semplice sarebbe quella di utilizzare 4 variabili locali:

int chromatid1Start; 
int chromatid1End; 
int chromatid2Start; 
int chromatid2End; 

Quindi, assegnare l'ingresso chromatid1 alla prima due variabili e chromatid2 alle ultime due variabili.

chromatid1Start = chromatid1; 
chromatid1End = chromatid1; 
chromatid2Start = chromatid2; 
chromatid2End = chromatid2; 

Eseguire un diritto-shift sulle variabili cromatidi Start fino al punto di crossover, poi a sinistra, spostare la stessa quantità esatta. Sulle variabili cromatidiche End, spostare a sinistra fino al punto di crossover, quindi spostare a destra lo stesso valore.

chromatid1Start = (chromatid1Start >> 16 * crossoverPercent) << 16 * crossoverPercent; 
chromatid1End = (chromatid1End << 16 * (1 - crossoverPercent)) >> 16 * (1 - crossoverPercent); 
chromatid2Start = (chromatid2Start >> 16 * crossoverPercent) << 16 * crossoverPercent; 
chromatid2End = (chromatid2End << 16 * (1 - crossoverPercent)) >> 16 * (1 - crossoverPercent); 

Con questo, si può attraversare l'inizio di uno con la fine dell'altro:

int daughterChromatid1 = chromatid1Start + chromatid2End; 
int daughterChromatid2 = chromatid2Start + chromatid1End;