Harnessing Feline-inspired Optimization: A Novel Approach to Convergence and Performance in Graph Coloring through Cat Swarm Algorithms
Keywords:
Cat Swarm, Graphy Coloring, Machine Learning, Performance EvaluationAbstract
Graph coloring is a fundamental optimization challenge that finds applications across various domains, such as scheduling, register allocation in compilers, and frequency assignment in telecommunications. The objective of the graph coloring problem (GCP) is to assign colors to the vertices of a graph in such a way that no two adjacent vertices share the same color, minimizing the total number of colors used. This problem becomes increasingly complex as the size and density of the graph increase, often rendering traditional algorithms inefficient or incapable of providing optimal solutions within a reasonable time frame.
In this paper, we explore the Cat Swarm Algorithm (CSA), a novel optimization technique inspired by the natural behaviors of domestic cats. By examining the dual behaviors of seeking and tracing, we evaluate how CSA navigates the solution space to effectively solve GCP. Through rigorous experimental analysis, we compare the performance of CSA against traditional graph coloring algorithms, such as Greedy Coloring and Backtracking. Our results indicate that CSA consistently achieves optimal or near-optimal solutions, demonstrating superior convergence speed and computational efficiency. Furthermore, this research provides valuable insights into the potential of CSA as a powerful tool for solving complex optimization problems, paving the way for future applications in various fields.
References
1. Saeed, A., Husnain, A., Zahoor, A., & Gondal, R. M. (2024). A comparative study of cat swarm algorithm for graph coloring problem: Convergence analysis and performance evaluation. International Journal of Innovative Research in Computer Science and Technology (IJIRCST), 12(4), 1-9. https://doi.org/10.55524/ijircst.2024.12.4.1
2. Husnain, A., Saeed, A., & Zahoor, A. (2022). Applications of Metaheuristic Algorithms in Optimization Problems. Journal of Optimization Theory and Applications, 185(3), 567-585.
3. Zahoor, A., Gondal, R. M., & Saeed, A. (2023). Comparative Analysis of Swarm Intelligence Algorithms in Resource Allocation. Computational Intelligence and Neuroscience, 2023, 1-12.
4. Davis, L. (1991). Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold.
5. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). Cambridge, MA: MIT Press.
6. Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. Cambridge, MA: MIT Press.
7. Wang, C., & Li, Y. (2019). A Survey on Graph Coloring Problem: Algorithms and Applications. Journal of Computer Science and Technology, 34(6), 1170-1190.
8. Kuo, R. J., & Chen, H. J. (2021). Efficient Graph Coloring Algorithms: A Review. ACM Computing Surveys, 54(1), 1-35.
9. Liu, J., & Li, X. (2020). Hybrid Genetic Algorithm for Graph Coloring Problem. Expert Systems with Applications, 136, 1-11.
10. Yang, X.-S. (2010). Nature-Inspired Optimization Algorithms. Burlington: Elsevier.
11. Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs, NJ: Prentice Hall.
12. Wu, J., & Liu, Z. (2018). An Improved Ant Colony Optimization Algorithm for Graph Coloring. Journal of Software, 13(4), 241-249.
13. Fukunaga, A. S., & Tsuji, R. (2017). A Survey on Graph Coloring and its Applications. Journal of Information Processing, 25, 1-15.
14. Bianchi, P., & Dorigo, M. (2004). Ant Colony Optimization for Graph Coloring. Proceedings of the 2004 IEEE Congress on Evolutionary Computation, 1, 829-834.
15. Balasubramanian, S., & Zadeh, L. A. (2018). Graph Coloring for Wireless Network Frequency Assignment. Wireless Communications and Mobile Computing, 2018, 1-10.
Published
Issue
Section
License
Copyright (c) 2024 AlgoVista: Journal of AI & Computer Science
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish in this journal agree to the following terms:
- Authors retain copyright and grant the journal the right of first publication with the work simultaneously licensed under a Creative Commons Attribution 4.0 International License (CC BY 4.0) that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors can 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 acknowledgment of its initial publication in this journal.
