Estoy trabajando para mejorar el proceso de optimización de algunos programas de modelado demográfico para que pueda adaptar mejor los modelos demográficos a los datos. Nos gustaría disminuir el tiempo de optimización.
El tiempo que lleva evaluar nuestra función objetivo varía mucho, dependiendo de los valores de entrada. Se conoce la relación entre el tiempo para evaluar la función objetivo y la entrada. Me pregunto si hay algún método de optimización que considere el costo de tiempo relativo de la función objetivo al elegir qué puntos evaluar.
¡Gracias!
Actualizar:
Como Paul solicitó, aquí hay algunas características destacadas de esta función objetivo particular:
- El número de parámetros es moderado (~ 12ish)
- Nuestro problema es no convexo, o al menos hay "crestas" estrechas y planas en la superficie de la función objetivo. En este momento estamos lidiando con esto usando múltiples optimizaciones desde diferentes puntos, pero nos encantaría hacerlo mejor.
- La función objetivo es bastante suave, aunque solo podemos calcular aproximaciones de diferencias finitas a derivadas.
- El costo de evaluación también es una función fluida de los valores de los parámetros, y es bastante predecible. en términos generales, para cada parámetro, el costo de evaluar es alto en un extremo del rango y bajo en el otro extremo. Por lo tanto, tenemos grandes regiones de conjuntos de parámetros costosos de evaluar, pero sabemos dónde están.
optimization
estrella nueva
fuente
fuente
Respuestas:
Un enfoque común para tratar con funciones objetivas costosas es construir (por ejemplo, el modelo de regresión) un "modelo de superficie de respuesta" que se aproxime a la función objetivo original, y luego optimizar sobre esa superficie de respuesta en lugar de trabajar con la función original. En la práctica, las superficies de respuesta son típicamente modelos cuadráticos que se ajustan por regresión, por lo que encontrar un mínimo de la superficie de respuesta se convierte en un problema de optimización muy fácil.
No ha dicho nada sobre la suavidad o convexidad de su función objetivo. Si la función no es suave o no convexa, entonces esto obviamente se vuelve mucho, mucho más difícil.
Tampoco ha dicho nada sobre dónde están los puntos caros en su espacio de parámetros. Si se distribuyen aleatoriamente en todo el espacio de parámetros, puede utilizar técnicas de diseño de experimentos para construir su modelo de superficie de respuesta y evitar los costosos puntos. Si hay regiones más grandes del espacio de parámetros donde las evaluaciones son caras, entonces podría intentar minimizar el número de puntos en esas áreas que utiliza para construir el modelo de superficie de respuesta. Por supuesto, si su óptimo se encuentra en el medio de dicha región, estará condenado a evaluar funciones en la región cara.
fuente
No conozco métodos que evalúen específicamente los costos relativos de evaluar el objetivo en diferentes puntos de prueba, pero si puede predecir de manera relativamente confiable si un candidato será costoso de evaluar o no, entonces podría sugerirle que pruebe método directo . Los métodos directos se ajustan a la familia de los métodos sin derivados. No es necesariamente algo malo usarlos, incluso si sospecha que su problema es bastante fácil porque pueden proporcionar cierto nivel de flexibilidad que los métodos para una optimización sin problemas no pueden.
La idea es que los métodos directos definan una malla (dependiente de la iteración) sobre la iteración actual y un "paso" de malla (dependiente de la iteración). En base a este paso de malla, el método determina los puntos de prueba en la malla que son vecinos de la iteración actual (se encuentran en la malla y están a una distancia definida por el paso de malla). Luego procederá a evaluar el objetivo en los vecinos. Tan pronto como se encuentra un mejor candidato, se convierte en la nueva iteración actual. A su elección, también puede evaluar a todos los vecinos y elegir el mejor.
En su caso, podría ser una buena idea ordenar a los vecinos en función de su estimación del costo de evaluar el objetivo allí. Evalúelos en este orden y elija el primer éxito como la próxima iteración. Intuitivamente, estás favoreciendo a los candidatos baratos. En los métodos directos, tales ordenamientos se ajustan a la categoría de modelos sustitutos , un concepto que generaliza el de un modelo de superficie de respuesta mencionado por Brian.
Aquí hay una excelente implementación de un método directo (en C ++): http://www.gerad.ca/nomad/Project/Home.html
Si eso parece estar dando resultados prometedores, no dude en ponerse en contacto conmigo y puedo sugerir otras mejoras.
Creo que NOMAD también tiene características para la optimización global (como el inicio múltiple que está aplicando actualmente) basado en el concepto de búsqueda de vecindario variable .
fuente