Optimización de múltiples parámetros con muchos mínimos locales

Question

Estoy buscando algoritmos para encontrar un "mejor" conjunto de valores de parámetros. La función en cuestión tiene muchos mínimos locales y cambia muy rápidamente. Para empeorar las cosas, probar un conjunto de parámetros es muy lento, del orden de 1 minuto, y no puedo calcular el degradado directamente.

¿Existen algoritmos bien conocidos para este tipo de optimización?

He tenido un éxito moderado con solo intentar valores aleatorios. Me pregunto si puedo mejorar el rendimiento haciendo que el selector de parámetros aleatorios tenga menos posibilidades de elegir parámetros cercanos a los que dieron malos resultados en el pasado. ¿Hay algún nombre para este enfoque para poder buscar consejos específicos?

Más información:

• parámetros son continuas
• Hay del orden de 5-10 parámetros. Ciertamente no más de 10.

Answer 1

he tratado recocido simulado y Optimización enjambre de partículas. (Como recordatorio, no pude usar el descenso de gradiente porque el gradiente no se puede calcular).

También he probado un algoritmo que realiza lo siguiente:

• escoger un punto al azar y una dirección aleatoria
• evaluar la función
• Manténgase en movimiento a lo largo de la dirección al azar durante el tiempo que el el resultado sigue mejorando, acelerando en cada iteración exitosa.
• Cuando el resultado deja de mejorar, retroceda y en su lugar intente moverse en una dirección ortogonal por la misma distancia.

Esta "dirección ortogonal" se generó mediante la creación de una matriz azar ortogonal (adaptado this code) con el número necesario de dimensiones.

Si el movimiento en la dirección ortogonal mejora el resultado, el algoritmo simplemente continúa en esa dirección. Si ninguna de las instrucciones mejora el resultado, la distancia de salto se reduce a la mitad y se intentará un nuevo conjunto de direcciones ortogonales. Eventualmente, el algoritmo concluyó que debe estar en un mínimo local, lo recordó y reinició todo en un nuevo punto aleatorio.

Este enfoque tuvo un rendimiento considerablemente mejor que el recocido simulado y el enjambre de partículas: requirió menos evaluaciones de la función (muy lenta) para lograr un resultado de la misma calidad.

Por supuesto mis implementaciones de S.A. y P.S.O. bien podría tener fallas: estos son algoritmos difíciles con mucho margen para ajustar los parámetros. Pero pensé en mencionar lo que terminó mejor para mí.

Answer 2

Realmente no puedo ayudarlo a encontrar un algoritmo para su problema específico.

Sin embargo, en cuanto a la elección aleatoria de los parámetros, creo que lo que estás buscando es genetic algorithms. Los algoritmos genéticos generalmente se basan en elegir alguna entrada aleatoria, seleccionar aquellos que son los que mejor se ajustan (hasta ahora) para el problema, y ​​mutarlos aleatoriamente/combinarlos para generar una próxima generación para la cual nuevamente se seleccionan los mejores.

Si la función es más o menos continua (es decir, pequeñas mutaciones de buenas entradas generalmente no generarán entradas malas (pequeñas siendo algo genéricas)), esto funcionaría razonablemente bien para su problema.

Answer 3

¿Cuántos parámetros hay, por ejemplo, cuántas dimensiones hay en el espacio de búsqueda? ¿Son continuos o discretos, por ejemplo, números reales o enteros, o solo unos pocos valores posibles?

Los enfoques que he visto para este tipo de problemas tienen una estructura general similar: tome una gran cantidad de puntos de muestra y ajústelos a las regiones que tienen "buenas" respuestas de alguna manera. Como tienes muchos puntos, sus diferencias relativas sirven de gradiente improvisado.

• Simulated Annealing: El enfoque clásico. Tome un montón de puntos, de manera probabilística mueva algunos a un punto vecino elegido al azar dependiendo de cuánto mejor sea.
• Particle Swarm Optimization: Tome un "enjambre" de partículas con velocidades en el espacio de búsqueda, de forma probabilística mueva aleatoriamente una partícula; si es una mejora, avísele a todo el enjambre.
• Genetic Algorithms: Esto es un poco diferente. En lugar de utilizar la información de los vecinos como la anterior, se obtienen los mejores resultados cada vez y se "cruzan" con la esperanza de obtener las mejores características de cada uno.

Los enlaces de wikipedia tienen un pseudocódigo para los dos primeros; Los métodos de GA tienen tanta variedad que es difícil enumerar solo un algoritmo, pero puede seguir los enlaces desde allí. Tenga en cuenta que hay implementaciones para todo lo anterior que puede usar o tomar como punto de partida.

Tenga en cuenta que todos estos, y en realidad cualquier enfoque de este algoritmo de búsqueda de grandes dimensiones, son heurísticos, lo que significa que tienen parámetros que deben ajustarse a su problema particular. Lo cual puede ser tedioso

Por cierto, el hecho de que la evaluación de la función sea tan costosa puede funcionar un poco para usted; dado que todos los métodos anteriores implican muchas evaluaciones independientes de funciones, esa parte del algoritmo se puede paralelizar trivialmente con OpenMP o algo similar para hacer uso de tantos núcleos como los que tiene en su máquina.

Answer 4

Su situación parece ser similar a la del cartel de Software to Tune/Calibrate Properties for Heuristic Algorithms, y yo le daría el mismo consejo I gave there: considerar un Metropolis-Hastings como enfoque con múltiples caminantes y un recocido simulado de los tamaños de paso.

La dificultad de utilizar los métodos de Monte Carlo en su caso es la evaluación costosa de cada candidato. ¿Cuánto cuesta en comparación con el tiempo que tiene a mano? Si necesita una buena respuesta en pocos minutos, esto no será lo suficientemente rápido. Si puede dejarlo funcionando durante la noche, funcionará razonablemente bien.

Dado un espacio de búsqueda complicado, recomendaría una distribución inicial aleatoria. La respuesta final puede ser simplemente el mejor resultado individual registrado durante toda la carrera, o la posición media del andador con el mejor resultado.

No se deje intimidar por el hecho de que estuve discutiendo la maximización allí y desee minimizar: la cifra de mérito puede ser negada o invertida.

Answer 5

No hay una forma generalizada de responder a su pregunta. Hay muchos libros/trabajos sobre el tema, pero tendrás que elegir tu camino de acuerdo a tus necesidades, que no se hablan claramente aquí.

Sin embargo, algunas cosas que debe saber: 1 minuto/prueba es demasiado para cualquier algoritmo. Supongo que, en su caso, que realmente debe hacer uno de los siguientes:

• obtener 100 computadoras para reducir el tiempo de prueba de parámetros de un tiempo razonable
• realmente tratar de llegar a los parámetros de la mano y la mente. Debe haber alguna redundancia y al menos alguna verificación de cordura para que pueda probar su caso en < 1min
• para posibles conjuntos de resultados, intente descubrir algunas 'operaciones' que lo modifiquen ligeramente en lugar de simplemente aleatorizarlo. Por ejemplo, en TSP, un operador básico es lambda, que intercambia dos nodos y crea así una nueva ruta. Tu puedes estar moviendo algunos números arriba/abajo por algún valor.
• entonces, encuentre algún buen algoritmo, su punto de partida puede estar en algún lugar here. El libro es un recurso invaluable para cualquiera que comience con la resolución de problemas.