Abstract
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 NP-Complete 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 by comparing the results of experiments on Bin-Packing problem, we analyze the effectiveness of steepest-descent hill climbing, stochastic hill climbing and first-improvement hill climbing as the local search algorithms in STAGE.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Boyan, J. A.: Learning Evaluation Function for Global Optimization. Doctoral dissertation, Computer Science Department, Carnige Mellon University (1998).
Boyan, J. A., & Moore, A. W.: Learning evaluation functions for global optimization and boolean satisfiability. In Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI) (1998).
Boese, K. D.: Models for Iterative Global Optimization. Doctoral dissertation, Computer Science Department, University of California, Los Angeles (1996).
Moll, R., Barto, A. G., Perkins, T. J., & Sutton, R. S.: Learning Instance-Independent Value Functions to Enhance Local Search, Proceeding of NIPS-98. Denver (1998).
Bertsekas, D. P., & Tsitsiklis, J. N.: Neuro-Dynamic Programming, Athena Scientific, Belmont, MA (1996).
Zhang, W., & Dietterich, T. G.: A reinforcement learning approach to job-shop scheduling. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) (1995), pages 1114–1120.
Boese, K.D., Khang, A. B., & Muddu, S.: On the Big Valley and Adaptive Multi-Start for Discrete Global Optimization. Operation Research Letters (1994), 16(2).
Coffman, E. G., Garey, M. R., & Johnson, D. S.: Approximation algorithms for bin packing: a survey. In D. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems. PWS Publishing (1996).
Garey, M. R., & Johnson, D. S.: Computer and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979).
Zhang, W. (1996). Reinforcement Learning for Job-Shop Scheduling. Doctoral dissertation, Computer Science Department, Oregon State University (1996).
Vazirani, Vijay V.: Approximation Algorithms, Springer-Verlag, New York (1999).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shouraki, S.B., Haffari, G. (2002). Different Local Search Algorithms in STAGE for Solving Bin Packing Problem. In: Shafazand, H., Tjoa, A.M. (eds) EurAsia-ICT 2002: Information and Communication Technology. EurAsia-ICT 2002. Lecture Notes in Computer Science, vol 2510. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36087-5_12
Download citation
DOI: https://doi.org/10.1007/3-540-36087-5_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00028-0
Online ISBN: 978-3-540-36087-2
eBook Packages: Springer Book Archive