Algoritmos Evolutivos: Desglose Óptimo de Repoblación

Question

Realmente está todo 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 genera aleatoriamente un cierto número de organismos (que en realidad son solo conjuntos de parámetros), los enfrenta a un problema y luego deja que los que tienen el mejor desempeño sobrevivan.

Luego se repobla con una combinación de cruces de los sobrevivientes, mutaciones de los sobrevivientes y también una cierta cantidad de nuevos organismos aleatorios.

Haga 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 cruzarse de vez en cuando.

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

He estado manteniendo el 10% de mejor desempeño y repoblando con 30% de cruces y 30% de mutaciones. El 30% restante es para nuevos organismos.

También probé la teoría de las islas múltiples, y también estoy interesado en sus resultados.

No se me olvida que este es exactamente el tipo de problema que un EA podría resolver. ¿Eres consciente de que alguien intenta eso?

¡Gracias de antemano!

Answer 1

Al principio intenté modelar cómo pensaba que eran los sistemas orgánicos. Finalmente decidió que eso no era bueno, y se volvió más agresivo, con 10% mantenido, 20% mutado, 60% cruzado y 10% aleatorio.

Entonces noté que mi 10% superior era casi idéntico. Entonces aumenté el azar al 30%. Eso ayudó un poco, pero no mucho.

Intenté varias islas, salteando generaciones y volviendo a sembrar, lo que dio mejores resultados, pero aún muy insatisfactorio, muy poca variación en el 10% superior, un número de generaciones increíblemente largo para obtener algún resultado. Principalmente, el código aprendió a hackear mi evaluación de aptitud física.

Es realmente fácil obtener los mejores resultados, así que no te preocupes por mantener a muchos de ellos cerca. Los cruces ayudan a reducir los rasgos positivos y negativos, por lo que son útiles, pero realmente lo que quieres obtener es una buena selección aleatoria. Céntrate en las mutaciones y los nuevos randoms para incorporar características, y deja que los cruces y los mejores. solo haz un seguimiento de los mejores y refínalos más lentamente. IE: las cosas basadas en la última generación solo están buscando mejores máximos locales, los randoms encuentran mejores máximos globales.

Todavía creo que se pueden encontrar respuestas óptimas a su pregunta observando fenómenos naturales, como en un artículo reciente sobre la aleatoriedad de las rutas de vuelo de la mosca de la fruta, por lo que puede dar resultado.

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

Los mejores recursos que he encontrado para GA y EA fueron los libros de John Koza en Programación genética . Cubre el tema en profundidad: técnicas para codificar el genoma, mutación aleatoria, reproducción, ajuste de la función de condición física.

Personalmente, solo he escrito un pequeño puñado de simuladores con fines pedagógicos. Lo que descubrí fue que la forma en que ajusté esos porcentajes estaba relacionada con los detalles de la función de estado físico que estaba usando, cuánta mutación aleatoria había introducido y cuán "inteligente" había intentado hacer la mutación y la reproducción, descubrí que cuanto menos 'inteligente' Intenté hacer que el mutador y la lógica de cruce, cuanto más rápido mejorara la población su puntaje de condición física, también descubrí que había sido demasiado conservador en la probabilidad de mutación: mis carreras iniciales alcanzaron los máximos locales y tuve un 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 ajustar ese tipo de parámetros aún puede ser un poco un arte. Por supuesto, siempre puedes probar un meta-GA, usando esos parámetros como un cromosoma, buscando configuraciones que produzcan una aptitud más rápida en la base GA que estás ejecutando.

Depende de qué tan 'meta' quieras obtener.

Answer 3

Este es un tema muy debatido (en la literatura y Melanie, et al libros ) tema que parece ser muy específico del 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 sugirió TraumaPony, modifíquelo usted mismo para cada problema que esté resolviendo o escriba algo para optimizarlo. Lo mejor que puede hacer es realizar un seguimiento de todos sus '' perillas giratorias '' y experimentos de ajuste 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 la escalada para poder tener una línea de base que superar.

@Kyle Burton: las tasas de cruce y mutación también son constantemente debatido en cada clase de problemas entregados a GA y GP.

Answer 4

Suponiendo que tiene un método para cuantificar los mejores resultados del X% por ciento, sugeriría que, en lugar de utilizar un umbral codificado, analice la distribución del rendimiento y realice su corte en algún lugar dentro del rango de la primera caída importante en el rendimiento, y luego ajusta tus cruces, mutaciones y nuevos organismos para llenar los vacíos. De esta manera, si tiene un muy "productivo" en el cual muchas variaciones fueron exitosas, no arrojas un número significativo de personas de alto rendimiento. Además, si tiene un "no productivo" ejecutar puede eliminar más de los organismos existentes a favor de más organismos más nuevos que deberían ocupar su lugar.

Answer 5

He tenido cierto éxito al aumentar la diversidad de la población al establecer 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 tasa 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 sensibles para la mutación y el cruce.

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

Como comentario aparte, tiendo a hacer crossover y mutación para cada niño.

Para los GA generacionales, trato de evitar el elitismo por completo, pero cuando pueblan desde varias islas, mantengo a la élite superior de cada isla. Cuando las islas se unen, entonces las élites pueden reproducirse juntas.

Answer 6

Parece que hay algunas respuestas que sugieren usar una segunda GA para determinar los parámetros óptimos para la primera GA, sin mencionar cómo determinar los parámetros óptimos para la segunda. No puedo evitar preguntarme sobre las creencias religiosas de quienes sugieren este enfoque ...

Answer 7

Como otros han mencionado, la combinación óptima dependería de su problema específico y 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, que es algo que Koza sugiere en algunos de sus trabajos. Para obtener esta diversidad desde el principio, puede dividir el espacio de su solución en cubos y luego asegurarse de que al menos un cierto número de personas caiga en cada cubo. (Por ejemplo, si tiene una representación de árbol para cada individuo, asegúrese de que se creen cantidades iguales de profundidad 2, 3, ..., profundidad_máx.)

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 desestimarla. Cuando desee enfatizarlo, debe mantener intactos 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 debe considerar ... por ejemplo, la duplicación (muchas personas idénticas o recientemente idénticas en la endogamia superior). Para reducir esto, es posible que desee barrer su población entre generaciones y reemplazar las duplicaciones con nuevas personas aleatorias o cruzadas.

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 generar aleatoriamente el resto (39%). Si hay duplicados, los elimino y los reemplazo con nuevos individuos aleatorios.

No uso mutaciones porque la gran cantidad de individuos al azar debería encargarse de agregar "mutaciones". durante el siguiente cruce.

Answer 8

Sabes lo que podrías hacer ... Podrías escribir un algoritmo genético para determinar esa distribución óptima.

Pero, por lo general, mantengo los cruces superiores del 12% y del 28%; con 30% cada uno para los demás.