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

Hdl Handle:
http://hdl.handle.net/11285/572177
Title:
Heurísticas con Algoritmos Genéticos para Ordenamiento Dinámico de Variables en Problemas de Satisfacción de Restricciones
Issue Date:
01/09/2004
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.
Keywords:
Heurísticas; Algoritmos Genéticos; Ordenamientos Dinámicos; Satisfacción de Restricciones; Ciencias Computacionales
Advisors:
Dr. Hugo Terashima Marín
Committee Member / Sinodal:
Dr. Eduardo Uresti Charre; Dra. Olivia M. Barrón Cano
Degree Level:
Maestro en Ciencias en Sistemas Inteligentes
School:
Electrónica, Computación, Información y Comunicaciones
Campus Program:
Campus Monterrey
Discipline:
Ingeniería y Ciencias Aplicadas / Engineering & Applied Sciences
Appears in Collections:
Ciencias Exactas

Full metadata record

DC FieldValue Language
dc.contributor.advisorDr. Hugo Terashima Marínes
dc.creatorDe la Calleja Manzanedo, Renéen
dc.date.accessioned2015-08-17T11:22:56Zen
dc.date.available2015-08-17T11:22:56Zen
dc.date.issued01/09/2004-
dc.identifier.urihttp://hdl.handle.net/11285/572177en
dc.description.abstractLos 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.es
dc.language.isoes-
dc.rightsOpen Accessen
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.titleHeurísticas con Algoritmos Genéticos para Ordenamiento Dinámico de Variables en Problemas de Satisfacción de Restriccioneses
dc.typeTesis de Maestríaes
dc.contributor.departmentITESMen
thesis.degree.grantorInstituto Tecnológico y de Estudios Superiores de Monterreyes
thesis.degree.levelMaestro en Ciencias en Sistemas Inteligenteses
dc.contributor.committeememberDr. Eduardo Uresti Charrees
dc.contributor.committeememberDra. Olivia M. Barrón Canoes
thesis.degree.disciplineElectrónica, Computación, Información y Comunicacioneses
dc.subject.keywordHeurísticases
dc.subject.keywordAlgoritmos Genéticoses
dc.subject.keywordOrdenamientos Dinámicoses
dc.subject.keywordSatisfacción de Restriccioneses
dc.subject.keywordCiencias Computacionaleses
thesis.degree.programCampus Monterreyes
dc.subject.disciplineIngeniería y Ciencias Aplicadas / Engineering & Applied Sciencesen
All Items in REPOSITORIO DEL TECNOLOGICO DE MONTERREY are protected by copyright, with all rights reserved, unless otherwise indicated.