lunes 12 agosto 2024

¿Qué es el Algoritmo de Temple Simulado?

El algoritmo de temple simulado es un método de optimización heurística utilizado para resolver problemas complejos, en los cuales se busca encontrar la mejor solución posible dentro de un gran espacio de soluciones. Este algoritmo, inspirado en el proceso de recocido metálico (en inglés, Simulated Annealing), es particularmente útil cuando otras técnicas de optimización pueden quedar atrapadas en mínimos locales.

¿Cómo Funciona el Algoritmo de Temple Simulado?

El algoritmo de temple simulado imita el proceso de enfriamiento de un material para llegar a un estado de baja energía. A continuación, te explicamos su funcionamiento y te mostramos cómo implementarlo en JavaScript.

1. Inicialización

El algoritmo comienza con una solución inicial y una temperatura alta. La temperatura controla la probabilidad de aceptar soluciones peores durante la búsqueda.

2. Iteración

En cada paso, se genera una nueva solución a partir de la solución actual, alterándola ligeramente. Si esta nueva solución es mejor que la actual, se acepta como la nueva solución. Si es peor, se acepta con una cierta probabilidad que depende de la temperatura.

3. Enfriamiento

La temperatura se reduce gradualmente a medida que avanza el algoritmo. A medida que la temperatura disminuye, la probabilidad de aceptar soluciones peores también disminuye.

4. Finalización

El proceso continúa hasta que la temperatura alcanza un umbral mínimo predefinido, o después de un número determinado de iteraciones.

Ejemplo en JavaScript

Supongamos que queremos resolver un problema simple: encontrar el valor mínimo de una función matemática. Usaremos el algoritmo de temple simulado para buscar el mínimo de la función:

f (x) = x^{2} + 4 \sin (5 x)

en el intervalo

[- 10, 10]

Paso 1: Implementar la función objetivo

function objectiveFunction(x) {
    return x * x + 4 * Math.sin(5 * x);
}

Esta función define la fórmula que queremos minimizar.

Paso 2: Implementar el Algoritmo de Temple Simulado

function simulatedAnnealing() {
    let currentSolution = Math.random() * 20 - 10;  // Solución inicial aleatoria en [-10, 10]
    let currentEnergy = objectiveFunction(currentSolution);
    let bestSolution = currentSolution;
    let bestEnergy = currentEnergy;
    let temperature = 100;  // Temperatura inicial
    const coolingRate = 0.99;  // Tasa de enfriamiento
    const absoluteTemperature = 0.01;  // Temperatura mínima

    while (temperature > absoluteTemperature) {
        let newSolution = currentSolution + (Math.random() * 2 - 1);  // Pequeña perturbación a la solución actual
        if (newSolution < -10 || newSolution > 10) continue;  // Asegura que estamos dentro de los límites

        let newEnergy = objectiveFunction(newSolution);

        // Aceptar la nueva solución si es mejor o con cierta probabilidad si es peor
        if (newEnergy < currentEnergy || Math.random() < Math.exp((currentEnergy - newEnergy) / temperature)) {
            currentSolution = newSolution;
            currentEnergy = newEnergy;
        }

        // Actualizar la mejor solución encontrada
        if (currentEnergy < bestEnergy) {
            bestSolution = currentSolution;
            bestEnergy = currentEnergy;
        }

        // Enfriar la temperatura
        temperature *= coolingRate;
    }

    return bestSolution;
}

let result = simulatedAnnealing();
console.log("Mejor solución encontrada: " + result);
console.log("Valor de la función en la mejor solución: " + objectiveFunction(result));

Explicación del Código

1. Objetivo de la Función (objectiveFunction): La función objectiveFunction(x) define la función que queremos minimizar. En este caso, es:

f (x) = x^{2} + 4 \sin (5 x)

2. Inicialización: En simulatedAnnealing, comenzamos con una solución aleatoria en el intervalo [-10, 10] y calculamos su "energía" usando objectiveFunction.

3. Iteración:

Se genera una nueva solución newSolution mediante una pequeña perturbación aleatoria de la solución actual.
Se calcula la energía de la nueva solución newEnergy.
Se decide si se acepta la nueva solución, basándose en si es mejor o, si es peor, con una probabilidad que depende de la temperatura.

4. Enfriamiento: La temperatura se reduce multiplicándola por coolingRate en cada iteración.

5. Finalización: El bucle continúa hasta que la temperatura es menor que absoluteTemperature. Al final, simulatedAnnealing devuelve la mejor solución encontrada.

Ventajas del Algoritmo de Temple Simulado

1. Escapatoria de mínimos locales: Permite escapar de mínimos locales al aceptar soluciones peores en las primeras etapas, cuando la temperatura es alta.

2. Simplicidad y Flexibilidad: Es fácil de implementar y puede adaptarse a una amplia variedad de problemas.

Conclusión

El algoritmo de temple simulado es una técnica poderosa y versátil para optimizar problemas complejos. Su implementación en JavaScript, como hemos visto, es relativamente sencilla y puede ser ajustada para adaptarse a diferentes necesidades de optimización. Con una comprensión adecuada de su funcionamiento y ajuste de parámetros, este algoritmo puede ser una herramienta invaluable en la caja de herramientas de cualquier programador o científico de datos.

Etiquetas:

algoritmos javascript

Creado por:

Jorge García

Fullstack developer