Cruce en Algoritmo Genético

Crossover es un operador genético utilizado para variar la programación de un cromosoma o cromosomas de una generación a la siguiente. Crossover es reproducción sexual. Se seleccionan al azar dos hilos del grupo de apareamiento para cruzarlos y producir una descendencia superior. El método elegido depende del método de codificación.

Diferentes tipos de cruce:

Punto de cruce único: se selecciona un punto de cruce en la string del organismo principal. Todos los datos más allá de ese punto en la string del organismo se intercambian entre los dos organismos principales. Las strings se caracterizan por el sesgo posicional.


Crossover de Dos Puntos: Este es un caso específico de una técnica de Crossover de N-puntos. Se eligen dos puntos aleatorios en los cromosomas individuales (strings) y el material genético se intercambia en estos puntos.


Cruzamiento uniforme: cada gen (bit) se selecciona aleatoriamente de uno de los genes correspondientes de los cromosomas originales.
Utilice el lanzamiento de una moneda como técnica de ejemplo.

Es posible que el cruce entre dos buenas soluciones no siempre produzca una solución mejor o tan buena. Dado que los padres son buenos, la probabilidad de que el hijo sea bueno es alta. Si la descendencia no es buena (solución deficiente), se eliminará en la siguiente iteración durante la «Selección».
Problemas con el cruce:

• Dependiendo de la codificación, los cruces simples pueden tener una alta probabilidad de producir descendencia ilegal.
  Por ejemplo, en TSP con codificación binaria o de ruta simple, la mayoría de los descendientes serán ilegales porque no todas las ciudades estarán en los descendientes y algunas ciudades estarán allí más de una vez.
• El cruce uniforme a menudo se puede modificar para evitar este problema
  . en TSP con codificación de ruta simple:
  Donde la máscara es 1, copia las ciudades de un padre
  Donde la máscara es 0, elige las ciudades restantes en el orden del otro padre