A Comparative Study of Cat Swarm Algorithm for Graph Coloring Problem: Convergence Analysis and Performance Evaluation
Keywords:
Cat Swarm Optimization, Cat Swarm Algorithm, Graph Coloring, Graph Coloring ProblemAbstract
The Graph Coloring Problem (GCP) is a significant optimization challenge widely suitable to solve scheduling problems. Its goal is to specify the minimum colors (k) required to color a graph properly. Due to its NP-completeness, exact algorithms become impractical for graphs exceeding 100 vertices. As a result, approximation algorithms have gained prominence for tackling large-scale instances. In this context, the Cat Swarm algorithm, a novel population-based metaheuristic in the domain of swarm intelligence, has demonstrated promising convergence properties compared to other population-based algorithms. This research focuses on designing and implementing the Cat Swarm algorithm to address the GCP. By conducting a comparative study with established algorithms, our investigation revolves around quantifying the minimum value of k required by the Cat Swarm algorithm for each graph instance. The evaluation metrics include the algorithm's running time in seconds, success rate, and the mean count of iterations or assessments required to reach a goal.
References
H. Al-Omari and K. E. Sabri, "New graph coloring algorithms," American Journal of Mathematics and Statistics, vol. 2, no. 4, pp. 739-741, 2006. Available from: https://thescipub.com/pdf/jmssp.2006.439.441.pdf
H. Almara’beh and A. Suleiman, "Heuristic algorithm for graph coloring based on maximum independent set," Journal of Applied Computer Science & Mathematics, vol. 13, no. 6, pp. 19-23, 2012. Available from: https://www.jacsm.ro/view/?pid=13_3
R. Dorne and J. K. Hao, "A new genetic local search algorithm for graph coloring," in Parallel Problem Solving from Nature—PPSN V: 5th International Conference Amsterdam, The Netherlands September 27–30, 1998 Proceedings 5, vol. 5, Springer Berlin Heidelberg, 1998, pp. 745-754.D. Available from: https://doi.org/10.1007/BFb0056916
Bre1az, "New Methods to Color the Vertices of a Graph," Management Science/Operations Research, Communications of the ACM, vol. 22, no. 4, pp. page numbers, 1979. Available from: https://doi.org/10.1145/359094.359101
J. A. Torkestani, "A New Vertex Coloring Algorithm Based On Variable Action-Set Learning Automata," Computing and Informatics, vol. 29, pp. 447–466, Arak, Iran, 2010. Available from: https://www.researchgate.net/publication/220106403_A_New_Vertex_Coloring_Algorithm_Based_on_Variable_Aaction-Set_Learning_Automata
S. C. Chu, P. W. Tsai, and J. S. Pan, "Cat swarm optimization," in PRICAI 2006: Trends in Artificial Intelligence: 9th Pacific Rim International Conference on Artificial Intelligence Guilin, China, August 7-11, 2006 Proceedings 9, Springer Berlin Heidelberg, 2006, pp. 854-858. Available from: https://www.geeksforgeeks.org/cat-swarm-optimization/
L. Rouse and M. Albrandt, "A Touch of Color: Graph Coloring," Mini-Excursion 2. Available from: https://www.claytonschools.net/cms/lib/MO01000419/Centricity/Domain/241/ChromaticChapter.pdf
N. D. Bacarisas and J. P. T. Yusiong, "The Effect of Varying the Fitness Function on the Efficiency of the Cat Swarm Optimization algorithm in Solving the Graph Colouring Problem," Annals. Computer Science Series, vol. 9, 2011. Available from: https://www.sciencedirect.com/topics/computer-science/swarm-optimization-algorithm
M. Chiarandini and T. Stützle, "An application of iterated local search to graph coloring problem," in Proc. Computational Symposium on Graph Coloring and its Generalizations, New York, USA, Ithaca, Sep. 2002, pp. 112-125. Available from: https://imada.sdu.dk/u/marco/Publications/Files/gcp-ils-Ithaca.pdf
A Kosowski and K. Manuszewski, "Classical coloring of graphs," Contemporary Mathematics, vol. 352, pp. 1-20, 2004. Available from: https://umv.science.upjs.sk/madaras/ATG/coloring%20algorithms.pdf
Mansuri, V. Gupta, and R. S. Chandel, "Coloring Programs in Graph Theory," Int. Journal of Math. Analysis, vol. 4, no. 50, pp. 2473-2479, Bhopal, (M.P.) India, 2010. Available from: https://www.geeksforgeeks.org/graph-coloring-applications/
M. Orouskhani, Y. Orouskhani, M. Mansouri, and M. Teshnehlab, "A Novel Cat Swarm Optimization Algorithm for Unconstrained Optimization Problems," I.J. Information Technology and Computer Science, vol. 11, pp. 32-41, 2013. Available from: https://www.mecs-press.org/ijitcs/ijitcs-v5-n11/IJITCS-V5-N11-4.pdf
R. Elio, J. Hoover, I. Nikolaidis, M. Salavatipour, L. Stewart, and K. Wong, "About computing science research methodology," in Google Scholar Google Scholar Reference, 2011. Available from: https://www.semanticscholar.org/paper/About-Computing-Science-Research-Methodology-Elio-Hoover/55a528f0f10b4ff4d4ec40d8fc30460ecf51f697
J. R. Allwright, R. Bordawekar, P. D. Coddington, K. Dincer, and C. L. Martin, "A comparison of parallel graph coloring algorithms," SCCS-666, pp. 1-19, 1995. Available from: https://www.researchgate.net/publication/2296563_A_Comparison_of_Parallel_Graph_Coloring_Algorithms
W. Matula, G. Marble, and J. D. Isaacson, "Graph coloring algorithms," in Graph Theory and Computing, New York, NY, USA: Academic Press, 1972, pp. 109-122. Available from: https://www.geeksforgeeks.org/graph-coloring-applications/
T. Leighton, "A graph coloring algorithm for large scheduling problems," Journal of Research of the National Bureau of Standards, vol. 84, no. 6, p. 489, 1979. Available from: https://nvlpubs.nist.gov/nistpubs/jres/84/jresv84n6p489_a1b.pdf
N. Musliu and M. Schwengerer, "Algorithm selection for the graph coloring problem," in International Conference on Learning and Intelligent Optimization, Berlin, Germany, Jan. 2013, pp. 389-403. Available from: https://link.springer.com/chapter/10.1007/978-3-642-44973-4_42
"Vertex Coloring: Welsh Powell Algorithm," Module 2: Planning and Scheduling, pp. 53-55. Available from: http://mrsleblancsmath.pbworks.com/w/file/fetch/46119304/vertex%20coloring%20algorithm.pdf
M. Taherdangkoo, M. H. Shirzadi, M. Yazdi, and M. HadiBagheri, "A Robust Clustering Method Based on Blind, Naked Mole-Rats (BNMR) Algorithm," Swarm and Evolutionary Computation, vol. 10, pp. 1–11, 2013. Available from: https://www.sciencedirect.com/science/article/abs/pii/S2210650213000035
S. C. Chu and P. W. Tsai, "Computational intelligence based on the behavior of cats," International Journal of Innovative Computing, Information and Control, vol. 3, no. 1, pp. 163-173, 2007. Available from: https://www.researchgate.net/publication/228721750_Computational_intelligence_based_on_the_
