TY - JOUR
T1 - Grammar-based generation of stochastic local search heuristics through automatic algorithm configuration tools
AU - Mascia, Franco
AU - López-Ibáñez, Manuel
AU - Dubois-Lacoste, Jérémie
AU - Stützle, Thomas
PY - 2014
Y1 - 2014
N2 - Several grammar-based genetic programming algorithms have been proposed in the literature to automatically generate heuristics for hard optimization problems. These approaches specify the algorithmic building blocks and the way in which they can be combined in a grammar; the best heuristic for the problem being tackled is found by an evolutionary algorithm that searches in the algorithm design space defined by the grammar. In this work, we propose a novel representation of the grammar by a sequence of categorical, integer, and real-valued parameters. We then use a tool for automatic algorithm configuration to search for the best algorithm for the problem at hand. Our experimental evaluation on the one-dimensional bin packing problem and the permutation flowshop problem with weighted tardiness objective shows that the proposed approach produces better algorithms than grammatical evolution, a well-established variant of grammar-based genetic programming. The reasons behind such improvement lie both in the representation proposed and in the method used to search the algorithm design space.
AB - Several grammar-based genetic programming algorithms have been proposed in the literature to automatically generate heuristics for hard optimization problems. These approaches specify the algorithmic building blocks and the way in which they can be combined in a grammar; the best heuristic for the problem being tackled is found by an evolutionary algorithm that searches in the algorithm design space defined by the grammar. In this work, we propose a novel representation of the grammar by a sequence of categorical, integer, and real-valued parameters. We then use a tool for automatic algorithm configuration to search for the best algorithm for the problem at hand. Our experimental evaluation on the one-dimensional bin packing problem and the permutation flowshop problem with weighted tardiness objective shows that the proposed approach produces better algorithms than grammatical evolution, a well-established variant of grammar-based genetic programming. The reasons behind such improvement lie both in the representation proposed and in the method used to search the algorithm design space.
KW - Automatic algorithm configuration
KW - Bin packing
KW - Flowshop scheduling
KW - Grammatical evolution
KW - Heuristics
UR - http://www.scopus.com/inward/record.url?scp=84903118447&partnerID=8YFLogxK
U2 - 10.1016/j.cor.2014.05.020
DO - 10.1016/j.cor.2014.05.020
M3 - Article
AN - SCOPUS:84903118447
SN - 0305-0548
VL - 51
SP - 190
EP - 199
JO - Computers and Operations Research
JF - Computers and Operations Research
ER -