PENERAPAN ALGORITMA GENETIKA HIBRIDA DENGAN SKEMA PENCARIAN LOKAL ADAPTIF UNTUK PENYELESAIAN TRAVELING SALESMAN PROBLEM PADA ANDROID


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.

[thumbnail of 5302411080.pdf]
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.

Item Type: Thesis (Under Graduates)
Uncontrolled Keywords: Traveling Salesman Problem, Algoritma Genetika Hibrida, Pencarian Lokal, Kesamaan Koefisien.
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
T Technology > TK Electrical and Electronic Engineering
Fakultas: Fakultas Teknik > Pendidikan Teknik Informatika dan Komputer, S1
Depositing User: Users 23382 not found.
Date Deposited: 20 Jul 2016 17:59
Last Modified: 20 Jul 2016 17:59
URI: http://lib.unnes.ac.id/id/eprint/23451

Actions (login required)

View Item View Item