Neilah Muazaroh, 080810544 (2012) NOVEL GENETIC ALGORITHM UNTUK MASALAH DEGREE-CONSTRAINED MINIMUM SPANNING TREE. Skripsi thesis, UNIVERSITAS AIRLANGGA.

Preview	Text (ABSTRAK) gdlhub-gdl-s1-2012-muazarohne-21128-5.abstr-k.pdf Download (116kB) | Preview
	Text (FULLTEXT) FULLTEXT.pdf Restricted to Registered users only Download (2MB) | Request a copy

Abstract

Skripsi ini bertujuan untuk menyelesaikan masalah degree-constrained minimum spanning tree (dc-MST) menggunakan novel genetic algorithm (NGA). Dc-MST merupakan suatu masalah penentuan jalur yang menghubungkan seluruh titik (kota) dalam suatu jaringan yang tidak memuat cycle dengan jumlah keterhubungan langsung antar titik dibatasi. Tujuan masalah dc-MST adalah meminimumkan total jarak antar titik yang terhubung langsung. Penyelesaian masalah dc-MST menggunakan NGA ini memandang masalah tersebut secara bi-objektif dengan mentransformasi masalah dc-MST menjadi dua fungsi, yaitu fungsi bobot dan fungsi fisibilitas. Algoritma ini tidak hanya melibatkan solusi fisibel tetapi juga solusi non-fisibel dengan evaluasi fungsi bobotnya menggunakan pengkodean Prüfer. NGA juga menambahkan proses local search scheme, dan menggunakan operator solusi pareto optimal untuk pencarian solusi terbaik. Contoh kasus pada skripsi ini bertujuan untuk menentukan jalur pembangunan jaringan telekomunikasi yang menghubungkan seluruh kota yang mempunyai panjang kabel minimum dimana panjang kabel tersebut diasumsikan sebagai total jarak antar kota yang terhubung langsung. Data yang digunakan yaitu data jarak 9 kota di Jawa Timur dan data jarak 100 kota di Jawa. Data-data tersebut diselesaikan menggunakan program yang dibuat dengan software Borland C++ Builder. Hasil terbaik penyelesaian masalah dc-MST menggunakan data jarak 9 kota adalah , sedangkan hasil terbaik penyelesaian masalah dc-MST menggunakan data jarak 100 kota adalah . Dibandingkan dengan beberapa penelitian sebelumnya yang menggunakan algoritma genetik, NGA mempunyai solusi yang cenderung lebih baik.

Actions (login required)

View Item