Lana Aristya Anggraini , 4111413002 (2017) PENYELESAIAN MASALAH PEWARNAAN PADA GRAF DENGAN ALGORITMA GENETIKA. Under Graduates thesis, Universitas Negeri Semarang.

Preview

PDF - Published Version Download (413kB) | Preview

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. Pewarnaan pada graf umumnya menggunakan Algoritma Welsh- Powell. Namun seiring berkembangnya ilmu pengetahuan, metode heuristic digunakan untuk mewarnai 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. Bilangan yang menyatakan minimal warna yang digunakan dalam pewarnaan titik graf disebut bilangan kromatik.

Actions (login required)

View Item