computer science - que - Algoritmos evolutivos: Desglose óptimo de la repoblación
que es un algoritmo genetico en informatica (8)
Todo está en el título, pero aquí hay un desglose para cualquiera que esté interesado en Algoritmos Evolutivos:
En un EA, la premisa básica es que genere aleatoriamente una cierta cantidad de organismos (que en realidad son solo conjuntos de parámetros), corríjalos contra un problema y luego deje que los mejores jugadores sobrevivan.
Luego repoblar 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 a las que se les permite cruzar 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 probé la teoría de múltiples islas, y también me interesan tus 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 por adelantado!
Este es un tema muy debatido (en la literatura y Melanie, et al libros ) 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.
Entonces, como TraumaPony sugirió, ajústelo usted mismo para cada problema que esté resolviendo o escriba 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 cruce y mutación también se debaten constantemente en cada clase de problemas entregados a GA y GP.
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 noté que mi 10% superior era más o menos idéntico. Entonces aumenté el azar al 30%. Eso ayudó a algunos, pero no mucho.
Probé isla múltiple, 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, número loco de generaciones para obtener resultados. En su mayoría, el código aprendió a hackear mi evaluación de la condición física.
Es realmente fácil obtener mejores resultados, así que no te preocupes por mantener muchos de ellos. 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.
Sigo creyendo que las respuestas óptimas a su pregunta se pueden encontrar al observar fenómenos naturales, como en un artículo reciente sobre la aleatoriedad de las trayectorias de vuelo de la mosca de la fruta, por lo que puede salir bien.
Probablemente la mejor respuesta es simplemente ejecutarlo y ajustarlo, no tengas miedo de modificarlo bastante, las poblaciones son robustas. Asegúrese de implementar una forma de guardar y continuar.
Los mejores recursos que he encontrado para GA y EA fueron los libros de John Koza sobre Programación Genética . 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 te da respuestas concretas, pero no creo que haya respuestas concretas, GA es impredecible por su naturaleza y ajustar ese tipo de parámetros puede ser 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'' quieres obtener.
Suponiendo que tiene un método para cuantificar el porcentaje superior X% de ejecutantes, sugiero que en lugar de utilizar un umbral codificado, analice la distribución de rendimiento y haga que su punto de corte esté en el rango de la primera caída importante en el rendimiento y luego ajuste sus 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.
Sabes lo que podrías hacer ... Podrías escribir un algoritmo genético para determinar esa distribución óptima.
Pero, por lo general, mantengo el 12% superior y el 28% de cruces; con 30% cada uno para los demás.
Aparentemente, hay algunas respuestas que sugieren el uso de una 2ª GA para determinar los parámetros óptimos para la 1ª GA, sin mencionar cómo determinar los parámetros óptimos para la 2ª. No puedo evitar preguntarme sobre las creencias religiosas de aquellos que sugieren este enfoque ...
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 cae 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, opté por un genotipo multicromosómico. 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.
Por otro lado, tiendo a hacer tanto el cruce como la mutación para cada niño.
Para GA generacionales, trato de evitar el elitismo por completo, pero cuando habito en múltiples islas, mantengo a la elite superior de cada isla. Cuando las islas se unen, las elites pueden criarse juntas.
Como otros han mencionado, 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 considerar 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 manera 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 obtienes un desglose, hay algunas cosas que considerar ... por ejemplo, la duplicación (una gran cantidad de individuos idénticos o recientemente idénticos en la primera endogamia). Para reducir esto, es posible que desee barrer su población entre generaciones y reemplazar las duplicaciones con nuevos individuos aleatorios o mestizos.
Dicho esto, mi enfoque actual es mantener el 1% superior, cruzar el 20% superior en un nuevo 20%, cruzar el 40% superior en el siguiente 20%, cruzar el 90% superior para generar el siguiente 20% y aleatoriamente generar 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.