ADAPTIVE HARMONY SEARCH FOR OPTIMIZING CONSTRAINED RESOURCE ALLOCATION PROBLEM
DOI:
https://doi.org/10.47839/ijc.17.4.1148Keywords:
Harmony Search Algorithm (HS), Bin packing problem (BPP), Virtual machine placement problem (VMP), Meta-heuristic.Abstract
Resource Allocation problem is finding the optimal assignment of finite available resources to tasks or users. Resource allocation problems refer to a wide range of applications such as production, supply chain management, transportation, ICT technologies, etc. Resource allocation problems are NP-hard in nature where the objective is to find the optimal allocations satisfying given constraints. Harmony search (HS) algorithm is a meta-heuristic population based algorithm found good for solving different optimization problems. This paper presents adaptive harmony search (AHS) for solving one-dimensional bin packing problem (BPP) and multi-objective virtual machine placement problem (VMP). The proposed real coded solution representation supports partial constraint satisfaction. Adaptive pitch adjustment rate (PAR) based on population diversity improves the performance of harmony search algorithm. Results show that proposed HS gives optimal solution for 50 BPP instances with 100 % success rate. The performance reduced for large instances of BPP. The proposed weighted AHS for multi objective VMP problem gives better results than genetic algorithm.References
S. K. Chaharsooghi, A. H. Meimand Kermani, “An effective ant colony optimization algorithm (ACO) for multi-objective resource allocation problem (MORAP),” Applied Mathematics and Computation, vol. 200, no. 1, pp. 167-177, 2008.
A. Borisenko, M. Haidl, S. Gorlatch, “A GPU parallelization of branch-and-bound for multiproduct batch plants optimization,” The Journal of Supercomputing, vol. 73, no. 2, pp. 639-651, 2017.
A. Borisenko, S. Gorlatch, “Comparing GPU-parallelized metaheuristics to branch-and-bound for batch plants optimization,” The Journal of Supercomputing, pp. 1-13, 2018.
D. Weyland, “A critical analysis of the harmony search algorithm – How not to solve Sudoku,” Operations Research Perspectives, vol. 2, pp. 97-105, 2015.
S. Sivasubramani, K. S. Swarup, “Multi-objective harmony search algorithm for optimal power flow problem,” International Journal Electric Power Energy System, vol. 33, no. 3, pp. 745–52, 2011.
A. Kaveh, S. Talatahari, “Particle swarm optimizer, ant colony strategy and harmony search scheme hybridized for optimization of truss structures,” Computers & Structures, vol. 87, no. 5-6, pp. 267-283, 2009.
S. A. Hussain, V. U. K. Sastry, “Application of genetic algorithm for bin packing,” International Journal of Computer Mathematics, vol. 63, no. 3-4, pp. 203-214, 1997.
T. Dokeroglu, A. Cosar, “Optimization of one-dimensional bin packing problem with island parallel grouping genetic algorithms,” Computers & Industrial Engineering, vol. 75, pp. 176-186, 2014.
K.-H. Loh, B. Golden, E. Wasil, “Solving the one-dimensional bin packing problem with a weight annealing heuristic,” Computers & Operations Research, vol. 35, no. 7, pp. 2283-2291, 2008.
S. Abidi, S. Krichen, E. Alba, J. M. Molina, “Improvement heuristic for solving the one-dimensional bin-packing problem,” Proceedings of the IEEE 5th International Conference on Modeling, Simulation and Applied Optimization (ICMSAO), 2013, pp. 1-5.
A. Singh, A. K. Gupta, “Two heuristics for the one-dimensional bin-packing problem,” OR Spectrum, vol. 29, no. 4, pp. 765-781, 2007.
K. Sim, E. Hart, B. Paechter, “A hyper-heuristic classifier for one dimensional bin packing problems: Improving classification accuracy by attribute evolution,” Proceedings of the International Conference on Parallel Problem Solving from Nature, Springer, Berlin, Heidelberg, 2012, pp. 348-357.
A. K. Bhatia, M. Hazra, S. K. Basu, “Better-fit heuristic for one-dimensional bin-packing problem,” Proceedings of the IEEE International Advance Computing Conference IACC 2009, 2009, pp. 193-196.
Alvim, Adriana CF, Celso C. Ribeiro, Fred Glover, and Dario J. Aloise, “A hybrid improvement heuristic for the one-dimensional bin packing problem,” Journal of Heuristics, 2004, vol. 10, no. 2, pp. 205-229.
M. Abdel-Basset, G. Manogaran, L. Abdel-Fatah, S. Mirjalili, “An improved nature inspired meta-heuristic algorithm for 1-D bin packing problems,” Personal and Ubiquitous Computing, 2018, pp. 1-16.
A. Scholl, R. Klein, C. Jürgens, “Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem,” Computers & Operations Research, vol. 24, no. 7, pp. 627-645, 1997.
D. Sensarma, S. S. Sarma, “A novel graph based algorithm for one dimensional bin packing problem,” International Journal of Global Research in Computer Science, vol. 5, no. 8, pp. 1-4, 2014.
N. Karmarkar, R. M. Karp, “An efficient approximation scheme for the one-dimensional bin-packing problem,” Proceedings of the IEEE 23rd Annual Symposium on Foundations of Computer Science SFCS’08, 1982, pp. 160-164.
K. Fleszar, K. S. Hindi, “New heuristics for one-dimensional bin-packing,” Computers & operations research, vol. 29, no. 7, pp. 821-839, 2002.
M. Masdari, S. S. Nabavi, V. Ahmadi, “An overview of virtual machine placement schemes in cloud computing,” Journal of Network and Computer Applications, vol. 66, pp. 106-127, 2016.
F. Lopez-Pires, B. Baran, “Virtual machine placement literature review,” arXiv preprint arXiv:1506.01509, 2015.
S. Vahora, R. Patel, H. Patel, S. Patel, “Efficient virtual machine management based on dynamic workload in cloud computing environment,” Proceedings of the IEEE International Advance Computing Conference (IACC), 2015, pp. 603-608.
R. Cziva, S. Jouët, D. Stapleton, F. P. Tso, D. P. Pezaros, “SDN-based virtual machine management for cloud data centers,” IEEE Transactions on Network and Service Management, vol. 13, no. 2, pp. 212-225, 2016.
J. Xu, J. A. Fortes, “Multi-objective virtual machine placement in virtualized data center environments,” Proceedings of the IEEE/ACM International Conference on Green Computing and Communications & International Conference on Cyber, Physical and Social Computing, 2010 Dec 18, pp. 179-188.
A. C. Adamuthe, J. T. Patil, “Differential evolution algorithm for optimizing virtual machine placement problem in cloud computing,” International Journal of Intelligent Systems and Applications, vol. 10, no. 7, pp. 58-65, 2018.
A. Satpathy, S. K. Addya, A. K. Turuk, B. Majhi, G. Sahoo, “Crow search based virtual machine placement strategy in cloud data centers with live migration,” Computers & Electrical Engineering, vol. 69, pp. 334-350, 2018.
F.-H. Tseng, X. Wang, L.-D. Chou, H.-C. Chao, and V. C. M. Leung, “Dynamic resource prediction and allocation for cloud data center using the multiobjective genetic algorithm,” IEEE Systems Journal, vol. 12, no. 2, pp. 1688-1699, 2018.
A. C. Adamuthe, R. M. Pandharpatte, G. T. Thampi, “Multiobjective virtual machine placement in cloud environment,” Proceedings of the IEEE International Conference on Cloud & Ubiquitous Computing & Emerging Technologies (CUBE), 2013, pp. 8-13.
J. Xu and J. Fortes, “Multi-objective virtual machine placement in virtualization data center environments,” Proceedings of the IEEE/ACM International Conference on Green Computing and Communications (GreenCom’10) & International Conference on Cyber, Physical and Social Computing (CPSCom’10), Dec. 18-20, 2010, pp. 179-188.
Z. Geem, “Harmony search algorithm for solving sudoku”, In: B. Apolloni, R.J. Howlett, L. Jain (eds) Knowledge-based intelligent information and engineering systems, Lecture Notes in Computer Science, vol. 4692. Springer, Berlin/Heidelberg, 2007, pp. 371–378.
Z. W. Geem, J.-Y. Choi, “Music composition using harmony search algorithm,” Proceedings of the Workshops on Applications of Evolutionary Computation, Springer, Berlin, Heidelberg, pp. 593-600, 2007.
Z. W. Geem, “Particle-swarm harmony search for water network design,” Engineering Optimization, vol. 41, no. 4, pp. 297-311, 2009.
Z. W. Geem, H. Hwangbo, “Application of harmony search to multi-objective optimization for satellite heat pipe design,” Proceedings of US-Korea Conference on Science, Technology, & Entrepreneurship (UKC 2006), Teaneck, NJ, USA, 2006, pp. 1-3.
Z. W. Geem, “Optimal scheduling of multiple dam system using harmony search algorithm,” Proceedings of the International Work-Conference on Artificial Neural Networks, Springer, Berlin, Heidelberg, 2007, pp. 316-323.
Z. W. Geem, K. S. Lee, Y. Park, “Application of harmony search to vehicle routing,” American Journal of Applied Sciences, vol. 2, no. 12, pp. 1552-1557, 2005.
A. Vasebi, M. Fesanghary, S. M. T. Bathaee, “Combined heat and power economic dispatch by harmony search algorithm,” International Journal of Electrical Power & Energy Systems, vol. 29, no. 10, pp. 713-719, 2007.
R. S. Rao, S. V. Lakshmi Narasimham, M. Ramalinga Raju, A. Srinivasa Rao, “Optimal network reconfiguration of large-scale distribution system using harmony search algorithm,” IEEE Transactions on Power Systems, vol. 26, no. 3, pp. 1080-1088, 2011.
M. Fesanghary, M. Mahdavi, M. Minary-Jolandan, and Y. Alizadeh, “Hybridizing harmony search algorithm with sequential quadratic programming for engineering optimization problems,” Computer Methods in Applied Mechanics and Engineering, vol. 197, no. 33-40, pp. 3080-3091, 2008.
X. Wang, X.-Z. Gao, and K. Zenger, An Introduction to Harmony Search Optimization Method, Springer International Publishing, 2015.
C.-M. Wang, Y.-F. Huang, “Self-adaptive harmony search algorithm for optimization,” Expert Systems with Applications, vol. 37, no. 4, pp. 2826-2837, 2010.
D. S. Rani, N. Subrahmanyam, M. Sydulu, “Self adaptive harmony search algorithm for optimal network reconfiguration,” Proceedings of the IEEE Power and Energy Conference at Illinois (PECI’2014), 2014, pp. 1-6.
M. P. Saka, O. Hasancebi, “Adaptive harmony search algorithm for design code optimization of steel structures,” Proceedings of the Harmony Search Algorithms for Structural Design Optimization, Springer, Berlin, Heidelberg, 2009, pp. 79-120.
https://people.sc.fsu.edu/~jburkardt/datasets/bin_packing/bin_packing.html
N. Mohamadi, “Application of genetic algorithm for the bin packing problem with a new representation scheme,” Mathematical Sciences, vol. 4, no. 3, pp. 253-266, 2010.
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
