Sobrecruzamiento (computación evolutiva)

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:

Computational.science.Genetic.algorithm.Crossover.One.Point.svg

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:

Computational.science.Genetic.algorithm.Crossover.Two.Point.svg

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:

Computational.science.Genetic.algorithm.Crossover.Cut.and.Splice.svg

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.

Computational.science.Genetic.algorithm.Crossover.Uniform.Crossover.svg

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.

Computational.science.Genetic.algorithm.Crossover.Half.Uniform.Crossover.svg

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

Obtenido de "Sobrecruzamiento (computaci%C3%B3n evolutiva)"

Wikimedia foundation. 2010.

Игры ⚽ Поможем написать курсовую

Mira otros diccionarios:

  • Cromosoma (computación evolutiva) — Saltar a navegación, búsqueda Para información sobre cromosomas en biología, véase cromosoma. En los algoritmos genéticos, un cromosoma (también a veces llamado genoma) es un conjunto de parámetros que definen una solución propuesta al problema… …   Wikipedia Español

  • Algoritmo evolutivo — Los algoritmos evolutivos son métodos de optimización y búsqueda de soluciones basados en los postulados de la evolución biológica. En ellos se mantiene un conjunto de entidades que representan posibles soluciones, las cuales se mezclan, y… …   Wikipedia Español

  • Algoritmo genético — Un algoritmo es una serie de pasos organizados que describe el proceso que se debe seguir, para dar solución a un problema específico. En los años 1970, de la mano de John Henry Holland, surgió una de las líneas más prometedoras de la… …   Wikipedia Español

  • Operador genético — Un operador genético es una función empleada en los algoritmos genéticos para mantener la diversidad genética de una población. La variación genética es necesaria para el proceso de evolución. Los operadores genéticos utilizados en los algoritmos …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”