In constraint satisfaction, local search is an incomplete method for finding a solution to a problem. It is based on iteratively improving an assignment of the variables until all constraints are satisfied. In particular, local search algorithms typically modify the value of a variable in an assignment at each step. The new assignment is close to the previous one in the space of assignment, hence the name local search.
All local search algorithms use a function that evaluates the quality of assignment, for example the number of constraints violated by the assignment. This amount is called the cost of the assignment. The aim of local search is that of finding an assignment of minimal cost, which is a solution if any exists.
Two classes of local search algorithms exist. The first one is that of greedy or non-randomized algorithms. These algorithms proceed by changing the current assignment by always trying to decrease (or at least, non-increase) its cost. The main problem of these algorithms is the possible presence of plateaus, which are regions of the space of assignments where no local move decreases cost. The second class of local search algorithm have been invented to solve this problem. They escape these plateaus by doing random moves, and are called randomized local search algorithms.
The most basic form of local search is based on choosing the change that maximally decreases the cost of the solution. This method, called hill climbing, proceeds as follows: first, a random assignment is chosen; then, a value is changed so as to maximally improve the quality of the resulting assignment. If no solution has been found after a given number of changes, a new random assignment is selected. Hill climbing algorithms can only escape a plateau by doing changes that do not change the quality of the assignment. As a result, they can be stuck in a plateau where the quality of assignment has a local maxima.
GSAT (greedy sat) was the first local search algorithm for satisfiability, and is a form of hill climbing.
A method for escaping from a local minimum is that of using a weighted sum of violated constraints as a measure of cost, and changing some weights when no improving move is available. More precisely, if no change reduces the cost of the assignment, the algorithm increases the weight of constraints violated by the current assignment.
De esta manera, cada movimiento que de otra manera no cambiaría el costo de la solución lo disminuye. Además, el peso de las restricciones que siguen siendo violadas durante un gran número de movimientos sigue aumentando. Por lo tanto, durante una serie de movimientos que no satisfacen una restricción, el costo de los movimientos hacia asignaciones que satisfacen esa restricción sigue aumentando.
Una desventaja de escalar colinas con movimientos que no reducen el costo es que puede recorrer tareas del mismo costo. La búsqueda tabú [1] [2] [3] supera este problema manteniendo una lista de asignaciones "prohibidas", llamada lista tabú . En particular, la lista tabú normalmente contiene sólo los cambios más recientes. Más precisamente, contiene el último par variable-valor de modo que la variable haya sido asignada recientemente al valor.
Esta lista se actualiza cada vez que se cambia la asignación. Si se asigna una variable a un valor, el par variable-valor se agrega a la lista y el par más antiguo se elimina de ella. De esta manera, la lista sólo contiene las asignaciones más recientes a una variable. Si un par variable-valor está en la lista tabú, entonces está prohibido cambiar la asignación actual estableciendo la variable en el valor. El algoritmo sólo puede elegir el mejor movimiento entre los que no están prohibidos. De esta manera, no puede recorrer la misma solución a menos que el número de movimientos en este ciclo sea mayor que la longitud de la lista tabú.
Un algoritmo de paseo aleatorio a veces se mueve como un algoritmo codicioso pero a veces se mueve de forma aleatoria. Depende de un parámetro , que es un número real entre 0 y 1. En cada movimiento, con probabilidad el algoritmo procede como un algoritmo codicioso, tratando de disminuir al máximo el costo de la tarea. Sin embargo, con la probabilidad , la solución cambia de alguna otra manera, lo que implica cierto grado de aleatoriedad.
El movimiento aleatorio de WalkSAT cambia el valor de una variable aleatoria de una restricción aleatoria violada. Para la satisfacibilidad proposicional de fórmulas de forma normal conjuntiva , que es la configuración original de este algoritmo, cada movimiento de este tipo cambia el valor de la variable de verdadero a falso o viceversa, y produce la satisfacibilidad de la restricción violada. Como ocurre con todas las estrategias de paseo aleatorio, un movimiento aleatorio solo se realiza con una probabilidad determinada y, de lo contrario, se realiza un movimiento que reduce al máximo el costo.
La técnica de recocido simulado se basa en cambiar la probabilidad de realizar un movimiento aleatorio por uno que reduzca al máximo el costo. En particular, el nombre proviene de la estrategia de disminuir la probabilidad de realizar movimientos aleatorios durante la ejecución del algoritmo, "congelando" virtualmente el espacio de búsqueda.
En particular, si la mejora del costo de un movimiento es negativa (el movimiento aumenta el costo), este movimiento se realiza con probabilidad , donde es un número real. Dado que la probabilidad de realizar este movimiento aumenta con , este parámetro se llama temperatura . El recocido simulado disminuye esta temperatura con el tiempo, lo que permite más movimientos aleatorios al principio y menos después del tiempo.
La búsqueda local suele funcionar en todas las variables, mejorando una asignación completa a ellas. Sin embargo, la búsqueda local también se puede ejecutar en un subconjunto de variables, utilizando algún otro mecanismo para las otras variables. Un algoritmo propuesto funciona con un conjunto de corte de ciclo , que es un conjunto de variables que, si se eliminan del problema, lo convierten en acíclico.
Para cualquier asignación de las variables del cutset, el problema restante tiene un bosque como gráfico primario. Como resultado, se puede resolver de manera eficiente. Para guiar la búsqueda local, se utiliza un algoritmo que detecta el número mínimo de restricciones que pueden violarse en lugar de un algoritmo de satisfacibilidad en la parte del problema para el bosque.
Este número mínimo se encuentra determinando el costo de cada asignación variable. Este costo es el número mínimo de restricciones violadas por una asignación de variables en el subárbol con raíz en la variable, cuando la variable toma el valor dado. Este costo se puede calcular de la siguiente manera. Si denota el costo de la tarea y son hijos de , se cumple la siguiente fórmula. En esta fórmula, es 0 o 1 dependiendo de si la asignación viola la restricción entre y .
El costo de las variables en el conjunto de corte es cero y se supone que a estas variables se les permite tomar solo su valor dado. Con estos supuestos, la fórmula anterior permite calcular el costo de todas las evaluaciones variables procediendo iterativamente de abajo hacia arriba desde las hojas hasta las raíces del bosque.
El costo de las evaluaciones variables se puede utilizar mediante búsqueda local para calcular el costo de una solución. El costo de los valores de las raíces del bosque es de hecho el número mínimo de restricciones violadas en el bosque para estos valores dados. Por lo tanto, estos costos pueden usarse para evaluar el costo de la asignación a las variables de corte y para estimar el costo de asignaciones similares en las variables de corte.
