- Sobrecruzamiento (computación evolutiva)
-
Sobrecruzamiento (computación evolutiva)
El sobrecruzamiento es un operador genético utilizado en los algoritmos genéticos para generar variación en la programación de un cromosoma o cromosomas de una generación a la siguiente. Es análogo a la recombinación de la reproducción sexual biológica, en la que los algoritmos genéticos se inspiran.
Contenido
Técnicas de sobrecruzamiento
Existen muchas técnicas de sobrecruzamiento para organismos que utilizan diferentes estructuras para almacenar los datos.
Sobrecruzamiento en un punto
Se selecciona un punto en el vector del primer parental. Todos los datos más allá de este punto en el vector del organismo se intercambiarán entre los dos organismos parentales. Los organismos resultantes son los hijos:
Sobrecruzamiento en dos puntos
El sobrecruzamiento en dos puntos requiere seleccionar dos puntos en los vectores de los organismos parentales. Todos los datos entre los dos puntos se intercambian entre los organismos parentales, creando dos organismos hijos:
Corte y empalme
Otro variante de sobrecruzamiento, el enfoque "cortar y empalmar", ocasiona un cambio de la longitud de los vectors de los hijos. la razón para esta diferencia es que se selecciona un punto de corte diferente para cada vector parental:
Sobrecruzamiento uniforme y uniforme medio
En ambos de estos esquemas los dos padres se combinan para producir los descendientes.
En el esquema de sobrecruzamiento uniforme (UX por el inglés Uniform Crossover), los bits del vector se comparan individualmente entre ambdos padres. Los bits se intercambian con una probabilidad fijada, usualmente 0.5.
En el esquema de sobrecruzamiento uniforme medio (HUX del inglés Half Uniform Crossover), exactamente la mitad de los bits que son diferentes se intercambian. Por esto se necesario calcular la distancia de Hamming (número de bits diferentes). Este número se divide entre dos, y el número resultante es la cantidad de bits diferentes que tiene que ser intercambiada entre los parentales.
Sobrecruzamiento de cromosomas ordenados
Dependiendo de cómo representa la solución el cromosoma, un cambio directo puede no ser posible.
Un caso de ello se da cuando el cromosoma es una lista ordenada, como la lista ordenada de las ciudades visitadas en el problema del viajero. Un punto de sobrecruzamiento se selecciona en los padres. Puesto que el cromosoma es una lista ordenada, un cambio directo introduciría duplicados y extraería candidatos necesarios de la lista. En cambio, el cromosoma hasta el punto de sobrecruzamiento se retiene para cada padre. La información después del punto de sobrecruzamiento se ordena como está ordenada en el otro padre. Por ejemplo, si nuestros dos padres son ABCDEFGHI e IGAHFDBEC y nuestro punto de sobrecruzamiento se establece después del cuarto carácter, entonces los hijos que resultan serían ABCDIGHFE e IGAHBCDEF.
Tendencias del Sobrecruzamiento
Para operadores de sobrecruzamiento que intercambian secciones contiguas de los cromosomas (p. ej. k-point) la ordenación de las variables se puede tornar importante. Esto es especialmente cierto cuando las buenas soluciones contienen bloques de construcción que podrían ser interrumpidas por un operador de sobrecruzamiento no respetuoso.
Véase también
- Algoritmo genético
- Operador genético (computación evolutiva)
- Mutación (computación evolutiva)
Categoría: Computación evolutiva
Wikimedia foundation. 2010.
