A new method for solving of the Graph Coloring Problem based on a fuzzy logic and whale optimization algorithm
محورهای موضوعی : Meta-heuresticsTaha Mostafaie 1 , Farzin Modarres khiyabani 2 , Nima Jafari Navimipour 3 , Behrooz Daneshian 4
1 - Department of Mathematic, Tabriz Branch, Islamic Azad University, Tabriz, Iran
2 - Department of Mathematic, Tabriz Branch, Islamic Azad University, Tabriz, Iran
3 - Department of Computer Engineering, Tabriz Branch, Islamic Azad University, Tabriz, Iran
4 - Department of Mathematics, Central Tehran Branch, Islamic Azad University, Tehran, Iran
کلید واژه: Graph coloring, Discrete optimization, Graph benchmark, Runtime,
چکیده مقاله :
Abstract: In recent years, Graph Coloring Problem (GCP) is one of the main optimization problems from literature. Many real world problems interacting with changing environments can be modeled by dynamic graphs. Graph vertex coloring with a given number of colors is a well-known and much-studied NP-hard problem. Meta-heuristic algorithms are a good choice to solve GCP because they are suitable for problems with NP-hard complexity. However, in many previously proposed algorithms, there are common problems such as runtime algorithm and low convergence of algorithm. Therefore, in this paper, we propose the Fuzzy Whale Optimization Algorithm (FWOA), a variety of basic Whale Optimization Algorithm (WOA), to improve runtime and convergence of algorithm in the GCP. Since WOA at first was introduced for solving continuous problem, we need a discrete WOA. Hence, to use FWOA to discrete search space, the standard arithmetic operators such as addition, subtraction and multiplication extant in FWOA encircling prey, exploitation phase and exploration phase operators based on distance’s theory needs to be redefined in the discrete space. Parameters p and r, are defined randomly in the WOA algorithm in FWOA algorithm defined as fuzzy and are selected in fuzzy tragedy. A set of graph coloring benchmark problems are solved and their performance are compared with some well-known heuristic search methods. Results illustrate that FWOA algorithm are the original focus of this work and in most cases success rate is nearly 100% and the runtime and convergence algorithm has been improved on some graphs. But as we have illustrated that comparison with other manners, we cannot deduce that our algorithm is the best in all instance of graphs. It can be said that a proposed algorithm is able to compete with other algorithms in this context. Obtained results approved the high performance of proposed method.
Abstract: In recent years, Graph Coloring Problem (GCP) is one of the main optimization problems from literature. Many real world problems interacting with changing environments can be modeled by dynamic graphs. Graph vertex coloring with a given number of colors is a well-known and much-studied NP-hard problem. Meta-heuristic algorithms are a good choice to solve GCP because they are suitable for problems with NP-hard complexity. However, in many previously proposed algorithms, there are common problems such as runtime algorithm and low convergence of algorithm. Therefore, in this paper, we propose the Fuzzy Whale Optimization Algorithm (FWOA), a variety of basic Whale Optimization Algorithm (WOA), to improve runtime and convergence of algorithm in the GCP. Since WOA at first was introduced for solving continuous problem, we need a discrete WOA. Hence, to use FWOA to discrete search space, the standard arithmetic operators such as addition, subtraction and multiplication extant in FWOA encircling prey, exploitation phase and exploration phase operators based on distance’s theory needs to be redefined in the discrete space. Parameters p and r, are defined randomly in the WOA algorithm in FWOA algorithm defined as fuzzy and are selected in fuzzy tragedy. A set of graph coloring benchmark problems are solved and their performance are compared with some well-known heuristic search methods. Results illustrate that FWOA algorithm are the original focus of this work and in most cases success rate is nearly 100% and the runtime and convergence algorithm has been improved on some graphs. But as we have illustrated that comparison with other manners, we cannot deduce that our algorithm is the best in all instance of graphs. It can be said that a proposed algorithm is able to compete with other algorithms in this context. Obtained results approved the high performance of proposed method.
Abbasian, R. and M. Mouhoub An efficient hierarchical parallel genetic algorithm for graph coloring problem, ACM.
Abbasian, R. and M. Mouhoub (2013). "A hierarchical parallel genetic approach for the graph coloring problem." Applied intelligence 39(3): 510-528.
Agnarsson, G. and R. Greenlaw (2007). Graph theory: Modeling, applications, and algorithms, Pearson/Prentice Hall.
Alves, M. S., J. R. Nascimento and U. S. Souza (2021). "On the complexity of coloring‐graphs." International Transactions in Operational Research 28(6): 3172-3189.
Astuti, W. (2015). "Graph Coloring Based on Evolutionary Algorithms to Support Data Hiding Scheme on Medical Images." Procedia Computer Science 74: 173-177.
Bensouyad, M. and D. Saidouni A discrete flower pollination algorithm for graph coloring problem, IEEE.
Biggs, N., N. L. Biggs and E. N. Biggs (1993). Algebraic graph theory, Cambridge university press.
Bui, T. N., T. H. Nguyen, C. M. Patel and K.-A. T. Phan (2008). "An ant-based algorithm for coloring graphs." Discrete Applied Mathematics 156(2): 190-200.
Chen, K. and H. Kanoh A discrete firefly algorithm based on similarity for graph coloring problems, IEEE.
Chiarandini, M. and T. Stützle An analysis of heuristics for vertex colouring, Springer.
Cui, G., L. Qin, S. Liu, Y. Wang, X. Zhang and X. Cao (2008). "Modified PSO algorithm for solving planar graph coloring problem." Progress in Natural Science 18(3): 353-357.
Deo, N. (2017). Graph theory with applications to engineering and computer science, Courier Dover Publications.
Djeloul, H., A. Layeb and S. Chikhi (2015). "Quantum Inspired Cuckoo Search Algorithm for Graph Coloring Problem." Quantum 22: 23.
Douiri, S. M. and S. Elbernoussi (2015). "Solving the graph coloring problem via hybrid genetic algorithms." Journal of King Saud University-Engineering Sciences 27(1): 114-118.
Evans, J. (2017). Optimization algorithms for networks and graphs, Routledge.
Faraji, M. and H. H. S. Javadi (2011). "Proposing a new algorithm based on bees behavior for solving graph coloring." International Journal Contemp. Math. Sciences 6(1): 41-49.
Fister Jr, I., X.-S. Yang, I. Fister and J. Brest (2012). "Memetic firefly algorithm for combinatorial optimization." arXiv preprint arXiv:1204.5165.
Galinier, P. and A. Hertz (2006). "A survey of local search methods for graph coloring." Computers & Operations Research 33(9): 2547-2562.
Goudet, O., C. Grelier and J.-K. Hao (2021). "A deep learning guided memetic framework for graph coloring problems." arXiv preprint arXiv:2109.05948.
Grimaldi, R. P. (2000). Discrete mathematics and combinational 1, Fatemi.
Guichard, D. (2017). "An Introduction to Combinatorics and Graph Theory." Whitman College-Creative Commons.(Cité en pages 33, 63 et 98.).
Han, L. and Z. Han A novel bi-objective genetic algorithm for the graph coloring problem, IEEE.
Hindi, M. and R. V. Yampolskiy Genetic Algorithm Applied to the Graph Coloring Problem.
Hsu, L.-Y., S.-J. Horng, P. Fan, M. K. Khan, Y.-R. Wang, R.-S. Run, J.-L. Lai and R.-J. Chen (2011). "MTPSO algorithm for solving planar graph coloring problem." Expert systems with Applications 38(5): 5525-5531.
Jensen, T. R. and B. Toft (2011). Graph coloring problems, John Wiley & Sons.
Kamath, V. and A. Pai (2018). "Applications of Graph Theory in Molecular Similarity Measurements." Research Journal of Pharmacy and Technology 11(4): 1375-1377.
Kaveh, A. and M. I. Ghazaan (2017). "Enhanced whale optimization algorithm for sizing optimization of skeletal structures." Mechanics Based Design of Structures and Machines 45(3): 345-362.
Kokosinski, Z. and Ł. Ochał Evaluation of metaheuristics for robust graph coloring problem, IEEE.
Mahmoudi, S. and S. Lotfi (2015). "Modified cuckoo optimization algorithm (MCOA) to solve graph coloring problem." Applied soft computing 33: 48-64.
Menaka, S. and J. Arthy "Study on complete coloring graph."
Mirjalili, S. and A. Lewis (2016). "The whale optimization algorithm." Advances in Engineering Software 95: 51-67.
Abbasian, R. and M. Mouhoub An efficient hierarchical parallel genetic algorithm for graph coloring problem, ACM.
Abbasian, R. and M. Mouhoub (2013). "A hierarchical parallel genetic approach for the graph coloring problem." Applied intelligence 39(3): 510-528.
Agnarsson, G. and R. Greenlaw (2007). Graph theory: Modeling, applications, and algorithms, Pearson/Prentice Hall.
Alves, M. S., J. R. Nascimento and U. S. Souza (2021). "On the complexity of coloring‐graphs." International Transactions in Operational Research 28(6): 3172-3189.
Astuti, W. (2015). "Graph Coloring Based on Evolutionary Algorithms to Support Data Hiding Scheme on Medical Images." Procedia Computer Science 74: 173-177.
Bensouyad, M. and D. Saidouni A discrete flower pollination algorithm for graph coloring problem, IEEE.
Biggs, N., N. L. Biggs and E. N. Biggs (1993). Algebraic graph theory, Cambridge university press.
Bui, T. N., T. H. Nguyen, C. M. Patel and K.-A. T. Phan (2008). "An ant-based algorithm for coloring graphs." Discrete Applied Mathematics 156(2): 190-200.
Chen, K. and H. Kanoh A discrete firefly algorithm based on similarity for graph coloring problems, IEEE.
Chiarandini, M. and T. Stützle An analysis of heuristics for vertex colouring, Springer.
Cui, G., L. Qin, S. Liu, Y. Wang, X. Zhang and X. Cao (2008). "Modified PSO algorithm for solving planar graph coloring problem." Progress in Natural Science 18(3): 353-357.
Deo, N. (2017). Graph theory with applications to engineering and computer science, Courier Dover Publications.
Djeloul, H., A. Layeb and S. Chikhi (2015). "Quantum Inspired Cuckoo Search Algorithm for Graph Coloring Problem." Quantum 22: 23.
Douiri, S. M. and S. Elbernoussi (2015). "Solving the graph coloring problem via hybrid genetic algorithms." Journal of King Saud University-Engineering Sciences 27(1): 114-118.
Evans, J. (2017). Optimization algorithms for networks and graphs, Routledge.
Faraji, M. and H. H. S. Javadi (2011). "Proposing a new algorithm based on bees behavior for solving graph coloring." International Journal Contemp. Math. Sciences 6(1): 41-49.
Fister Jr, I., X.-S. Yang, I. Fister and J. Brest (2012). "Memetic firefly algorithm for combinatorial optimization." arXiv preprint arXiv:1204.5165.
Galinier, P. and A. Hertz (2006). "A survey of local search methods for graph coloring." Computers & Operations Research 33(9): 2547-2562.
Goudet, O., C. Grelier and J.-K. Hao (2021). "A deep learning guided memetic framework for graph coloring problems." arXiv preprint arXiv:2109.05948.
Grimaldi, R. P. (2000). Discrete mathematics and combinational 1, Fatemi.
Guichard, D. (2017). "An Introduction to Combinatorics and Graph Theory." Whitman College-Creative Commons.(Cité en pages 33, 63 et 98.).
Han, L. and Z. Han A novel bi-objective genetic algorithm for the graph coloring problem, IEEE.
Hindi, M. and R. V. Yampolskiy Genetic Algorithm Applied to the Graph Coloring Problem.
Hsu, L.-Y., S.-J. Horng, P. Fan, M. K. Khan, Y.-R. Wang, R.-S. Run, J.-L. Lai and R.-J. Chen (2011). "MTPSO algorithm for solving planar graph coloring problem." Expert systems with Applications 38(5): 5525-5531.
Jensen, T. R. and B. Toft (2011). Graph coloring problems, John Wiley & Sons.
Kamath, V. and A. Pai (2018). "Applications of Graph Theory in Molecular Similarity Measurements." Research Journal of Pharmacy and Technology 11(4): 1375-1377.
Kaveh, A. and M. I. Ghazaan (2017). "Enhanced whale optimization algorithm for sizing optimization of skeletal structures." Mechanics Based Design of Structures and Machines 45(3): 345-362.
Kokosinski, Z. and Ł. Ochał Evaluation of metaheuristics for robust graph coloring problem, IEEE.
Mahmoudi, S. and S. Lotfi (2015). "Modified cuckoo optimization algorithm (MCOA) to solve graph coloring problem." Applied soft computing 33: 48-64.
Menaka, S. and J. Arthy "Study on complete coloring graph."
Mirjalili, S. and A. Lewis (2016). "The whale optimization algorithm." Advances in Engineering Software 95: 51-67.
Mondal, B. and K. De (2017). "Overview Applications of Graph Theory in Real Field." International Journal of Scientific Research in Computer Science, Engineering and Information Technology 2(5): 751-759.
Morris, J. and F. Song (2021). "Simple vertex coloring algorithms." arXiv preprint arXiv:2102.07089.
Mostafaie, T., F. M. Khiyabani and N. J. Navimipour (2020). "A systematic study on meta-heuristic approaches for solving the graph coloring problem." Computers & Operations Research 120: 104850.
Pal, A. J., B. Ray, N. Zakaria and S. S. Sarma (2012). "Comparative performance of modified simulated annealing with simple simulated annealing for graph coloring problem." Procedia Computer Science 9: 321-327.
Panda, P. R., N. D. Dutt and A. Nicolau (1997). "Memory data organization for improved cache performance in embedded processor applications." ACM Transactions on Design Automation of Electronic Systems (TODAES) 2(4): 384-409.
Postigo, J., J. Soto-Begazo, V. R. Fiorela, G. M. Picha, R. Flores-Quispe and Y. Velazco-Paredes (2021). Comparative Analysis of the main Graph Coloring Algorithms. 2021 IEEE Colombian Conference on Communications and Computing (COLCOM), IEEE.
Rao, N. S. V. (1993). "Computational complexity issues in operative diagnosis of graph-based systems." IEEE Transactions on Computers 42(4): 447-457.
Schmidt, C., N.-E. Guenther and L. Zdeborová (2016). "Circular coloring of random graphs: statistical physics investigation." Journal of Statistical Mechanics: Theory and Experiment 2016(8): 083303.
Tomar, R. S., S. Singh, S. Verma and G. S. Tomar A novel abc optimization algorithm for graph coloring problem, IEEE.
Trinajstic, N. (2018). Chemical graph theory, Routledge.
Trudeau, R. J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.), New York: Dover Pub.
Vecchio, D. A., S. H. Mahler, M. D. Hammig and N. A. Kotov (2021). "Structural Analysis of Nanoscale Network Materials Using Graph Theory." ACS nano 15(8): 12847-12859.
Xu, Y. and Y. Chen (2021). "A Cuckoo Quantum Evolutionary Algorithm for the Graph Coloring Problem." arXiv preprint arXiv:2108.08691.
Zhou, J., S.-C. Fang and W. Xing (2017). "Graph coloring is a classical NP-hard combinatorial optimization problem with many practical applications. A broad range of heuristic methods exist for tackling the graph coloring problem: from fast greedy algorithms to more time-consuming metaheuristics. Although the latter produce better results in terms of minimizing the number of colors, the former are widely employed due to their simplicity." Computational Optimization and Applications 66(1): 163-185.
