En informática , el algoritmo de conflictos mínimos es un algoritmo de búsqueda o método heurístico para resolver problemas de satisfacción de restricciones .
Dada una asignación inicial de valores a todas las variables de un problema de satisfacción de restricciones, el algoritmo selecciona aleatoriamente una variable del conjunto de variables con conflictos que violan una o más de sus restricciones. [1] Luego asigna a esta variable el valor que minimiza el número de conflictos. Si hay más de un valor con un número mínimo de conflictos, elige uno al azar. Este proceso de selección de variables aleatorias y asignación de valores de conflicto mínimo se repite hasta que se encuentra una solución o se alcanza un número máximo de iteraciones preseleccionado.
Debido a que un problema de satisfacción de restricciones se puede interpretar como un problema de búsqueda local cuando todas las variables tienen un valor asignado (llamado estado completo), el algoritmo de conflictos mínimos puede verse como una heurística de reparación [2] que elige el estado con el número mínimo de conflictos.
Algoritmo
El algoritmo MIN-CONFLICTS es de entrada: csp , Un problema de satisfacción de restricciones. max_steps , la cantidad de pasos permitidos antes de darse por vencido. current_state , una asignación inicial de valores para las variables en el csp. salida: Un conjunto de valores de solución para la variable o falla . para i ← 1 a max_steps hacer si current_state es una solución de csp entonces devuelve current_state set var ← una variable elegida aleatoriamente del conjunto de variables en conflicto CONFLICTED [ csp ] set value ← el valor v para var que minimiza CONFLICTS ( var , v , current_state , csp ) establece var ← valor en current_state falla de retorno
Aunque no se especifica en el algoritmo, una buena asignación inicial puede ser fundamental para abordar rápidamente una solución. Utilice un algoritmo codicioso con cierto nivel de aleatoriedad y permita que la asignación de variables rompa las restricciones cuando ninguna otra asignación sea suficiente. La aleatoriedad ayuda a que los conflictos mínimos eviten los mínimos locales creados por la asignación inicial del algoritmo codicioso. De hecho, los problemas de satisfacción de restricciones que responden mejor a una solución de conflictos mínimos funcionan bien cuando un algoritmo codicioso casi resuelve el problema. Los problemas de coloración de mapas funcionan mal con el algoritmo codicioso y los conflictos mínimos. Las subáreas del mapa tienden a mantener estables sus colores y los conflictos mínimos no pueden escalar colinas para romper el mínimo local. La función CONFLICTS cuenta el número de restricciones violadas por un objeto en particular, dado que se conoce el estado del resto de la asignación.
Historia
Aunque la inteligencia artificial y la optimización discreta conocían y razonaban sobre los problemas de satisfacción de restricciones durante muchos años, no fue hasta principios de la década de 1990 que este proceso para resolver grandes CSP se codificó en forma algorítmica. Al principio, Mark Johnston, del Instituto de Ciencias del Telescopio Espacial, buscó un método para programar observaciones astronómicas en el Telescopio Espacial Hubble . En colaboración con Hans-Martin Adorf de la Instalación de Coordinación Europea del Telescopio Espacial , creó una red neuronal capaz de resolver un problema de juguete n- reinas (para 1024 reinas). [3] [4] Steven Minton y Andy Philips analizaron el algoritmo de la red neuronal y lo separaron en dos fases: (1) una asignación inicial usando un algoritmo codicioso y (2) una fase de minimización de conflictos (que luego se llamará "min-conflictos "). Se redactó y presentó un artículo en AAAI-90; Philip Laird proporcionó el análisis matemático del algoritmo.
Posteriormente, Mark Johnston y el personal de STScI utilizaron conflictos mínimos para programar el tiempo de observación de los astrónomos en el Telescopio Espacial Hubble.
Ejemplo
Min-Conflicts resuelve el problema de las N- Reinas seleccionando al azar una columna del tablero de ajedrez para la reasignación de reina. El algoritmo busca en cada movimiento potencial el número de conflictos (número de reinas atacantes), que se muestra en cada cuadro. El algoritmo mueve a la reina a la casilla con el mínimo de conflictos, rompiendo los empates de forma aleatoria. Tenga en cuenta que la cantidad de conflictos se genera por cada nueva dirección desde la que una reina puede atacar. Si dos reinas atacan desde la misma dirección (fila o diagonal), el conflicto solo se cuenta una vez. También tenga en cuenta que si una reina está en una posición en la que un movimiento la pondría en mayor conflicto que su posición actual, no realiza ningún movimiento. De ello se deduce que si una reina se encuentra en un estado de conflicto mínimo, no tiene que moverse.
El tiempo de ejecución de este algoritmo para resolver N -Queens es independiente del tamaño del problema. Este algoritmo incluso resolverá el problema del millón de reinas en un promedio de 50 pasos. Este descubrimiento y observaciones llevaron a una gran cantidad de investigación en 1990 y comenzaron a investigar los problemas de búsqueda local y las distinciones entre problemas fáciles y difíciles. N -Queens es fácil para la búsqueda local porque las soluciones están distribuidas densamente en todo el espacio estatal. También es eficaz para problemas difíciles. Por ejemplo, se ha utilizado para programar observaciones para el telescopio espacial Hubble , reduciendo el tiempo necesario para programar una semana de observaciones de tres semanas a alrededor de 10 minutos. [5]
Ver también
Referencias
- ^ Minton, Steven; Mark D. Johnston; Andrew B. Philips; Philip Laird (1990). "Resolución de problemas de programación y satisfacción de restricciones a gran escala mediante un método de reparación heurística" (PDF) . Octava Conferencia Nacional sobre Inteligencia Artificial (AAAI-90), Boston, Massachusetts : 17-24 . Consultado el 27 de marzo de 2013 .
- ^ Minton, Steven; Mark D. Johnston; Andrew B. Philips; Philip Laird (1992). "Minimización de conflictos: un método de reparación heurístico para la satisfacción de restricciones y problemas de programación" (PDF) . Inteligencia artificial . 58 (1): 161-205. CiteSeerX 10.1.1.308.6637 . doi : 10.1016 / 0004-3702 (92) 90007-k . Consultado el 27 de marzo de 2013 .
- ^ Johnston, MD; Adorf, H.-M. (1989). "Aprendizaje en redes neuronales estocásticas para problemas de satisfacción de restricciones". NASA Conf. On Space Telerobotics 1989, Pasadena, CA; G. Rodríguez, H. Seraji (Eds.) : 367–376 vol.II.
- ^ Adorf, H.-M .; Johnston, MD (1990). "Un algoritmo de red neuronal estocástica discreta para problemas de satisfacción de restricciones". 1990 Conferencia conjunta internacional IJCNN sobre redes neuronales : 917–924 vol.3. doi : 10.1109 / IJCNN.1990.137951 .
- ^ Stuart Russell, Peter Norvig, "Inteligencia artificial: un enfoque moderno (tercera edición)", págs. 220-222, 11 de diciembre de 2009.
- Stuart J. Russell y Peter Norvig , Inteligencia artificial: un enfoque moderno
enlaces externos
- [1] La microforma heurística de min-conflictos: experimento y resultados teóricos / Steven Minton ... [et al.]. NASA, Centro de Investigación Ames, Subdivisión de Investigación en Inteligencia Artificial. Distribuido a bibliotecas depositarias en microfichas.