Maximización global de la función objetiva costosa

Estoy interesado en maximizar globalmente una función de muchos ( ) parámetros reales (resultado de una simulación compleja). Sin embargo, la función en cuestión es relativamente costosa de evaluar y requiere aproximadamente 2 días para cada conjunto de parámetros. Estoy comparando diferentes opciones y me preguntaba si alguien tenía sugerencias.$\approx 30$

Sé que hay un conjunto de métodos para este tipo de procesos que implican desarrollar funciones aproximadas y luego maximizarlas (por ejemplo, Jones et al. "Optimización global eficiente de funciones de caja negra costosas" ). Sin embargo, esto parece estar relativamente involucrado con el código.

Tengo la capacidad de ejecutar una gran cantidad de simulaciones en paralelo (50+). Esto parecía sugerir el uso de algoritmos genéticos para hacer esta optimización, ya que puedo crear una población de soluciones candidatas tan rápido como puedo hacer una.

Aquí están mis preguntas: 1) ¿Alguien tiene experiencias con implementaciones disponibles gratuitamente de este tipo de solucionadores / recomendaciones globales? 2) ¿Hay razones para preferir o evitar algoritmos genéticos aquí?

Este es un problema físico, y mis primeros experimentos han demostrado que la figura del mérito cambia con bastante suavidad a medida que cambio los parámetros.

ACTUALIZAR:

¡Gracias por la ayuda! Algunos detalles más: no necesito ninguna información más allá de la ubicación del máximo. La simulación es determinista, no Monte Carlo, por lo que la complicación no es gran cosa. No hay límites ni restricciones explícitos en los parámetros. Otra información que tengo (y no mencioné antes) es una idea del tamaño del máximo requerido. Si bien estoy buscando un máximo global, también estaría contento con cualquier cosa de esta escala o mayor, no sé si esto me ayudaría. Espero que si hago la detección de manera más sistemática (hipercubos latinos como lo sugiere Brian Borchers), esto aparecerá.

Los algoritmos genéticos son una elección muy pobre cuando la función objetivo es extremadamente costosa de evaluar: estos métodos requieren muchas evaluaciones de función en cada generación (con lo que el paralelismo puede ayudar) y muchas generaciones (que son inherentemente secuenciales). A los dos días por generación, esto sería muy lento.

No has mencionado de dónde vino este problema. ¿Está analizando estadísticamente una superficie de probabilidad (en cuyo caso querrá algo más que los parámetros óptimos y el valor objetivo) o simplemente está optimizando una función objetivo?

No ha mencionado si el cálculo de la función objetivo es preciso o inexacto. A menudo ocurre que cuando la función objetivo se calcula mediante la simulación de Monte Carlo, los valores son bastante ruidosos. Esto puede inducir a error a muchos algoritmos de optimización. Los métodos de superficie de respuesta ayudan con este problema al suavizar el ruido.

No ha mencionado ninguna restricción en los parámetros. ¿Están acotados? ¿Existen restricciones lineales o no lineales entre los parámetros?

Lo más probable es que la mayoría de sus 30 parámetros no sean realmente tan importantes para el problema. Sugeriría usar un enfoque de detección de diseño experimental para determinar primero cuáles de los 30 parámetros son realmente importantes en la optimización, y luego, después de establecer valores razonables para los parámetros sin importancia, optimice sobre los parámetros importantes. Métodos como Latin Hypercube Sampling pueden ser muy útiles para descartar los parámetros relativamente poco importantes. En esta etapa de detección, puede utilizar fácilmente cientos de procesadores.

Después de reducir el número de parámetros a un tamaño más razonable, usaría un método de superficie de respuesta para optimizar los parámetros restantes. Si la superficie de respuesta es realmente multimodal, y utiliza un modelo de superficie de respuesta demasiado simple (por lo general, las personas simplemente se ajustan a un modelo cuadrático), podría fácilmente confundirse y perderse el máximo global. ¡Ten cuidado! En esta etapa, puede volver a utilizar muchos procesadores mediante el uso de un diseño experimental que ofrece una muy buena cobertura del espacio de parámetros. Busque puntos de diseño en los que el modelo ajustado esté lejos de los valores calculados; esto es una indicación de que la superficie de respuesta no funciona bien en esa región. Puede que tenga que construir superficies de respuesta en regiones separadas del espacio de parámetros.

Como último paso, puede comenzar con los parámetros de la optimización de la superficie de respuesta e intentar mejorar los valores de los parámetros seleccionados ajustándolos uno por uno (descenso coordinado).

Secundaré la recomendación de DAKOTA como marco para este tipo de optimización. Si va a hacer esta optimización solo una vez, entonces podría ser más fácil organizar los cálculos a mano, pero si va a hacerlo repetidamente, entonces DAKOTA sería muy útil.

1. No tengo ninguna experiencia con este tipo de solucionadores; Algunos de mis compañeros de trabajo los han usado. DAKOTA parece ser el paquete de software recomendado para este tipo de tareas. Incluye una interfaz que permite al usuario enviar trabajos repetidamente a una cola de envío y usar la salida para estudios de parámetros, análisis de sensibilidad, etc. No estoy lo suficientemente familiarizado para saber si aprovechará o no la ejecución de muchas simulaciones. simultaneamente.

2. Suponiendo que sus parámetros son continuos, si la figura del mérito cambia suavemente a medida que cambian los parámetros, entonces un modelo sustituto debe hacer un trabajo razonable para ajustar la figura del mérito, y la información derivada sustituta debe ser útil para refinar la convergencia. Para 30 parámetros, los métodos de optimización deterministas sin derivación también deberían ser útiles; allí de nuevo, la suavidad debería ayudar. Por el contrario, los algoritmos genéticos no utilizarán información derivada en absoluto, y a menudo requieren el ajuste de parámetros como la tasa de mutación, la tasa de recombinación y los parámetros de selección para lograr un buen rendimiento. Como opción algorítmica, usaría algoritmos genéticos como alternativa, porque esperaría que una optimización sustituta bien diseñada o un método de optimización determinista sin derivadas tengan un mejor comportamiento de convergencia.

Eche un vistazo a TOMLAB, DAKOTA y OpenMDAO para la optimización de caja negra.

Edición n. ° 3: la optimización bayesiana es muy similar a EGO:

https://github.com/mwhoffman/pybo

https://github.com/hyperopt/hyperopt

licencias limitadas:

https://github.com/rmcantin/bayesopt

https://github.com/HIPS/Spearmint

Editar # 2:

El primer enfoque es construir un metamodelo / sustituto (usando kriging / GP) alrededor de una función costosa y usar esta información adicional para encontrar el punto óptimo global más rápido y con menos evaluaciones (EGO).

El segundo enfoque, como en MDAS, es hacer una búsqueda directa con algunas adaptaciones inteligentes en múltiples niveles.

Los enfoques heurísticos son de naturaleza genética / aleatoria y sin ninguna garantía.

Editar # 1:

TOMLAB es una herramienta basada en MATLAB que tiene la mejor velocidad / calidad de optimización según el documento de Sahinidis. Pero esta es una herramienta comercial con un uso corporativo significativo. No estoy usando esto.

DAKOTA está más adaptado para la cuantificación de incertidumbre, además de la optimización general. Basado en c ++ y algunos códigos Fortran heredados. Aunque bajo licencia LGPL y binarios disponibles para descargar, es muy difícil recompilar al menos desde mi experiencia en Win7 con GCC o MSVS / ifort. Tiene dependencias en boost, lapack, cmake for build. Básicamente, este es un contenedor para numerosos solucionadores de código abierto y pocos comerciales. Este es un producto SNL y está estrechamente integrado con otros proyectos de Sandia NL. Pude integrar con éxito esta en lugar de algunas rutinas IMSL. El periódico de Sahinidis perdió el paralelismo masivo posible con DAKOTA.

OpenMDAO es un software de diseño basado en la optimización desarrollado en Python por la NASA bajo licencia APACHE. Estoy probando esto actualmente.

Si no puede permitirse el lujo de 30 ejecuciones, cada una variando un parámetro, varíelas en grupos:
por ejemplo, 8 ejecute cada una variando 4 parámetros juntos, luego refine las mejores 2 ejecuciones / 8 parámetros ...
(No tengo idea de cómo intercambiar ganancia de información versus tiempo de ejecución total; ¿ bandido multi-armado ?)

Aquí hay un código que permite optimizar eficientemente las costosas funciones de caja negra utilizando CPU multinúcleo.

Aquí se da una descripción de las matemáticas detrás del código .