Evolving and reusing Bin Packing heuristic through Grammatical Differential Evolution

摘要

The Bin Packing Problem is a classic optimization problem, over the years many heuristics have been developed to obtain better results. There are many approaches to generating heuristics automatically, those approaches are based Genetic Programming, but the heuristics generated sometimes can not be applied to the problem. Recently in the Artificial Intelligence field, the Grammar Evolution approach emerged, which generated expressions like the generated by Genetic Programming; these algorithms evolve into a grammar based on the Backus Naur Form. In the present work we show a Grammar Evolution based on Differential Evolution, which automatically generated heuristics for the Bin Packing Problem instances. Those heuristics generated by the Grammar Evolution are like the Best-Fit heuristic which was designed by humans. The work's goal is to prove that is feasible to use the Grammar Evolution to automatically generate and reusing heuristics which have at least the same performance than the best generated by humans, we also propose a Grammar to improve the results obtained for a Grammar based on Genetic Programming.