algoritmos evolutivos: Óptimo Repoblación averías

Question

Es realmente todo en el título, pero aquí hay un desglose para cualquier persona que esté interesada en algoritmos evolutivos:

En un EA, la premisa básica es que se genera de forma aleatoria un cierto número de organismos (que en realidad son solo conjuntos de parámetros), ejecútelos contra un problema y luego permita que los mejores jugadores sobrevivan.

Repobulará con una combinación de cruces de supervivientes, mutaciones de los supervivientes y también un cierto número de nuevos organismos aleatorios.

Haz eso miles de veces y surgen organismos eficientes.

Algunas personas también hacen cosas como introducir múltiples "islas" de organismos, que son poblaciones separadas que pueden cruzarse de vez en cuando.

Entonces, mi pregunta es: ¿cuáles son los porcentajes de repoblación óptimos?

He estado manteniendo el 10% de los mejores artistas y repoblando con 30% de cruces y 30% de mutaciones. El 30% restante es para organismos nuevos.

También he probado la teoría de isla múltiple, y también me interesan sus resultados.

No se me escapa que este es exactamente el tipo de problema que EA podría resolver. ¿Conoces a alguien que intente eso?

¡Gracias de antemano!

Answer 1

Inicialmente intenté modelar lo que pensé que eran los sistemas orgánicos. Finalmente decidió que no era bueno, y fue más agresivo, con 10% guardado, 20% mutado, 60% cruzado y 10% aleatorio.

Entonces me di cuenta de mi top 10% eran todos más o menos iguales. Entonces aumenté el azar al 30%. Eso ayudó a algunos, pero no mucho.

Probé varias islas, omisión de generación y resiembra, lo que dio mejores resultados, pero aún muy insatisfactorio, muy poca variación en el 10% superior, muchísimas generaciones para obtener resultados. En su mayoría, el código aprendió a hackear mi evaluación de la condición física.

Es muy fácil de conseguir mejor rendimiento, por lo que no se preocupe de mantener muchos de ellos alrededor. Los cruces ayudan a reducir los rasgos positivos y negativos, por lo que son útiles, pero en realidad lo que quieres obtener es una buena cantidad de cruces aleatorios. Concéntrate en las mutaciones y en los nuevos randoms para incorporar características, y deja que los híbridos y los mejores jugadores solo haga un seguimiento de los mejores y refinelos más lentamente. IE: las cosas basadas en la última generación solo están encontrando mejores máximos locales, los randoms encuentran mejores máximos globales.

todavía creen respuestas óptimas a su pregunta se puede encontrar mediante la observación de los fenómenos naturales, tales como en un artículo reciente sobre la aleatoriedad de las trayectorias de vuelo mosca de la fruta, por lo que puede ser un éxito.

Probablemente la mejor respuesta es simplemente ejecutarlo y modificarlo, no tenga miedo de modificarlo bastante, las poblaciones son robustas. Asegúrese de implementar una forma de guardar y continuar.

Answer 2

Sabe lo que podría hacer ... Podría escribir un algoritmo genético para determinar la distribución óptima.

Pero, generalmente mantengo el 12% superior, y el 28% de cruces; con 30% cada uno para los demás.

Answer 3

Los mejores recursos que he encontrado para GA y EA fueron los libros de John Koza en Genetic Programming. Abarca el tema en profundidad: técnicas para codificar el genoma, mutación aleatoria, reproducción, ajuste de la función de aptitud.

Personalmente, solo he escrito un pequeño puñado de simuladores con fines pedagógicos. Lo que encontré fue que la forma en que sintonicé esos porcentajes estaba relacionada con los detalles de la función de acondicionamiento físico que estaba usando, la cantidad de mutaciones al azar que había introducido y lo 'inteligente' que había intentado hacer la mutación y la crianza: descubrí que menos 'inteligente' Intenté hacer el mutador y la lógica cruzada, cuanto más rápido la población mejoraba su puntaje de condición física, también descubrí que había sido demasiado conservador en cuanto a la probabilidad de mutación, mis carreras iniciales alcanzaron máximos locales y tuve una Es difícil salir de ellos.

Nada de esto le da respuestas concretas, pero no creo que haya respuestas concretas, GA es impredecible por su naturaleza y afinar ese tipo de parámetros puede seguir siendo un poco artístico. Por supuesto, siempre puedes probar un meta-GA, usando esos parámetros como un cromosoma, buscando configuraciones que produzcan un estado físico más rápido en la GA base que estás ejecutando.

Depende de cómo "meta" que desea obtener.

Answer 4

Este es un tema muy debatido (en la literatura y Melanie, et al books) que parece ser muy específico de un dominio. Lo que funciona para un problema de un tipo con n parámetros casi nunca funcionará para otro problema, otro dominio u otro conjunto paramétrico.

Por lo tanto, como se sugiere TraumaPony, ajustar usted mismo para cada problema que se está resolviendo o escribir algo para optimizarlo para usted. Lo mejor que puede hacer es realizar un seguimiento de todos sus experimentos de "perilla" y de ajuste fino para que pueda trazar el terreno de la solución y tener una idea de cómo optimizar dentro de ese espacio rápidamente. Pruebe también técnicas alternativas como el alpinismo para que pueda tener una línea de base que superar.

@Kyle Burton: las tasas de crossover frente a las mutaciones también son constantly debated en cada clase de problemas entregados a GA y GP.

Answer 5

Suponiendo que tiene un método para cuantificar el porcentaje X% superior, sugiero que en lugar de utilizar un umbral codificado, analice la distribución de rendimiento y haga que su corte esté en el rango de la primera caída importante en el rendimiento y luego sintonizar tus cruces, mutaciones y nuevos organismos para llenar los vacíos. De esta forma, si tiene una ejecución muy "productiva" en la que se produjeron muchas variaciones, no arrojará un número significativo de personas de alto rendimiento. Además, si tiene una ejecución "improductiva" puede eliminar más organismos existentes a favor de organismos más nuevos que deberían ocupar su lugar.

Answer 6

No parece haber algunas respuestas que sugieren el uso de un segundo GA para determinar los parámetros óptimos para la primera GA, con ninguna mención de cómo determinar los parámetros óptimos para la segunda. No puedo evitar preguntarme acerca de las creencias religiosas de aquellos que sugieren este enfoque ...

Answer 7

He tenido cierto éxito al aumentar la diversidad de la población estableciendo la mutación y el cruce de un par de genes de los cromosomas originales.

Esto funciona hasta que la tasa de mutación se reduce a cero; dado que es probable que haya una presión evolutiva periódica para hacer esto, debe intentar asegurarse de que estos genes tengan una frecuencia mínima.

En la práctica, he optado por un genotipo múltiples cromosoma. Un cromosoma codificado para la función reproductiva del otro.El 'cromosoma de reproducción' más pequeño tenía tasas fijas razonables para la mutación y el cruce.

Descubrí que esto detendría la meseta clásica y la convergencia de la población.

Como un lado, tiendo a hacer ambos crossover y mutación para cada niño.

Para los GA generacionales, trato de evitar el elitismo por completo, pero cuando habito en varias islas, mantengo la elite superior de cada isla. Cuando las islas se unen, las elites pueden criarse juntas.

Answer 8

Como han mencionado otros, la combinación óptima dependerá de su problema específico y de otros factores específicos del problema, como el tamaño del espacio de la solución.

Antes de analizar el desglose de la evolución de una generación a la siguiente, es importante tener en cuenta el tamaño de cada generación. En general, mi enfoque es comenzar con una población bastante grande (~ 100k-500k individuos) de individuos bastante diversos, lo cual es algo que Koza sugiere en algunos de sus trabajos. Para obtener esta diversidad desde el principio, puede dividir su espacio de solución en cubos, y luego asegurarse de que al menos una cierta cantidad de personas caiga en cada cubeta. (Por ejemplo, si tiene una representación en árbol para cada individuo, asegúrese de que se creen cantidades iguales de profundidad 2, 3, ..., max_depth)

En cuanto a su pregunta real, no hay una forma clara de abordarla, pero dependiendo de su problema, es posible que desee enfatizar la aleatoriedad o quitarle importancia. Cuando desee enfatizarlo, debe mantener intactos a menos individuos e introducir un mayor número de nuevos individuos al azar. En general, le gustaría hacer esto si hay muchos máximos locales en su espacio de solución y desea tener una búsqueda más amplia.

Cuando obtiene un desglose, hay algunas cosas que considerar ... en primer lugar, la duplicación (una gran cantidad de individuos idénticos o nuevos en la primera endogamia). Para reducir esto, es posible que desee examinar su población entre generaciones y reemplazar las duplicaciones con nuevas personas al azar o cruzadas.

Dicho esto, mi enfoque actual es mantener el 1% superior, cruzar el 20% superior en un 20% nuevo, cruzar el 40% superior en el siguiente 20%, cruzar el 90% superior para generar los próximos 20 %, y genera al azar el resto (39%). Si hay duplicados, los elimino y los reemplazo con nuevos individuos aleatorios.

No utilizo mutaciones porque el alto número de individuos al azar debería tener cuidado de agregar "mutaciones" durante el siguiente cruzamiento.