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

Preview	Text (ABSTRAK) 21.pdf Download (129kB) | Preview
	Text (FULL TEXT) 24600.pdf Restricted to Registered users only Download (2MB) | Request a copy

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.

Actions (login required)

View Item