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;
}
