En satisfacción de restricciones , la búsqueda local es un método incompleto para encontrar una solución a un problema . Se basa en mejorar iterativamente una asignación de las variables hasta que se satisfagan todas las restricciones. En particular, los algoritmos de búsqueda local normalmente modifican el valor de una variable en una asignación en cada paso. La nueva asignación se acerca a la anterior en el espacio de asignación, de ahí el nombre de búsqueda local .
Todos los algoritmos de búsqueda local utilizan una función que evalúa la calidad de la asignación, por ejemplo, el número de restricciones violadas por la asignación. Esta cantidad se llama costo de la asignación. El objetivo de la búsqueda local es encontrar una asignación de costo mínimo, que es una solución si existe.
Existen dos clases de algoritmos de búsqueda local. El primero es el de los algoritmos codiciosos o no aleatorios. Estos algoritmos proceden cambiando la asignación actual tratando siempre de disminuir (o al menos, no aumentar) su costo. El principal problema de estos algoritmos es la posible presencia de mesetas , que son regiones del espacio de asignaciones donde ningún movimiento local disminuye el costo. La segunda clase de algoritmo de búsqueda local se ha inventado para resolver este problema. Escapan de estas mesetas haciendo movimientos aleatorios y se denominan algoritmos de búsqueda local aleatorios.
Algoritmos codiciosos
Montañismo
La forma más básica de búsqueda local se basa en elegir el cambio que reduzca al máximo el costo de la solución. Este método, llamado escalada de colinas , procede de la siguiente manera: primero, se elige una asignación aleatoria; luego, se cambia un valor para mejorar al máximo la calidad de la asignación resultante. Si no se ha encontrado una solución después de un número determinado de cambios, se selecciona una nueva asignación aleatoria. Los algoritmos de escalada de colinas solo pueden escapar de una meseta haciendo cambios que no cambien la calidad de la tarea. Como resultado, pueden quedarse estancados en una meseta donde la calidad de la asignación tiene un máximo local.
GSAT (codicioso sat) fue el primer algoritmo de búsqueda local de satisfacibilidad y es una forma de escalar colinas.
Método de ruptura o ponderación de restricciones
Un método para escapar de un mínimo local es el de usar una suma ponderada de restricciones violadas como una medida de costo y cambiar algunas ponderaciones cuando no se dispone de un movimiento de mejora. Más precisamente, si ningún cambio reduce el costo de la asignación, el algoritmo aumenta el peso de las restricciones violadas por la asignación actual.
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 permanecen violadas durante una gran cantidad de movimientos sigue aumentando. Por lo tanto, durante una serie de movimientos que no satisfacen una restricción, el costo de los movimientos a las asignaciones que satisfacen esa restricción sigue aumentando.
Búsqueda tabú
Un inconveniente de escalar colinas con movimientos que no reducen el costo es que puede pasar de asignaciones 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 solo los cambios más recientes. Más precisamente, contiene el último par variable-valor de manera que la variable se haya asignado 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 esta forma, la lista solo 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 solo 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ú.
Caminata aleatoria
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 asignación. Con probabilidadsin embargo, la solución se cambia de alguna otra manera, lo que implica cierto grado de aleatoriedad.
WalkSAT
El movimiento aleatorio de WalkSAT está cambiando el valor de una variable aleatoria de una restricción violada aleatoriamente. Para la satisfacibilidad proposicional de fórmulas conjuntivas de forma normal , 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. Al igual que con todas las estrategias de caminata aleatoria, un movimiento aleatorio solo se realiza con una probabilidad dada, y un movimiento que reduce al máximo el costo se realiza de otra manera.
Recocido simulado
La técnica de recocido simulado se basa en cambiar la probabilidad de hacer un movimiento aleatorio sobre uno que reduzca al máximo el costo. En particular, el nombre se origina en la estrategia de disminuir la probabilidad de realizar movimientos aleatorios durante la ejecución del algoritmo, por lo que virtualmente "congela" el espacio de búsqueda.
En particular, si la mejora del costo de un movimiento es negativo (el movimiento aumenta el costo), este movimiento se realiza con probabilidad , dónde es un número real. Dado que la probabilidad de hacer 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.
Búsqueda local en un corte de bicicleta
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 en un ciclo de corte , que es un conjunto de variables que, si se eliminan del problema, lo vuelven acíclico.
Para cualquier asignación de las variables del conjunto de corte, el problema restante tiene un bosque como gráfico principal. 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 se pueden violar en lugar de un algoritmo de satisfacibilidad en la parte del problema del bosque.
Este número mínimo se encuentra determinando el costo de cada asignación de variable. Este costo es el número mínimo de restricciones violadas por una asignación de las variables en el subárbol enraizado 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 asignación y son los hijos de , se cumple la siguiente fórmula. En esta fórmula, es el 0 o el 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 estas variables pueden tomar solo su valor dado. Con estos supuestos, la fórmula anterior permite calcular el costo de todas las evaluaciones de variables procediendo iterativamente de abajo hacia arriba desde las hojas hasta la (s) raíz (s) del bosque.
El costo de las evaluaciones de variables se puede utilizar mediante una 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.
enlaces externos
Referencias
- ^ Glover, Fred (enero de 1986). "Caminos futuros para la programación de enteros y enlaces a la inteligencia artificial" . Investigación de Computación y Operaciones . 13 (5): 533–549. doi : 10.1016 / 0305-0548 (86) 90048-1 .
- ^ Glover, Fred (agosto de 1989). "Búsqueda tabú - Parte I" . Revista ORSA de Computación . 1 (3): 190–206. doi : 10.1287 / ijoc.1.3.190 . ISSN 0899-1499 .
- ^ Glover, Fred (febrero de 1990). "Tabu Search — Part II" . Revista ORSA de Computación . 2 (1): 4–32. doi : 10.1287 / ijoc.2.1.4 . ISSN 0899-1499 .
- Dechter, Rina (2003). Procesamiento de restricciones . Morgan Kaufmann. ISBN 978-1-55860-890-0.