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.