Optimización Genética de Problemas SAT

Hdl Handle:
http://hdl.handle.net/11285/572187
Title:
Optimización Genética de Problemas SAT
Authors:
Rodríguez Tello, Eduardo A.
Issue Date:
01/11/1999
Abstract:
El 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.
Keywords:
Satisfactibilidad; SAT; Algoritmos de Satisfacción; PMABG; Ciencias Computacionales
Degree Program:
Maestría en Ciencias de la Computación
Advisors:
Dr. José Torres Jiménez
Committee Member / Sinodal:
Dr. Eduardo Morales Manzanares; Dr. Juan Frausto Solís
Degree Level:
Maestro en Ciencias de la Computación
School:
Ingeniería y Ciencias
Campus Program:
Campus Morelos
Discipline:
Ingeniería y Ciencias Aplicadas / Engineering & Applied Sciences
Appears in Collections:
Ciencias Exactas

Full metadata record

DC FieldValue Language
dc.contributor.advisorDr. José Torres Jiménezes
dc.contributor.authorRodríguez Tello, Eduardo A.en
dc.date.accessioned2015-08-17T11:23:09Zen
dc.date.available2015-08-17T11:23:09Zen
dc.date.issued01/11/1999-
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.es
dc.language.isoes-
dc.rightsOpen Accessen
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.titleOptimización Genética de Problemas SATes
dc.typeTesis de Maestríaes
dc.contributor.departmentITESMen
thesis.degree.grantorInstituto Tecnológico y de Estudios Superiores de Monterreyes
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
All Items in REPOSITORIO DEL TECNOLOGICO DE MONTERREY are protected by copyright, with all rights reserved, unless otherwise indicated.