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; }
Ay, que no anden googleando. Esto no es en sí un GRASP. Me preocupa lo de la comparación porque es sensible al orden de los elementos. Habría que ordenarlos de menor a mayor o algo después de cada creación y modificación para que se pueda comparar de esa manera. De hecho, no estoy segura si mi propio código sufre del mismo problema :P Van 6 pts por este avance.
ResponderEliminar