Heurísticas con Algoritmos Genéticos para Ordenamiento Dinámico de Variables en Problemas de Satisfacción de Restricciones

Abstract

Los Problemas de Satisfacción de Restricciones (PSR o CSP por sus siglas en inglés) representan un tópico de gran interés dentro de la Inteligencia Artificial y surgen en muchas áreas de esta como lo son planeación, visión, distribución de recursos en itinerarios entre otros. Básicamente un CSP está compuesto por un conjunto de variables, un dominio de valores posibles para cada variable y un conjunto de restricciones definidas sobre los valores que pueden tomar las variables simultáneamente. En general, estos problemas son de tipo NP-completos y son dignos de ser estudiados dado que son problemas que cuentan con características Únicas las cuales pueden ser explotadas para llegar a una solución. Un nÚmero de enfoques diferentes han sido desarrollados para solucionar problemas de este tipo. En particular, cualquier técnica determinística de bÚsqueda de solución que sea escogida para atacar este problema, puede ver mejorada significativamente su eficiencia si es que se determina un buen orden de variables a instanciar, así como un buen orden de valores a asignar a estas variables. Numerosas técnicas, las cuales se basan en heurísticas de tipo ya sea estático o dinámico, han sido propuestas para solucionar estos Últimos problemas. En el presente trabajo se hace uso de los Algoritmos Genéticos, los cuales han demostrado ser lo suficientemente robustos para resolver una amplia variedad de problemas, para determinar este orden en las variables a instanciar de manera dinámica y acoplarlo a un algoritmo de bÚsqueda convencional. Se muestra en este trabajo que mediante este enfoque es posible obtener resultados suficientemente aceptables en la eficiencia del proceso de bÚsqueda por una solución. Asimismo, se analiza también bajo qué circunstancias este enfoque resulta más eficiente que algunas otras heurísticas propuestas en la literatura.