Analysis of STAGE Algorithm Based on Solving Bin Packing Problem.
Gholamreza Haffari, Saeed Bagheri Shouraki · International Conference on Machine Learning and Applications · 2002
Previous researches have shown the success of using Reinforcement Learning in solving combinatorial optimization problems. The main idea of these methods is to learn (near) optimal evaluation functions to improve local searches and find (near) optimal solutions. STAGE algorithm, introduced by Boyan & Moore, is one of the most important algorithms in this area. In this paper, we focus on Bin-Packing problem, an important NPComplete problem. We analyze cost surface structure of this problem and investigate ”big valley” structure for the set of its local minima. The result gives reasons for STAGE’s success in solving this problem. Then based on experimental results of Bin-Packing problem, we analyze the effectiveness of using different local search algorithms and different learning structures in STAGE.