Una suave introducción a los algoritmos de optimización estocástica

Optimización estocástica se refiere al uso de la aleatoriedad en la función objetivo o en el algoritmo de optimización.

Los algoritmos de optimización desafiantes, como los problemas de objetivos no lineales de alta dimensión, pueden contener múltiples óptimos locales en los que los algoritmos de optimización deterministas pueden atascarse.

Los algoritmos de optimización estocástica proporcionan un enfoque alternativo que permite tomar decisiones locales menos óptimas dentro del procedimiento de búsqueda que pueden aumentar la probabilidad de que el procedimiento localice los óptimos globales de la función objetivo.

En este tutorial, descubrirá una suave introducción a la optimización estocástica.


Recomendado: ¿Qué es el Big data?.


Después de completar este tutorial, sabrá:

  • Los algoritmos de optimización estocástica utilizan la aleatoriedad como parte del procedimiento de búsqueda.
  • Ejemplos de algoritmos de optimización estocástica como recocido simulado y algoritmos genéticos.
  • Consideraciones prácticas al utilizar algoritmos de optimización estocástica, como evaluaciones repetidas.

Empecemos.

Una suave introducción a los algoritmos de optimización estocástica

Una suave introducción a los algoritmos de optimización estocástica
Foto de John, algunos derechos reservados.

Descripción general del tutorial

Este tutorial se divide en tres partes; son:

  1. ¿Qué es la optimización estocástica?
  2. Algoritmos de optimización estocástica
  3. Consideraciones prácticas para la optimización estocástica

¿Qué es la optimización estocástica?

La optimización se refiere a algoritmos de optimización que buscan las entradas a una función que dan como resultado el mínimo o máximo de una función objetivo.

La optimización estocástica o búsqueda estocástica se refiere a una tarea de optimización que involucra aleatoriedad de alguna manera, ya sea de la función objetivo o en el algoritmo de optimización.

La búsqueda y optimización estocásticas se refiere a problemas en los que hay ruido de aleatoriedad en las mediciones proporcionadas al algoritmo y / o hay aleatoriedad inyectada (Monte Carlo) en el algoritmo mismo.

– Página xiii, Introducción a la búsqueda y optimización estocásticas, 2003.

La aleatoriedad en la función objetivo significa que la evaluación de soluciones candidatas implica cierta incertidumbre o ruido y se deben elegir algoritmos que puedan avanzar en la búsqueda en presencia de este ruido.

La aleatoriedad en el algoritmo se utiliza como estrategia, p. Ej. decisiones estocásticas o probabilísticas. Se utiliza como una alternativa a las decisiones deterministas en un esfuerzo por mejorar la probabilidad de ubicar el óptimo global o un óptimo local mejor.

Los métodos de optimización estocástica estándar son frágiles, sensibles a la elección del tamaño de paso y otros parámetros algorítmicos, y exhiben inestabilidad fuera de las familias de objetivos con buen comportamiento.

– La importancia de mejores modelos en optimización estocástica, 2019.

Es más común referirse a un algoritmo que usa aleatoriedad que a una función objetivo que contiene evaluaciones ruidosas cuando se habla de optimización estocástica. Esto se debe a que la aleatoriedad en la función objetivo se puede abordar utilizando aleatoriedad en el algoritmo de optimización. Como tal, la optimización estocástica puede denominarse “optimización robusta. “

Un algoritmo determinista puede estar engañado (por ejemplo, “engañado” o “confundido“) Por la evaluación ruidosa de soluciones candidatas o gradientes de funciones ruidosas, lo que hace que el algoritmo rebote o se atasque (por ejemplo, no converja).

Los métodos de optimización estocástica proporcionan un medio para hacer frente al ruido inherente del sistema y hacer frente a modelos o sistemas que son altamente no lineales, de alta dimensión o inapropiados para los métodos deterministas clásicos de optimización.

– Optimización estocástica, 2011.

El uso de la aleatoriedad en un algoritmo de optimización permite que el procedimiento de búsqueda funcione bien en problemas de optimización desafiantes que pueden tener una superficie de respuesta no lineal. Esto se logra mediante el algoritmo que toma pasos o movimientos subóptimos localmente en el espacio de búsqueda que le permiten escapar de los óptimos locales.

La aleatoriedad puede ayudar a escapar de los óptimos locales y aumentar las posibilidades de encontrar un óptimo global.

– Página 8, Algoritmos de optimización, 2019.

La aleatoriedad utilizada en un algoritmo de optimización estocástica no tiene que ser una verdadera aleatoriedad; en cambio, el pseudoaleatorio es suficiente. Un generador de números pseudoaleatorios se usa casi universalmente en optimización estocástica.

El uso de la aleatoriedad en un algoritmo de optimización estocástica no significa que el algoritmo sea aleatorio. En cambio, significa que algunas decisiones tomadas durante el procedimiento de búsqueda implican una parte de aleatoriedad. Por ejemplo, podemos conceptualizar esto como que el movimiento de la corriente al siguiente punto en el espacio de búsqueda realizado por el algoritmo puede realizarse de acuerdo con una distribución de probabilidad relativa al movimiento óptimo.

Ahora que tenemos una idea de qué es la optimización estocástica, veamos algunos ejemplos de algoritmos de optimización estocástica.

Algoritmos de optimización estocástica

El uso de la aleatoriedad en los algoritmos a menudo significa que las técnicas se denominan “búsqueda heurística”, ya que utilizan un procedimiento de regla general que puede funcionar o no para encontrar el óptimo en lugar de un procedimiento preciso.

Muchos algoritmos estocásticos se inspiran en un proceso biológico o natural y pueden denominarse “metaheurísticas” como un procedimiento de orden superior que proporciona las condiciones para una búsqueda específica de la función objetivo. También se les conoce como “caja negra”Algoritmos de optimización.

La metaheurística es un término bastante desafortunado que se utiliza a menudo para describir un subcampo principal, de hecho el subcampo principal, de optimización estocástica.

– Página 7, Fundamentos de metaheurística, 2011.

Existen muchos algoritmos de optimización estocástica.

Algunos ejemplos de algoritmos de optimización estocástica incluyen:

  • Búsqueda local iterada
  • Escalada estocástica
  • Descenso de gradiente estocástico
  • Búsqueda tabú
  • Procedimiento de búsqueda adaptativa aleatoria codiciosa

Algunos ejemplos de algoritmos de optimización estocástica que se inspiran en procesos biológicos o físicos incluyen:

  • Recocido simulado
  • Estrategias de evolución
  • Algoritmo genético
  • Evolución diferencial
  • Optimización de Enjambre de partículas

Ahora que estamos familiarizados con algunos ejemplos de algoritmos de optimización estocástica, veamos algunas consideraciones prácticas al usarlos.

Consideraciones prácticas para la optimización estocástica

Existen consideraciones importantes cuando se utilizan algoritmos de optimización estocástica.

La naturaleza estocástica del procedimiento significa que cualquier ejecución única de un algoritmo será diferente, dada una fuente diferente de aleatoriedad utilizada por el algoritmo y, a su vez, diferentes puntos de partida para la búsqueda y decisiones tomadas durante la búsqueda.

El generador de números pseudoaleatorios que se utiliza como fuente de aleatoriedad se puede sembrar para asegurar que se proporcione la misma secuencia de números aleatorios en cada ejecución del algoritmo. Esto es bueno para pequeñas demostraciones y tutoriales, aunque es frágil ya que trabaja contra la aleatoriedad inherente del algoritmo.

En cambio, un algoritmo dado se puede ejecutar muchas veces para controlar la aleatoriedad del procedimiento.

Esta idea de múltiples ejecuciones del algoritmo se puede utilizar en dos situaciones clave:

  • Comparación de algoritmos
  • Evaluación del resultado final

Los algoritmos pueden compararse en función de la calidad relativa del resultado encontrado, el número de evaluaciones de funciones realizadas o alguna combinación o derivación de estas consideraciones. El resultado de cualquier ejecución dependerá de la aleatoriedad utilizada por el algoritmo y por sí solo no puede representar de manera significativa la capacidad del algoritmo. En cambio, se debe utilizar una estrategia de evaluación repetida.

Cualquier comparación entre algoritmos de optimización estocástica requerirá la evaluación repetida de cada algoritmo con una fuente diferente de aleatoriedad y el resumen de la distribución de probabilidad de los mejores resultados encontrados, como la media y la desviación estándar de los valores objetivos. A continuación, se puede comparar el resultado medio de cada algoritmo.

En los casos en los que es probable que existan múltiples mínimos locales, puede ser beneficioso incorporar reinicios aleatorios después de que se cumplan nuestras condiciones de terminación, donde reiniciamos nuestro método de descenso local desde puntos iniciales seleccionados al azar.

– Página 66, Algoritmos de optimización, 2019.

De manera similar, cualquier ejecución única de un algoritmo de optimización elegido por sí sola no representa de manera significativa los óptimos globales de la función objetivo. En cambio, se debe utilizar una estrategia de evaluación repetida para desarrollar una distribución de soluciones óptimas.

El máximo o mínimo de la distribución se puede tomar como solución final, y la propia distribución proporcionará un punto de referencia y confianza de que la solución encontrada es “relativamente bueno” o “suficientemente bueno”Dados los recursos gastados.

  • Reinicio múltiple: Un enfoque para mejorar la probabilidad de localizar los óptimos globales mediante la aplicación repetida de un algoritmo de optimización estocástica a un problema de optimización.

La aplicación repetida de un algoritmo de optimización estocástica en una función objetivo a veces se denomina estrategia de reinicio múltiple y puede incorporarse al algoritmo de optimización en sí o prescribirse de manera más general como un procedimiento en torno al algoritmo de optimización estocástico elegido.

Cada vez que haces un reinicio aleatorio, el escalador termina en algún óptimo local (posiblemente nuevo).

– Página 26, Fundamentos de metaheurística, 2011.

Otras lecturas

Esta sección proporciona más recursos sobre el tema si está buscando profundizar.

Tutoriales relacionados

Documentos

Libros

Artículos

Resumen

En este tutorial, descubrió una suave introducción a la optimización estocástica.

Específicamente, aprendiste:

  • Los algoritmos de optimización estocástica utilizan la aleatoriedad como parte del procedimiento de búsqueda.
  • Ejemplos de algoritmos de optimización estocástica como recocido simulado y algoritmos genéticos.
  • Consideraciones prácticas al utilizar algoritmos de optimización estocástica, como evaluaciones repetidas.

¿Tiene usted alguna pregunta?
Haga sus preguntas en los comentarios a continuación y haré todo lo posible para responder.