Mostrar el registro sencillo del ítem

dc.contributor.authorFarías Zárate, Claudia Janneth
dc.creatorFARIAS ZARATE, CLAUDIA JANNETH; 274175
dc.date.accessioned2015-08-17T09:37:00Zen
dc.date.available2015-08-17T09:37:00Zen
dc.date.issued2006-05-01
dc.identifier.urihttp://hdl.handle.net/11285/567426en
dc.description.abstractEl problema de corte de material se define principalmente como el corte de un conjunto de piezas pequeñas a partir de objetos de materia prima de mayor tamaño tratando de minimizar el desperdicio de material utilizando la menor cantidad de objetos. Debido a que el problema de corte de material posee una gran importancia tanto económica como ecológica en numerosas industrias como la de madera, vidrio, papel, cartón, textil, metal, entre otras, en los últimos años ha aumentado el interés en el desarrollo de diferentes técnicas de optimización que sean eficientes en la resolución de una gran variedad de problemas de corte de material. Desafortunadamente, debido a la naturaleza NP-difícil de los problemas de corte de material, resulta prácticamente imposible el solucionar instancias de gran tamaño mediante el uso de técnicas exactas, razón por la cual la mayoría de los algoritmos para solucionar este tipo de problemas están basados en el uso de heurísticas, las cuales no proporcionan resultados de buena calidad en la mayoría de los casos. Debido a la gran similitud entre los problemas de corte y de empacado, los métodos de solución empleados para éstos, pueden ser fácilmente aplicados también en problemas de carga de vehículos, calendarización de tareas en intervalos de tiempo definidos, entre otros. Esta tesis considera el problema de corte de material en dos dimensiones utilizando un método para el desarrollo de hiperheurísticas generales que solucionen diferentes instancias del problema de corte de material de forma eficiente, dicho método se compone de una etapa de entrenamiento y una de prueba, la etapa de entrenamiento es llevada a cabo por un Algoritmo Genético con cromosomas de longitud variable. Durante la etapa de entrenamiento, el Algoritmo Genético se encarga de evolucionar una población de individuos (hiperheurísticas), mediante la solución de un conjunto de problemas de entrenamiento formado por diferentes instancias del problema de corte de material. La finalidad de utilizar diferentes instancias del problema de corte durante la etapa de entrenamiento es desarrollar procesos de solución generales que puedan ser utilizados para resolver una gran variedad de instancias, en lugar de encontrar buenas soluciones para instancias específicas. Los 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 combinación de una heurística de selección (HS) y una de acomodo (HA). 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 las heurísticas asociadas a dicha regla HS(i) y HA(i); al llevar a cabo esta acción, el estado del problema se transforma de P a P0. Este procedimiento es repetido hasta resolver el problema completamente. La función primordial del algoritmo genético durante la etapa de entrenamiento es la de seleccionar diferentes estados del problema y asociar cada uno de ellos con alguna de las cuarenta acciones disponibles, las cuales se encuentran formadas por una heurística de selección y una de acomodo. Una acción determinada puede asociarse a varios estados o a ninguno. Al finalizar la etapa de entrenamiento, el mejor individuo es utilizado para resolver el grupo de problemas de prueba, el cual está formado por diferentes instancias del problema de corte de material que no fueron utilizadas durante el proceso de entrenamiento. La utilización del método propuesto para el desarrollo de hiperheurísticas generales obtuvo muy aceptables resultados para aproximadamente el 2.59% de las instancias resueltas se encontraron mejores resultados que los obtenidos por las heurísticas simples. Los resultados confirman la efectividad del método planteado para el desarrollo de hiperheurísticas generales que puedan resolver una gran variedad de instancias del problema de corte de material en dos dimensiones. Además, debido al grado de abstracción del método propuesto es posible extender su uso a otro tipo de problemas de optimización, lo cual implicaría un menor tiempo de desarrollo. De esta manera se prueba la validez de la hipótesis planteada.
dc.languagespa
dc.publisherInstituto Tecnológico y de Estudios Superiores de Monterrey
dc.relationInvestigadoreses_MX
dc.relationEstudianteses_MX
dc.relation.isFormatOfversión publicadaes_MX
dc.relation.isreferencedbyREPOSITORIO NACIONAL CONACYT
dc.rightsopenAccess
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0*
dc.subject.classificationArea::INGENIERÍA Y TECNOLOGÍA::CIENCIAS TECNOLÓGICAS::TECNOLOGÍA DE LOS ORDENADORES::LENGUAJES ALGORÍTMICOSes_MX
dc.titleHiperheurísticas mediante un algoritmo genético con cromosomas de longitud variable para resolver problemas de corte de material en dos dimensiones
dc.typeTesis de Maestría / master Thesis
dc.contributor.departmentITESM-Campus Monterreyen
dc.contributor.committeememberTerashima Marín, Hugoes
dc.contributor.committeememberValenzuela Rendón, Manueles
dc.contributor.committeememberUresti Charre, Eduardoes
refterms.dateFOA2018-03-06T14:13:45Z
refterms.dateFOA2018-03-06T14:13:45Z
html.description.abstractEl problema de corte de material se define principalmente como el corte de un conjunto de piezas pequeñas a partir de objetos de materia prima de mayor tamaño tratando de minimizar el desperdicio de material utilizando la menor cantidad de objetos. Debido a que el problema de corte de material posee una gran importancia tanto económica como ecológica en numerosas industrias como la de madera, vidrio, papel, cartón, textil, metal, entre otras, en los últimos años ha aumentado el interés en el desarrollo de diferentes técnicas de optimización que sean eficientes en la resolución de una gran variedad de problemas de corte de material. Desafortunadamente, debido a la naturaleza NP-difícil de los problemas de corte de material, resulta prácticamente imposible el solucionar instancias de gran tamaño mediante el uso de técnicas exactas, razón por la cual la mayoría de los algoritmos para solucionar este tipo de problemas están basados en el uso de heurísticas, las cuales no proporcionan resultados de buena calidad en la mayoría de los casos. Debido a la gran similitud entre los problemas de corte y de empacado, los métodos de solución empleados para éstos, pueden ser fácilmente aplicados también en problemas de carga de vehículos, calendarización de tareas en intervalos de tiempo definidos, entre otros. Esta tesis considera el problema de corte de material en dos dimensiones utilizando un método para el desarrollo de hiperheurísticas generales que solucionen diferentes instancias del problema de corte de material de forma eficiente, dicho método se compone de una etapa de entrenamiento y una de prueba, la etapa de entrenamiento es llevada a cabo por un Algoritmo Genético con cromosomas de longitud variable. Durante la etapa de entrenamiento, el Algoritmo Genético se encarga de evolucionar una población de individuos (hiperheurísticas), mediante la solución de un conjunto de problemas de entrenamiento formado por diferentes instancias del problema de corte de material. La finalidad de utilizar diferentes instancias del problema de corte durante la etapa de entrenamiento es desarrollar procesos de solución generales que puedan ser utilizados para resolver una gran variedad de instancias, en lugar de encontrar buenas soluciones para instancias específicas. Los 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 combinación de una heurística de selección (HS) y una de acomodo (HA). 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 las heurísticas asociadas a dicha regla HS(i) y HA(i); al llevar a cabo esta acción, el estado del problema se transforma de P a P0. Este procedimiento es repetido hasta resolver el problema completamente. La función primordial del algoritmo genético durante la etapa de entrenamiento es la de seleccionar diferentes estados del problema y asociar cada uno de ellos con alguna de las cuarenta acciones disponibles, las cuales se encuentran formadas por una heurística de selección y una de acomodo. Una acción determinada puede asociarse a varios estados o a ninguno. Al finalizar la etapa de entrenamiento, el mejor individuo es utilizado para resolver el grupo de problemas de prueba, el cual está formado por diferentes instancias del problema de corte de material que no fueron utilizadas durante el proceso de entrenamiento. La utilización del método propuesto para el desarrollo de hiperheurísticas generales obtuvo muy aceptables resultados para aproximadamente el 2.59% de las instancias resueltas se encontraron mejores resultados que los obtenidos por las heurísticas simples. Los resultados confirman la efectividad del método planteado para el desarrollo de hiperheurísticas generales que puedan resolver una gran variedad de instancias del problema de corte de material en dos dimensiones. Además, debido al grado de abstracción del método propuesto es posible extender su uso a otro tipo de problemas de optimización, lo cual implicaría un menor tiempo de desarrollo. De esta manera se prueba la validez de la hipótesis planteada.
dc.identificator7
dc.identificator33
dc.identificator3304
dc.identificator120302


Ficheros en el ítem

Thumbnail
Thumbnail

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem

openAccess
Excepto si se señala otra cosa, la licencia del ítem se describe como openAccess