PENYELESAIAN MASALAH PEWARNAAN PADA GRAF DENGAN ALGORITMA GENETIKA
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.
Item Type: | Thesis (Under Graduates) |
---|---|
Uncontrolled Keywords: | Pewarnaan Graf, Metode heuristic, Algoritma Genetika |
Subjects: | Q Science > QA Mathematics |
Fakultas: | Fakultas Matematika dan Ilmu Pengetahuan Alam > Matematika, S1 |
Depositing User: | Users 7 not found. |
Date Deposited: | 16 Jan 2019 15:44 |
Last Modified: | 16 Jan 2019 15:49 |
URI: | http://lib.unnes.ac.id/id/eprint/32185 |
Actions (login required)
View Item |