Enfriamiento Simulado - Problema de la Mochila - Ejercicios de Algorítmica

Vamos a resolver el problema de la mochila utilizando Enfriamiento Simulado. Para ello, supongamos que la capacidad de la mochila es q = 180 y que puede insertar hasta 100 elementos, con pesos aleatorios comprendidos entre [1, 100], esto es, considere el siguiente vector P = {p1, p2, …, p100}, con pi = [1,100]. Se permite que dos elementos pesen lo mismo.

Solución al Problema de la Mochila con Enfriamiento Simulado

Una posible solución es la siguiente:

public class Ej2 {
    public static void main(String[] args) {
        double temp = 1000.0;
        double tempFinal = 10;
        int objetosMax = 100;
        int pesoMax = 180;
     
        int[] sol = generarSolInicial(objetosMax);
        int[] pesos = generarPesos(objetosMax, pesoMax);
   
        while (temp > tempFinal) {
            int[] mejorVecino = new int[sol.length];
         
            // Copiamos el Mejor vecino actual que es nuestra solución inicial
            System.arraycopy(sol, 0, mejorVecino, 0, sol.length);
         
            //Calculo el coste (peso) de la funcion con el vecino actual
            int costeActual = costeFuncion(mejorVecino, pesos);
         
            //Copiamos el vecino actual para ir modificando
            int[] copiaVecino = new int[sol.length];
            System.arraycopy(sol, 0, copiaVecino, 0, sol.length);
            boolean encontrado = false;
            for (int i = 0; i < sol.length && encontrado == false; 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 si es menor o igual que el peso maximo y tiene mayor coste
                // o probabilidad de aceptacion es mayor que 1 lo acepto
             
                if (costeFuncion(copiaVecino, pesos) <= pesoMax &&
                        ((costeActual < costeFuncion(copiaVecino, pesos) ||
                        probabilidadAceptacion(costeActual, costeFuncion(copiaVecino, pesos), temp) > 1 ))) {
                    mejorVecino = copiaVecino;
                    costeActual = costeFuncion(copiaVecino, pesos);
                    encontrado = true;
             
                // Si no se cumple la condición, dejamos el array como estaba
                } else {           
                    copiaVecino = new int[sol.length];
                    System.arraycopy(sol, 0, copiaVecino, 0, sol.length);
                }
            }
         
            sol = mejorVecino; //Igualamos la solucion al mejor vecino
            temp *= 0.9; // Enfriamos la temperatura un 10%
        }
        System.out.print("Objetos que llevamos en la mochila (1, si) (0, no) : ");
        for (int i = 0; i < sol.length; i++) {
            System.out.print(sol[i]);
            if (i != pesos.length - 1)
                System.out.print(",");
        }
     
        System.out.print("\nPesos: ");
     
        for (int i = 0; i < pesos.length; i++) {
            System.out.print(pesos[i]);
            if (i != pesos.length - 1)
                System.out.print(",");
        }
        System.out.println("\nLa mochila lleva: " + costeFuncion(sol, pesos) + "kg de peso");
    }
    // Calculamos el coste (peso) sumando los objetos cogidos
    // es decir, los que tienen 1 en el array de binarios
    // dicha suma nos dará el peso total de los objetos que llevamos
    // en la mochila
 
    public static int costeFuncion(int[] mejorVecino, int[] pesos) {
     
        int peso = 0;
        for (int i = 0; i < mejorVecino.length; i++) {
            if (mejorVecino[i] == 1) {
                peso += pesos[i];
            }
        }
        return peso;
    }
    public static double probabilidadAceptacion(int costeActual, int costeVecino, double temperatura) {
        return Math.exp((costeVecino - costeActual) / temperatura);
    }
    // Creamos un array de ceros de tamaño tam
    // Suponiendo que la mochila en un principio está vacía
    // 1 en el array significará que el objeto de dicha
    // posición ha sido cogido
    public static int[] generarSolInicial(int tam) {
        int[] solInicial = new int[tam];
        for (int i = 0; i < tam; i++) {
            solInicial[i]=0;
        }
        return solInicial;
    }
 
    // Generamos pesos aleatorios de 0 a 100
 
    public static int[] generarPesos(int size, int pesoMax) {
        int[] pesos = new int[size];

        for (int i = 0; i < size; i++) {
            pesos[i] = (int) (Math.random() * 100);
        }

        return pesos;
    }
}