Penyelesaian Masalah Pewarnaan pada Graf dengan Algoritma Genetika

  • Lana Aristya Anggraini Universitas Negeri Semarang
  • Isnaini Rosyida UNNES
  • Tri Sri Noor Asih UNNES
Keywords: Pewarnaan Graf, Metode heuristic, Algoritma Genetika

Abstract

Pada penelitian ini, dijelaskan langkah-langkah matematis tentang penyelesaian masalah pewarnaan graf (graph colouring) dengan menggunakan Algoritma Genetika. Langkah – langkah tersebut meliputi konstruksi nilai fitness, proses crossover, dan proses mutasi pada Algoritma Genetika untuk masalah pewarnaan graf. Untuk menyelesaikan masalah pewarnaan graf dengan Algoritma Genetika, dilakukan pengkodean kromosom berbentuk array. Kemudian kromosom tersebut dikenakan operator seleksi dengan metode roda roullet, crossover satu titik dan mutasi satu gen sehingga menjadi populasi baru. Populasi baru yang terbentuk kemudian dievaluasi dengan konstruksi nilai fitness yang dibangun untuk meminimalisir kesalahan pewarnaan dan menemukan minimal warna. Proses tersebut dilakukan hingga didapatkan generasi yang memuat penyelesaian pewarnaan graf. Penyelesaian pewarnaan graf merupakan pelabelan titik dengan minimal warna dan nol kesalahan pewarnaan. Pada penelitian ini ditambahkan rancangan program dengan  tertentu untuk evaluasi nilai fitness, operator crossover dan mutasi telah berhasil dibuat.

References

Barod, P., Hawanna, V, & Jagtap, V. 2014. Genetic and Memetic Algorithm on Graph Colouring. Scientific Journal of Impact Factor (SJIF) 1, 269-276.
Budayasa, I. K. 2007. Teori Graph dan Aplikasinya. Surabaya: Unesa University Press.
Costa, D, & Hertz, A. 1997. Ants can colour graphs, Journal of the Operational Research Society 48, 295-305.
Croitoru, C, & Adriana, A. 2002. A New Genetic Graph Coloring Heuristic. In Proceedings of The Computational Symposium on Graph Coloring and its Generalizations, 63-74. Ithaca, New York, USA.
Desiani, A, & Arhani, M. 2006. Konsep Kecerdasan Buatan. Yogyakarta: Andi Offset.
Fitriana, E. N, & Sugiharti. E. 2015. Implementasi Algoritma Genetika dengan Teknik Kendali Logika Fuzzy untuk Mengatasi TSP Menggunakan MATLAB. 2015. Unnes Journal of Mathematics, vol. 4, no. 2: 1-9.
Fleurent, C, & Ferland, J. A. 1996. “Genetic and hybrid algorithms for graph coloring,” Annals of Operations Research, vol. 63, pp. 437–461.
Glass, C. A, & Bennett, A. P. 2003. Genetic algorithm for graph coloring: Exploration of Galinier and Hao's algorithm. Journal of Combinatorial Optimization 3: 229-236
Gwee, B. H., Lim, M. H, & Ho, J. S. 1993. Solving fourcolouring map problem using genetic algorithm. In Proceedings of First New Zealand International Two-Stream Conference on Artificial Neural Networks and Expert Systems, 332-333. New Zealand.
Hertz, D. A. 1987. Using Tabu Search technique for Graph Coloring. Computing Springer Verlag 39, 345-351.
Hindi, M. M, & Yampolskiy, R. V. 2012. Genetic Algorithm Applied to the Graph Coloring Problem. Kentucky : Computer Engineering and Computer Science J.B Speed School of Engineering Louisville.
Jusuf, H. 2009. Pewarnaan Graph Pada Simpul Untuk Mendeteksi Konflik Penjadwalan Kuliah. Seminar Nasional Aplikasi Teknologi Informasi. ISSN:1907-5022.
Rosyida, I., Widodo, Indarti, Ch. R., Sugeng, K.A. 2015 A new approach for determining fuzzy chromatic number of fuzzy graph. Journal of Intelligent & Fuzzy System, 28, 2331-2341.
Sari, F. A., Dwijanto, & Sugiharti. E. 2013. Implementasi Algoritma Genetika untuk menyelesaikan Masalah Travelling Salesman Problem menggunakan Software MATLAB. Unnes Journal of Mathematics, vol. 2, no. 2: 1-5,
Susiloputro, A., Rochmad, & Alamsyah. 2012. Penerapan Pewarnaan Graf pada Penjdwalan Ujian menggunakan Algoritma Welsh Powell. Unnes Journal of Mathematics, vol. 1, no.1: 1-7.
Shen, J. W. 2003. Solving the Graph Coloring Problem using Genetic Programming, in Genetic Algorithms and Genetic Programming. Stanford 187-196.
Setyono, O. & Rusdiansyah, A. 2006. Perancangan Sistem Rute Dan Penjadwalan Pengiriman Barang Di PT. Karya Mandiri Kencana Surabaya. Prosiding Seminar Nasional Manajemen Teknologi III, Prodi MMT ITS, Surabaya.
Wibisono, S. 2008. Matematika Diskrit (2^nd ed.). Yogyakarta : Graha Ilmu.
Zukhri, Z. 2014. Algoritma Genetika: Metode Komputasi Evolusioner untuk Menyelesaikan Masalah Optimasi. Yogyakarta: Andi Offsite.
Published
2019-06-19
Section
Articles