Resumen

Los problemas de satisfacción de restricciones son de especial interés para la comunidad de inteligencia artificial e investigación de operaciones debido a sus numerosas aplicaciones. Aunque las heurísticas implicadas en la resolución de estos problemas han sido ampliamente estudiadas en el pasado, se sabe poco sobre la relación entre las instancias y el rendimiento respectivo de las heurísticas utilizadas para resolverlas. Este documento se centra tanto en la exploración del espacio de instancias para identificar las relaciones entre las instancias y las heurísticas de buen rendimiento como en la forma de utilizar dichas relaciones para mejorar la búsqueda. En primer lugar, el documento describe una metodología para explorar el espacio de instancias de los problemas de satisfacción de restricciones y evaluar el rendimiento correspondiente de seis heurísticas de ordenación de variables para dichas instancias con el fin de encontrar regiones en el espacio de instancias en las que algunas heurísticas superan a las demás. El análisis de dichas regiones favorece la comprensión de cómo funcionan estas heurísticas y contribuye a su mejora. En segundo lugar, utilizamos la información recopilada en la primera etapa para predecir la heurística más adecuada en función de las características de la instancia que se está resolviendo. Este enfoque demostró ser competitivo cuando se comparó con las heurísticas aplicadas de forma aislada tanto en instancias generadas aleatoriamente como en instancias estructuradas de problemas de satisfacción de restricciones.

• Materias:Inteligencia artificial Minería de datos Algoritmos genéticos Cerebro - fisiopatología Neurociencia Cognitiva
• Subjects:Artificial intelligence Data mining Genetic algorithms Brain - pathophysiology Cognitive Neuroscience
• Palabras claves:problema de satisfacción de restricciones, espacio de instancia, heurística, relaciones, heurística de ordenación de variables, instancia, comunidad de investigación de operaciones, instancia de restricciones, espacio de restricciones, muchas aplicaciones
• Keywords:constraints satisfaction problem, instance space, heuristic, relations, variable ordering heuristic, instance, operations research community, instance of constraints, space of constraints, many application