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.

[thumbnail of 4111413002.pdf]
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 View Item