Policy matrix evolution for generation of heuristics
Policy matrix evolution for generation of heuristics
复制标题
用于生成启发式的策略矩阵演化
作者：
E. Özcan;A. Parkes
在线打包是一个众所周知的问题，在这个问题中，必须立即决定将不同大小的物品放入固定容量的垃圾箱中。关联的决策可以基于索引策略，其中每个决策选项都被独立地赋予一个值，并选择最大值。在本文中，我们将这种启发式的在线装箱表示为一个简单的分数矩阵。然后，我们使用遗传算法来搜索具有良好性能的矩阵。这可以看作是打包启发式的参数调优，但在其中使用了细粒度表示，因此参数数量比标准参数调优要大得多。进化矩阵比标准启发式执行得更好。它们还揭示了有趣的结构，因此对启发式得分函数应该如何表示以及它们可能表现出什么样的结构的问题产生了影响。
Online bin-packing is a well-known problem in which immediate decisions must be made about the placement of items with various sizes into fixed capacity bins. The associated decisions can be based on an index policy in which each decision option is independently given a value and the highest value choice is selected. In this paper, we represent such heuristics for online bin packing as a simple matrix of scores. We then use a genetic algorithm to search for matrices giving good performance. This might be regarded as parameter tuning of the packing heuristic but in which a fine-grained representation is used and so the number of parameters is much larger than in standard parameter tuning. The evolved matrices perform better than the standard heuristics. They also reveal interesting structures and so have impact on questions of how heuristic score functions should be represented and what structure they might be expected to exhibit.