An Analysis of Heuristic Templates in Genetic Programming for One-Dimensional Cutting and Packing Problems

Created by W.Langdon from gp-bibliography.bib Revision:1.7650

@InProceedings{quesada:2023:GECCOcomp,

• author = "Jesus Quesada and Francisco Javier Gil-Gala and Marko Durasevic and Maria Sierra and Ramiro Varela",
• title = "An Analysis of Heuristic Templates in Genetic Programming for {One-Dimensional} Cutting and Packing Problems",
• booktitle = "Proceedings of the 2023 Genetic and Evolutionary Computation Conference",
• year = "2023",
• editor = "Sara Silva and Luis Paquete and Leonardo Vanneschi and Nuno Lourenco and Ales Zamuda and Ahmed Kheiri and Arnaud Liefooghe and Bing Xue and Ying Bi and Nelishia Pillay and Irene Moser and Arthur Guijt and Jessica Catarino and Pablo Garcia-Sanchez and Leonardo Trujillo and Carla Silva and Nadarajen Veerapen",
• pages = "623--626",
• address = "Lisbon, Portugal",
• series = "GECCO '23",
• month = "15-19 " # jul,
• organisation = "SIGEVO",
• publisher = "Association for Computing Machinery",
• publisher_address = "New York, NY, USA",
• keywords = "genetic algorithms, genetic programming, packing problem, hyper-heuristic: Poster",
• isbn13 = "9798400701191",
• DOI = "doi:10.1145/3583133.3590674",
• size = "4 pages",
• abstract = "One-dimensional cutting stock and packing problems require determining a set of patterns that are applied a number of times each on raw material pieces to produce a number of customer orders. Among many other solving methods, greedy algorithms guided by heuristic rules stand out due to their low computational cost and ability to be adapted to sets of instances with similar structures. In this paper, we use genetic programming (GP) to evolve heuristics for the one-dimensional bin packing problem. We explore two greedy variants taken from the literature; in the first one, termed cut-by-cut, the heuristic rule is used to construct the pattern by selecting the most appropriate item that should be packed. In the second one, denoted as pattern-by-pattern, a number of patterns are randomly generated, and the heuristic selects the most appropriate one to be applied. We thoroughly analysed the problem's features to identify the relevant attributes of each greedy strategy. From these attributes, we exploited GP to evolve a number of heuristics adapted to a well-known benchmark set of one-dimensional bin packing instances. The experimental results provided interesting insights into the problem features and showed that the evolved heuristics are competitive with the state-of-the-art.",
• notes = "GECCO-2023 A Recombination of the 32nd International Conference on Genetic Algorithms (ICGA) and the 28th Annual Genetic Programming Conference (GP)",

}

Genetic Programming entries for Jesus Quesada Francisco Javier Gil Gala Marko Durasevic Maria Sierra Ramiro Varela Arias

Citations