Hiperheurísticas mediante un enfoque evolutivo para el ordenamiento dinámico de variables en problemas de satisfacción de restricciones

Los problemas de satisfacción de restricciones (CSPs por sus siglas en inglés) representan un tema de gran interés en el área de sistemas inteligentes y sus aplicaciones incluyen planeación, visión, distribución de recursos, etc. Un CSP está compuesto por un conjunto de variables, un dominio de valores para cada variable y un conjunto de restricciones definidas sobre los valores que pueden tomar las variables simultáneamente. Asociado a los CSPs se encuentra el problema del ordenamiento de variables y de valores. Un buen ordenamiento de variables al momento de buscar una solución representa una menor complejidad en la búsqueda. Existen una gran cantidad de heurísticas que se han diseñado para seleccionar dinámicamente la siguiente variable a instanciar, pero ninguna de ellas ha demostrado ser eficiente para todas las instancias. Además, existen instancias de CSPs que son particularmente difíciles de resolver, ya que requieren una elevada cantidad de verificaciones de consistencia para encontrar una solución o demostrar que no existe alguna. Este trabajo considera el problema del ordenamiento dinámico de variables en CSPs utilizando hiperheurísticas producidas mediante un modelo evolutivo. Este modelo se compone de una etapa de entrenamiento y una de prueba. La etapa de entrenamiento se realiza con ayuda de un algoritmo genético con cromosomas de longitud variable. Durante la etapa de entrenamiento, el AG se encarga de evolucionar una población de individuos que representan las hiperheurísticas mediante la solución de un conjunto de entrenamiento formado por diferentes instancias de CSPs difíciles. La intención de utilizar diferentes instancias de CSPs durante la etapa de entrenamiento es desarrollar procesos de solución generales que puedan ser aplicados para resolver un gran número de instancias, más que encontrar buenas soluciones para instancias específicas. Estos individuos de la población representan grupos de reglas del tipo condición-acción, en donde la condición simboliza un estado específico del problema y la acción es una heurística de ordenamiento de variables. En términos generales, el procedimiento que se lleva a cabo es el siguiente: dado un estado P del problema, encontrar la regla más cercana i y aplicar la heurística asociada a dicha regla. Al llevar a cabo esta acción, el problema se transforma en P1 . El procedimiento se repite hasta resolver el problema completamente. La función primordial del AG durante la etapa de entrenamiento es seleccionar diferentes estados del problema y asociar cada uno de ellos con alguna de las heurísticas de bajo nivel para el ordenamiento dinámico de variables. Una misma heurística puede asociarse a varios estados o a ninguno. Al finalizar la etapa de entrenamiento, el mejor individuo de la población es utilizado para resolver el conjunto de problemas de prueba, el cual está formados por diferentes instancias de CSPs de las que fueron utilizadas durante el proceso de entrenamiento. Las hiperheurísticas generadas mediante el modelo presentado en este trabajo se comparan con los resultados obtenidos mediante la aplicación por separado de las heurísticas de bajo nivel para los problemas de entrenamiento y prueba. La investigación demuestra que es posible generar hiperheurísticas con eficiencia competitiva para una gran cantidad de instancias de CSPs mediante el modelo evolutivo presentado. Los resultados también dejan en claro que no existe una heurística capaz por sí sola de resolver eficientemente todas las instancias de CSPs. Sin embargo, el modelo evolutivo fue capaz de generar una hiperheurística general competitiva, la cual logró resultados muy parecidos a los producidos por el mejor resultado de las heurísticas simples y una reducción significativa al compararse contra el número de verificaciones de consistencia requerido por el resultado promedio de las heurísticas simples.