Application of Genetic Algorithm on Inclusive Labeling of a Graph
Abstract
As science developed, heuristic methods began to be used in graph coloring. Heuristic methods that have been used for graph coloring include Genetic Algorithm, Tabu Search, and Ant Colony Algorithm. A Genetic Algorithm is a method for solving optimization problems. In this study, the Genetic Algorithm will be used for the issue of labeling irregular vertices of inclusive distances to label any graph inclusively. We restrict an inclusive 1-distance to a simple graph using one-point crossover and mutation. The steps are a generation of random chromosomes, evaluating chromosome fitness values with tournament selection, conducting an evolutionary process consisting of one-point crossover and mutation, repeating the process until the termination criteria are met. The results of implementing the genetic algorithm on inclusive labeling can be determined by the chromatic number based on the adjacency matrix. The results of this labeling can be used as an alternative solution to the problem of inclusive labeling.
Keywords: Genetic Algorithm; graph labeling; inclusive labeling.
Abstrak
Seiring berkembangnya ilmu pengetahuan metode heuristic mulai digunakan dalam pewarnaan graf. Metode heuristic yang telah digunakan untuk pewarnaan graf antara lain Algoritma Genetika, Tabu Search, dan Algoritma Semut (Ant Colony). Algoritma Genetika merupakan metode untuk menyelesaikan masalah optimasi. Pada penelitian ini, Algoritma Genetika digunakan untuk masalah pelabelan titik tak-teratur jarak inclusive agar dapat melabeli sebarang graf secara inclusive. Kami membatasi lingkup penelitian dengan menerapkan jarak inclusive 1 pada graf sederhana, menggunakan crossover satu titik dan mutasi. Metode yang digunakan dalam penelitian ini adalah studi literatur dengan mengkaji penggunaan Algoritma Genetika pada pelabelan titik tak-teratur jarak inclusive suatu graf. Langkah-langkah yang dilakukan adalah: pembangkitan kromosom secara acak, evaluasi nilai fitness kromosom dengan tournament selection, melakukan proses evolusi yang terdiri dari crossover satu titik dan mutasi, perulangan proses sampai kriteria pemerhentian terpenuhi. Hasil implementasi algoritma genetika pada pelabelan inclusive adalah dapat mengetahui bilangan kromatik berdasarkan matriks adjacency. Hasil pelabelan ini dapat dijadikan sebagai salah satu alternatif penyelesaian masalah pelabelan inklusif.
Kata Kunci : Algoritma Genetika; pelabelan graf; pelabelan inklusif.
Keywords
References
J. Sedlacek, "Problem 27," in Theory of Graphs and it's Applications (Smolenice, 1963), Publ. House Czechoslovak Acad. Sci., Prague, 1964, pp. 163-164.
B. M. Stewart, "Magic graphs," Can. J. Math, vol. 18, pp. 1031-1059, 1966.
A. Kotzig and A. Rosa, "Magic Valuations of Finite Graph," Canad. Math. Bull., vol. 13, pp. 451-461, 1970.
Slamin, "On Distance Irregular Labelling of Graphs," Far East Journal of Mathematical Sciences (FJMS), vol. 102, no. 5, pp. 919-932, 2017.
M. "Ba" "c" ̌"a" , A. S. Fen ̌ovc ̌i ́kova ́, Slamin and K. A. Sugeng, "On Inclusive Distance Vertex Irregular Labelings," Electronic Journal of Graph Theory and Applications, vol. 6, no. 1, pp. 61-83, 2018.
B. Şahin and A. Şahin, "On Domination Polynomials of Caterpillar Graphs," Turk. J. Math. Comput. Sci., vol. 9, p. 34–38, 2018.
H. Farooq, M. N. Zakaria, M. F. Hassan, and S. Sulaiman, "An Interactive Visualization of Genetic Algorithm on 2-D Graph," International Journal of Software Science and Computational Intelligence, vol. 4, no. 1, pp. 34-54, 2020, DOI: 10.4018/jssci.2012010102.
G. Nirmala and D. Ramprasad, "Application of Genetic Algorithm in Graph Theory," International Journal of Scientific and Research Publications, vol. 2, no. 7, pp. 1-3, 2012.
M. M. Hindi and R. V. Yampolskiy, "Genetic Algorithm Applied to the Graph Coloring Problem," in Proceedings of the Twenty-third Midwest Artificial Intelligence and Cognitive Science Conference, April 21 – 22, pp. 60-66, University of Cincinnati, Ohio, 2012.
P. Barod, V. Hawanna and V. Jagtap, "Genetic Algorithm and Memetic Algorithm on Graph Colouring," Scientific Journal of Impact Factor (SJIF), vol. 1, pp. 269-276, 2014.
M. Assi, B. Halawi and R. A. Haraty, "Genetic Algorithm Analysis using the Graph Coloring Method for Solving the University Timetable Problem," Procedia Computer Science, vol. 126, p. 899–906, 2018.
L. A. Anggraini, I. Rosyida and T. S. N. Asih, "Graph Coloring Problem Solution with Genetics Algorithm," UNNES Journal of Mathematics, vol. 8, no. 1, pp. 30-39, 2019.
A. R. Savitri, I. Halikin and K. Wijaya, "On Inclusive 1-Distance Vertex Irregularity Strength of Firecracker, Broom, dan Banana Tree," in Proceeding of International Conference on Mathematics and Islam (ICMIs), pp. 228-232, Mataram, 2018.
DOI: 10.15408/inprime.v4i1.24327
Refbacks
- There are currently no refbacks.
.
