Harmony search algorithm with adaptive parameter setting for solving large bin packing problems

Abstract: Bin packing problem is a constrained optimization problem with a huge search space due to large combinations. Bin packing problem has a wide range of applications in multiple fields. This paper presents harmony search algorithm with different initialization and adaptive PAR strategies for solving bin packing problem. The proposed Harmony search (HS) variations tests two partial feasible initialization strategies for bin packing problem. The paper presents adaptive PAR strategies for better exploration and exploitation of HS algorithm. The PAR values are tuned in every iteration. Improved initialization strategy, population initialization after premature convergence and adaptive PAR leads to the better exploration of harmony search algorithm for bin packing problem. The performance of variations are tested over 120 benchmark instances with 100 and 200 objects with varying complexities. The results show that improved HS performs better than basic HS with respect to best, mean, convergence rate. The performance of algorithms is tested with varying harmony memory size and harmony memory considering rate. Results show that variation in these two parameter values has less effect on performance of improved versions.

How to cite this paper

 Adamuthe, A & Nitave, T. (2020). Harmony search algorithm with adaptive parameter setting for solving large bin packing problems.Decision Science Letters , 9(4), 581-594.

Refrences

Abdel-Basset, M., Manogaran, G., Abdel-Fatah, L., & Mirjalili, S. (2018). An improved nature inspired meta-heuristic algorithm for 1-D bin packing problems. Personal and Ubiquitous Computing, 22(5-6), 1117-1132.
Adamuthe, A. C., & Patil, J. T. (2018). Differential evolution algorithm for optimizing virtual machine placement problem in cloud computing. International Journal of Intelligent Systems and Applications, 11(7), 58.
Aggoun, A., Rhiat, A., & Fages, F. (2016, May). Panorama of real-life applications in logistics embedding bin packing optimization algorithms, robotics and cloud computing technologies. In 2016 3rd International Conference on Logistics Operations Management (GOL) (pp. 1-4). IEEE.
Alvim, A. C., Ribeiro, C. C., Glover, F., & Aloise, D. J. (2004). A hybrid improvement heuristic for the one-dimensional bin packing problem. Journal of Heuristics, 10(2), 205-229.
Banerjee, A., Mukherjee, V., & Ghoshal, S. P. (2014). An opposition-based harmony search algorithm for engineering optimization problems. Ain Shams Engineering Journal, 5(1), 85-101.
Berghammer, R., & Reuter, F. (2003). A linear approximation algorithm for bin packing with absolute approximation factor 32. Science of Computer Programming, 48(1), 67-80.
Dósa, G., & Sgall, J. (2013). First Fit bin packing: A tight analysis. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
Dósa, G., & Sgall, J. (2014, July). Optimal analysis of Best Fit bin packing. In International Colloquium on Automata, Languages, and Programming (pp. 429-441). Springer, Berlin, Heidelberg.
Falkenauer, E. (1996). A hybrid grouping genetic algorithm for bin packing. Journal of heuristics, 2(1), 5-30.
Fleszar, K., & Hindi, K. S. (2002). New heuristics for one-dimensional bin-packing. Computers & operations research, 29(7), 821-839.
Geem, Z. W., Kim, J. H., & Loganathan, G. V. (2001). A new heuristic optimization algorithm: harmony search. simulation, 76(2), 60-68.
Kattan, A., & Abdullah, R. (2013). A dynamic self-adaptive harmony search algorithm for continuous optimization problems. Applied Mathematics and Computation, 219(16), 8542-8567.
Khalili, M., Kharrat, R., Salahshoor, K., & Sefat, M. H. (2014). Global dynamic harmony search algorithm: GDHS. Applied Mathematics and Computation, 228, 195-219.
Layeb, A., & Benayad, Z. (2014). A novel firefly algorithm based ant colony optimization for solving combinatorial optimization problems. IJCSA, 11(2), 19-37.
Layeb, A., & Boussalia, S. R. (2012). A novel quantum inspired cuckoo search algorithm for bin packing problem. International Journal of Information Technology and Computer Science, 4(5), 58-67.
Lee, K. S., & Geem, Z. W. (2005). A new meta-heuristic algorithm for continuous engineering optimization: harmony search theory and practice. Computer methods in applied mechanics and engineering, 194(36-38), 3902-3933.
Levine, J., & Ducatelle, F. (2004). Ant colony optimization and local search for bin packing and cutting stock problems. Journal of the Operational Research society, 55(7), 705-716.
Mahdavi, M., Fesanghary, M., & Damangir, E. (2007). An improved harmony search algorithm for solving optimization problems. Applied mathematics and computation, 188(2), 1567-1579.
Martel, C. U. (1985). A linear time bin-packing algorithm. Operations research letters, 4(4), 189-192.
Martello, S., & Toth, P. (1990). Lower bounds and reduction procedures for the bin packing problem. Discrete applied mathematics, 28(1), 59-70.
Omran, M. G., & Mahdavi, M. (2008). Global-best harmony search. Applied mathematics and computation, 198(2), 643-656.
Park, J., Kwon, S., Kim, M., & Han, S. (2017). A cascaded improved harmony search for line impedance estimation in a radial power system. IFAC-PapersOnLine, 50(1), 3368-3375.
Perboli, G., Gobbato, L., & Perfetti, F. (2014). Packing problems in transportation and supply chain: new problems and trends. Procedia-Social and Behavioral Sciences, 111(0), 672-681.
Schoenfield, J. E. (2002). Fast, exact solution of open bin packing problems without linear programming. Draft. US Army Space & Missile Defence Command, Huntsville, 20, 72.
Schwerin, P., & Wäscher, G. (1997). The bin-packing problem: A problem generator and some numerical experiments with FFD packing and MTP. International Transactions in Operational Research, 4(5-6), 377-389.
Simchi‐Levi, D. (1994). New worst‐case results for the bin‐packing problem. Naval Research Logistics (NRL), 41(4), 579-585.
Song, W., Xiao, Z., Chen, Q., & Luo, H. (2013). Adaptive resource provisioning for the cloud using online bin packing. IEEE Transactions on Computers, 63(11), 2647-2660.
Taherinejad, N. (2009, August). Highly reliable harmony search algorithm. In 2009 European Conference on Circuit Theory and Design (pp. 818-822). IEEE.
Valian, E., Tavakoli, S., & Mohanna, S. (2014). An intelligent global harmony search approach to continuous optimization problems. Applied Mathematics and Computation, 232, 670-684.
Wang, C. M., & Huang, Y. F. (2010). Self-adaptive harmony search algorithm for optimization. Expert Systems with Applications, 37(4), 2826-2837.
Yadav, P., Kumar, R., Panda, S. K., & Chang, C. S. (2012). An intelligent tuned harmony search algorithm for optimisation. Information Sciences, 196, 47-72.
Zendaoui, Z., & Layeb, A. (2016). Adaptive cuckoo search algorithm for the bin packing problem. In Modelling and Implementation of Complex Systems (pp. 107-120). Springer, Cham.