algorithm - resueltos - ejemplos de aplicaciones de algoritmos geneticos
Eficiencia de cruce en algoritmos genéticos. (6)
He implementado una serie de algoritmos genéticos para resolver una variedad de problemas. Sin embargo, sigo siendo escéptico acerca de la utilidad del cruce / recombinación.
Por lo general, primero implemento la mutación antes de implementar el cruce. Y después de implementar el crossover, normalmente no veo una aceleración significativa en la velocidad a la que se genera una buena solución candidata en comparación con el simple uso de la mutación y la introducción de algunos individuos aleatorios en cada generación para garantizar la genética.
Por supuesto, esto puede atribuirse a las malas elecciones de la función de cruce y / o las probabilidades, pero me gustaría obtener alguna explicación / evidencia concreta de por qué / si el cruce mejora o no los GA. ¿Ha habido algún estudio al respecto?
Entiendo el razonamiento detrás de esto: el cruce permite que las fortalezas de dos individuos se combinen en un solo individuo. Pero para mí es como decir que podemos unir a un científico y un jaguar para obtener un híbrido inteligente y rápido.
EDIT: En la respuesta de mcdowella, mencionó que encontrar un caso en el que el cruce puede mejorar en la escalada de una colina desde múltiples puntos de partida no es trivial. ¿Podría alguien dar más detalles sobre este punto?
Depende en gran medida de la suavidad de su espacio de búsqueda. Ejemplo perverso: si cada "genoma" se procesara antes de usarlo para generar "fenomas", entonces solo estaría haciendo una búsqueda aleatoria.
Caso menos extremo, esta es la razón por la que a menudo los enteros de código gris en GA.
Debe adaptar sus funciones de cruce y mutación a la codificación. Los GA se descomponen con bastante facilidad si les arrojas cálculos antipáticos. Si el cruce de A y B no produce algo que sea tanto A como B, entonces es inútil.
Ejemplo:
El genoma tiene una longitud de 3 bits, el bit 0 determina si se trata de una vivienda en tierra o en el mar. Los bits 1-2 describen funciones digestivas para criaturas terrestres y capacidades visuales para criaturas marinas.
Consideremos dos criaturas terrestres.
| bit 0 | bit 1 | bit 2
----+-------+-------+-------
Mum | 0 | 0 | 1
Dad | 0 | 1 | 0
Podrían cruzar entre los bits 1 y 2, dando como resultado un niño cuya función digestiva es un compromiso entre las mamás y los papás. Genial.
Este cruce parece razonable siempre que el bit 0 no haya cambiado . Si lo hace, entonces su función de cruce ha convertido algún tipo de agallas en algún tipo de ojos. Er ... Wut? Bien podría haber sido una mutación aleatoria.
Se plantea la pregunta de cómo el ADN soluciona este problema. Bueno, es a la vez modal y jerárquico. Hay secciones grandes que pueden cambiar mucho sin mucho efecto, en otras, una sola mutación puede tener efectos drásticos (como el bit 0 anterior). A veces, el valor de X afecta el comportamiento marcado por Y, y todos los valores de X son legales y pueden explorarse, mientras que una modificación de Y hace que el animal se vuelva seguro.
Los análisis teóricos de las AG a menudo utilizan codificaciones extremadamente rudimentarias y sufren más problemas numéricos que semánticos .
El cruce y la mutación !! En realidad ambos son necesarios. Crossover es un operador explorador, pero la mutación es explotadora. Teniendo en cuenta la estructura de las soluciones, el problema y la probabilidad de tasa de optimización, es muy importante seleccionar un valor correcto para Pc y Pm (probabilidad de cruce y mutación).
Compruebe este GA-TSP-Solver , utiliza muchos métodos de cruce y mutación. Puede probar cualquier cruce junto con mutaciones con probabilidades dadas.
Las dos obras seminales de John Holland "Adaptación en sistemas naturales y artificiales" y "Orden oculta" (menos formal) discuten la teoría del cruce en profundidad. La OMI, "Algoritmos genéticos en búsqueda, optimización y aprendizaje automático" de Goldberg tiene un capítulo muy accesible sobre fundamentos matemáticos que incluye conclusiones tales como:
Con crossover y reproducción ... esos esquemas con un rendimiento superior a la media y longitudes cortas definidas se muestrearán a tasas que aumentan exponencialmente.
Otra buena referencia podría ser "Una extensión de la teoría de la convergencia y una prueba de la complejidad del tiempo de los algoritmos genéticos" de Ankenbrandt (en "Fundamentos de los algoritmos genéticos" de Rawlins).
Me sorprende que el poder del cruce no haya sido evidente para usted en su trabajo; cuando comencé a usar algoritmos genéticos y vi cuán poderosamente "dirigido" parecía el cruce, sentí que obtuve una idea de la evolución que anuló lo que me habían enseñado en la escuela. Todas las preguntas sobre "¿cómo podría la mutación conducir a esto y aquello?" y "Bueno, a lo largo de tantas generaciones ..." parecían estar básicamente equivocados.
Mi impresión es que la escalada desde múltiples inicios aleatorios es muy efectiva, pero que tratar de encontrar un caso en el que el cruce pueda mejorar esto no es trivial. Una referencia es "Crossover: The Divine Afflatus in Search" de David Icl˘anzan, que afirma
La teoría de GA tradicional se basa en la Hipótesis de Bloque de Construcción (BBH) que establece que los Algoritmos Genéticos (AG) funcionan mediante el descubrimiento, el énfasis y la recombinación de esquemas de orden bajo en cadenas de alta calidad, de manera muy paralela. Históricamente, los intentos de capturar las características del paisaje de aptitud topológica que ejemplifican este proceso intuitivo y directo, han sido casi infructuosos. Los métodos recombinantes basados en la población se habían superado repetidamente en las suites de pruebas abstractas de diseño especial, por diferentes variantes de algoritmos basados en mutaciones.
Un artículo relacionado es "Superar la dificultad jerárquica al escalar la estructura de bloques de construcción" por David Iclănzan y Dan Dumitrescu, que afirma
La hipótesis de los bloques de construcción sugiere que los algoritmos genéticos (GA) son adecuados para problemas jerárquicos, donde una solución eficiente requiere la descomposición adecuada del problema y el ensamblaje de la solución de la sub-solución con fuertes interdependencias no lineales. El documento propone un espacio de escalador que opera sobre el bloque de construcción (BB) que puede abordar problemas jerárquicos de manera eficiente.
Tienes razón al ser escéptico acerca de la operación de cruce. Hay un artículo llamado "Sobre la efectividad del cruce en la optimización evolutiva simulada" (Fogel y Stayton, Biosystems 1994). Está disponible de forma gratuita en 1 (una buena fuente de muchos otros excelentes pubs de Fogel).
Por cierto, si aún no lo has recomendado, te recomendamos que busques una técnica llamada "Evolución diferencial". Puede ser muy bueno para resolver muchos problemas de optimización.
depende principalmente del espacio de búsqueda y el tipo de cruce que está utilizando. Para algunos problemas, encontré que al usar el cruce al principio y luego a la mutación, acelerará el proceso para encontrar una solución; sin embargo, este no es un buen enfoque ya que acabaré encontrando soluciones similares. Si utilizamos tanto la transición como la mutación, generalmente obtengo mejores soluciones optimizadas. Sin embargo, para algunos problemas el cruce puede ser muy destructivo.
Además, los operadores genéticos por sí solos no son suficientes para resolver problemas grandes / complejos. Cuando sus operadores no mejoran su solución (de modo que cuando no aumentan el valor de la forma física), debe comenzar a considerar otras soluciones como la evolución incremental, etc.