ALGORITMA GENETIK DENGAN CROSSOVER BERDASARKAN POSISI UNTUK PERSOALAN dc-MST (DEGREE-CONSTRAINED MINIMUM SPANNING TREE)

MIRZA NURIAVANI, 080012202 (2006) ALGORITMA GENETIK DENGAN CROSSOVER BERDASARKAN POSISI UNTUK PERSOALAN dc-MST (DEGREE-CONSTRAINED MINIMUM SPANNING TREE). Skripsi thesis, UNIVERSITAS AIRLANGGA.

[img]
Preview
Text (ABSTRAK)
21.pdf

Download (129kB) | Preview
[img] Text (FULL TEXT)
24600.pdf
Restricted to Registered users only

Download (2MB) | Request a copy
Official URL: http://lib.unair.ac.id

Abstract

Persoalan dc-MST (degree constrained-Minimum Spanning Tree) adalah menentukan jalur yang menghubungkan sejumlah n tempat/kota dalam jaringan yang tidak memuat cycle dan kemampuan/daya tampung dari tempat/kota tersebut dibatasi. Tujuan dari persoalan dc-MST adalah untuk meminimalkan total jarak antara tempat/kota yang terhubung langsung. Dalam skripsi ini akan digunakan suatu metode untuk menyelesaikan persoalan dc-MST, metode tersebut adalah algoritma genetik (Genetic Algorithm) dengan crossover berdasarkan posisi. Algoritma genetik merupakan algoritma yang diinspirasikan oleh teori evolusi, yang diawali dengan melakukan generate populasi awal di daerah fisibel. Melalui operator-operator genetik, yaitu seleksi, crossover, dan mutasi akan dicari solusi yang terbaik. Ada dua data yang digunakan untuk persoalan dc-MST: jarak 9 kota dan jarak 100 kota. Data-data ini diambil dari Workshop Integer Programming, data 9 kota akan diselesaikan secara manual dan menggunakan program C++. Parameter untuk 9 kota yang diselesaikan secara adalah: pop_size = 10, pc = 0,6, pm = 0,01, didapatkan solusinya sebesar 1.111 km. Untuk 9 kota yang diselesaikan dengan menggunakan program C++ dengan pop_size = 10, pc = 0,6, pm = 0,01, maksimum generasi =100, Solusi terbaiknya adalah sebesar 793 km dari generasi ke-99 individu ke-13. Untuk persoalan dc-MST dengan 100 kota akan diselesaikan dengan menggunakan program C++, parameter-parameternya antara lain: pop_size = 30, pc = 0,6, pm = 0,01, maksimum generasi = 200. Dan solusi terbaiknya adalah sebesar 23.295 km dari generasi ke-141 kromosom ke-41.

Item Type: Thesis (Skripsi)
Additional Information: KKC KK MPM. 11/06 Nur a
Uncontrolled Keywords: GENETICS ALGORITHMS, CONSTRAINTS
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA276-280 Mathematical Analysis
Divisions: 08. Fakultas Sains dan Teknologi > Matematika
Creators:
CreatorsEmail
MIRZA NURIAVANI, 080012202UNSPECIFIED
Contributors:
ContributionNameEmail
ContributorHerry Suprajitno, S.Si., M.SiUNSPECIFIED
ContributorDrs. Eto Wuryanto, DEAUNSPECIFIED
Depositing User: Tn Fariddio Caesar
Date Deposited: 19 Sep 2006 12:00
Last Modified: 07 Jun 2017 21:12
URI: http://repository.unair.ac.id/id/eprint/24600
Sosial Share:

Actions (login required)

View Item View Item