Show simple item record

dc.contributor.advisorDr. José Torres Jiménezes
dc.creatorRodríguez Tello, Eduardo A.en
dc.date.accessioned2015-08-17T11:23:09Zen
dc.date.available2015-08-17T11:23:09Zen
dc.date.issued1999-01-11
dc.identifier.urihttp://hdl.handle.net/11285/572187en
dc.description.abstractEl problema de satisfactibilidad (SAT) tiene relevancia desde un contexto teórico y práctico. En el contexto teórico el problema SAT es fundamental para el análisis de la complejidad computacional de diversos problemas. En el contexto práctico, la solución de problemas SAT es requisito fundamental de diversos métodos de razonamiento. De esta manera el encontrar un procedimiento eficiente para resolver el problema SAT es muy importante. En esta tesis se plantea un enfoque novedoso para resolver problemas SAT usando algoritmos genéticos (AG), el algoritmo está basado en el reordenamiento de las variables que intervienen en las cláusulas del problema SAT, y la aplicación posterior de un AG tradicional. Los resultados presentados en este trabajo evidencian que el enfoque propuesto es consistentemente mejor que un AG tradicional para resolver problemas SAT duros. Por otra parte, las principales aportaciones de esta tesis son: � La implementación de un algoritmo de Recocido Simulado que permite resolver el Problema de Minimización del Ancho de Banda de Grafos (PMABG) de manera competitiva. � El uso de una métrica especial para el PMABG (7) que es substancialmente mejor que la medida empleada comÚnmente (B), y además permite bandear grafos pesados. � Lograr identificar las características que debe cumplir un buen generador de casos de prueba para problemas SAT. Estas son: garantizar el control del grado de repetibilidad de las variables que intervienen en el problema; proveer un mecanismo que garantice el balance entre las apariciones positivas y negativas de cada variable del problema; evitar generar cláusulas triviales, así como cuidar que la razón entre cláusulas y variables sea aproximadamente entre 2 y 4. � Un enfoque novedoso para generar casos de prueba duros del problema SAT a partir de su analogía geométrica con grafos.
dc.languagespa
dc.publisherInstituto Tecnológico y de Estudios Superiores de Monterrey
dc.rightsinfo:eu-repo/semantics/openAccess
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0*
dc.titleOptimización Genética de Problemas SATes
dc.typeTesis de maestría
dc.contributor.departmentITESMen
thesis.degree.levelMaestro en Ciencias de la Computaciónes
dc.contributor.committeememberDr. Eduardo Morales Manzanareses
dc.contributor.committeememberDr. Juan Frausto Solíses
thesis.degree.disciplineIngeniería y Cienciases
thesis.degree.nameMaestría en Ciencias de la Computaciónes
dc.subject.keywordSatisfactibilidades
dc.subject.keywordSATes
dc.subject.keywordAlgoritmos de Satisfacciónes
dc.subject.keywordPMABGes
dc.subject.keywordCiencias Computacionaleses
thesis.degree.programCampus Moreloses
dc.subject.disciplineIngeniería y Ciencias Aplicadas / Engineering & Applied Sciencesen
refterms.dateFOA2018-03-24T09:30:14Z
refterms.dateFOA2018-03-24T09:30:14Z
html.description.abstractEl problema de satisfactibilidad (SAT) tiene relevancia desde un contexto teórico y práctico. En el contexto teórico el problema SAT es fundamental para el análisis de la complejidad computacional de diversos problemas. En el contexto práctico, la solución de problemas SAT es requisito fundamental de diversos métodos de razonamiento. De esta manera el encontrar un procedimiento eficiente para resolver el problema SAT es muy importante. En esta tesis se plantea un enfoque novedoso para resolver problemas SAT usando algoritmos genéticos (AG), el algoritmo está basado en el reordenamiento de las variables que intervienen en las cláusulas del problema SAT, y la aplicación posterior de un AG tradicional. Los resultados presentados en este trabajo evidencian que el enfoque propuesto es consistentemente mejor que un AG tradicional para resolver problemas SAT duros. Por otra parte, las principales aportaciones de esta tesis son: � La implementación de un algoritmo de Recocido Simulado que permite resolver el Problema de Minimización del Ancho de Banda de Grafos (PMABG) de manera competitiva. � El uso de una métrica especial para el PMABG (7) que es substancialmente mejor que la medida empleada comÚnmente (B), y además permite bandear grafos pesados. � Lograr identificar las características que debe cumplir un buen generador de casos de prueba para problemas SAT. Estas son: garantizar el control del grado de repetibilidad de las variables que intervienen en el problema; proveer un mecanismo que garantice el balance entre las apariciones positivas y negativas de cada variable del problema; evitar generar cláusulas triviales, así como cuidar que la razón entre cláusulas y variables sea aproximadamente entre 2 y 4. � Un enfoque novedoso para generar casos de prueba duros del problema SAT a partir de su analogía geométrica con grafos.


Files in this item

Thumbnail
Name:
DocsTec_1879.pdf
Size:
4.294Mb
Format:
PDF
Thumbnail
Name:
DocsTec_1879_1.pdf
Size:
31.90Kb
Format:
PDF

This item appears in the following Collection(s)

Show simple item record

info:eu-repo/semantics/openAccess
Except where otherwise noted, this item's license is described as info:eu-repo/semantics/openAccess