¿Cómo encontrar los mejores parámetros para un algoritmo genético?

Question

Algunos marcos Algoritmo Genético, como http://www.aforgenet.com/ requiere muchos parámetros, tales como la tasa de mutación, tamaño de la población, etc.

Hay mejores números universales para estos parámetros? Creo que depende del problema (retraso de la función de acondicionamiento físico, retraso de la mutación, retraso de recombinación, índice de evolución, etc.). Mi primer pensamiento fue usar un GA para configurar otro GA.

¿Alguna idea mejor?

Answer 1

La única vez que programé un algoritmo genético, incluí esos valores en los valores para mutar, básicamente como dijiste usando un GA para configurarse. Funcionó sorprendentemente bien, especialmente porque considero que es beneficioso para esos valores cambiar en el transcurso de su cálculo.

Answer 2

Realmente no hay una manera automática de hacerlo para un conjunto de datos determinado. Si lo hubiera, no expondrían esos parámetros. Usar un segundo GA para sintonizar los parámetros del primer GA es peligroso. ¿Utiliza un tercer GA para sintonizar los parámetros del segundo? Incluso si lo hicieras, es una receta para el sobreajuste de todos modos.

Mi consejo sería jugar con los parámetros, y ver cómo afectan la distribución de su población en cada generación, cuántas generaciones se necesitan para llegar a una respuesta aceptable, etc. Si tiene demasiada mutación, su población nunca estabilizar. Demasiado poco y terminarás con homogeneidad.

Es un sucio secreto de GA que afinarlos es un arte, no una ciencia.

Answer 3

Encuentro que es útil pensar en estos problemas como un paisaje, donde se trata de encontrar el punto más bajo.

Los métodos como los algoritmos genéticos se utilizan cuando el paisaje es demasiado grande para probar todos los puntos, y la "forma" del paisaje es tal que métodos como el descenso en pendiente te atascarán en los mínimos locales.

Un buen ejemplo es la función de Rastrigin (image ref): :

Las opciones son:

tamaño Generación:

• demasiado grande: vas a tener un larga tiempo de época, restringiendo cuántas oportunidades de cada individuo tiene para explorar su vecindario .
• Demasiado pequeño: no obtiene una buena cobertura del espacio de búsqueda.

tasa de mutación:

• demasiado alto: corre el riesgo de los individuos "saltar" sobre una solución que estaban cerca de .
• Demasiado bajo: todos van a quedar atrapados en mínimos locales.

Por lo tanto, realmente depende de su espacio de búsqueda particular. Experimenta con los parámetros y trata de encontrar la combinación óptima.Estoy de acuerdo en que usar otro GA para optimizar los parámetros no va a resolver el problema.

Answer 4

No es fácil.

¿Por qué? Debido al teorema No Free Lunch. Esto básicamente indica que no hay general algoritmo de búsqueda que funciona bien para todos los problemas.

Lo mejor que puedes hacer es personalizar la búsqueda de un espacio problemático específico. Tendrás que modificar manualmente tus parámetros para adaptarlos a tu solución. Lo siento.

El uso de un GA para encontrar parámetros GA se complica. ¿Cómo se encuentran los parámetros óptimos para su búsqueda GAGA? Otra GA ...?

Answer 5

Como todos los demás dijeron, no hay una sola respuesta. Aunque existe cierta tendencia a utilizar la tasa de cruce en el nivel 0.7-0.9 y la mutación en 0.1-0.3 realmente depende. Depende del problema, puede depender de la función de aptitud, y definitivamente depende del Algoritmo Genético en sí mismo. Hay muchas variaciones de GA, los parámetros óptimos para el mismo problema pueden variar.

En cuanto a usar GA para ajustar los parámetros del objetivo GA, hay enfoques como ese, pero, como se señaló, ¿cómo ajustar los parámetros del primer GA? Tenga en cuenta que, tal vez, la tasa de mutación debería ser mayor al principio, y que debería disminuir mientras que la tasa de cruce debería aumentar. Es un problema de exploración versus explotación. Existen enfoques para que GA sea más adaptable y le permita cambiar sus parámetros a medida que busca soluciones. Los controladores difusos a veces se utilizan para manipular los parámetros de GA. También hay otros enfoques.

Si desea obtener más información al respecto, compre algunos libros o consulte los documentos de investigación académica.
Si necesita configurar su propio GA sin una extensa investigación, pruebe algunos valores de otros y experimente con ellos.

Answer 6

Me resulta bastante decepcionante hay tantas respuestas que suponen que no puede encontrar los mejores parámetros para el algoritmo genético de forma automática. Acepto que los parámetros dependen del problema; sin embargo, existen métodos para encontrarlos.

Además, el No Free Lunch Theorem de ninguna manera hace que deje de encontrar los mejores parámetros, como ya ha habido discusión que discute el hecho de:

• Practically it does not hold
• Description length may dispute the theorem
• Coevolution can make the theorem irrelevant

Hay dos tipos de configuración de parámetros:

• afinamientos de parámetros (parámetro de búsqueda en línea - antes de que el GA se ejecuta)
• de control de parámetro (parámetro de ajustes en línea - durante la carrera GA)
  • adaptativa
  • Auto Adaptativo
  • determinista

Hay mucha literatura disponible allí que describen cómo uno puede encontrar estos parámetros óptimos, depende de si desea realizar la búsqueda de parámetros fuera de línea o en línea. La creencia popular es que fuera de línea es más adecuado para la mayoría de los casos porque los métodos de control de parámetros en línea agregarían demasiada complejidad a fuera de línea.

Éstos son algunos ejemplos para encontrar la "mejor" parámetros:

parámetro de ajuste:

• simple barrido de parámetros (probar todo)
• Meta-GA sábana de una GA
• Racing strategy para encontrar los mejores parámetros
• Meta-GA and Racing together

control de parámetros:

• Adaptive probabilities for mutation and crossover
• Self adaptive popuation size
• Deterministic Genetic Operators

y muchos más, sólo la búsqueda de la literatura utilizando palabras clave utilizadas anteriormente. ¡Existen métodos científicos para encontrar parámetros adecuados para cualquier problema en particular!