Busqueda Recocido Simulado

El Enfriamiento o Recocido Simulado es un algoritmo de búsqueda por entornos con un criterio probabilístico de aceptación de soluciones basado en enfriamiento (Termodinámica).

„ Un modo de evitar que la búsqueda local finalice en óptimos locales, hecho que suele ocurrir con los algoritmos tradicionales de búsqueda local, es permitir que algunos movimientos sean hacia soluciones peores„ Pero si la búsqueda está avanzando realmente hacia una buena solución,
estos movimientos “de escape de óptimos locales” deben realizarse de un modo controlado,esto se realiza controlando la frecuencia de los movimientos de escape mediante una función de
probabilidad que hará disminuir la probabilidad de estos movimientos hacia soluciones peores conforme avanza la búsqueda (y por tanto estamos más cerca, previsiblemente, del óptimo local)
„ Así, se aplica la filosofía habitual de búsqueda de diversificar al principio e intensificar al final.
Hace uso de una variable llamada Temperatura, T, cuyo valor determina en qué medida pueden ser aceptadas soluciones vecinas peores que la actual?? La variable Temperatura se inicializa a un valor alto, denominado Temperatura inicial, T0, y se va reduciendo cada iteración mediante un mecanismo de enfriamiento de la temperatura, α(·), hasta alcanzar una Temperatura final, Tf

#Vertices = 12 Densidad = .4
Se generaron 29 aristas.
#instancia
(0, 1)
(0, 3)
(0, 9)
(0, 11)
(1, 8)
(1, 9)
(1, 10)
(1, 11)
(2, 3)
(2, 5)
(2, 6)
(2, 10)
(3, 4)
(3, 5)
(3, 6)
(3, 7)
(4, 5)
(4, 6)
(4, 7)
(4, 8)
(4, 11)
(5, 10)
(5, 11)
(6, 7)
(6, 8)
(6, 9)
(6, 10)
(6, 11)
(8, 9)
Cota inferior: 5.
Cota superior: 10.

0 0 8 factible
0 1 8 factible
0 2 8 factible
0 3 8 factible
0 4 8 factible
1 0 10 factible
RS 9 factible
1 1 9 factible
1 2 9 factible
1 3 9 factible
1 4 9 factible
2 0 9 factible
2 1 9 factible
RS 8 factible
2 2 8 factible
2 3 8 factible
2 4 8 factible
3 0 9 factible
3 1 9 factible
3 2 9 factible
3 3 9 factible
3 4 9 factible
4 0 11 factible
4 1 10 factible
4 2 10 factible
4 3 10 factible
RS 9 factible
4 4 9 factible
5 0 8 factible
5 1 8 factible
5 2 8 factible
5 3 8 factible
5 4 8 factible
6 0 10 factible
6 1 10 factible
RS 9 factible
6 2 9 factible
6 3 9 factible
6 4 9 factible


Se realizaron cambios a la función búsqueda...

public static ArrayList<Integer> busqueda(ArrayList<Arista> grafo, int n,int it,int re,int temperact, double enfriamiento) {
        //ArrayList<ArrayList<Integer>> lista = new ArrayList<ArrayList<Integer>>();
 ArrayList<Integer> mejorSol = null;
 // int intentos =0;
 //boolean TAB;
 //define la mejor solucion como nula para que cualquiera pueda mejorarla
 int mejorObj = n;//tamaño de la cubierta inicial seria el total de nodos en el grafo idem
 ArrayList<Integer> lista = new ArrayList<Integer>();
 
 for (int reinicio = 0; reinicio < re; reinicio++) {//pasos de reinicio
     ArrayList<Integer> solucion = Arista.inicial(grafo);//solucion inicial
     //Arista.imprime(solucion);
     int obj = Arista.objetivo(solucion);//objetivo de solucion
     //temperact=1000;
     for (int iter = 0; iter < it; iter++) {//iteraciones de comparar
  boolean fact = Arista.factible(solucion, grafo);//la solucion es factible
  ArrayList<Integer> otrasolucion = modificacion(solucion, n, fact); //modifica la solucion inicial a otra solucion
  boolean otraFact = Arista.factible(otrasolucion, grafo);//verifica que sea factible
  int otraObj = Arista.objetivo(otrasolucion);//el objetivo de esta
  int temp= mejorObj - obj;
  if (otraFact && otraObj <= obj) {//si la otra es factible y el objetivo es menor igual 
      solucion = otrasolucion;//ahora cambian de papel
      obj = otraObj;
      fact = otraFact;
      if(Arista.r.nextDouble() <= Math.exp(temp))//
   {
       temperact*= enfriamiento;
       lista.add(otraObj);
       System.out.println("RS "+ otraObj+ (fact ? "  factible" : "  no factible"));
   }
      
      if (obj < mejorObj) {//si es mejor que el mejor objetivo
   mejorObj = obj;
   mejorSol = new ArrayList<Integer>();//la agrega como mejor solucion
   Iterator<Integer> ve = solucion.iterator();
   while (ve.hasNext()) {
       mejorSol.add(ve.next());
   }
      }
  } 
  lista.add(mejorObj);
  System.out.println(reinicio + " " +iter + " " + obj + " " + (fact ? "factible" : "no factible")) ;
     }
 }
 //Arista.imprime(lista);
 return mejorSol;
    }