Loading...
Please wait, while we are loading the content...
Similar Documents
Evolving Bin Packing Heuristics with Genetic Programming (2006)
| Content Provider | CiteSeerX |
|---|---|
| Author | Burke, E. K. Hyde, M. R. Kendall, G. |
| Description | The bin-packing problem is a well known NP-Hard optimisation problem, and, over the years, many heuristics have been developed to generate good quality solutions. This paper outlines a genetic programming system which evolves a heuristic that decides whether to put a piece in a bin when presented with the sum of the pieces already in the bin and the size of the piece that is about to be packed. This heuristic operates in a fixed framework that iterates through the open bins, applying the heuristic to each one, before deciding which bin to use. The best evolved programs emulate the functionality of the human designed `first-fit' heuristic. Thus, the contribution of this paper is to demonstrate that genetic programming can be employed to automatically evolve bin packing heuristics which are the same as high quality heuristics which have been designed by humans. |
| File Format | |
| Language | English |
| Publisher | Springer |
| Publisher Date | 2006-01-01 |
| Publisher Institution | PARALLEL PROBLEM SOLVING FROM NATURE - PPSN IX SPRINGER LECTURE NOTES IN COMPUTER SCIENCE. VOLUME 4193 OF LNCS., REYKJAVIK, ICELAND, SPRINGER-VERLAG (2006) 860–869 |
| Access Restriction | Open |
| Subject Keyword | Np-hard Optimisation Problem Many Heuristic Good Quality Solution Bin-packing Problem Evolved Program High Quality Heuristic Fixed Framework Genetic Programming Open Bin Genetic Programming System |
| Content Type | Text |
| Resource Type | Article |
