# 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:
- 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:
- Committee Member / Sinodal:
- 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 Field | Value | Language |
---|---|---|

dc.contributor.advisor | Dr. Hugo Terashima Marin | es |

dc.contributor.author | López Camacho, Eunice | es |

dc.date.accessioned | 2015-08-17T11:35:42Z | en |

dc.date.available | 2015-08-17T11:35:42Z | en |

dc.date.issued | 01/05/2012 | - |

dc.identifier.uri | http://hdl.handle.net/11285/572577 | en |

dc.description.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. | en |

dc.language.iso | en | en |

dc.rights | Open Access | en |

dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |

dc.title | en | |

dc.type | Tesis de Doctorado | es |

thesis.degree.grantor | Instituto Tecnológico y de Estudios Superiores de Monterrey | es |

thesis.degree.level | Doctor of Philosophy in Engineering with Major in Inteligent Systems | en |

dc.contributor.committeemember | Dr. Gabriela Ochoa | es |

dc.contributor.committeemember | Dr. Peter Ross | es |

dc.contributor.committeemember | Dr. Eduardo Uresti Charre | es |

dc.contributor.committeemember | Dr. Manuel Valenzuela Rendon | es |

thesis.degree.discipline | School Of Engineering And Information Technologies Graduate Programs | en |

thesis.degree.name | Graduate Program in Electronics and Information Technologies | en |

dc.subject.keyword | Evolutionary Framework | en |

dc.subject.keyword | Production Of Hyperheuristics | en |

dc.subject.keyword | 2D Irregular Bin Packing Problem | en |

dc.subject.keyword | Multinomial Logistic Regression Model | en |

thesis.degree.program | Campus Monterrey | es |

dc.subject.discipline | Ingeniería y Ciencias Aplicadas / Engineering & Applied Sciences | es |

All Items in REPOSITORIO DEL TECNOLOGICO DE MONTERREY are protected by copyright, with all rights reserved, unless otherwise indicated.