¿Por qué añadir Crossover a mi algoritmo genético me da peores resultados?

Question

He implementado un Algoritmo Genético para resolver el Problema del Viajero Vendedor (TSP). Cuando uso solo mutación, encuentro mejores soluciones que cuando agrego el cruce. Sé que los métodos de cruce normales no funcionan para TSP, así que implementé los métodos Ordered Crossover y PMX Crossover, y ambos tienen malos resultados.

Éstos son los otros parámetros que estoy usando:

Mutación: sola mutación Intercambiar o invertido Subsequence Mutación (as described by Tiendil here) con tasas de mutación probados entre el 1% y el 25%.

Selección: Ruleta Selección Rueda función

aptitud: 1/distancia de recorrido

Tamaño de la población: Probado 100, 200, 500, que también corren el GA 5 veces para que Tengo una variedad de poblaciones iniciales.

parada Condición: 2500 generaciones

Con el mismo conjunto de datos de 26 puntos, por lo general obtener resultados de unos 500-600 distancia utilizando puramente mutación con altas tasas de mutación. Al agregar crossover, mis resultados generalmente están en el rango de distancia 800. La otra cosa confusa es que también he implementado un algoritmo de escalada en colina muy simple para resolver el problema y cuando corro esas 1000 veces (más rápido que correr el GA 5 veces) obtengo resultados alrededor de 410-450 de distancia, y esperaría para obtener mejores resultados usando una GA.

¿Alguna idea de por qué mi GA se desempeña peor cuando agrego crossover? ¿Y por qué funciona peor que un algoritmo Hill-Climb simple que debería atascarse en máximos locales ya que no tiene forma de explorar una vez que encuentra un máximo local?

Answer 1

Parece que su operador de crossover está introduciendo demasiada aleatoriedad en las nuevas generaciones, por lo que está perdiendo su esfuerzo de cálculo tratando de mejorar las soluciones malas. Imagine que el algoritmo Hill-Climb puede mejorar una solución dada a lo mejor de su vecindad, pero su algoritmo genético solo puede hacer mejoras limitadas a poblaciones (soluciones) casi aleatorias.

También vale la pena decir que GA no es la mejor herramienta para resolver el TSP. De todos modos, debería ver algunos ejemplos de cómo implementarlo. p.ej. http://www.lalena.com/AI/Tsp/

Answer 2

Una razón por la que sus resultados empeoran cuando se agrega el cruce, porque puede no estar haciendo lo que debería: combinar las mejores características de dos personas. Intente con una baja probabilidad de cruce ¿puede ser? La diversidad de la población podría ser un problema aquí. Morrison y De Jong en su trabajo Measurement of Population Diversity propone una nueva medida de la diversidad. Usando esa medida, puede ver cómo la diversidad de su población está cambiando a través de las generaciones. Vea qué diferencia hace cuando usa el filtro cruzado o no usa el filtro cruzado (crossover).

Además, podría haber algún pequeño error/detalle perdido en su implementación de OX o PMX. Tal vez has pasado por alto algo? Por cierto, ¿puede querer probar el operador de cruce Edge Recombination? (Pyevolve tiene una implementación).

Answer 3

Para idear estrategias "innovadoras", los algoritmos genéticos generalmente usan crossover para combinar proezas de diferentes soluciones candidatas con el fin de explorar el espacio de búsqueda muy rápidamente y encontrar nuevas estrategias de mayor aptitud física, nada diferente a la funcionamiento interno de la inteligencia humana (esta es la razón por la que es discutible que nunca realmente "inventemos" nada, sino que simplemente mezclamos cosas que ya conocemos).

Al hacerlo (combinando aleatoriamente diferentes individuos) el cruce no conserva la simetría ni el orden, y cuando el problema depende mucho de la simetría o del orden de los genes en el cromosoma (como en su caso particular) de hecho, es probable que la adopción de cruces dé lugar a peores resultados. Como se menciona a sí mismo, es bien conocido que se sabe que el crossover no funciona para el vendedor ambulante.

Vale la pena subrayar que sin esta hazaña de simetría los algoritmos genéticos cruzados no serían capaces de llenar "nichos" evolutivos (donde la falta de simetría suele ser necesaria) - y es por eso que el cruce (en todas sus variantes) es esencialmente importante en la gran mayoría de los casos.

Answer 4

Con la selección de ruedas de ruleta, está introduciendo malos padres en la mezcla. Si desea cargar la rueda de alguna manera para elegir mejores padres, esto puede ayudar.

Recuerde, gran parte de su población podría ser padres no aptos. Si no está ponderando la selección de padres, es muy probable que genere consistentemente malas soluciones que invadan el grupo. Pondere su selección para elegir mejores padres con más frecuencia, y use la mutación para corregir un grupo similar agregando aleatoriedad.

Answer 5

Puede intentar introducir elitismo en su proceso de selección. Elitismo significa que los dos individuos de mayor aptitud en la población se conservan y se copian a la nueva población antes de realizar cualquier selección. Después de que se complete el elitismo, la selección continúa de forma normal. Hacer esto significa que no importa qué padres sean seleccionados por la rueda de la ruleta o qué produzcan durante el cruce, las dos mejores personas siempre se conservarán. Esto evita que la nueva población pierda aptitud porque sus dos mejores soluciones no pueden ser peores que la generación anterior.