Algoritmo BRST

El algoritmo de Boender-Rinnooy-Stougie-Timmer (BRST) es un algoritmo de optimización adecuado para encontrar el óptimo global de funciones de caja negra . En su artículo, Boender et al. ^{[ 1 ]} describen su método como un método estocástico que combina muestreo, agrupamiento y búsqueda local, y que finaliza con un rango de intervalos de confianza para el valor del mínimo global.

El algoritmo de Boender et al. ha sido modificado por Timmer. ^{[ 2 ]} Timmer consideró varios métodos de agrupamiento. Basándose en experimentos, se determinó que un método llamado "enlace simple multinivel" era el más preciso.

Los algoritmos de Csendes ^{[ 3 ]} son ​​implementaciones del algoritmo de [Boender et al. ] ^{[ 1 ]} y dieron origen al software de dominio público GLOBAL. Los algoritmos locales empleados son un algoritmo de búsqueda lineal con dirección aleatoria, también utilizado por Törn, y un algoritmo cuasi-Newton que no utiliza la derivada de la función. Los resultados muestran la dependencia del resultado con respecto al algoritmo local auxiliar utilizado.

Ampliar la clase de funciones para incluir funciones multimodales hace que el problema de optimización global sea irresoluble en general. Para que sea resoluble, además de la continuidad, debe conocerse alguna condición de suavidad sobre la función.

La existencia de varios mínimos locales y la irresolubilidad en general son características importantes de la optimización global. La irresolubilidad implica que no se puede garantizar una solución en un número finito de pasos. Existen dos maneras de abordar este problema. En primer lugar, se establecen condiciones a priori sobre f y A, lo que convierte el problema en uno resoluble o, al menos, permite afirmar con certeza que se ha encontrado una solución. Esto restringe la clase de funciones que se pueden considerar. El segundo enfoque, que permite considerar una clase más amplia de funciones objetivo, consiste en renunciar al requisito de resolubilidad y tratar únicamente de obtener una estimación del mínimo global. En este enfoque probabilístico, también sería deseable obtener resultados sobre la calidad de la estimación obtenida. Algunos problemas resolubles pueden pertenecer a esta clase, ya que el número de pasos necesarios para una solución garantizada podría ser prohibitivo.

Al relajar el requisito de resolubilidad, parece lógico exigir que la probabilidad de obtener una solución se aproxime a 1 si se permite que el procedimiento continúe indefinidamente. Un procedimiento de búsqueda global probabilístico obvio consiste en utilizar un algoritmo local que parta de varios puntos distribuidos por toda la región de optimización. Este procedimiento se denomina "Multistart". Multistart es, sin duda, uno de los primeros procedimientos globales utilizados. Incluso se ha empleado en la optimización local para aumentar la confianza en la solución obtenida. Una desventaja de Multistart es que, al utilizar muchos puntos de partida, el mismo mínimo acabará determinándose varias veces. Para mejorar la eficiencia de Multistart, esto debe evitarse.

Los métodos de agrupamiento se utilizan para evitar esta determinación repetida de mínimos locales. Esto se realiza en tres pasos que pueden utilizarse de forma iterativa. Los tres pasos son:

• (a) Puntos de muestra en la región de interés .
• (b) Transformar la muestra para obtener puntos agrupados alrededor de los mínimos locales.
• (c) Utilice una técnica de agrupamiento para reconocer estos grupos (es decir, vecindarios de los mínimos locales).

Si el procedimiento que emplea estos pasos resulta exitoso, iniciar una optimización local desde cada clúster determinaría los mínimos locales y, por lo tanto, también el mínimo global. La ventaja de este enfoque radica en que el trabajo ahorrado al calcular cada mínimo una sola vez puede emplearse en los cálculos de (a) y (b), lo que aumentará la probabilidad de encontrar el mínimo global.

Al ser un método de agrupamiento , su eficacia es mayor para problemas de baja dimensionalidad y se vuelve menos eficaz para problemas que tienen unos pocos cientos de variables.

• http://www.abo.fi/~atorn/Globopt.html Con el permiso del autor, el texto ha sido copiado textualmente.
• Janka compara varios algoritmos de optimización global, de los cuales BRST muestra un rendimiento superior.
• Janka presenta el número de evaluaciones de funciones realizadas en el conjunto de prueba de Dixon-Szegö. Junto con el algoritmo MCS , el BRST requiere el menor número de evaluaciones.