Búsqueda Tabú

El algoritmo consiste en utilizar Búsqueda Local pero con una solución inicial brindada con un factor de azar. La solución que brinda se guarda para futuras comparaciones y será actualizado en aquellos casos donde la nueva solución sea mejor que la anterior.

El motivo por el cual se parte de una solución inicial al azar es porque, al ser GRASP un algoritmo que solamente termina cuando llega a su límite de iteraciones máximas o durante unas iteraciones predeterminadas no hubo cambios. Si la solución fuese la cota inferior, siempre partiría de la misma, y siempre llegaría a lo mismo, terminando el algoritmo en los pasos dichos por la cantidad de iteraciones sin cambios.

-while
-Genera Solución inicial
-Aplica Busqueda Local
-if la solucion actual es mejor solucion
   mejorSol= solActual
}}
return  mejorSol;



En el peor caso, el algoritmo deberá  iterar hasta alcanzar la cantidad máxima de iteraciones (ya que se supone que es mucho mayor a la cantidad de iteraciones que deben pasar sin cambios para parar). Dado que en cada iteración se ejecutan SolucionInicial y la BusquedaLocal, la complejidad sería
                        O(im ∗ (n² + n⁵ m)) = O(im ∗ n⁵ m)
aunque, por supuesto, no se espera que llegue nunca a ejecutar casos de ese estilo.

En cada etapa construir una lista de candidatos con movimientos admisibles Ordenados con respecto a su beneficio.
Restringir la lista de forma que contenga buenos movimiento aunque no necesariamente óptimo „ Restringir por cardinalidad (los Objetivos mejores)

Idea:produce una diversidad de buenas soluciones, se espera que al menos una de ellas esté en un entorno de la solución óptima.

Se generaron 15 aristas.

Cota inferior: 4.

Cota superior: 7.

0 0 5 factible

0 1 5 factible

0 2 5 factible

0 3 5 factible

0 4 5 factible

1 0 7 factible

1 1 7 factible

1 2 7 factible

1 3 7 factible

1 4 7 factible

2 0 7 factible

2 1 7 factible

2 2 7 factible

2 3 6 factible

2 4 6 factible

3 0 7 factible

3 1 6 factible

3 2 6 factible

3 3 6 factible

3 4 6 factible

4 0 7 factible

4 1 7 factible

4 2 7 factible

4 3 7 factible

4 4 7 factible

5 0 6 factible

5 1 6 factible

5 2 6 factible

5 3 6 factible

5 4 6 factible

6 0 7 factible

6 1 7 factible

6 2 7 factible

6 3 7 factible

6 4 7 factible

public static boolean tabu (ArrayList<ArrayList<Integer>>cola, ArrayList<Integer> solucion, int iter)
    {
 cola = null;
 while(iter>0)
     { 
  if(cola.contains(solucion))
      {
   //cont++;modifica();
   return false;
      }
  else 
      {
   cola.add(solucion);
   if (cola.size()>=iter)
       {
    cola.remove(cola.get(0));
       }
      }
     }
 return true;
    }
    //busqueda**
    public static ArrayList<Integer> busqueda(ArrayList<Arista> grafo, int n,int it,int re) {
 ArrayList<ArrayList<Integer>> listatabu = 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
     
     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
  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 (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());
   }
      }
  } 
  System.out.println(reinicio + " " +iter + " " + obj + " " + (fact ? "factible" : "no factible")) ;
     }
 }
 // return mejorSol;//regresa la mejor solucion 
 //incluir busqueda tabú

 while(intentos>0)
     {
  TAB=false;
  int Obj=Arista.objetivo(mejorSol);
  boolean fact=Arista.factible(mejorSol,grafo);
  ArrayList<Integer> Actual = Arista.modificacion(mejorSol,n,fact);
  fact=Arista.factible(Actual,grafo);
  int objetivo=Arista.objetivo(Actual);
  
  if(tabu(listatabu,Actual,10)==true)//lista!
      {
   if(fact==true && Obj<=objetivo)
       {
    TAB=true;
    mejorSol = Actual;
    Obj = objetivo;
    if(objetivo<Obj)
       {
    System.out.println("MejorSolucion "+mejorSol+"Cobertura"+Obj+".");
    Arista.imprime(listatabu);//
       }
    if(TAB ==false)
        {
     intentos --;
        }  
    else
        System.out.println("reintenta ->"+"#intentos:"+intentos);      
       }
      }
     }
 return mejorSol;
    }