La optimización se refiere a encontrar el conjunto de entradas a una función objetivo que da como resultado la salida máxima o mínima de la función objetivo.
Es común describir los problemas de optimización en términos de optimización local frente a global.
De manera similar, también es común describir algoritmos de optimización o algoritmos de búsqueda en términos de búsqueda local frente a búsqueda global.
En este tutorial, descubrirá las diferencias prácticas entre la optimización local y global.
Después de completar este tutorial, sabrá:
- La optimización local implica encontrar la solución óptima para una región específica del espacio de búsqueda, o el óptimo global para problemas sin óptimos locales.
- La optimización global implica encontrar la solución óptima a problemas que contienen óptimos locales.
- Cómo y cuándo usar algoritmos de búsqueda locales y globales y cómo usar ambos métodos en conjunto.
Empecemos.
Optimización local versus optimización global
Foto de Marco Verch, algunos derechos reservados.
Descripción general del tutorial
Este tutorial se divide en tres partes; son:
- Optimización local
- Optimización global
- Optimización local frente a global
Optimización local
Un óptimo local es el extremo (mínimo o máximo) de la función objetivo para una región determinada del espacio de entrada, p. Ej. una cuenca en un problema de minimización.
… buscamos un punto que sea solo localmente óptimo, lo que significa que minimiza la función objetivo entre los puntos factibles que están cerca de él …
– Página 9, Optimización convexa, 2004.
Una función objetivo puede tener muchos óptimos locales, o puede tener un único óptimo local, en cuyo caso el óptimo local es también el óptimo global.
- Optimización local: Ubique los óptimos para una función objetiva desde un punto de partida que se cree que contiene los óptimos (por ejemplo, una cuenca).
La optimización local o la búsqueda local se refiere a la búsqueda de óptimos locales.
Un algoritmo de optimización local, también llamado algoritmo de búsqueda local, es un algoritmo destinado a localizar un óptimo local. Es adecuado para atravesar una región determinada del espacio de búsqueda y acercarse (o encontrar exactamente) los extremos de la función en esa región.
… Los métodos de optimización local se utilizan ampliamente en aplicaciones donde es valioso encontrar un buen punto, si no el mejor.
– Página 9, Optimización convexa, 2004.
Los algoritmos de búsqueda local normalmente operan en una única solución candidata e implican realizar de forma iterativa pequeños cambios en la solución candidata y evaluar el cambio para ver si conduce a una mejora y se toma como la nueva solución candidata.
Un algoritmo de optimización local localizará el óptimo global:
- Si el optima local es el optima global, o
- Si la región que se busca contiene el optima global.
Estos definen los casos de uso ideales para utilizar un algoritmo de búsqueda local.
Puede haber un debate sobre qué constituye exactamente un algoritmo de búsqueda local; sin embargo, tres ejemplos de algoritmos de búsqueda local que utilizan nuestras definiciones incluyen:
- Algoritmo de Nelder-Mead
- Algoritmo BFGS
- Algoritmo de escalada
Ahora que estamos familiarizados con la optimización local, echemos un vistazo a la optimización global.
Optimización global
Un óptimo global es el extremo (mínimo o máximo) de la función objetivo para todo el espacio de búsqueda de entrada.
Optimización global, donde el algoritmo busca el óptimo global mediante el empleo de mecanismos para buscar partes más grandes del espacio de búsqueda.
– Página 37, Inteligencia computacional: Introducción, 2007.
Una función objetivo puede tener uno o más de un óptimo global, y si hay más de uno, se denomina problema de optimización multimodal y cada óptimo tendrá una entrada diferente y la misma evaluación de la función objetivo.
- Optimización global: Busque los óptimos para una función objetiva que pueda contener óptimos locales.
Una función objetiva siempre tiene un óptimo global (de lo contrario no nos interesaría optimizarlo), aunque también puede tener óptimos locales que tengan una evaluación de la función objetiva que no sea tan buena como el optima global.
El óptimo global puede ser el mismo que el óptimo local, en cuyo caso sería más apropiado referirse al problema de optimización como una optimización local, en lugar de una optimización global.
La presencia de óptimos locales es un componente principal de lo que define la dificultad de un problema de optimización global, ya que puede ser relativamente fácil localizar un óptimo local y relativamente difícil localizar los óptimos globales.
La optimización global o búsqueda global se refiere a la búsqueda de óptimos globales.
Un algoritmo de optimización global, también llamado algoritmo de búsqueda global, está destinado a localizar un óptimo global. Es adecuado para recorrer todo el espacio de búsqueda de entrada y acercarse (o encontrar exactamente) los extremos de la función.
La optimización global se utiliza para problemas con una pequeña cantidad de variables, donde el tiempo de cálculo no es crítico y el valor de encontrar la verdadera solución global es muy alto.
– Página 9, Optimización convexa, 2004.
Los algoritmos de búsqueda global pueden implicar la gestión de una sola o una población de soluciones candidatas a partir de las cuales se generan y evalúan de forma iterativa nuevas soluciones candidatas para ver si dan como resultado una mejora y se toman como el nuevo estado de trabajo.
Puede haber un debate sobre qué constituye exactamente un algoritmo de búsqueda global; sin embargo, tres ejemplos de algoritmos de búsqueda global que utilizan nuestras definiciones incluyen:
- Algoritmo genético
- Recocido simulado
- Optimización de Enjambre de partículas
Ahora que estamos familiarizados con la optimización global y local, comparemos y contrastamos las dos.
Optimización local frente a global
Los algoritmos de optimización de búsqueda local y global resuelven diferentes problemas o responden diferentes preguntas.
Se debe utilizar un algoritmo de optimización local cuando sepa que se encuentra en la región de los óptimos globales o que su función objetivo contiene un único óptimo, p. Ej. unimodal.
Se debe utilizar un algoritmo de optimización global cuando se sabe muy poco sobre la estructura de la superficie de respuesta de la función objetivo, o cuando se sabe que la función contiene óptimos locales.
Optimización local, donde el algoritmo puede atascarse en un óptimo local sin encontrar un óptimo global.
– Página 37, Inteligencia computacional: Introducción, 2007.
La aplicación de un algoritmo de búsqueda local a un problema que requiere un algoritmo de búsqueda global arrojará resultados deficientes, ya que la búsqueda local será atrapada (engañada) por los óptimos locales.
- Busqueda local: Cuando estás en la región de los óptimos globales.
- Búsqueda global: Cuando se sabe que existen óptimos locales.
Los algoritmos de búsqueda local a menudo otorgan a los beneficiarios de la complejidad computacional relacionados con la localización de los óptimos globales, siempre que se mantengan las suposiciones hechas por el algoritmo.
Los algoritmos de búsqueda global a menudo dan muy pocos o ningún beneficiario sobre la localización de los óptimos globales. Como tal, la búsqueda global se utiliza a menudo en problemas que son lo suficientemente difíciles como para «bueno«O»suficientemente bueno”Se prefieren las soluciones a ninguna solución. Esto podría significar óptimos locales relativamente buenos en lugar de óptimos globales verdaderos si localizar el óptimo global es intratable.
A menudo es apropiado volver a ejecutar o reiniciar el algoritmo varias veces y registrar los óptimos encontrados en cada ejecución para tener cierta confianza en que se han localizado soluciones relativamente buenas.
- Busqueda local: Para problemas estrechos donde se requiere una solución global.
- Búsqueda global: Para problemas amplios donde los óptimos globales pueden ser intratables.
A menudo sabemos muy poco sobre la superficie de respuesta para una función objetivo, p. Ej. si un algoritmo de búsqueda local o global es el más apropiado. Por lo tanto, puede ser deseable establecer una línea de base en el rendimiento con un algoritmo de búsqueda local y luego explorar un algoritmo de búsqueda global para ver si puede funcionar mejor. Si no puede, puede sugerir que el problema es unimodal o apropiado para un algoritmo de búsqueda local.
- Mejores prácticas: Establezca una línea de base con una búsqueda local y luego explore una búsqueda global de funciones objetivas donde se sabe poco.
La optimización local es un problema más simple de resolver que la optimización global. Como tal, la gran mayoría de la investigación sobre optimización matemática se ha centrado en técnicas de búsqueda local.
Una gran parte de la investigación sobre programación general no lineal se ha centrado en métodos de optimización local, que como consecuencia están bien desarrollados.
– Página 9, Optimización convexa, 2004.
Los algoritmos de búsqueda global son a menudo toscos en su navegación por el espacio de búsqueda.
Muchos métodos de población funcionan bien en la búsqueda global, pudiendo evitar los mínimos locales y encontrando las mejores regiones del espacio de diseño. Desafortunadamente, estos métodos no funcionan tan bien en la búsqueda local en comparación con los métodos de descenso.
– Página 162, Algoritmos de optimización, 2019.
Como tal, pueden ubicar la cuenca para un buen óptimo local o global, pero es posible que no puedan ubicar la mejor solución dentro de la cuenca.
Las técnicas de optimización locales y globales se pueden combinar para formar algoritmos de entrenamiento híbridos.
– Página 37, Inteligencia computacional: Introducción, 2007.
Por lo tanto, es una buena práctica aplicar una búsqueda local a las soluciones candidatas óptimas encontradas por un algoritmo de búsqueda global.
- Mejores prácticas: Aplicar una búsqueda local a las soluciones encontradas por una búsqueda global.
Otras lecturas
Esta sección proporciona más recursos sobre el tema si está buscando profundizar.
Libros
Artículos
Resumen
En este tutorial, descubrió las diferencias prácticas entre la optimización local y global.
Específicamente, aprendiste:
- La optimización local implica encontrar la solución óptima para una región específica del espacio de búsqueda, o el óptimo global para problemas sin óptimos locales.
- La optimización global implica encontrar la solución óptima a problemas que contienen óptimos locales.
- Cómo y cuándo usar algoritmos de búsqueda locales y globales y cómo usar ambos métodos en conjunto.
¿Tiene usted alguna pregunta?
Haga sus preguntas en los comentarios a continuación y haré todo lo posible para responder.