Dimension reduction in the search for online bin packing policies
Shahriar Asta, Ender Özcan, Andrew J. Parkes · 2013
In online bin-packing problems, a policy must be found for assigning items, according their size, immediately upon their arrival to bins with known initial capacities. In previous work of Ozcan and Parkes (GECCO 2011), a policy was represented as a 2-dimensional "matrix" (array) and good matrices were then evolved using a genetic algorithm (GA). Here, we consider a form of dimensional reduction in which variables in the matrix are grouped into elements taken from one-dimensional vectors. We find that with the right form of grouping, the GA then typically finds such "vector policies" significantly more quickly, and yet suffers little loss of overall quality.