Teguh Narwadi, 5302411080 (2015) PENERAPAN ALGORITMA GENETIKA HIBRIDA DENGAN SKEMA PENCARIAN LOKAL ADAPTIF UNTUK PENYELESAIAN TRAVELING SALESMAN PROBLEM PADA ANDROID. Under Graduates thesis, Universitas Negeri Semarang.

Preview

PDF Download (1MB) | Preview

Abstract

Algoritma genetika (GA) merupakan teknik pencarian berbasis populasi yang digunakan untuk menemukan perkiraan solusi terbaik dalam masalah optimasi seperti mendapatkan jarak optimal dalam kasus traveling salesman problem (TSP). Dimana permasalahan utama TSP adalah menemukan rute dengan jarak minimal. Namun terdapat kelemahan dari GA yaitu ketika terjebak pada optimal lokal dan tidak mampu melepaskan diri, sehingga kinerjanya terus memburuk. Salah satu metode perbaikan kelemahan tersebut dengan algoritma genetika hibrida dengan skema pencarian lokal adaptif (HGA). Dalam penelitian ini menyajikan pengaplikasian dari HGA untuk menyelesaian TSP secara efektif. Aplikasi ini dikembangkan pada android karena android saat ini telah banyak digunakan oleh sebagian besar masyarakat dunia dan bersifat mobile. Penggunaan teknik pencarian lokal digunakan untuk mencari solusi terbaik dari populasi. Jika ditemukan solusi yang lebih baik maka solusi GA diganti dengan solusi yang lebih baik. Untuk mengefektifkan penggunaan pencarian lokal digunakan skema pencarian lokal yang dapat secara otomatis mengontrol penggunaan teknik pencarian lokal kedalam GA sehingga pencarian lokal menjadi adaptif. Solusi terbaik yang dihasilkan oleh algoritma ditampilkan kedalam Google Maps pada Android. Dalam pengujian, untuk menguji efektivitas HGA dengan skema pencarian lokal adaptif dibandingkan dengan GA tanpa pencarian lokal dengan 5 sample kabupaten/kota di Jawa Tengah dengan jumlah kota yang berbeda. Setiap sampel TSP dilakukan simulasi sebanyak 10 kali menggunakan parameter yang telah ditentukan. Hasil pengujian diperoleh bahwa solusi rata-rata HGA menunjukkan dalam 5 pengujian dari 5 sampel (100%) lebih baik dari GA. Waktu komputasi yang dibutuhkan oleh HGA terhitung paling lama dari 5 sampel pengujian TSP. Hasil penelitian menunjukkan bahwa algoritma genetika hibrida dengan skema pencarian lokal lebih efektif dibandingkan algoritma genetika tanpa pencarian lokal dalam menemukan rute perjalanan dengan jarak yang optimal terutama dalam kasus dengan masalah yang kompleks. Akan tetapi beban komputasi algoritma genetika hibrida lebih lama dalam menemukan jarak yang optimal.

Actions (login required)

View Item