¿Cuándo son los algoritmos genéticos una buena opción para la optimización?

Los algoritmos genéticos son una forma de método de optimización. A menudo, el descenso de gradiente estocástico y sus derivados son la mejor opción para la optimización de la función, pero a veces todavía se utilizan algoritmos genéticos. Por ejemplo, la antena de la nave espacial ST5 de la NASA se creó con un algoritmo genético:

¿Cuándo son los métodos de optimización genética una mejor opción que los métodos de descenso de gradiente más comunes?

Los algoritmos genéticos (GA) son una familia de heurísticas que son empíricamente buenos para proporcionar una respuesta decente en muchos casos, aunque rara vez son la mejor opción para un dominio dado.

Usted menciona algoritmos basados ​​en derivados, pero incluso en ausencia de derivados, hay muchos algoritmos de optimización sin derivados que funcionan mucho mejor que los GA. Vea esto y esta respuesta para algunas ideas.

Lo que muchos algoritmos de optimización estándar tienen en común (incluso métodos libres de derivadas) es la suposición de que el espacio subyacente es una variedad uniforme (quizás con algunas dimensiones discretas), y la función para optimizar es algo bien comportada.

Sin embargo, no todas las funciones están definidas en un múltiple liso. A veces desea optimizar sobre un gráfico u otras estructuras discretas (optimización combinatoria): aquí hay algoritmos dedicados, pero los GA también funcionarían.

Cuanto más se acerque a las funciones definidas sobre estructuras complejas y discretas, más GA pueden ser útiles, especialmente si puede encontrar una representación en la que los operadores genéticos trabajen de la mejor manera (lo que requiere mucho conocimiento manual y dominio del dominio).

Por supuesto, el futuro podría llevar a olvidar los GA por completo y desarrollar métodos para mapear espacios discretos en espacios continuos , y utilizar la maquinaria de optimización que tenemos en la representación continua.

Los métodos genéticos son muy adecuados para la optimización multicriterio cuando el descenso de gradiente se dedica a la optimización de monocriterios. El descenso de gradiente permite encontrar un mínimo de funciones cuando existen derivadas y solo hay una solución óptima (si exceptuamos las minimas locales). Un algoritmo genético puede usarse en problemas de múltiples criterios y conducir a un continuo de soluciones, cada una de las cuales es un individuo de una población, que ha evolucionado desde una población inicial. Los valores a optimizar son los fenotipos de los individuos y puede haber varios fenotipos. En general, ninguno de los individuos tiene simultáneamente el mejor valor de cada fenotipo, por lo que no hay una sola solución. Los individuos en la población final, que son todas las soluciones de la optimización, son parte del "frente de Pareto" y están marcados como "Rango uno de Pareto" individuos. Esto significa que, en comparación con todos los demás individuos que tienen el mismo rendimiento para cada fenotipo, son al menos mejores para un fenotipo que los otros.

¿Mejor en qué sentido?

En mi experiencia, los GA son uno de los optimizadores más pragmáticos. Si bien muchos algoritmos más precisos requieren tiempo y esfuerzo para formalizar problemas reales en el mundo matemático, los GA pueden manejar cualquier función de costo con reglas y restricciones complejas (los GA están relacionados por un enfoque de ejecución después de todo y no por un cálculo específico). Este proceso es sencillo y puede probar muchos enfoques para el trabajo exploratorio.

También aprecio la posibilidad de reinyectar soluciones pasadas al algoritmo para futuras ejecuciones, lo cual es bueno para tareas repetidas.

Conceptualmente, un algoritmo genético se puede representar mediante un hashmap de funciones y se adapta a lenguajes funcionales como Clojure, que también es un lenguaje en el que puede lograr grandes resultados muy rápidamente.

Los algoritmos genéticos también se pueden anidar: ¡la función de costo de un GA puede ser un GA! Estos algoritmos aprovechan el hardware y la infraestructura modernos que les permiten calcular una población muy grande para que, incluso con simples operaciones de mutación / selección, aún puedan lograr buenos resultados.

Incluso para problemas simples como encontrar el mínimo de una función de onda, los GA no son tan malos y pueden lograr una precisión decente en un tiempo aceptable.

Entonces, sí, las soluciones analíticas pueden tener un tiempo de ejecución y precisión más rápidos, ¡pero el tiempo requerido para producir sobrepeso a menudo espera beneficios! Así que cuando ? Casi siempre para mí, al menos para la metaoptimización.