Búsqueda Tabú - Ejercicios de Algorítmica

Vamos a dar una solución a un problema mediante un algorítmo de búsqueda Tabú en este caso sin memoria de largo alcance.

Se desea fabricar un material aislante compuesto por siete materiales distintos. Se desea encontrar cuál es el orden en que deben mezclarse dichos materiales para asegurar que sea lo más aislante posible. 

Para evaluar la calidad aislante de la solución, suponga que ésta se mide por la suma de los tres primeros componentes, esto es, sobre la figura de arriba sería 4+2+7 = 13. Si realizamos la permutación 4 5, entonces, la nueva solución candidata sería [5, 2, 7, 1, 4, 6, 3], siendo su coste 5+2+7 = 14 (>13) y por tanto se aceptaría. De esta condición se deduce que el máximo se alcanzará cuando tengamos en las tres posiciones superiores {5, 6, 7}, en cualquier orden posible o, en otras palabras, que el máximo global sería 5+6+7 = 18.

public class Ej1 {
    public static void main(String[] args) {
        int[] sol = {4, 2, 7, 1, 5, 6, 3};
        ArrayList listaTabu = new ArrayList();
        int maxListaTabu = 4;
        //Datos para testear
        int contIteraciones = 0;
        while (costeFuncion(sol) < 18) {
            //Mejor candidato actual
            int[] mejorSol = new int[sol.length];
            System.arraycopy(sol, 0, mejorSol, 0, sol.length);
            //Nueva solució actual
            int[] nuevaSol = new int[sol.length];
            System.arraycopy(sol, 0, nuevaSol, 0, sol.length);
            //Genero dos posiciones aleatorias para intercambiar,
            //posicionUno entre 0 y 2, y posicionDos entre 3 y el maximo del array
            int posicionUno = (int) Math.floor(Math.random() * 3);
            int posicionDos = (int) Math.floor(Math.random() * 3 + (sol.length - 3));
            // Intercambio los valores de la nueva solucion
            // con el método de la burbuja creando un auxiliar
            int auxiliar = nuevaSol[posicionUno];
            nuevaSol[posicionUno] = nuevaSol[posicionDos];
            nuevaSol[posicionDos] = auxiliar;
            // Criterio de aspiracion si es mejor y no esta en la lista tabu lo acepto
            if (!listaTabu.contains(nuevaSol) && costeFuncion(sol) < costeFuncion(nuevaSol)) {
                mejorSol = nuevaSol;
                // Agrego la mejor solucion a la lista tabu
                listaTabu.add(mejorSol);
                // Si está en la lista tabu y es mejor 
            } else if (listaTabu.contains(nuevaSol) && costeFuncion(sol) < costeFuncion(nuevaSol)) {
                int pos = listaTabu.indexOf(nuevaSol);
                int[] sacado = (int[]) listaTabu.get(pos);
                listaTabu.remove(pos);
                listaTabu.add(sacado);
                mejorSol = sacado;
            }
            //Si la mejor solucion es mayor que la sol actual, me quedo con la mejorSol
            if (costeFuncion(sol) < costeFuncion(nuevaSol)) {
                sol = mejorSol;
            }
            //Tenencia tabu, la lista solo contendra el maxTabuList
            if (listaTabu.size() > maxListaTabu) {
                listaTabu.remove(0); //Elimino de la lista tabú
            }
            contIteraciones++;
        }
        pintarResultado(sol);
        System.out.println("Núm iteraciones: " + contIteraciones);
        System.out.println("Lista Tabu");
        for (int i = 0; i < listaTabu.size(); i++) {
            int[] stabu = (int[]) listaTabu.get(i);
            for (int j = 0; j < sol.length; j++) {
                System.out.print(stabu[j]);
            }
            System.out.println("");
        }
    }
    public static void pintarResultado(int[] sol) {
        System.out.print("Solución: ");
        for (int i = 0; i < sol.length; i++) {
            System.out.print(sol[i]);
        }
        System.out.println(", Calidad: " + costeFuncion(sol));
    }
    public static int costeFuncion(int[] mejorSol) {
        return mejorSol[0] + mejorSol[1] + mejorSol[2];
    }
    public static double probabilidadAceptacion(int costeActual, int costeVecino, double temperatura) {
        return Math.exp((costeVecino - costeActual) / temperatura);
    }
}