Evolving Bin Packing Heuristics with Genetic Programming
Evolving Bin Packing Heuristics with Genetic Programming
复制标题
通过遗传编程改进装箱启发法
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
G. Kendall
中科院分区：
文献类型：
--
作者：
E. Burke;Matthew R. Hyde;G. Kendall
装箱问题是一个众所周知的NP-Hard优化问题，多年来，许多启发式算法已经被开发出来，以产生高质量的解。本文概述了一种遗传编程系统，它进化了一种启发式算法，当获得已在垃圾桶中的碎片总数和即将打包的碎片的大小时，该启发式算法决定是否将一件物品放入垃圾箱。这种启发式方法在一个固定的框架中运行，该框架迭代打开的垃圾箱，将启发式方法应用于每个垃圾箱，然后决定使用哪个垃圾箱。进化得最好的程序模仿人类设计的“First-Fit”启发式功能。因此，本文的贡献在于证明了遗传编程可以用于自动进化装箱启发式算法，这些启发式算法与人类设计的高质量启发式算法相同。
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.
DOI：
10.1007/bfb0055923
发表时间：
1998
期刊：
--
影响因子：
--
作者：
Moshe Sipper
通讯作者：
Moshe Sipper