Enfriamiento Simulado - Ejercicios de Algorítmica

En este artículo vamos a realizar un ejercicio de Algorítmica donde vamos a poner en práctica lo aprendido en el artículo de teoría sobre Enfriamiento Simulado, también llamado "Recocido Simulado", "Temple Simulado", o en inglés Simulated Annealing.

Ejercicio práctico sobre Enfriamiento Simulado

Queremos hallar el máximo de f(x)=x3 -60x2+900x+100 entre x=0 y x=31. Para resolver el problema usando SA, se propone seguir la siguiente estrategia. En primer lugar, discretizamos el rango de valores de x con vectores binarios de 5 componentes entre 00000 y 11111. Estos 32 vectores constituyen S las soluciones factibles del problema. Le damos un valor inicial a T intuitivamente, por ejemplo, T0 =100 o 500 y en cada iteración del algoritmo lo reduciremos en 10%, es decir utilizando la estrategia de descenso geométrico: Tk = 0.9 Tk-1. Cada iteración consiste de lo siguiente: 

1. El número de vecinos queda fijado a 5, siendo éstos variaciones de un bit de la solución. Por ejemplo, si partimos de 00011, los 5 posibles vecinos resultantes serían: 10011, 01011, 00111, 00001, 00010.

2. Para aplicar el criterio de aceptación, escogemos un vecino, buscamos su coste asociado en la tabla auxiliar que se proporciona y calculamos la diferencia con la solución actual. Si está más cerca del óptimo se acepta, si no, se aplica Pa (δ, T) = e-δ/T . Siendo T la temperatura actual y δ la diferencia de costes entre la solución candidata y la actual. 

3. Concluya la búsqueda cuando el proceso se enfríe o cuando no se acepte ninguna solución de su vecindad.

4. Imagen de guía:

Ejercicio resuelto de Enfriamiento Simulado

Posible solución al ejercicio usando java. En el ejemplo podemos apreciar cómo si disminuimos el enfriamiento de la temperatura (temp *= 0.90) a (temp *= 0.99) obtendremos por lo general un resultado más exacto porque realizaremos más iteraciones, mientras que si enfriamos más rápidamente, (temp *= 0.90) a (temp *= 0.80) obtendremos resultados peores.

public class Ej1 {

    public static void main(String[] args) {
        int temp = 1000;
        int tempFinal = 10;
     
        // Solución inicial aleatoria
        int sol[] = {0, 0, 0, 0, 0};
        while (temp > tempFinal) {
         
            boolean encontrado = false;
         
            // Copiamos la solución de sol en mejorVecino
            int[] mejorVecino = new int[sol.length];
            System.arraycopy(sol, 0, mejorVecino, 0, sol.length);
            // Calculo el coste de la funcion con el vecino actual
            int costeActual = costeFuncion(binarioADecimal(mejorVecino));
         
            // Copiamos el vecino actual para ir modificándolo
            int[] copiaVecino = new int[sol.length];
            System.arraycopy(sol, 0, copiaVecino, 0, sol.length);
         
            for (int i = 0; i < sol.length && !encontrado ; i++ ){
             
                // Hallamos los vecinos con una función que altera los bits
                // Por ejemplo los vecinos de {0,0,1,0,1} serían:
                // {1,0,1,0,1}, {0,1,1,0,1}, {0,0,0,0,1}, {0,0,1,1,1} y {0,0,1,0,0}
             
                if (copiaVecino[i] == 1){
                    copiaVecino[i] = 0;
                } else {
                    copiaVecino[i] = 1;
                }
             
                // Comparamos el coste del vecino actual con el nuevo vecino
                // y lo aceptamos si el coste es mayor o la probabilidad
                // de aceptación es mayor, lo aceptamos
             
                if (costeActual < costeFuncion(binarioADecimal(copiaVecino)) ||
                        probabilidadAceptacion(costeActual,
                                costeFuncion(binarioADecimal(copiaVecino)), temp) > Math.random()){
                 
                    mejorVecino = copiaVecino;
                    costeActual = costeFuncion(binarioADecimal(copiaVecino));
                    encontrado = true;
                }
             
                copiaVecino = new int[sol.length];
                System.arraycopy(sol, 0, copiaVecino, 0, sol.length);
                           
            }
         
            sol = mejorVecino;
         
            // Enfriamos la temperatura en cada iteración         
            temp *= 0.90;
         
        }
     
        // Mostramos los resultados por pantalla
     
        System.out.print("Número binario: [");
        for (int i = 0 ; i < sol.length ; i++){
            System.out.print(sol[i]);
        }
        System.out.print("]");
     
        int dec = binarioADecimal(sol);
        System.out.println(", Valor en decimal: " + dec + " ,Coste: " + costeFuncion(dec) );
     
    }
    public static int costeFuncion(int x) {
     
        // Realizamos el coste según la operación propuesta
        int v = 0;
        v = (int) Math.pow(x, 3) - 60 * (int) Math.pow(x, 2) + (900 * x) + 100;
        return v;
    }
    public static int binarioADecimal(int[] binario) {
        // Realizamos una función para convertir el array de binarios en un valor decimal
     
        int v = 0;
        int cont = 0;
     
        for (int i = binario.length - 1; i >= 0; i--) {
            if (binario[i] == 1) {
                v += (int) Math.pow((double) 2, (double) cont);
            }
            cont++;
        }
        return v;
    }
 
    public static double probabilidadAceptacion (int costeActual, int costeVecino, double temperatura){
     
        // Si la nueva solucion es peor se calcula una probabilidad de aceptación
     
        return Math.exp((costeVecino - costeActual) / temperatura);
    }
}