Cruce de dos enteros en bits

Actualmente estoy tratando de darme cuenta de un ejemplo muy simple de algoritmos genéticos.Cruce de dos enteros en bits

En un punto, debe hacer un "cruce" (biología) con dos números (padres) para obtener un "niño".

puede encontrar una explicación de Cross-Over aquí: (. El segundo ejemplo, el "de un punto" más fácil Cross-Over es el que yo estoy tratando de hacer)

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

Los cromosomas (padres e hijos) son números, pero el "cruce" será un poco operativo.

he encontrado una solución para uno de los "cromosomas", que es el siguiente:

mover la cantidad x bits a la derecha (>>> operador)
y luego pasar los bits de nuevo X posiciones pero esta vez hacia la izquierda (operador <<)

Esto mantendría el final de uno de los cromosomas y llenará el inicio con 0s.

Pero realmente no sé cómo resolver el problema del otro cromosoma y luego también hacer el Cruce.

(Probablemente un XOR vez me quedé con el inicio/final de los cromosomas y llena el resto con 0s.)

o debería incluso abordar este problema desde otro ángulo?

Fuente

2012-07-29 m_vdbeek

es que siempre sabes lo grande que sus dos entradas son como números (por ejemplo, números enteros de 16 bits) ? – David

Sí, siempre son enteros de 16 bits. Una cosa que se puede modificar es el% de Cross-Over. Por ejemplo, el 75% mantendría los primeros 4 (25%) bits del padre A y luego seguiría esos 4 bits con 12 (75%) bits del padre B. –

Si la fracción de la Cruz-Over es p (por ejemplo, p = 0,25), entonces esto debería funcionar:

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

Un par de notas:

esto es sólo pseudocódigo . Es posible que desee algunos moldes allí.
Esto se trata p de manera diferente a como lo tratas en tu comentario anterior. (Basta con sustituir p con 1-p para llegar a su definición de p.)

Fuente

2012-07-29 01:11:24 David

Guau, ¡mente = ¡volado! Me llevará algo de tiempo entender este código. ^^ ¡Gracias por tu respuesta rápida! –

Bueno, cambiando el patrón 0xffff a la derecha y luego a la izquierda está haciendo lo mismo que tenía en su descripción, así que si su p = .5, su máscara1 terminará siendo 0xff después del cambio a la derecha, y luego 0xff00 después del cambio a la izquierda espalda. XORing esto con 0xffff te proporciona todos los bits que no están activados en mask2. – David

¡Gracias por la explicación! –

Un enfoque ingenuo sería utilizar 4 variables locales:

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

A continuación, asignar la entrada chromatid1 a la primera dos variables y chromatid2 a las dos últimas variables.

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

Realizar un desplazamiento a la derecha en las variables de cromátidas Start hasta el punto de cruce, luego a la izquierda por desplazamiento de la misma cantidad exacta. En las variables de cromátida End, haga un desplazamiento hacia la izquierda hasta el punto de cruce, y luego hacia la derecha la misma cantidad.

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 esto, se puede cruzar el inicio de una con el extremo de la otra:

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

Fuente

2012-07-29 01:16:10 saluce

Respuesta

Cuestiones relacionadas