An Evolutionary Framework for Producing Hyper-Heuristics for Solving the 2D Irregular Bin Packing Problem

Hdl Handle:
http://hdl.handle.net/11285/572577
Title:
An Evolutionary Framework for Producing Hyper-Heuristics for Solving the 2D Irregular Bin Packing Problem
Authors:
López Camacho, Eunice
Issue Date:
01/05/2012
Abstract:
This document presents a doctoral dissertation which is a requirement for the Ph.D. degree in Information Technologies and Communications from Instituto Tecnológico y de Estudios Superiores de Monterrey (ITESM), Campus Monterrey, major in Intelligent Systems in the field of Hyper-heuristic Search for the Bin Packing Problem. This dissertation works with an evolutionary framework that produces hyper-heuristics for solving several types of bin packing problems introducing relevant improvements to the solution model. The Bin Packing Problem is a particular case of the Cutting and Packing Problem, where a set of pieces are placed into identical objects and the objective is to minimize the number of objects needed. Given the NP-hard nature of this optimization problem, many heuris? tic approaches have been proposed. In this work a solution model is proposed, based on a genetic algorithm, in which a hyper-heuristic is built as a rule or a high-level heuristic that combines several low-level heuristics when building a solution from scratch. Therefore, the hyper-heuristic takes advantage of the main strengths of the low-level heuristics to solve particular kinds of problem instances. A hyper-heuristic is a list of several representative states of the problem, each one labelled by a low-level heuristic. A problem instance to be solved by a hyper-heuristic is first summarized by a numerical vector that carries some of its main features. This vector is then compared with the hyper-heuristic representative states and the correspondent heuristic is chosen to be applied. After one or several pieces are placed, the problem state is updated. This process continues until the problem instance is completely solved. The main inputs of the evolutionary framework in order to produce a hyper-heuristic are: (1) a vector-based way of representing the problem state; (2) a set of low-level heuristics; and (3) a set of training problem instances. The research presented in this document improves each of these elements. First, a data mining based methodology was developed to select the best set of features that can represent the state of the problem instances. This six-step methodology includes the application of the k-means clustering technique and a Multinomial Logistic Regression model to find a subset of features that best predict heuristic performance. This methodology does not require intensive knowledge of the problem domain. Promising results were found when comparing hyper-heuristics produced employing an intuitive representation and a representation built with this methodology. Besides, there are some other solution approaches developed for other combinatorial optimization problems that also require to represent instances with a limited number of features. Therefore, the proposed methodology can be exported for other search space approaches. Second, the Djang and Finch selection heuristic was properly adapted from the onedimensional to the two-dimensional Bin Packing Problem. This adaptation includes a timesaving routine based on avoiding repetitive computations. With the pieces in decreasing order, this heuristic starts filling an object until it is at least one-third full. Then it tries combinations of one, two or three pieces that completely fills the object. If this is not possible, a small waste is allowed and it is increased as necessary until there are not remaining pieces that fit. Then, a new object is opened. Several experiments were conducted with the initial fraction of the object that is full before trying combination of pieces. We found that filling the object up to one-fourth, one-third and one-half produces effective heuristics that behaves differently in different kinds of instances. Third, the level of generality handled by the evolutionary framework was increased in terms of the kind of instances solved. The solution model can be trained with one- and twodimension regular and irregular instances. Irregular instances include convex and concave polygons. Once the hyper-heuristic is evolved, it is able to solved any instance from any of these types with good results and without further parameter tuning. The framework was tested with a large dataset of 1417 instances. One-dimensional instances were drawn from the literature. An algorithm was designed for randomly producing two-dimensional instances with concave pieces. Therefore, geometric functions had to be implemented for dealing with concavities. Twenty hyper-heuristics were generated and tested. Broadly speaking, hyperheuristics were able to learn a combination of single heuristics that produce, at least, the same result than the best single heuristic for each testing case. Finally, an analysis was performed to find which feature values of the Bin Packing Pro? blem are more likely to lead to a good performance of heuristics and hyper-heuristics. With the Principal Component Analysis technique, a two-dimensional map was built in which the 1417 instances were plotted. The more similar two instances are according to nine selected features, the closer the two instances are plotted in the map. It is possible to find combination of feature values that characterize each section of the map. By over imposing the performance of heuristics and hyper-heuristics over the map, we can draw conclusions about the main relations among features and performance. Understanding the Bin Packing Problem structure will help in the design of new solution approaches.
Keywords:
Evolutionary Framework; Production Of Hyperheuristics; 2D Irregular Bin Packing Problem; Multinomial Logistic Regression Model
Degree Program:
Graduate Program in Electronics and Information Technologies
Advisors:
Dr. Hugo Terashima Marin
Committee Member / Sinodal:
Dr. Gabriela Ochoa; Dr. Peter Ross; Dr. Eduardo Uresti Charre; Dr. Manuel Valenzuela Rendon
Degree Level:
Doctor of Philosophy in Engineering with Major in Inteligent Systems
School:
School Of Engineering And Information Technologies Graduate Programs
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 Marines
dc.contributor.authorLópez Camacho, Eunicees
dc.date.accessioned2015-08-17T11:35:42Zen
dc.date.available2015-08-17T11:35:42Zen
dc.date.issued01/05/2012-
dc.identifier.urihttp://hdl.handle.net/11285/572577en
dc.description.abstractThis document presents a doctoral dissertation which is a requirement for the Ph.D. degree in Information Technologies and Communications from Instituto Tecnológico y de Estudios Superiores de Monterrey (ITESM), Campus Monterrey, major in Intelligent Systems in the field of Hyper-heuristic Search for the Bin Packing Problem. This dissertation works with an evolutionary framework that produces hyper-heuristics for solving several types of bin packing problems introducing relevant improvements to the solution model. The Bin Packing Problem is a particular case of the Cutting and Packing Problem, where a set of pieces are placed into identical objects and the objective is to minimize the number of objects needed. Given the NP-hard nature of this optimization problem, many heuris? tic approaches have been proposed. In this work a solution model is proposed, based on a genetic algorithm, in which a hyper-heuristic is built as a rule or a high-level heuristic that combines several low-level heuristics when building a solution from scratch. Therefore, the hyper-heuristic takes advantage of the main strengths of the low-level heuristics to solve particular kinds of problem instances. A hyper-heuristic is a list of several representative states of the problem, each one labelled by a low-level heuristic. A problem instance to be solved by a hyper-heuristic is first summarized by a numerical vector that carries some of its main features. This vector is then compared with the hyper-heuristic representative states and the correspondent heuristic is chosen to be applied. After one or several pieces are placed, the problem state is updated. This process continues until the problem instance is completely solved. The main inputs of the evolutionary framework in order to produce a hyper-heuristic are: (1) a vector-based way of representing the problem state; (2) a set of low-level heuristics; and (3) a set of training problem instances. The research presented in this document improves each of these elements. First, a data mining based methodology was developed to select the best set of features that can represent the state of the problem instances. This six-step methodology includes the application of the k-means clustering technique and a Multinomial Logistic Regression model to find a subset of features that best predict heuristic performance. This methodology does not require intensive knowledge of the problem domain. Promising results were found when comparing hyper-heuristics produced employing an intuitive representation and a representation built with this methodology. Besides, there are some other solution approaches developed for other combinatorial optimization problems that also require to represent instances with a limited number of features. Therefore, the proposed methodology can be exported for other search space approaches. Second, the Djang and Finch selection heuristic was properly adapted from the onedimensional to the two-dimensional Bin Packing Problem. This adaptation includes a timesaving routine based on avoiding repetitive computations. With the pieces in decreasing order, this heuristic starts filling an object until it is at least one-third full. Then it tries combinations of one, two or three pieces that completely fills the object. If this is not possible, a small waste is allowed and it is increased as necessary until there are not remaining pieces that fit. Then, a new object is opened. Several experiments were conducted with the initial fraction of the object that is full before trying combination of pieces. We found that filling the object up to one-fourth, one-third and one-half produces effective heuristics that behaves differently in different kinds of instances. Third, the level of generality handled by the evolutionary framework was increased in terms of the kind of instances solved. The solution model can be trained with one- and twodimension regular and irregular instances. Irregular instances include convex and concave polygons. Once the hyper-heuristic is evolved, it is able to solved any instance from any of these types with good results and without further parameter tuning. The framework was tested with a large dataset of 1417 instances. One-dimensional instances were drawn from the literature. An algorithm was designed for randomly producing two-dimensional instances with concave pieces. Therefore, geometric functions had to be implemented for dealing with concavities. Twenty hyper-heuristics were generated and tested. Broadly speaking, hyperheuristics were able to learn a combination of single heuristics that produce, at least, the same result than the best single heuristic for each testing case. Finally, an analysis was performed to find which feature values of the Bin Packing Pro? blem are more likely to lead to a good performance of heuristics and hyper-heuristics. With the Principal Component Analysis technique, a two-dimensional map was built in which the 1417 instances were plotted. The more similar two instances are according to nine selected features, the closer the two instances are plotted in the map. It is possible to find combination of feature values that characterize each section of the map. By over imposing the performance of heuristics and hyper-heuristics over the map, we can draw conclusions about the main relations among features and performance. Understanding the Bin Packing Problem structure will help in the design of new solution approaches.en
dc.language.isoenen
dc.rightsOpen Accessen
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.titleAn Evolutionary Framework for Producing Hyper-Heuristics for Solving the 2D Irregular Bin Packing Problemen
dc.typeTesis de Doctoradoes
thesis.degree.grantorInstituto Tecnológico y de Estudios Superiores de Monterreyes
thesis.degree.levelDoctor of Philosophy in Engineering with Major in Inteligent Systemsen
dc.contributor.committeememberDr. Gabriela Ochoaes
dc.contributor.committeememberDr. Peter Rosses
dc.contributor.committeememberDr. Eduardo Uresti Charrees
dc.contributor.committeememberDr. Manuel Valenzuela Rendones
thesis.degree.disciplineSchool Of Engineering And Information Technologies Graduate Programsen
thesis.degree.nameGraduate Program in Electronics and Information Technologiesen
dc.subject.keywordEvolutionary Frameworken
dc.subject.keywordProduction Of Hyperheuristicsen
dc.subject.keyword2D Irregular Bin Packing Problemen
dc.subject.keywordMultinomial Logistic Regression Modelen
thesis.degree.programCampus Monterreyes
dc.subject.disciplineIngeniería y Ciencias Aplicadas / Engineering & Applied Scienceses
All Items in REPOSITORIO DEL TECNOLOGICO DE MONTERREY are protected by copyright, with all rights reserved, unless otherwise indicated.