Algoritmo MCS

Para la optimización matemática , la búsqueda de coordenadas multinivel ( MCS ) es un algoritmo eficiente ^{[ 1 ]} para la optimización global con restricciones de límites utilizando solo valores de función . ^{[ 2 ]}

Para ello, el espacio de búsqueda n-dimensional se representa mediante un conjunto de hipercubos (cajas) que no se intersecan. Estas cajas se dividen iterativamente a lo largo de un plano axial según el valor de la función en un punto representativo de la caja (y sus vecinas) y su tamaño. Estos dos criterios de división se combinan para formar una búsqueda global, dividiendo las cajas grandes, y una búsqueda local, dividiendo las áreas donde el valor de la función es adecuado.

Además, se puede utilizar una búsqueda local que combine una interpolación cuadrática (multidimensional) de la función y búsquedas lineales para mejorar el rendimiento del algoritmo ( MCS con búsqueda local ); en este caso, se utiliza el MCS simple para proporcionar los puntos de partida (iniciales). La información proporcionada por las búsquedas locales (mínimos locales de la función objetivo) se retroalimenta al optimizador y afecta a los criterios de división, lo que resulta en una menor agrupación de muestras alrededor de los mínimos locales, una convergencia más rápida y una mayor precisión.

El flujo de trabajo de MCS se visualiza en las figuras 1 y 2. Cada paso del algoritmo se puede dividir en cuatro etapas:

1. Identificar un candidato potencial para dividir (magenta, grueso).
2. Identifique la dirección de división óptima y la posición óptima esperada del punto de división (verde).
3. Evalúe la función objetivo en el punto de división o recupérela del conjunto ya calculado; esto último se aplica si ya se ha alcanzado el punto de división actual al dividir una caja vecina.
4. Generar nuevos recuadros (magenta, delgados) en función de los valores de la función objetivo en el punto de división.

En cada paso, el punto verde con el halo amarillo temporal es el punto base único de la caja; cada caja tiene un valor asociado del objetivo, es decir, su valor en el punto base de la caja.

Para determinar si una caja se dividirá, se utilizan dos criterios de división distintos. El primero, la división por rango , garantiza que las cajas grandes que no se han dividido con frecuencia se dividirán eventualmente. Si se aplica, el punto de división se determina fácilmente en una fracción fija de la longitud del lado que se divide. El segundo, la división por ganancia esperada , emplea un modelo cuadrático parabólico unidimensional local (sustituto) a lo largo de una única coordenada. En este caso, el punto de división se define como el mínimo del sustituto a lo largo de un segmento de línea y la caja se divide solo si el valor interpolante (que sirve como aproximación del valor real del objetivo) es menor que el mejor valor de la función muestreada actualmente.

Se garantiza que el algoritmo convergerá al mínimo global a largo plazo (es decir, cuando el número de evaluaciones de la función y la profundidad de búsqueda sean arbitrariamente grandes) si la función objetivo es continua en la vecindad del minimizador global. Esto se debe a que cualquier caja acabará siendo arbitrariamente pequeña, por lo que el espaciado entre muestras tiende a cero a medida que el número de evaluaciones de la función tiende a infinito.

MCS está diseñado para implementarse de forma recursiva y eficiente con la ayuda de árboles . Con este enfoque, la cantidad de memoria requerida es independiente de la dimensionalidad del problema, ya que los puntos de muestreo no se almacenan explícitamente. En cambio, solo se guarda una coordenada de cada muestra y las coordenadas restantes se pueden recuperar rastreando el historial de una caja hasta la raíz (caja inicial). Este método fue sugerido por los autores y utilizado en su implementación original. ^{[ 2 ]}

• Página principal del algoritmo
• Rendimiento del algoritmo en relación con otros