University of Nottingham, School of Computer Science, Jubilee Campus, Nottingham, NG8 1BB, UK.
Evol Comput. 2012 Spring;20(1):63-89. doi: 10.1162/EVCO_a_00044. Epub 2011 Dec 2.
The literature shows that one-, two-, and three-dimensional bin packing and knapsack packing are difficult problems in operational research. Many techniques, including exact, heuristic, and metaheuristic approaches, have been investigated to solve these problems and it is often not clear which method to use when presented with a new instance. This paper presents an approach which is motivated by the goal of building computer systems which can design heuristic methods. The overall aim is to explore the possibilities for automating the heuristic design process. We present a genetic programming system to automatically generate a good quality heuristic for each instance. It is not necessary to change the methodology depending on the problem type (one-, two-, or three-dimensional knapsack and bin packing problems), and it therefore has a level of generality unmatched by other systems in the literature. We carry out an extensive suite of experiments and compare with the best human designed heuristics in the literature. Note that our heuristic design methodology uses the same parameters for all the experiments. The contribution of this paper is to present a more general packing methodology than those currently available, and to show that, by using this methodology, it is possible for a computer system to design heuristics which are competitive with the human designed heuristics from the literature. This represents the first packing algorithm in the literature able to claim human competitive results in such a wide variety of packing domains.
文献表明，一维、二维和三维的装箱和背包问题是运筹学中的难题。已经研究了许多技术，包括精确、启发式和元启发式方法，以解决这些问题，但当遇到新的实例时，通常不清楚应该使用哪种方法。本文提出了一种方法，其动机是构建能够设计启发式方法的计算机系统。总体目标是探索自动化启发式设计过程的可能性。我们提出了一种遗传编程系统，用于为每个实例自动生成高质量的启发式方法。不需要根据问题类型（一维、二维或三维背包和装箱问题）更改方法，因此它具有文献中其他系统无法比拟的通用性。我们进行了广泛的实验，并与文献中最好的人类设计启发式进行了比较。请注意，我们的启发式设计方法在所有实验中都使用相同的参数。本文的贡献在于提出了一种比现有方法更通用的包装方法，并表明通过使用这种方法，计算机系统可以设计出与文献中人类设计的启发式方法相竞争的启发式方法。这是文献中第一个能够在如此广泛的包装领域声称具有人类竞争力的包装算法。
