Los algoritmos de búsqueda local se caracterizan por definir, dada una posible
solución del problema, soluciones vecinas. Dos soluciones se consideran vecinas si
ellas son parecidas bajo algún criterio. Definida la función de vecindad, el algoritmo lo
que hace es generar una solución inicial y proseguir a enumerar sus vecinos. Después bajo algún criterio se selecciona una mejor solución de acuerdo a la función objetivo.
La función objetivo esta definida como un valor (en este caso el numero de vértices que se utilizaron para la cubierta modificada). Luego reinicia el procedimiento pero esta vez tomando como solucion inicial a la elegida anteriormente como mejor vecina. El algoritmo finaliza cuando no existe una mejor solución que la actual.
Notar que la heurística (tal y como por definición de heurística debería de ser) no
es exacta, es decir que no brinda (necesariamente) la mejor solución al problema.
Como solución inicial se eligió una bastante sencilla. Consistió en recorrer todos los conjuntos de nodos y verificar si en la solución a devolver no existía ya alguno de sus aristas . De no ser así se agregaba uno al azar.
-Se genera solución inicial
-mientras no encuentre un menor resultado
s= solución actual
-el actual sera el mejor
-regresa el mejor
BusquedaLocal
El algoritmo lo primero que realiza es generar la solución inicial, lo cual le cuesta O(nm). Luego ejecuta modifica y búsqueda hasta encontrar una mejor solución. Dado que el bucle se ejecuta si hay una mejora en la soluci ́n, y que ́sta no puede tener mas de n nodos, el caso en donde más veces iterará será cuando la otra solución arroje un resultado de longitud n y en cada iteración se disminuya la respuesta en uno, hasta alcanzar el mínimo en un conjunto con un solo nodo. En éste caso se harían n iteraciones, por lo que la complejidad sería
O(nm + n(n⁴ m)) = O(n⁵ m).
# Instancia generada para 5 vértices con densidad .5
Cota inferior: 3.
Cota superior: 2.
0 0 2 factible
0 1 2 factible
0 2 2 factible
0 3 2 factible
0 4 2 factible
1 0 2 factible
1 1 2 factible
1 2 2 factible
1 3 2 factible
1 4 2 factible
2 0 2 factible
2 1 2 factible
2 2 2 factible
2 3 2 factible
2 4 2 factible
3 0 3 factible
3 1 3 factible
3 2 3 factible
3 3 3 factible
3 4 3 factible
4 0 3 factible
4 1 3 factible
4 2 3 factible
4 3 3 factible
4 4 3 factible
/**
Crea el conjunto de solucion inicial
lo mismo que el procedimiento de la cota inferior pero en lugar de ordenarlo
*/
public static ArrayList<integer> inicial(ArrayList<arista> grafo) { //lista de solucion inicial
ArrayList<integer> cubierta = new ArrayList<integer>();//lista de la cubierta (conjunto seleccionado como solucion inicial)
ArrayList<arista> copia = new ArrayList<arista>();//lista de aristas copia de la cubierta
//de nuevo recorre el grafo
Iterator<arista> it = grafo.iterator();
while (it.hasNext()) {
copia.add(it.next());//y lo agrega a la copia
}
//si el conjunto es mayor a 0
while (copia.size() > 0) {
int largo = copia.size();//se toma el largo del arreglo de aristas
//System.out.println("Faltan " + largo + " aristas por cubrir.");//el largo de las aristas
/**SELECCIONA*/
//selecciona un vertice al azar y lo toma en el conjunto seleccion
int seleccion = Arista.r.nextInt(largo);
//System.out.println(seleccion);
//de acuerdo a la posicion del elemento seleccionado verifica el arista
Arista a = copia.get(seleccion);
//cualquier vertice tenga este arista podra formar parte del conjunto de seleccion
if (Arista.r.nextBoolean()) {
seleccion = a.desde;
} else {
seleccion = a.hasta;
}
//crea la cubierta con los elementos seleccionados
cubierta.add(new Integer(seleccion));
it = grafo.iterator();
//lista de aristas eliminados
ArrayList<arista> eliminados = new ArrayList<arista>();
//agrega los eliminados tanto los vertices hasta y desde a la lista
while (it.hasNext()) {
a = it.next();
//si los aristas forman parte de la seleccion los agrega a la lista eliminados
if (a.desde == seleccion || a.hasta == seleccion) {
eliminados.add(a);
}
}
copia.removeAll(eliminados); //de la copia quita los eliminados
}
return cubierta;//regresa la cubierta seleccionada como solucion inicial
}
public static boolean factible(ArrayList<integer> solucion, ArrayList<arista> grafo) {
Iterator<arista> it = grafo.iterator();//recorre la lista de aristas del grafo
while (it.hasNext()) {
Arista a = it.next(); //
if (!(solucion.contains(new Integer(a.hasta)) || solucion.contains(new Integer(a.desde)))) {
//si la solucion no contiene(cubre) todas las aristas regresa un false no es factible
return false;
}
}
return true; //y si si pues si :D
}
/**Recibe una solucion inicial
Regresa el tamaño de la modificacion
*/
public static ArrayList<integer> modificacion(ArrayList<integer> solucion, int n, boolean fact)//recibe solucion inicial
{
ArrayList<integer> nueva = new ArrayList<integer>();//nueva es la copia de una solucion inicial
int k = solucion.size();// tamaño de esta
int brinca = (fact || k == n) ? Arista.r.nextInt(k) : -1;
//si es factible o es igual al total de vertices quita un elemento de forma aleatoria
for (int i = 0; i < k; i++) {
if (i != brinca) {
nueva.add(solucion.get(i));//agrega un nuevo vertice a la solucion
}
}
if (!fact && k < n) {//si no es factible y el tamaño de la solucion inicial es menor
while (true) {
Integer agrega = new Integer(Arista.r.nextInt(n));//agrega
if (nueva.indexOf(agrega) < 0) {
nueva.add(agrega);
break;
}
}
}
return nueva;//regresa la nueva
}
//busqueda
public static ArrayList<Integer> busqueda(ArrayList<arista> grafo, int n) {
ArrayList<integer> mejorSol = null;
//define la mejor solucion como nula para que cualquiera pueda superarla
int mejorObj = n;//tamaño de la cubierta inicial seria el total de nodos en el grafo idem
for (int reinicio = 0; reinicio < 5; reinicio++) {//pasos de reinicio
ArrayList<Integer> solucion = Arista.inicial(grafo);//solucion inicial
//Arista.imprime(solucion);
int obj = Arista.objetivo(solucion);//objetivo de la solucion
for (int iter = 0; iter < 5; 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 en otrasolucion
boolean otraFact = Arista.factible(otrasolucion, grafo);
//verifica que sea factible
int otraObj = Arista.objetivo(otrasolucion);//define su tamanio
if (otraFact && otraObj <= obj) {//si es mejor que la anterior
solucion = otrasolucion;//se toma esa solucion
obj = otraObj;//ese objetivo
fact = otraFact;//la factibilidad
if (obj < mejorObj) {//y se convierte en la mejor
mejorObj = obj;//:3
mejorSol = new ArrayList<Integer>();
Iterator<integer> it = solucion.iterator();
while (it.hasNext()) {
mejorSol.add(it.next());
}
}
}
System.out.println(reinicio + " " +iter + " " + obj + " " + (fact ? "factible" : "no factible")) ;
}
}
return mejorSol;//devuelve la mejor solucion
}
Referencias
Informe Algoritmos 2007
