Parallel Discrete Harmony Search Algorithm for the Graph Coloring Problem
Received: 30 July 2024 | Revised: 23 August 2024 | Accepted: 3 September 2024 | Online: 7 September 2024
Corresponding author: Akram Kout
Abstract
Graph coloring is an NP-hard combinatorial optimization problem with significant implications in both theoretical and practical contexts due to its complexity and extensive applicability. In this work, a novel approach is proposed to address the graph coloring problem through a parallel discrete Harmony Search algorithm, termed PDHSCol. By harnessing the robustness of the Harmony Search algorithm and integrating parallel processing, our algorithm enhances performance by concurrently generating and evaluating multiple solutions. Implemented in MATLAB, PDHSCol was evaluated using a variety of DIMACS benchmark instances. The experimental results demonstrate that the algorithm performs effectively and yields promising improvements over various other methods, highlighting its potential to deliver high-quality solutions.
Keywords:
DPHSCol, DIMACS, graph coloring problem, NP-hard problem, Harmony Search AlgorithmDownloads
References
A. Gamst, "Some lower bounds for a class of frequency assignment problems," IEEE Transactions on Vehicular Technology, vol. 35, no. 1, pp. 8–14, Oct. 1986.
D. de Werra, Ch. Eisenbeis, S. Lelait, and B. Marmol, "On a graph-theoretical model for cyclic register allocation," Discrete Applied Mathematics, vol. 93, no. 2, pp. 191–203, Jul. 1999.
Y.-M. Chen and W.-C. Wang, "An adaptive rescheduling scheme based heuristic algorithm for cloud services applications," in International Conference on Machine Learning and Cybernetics, Guilin, China, Jul. 2011, vol. 3, pp. 961–966.
I. Mendez-Diaz and P. Zabala, "A Branch-and-Cut algorithm for graph coloring," Discrete Applied Mathematics, vol. 154, no. 5, pp. 826–847, Apr. 2006.
A. Mehrotra and M. A. Trick, "A Column Generation Approach for Graph Coloring," INFORMS Journal on Computing, vol. 8, no. 4, pp. 344–354, Nov. 1996.
D. Brelaz, "New methods to color the vertices of a graph," Communications of the ACM, vol. 22, no. 4, pp. 251–256, Dec. 1979.
D. J. A. Welsh and M. B. Powell, "An upper bound for the chromatic number of a graph and its application to timetabling problems," The Computer Journal, vol. 10, no. 1, pp. 85–86, Jan. 1967.
C. Fleurent and J. A. Ferland, "Genetic and hybrid algorithms for graph coloring," Annals of Operations Research, vol. 63, no. 3, pp. 437–461, Jun. 1996.
K. A. Dowsland and J. M. Thompson, "An improved ant colony optimisation heuristic for graph colouring," Discrete Applied Mathematics, vol. 156, no. 3, pp. 313–324, Feb. 2008.
C. Avanthay, A. Hertz, and N. Zufferey, "A variable neighborhood search for graph coloring," European Journal of Operational Research, vol. 151, no. 2, pp. 379–388, Dec. 2003.
Z. W. Geem, J. H. Kim, and G. V. Loganathan, "A New Heuristic Optimization Algorithm: Harmony Search," SIMULATION, vol. 76, no. 2, pp. 60–68, Feb. 2001.
M. Z. Gashti, "Detection of Spam Email by Combining Harmony Search Algorithm and Decision Tree," Engineering, Technology & Applied Science Research, vol. 7, no. 3, pp. 1713–1718, Jun. 2017.
R. M. A. Qasem and S. M. Massadeh, "Solving Cell Placement Problem Using Harmony Search Algorithms," Engineering, Technology & Applied Science Research, vol. 8, no. 4, pp. 3172–3176, Aug. 2018.
X. Wang, X.-Z. Gao, and S. J. Ovaska, "Fusion of clonal selection algorithm and harmony search method in optimisation of fuzzy classification systems," International Journal of Bio-Inspired Computation, vol. 1, no. 1–2, pp. 80–88, Jan. 2009.
Y. Cui, W. Dong, D. Hu, and H. Liu, "The Application of Improved Harmony Search Algorithm to Multi-UAV Task Assignment," Electronics, vol. 11, no. 8, Jan. 2022, Art. no. 1171.
X. Li, X. Li, and G. Yang, "A novelty harmony search algorithm of image segmentation for multilevel thresholding using learning experience and search space constraints," Multimedia Tools and Applications, vol. 82, no. 1, pp. 703–723, Jan. 2023.
K. Szwarc and U. Boryczka, "A novel approach to the Orienteering Problem based on the Harmony Search algorithm," PLOS ONE, vol. 17, no. 2, Feb. 2022, Art. no. e0264584.
A. Askarzadeh and E. Rashedi, "Harmony search algorithm: Basic concepts and engineering applications," in Recent Developments in Intelligent Nature-Inspired Computing, P. Srikanta, Ed. Hershey, PA, USA: IGI Global, 2017, pp. 1–36.
M. Mahdavi, M. Fesanghary, and E. Damangir, "An improved harmony search algorithm for solving optimization problems," Applied Mathematics and Computation, vol. 188, no. 2, pp. 1567–1579, May 2007.
L. Wang, R. Yang, Y. Xu, Q. Niu, P. M. Pardalos, and M. Fei, "An improved adaptive binary Harmony Search algorithm," Information Sciences, vol. 232, pp. 58–87, May 2013.
K. S. Lee, Z. W. Geem, S. Lee, and K. Bae, "The harmony search heuristic algorithm for discrete structural optimization," Engineering Optimization, vol. 37, no. 7, pp. 663–684, Oct. 2005.
D. S. Johnson and M. A. Trick, Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge. Providence, Rhode Island: American Mathematical Society, 1996.
H. Djelloul, A. Layeb, and S. Chikhi, "A Binary Cuckoo Search Algorithm for Graph Coloring Problem," International Journal of Applied Evolutionary Computation, vol. 5, no. 3, pp. 42–56, Jul. 2014.
H. Djelloul, S. Sabba, and S. Chikhi, "Binary bat algorithm for graph coloring problem," in Second World Conference on Complex Systems, Agadir, Morocco, Nov. 2014, pp. 481–486.
T. M. Mostafaie, F. Modarres Khiyabani, N. Jafari Navimipour, and B. Daneshian, "A new method for solving of the Graph Coloring Problem based on a fuzzy logic and whale optimization algorithm," Iranian Journal of Optimization, vol. 13, no. 2, pp. 115–121, Jun. 2021.
S. Gupta and Singh, "Greedy Graph Coloring Algorithm Based on Depth First Search," International Journal on Emerging Technologies, vol. 11, no. 2, pp. 854–862, Mar. 2020.
Downloads
How to Cite
License
Copyright (c) 2024 Sofiane Chemaa, Akram Kout, Halima Djelloul, Nassir Harrag
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the 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) after its publication in ETASR with an acknowledgement of its initial publication in this journal.
