Sin crossover, todo lo que tienes son mutaciones locales. Esto significa que el cambio sucederá lentamente y será muy difícil sacar a su población de un óptimo local.
Con crossover, puede combinar soluciones parciales de diferentes candidatos. Esto a menudo significa hacer un salto bastante grande de cualquiera de los padres, lo que significa que puede salir de un óptimo local un poco más fácilmente.
Para que el crossover funcione, debe asegurarse de que su representación haga posible que el crossover se recombine en algo sensible.
- ¿Qué hace que NP-hard sea más difícil?
- Cómo entender la notación big-O
- Cómo resolver el problema de invertir la cadena dada si el tamaño de la cadena es mayor que el tamaño de mi RAM
- ¿Las funciones de JavaScript como map (), reduce () y filter () ya están optimizadas para recorrer la matriz?
- ¿Qué es el algoritmo de sincronización YAWNS?
Por ejemplo, para el problema del vendedor ambulante, una representación para un recorrido es [índice de la primera ciudad visitada, índice de la segunda ciudad visitada fuera de la lista de todas las ciudades no visitadas hasta ahora, …]. En esta representación, el uso de crossover tiende a conducir a un recorrido cuya última parte no se parece a ninguno de los padres, ya que el significado de cada coordenada depende de las coordenadas anteriores. Por ejemplo, en el recorrido [3,2,1], la coordenada final corresponde a la ciudad número 1; pero en el recorrido [1,1,1], la coordenada final corresponde a la ciudad número 3. El mismo valor en la misma posición, pero con un significado muy diferente.
Por supuesto, las cosas podrían ser peores. Otra representación para TSP serían las permutaciones reales. En ese caso, el cruce probablemente conducirá a una gira imposible y sin sentido. Por ejemplo, los recorridos del ejemplo anterior ahora se representarían como [3,2,1] y [1,2,3], que podrían combinarse a través de un cruce en [3,2,3], que claramente no es un recorrido válido
Si puede encontrar una representación significativa que permita el cruce, entonces puede ser una herramienta muy poderosa. De lo contrario, debe atenerse a las mutaciones (pero quizás aumente un poco la tasa de mutación para tratar de lidiar con el problema de los óptimos locales).
