▷ ¿Cómo usar recocido simulado para aproximar una función?

Estás leyendo la publicación: ¿Cómo usar recocido simulado para aproximar una función?

El recocido simulado es una técnica de búsqueda no informada para optimizar los mínimos globales de una función. Se ha convertido en un enfoque popular en las últimas dos décadas debido a su facilidad de implementación, cualidades de convergencia y uso de movimientos de escalada para escapar de los óptimos locales. Se utiliza principalmente para resolver problemas de optimización discreta y, en menor medida, problemas de optimización continua. En este artículo, analizaremos el recocido simulado con una pequeña implementación para comprender el funcionamiento de esta técnica. Usando este método, encontraremos los mínimos de una función dada. Los siguientes son los temas a tratar.

Tabla de contenido

Acerca de la optimización local
Acerca del recocido simulado
Trabajo de recocido simulado
Implementación de recocido simulado para optimizar una función

Simulated Annealing es un algoritmo de búsqueda local meta-heurístico capaz de escapar de los óptimos locales. Comencemos por comprender la optimización local.

Acerca de la optimización local

Un problema de optimización combinatoria se define definiendo una colección de soluciones y una función de costo que asigna un valor numérico a cada opción. Una solución óptima es aquella que tiene el costo más bajo posible (puede haber más de una de esas soluciones). La optimización local tiene como objetivo mejorar una solución arbitraria a un problema de este tipo mediante una serie de mejoras locales incrementales.

Para comenzar a definir un algoritmo de optimización local, proporcione una forma de perturbar las soluciones para adquirir varias soluciones. La vecindad de ‘A’ se refiere al conjunto de soluciones que pueden adquirirse en uno de esos pasos a partir de una solución dada ‘A’. Luego, el algoritmo ejecuta el ciclo básico, dejando las técnicas precisas para seleccionar una solución (S) y un vecino no probado (S’) para los detalles de implementación.

Aunque S no tiene que ser la mejor solución después de que se complete el ciclo, será localmente óptimo en el sentido de que ninguno de sus vecinos tiene un costo menor. La esperanza es que localmente óptimo funcione. A continuación se muestra la imagen con un conjunto de pasos para calcular la optimización local.

Revista de análisis de la India

¿Está buscando un repositorio completo de bibliotecas de Python utilizadas en ciencia de datos, echa un vistazo aquí.

Acerca del recocido simulado

El recocido simulado recibe su nombre del proceso de recocido físico con sólidos, en el que un sólido cristalino se calienta y luego se enfría suavemente hasta que obtiene la estructura de red cristalina más regular posible y, por lo tanto, está libre de fallas en el cristal.

La disposición final da como resultado un sólido con mayor integridad estructural si el programa de enfriamiento es adecuadamente lento. El recocido simulado conecta este tipo de comportamiento termodinámico con la búsqueda de mínimos globales en un problema de optimización discreto. También presenta un método algorítmico para aprovechar dicha relación.

Los valores de dos soluciones (la solución actual y una solución recién seleccionada) se comparan en cada iteración de un proceso de recocido simulado aplicado a un problema de optimización discreto. Siempre se aceptan soluciones de mejora, mientras que se permite un subconjunto de soluciones de no mejora (inferiores) con el objetivo de escapar de los óptimos locales y alcanzar los óptimos globales.

La probabilidad de aceptar soluciones que no mejoran está determinada por un parámetro de temperatura, que normalmente no aumenta con cada iteración del algoritmo.

El aspecto algorítmico esencial del recocido simulado es que permite el escape de los óptimos locales a través de pasos de escalada (es decir, movimientos que empeoran el valor de la función objetivo). A medida que el parámetro de temperatura se aproxima a cero, los movimientos de escalada se vuelven menos comunes y la distribución de soluciones asociada con la cadena de Markov no homogénea que modela el comportamiento del algoritmo converge a una forma en la que toda la probabilidad se concentra en el conjunto de soluciones globalmente óptimas (siempre que la algoritmo es convergente; de lo contrario, el algoritmo convergerá a un óptimo local, que puede ser o no globalmente óptimo).

Trabajo de recocido simulado

Se requieren varias definiciones para caracterizar los aspectos especiales de un enfoque de recocido simulado para problemas de optimización discretos.

Considere una colección de todas las soluciones potenciales, a menudo conocida como el espacio de solución. Luego, en el espacio de soluciones, crea una función objetivo. El propósito es determinar el mínimo global que existe en el conjunto de soluciones. Para verificar que existe un mínimo global, la función objetivo debe estar restringida. Para la colección de soluciones, defina una función de vecindad. Como resultado, las soluciones vecinas se asocian con cada solución y se pueden obtener en una sola iteración de un algoritmo de búsqueda local.

El recocido simulado comienza con una solución elegida de una colección de soluciones. Posteriormente se crea una solución vecina, ya sea al azar o de acuerdo con una regla predefinida. El criterio de aceptación de Metropolis se usa para representar cómo un sistema termodinámico progresa desde la solución o estado actual hasta una solución candidata con el contenido de energía más bajo.

Con base en la probabilidad de aceptación, la solución candidata se elige como la solución actual. Esta probabilidad de aceptación es el bloque de construcción fundamental del proceso de búsqueda en el recocido simulado. Si la temperatura se reduce gradualmente, el sistema puede acercarse a un equilibrio (estado estacionario) con cada repetición.

Se especifican las funciones objetivo y se denota la energía asociada con las soluciones. El equilibrio está determinado por la distribución de Boltzmann. Podría definirse como la probabilidad de que el sistema se encuentre en un estado con una función de energía (la función objetivo) a una determinada temperatura, donde la probabilidad es proporcional al total de todas las funciones concebibles.

Si la probabilidad de crear una solución candidata a partir de los vecinos de la solución es uno, entonces se puede crear una matriz estocástica cuadrada no negativa con probabilidades de transición. Estas probabilidades de transición definen un conjunto de soluciones producidas por una cadena de Markov no homogénea.

Implementación de recocido simulado para optimizar una función

Implementemos recocido simulado calculando una búsqueda ciega para optimizar los mínimos de la función y observar el progreso.

Importar bibliotecas necesarias

importar numpy como np importar matplotlib.pyplot como plt

Definición de la función objetivo para la que se ha de realizar la optimización. Usaremos una función objetivo unidimensional sencilla con límites [-10,10] con el óptimo en 0.0.

def objetivo(x): devolver x[0]**2.0 r_min, r_max = -10.0, 10.0 entradas = np.arange(r_min, r_max, 0.1) resultados = [objective([x]) para x en entradas]plt.plot(entradas, resultados) x_optima = 0.0 plt.axvline(x=x_optima, ls=”–“, color=”red”) plt.show()

Después de eso, podemos tener una comprensión más clara de cómo el criterio de aceptación metropolitano cambia con la temperatura a lo largo del tiempo. Los criterios dependen de la temperatura, pero también dependen de cuán diferente sea la evaluación objetiva del nuevo punto de la solución de trabajo actual. Como resultado, trazaremos el criterio para algunas “diferencias en el valor de la función objetivo” distintas para mostrar cómo afectan la probabilidad de aceptación.

iteraciones = 120 initial_temp = 12 iteraciones = [i for i in range(iterations)]
temperaturas = [initial_temp/float(i + 1) for i in iterations]
diferencias = [0.01, 0.1, 0.5, 1.0]
para d en diferencias: metropolis = [np.exp(-d/t) for t in temperatures]
label=”diff=%.2f” % d plt.plot(iteraciones, metrópolis, label=label) plt.xlabel(‘Iteración’) plt.ylabel(‘Criterio de Metrópolis’) plt.legend() plt.show()

El gráfico se divide en cuatro líneas para representar las cuatro disparidades entre la nueva opción más pobre y la solución funcional actual. Como se puede predecir, cuanto mayor sea la disparidad, menos probable es que el modelo acepte la peor opción, independientemente de la repetición del algoritmo. También podemos ver que la posibilidad de aceptar respuestas inferiores se reduce con la iteración del algoritmo en todas las circunstancias.

Construyamos una función de recocido simulada

def recocido_simulado(objetivo, límites, n_iteraciones, tamaño de paso, temperatura): mejor = límites[:, 0] + np.random.rand(len(límites)) * (límites[:, 1] – límites[:, 0]) best_eval = objetivo (mejor) curr, curr_eval = mejor, best_eval puntuaciones = list() for i in range(n_iterations): candidato = curr + np.random.randn(len(límites)) * paso_tamaño candidato_eval = objetivo(candidato) if evaluación_candidato < evaluación_mejor: mejor, evaluación_mejor = candidato, puntajes evaluación_candidato. / float(i + 1) metropolis = np.exp(-diff / t) if diff < 0 or np.random.rand() < metropolis: curr, curr_eval = candidato, candidato_eval return [best, best_eval, scores]

Ahora que sabemos cómo se comportan la temperatura y el criterio de aceptación de la metrópolis con el tiempo, podemos usar recocido simulado para nuestro problema de prueba.

np.random.seed(10) límites = np.asarray([[-10.0, 10.0]]) n_iteraciones = 1000 step_size = 0.1 temp = 12 mejor, puntuación, puntuaciones = recocido_simulado(objetivo, límites, n_iteraciones, step_size, temp) print(‘Completado…’) print(‘f(%s) = %f’ % (mejor puntuación))

Comience por sembrar el generador de números pseudoaleatorios. Esto no es esencial en general, pero es necesario en este caso para asegurarse de que se produzca la misma secuencia de números aleatorios cada vez que se realiza el método para que los resultados puedan graficarse posteriormente.

El algoritmo buscará 1000 iteraciones con un tamaño de paso de 0,1 en este ejemplo. La temperatura inicial será de 12.0. Debido a que la técnica de búsqueda es más sensible al programa de recocido que a la temperatura inicial, los ajustes de temperatura inicial son casi arbitrarios.

Trazar el informe de progreso

plt.figure(figsize=(10,5)) plt.plot(puntajes, ‘.-‘) plt.xlabel(‘Número de mejora’) plt.ylabel(‘Evaluación f(x)’) plt.show()

Durante la búsqueda de escalada, se construye un gráfico de líneas para mostrar la evaluación de la función objetivo para cada mejora. Durante la búsqueda, podemos ver aproximadamente 78 cambios en la evaluación de la función objetivo, con cambios sustanciales al principio y cambios muy modestos a imperceptibles cerca de la conclusión a medida que el algoritmo se asienta en los valores óptimos.

Veredicto Final

Los métodos de optimización de recocido simulado se pueden usar para resolver problemas de optimización de un solo objetivo y de múltiples objetivos. Se ha utilizado en disciplinas tan diversas como la ingeniería de sistemas de procesos, la investigación de operaciones y los materiales inteligentes. Con este artículo de implementación práctica, hemos entendido el funcionamiento del recocido simulado para optimizar la aproximación de una función.

Referencias

Tabla de Contenido

¿Cómo usar recocido simulado para aproximar una función?