La búsqueda de coordenadas multinivel ( MCS ) es un algoritmo eficiente para la optimización global restringida por límite que utiliza únicamente valores de función .
Para hacerlo, el espacio de búsqueda n-dimensional está representado por un conjunto de hipercubos (cajas) que no se cruzan. Luego, las cajas se dividen iterativamente a lo largo de un plano de eje de acuerdo con el valor de la función en un punto representativo de la caja (y sus vecinos) y el tamaño de la caja. Estos dos criterios de división se combinan para formar una búsqueda global dividiendo cuadros grandes y una búsqueda local dividiendo áreas para las que el valor de la función es bueno.
Además, se puede utilizar una búsqueda local que combine un interpolador cuadrático (multidimensional) de la función y búsquedas de línea para aumentar el rendimiento del algoritmo ( MCS con búsqueda local ); en este caso, el MCS simple se utiliza para proporcionar los puntos de partida (iniciales). La información proporcionada por las búsquedas locales (es decir, los mínimos locales de la función objetivo) se retroalimenta al optimizador e influye en los criterios de división, lo que da como resultado un agrupamiento de muestras reducido alrededor de los mínimos locales y una convergencia más rápida.
Flujo de trabajo simplificado
El flujo de trabajo básico se presenta en la figura 1. Generalmente, cada paso se puede caracterizar por tres etapas:
- Identifique un candidato potencial para la división (magenta, grueso).
- Identifique la dirección de división óptima y la posición óptima esperada de los puntos de división (verde).
- Evalúe la función objetivo en puntos de división no considerados previamente. Genere nuevos cuadros (magenta, delgados) basados en los valores de la función objetivo en los puntos de división (verdes).
En cada paso, al menos un punto de división (amarillo) es una muestra de función conocida (rojo), por lo que el objetivo nunca se evalúa allí nuevamente.
Para determinar si una caja se dividirá, se utilizan dos criterios de división separados. El primero, dividido por rango , asegura que las cajas grandes que no se han dividido con demasiada frecuencia se dividirán eventualmente. Si se aplica, el punto de división se puede determinar a priori. El segundo, dividido por la ganancia esperada , emplea un modelo cuadrático unidimensional local (sustituto) a lo largo de una sola coordenada. En este caso, el punto de división se define como el mínimo del sustituto y la caja se divide solo si el valor interpolante allí es menor que el valor de la función de mejor muestra actual.
Convergencia
Se garantiza que el algoritmo convergerá al mínimo global a largo plazo (es decir, cuando el número de evaluaciones de funciones y la profundidad de búsqueda son arbitrariamente grandes) si la función objetivo es continua en la vecindad del minimizador global. Esto se deriva del hecho de que cualquier caja se volverá arbitrariamente pequeña eventualmente, por lo tanto, el espacio entre muestras tiende a cero cuando el número de evaluaciones de funciones tiende a infinito.
Implementación recursiva
MCS fue diseñado para ser implementado de manera eficiente y recursiva 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 su lugar, solo se guarda una única 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.
Cuando se implementa con cuidado, esto también permite evitar evaluaciones repetidas de funciones. Más precisamente, si un punto de muestreo se coloca a lo largo del límite de dos casillas adyacentes, esta información a menudo se puede extraer rastreando el historial del punto para una pequeña cantidad de pasos. En consecuencia, se pueden generar nuevas subcajas sin evaluar la función objetivo (potencialmente cara). Este escenario se visualiza en la figura 1 siempre que un punto verde (pero no amarillo) y rojo coincidan, por ejemplo, cuando el cuadro con esquinas alrededor y se divide.