„ 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; }
Ahí hay cierta confusión entre los conceptos "solución actual" y "la mejor solución vista". Además, falta la división por temperact en el argumento de exp(). 6 pts por el avance. Ahorita lo arreglamos llegando.
ResponderEliminar