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

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

Skripsi diajukan sebagai salah satu syarat untuk memproleh gelar Sarjana Pendidikan Program Studi Pendidikan Teknik Informatika dan Komputer

Oleh Teguh Narwadi NIM.5302411080

JURUSAN TEKNIK ELEKTRO FAKULTAS TEKNIK

UNIVERSITAS NEGERI SEMARANG 2015

PERNYATAAN KEASLIAN TULISAN

Dengan ini saya menyatakan bahwa: 1. Skripsi ini, adalah asli dan belum pernah diajukan untuk mendapatkan gelar akademik (sarjana, magister, dan/atau doktor), baik di Universitas Negeri Semarang (UNNES) maupun di perguruan tinggi lain. 2. Karya tulis ini adalah murni gagasan, rumusan, dan penelitian saya sendiri tanpa bantuan pihak lain, kecuali arahan Pembimbing dan masukan Tim Penguji. 3. Dalam karya tulis ini tidak terdapat karya atau pendapat yang telah ditulis atau dipublikasikan orang lain, kecuali secara tertulis dengan jelas dicantumkan sebagai acuan dalam naskah dengan disebutkan nama pengarang dan dicantumkan dalam daftar pustaka. 4. Pernyataan ini saya buat dengan sesungguhnya dan apabila dikemudian hari terdapat penyimpangan dan ketidakbenaran dalam pernyataan ini, maka saya bersedia menerima sanksi akademik berupa pencabutan gelar yang telah diperoleh karena karya ini, serta sanksi lainnya sesuai dengan norma yang berlaku di perguruan tinggi ini.

Semarang, Oktober 2015

ii

PERSETUJUAN PEMBIMBING

Nama

: Teguh Narwadi

NIM

: 5302411080

Program Studi : S – 1 Pendidikan Teknik Informatika dan Komputer Judul Skripsi : Penerapan Algoritma Genetika Hibrida Dengan Skema Pencarian Lokal Adaptif Untuk Penyelesaian Traveling Salesman Problem Pada Android Skripsi ini telah disetujui oleh pembimbing untuk diajukan ke sidang panitia ujian skripsi Program Studi S-1 Pendidikan Teknik Informatika dan Komputer Jurusan Teknik Elektro FT. UNNES.

Semarang, 28 September 2015

iii

PENGESAHAN

Skripsi dengan judul Penerapan Algoritma Genetika Hibrida Dengan Skema Pencarian Lokal Adaptif Untuk Penyelesaian Traveling Salesman Problem pada Android telah dipertahankan di depan sidang Panitia Ujian Skripsi Fakultas Teknik UNNES pada tanggal

Oktober 2015. Oleh

Nama

: Teguh Narwadi

NIM

: 5302411080

Program Studi : Pendidikan Teknik Informatika dan Komputer

iv

MOTTO DAN PERSEMBAHAN

Motto: 

Sesuatu yang belum dikerjakan, seringkali tampak mustahil, kita baru yakin kalau kita melakukannya dengan baik. (Evelyn Underhill)



Jangan biarkan opini orang-orang menghalangimu dari suara hatimu. Dan yang paling penting, milikilah keberanian untuk mengikuti nurani dan intuisimu. (Steve Jobs)



Jangan kecewa apabila hasil yang diperoleh tidak seperti yang diharapkan, percaya bahwa semuanya adalah kesuksesan, bukan kegagalan. (Thomas Alva Edison)

Persembahan:  Tuhan Yang Maha Esa 

Bapak, Ibu, Adik, beserta keluarga tercinta yang tak henti-hentinya memberikan doa, semangat, dan dukungan.

 Teman-teman seperjuangan Pendidikan Teknik Informatika dan Komputer angkatan 2011.  Sahabat-sahabatku kos yang telah memberikan semangat.

v

KATA PENGANTAR

Segala puji dan syukur penulis ucapkan kehadirat Allah SWT dan mengharapkan ridho yang telah melimpahkan rahmat-Nya sehingga dapat diselesaikan penyusunan skripsi yang berjudul “Penerapan Algoritma Genetika Hibrida Dengan Adaptasi Skema Pencarian Lokal Untuk Traveling Salesman Problem Pada Android”. Skripsi ini disusun sebagai salah satu persyaratan meraih gelar Sarjana Pendidikan pada Program Studi Pendidikan Teknik Informatika dan Komputer Universitas Negeri Semarang. Dalam penyusunan skripsi ini tidak bisa lepas dari dukungan berbagai pihak. Oleh sebab itu pada kesempatan ini ingin diberikan rasa hormat dan ucapan terima kasih kepada, 1.

Prof. Dr. Fathur Rokhman, M.Hum., Rektor Universitas Negeri Semarang yang telah memberikan kesempatan kepada saya untuk belajar di Universitas Negeri Semarang.

2.

Dr. Nur Qudus, M.T., Dekan Fakultas Teknik Universitas Negeri Semarang yang telah memberikan ijin untuk melaksanakan penelitian.

3.

Drs. Suryono, M.T., Ketua Jurusan Teknik Elektro Fakultas Teknik Universitas Negeri Semarang yang telah memberikan kesempatan untuk memaparkan gagasan dalam bentuk skripsi ini.

vi

4.

Feddy Setio Pribadi, S.Pd., M.T., Ketua Prodi Pendidikan Teknik Informatika dan Komputer Fakultas Teknik Universitas Negeri Semarang yang telah membantu dalam administrasi penelitian.

5.

Dr. Ir. Subiyanto, ST, MT, Dosen pembimbing yang telah memberikan bimbingan, pengarahan, saran, dan motivasi kepada saya dalam penyusunan skripsi ini.

6.

Segenap dosen jurusan Teknik Elektro Fakultas Teknik Universitas Negeri Semarang yang telah banyak membekali ilmu pengetahuan.

7.

Teman-teman mahasiswa PTIK UNNES angkatan 2011 yang saling memberikan semangat dan perhatian.

8.

Semua pihak yang telah membantu dalam penyusunan skripsi ini. Penulis hanya bisa memanjatkan doa semoga semua pihak yang telah

membantu penulis dalam penyusunan skripsi ini mendapatkan pahala dari Allah SWT. Penulis berharap semoga skripsi ini bermanfaat bagi semua pihak khususnya bagi penulis sendiri dan masyarakat serta pembaca pada umumnya.

Semarang,

Penulis

vii

Oktober 2015

ABSTRAK Narwadi, Teguh. 2015. Penerapan Algoritma Genetika Hibrida Dengan Skema Pencarian Lokal Adaptif Untuk Penyelesaian Traveling Salesman Problem pada Android. Skripsi, Jurusan Teknik Elektro, Program Studi Pendidikan Teknik Informatika dan Komputer, Fakultas Teknik, Universitas Negeri Semarang. Dr. Ir. Subiyanto S.T., M.T. Kata Kunci: Traveling Salesman Problem, Algoritma Genetika Hibrida, Pencarian Lokal, Kesamaan Koefisien. 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.

viii

DAFTAR ISI Halaman HALAMAN JUDUL ................................................................................................ i PERNYATAAN KEASLIAN TULISAN .............................................................. ii PERSETUJUAN PEMBIMBING .......................................................................... iii PENGESAHAN ..................................................................................................... iv MOTTO DAN PERSEMBAHAN .......................................................................... v KATA PENGANTAR ........................................................................................... vi ABSTRAK ........................................................................................................... viii DAFTAR ISI .......................................................................................................... ix DAFTAR TABEL ................................................................................................. xii DAFTAR GAMBAR ........................................................................................... xiii DAFTAR LAMPIRAN ........................................................................................ xvi BAB I PENDAHULUAN ....................................................................................... 1 1.1

Latar Belakang Masalah ............................................................................... 1

1.2

Rumusan Masalah ........................................................................................ 3

1.3

Batasan Masalah........................................................................................... 4

1.4

Tujuan Penelitian ......................................................................................... 5

1.5

Manfaat Penelitian ....................................................................................... 5

ix

1.6

Sistematika Penulisan .................................................................................. 5

BAB II TINJAUAN PUSTAKA............................................................................. 7 2.1

Penelitian Terdahulu .................................................................................... 7

2.2

Landasan Teori ............................................................................................. 9 2.2.1

Traveling Salesman Problem ............................................................ 9

2.2.2

Algoritma Genetika ......................................................................... 11

2.2.3

Pencarian Lokal ............................................................................... 18

2.2.4

Skema Pencarian Lokal Adaptif...................................................... 19

2.2.5

Algoritma Genetika Hibrida ............................................................ 21

2.2.6

Android ........................................................................................... 23

BAB III METODE PENELITIAN........................................................................ 28 3.1

Studi Pustaka .............................................................................................. 28

3.2

Analisis Permasalahan ............................................................................... 28

3.3

Mapping HGA dengan skema pencarian lokal adaptif pada TSP .............. 30 3.3.1

Algoritma Genetika untuk menyelesaikan TSP .............................. 30

3.3.2

Algoritma Genetika Hibrida Dengan Skema Pencarian Lokal

Adaptif untuk menyelesaikan TSP ................................................................ 34 3.4

Tahap Pengembangan Sistem .................................................................... 37 3.4.1

Analisis Hardware dan Software ..................................................... 37

3.4.2

Desain Sistem TSP .......................................................................... 38

x

3.5

3.6

Implementasi .............................................................................................. 43 3.5.1

Integrasi Google Maps .................................................................... 43

3.5.2

Pengkodean ..................................................................................... 44

Pengujian .................................................................................................... 51

BAB IV HASIL DAN PEMBAHASAN .............................................................. 54 4.1

Hasil Penelitian .......................................................................................... 54

4.1.1

Hasil Sistem TSP pada Android ......................................................... 54

4.1.2

Hasil Pengujian ................................................................................... 58

4.2

Pembahasan ................................................................................................ 64

4.2.1

Perbandingan Hasil Pengujian ............................................................ 64

4.2.2

Analisis Hasil Pengujian ..................................................................... 67

4.2.3

Analisis Penggunaan Pencarian Lokal dalam HGA ........................... 75

4.2.4

Komparasi dengan penelitian lain....................................................... 79

4.2.5

Hambatan Penelitian ........................................................................... 80

BAB V PENUTUP ................................................................................................ 82 5.1

Simpulan .................................................................................................... 82

5.2

Saran ........................................................................................................... 82

DAFTAR PUSTAKA ........................................................................................... 83 LAMPIRAN .......................................................................................................... 85

xi

DAFTAR TABEL Halaman Tabel 3.1 Sampel 5 Kota ...................................................................................... 30 Tabel 3.2 Jarak Antar Kota ................................................................................... 31 Tabel 3.3 Populasi Awal ...................................................................................... 31 Tabel 3.4 Inverse fungsi objektif ke fungsi fitness .............................................. 32 Tabel 3.5 Populasi Baru ....................................................................................... 34 Tabel 3.6 Individu baru yang dihasilkan .............................................................. 36 Tabel 3.7 Daftar Kabupaten/Kota di Jawa Tengah .............................................. 51 Tabel 4.1 Hasil percobaan data case1................................................................... 59 Tabel 4.2 Hasil percobaan data case2................................................................... 60 Tabel 4.3 Hasil percobaan data case3................................................................... 61 Tabel 4.4 Hasil percobaan data case4................................................................... 62 Tabel 4.5 Hasil percobaan data case5................................................................... 63 Tabel 4.6 Perbandingan Hasil Pengujian Jarak .................................................... 64 Tabel 4.7 Perbandingan Hasil Pengujian Waktu Komputasi ............................... 66

xii

DAFTAR GAMBAR Halaman Gambar 2.1 Posisi kota-kota yang akan dilewati ................................................ 10 Gambar 2.2 Kerangka Kerja Algoritma Genetika (Zukhri, 2014) ...................... 12 Gambar 2.3 Proses Seleksi Turnamen ................................................................. 16 Gambar 2.4 Proses order crossover ..................................................................... 17 Gambar 2.5 Proses Exchange Crossover ............................................................. 18 Gambar 2.6 Tampilan Awal Peta ........................................................................ 26 Gambar 2.7 Contoh Penggunaan Markers ........................................................... 27 Gambar 2.8 Contoh Penggunaan Polyline ........................................................... 28 Gambar 3.1 Desain Penelitian dan Pengambangan HGA ................................... 29 Gambar 3.2 Permintaan marker pada Google Maps ........................................... 39 Gambar 3.3 Alur proses sistem yang berjalan ..................................................... 40 Gambar 3.4 Tampilan Dashbord Admin ............................................................. 41 Gambar 3.5 Tampilan Halaman Awal User ........................................................ 41 Gambar 3.6 Tampilan Halaman Input Kota ........................................................ 42 Gambar 3.7 Tampilan Halaman Hasil Perhitungan Algoritma ........................... 42 Gambar 3.8 Source code fungsi objektif ............................................................. 44

xiii

Gambar 3.9 Source code seleksi turnamen .......................................................... 45 Gambar 3.10 Source code order crossover .......................................................... 46 Gambar 3.11 Source code swap mutasi ............................................................... 46 Gambar 3.12 Source code algoritma genetika ..................................................... 47 Gambar 3.13 Source code hill climbing .............................................................. 47 Gambar 3.14 Source code cosine similarity ........................................................ 49 Gambar 3.15 Source code cosine similarity dalam populasi ............................... 50 Gambar 3.16 Source code fungsi HGA ............................................................... 50 Gambar 4.1 Tampilan Halaman Utama Aplikasi ................................................ 54 Gambar 4.2 Tampilan Halaman Select Kota ....................................................... 55 Gambar 4.3 Tampilan Halaman Markers Kota ................................................... 56 Gambar 4.4 Tampilan Halaman Pilih Algoritma ................................................ 56 Gambar 4.5 Tampilan Halaman Hasil Perhitungan ............................................. 57 Gambar 4.6 Tampilan Dashboard Admin ........................................................... 58 Gambar 4.7 Tampilan Halaman Tentang Aplikasi .............................................. 58 Gambar 4.8 Grafik Jarak Perjalanan pada Case1 ................................................ 67 Gambar 4.9 Grafik Jarak Perjalanan pada Case2 ................................................ 68 Gambar 4.10 Grafik Jarak Perjalanan pada Case3 .............................................. 69 Gambar 4.11 Grafik Jarak Perjalanan pada Case4 .............................................. 69

xiv

Gambar 4.12 Grafik Jarak Perjalanan pada Case5 .............................................. 70 Gambar 4.13 Grafik Waktu Komputasi pada Case1 ........................................... 72 Gambar 4.14 Grafik Waktu Komputasi pada Case2 ........................................... 72 Gambar 4.15 Grafik Waktu Komputasi pada Case3 ........................................... 73 Gambar 4.16 Grafik Waktu Komputasi pada Case4 ........................................... 74 Gambar 4.17 Grafik Waktu Komputasi pada Case5 ........................................... 74 Gambar 4.18 Presentase Pencarian Lokal dalam HGA pada Case1.................... 76 Gambar 4.19 Presentase Pencarian Lokal dalam HGA pada Case2.................... 76 Gambar 4.20 Presentase Pencarian Lokal dalam HGA pada Case3.................... 77 Gambar 4.21 Presentase Pencarian Lokal dalam HGA pada Case4.................... 78 Gambar 4.22 Presentase Pencarian Lokal dalam HGA pada Case5.................... 78

xv

DAFTAR LAMPIRAN Halaman Lampiran 1. Hasi Sistem Algoritma Penyelesaian TSP ...................................... 85 Lampiran 2. Hasil Rute Perjalanan Optimal Menggunakan HGA ...................... 87 Lampiran 3. Grafik Nilai Fitness HGA ............................................................... 88 Lampiran 4. Hasil Penggunaan Pencarian Lokal ................................................ 89 Lampiran 5. Surat Penetapan Dosen Pembimbing ............................................ 102

xvi

BAB I PENDAHULUAN

1.1 Latar Belakang Masalah Traveling Salesman Problem (TSP) adalah masalah klasik optimasi kombinatorial dan telah diaplikasikan dalam planning, scheduling, sequencing dan vehicle routing problem (Rafsanjani, et al., 2015). TSP merupakan permasalahan rute perjalanan untuk mengunjungi banyak kota dan setiap kota dikunjungi satu kali, dimulai dan diakhiri pada kota yang sama dimana jarak perjalanan minimal (Bryant, 2000). Dalam teori kompleksitas komputasi, TSP termasuk dalam kelas masalah NP-hard (non-deterministic polynomial-time hard), dengan demikian, bahwa tidak ada algoritma yang menjamin untuk mendapatkan rute yang optimal dalam waktu singkat (Berninger, 2014). Satu metode yang pasti akan menemukan solusi optimal dari TSP adalah penghitungan

menyeluruh

dan

evaluasi.

Prosedur

ini

dimulai

dengan

membangkitkan kemungkinan semua perjalanan dan mengevaluasinya sesuai panjang perjalanan. Perjalanan dengan panjang terkecil dipilih sebagai yang terbaik, dan dijamin akan optimal (Homaifar, et al., 1992). Dalam penelitian yang dilakukan oleh Adullah Homaifar (1992) jika mampu mengidentifikasi dan mengevaluasi satu tur pernanodetik (atau satu miliar tur per detik), maka

1

2

diperlukan hampir sepuluh juta tahun (jumlah kemungkinan tur = 3.2 ×

)

untuk mengevaluasi semua tur pada 25 kota TSP. Untuk dapat menghasilkan solusi optimal dalam waktu yang singkat pada TSP diperlukan sebuah metode heuristik. Beberapa metode heuristik yang biasa digunakan untuk menyelesaikan TSP adalah Simulated Annealing, Tabu Search, Ant Colony Optimization, Artificial Immune System, dan Genetic Algorithm (Zukhri, 2014: 10). Genetic Algorithm/ Algoritma Genetika (GA) merupakan teknik pencarian berbasis populasi yang digunakan untuk menemukan perkiraan solusi terbaik dalam masalah optimasi menggunakan operator genetik (Reese, 2009). GA dapat menjadi alternatif untuk menyelesaikan TSP, karena telah terbukti lebih efisien dalam menemukan solusi optimal atau mendekati optimal (Chang, et al., 2010; Changdar, et al., 2013; Gupta dan Panwar, 2013). Terdapat kelemahan besar didalam GA bahwa ketika terjebak pada lokal optimum, kinerja GA terus memburuk dan tidak ada cara untuk melepaskan diri (Yun, et al., 2009). Oleh karena itu, GA terkadang tidak mampu menemukan solusi optimal untuk masalah TSP. Salah satu metode untuk mengatasi kelemahan tersebut adalah hibridisasi dengan teknik pencarian lokal. Teknik ini dapat meningkatkan performa dari GA dengan dengan memasukkan individu baru terbaik ke dalam perulangan GA (Zhao, et al, 2009; Ahmed, 2013; Wang, 2014). Penelitian

ini

menyajikan

pengaplikasian

dari

hibridisasi

GA

dengan

menggunakan skema pencarian lokal adaptif untuk menyelesaikan TSP. Skema pencarian lokal tersebut dapat mengontorol penggunaan teknik pencarian lokal kedalam perulangan GA. HGA dengan skema pencarian lokal adaptif telah

3

terbukti efektif dibandingkan dengan GA tanpa pencarian lokal dalam menyelesaikan permasalahan optimasi seperti TSP (Yun, et al., 2009; Rafsanjani, et al., 2015).

Kebutuhan aplikasi untuk menentukan rencana perjalanan dengan rute yang optimal dibutuhkan banyak perusahaan pada saat ini. Sebagai contoh, pada perusahaan jasa pengiriman barang seperti JNE, TIKI, dan POS Indonesia, dimana seorang kurir/ salesman harus mengirimkan barang kepada konsumen dengan tempat tujuan yang berbeda-beda. Tujuan dari perusahaan tersebut adalah untuk mendapatkan keuntungan yang maksimal sehingga aplikasi yang mampu memandu para kurir dan menentukan rute perjalanan yang optimal (dengan jarak yang minimal) dibutuhkan untuk mencapai tujuan tersebut. Aplikasi tersebut dikembangkan pada android karena android merupakan sistem operasi yang paling banyak digunakan diseluruh dunia berdasarkan installed base dari semua sistem operasi pada tahun 2015 (Manjoo, 2015). Selain itu android bersifat mobile yang tentunya mudah untuk dibawa dan telah terintegrasi dengan Google Maps. Dalam penelitian ini, penulis mengangkat judul Penerapan Algoritma Genetika Dengan Skema Teknik Pencarian Lokal Adaptif untuk Penyelesaian Traveling Salesman Problem pada Android.

1.2 Rumusan Masalah Berdasarkan latar belakang di atas, kelemahan GA ketika terjebak dapat keadaan optimal lokal, yang mengakibatkan GA terkadang tidak mampu menemukan solusi optimal untuk masalah TSP. Kelemahan tersebut dapat

4

ditingkatkan menggunakan HGA dengan skema pencarian lokal adaptif, yang secara otomatis dapat mengontrol penggunaan teknik pencarian lokal kedalam GA secara efektif. Sehingga dapat dirumuskan masalah, bagaimanakah menerapkan Algoritma Genetika Hibrida dengan Skema Pencarian Lokal Adaptif secara efektif dalam menyelesaikan Traveling Salesman Problem pada Android.

1.3 Batasan Masalah Berdasarkan masalah diatas maka dalam penelitian ini, permasalahan dibatasi sebagai berikut: a.

Rute perjalanan yang digunakan dalam lingkup antar kota-kota di provinsi Jawa Tengah.

b.

Data jarak perjalanan diperoleh dari penghitungan jarak antar dua kota, menggunakan fungsi jarak.

c.

Penentuan rute optimum, dimana penjumlahan jarak-jarak semua kota yang dikunjungi paling kecil/ terpendek berarti rute yang paling optimal.

d.

Perencanaan perjalanan kota-kota yang akan dikunjungi ditampilkan menggunakan Markers dalam Google Maps Android.

e.

Hasil keluaran sistem menggambarkan rute optimum dari kota-kota yang dikunjungi digambarkan dengan polyline.

f.

Dalam perencanaan perjalanan tidak memperhatikan kota awal dan kota akhir.

5

1.4 Tujuan Penelitian Tujuan dari penelitian ini adalah untuk mewujudkan Algoritma Genetika Hibrida dengan Skema Pencarian Lokal Adaptif efektif dalam menyelesaikan Traveling Salesman Problem.

1.5 Manfaat Penelitian Penelitian ini dapat memberikan manfaat sebagai berikut: a.

Penelitian ini diharapkan dapat membantu meningkatkan efektifitas algoritma genetika dalam menyelesaikan traveling salesman problem.

b.

Penelitian ini diharapkan dapat menghasilkan aplikasi dalam menyelesaikan traveling salesman problem yang berjalan pada sistem operasi android.

1.6 Sistematika Penulisan Sistematika penulisan terdiri dari tiga bagian, yaitu bagian awal, bagian isi dan bagian akhir. 1.

Bagian awal Bagian awal skripsi terdiri dari halaman judul, halaman persetujuan,

halaman pengesahan, halaman moto dan persembahan, prakata, daftar isi, daftar tabel, daftar gambar dan daftar lampiran. 2.

Bagian isi Bagian isi memuat 5 Bab yang terdiri dari:

6

Bab I : Pendahuluan Bagian pendahuluan berisi tentang latar belakang, rumusan masalah, tujuan dan manfaat penelitian dan sistematika penulisan. Bab II : Tinjauan Pustaka Bagian tinjauan pustaka berisi tentang penelitian terdahulu dan landasan teoritis yang dikemukakan tentang teori-teori yang mendukung penelitian. Bab III : Metode Penelitian Bagian metode penelitian berisi tentang jenis penelitian, prosedur penelitian, rancangan dan pengembangan sistem, implementasi dan pengujian sistem Bab IV : Hasil dan Pembahasan Bagian ini berisi hasil penelitian dan pembahasan penelitian. Bab V : Kesimpulan dan Saran Bagian ini berisi tentang kesimpulan penelitian dan saran. 3.

Bagian akhir Bagian akhir skripsi terdiri dari daftar pustaka dari jurnal, buku dan

kepustakaan lain yang digunakan sebagai acuan dalam skripsi serta terdiri dari lampiran kelengkapan data.

BAB II TINJAUAN PUSTAKA

2.1 Penelitian Terdahulu Penelitian mengenai algoritma genetika hibrida untuk penyelesaian traveling salesman problem sudah ada penelitian sebelumnya, diantaranya oleh Feng-Gen Zhao, Jiang-Sheng Sun, Su-Jian Li, Wei-Min Liu (2009) dalam penelitiannya yang berjudul A Hybrid Genetic Algorithm for the Traveling Salesman Problem with Pickup and Delivery. Dalam penelitian ini untuk menyelesaikan permasalahan traveling salesman problem digunakan algoritma genetika hibrida. Hibridisasi yang dilakukan hanya menambahkan teknik pencarian lokal kedalam algoritma genetika untuk mempercepat laju konvergen. Hasil yang diperoleh membuktikan bahwa algoritma genetika hibrida mampu mengungguli algoritma tabu search dalam akurasi hasil jarak. Penelitian yang dilakukan oleh YoungSu Yun, Chiung Moon dan Dacho Kim (2009) dengan judul penelitian Hybrid genetic algorithm with adaptive local search scheme for solving multistage-based supply chain problems. Dalam penelitian ini terdapat skema pencarian lokal untuk mengontrol penggunaan teknik pencarian lokal kedalam algoritma genetika sehingga algoritma yang dibangun lebih efisien. Algoritma tersebut diterapkan pada permasalahan multistage-based supply chain. Hasil dari penelitian ini menunjukkan bahwa

7

8

algoritma genetika hibrida mampu mengungguli algoritma genetika tanpa pencarian lokal dalam menyelesaikan multistage-based supply chain problems. Penelitian lain yang dilakukan oleh Marjan Kuchaki Rafsanjani, Sadegh Eskandari dan Arsham Borumand Saeid (2015) dengan judul penelitian A similarity-based mechanism to control genetic algorithm and local search hybridization to solve traveling salesman problem. Penelitian ini dalam prosesnya menggunakan mekanisme berbasis kesamaan untuk mengontrol penggunaan pencarian lokal kedalam perulangan algoritma genetika. Hasil yang didapatkan menunjukkan bahwa algoritma genetika hibrida mampu menemukan panjang rute yang optimal disemua percobaan dibandingkan dengan algoritma genetika tanpa pencarian lokal. Dalam penelitian Anupriya dan Mansi Saxena (2013) dengan judul An Android Application for Google Map Navigation System Implementing Traveling Salesman Problem, dalam penelitian tersebut menggunakan algoritma genetika sederhana yang diimplementasikan pada google maps yang berjalan pada sistem operasi android. Hasil yang diperoleh bahwa implementasi algoritma genetika untuk menyelesaikan traveling salesman problem mampu dibangun di sistem operasi Android. Berdasarkan uraian diatas, penulis menerapkan algoritma genetika hibrida dengan skema pencarian lokal adaptif untuk menyelesaikan traveling salesman problem yang berjalan pada sistem operasi Android.

9

2.2 Landasan Teori 2.2.1 Traveling Salesman Problem Traveling Salesman Problem (TSP) merupakan salah satu masalah yang paling popular dalam optimasi kombinatorial dan telah diaplikasikan dalam perencanaan, penjadwalan, sequencing dan vehicle routing problems (Rafsanjani, et al., 2015). a.

Deskripsi Umum Travelling Salesmen Problem (TSP) termasuk ke dalam kelas NP hard yang

pada umumnya menggunakan pendekatan heuristik untuk mencari solusinya. Permasalahan utama dari TSP adalah bagaimana seorang salesman dapat menentukan rute perjalananannya untuk mengunjungi sejumlah kota yang diketahui jarak satu kota dengan kota lainnya sehingga jarak yang ditempuh merupakan jarak minimum dimana salesmen hanya dapat mengunjungi kota tersebut tepat satu kali (Bryant, 2000). Persoalan yang dihadapi TSP adalah bagaimana merencanakan total jarak yang minimum. Untuk menyelesaikan persoalan tersebut, tidak mudah dilakukan karena terdapat ruang pencarian dari sekumpulan permutasi sejumlah kota. Maka TSP kemudian dikenal dengan persoalan Non Polinomial. Gambaran sederhana dari pengertian TSP adalah sebagai berikut:

10

Gambar 2.1 Posisi kota-kota yang akan dilewati Persoalan TSP dapat dipecahkan dengan mengenumerasi

, dengan n

adalah jumlah kota dan kemudian memilih rute dengan panjang terpendek. Posisi kota dengan jumlah 4 kota (a, b, c, d) seperti ditunjukkan pada gambar 2.1 tersebut memiliki

rute yang dapat dilalui, yaitu:

R1 = (a, b, c, d, a) atau (a, d, c, b, a) dengan panjang rute 10 + 12 + 8 + 15 = 45 R2 = (a, c, d, b, a) atau (a, b, d, c, a) dengan panjang rute 12 + 5 + 9 + 15 = 41 R3 = (a, c, b, d, a) atau (a, d, b, c, a) dengan panjang rute 10 + 5 + 9 + 8 = 32 Jadi, rute terpendek adalah R3 = (a, c, b, d, a) atau (a, d, b, c, a) dengan panjang rute 10 + 5 + 9 + 8 = 32. Ini adalah solusi persoalan TSP untuk gambar 2.1 b.

Fungsi Objektif Fungsi objektif merupakan fungsi tujuan dari permasalahan, dalam TSP

tujuan utama adalah mendapatkan jarak minimal dari sebuah perjalanan. Secara matematis, TSP dapat didefinisikan sebagai kumpulan dari n kota { , ,… dan permutasi

,...,

!, tujuannya adalah untuk memilih

},

sehingga jumlah

semua jarak antar setiap kota dan penggantinya diminimalkan. Untuk menghitung

11

jarak antar kota

digunakan fungsi objektif TSP pada persamaan 2.1 (Fajardo

dan Oppus, 2010).

Jika jarak tempuh antar kota

, kota pertama adalah

dan

merupakan kota terakhir dalam setiap perjalanan dan koordinat kota dari seluruh kota

, dimana salesman akan mengunjungi semua kota, kemudian

total jarak dalam semua perjalanan (f). Fungsi untuk menghitung jarak dalam seluruh perjalanan dinyatakan dalam persamaan 2.2 (Davendra, 2010).

2.2.2 Algoritma Genetika Algoritma genetika merupakan suatu metode heuristik yang dikembangkan berdasarkan prinsip genetika dan proses seleksi alamiah Teori Evolusi Darwin. Dalam algoritma genetika proses pencarian penyelesaian atau proses terpilihnya sebuah penyelesaian berlangsung sama seperti terpilihnya suatu individu untuk bertahan hidup dalam proses evolusi (Zukhri, 2014: 10). a.

Struktur Umum Kerangka kerja yang biasa digunakan dalam penerapan algoritma genetika

untuk menyelesaikan suatu masalah optimasi ditunjukkan Gambar 2.2.

12

Permasalahan optimasi yang diselesaikan dengan algoritma genetika perlu dikodekan ke dalam kromosom. Hal ini disebabkan dalam proses komputasi yang sebenarnya, kromosom-kromosom itulah yang diproses menggunakan operatoroperator genetika seperti seleksi, penyilangan, dan mutasi.

Gambar 2.2 Kerangka Kerja Algoritma Genetika (Zukhri, 2014)

Dalam algoritma genetika, pemrosesan kromosom-kromosom sebagai sebuah populasi oleh operator genetika terjadi secara berulang. Pada mulanya populasi awal dibangkitkan secara acak. Selanjutnya, operator-operator genetika menggabungkan

informasi

genetis

untuk

membentuk

populasi

generasi

berikutnya. Pada generasi berikutnya, nilai fitness kromosom sebagai representasi dari penyelesaian masalah diharapkan bertambah semakin bagus (Zukhri, 2014: 19). Berikut prosedur kerja algoritma genetika sederhana.

13

Procedure: Algoritma Genetika Input: Permasalahan optimasi, parameter GA Output: Solusi terbaik Begin Step1: Algoritma Genetika Step2: Representasi Pengkodean masalah kedalam kromosom Step3: Inisialisasi Populasi Menghasilkan populasi secara acak sebanyak jumlah populasi Step4: Operator Genetika Step4.1: Seleksi Memilih dua orang tua menggunakan metode seleksi Step4.2: Crossover Menyilangkan dua orangtua yang dipilih menggunakan metode crossover Step4.3: Mutasi Menukar gen anak yang dihasilkan menggunakan metode mutasi Step5: Kondisi Berhenti Kondisi berhenti telah ditetapkan menggunakan jumlah generasi. Jika jumlah generasi terpenuhi maka proses perulangan berhenti End b.

Representasi Hal pertama yang harus dilakukan dalam algoritma genetika adalah

bagaimana solusi dari masalah direpresentasikan sebagai kumpulan kromosom. Representasi meliputi pengkodean gen dari kromosom. Gen merupakan bagian dari kromosom, dimana satu gen mewakili satu variabel. Gen dapat direpresentasikan dalam bentuk: string bit, array bilangan real, path/jalur, elemen permutasi, dan lain-lain (Kusumadewi, 2003:280). Representasi path merupakan representasi paling nyata dari perjalanan dalam TSP, solusi direpresentasikan sebagai daftar n kota (Larranaga, et al., 1999).

14

Misalkan dalam kasus TSP, biasanya kromosom tersusun dari indeks setiap kota. Jika banyaknya kota adalah 9, maka kromosom terdiri dari 9 gen. Setiap gen dapat berisi bilangan bulat yang merupakan indeks dari kota-kota tersebut. Misal P Є {Pati, Kudus, Grobogan, Solo, Semarang, Demak, Jepara, Rembang, Boyolali}, maka kromosom dapat dikodekan sebagai kombinasi bilangan 1 sampai 9. Jika kesembilan kota diindeks dengan urutan seperti itu, maka kromosom 1

2

3

4

5 6

7

8

9

Mempresentasikan rute, Pati–Kudus–Grobogan–Solo–Semarang–Demak–Jepara–Rembang–Boyolali. c.

Inisialisasi Populasi Inisialisasi populasi merupakan proses pembentukan populasi awal dari

kromosom sebanyak ukuran populasi (UkPop). Ukuran populasi mempengaruhi kinerja algoritma genetika jika masalahnya menjadi lebih sulit maka ukuran populasi harus meningkatkan (Reese, 2009). Mengingat setiap kromosom menyatakan urutan kota yang harus dikunjungi oleh salesman, maka representasi kromosom yang paling sederhana untuk menyatakan penyelesaian TSP adalah dalam bentuk permutasi dari indeks kota dan dapat dinyatakan sebagai vector v berikut: vi = [g1, g2, … , gN], dengan 1 ≤ i ≤ UkPop.

15

Populasi awal dibentuk secara acak. Hal ini berarti bahwa penyelesaian yang dihasilkan oleh algoritma genetika pada generasi pertama didapat dari penjumlahan jarak antar kota yang didekode dari bilangan kromosom v1, v2, … , vUkPop (Zukhri, 2014). d.

Proses Evaluasi Proses evaluasi merupakan proses untuk menghitung nilai fitness yang

menyatakan tingkat kualitas kromosom. Dalam masalah TSP, fungsi fitness tidak dapat didefinisikan secara langsung dari fungsi objektif karena TSP merupakan masalah pencarian nilai minimum (Zukhri, 2014). Oleh karena itu, fungsi fitness harus dipetakan dari fungsi objektifnya, dengan persamaan 3. eval(v )=

Dimana eval(v) merupakan fungsi fitness dan f (v) adalah fungsi objektif TSP. e.

Proses Seleksi Seleksi merupakan operator dalam algoritma genetika yang bertujuan untuk

memilih kromosom yang tetap bertahan dalam populasi untuk mengalami proses penyilangan. Salah satunya adalah Seleksi Turnamen, Dalam seleksi ini, kromosom-kromosom dalam suatu populasi dibagi menjadi beberapa grup secara acak. Setiap grup harus beranggotakan paling tidak dua kromosom. Seleksi dilakukan dengan mempertahankan kromosom dengan nilai fitness tertinggi pada setiap grup. Adanya pembagaian populasi menjadi grup-grup dengan anggota

16

yang lebih kecil, menyebabkan komputasi dalam model seleksi ini lebih ringan dibandingakan dengan model seleksi peringkat (Zukhri, 2014: 43). Pada metode seleksi dengan turnamen ini, akan ditetapkan suatu nilai turnamen untuk individu-individu yang dipilih secara random dari suatu populasi. Individu-individu yang terbaik dalam kelompok ini akan diseleksi sebagai induk. Parameter yang digunakan pada metode ini adalah ukuran turnamen yang bernilai antara 2 sampai N jumlah individu dalam suatu populasi (Kusumadewi, 2003: 289). Seleksi turnamen lebih efisien dan sederhana dalam implementasi dibandingkan metode seleksi yang lain (Razali dan Geraghty, 2011). Pada gambar 2.3 ditunjukkan proses seleksi turnamen dengan N=3.

Gambar 2.3 Proses Seleksi Turnamen

f.

Crossover Crosover atau penyilangan merupakan operator dalam algoritma genetika

yang bertujuan untuk melahirkan kromosom baru yang mewarisi sifat-sifat induknya (Zukhri, 2014:43). Salah satu metode crossover adalah Order Crossover, pada order crossover (OX) untuk menghasilkan keturunan dipilih dua titik silang dari kromosom induk. Kemudian gen-gen pada kromosom induk

17

pertama yang berada diantara titik penyilangan digantikan oleh gen-gen pada induk kedua. OX tepat digunakan untuk representasi path / permutasi, karena OX bukan merupakan masalah permutasi melingkar (Liu, et al., 2014). Dalam gambar 2.8 akan dijelaskan proses dari OX (Berninger, 2014).

Gambar 2.4 Proses order crossover

g.

Mutasi Fungsi mutasi adalah untuk menambah keragaman dalam populasi dan

mencegah kromosom jatuh ke dalam minimum lokal (Wang, 2014). Salah satu metode mutasi adalah Mutasi Exchange Dalam metode mutasi exchange, proses mutasi dilakukan dengan menukar dua kromosom dalam kumpulan data

18

(Berninger, 2014). Untuk lebih jalasnya dapat dilihat ilustrasi metode mutasi ini dalam gambar 2.12.

Gambar 2.5 Proses Exchange Crossover h.

Elitisme Karena seleksi dilakukan secara random, maka tidak ada jaminan bahwa

suatu individu bernilai fitness tertinggi akan selalu terpilih. Atau bahkan dapat rusak (nilai fitnessnya menurun) karena proses pindah-silang dan proses mutasi. Untuk menjaga agar individu bernilai fitness tertinggi tersebut tidak hilang selama proses evolusi, maka perlu dibuat satu atau beberapa kopinya. Prosedur ini sering dikenal sebagai elitisme (Suyanto, 2005).

2.2.3 Pencarian Lokal Pencarian lokal merupakan metode optimasi klasik yang menghasilkan solusi optimal lokal dengan mengeksplorasi lingkungan dari solusi awal yang diberikan. Penggunaan teknik pencarian lokal telah terbukti berguna dalam memecahkan masalah kombinatorial. Untuk teknik pencarian lokal, Hill Climbing yang disarankan oleh Michalewicz (1994) digunakan dalam penelitian ini. Hill Climbing (HC) merupakan algoritma pencarian untuk solusi yang lebih baik di lingkungan. Gerakan pencarian HC dicari berdasarkan nilai heuristik terbaik. Jika

19

menemukan solusi yang lebih baik, perubahan solusi saat ini dengan solusi baru. Jika solusi baru tidak lebih baik dari solusi saat ini maka algoritma berhenti dan menyimpan solusi optimal lokal saat ini. Metode ini dapat menjamin sifat yang diinginkan dari teknik pencarian lokal untuk hibridisasi dengan GA (Yun, 2006). Prosedur HC adalah sebagai berikut: Procedure: Perulangan metode hill climbing Begin Pilih individu terbaik dari populasi sekarang menggunakan nilai fitness Hasilkan individu secara acak sebanyak ukuran populasi dari lingkungan Pilih individu dengan nilai fitness terbaik dari individu yang baru dihasilkan If fitness( ) < fitness( ) then Else If fitness( ) ≥ fitness(

) then

end End

2.2.4 Skema Pencarian Lokal Adaptif Konsep dasar dari penerapan skema pencarian lokal adaptif ke dalam GA adalah mempertimbangkan apakah GA konvergen ke solusi optimal global atau optimal lokal. Ketika GA konvergen ke solusi optimal global, solusi yang dihasilkan terus meningkat. Namun, ketika GA konvergen ke solusi optimal lokal, kinerja GA terus memburuk (Yun, et al., 2009). Dalam situasi ini GA terjebak dalam kondisi optimum lokal, dimana sulit bagi GA menghindari konvergensi dini untuk solusi optimal lokal. Istilah konvergensi dini berarti bahwa populasi untuk masalah optimasi berkumpul terlalu dini, sehingga menjadi optimal terlalu

20

awal. Dalam hal ini, keturunan yang dihasilkan dari orang tua menggunakan bantuan operator genetik tidak lebih unggul dibandingkan orang tua mereka. Kelemahan tersebut dapat ditingkatkan dengan teknik pencarian lokal yang dapat mencari di sekitar area konvergensi di perulangan GA dan memasukkan individu baru dengan nilai fitness yang lebih tinggi kedalam perulangan GA (Yun, 2006; Yun et al, 2009). Berdasarkan konsep tersebut di atas, skema pencarian lokal adaptif diusulkan dalam penelitian ini. Skema pencarian lokal adaptif yang diusulkan adalah dengan menggunakan similarity coefﬁcient method (SCM). Untuk informasi tentang SCM yang digunakan dalam skema pencarian lokal adaptif, penulis merujuk pada penelitian yang dilakukan oleh Rafsanjani, et al., 2015. SCM menggunakan kesamaan koefisien untuk mengukur kesamaan dua individu. Dalam penelitian ini metode kesamaan koefisien yang digunakan adalah cosine similarity, sebagai metode cosinus tepat untuk mengukur kesamaan yang ada antar individu berbasis prioritas dalam populasi GA untuk traveling salesman problem karena urutan traveling tidak berubah dengan skala individu. Cosine similarity merupakan ukuran kesamaan antara dua vektor dari hasil kali yang mengukur cosinus dari sudut yang dihasilkan. Untuk menghitung Cosine similarity

antara dua individu dari populasi, di hitung menggunakan persamaan 2.4.

dimana,

dan

21

= vektor dot produk dari l dan m, dihitung dengan

= panjang dari vector l, dihitung dengan

= panjang dari vector m, dihitung dengan

Untuk menghitung rata-rata cosine similarity untuk semua individu dari populasi GA, dihitung menggunakan persamaan 5 (Rafsanjani, et al., 2015).

dimana, P

= Populasi dari GA

|P|

= Ukuran opulasi

Penggunaan teknik pencarian lokal ke GA diatur oleh kondisi berikut ini:

2.2.5 Algoritma Genetika Hibrida Dalam algoritma genetika hibrida (HGA) penulis menggabungkan algoritma genetika dengan pencarian lokal menggunakan skema pencarian lokal adaptif yang dirancang untuk mengontrol penggunaan teknik pencarian lokal di

22

perulangan GA. Skema pencarian lokal adaptif yang digunkan adalah metode kesamaan koefisien. Ketika GA terus konvergen maka kesamaan antara individu dalam populasi menjadi lebih tinggi. Menyebabkan nilai fitness antara individu menjadi mirip satu sama lain dan keragaman dari populasi berkurang, yang pastinya kinerja GA akan memburuk. Oleh karena itu, alternatif yang dapat digunakan untuk meningkatkan kinerja GA adalah menambahkan individu baru ke dalam populasi GA dengan menggunakan metode pencarian lokal hill climbing. Individu-individu baru tidak harus memiliki kesamaan yang sama dengan populasi saat ini dan juga menjaga nilai fitness tinggi tertentu yang mirip dengan kesamaan populasi. Individuindividu yang dihasilkan dari metode pencarian lokal dapat mencari di sekitar area konvergensi menggunakan perulangan GA. Untuk prosedur dari HGA dalam menyelesaikan TSP adalah sebagai berikut: Algoritma: HGA untuk Traveling Salesman Problem Input: Data kota-kota TSP Output: Rute perjalanan terbaik Begin Step1: Algoritma Genetika Step1.1: Representasi Pengkodean masalah menggunakan path representasi Step1.2: Inisialisasi populasi Menghasilkan populasi secara acak sebanyak jumlah populasi Step1.3: Evaluasi Evaluasi populasi sekarang dengan fungsi fitness kemudian salin individu terbaik menggunakan elitism Step1.4: Operator genetika Step1.4.1: Seleksi Menghasilkan dua orangtua menggunakan seleksi turnamen Step1.4.2: Crossover

23

Pindah silang dua orangtua yang dipilih menggunakan order crossover Step1.4.3: Mutasi Tukar gen anak yang dihasilkan menggunakan mutasi exchange Step1.5: Kondisi berhenti Kondisi berhenti telah ditetapkan menggunakan jumlah generasi. Jika jumlah generasi terpenuhi maka proses perulangan akan berhenti Step2: Pencarian lokal Terapkan teknik pencarian lokal jika kondisi pada skema pencarian lokal adaptif telah terpenuhi. Lanjutkan ke Step 1.3 End

2.2.6 Android Dalam pembahasan ini dirujuk dari website resmi Developer Android (2015). Android menyediakan framework aplikasi yang memungkinkan untuk membangun aplikasi dan game yang inovatif untuk perangkat mobile dalam bahasa pemrograman Java. Android telah terintegrasi dengan Google API yang memungkinkan developer untuk membangun aplikasi menggunakan berbagai API Android yang disediakan oleh Google diantaranya Google Maps API Android V2. a.

Google Maps API Android V2 Google Maps Android API merupakan layanan dari Google yang berfungsi

untuk mengintegrasikan peta pada aplikasi yang dibangun berdasarkan pada Google Maps data. API secara otomatis menangani akses ke Google Maps server seperti data download, dan tampilan peta. Fungsi lain dari API yaitu dapat menambahkan markers, poligon dan overlay untuk peta dasar, dan mengubah

24

pandangan user dari peta ke area tertentu. API memberikan informasi tambahan untuk lokasi pada peta, dan memungkinkan untuk menambahkan grafis pada peta: - Menambahkan ikon untuk menentukan posisi tertentu pada peta (Markers). - Menambahkan segmen garis (Polyline). - Menambahkan segmen tertutup (Poligon). - Menambahkan grafik bitmap ke posisi tertentu di peta (Ground Overlays). - Menambahkan gambar yang ditampilkan diatas peta (Tile Overlays). Google Maps Android API tidak terdapat dalam platform Android, tetapi tersedia pada perangkat dengan Google Play Store yang berjalan pada Android 2.2 atau lebih tinggi, melalui Google Play Services. b.

Integrasi Google Maps Android Untuk mengintegrasikan Google Maps ke dalam aplikasi, perlu menginstal

Google Play services libraries pada framework ADT. Kemudian untuk mendapatkan akses Google Maps API, diperlukan Android API key dan menambahkan kedalam aplikasi yang dibangun. Untuk mendapatkan API key harus dihasilkan dengan menggunakan SHA1 fingerprint dari komputer developer, berikut perintah yang harus dijalankan: keytool -list -v -keystore "%USERPROFILE%\.android\debug.keystore" -alias androiddebugkey -storepass android -keypass android

25

Daftarkan SHA1 fingerprint di Google APIs Console untuk mendapatkan API

key

dan

dapat

mengakses

Google

Maps

Android

V2.

Dalam

AndroidManifest.xml, tambahkan API key seperti baris kode berikut: <meta-data android:name="com.google.android.geo.API_KEY" android:value="API_KEY"/>

Menentukan izin kebutuhan aplikasi, dengan menambahkan <usespermission>

elemen

sebagai

sub

dari

<manifest>

elemen

dalam

AndroidManifest.xml. Tambahkan izin berikut untuk menggunakan Google Maps Android API: <uses-permission android:name="android.permission.INTERNET"/> <uses-permission android:name="android.permission.ACCESS_NETWORK_STATE"/> <uses-permission android:name="android.permission.WRITE_EXTERNAL_STORAGE"/>

Setelah beberapa pengaturan, tampilan peta pada Aplikasi Android ditunjukkan pada Gambar 2.6.

26

Gambar 2.6 Tampilan Awal Peta

c.

Markers Markers mengidentifikasi lokasi pada peta. Markers default menggunakan

ikon standar yang umum untuk Google Maps. Dengan API dapat untuk mengubah warna, gambar atau anchor point ikon. Markers adalah objek dari jenis Marker, dan

ditambahkan

ke

peta

dengan

metode

GoogleMap.addMarker

(markerOptions). Contoh penggunaan Markers ditunjukkan pada Gambar 2.7.

27

Gambar 2.7 Contoh Penggunaan Markers Pada aplikasi yang dibangun marker digunakan untuk penanda lokasi awal sebagai kota keberangkatan dan kota-kota tujuan dari salesman. Markers menjadi sebuah penanda perjalanan akan dimulai dari mana dan berakhir ke kota awal perjalanan dimulai. d.

Polyline Polyline mendefinisikan satu set segmen garis yang terhubung pada peta.

Sebuah objek Polyline terdiri dari satu set lokasi LatLng, dan menciptakan serangkaian segmen garis yang menghubungkan lokasi-lokasi dalam urutan. Untuk membuat Polyline, pertama buat objek dengan PolylineOptions dan menambah titik dari LatLng. Segmen garis yang ditarik dari titik-titik sesuai dengan urutan yang sesuai ke objek PolylineOptions. Untuk menambah titik ke objek PolylineOptions, panggilan PolylineOptions.add(). Contoh penggunaan polyline dengan garis berwarna merah dan ditandai dengan marker sebagai titik penghubung, ditunjukkan pada Gambar 2.8.

28

Gambar 2.8 Contoh Penggunaan Polyline

29

BAB III METODE PENELITIAN

3.1 Studi Pustaka Studi pustaka yang dilakukan dalam penelitian ini dengan cara membaca literatur yang berkaitan dengan algoritma genetika, skema pencarian lokal adaptif, hill climbing dan traveling salesman problem dari jurnal, paper dan buku yang berkaitan. Langkah-langkah penelitian secara keseluruhan dalam penelitian ini disajikan pada gambar 3.1.

3.2 Analisis Permasalahan Analisis masalah merupakan tahapan setelah melakukan studi pustaka. Analisis Permasalahan dilakukan untuk mengetahui sistem yang sudah ada sebelumnya dalam penyelesaian traveling salesman problem. Algoritma genetika telah banyak diteliti untuk menyelesaikan traveling salesman problem, disini penulis menerapkan skema pencarian lokal adaptif untuk hibridisasi algoritma genetika yang diimplementasikan pada android. Di Indonesia belum ada peneliti yang menerapkan algoritma genetika dengan skema pencarian lokal adaptif untuk menyelesaikan traveling salesman problem pada android.

28

29

Mulai

Studi Pustaka

Analisis Permasalahan

Perhitungan Algoritma Genetika Hibrida dengan Skema Pencarian Lokal Adaptif

Pengembangan Sistem: - Analisis Software dan Hardware - Desain Sistem

Implementasi

Pengujian

Hasil yang didapatkan optimum?

Tidak

Ya Pembuatan Laporan

Selesai

Gambar 3.1 Desain Penelitian dan Pengambangan HGA

30

3.3

Mapping HGA dengan skema pencarian lokal adaptif pada TSP Ada 2 program yang dikembangkan dalam skripsi ini. Salah satu program

adalah algoritma genetika sederhana untuk penyelesaian TSP dan satu program adalah algoritma genetika hibrida dengan skema pencarian lokal adaptif untuk penyelesaian TSP. Kedua program tersebut diterapkan pada sistem Android menggunakan software ADT-Bundle dengan Bahasa pemrograman Java. 3.3.1 Algoritma Genetika untuk menyelesaikan TSP Algoritma genetika telah dijelaskan pada bagian teori, proses operasi algoritma genetika diulangi dalam perulangan generasi. Langkah pertama dalam GA

yaitu merepresentasikan masalah kedalam kromosom

/

rute dan

membangkitkan populasi secara acak, sehingga terdapat banyak rute dengan panjang yang berbeda. Sebuah rute akan disilangkan dengan rute yang lain dan dilakukan proses mutasi. Setelah proses mutasi selesai didapatkan rute terbaik yang disimpulkan sebagai penyelesaian TSP. Tabel merupakan sampel TSP dengan 5 kota tujuan. Tabel 3.1 Sampel 5 Kota Kota

Latitude

Longitude

Kendal

-6.920633

110.20483

Semarang

-6.990155

110.422515

Batang

-6.906720

109.732468

Banjarnegera

-7.399196

109.688866

Purwokerto

-7.427879

109.242443

31

Untuk menghitung jarak antar dua kota

digunakan fungsi Eucidean pada

Persamaan 1, sehingga jarak antar kota ditunjukkan pada tabel 3.2.

Tabel 3.2 Jarak Antar Kota Jarak

Kendal Semarang Batang Banjarnegera Purwokerto

Kendal

0

0.228

0.472

0.703

1.087

Semarang

0.228

0

0.695

0.839

1.258

Batang

0.472

0.695

0

0.494

0.715

Banjarnegera 0.703

0.839

0.494

0

0.447

1.087

1.258

0.715

0.447

0

Purwokerto



Pembentukan populasi awal Pembentukan populasi awal dibentuk secara acak dari kromosom sebanyak

jumlah populasi, pada penyelesaian yang dihasilkan oleh algoritma genetika pada generasi pertama didapat dari penjumlahan jarak semua kota yang dikunjungi oleh salesman menggunakan persamaan 2.2. Pembentukan populasi awal dengan 4 populasi, ditunjukkan pada Tabel 3.3. Tabel 3.3 Populasi Awal Kromosome

Representasi Path Kendal Purwokerto Banjarnegera Semarang Batang Batang Semarang Purwokerto Banjarnegera Kendal Banjarnegera Kendal Purwokerto Semarang Batang Batang Semarang Kendal Banjarnegera Purwokerto

32



Evaluasi Proses evaluasi dilakukan dengan fungsi fitness, kromosom dengan nilai

fitness tertinggi merupakan kromosom terbaik. Dalam permasalahan TSP fungsi fitness tidak dapat didefinisikan secara langsung dari fungsi objektif karena TSP merupakan masalah pencarian nilai minimum. Oleh karena itu fungsi fitness merupakan kebalikan (inverse) dari fungsi objektif, sehingga,

Semakin kecil fungsi objektif maka semakin besar fungsi fitness, dalam permasalahan TSP untuk meminimalkan jarak maka perlu memaksimalkan fungsi fitnessnya. Hasil pemetaan fungsi objektif ke fungsi fitness dari populasi awal terlihat pada Tabel 3.4. Tabel 3.4 Inverse fungsi objektif ke fungsi fitness Kromosom

3.542 3.577 4.239 2.790 

0.282 0.279 0.235 0.358

Elitism Pada tahap ini kromosom terbaik disimpan untuk menghindari kromosom

terbaik yang hilang selama proses crossover dan mutasi. Dari populasi awal kromosom

,

33

merupakan kromosom terbaik dengan nilai fitness terbesar. Selanjutnya ada 3 kromosom yang akan dihasilkan melalui proses crossover dan mutasi. 

Seleksi Proses seleksi memilih dua orang tua dari populasi menggunakan seleksi

turnamen. Dalam seleksi turnamen memilih kromosom dalam populasi secara acak sebanyak ukuran turnamen, kemudian dari kromosom tersebut dipilih satu yang terbaik. Ukuran turnamen adalah 3, kromosom acak dari populasi adalah kemudian pilih yang terbaik dari kromosom acak menggunakan metode evaluasi. Jadi kromosom

merupakan yang terbaik dan dijadikan sebagai

parent1. Untuk mendapatkan parent2 dilakukan prosedur seleksi yang sama seperti mendapatkan parent1. 

Crossover Hasil dari seleksi kemudian dipindah silang menggunakan order crossover.

Setelah operator penyilangan, kromosom-kromosom hasil penyilangan akan dilakukan proses mutasi. 

Mutasi Gen akan terkena mutasi jika bilangan random r yang dibangkitkan untuk

gen yang bersangkutan kurang dari probabilitas mutasi (Pm). Untuk selanjutnya gen/kota yang terpilih akan ditukar letaknya dengan gen/kota lain secara acak yang terdapat pada kromosom yang sama. Hasil proses mutasi terdapat dalam Tabel 3.5.

34

Tabel 3.5 Populasi Baru Kromosom

Representasi Path Semarang Kendal Banjarnegera Purwokerto Batang

2.790

Semarang Kendal Banjarnegera Purwokerto Batang

2.790

Purwokerto Semarang Batang Kendal Banjarnegera

3.577

Semarang Banjarnegera Batang Purwokerto Kendal

3.366

3.3.2 Algoritma Genetika Hibrida Dengan Skema Pencarian Lokal Adaptif untuk menyelesaikan TSP Dalam HGA terdapat penambahan teknik pencarian lokal kedalam algoritma genetika yang dikontrol dengan skema pencarian lokal. Untuk menentukan teknik pencarian lokal digunakan didalam GA atau tidak diperlukan perhitungan kesamaan antara individu didalam populasi menggunakan Persamaan 2.5. Sebagai contoh menghitung kesamaan kromosom

dan kromosom

.

= Semarang Kendal Banjarnegera Purwokerto Batang = Purwokerto Semarang Batang Kendal Banjarnegera Koordinat kromosom

dan

adalah sebagai berikut,

= {( -6.990155, 110.422515) (-6.920633, 110.20483) (-7.399196, 109.688866) (-7.427879, 109.242443) (-6.906720, 109.732468)} = {( -7.427879, 109.242443) (-6.990155, 110.422515) (-6.906720, 109.732468) (-6.920633, 110.20483)

35

(-7.399196, 109.688866)} Dalam menghitung kesamaan antar individu dapat dihitung dengan persamaan 2.4. Untuk vektor, dan Maka,

Sehingga perhitungan kesamaan cosine menjadi seperti berikut:

= 60597.74

36

Untuk menghitung kesamaan antar individu dalam suatu populasi dapat dihitung dengan persamaan 2.5, hasil perhitungan adalah sebagai berikut.

Kondisi dimana teknik pencarian lokal digunakan didalam algoritma genetika adalah

, jadi

sehingga kondisi

tersebut terpenuhi untuk menerapkan teknik pencarian lokal. Langkah yang harus dikerjakan untuk teknik pencarian lokal menggunakan metode hill climbing yang diusulkan oleh Michalewicz adalah memilih individu terbaik

dari populasi yang dihasilkan oleh GA. = Semarang Kendal Banjarnegera Purwokerto Batang Kemudian hasilkan individu secara acak sebanyak ukuran populasi dari

individu terbaik, dengan menggunakan operator genetika, proses yang dilakukan sama seperti menghasilkan populasi baru pada algoritma genetika. Tabel 3.6 Individu baru yang dihasilkan

37

Kromosom

Representasi Path Batang Semarang Kendal Banjarnegera Purwokerto Batang Semarang Kendal Banjarnegera Purwokerto Banjarnegera Semarang Kendal Batang Purwokerto Batang Semarang Kendal Banjarnegera Purwokerto

Pilih individu terbaik

2.790 2.790 2.703 2.790

dari populasi yang baru dihasilkan menggunakan

fungsi fitness = Banjarnegera Semarang Kendal Batang Purwokerto Selanjutnya bandingkan fitness sehingga fitness( ) < fitness(

= 0.358 dengan fitness

= 0.369,

), kemudian substitusikan individu terbaik dari

GA = Semarang Kendal Banjarnegera Purwokerto Batang dengan individu terbaik populasi yang baru = Banjarnegera Semarang Kendal Batang Purwokerto Berdasarkan perhitungan dari algoritma genetika hibrida dengan skema pencarian lokal adaptif didapatkan jarak terbaik dengan panjang 2.703 dengan rute perjalanan yaitu Banjarnegera → Semarang → Kendal → Batang → Purwokerto.

3.4

Tahap Pengembangan Sistem

3.4.1 Analisis Hardware dan Software

38

Dibutuhkan perangkat keras dan perangkat lunak dengan spesifikasi tertentu untuk menunjang dalam pembuatan sistem. Berikut spesifikasi minimum perangkat keras dan perangkat lunak yang dibutuhkan untuk mengimplentasikan racangan pengembangan sistem dalam penelitian ini. a.

Perangkat Keras Minimum spesifikasi perangkat keras yang digunakan dalam implementasi

sistem adalah: -

Prosesor Dual Core+, Harddisk Space 25 GB, Ram 2 GB.

-

Smartphone Single Core+, 512 GB RAM.

b.

Perangkat Lunak Perangkat lunak yang digunakan dalam implementasi sistem adalah sebagai

berikut: -

Windows 7/8/Vista (32/64-bit) sebagai sistem operasi laptop.

-

Terinstal Java Developer Kit (JDK) 7.

-

ADT Bundle sebagai software pemrograman java.

-

Android 4.0 (IceCreamSandwich) sebagai sistem operasi smartphone.

3.4.2 Desain Sistem TSP

39

Desain sistem meliputi alur proses sistem yang berupa flowchart sistem dan desain interface yang meliputi desain antarmuka user dan desain antarmuka admin. a.

Desain alur proses sistem Dalam aplikasi ini, fungsi google maps adalah untuk mendapatkan dan

menampilkan marker dari lokasi geografi (latitude dan longitude) pada Maps sebagai tempat tujuan dari salesman. Berikut rancangan alur sistem untuk menampilkan marker:

Mulai

Database kota (latitude, longitude)

Interface sistem

Masukkan kota

Google Server

Markers ditemukan?

Menampilkan pada Maps

Selesai

Gambar 3.2 Permintaan marker pada Google Maps

40

Proses berjalannya sistem terdiri dari permintaan Markers sebagai penanda lokasi tujuan salesman, kemudian proses penghitungan rute terbaik menggunakan algoritma genetika hibrida dengan skema pencarian lokal adaptif. Berikut rancangan perhitungan rute optima menggunakan algoritma yang dibangun:

Masukan Lokasi (markers pada google maps android)

Menghitung Jarak (Fungsi Euclidean)

Menghasilkan populasi awal

Evaluasi (Fungsi Fitness)

Elitism

Mutasi

Ya Kondisi Berhenti

Crossover

Tidak Scosine ≥ α

Tidak Seleksi

Ya Methode Hill Climbing

Rute Terbaik Ditampilkan pada Google Maps Android

Gambar 3.3 Alur proses sistem yang berjalan

41

b.

Desain perencangan interface Desain perancangan antarmuka meliputi desain tampilan dashboard admin,

desain tampilan user. Berikut desain interface sistem yang dikembangkan: Tambah

Dashboard

No

Kota

Latitude

Longitude

Gambar 3.4 Tampilan Dashbord Admin

Hybrid Optimization

Select

Direction

Google Maps

Gambar 3.5 Tampilan Halaman Awal User

Login

About

42

Finish

Select

Semarang Kendal Batang Banjarnegara Purwokerto Blora Pati Kudus

Gambar 3.6 Tampilan Halaman Input Kota

Reset

Hybrid Optimization

Result

Petunjuk Arah Google Maps

Gambar 3.7 Tampilan Halaman Hasil Perhitungan Algoritma

Evolusi

43

3.5

Implementasi

3.5.1 Integrasi Google Maps Untuk menampilkan peta diperlukan untuk menambahkan baris kode berikut pada layout dan java file, baris kode untuk main_activity.xml sebagai berikut:

Baris kode untuk java file yang terdapat pada MainActivity.java adalah sebagai berikut:

public class MapsActivity extends FragmentActivity { @Override protected void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); setContentView(R.layout.activity_maps); SupportMapFragment mapFragment = (SupportMapFragment) getSupportFragmentManager() .findFragmentById(R.id.map); }

Pada aplikasi yang dikembangkan polyline digunakan untuk panduan perjalanan, dimulai dari marker sebagai penanda kota awal dan kota-kota tujuan

44

oleh salesman, kemudian dilakukan perhitungan menggunakan algoritma genetika hibrida dengan skema pencarian lokal adaptif untuk pengoptimalan sebuah perjalanan. Setelah perhitungan selesai, ditampilkan pada Google Maps dengan nomor urutan Marker dengan garis merah sebagai penanda perjalanan. Baris kode berikut digunakan untuk menampilkan polyline. PolylineOptions rectOptions = new PolylineOptions() .add(new LatLng(37.35, -122.0)) .add(new LatLng(37.45, -122.0)) .add(new LatLng(37.45, -122.2)) .add(new LatLng(37.35, -122.0)); Polyline polyline = myMap.addPolyline(rectOptions);

3.5.2 Pengkodean Sistem simulasi penyelesaian TSP menggunakan HGA dengan skema pencarian lokal adaptif diimplementasikan dalam bahasa pemrograman java. Berikut ini akan disajikan beberapa potongan source code yang berhubungan dalam proses HGA untuk menyelesaikan TSP. a.

Fungsi Objektif TSP public double distanceTo(City city){ int xDistance = Math.abs(getX() - city.getX()); int yDistance = Math.abs(getY() - city.getY()); double distance = Math.sqrt((xDistance*xDistance) + (yDistance*yDistance)); return distance; }

Gambar 3.8 Source code fungsi objektif

45

b.

Operator genetika Pada operator genetika terdapat tiga operator yang digunakan dalam

penelitian yaitu seleksi, crossover dan mutasi. -

Seleksi Turnamen private static Tour tournamentSelection(Population pop) { Population tournament = new Population(tournamentSize, false); for (int i = 0; i < tournamentSize; i++) { int randomId = (int) (Math.random() * pop.populationSize()); tournament.saveTour(i, pop.getTour(randomId)); } Tour fittest = tournament.getFittest(); return fittest; }

Gambar 3.9 Source code seleksi turnamen -

Order Crossover public static Tour crossover(Tour parent1, Tour parent2) { Tour child = new Tour(); int startPos = (int)(Math.random()*parent1.tourSize()); int endPos = (int)(Math.random() * parent1.tourSize()); for (int i = 0; i < child.tourSize(); i++) { if (startPos < endPos && i > startPos && i < endPos) { child.setCity(i, parent1.getCity(i)); } else if (startPos > endPos) { if (!(i < startPos && i > endPos)) { child.setCity(i, parent1.getCity(i)); } } } for (int i = 0; i < parent2.tourSize(); i++) { if (!child.containsCity(parent2.getCity(i))) { for (int ii = 0; ii < child.tourSize(); ii++) { if (child.getCity(ii) == null) { child.setCity(ii, parent2.getCity(i)); break; } } } } return child; }

46

Gambar 3.10 Source code order crossover -

Mutasi Swap private static void mutate(Tour tour) { for(int tourPos1=0; tourPos1
Gambar 3.11 Source code swap mutasi c.

Algoritma Genetika public class GA { private static final double mutationRate = 0.05; private static final int tournamentSize = 3; private static final boolean elitism = true; public static Population evolvePopulation(Population pop) { Population newPopulation = new Population(pop.populationSize(), false); int elitismOffset = 0; if (elitism) { newPopulation.saveTour(0, pop.getFittest()); elitismOffset = 1; } for(int i=elitismOffset; i
47

Gambar 3.12 Source code algoritma genetika

d.

Algoritma Genetika Hibrida dengan Skema Pencarian Lokal Adaptif Dalam algoritma genetika hibrida terdapat beberapa tambahan seperti

metode hill climbing dan penghitungan cosine similarity. -

Hill Climbing public static Population hillClimbing(Population newPopulation) { Population currentPop = newPopulation; double currentFitness = currentPop.getFittest().getFitness(); Population neighborhoodPop = new Population(currentPop.populationSize(), false); int elitismOffset = 0; if (elitism) { neighborhoodPop.saveTour(0, currentPop.getFittest()); elitismOffset = 1; } for (int i = elitismOffset; i < currentPop.populationSize(); i++) { Tour parent1 = tournamentSelection(currentPop); Tour parent2 = tournamentSelection(currentPop); Tour child = crossover(parent1, parent2); neighborhoodPop.saveTour(i, child); } for (int i = elitismOffset; i < currentPop.populationSize(); i++) { mutate(neighborhoodPop.getTour(i)); } double neighborhoodFitness = neighborhoodPop.getFittest().getFitness(); if (neighborhoodFitness > currentFitness) { currentPop = neighborhoodPop; } else if (neighborhoodFitness <= currentFitness) { currentPop = currentPop; } return currentPop; }

Gambar 3.13 Source code hill climbing

48

49

-

Cosine Similarity public static double ScosineML(Tour M, Tour L) { double MdotL = 0; double jml_u = 0; double lengthM = 0; double jml_v = 0; double lengthL = 0; for (int i = 0; i < M.tourSize(); i++) { double double double double

x1 y1 x2 y2

= = = =

M.getCity(i).getX(); M.getCity(i).getY(); L.getCity(i).getX(); L.getCity(i).getY();

MdotL += (x1*x2)+(y1*y2); // l.m jml_v += (x1*x1)+(y1*y1); // (m^2) jml_u += (x2*x2)+(y2*y2); // (l^2) } lengthM = Math.sqrt(jml_u); //|m| lengthL = Math.sqrt(jml_v); //|l| double ScosineML = MdotL/(lengthM*lengthL); return ScosineML; }

Gambar 3.14 Source code cosine similarity

-

Menghitung Cosine Similarity dalam suatu populasi public static double Scosine(Population pop) { double Scosinelm = 0; double jmlML = 0; int bil = pop.populationSize(); BigDecimal faktorial = BigDecimal.valueOf(1); BigDecimal bfaktorial = BigDecimal.valueOf(2); if (bil > 0) { for (int i = bil; i > 0; i--) { faktorial = faktorial.multiply(BigDecimal.valueOf(i)); } } int bil2 = bil - 2; if (bil2 > 0) { for (int i = bil2; i > 0; i--) { bfaktorial = bfaktorial.multiply(BigDecimal.valueOf(i)); } } BigDecimal kombinasi = faktorial.divide(bfaktorial);

50

int bil2 = bil - 2; if (bil2 > 0) { for (int i = bil2; i > 0; i--) { bfaktorial = bfaktorial.multiply(BigDecimal.valueOf(i)); } } BigDecimal kombinasi = faktorial.divide(bfaktorial); for (int l = for (int Tour Tour

0; l < pop.populationSize()-1; l++) { m = l+1; m < pop.populationSize(); m++ ){ M = pop.getTour(m); L = pop.getTour(l);

double temp = ScosineML(M, L); jmlML += temp; } } Scosinelm = jmlML/kombinasi.doubleValue(); return Scosinelm; }

Gambar 3.15 Source code cosine similarity dalam populasi

-

Fungsi algoritma genetika hibrida

protected void generateHGA() { Population hga_pop = new Population(int_popsize, true); hga_pop = hGA.evolvePopulation(hga_pop); double hga_temp_distance = hga_pop.getFittest().getDistance(); for (int i = 0; i < int_gen; i++) { hga_pop = hGA.evolvePopulation(hga_pop); ScosineP = hGA.Scosine(hga_pop); TourManager.scosine.add(String.valueOf(ScosineP)); // Not convergen if (ScosineP < alpha) { hga_temp_distance = hga_pop.getFittest().getDistance(); } // Convergen else if (ScosineP >= alpha) { hga_pop = hGA.hillClimbing(hga_pop); hga_temp_distance = hga_pop.getFittest().getDistance(); } hga_distance = String.valueOf(hga_temp_distance); } }

Gambar 3.16 Source code fungsi HGA

51

3.6 Pengujian Untuk menguji efektifitas algoritma genetika hibrida (HGA) dengan skema pencarian lokal adaptif dibandingkan dengan algoritma genetika (GA) tanpa pencarian lokal dalam menemukan panjang rute terpendek permasalahan traveling salesman. Langkah-langkah dari strategi pengujian adalah sebagai berikut: a.

Data Pengujian Sampel data untuk TSP dari kabupaten/kota di Jawa Tengah, Indonesia.

Data berupa lokasi geografis didapatkan dari https://maps.google.co.id. Berikut daftar kabupaten/kota di Jawa Tengah. Tabel 3.7 Daftar Kabupaten/Kota di Jawa Tengah No.

City

Latitude

Longitude

1

Semarang

-6.990155

110.422515

2

Kendal

-6.920633

110.20483

3

Batang

-6.906720

109.732468

4

Banjarnegera

-7.399196

109.688866

5

Purwokerto

-7.427879

109.242443

6

Blora

-6.970731

111.421695

7

Boyolali

-7.538509

110.611589

8

Brebes

-6.875365

109.053143

9

Cilacap

-7.727205

109.009361

10

Demak

-6.894602

110.638154

11

Purwodadi

-7.083219

110.913327

12

Jepara

-6.590626

110.667318

13

Karanganyar

-7.597301

110.950577

14

Kebumen

-7.669664

109.651954

52

15

Klaten

-7.705463

110.600388

16

Kudus

-6.808916

110.842946

17

Magelang

-7.476794

110.218917

18

Pati

-6.753899

111.042784

19

Kajen

-7.027724

109.590379

20

Pemalang

-6.879946

109.380047

21

Purbalingga

-7.389535

109.363185

22

Purworejo

-7.713033

110.009351

23

Rembang

-6.705611

111.348445

24

Ungaran

-7.127487

110.403562

25

Sragen

-7.427645

111.023387

26

Sukoharjo

-7.683752

110.846919

27

Slawi

-6.974607

109.139532

28

Temanggung

-7.316753

110.178341

29

Wonogiri

-7.813768

110.926073

30

Wonosobo

-7.358785

109.902953

31

Kota Salatiga

-7.320499

110.498854

32

Kota Surakarta

-7.581987

110.826337

33

Kota Tegal

-6.867419

109.137794

34

Kota Pekalongan

-6.890554

109.676231

35

Mungkid

-7.561907

110.256464

Dalam pengujian ini 5 sampel TSP diambil dengan jumlah kota yang berbeda, meliputi: -

Case1 dengan jumlah kota 7 meliputi Semarang, Kendal, Batang, Banjarnegera, Purwokerto, Blora, Boyolali.

53

-

Case2 dengan jumlah kota 14 meliputi Semarang, Kendal, Batang, Banjarnegera, Purwokerto, Blora, Boyolali, Brebes, Cilacap, Demak, Purwodadi, Jepara, Karanganyar, Kebumen.

-

Case3 dengan jumlah kota 20 meliputi Semarang, Kendal, Batang, Banjarnegera, Purwokerto, Blora, Boyolali, Brebes, Cilacap, Demak, Purwodadi, Jepara, Karanganyar, Kebumen, Klaten, Kudus, Magelang, Pati, Kajen, Pemalang.

-

Case4 dengan jumlah kota 25 meliputi Semarang, Kendal, Batang, Banjarnegera, Purwokerto, Blora, Boyolali, Brebes, Cilacap, Demak, Purwodadi, Jepara, Karanganyar, Kebumen, Klaten, Kudus, Magelang, Pati, Kajen, Pemalang, Purbalingga, Purworejo, Rembang, Ungaran, Sragen.

-

Case5 dengan jumlah kota 35 meliputi Semarang, Kendal, Batang, Banjarnegera, Purwokerto, Blora, Boyolali, Brebes, Cilacap, Demak, Purwodadi, Jepara, Karanganyar, Kebumen, Klaten, Kudus, Magelang, Pati, Kajen, Pemalang, Purbalingga, Purworejo, Rembang, Ungaran, Sragen, Sukoharjo, Slawi, Temanggung, Wonogiri, Wonosobo, Kota Salatiga, Kota Surakarta, Kota Tegal, Kota Pekalongan, Mungkid.

b.

Parameter Algoritma Parameter yang digunakan untuk algoritma genetika hibrida dengan skema

pencarian lokal dan algoritma genetika tanpa pencarian lokal berada dalam kondisi yang sama yaitu probabilitas mutasi 0.05, ukuran turnamen 3 dan nilai batas untuk skema pencarian lokal adaptif adalah 0.99997. Untuk setiap sampel

54

TSP dilakukan uji 10 kali, dengan jumlah populasi 7, 14, 20, 25, 35 dan jumlah generasi 70, 140, 200, 250, 350 pada masing-masing sample TSP. c.

Perbandingan hasil optimasi Dari 10 percobaan yang dilakukan didapatkan hasil yang berupa jarak

terbaik, jarak rata-rata dan jarak terburuk. Hasil percobaan yang dihasilkan oleh algoritma genetika hibrida dan algoritma genetika tanpa pencarian lokal dari 5 sample TSP dibandingkan satu sama lain.

55

BAB IV HASIL DAN PEMBAHASAN

4.1 Hasil Penelitian 4.1.1 Hasil Sistem TSP pada Android Setelah aplikasi Algoritma Genetika Hibrida dengan skema pencarian lokal adaptif dalam penyelesaian Travelling Salesman Problem pada Android selesai dibangun, maka tahap selanjutnya adalah tahap uji coba program. Tahap ini pengujian dilakukan dengan menjalankan program Travelling Salesman Problem yang sebagai inputan adalah data sampel case1, case2, case3, case4 dan case5, dengan parameter yang telah ditentukan. Dalam aplikasi yang telah dibuat, terdapat tampilan menu utama sebagai tampilan awal aplikasi.

Gambar 4.1 Tampilan Halaman Utama Aplikasi

54

55

Pada tampilan aplikasi pada Gambar 4.1 berfungsi untuk melakukan proses pencarian rute menggunakan algoritma genetika hibrida dengan skema pencarian lokal adaptif dengan beberapa tombol yang fungsinya antara lain: -

Tombol

Select

berfungsi

untuk

memasukkan

data

TSP

berupa

kabupaten/kota di Jawa Tengah.

Gambar 4.2 Tampilan Halaman Select Kota

Setelah kabupaten/kota selesai dipilih, Google Maps menampilakan data yang dipilih pada Maps yang ditandai dengan Markers.

56

Gambar 4.3 Tampilan Halaman Markers Kota -

Tombol Direction berfungsi untuk memilih Program A atau Program B yang digunakan untuk melakukan perhitungan TSP. Hasil perhitungan ditampilkan pada Gambar 4.4.

Gambar 4.4 Tampilan Halaman Pilih Algoritma

57

Setelah perhitungan selesai dilakukan oleh Algoritma, hasil berupa rute perjalanan ditampilakan kedalam Maps. Seperti pada Gambar 4.5 berikut.

Gambar 4.5 Tampilan Halaman Hasil Perhitungan

Perencanaan rute perjalanan dihasilkan dan ditampilkan, untuk melihat jarak dan waktu komputasi yang diperlukan dapat dilihat dengan tombol RESULT, untuk mengulang kembali sistem digunakan tombol RESET. -

Tombol Login berfungsi untuk masuk kedalam dashboard admin, yang dapat digunakan untuk melakukan penambahan atau mengubah data kabupaten/kota.

58

Gambar 4.6 Tampilan Dashboard Admin -

Tombol About berfungsi untuk menampilkan halaman informasi tentang aplikasi yang dikembangkan.

Gambar 4.7 Tampilan Halaman Tentang Aplikasi 4.1.2 Hasil Pengujian Hasil pengujian aplikasi yang dibangun dengan menggunakan 5 data sample TSP dengan parameter yang telah ditentukan pada setiap sampel. Kemudian dilakukan proses perhitungan sebanyak 20 kali dan didapatkan jarak terbaik, jarak rata-rata dan jarak terburuk.

59

a.

Percobaan menggunakan data case1 Pada data percobaan case1 jumlah kota 7 dipilih dengan jumlah populasi

dan jumlah generasi masing-masing 7 dan 70, hasil yang diperoleh dari percobaan case1 ditunjukkan pada table 4.1. Tabel 4.1 Hasil percobaan data case1

Percobaan

Jumlah Kota

Waktu Komputasi (detik)

Panjang Tur(Jarak)

GA

GA

HGA

HGA

1

7

0.058

0.207

4.785

4.785

2

7

0.036

0.12

4.785

4.785

3

7

0.033

0.115

4.785

4.785

4

7

0.032

0.127

4.785

4.785

5

7

0.035

0.122

4.785

4.785

6

7

0.035

0.272

5.226

4.785

7

7

0.032

0.181

4.785

4.785

8

7

0.031

0.125

5.226

4.785

9

7

0.032

0.13

5.226

4.785

10

7

0.04

0.117

5.166

4.785

0.0364

0.1516

4.9554

4.785

Terbaik

4.785

4.785

Terburuk

5.226

4.785

Rata-rata

60

b.



Percobaan

Jumlah Kota


Panjang Tur(Jarak)

GA

HGA

GA

HGA

1

14

0.314

1.571

7.98

7.354

2

14

0.587

1.478

6.961

6.936

3

14

0.296

1.822

7.563

6.936

4

14

0.346

1.582

6.936

6.936

5

14

0.307

1.32

7.316

7.316

6

14

0.238

1.367

7.795

7.616

7

14

0.613

1.458

7.563

6.936

8

14

0.227

1.35

7.951

7.616

9

14

0.464

1.462

8.84

7.583

10

14

0.228

1.508

8.589

6.936

0.362

1.4918

7.7494

7.2165

Terbaik

6.936

6.936

Terburuk

8.84

7.616

Rata-rata

61

c.



Percobaan

Jumlah Kota


Panjang Tur(Jarak)

GA

HGA

GA

HGA

1

20

0.981

5.94

9.294

9.756

2

20

0.708

5.613

9.694

7.321

3

20

1.011

5.418

8.35

8.35

4

20

0.712

5.851

8.386

8.82

5

20

0.902

5.352

9.894

7.942

6

20

0.911

5.573

9.63

8.482

7

20

0.939

5.096

10.531

7.507

8

20

0.979

5.157

8.457

8.728

9

20

0.872

5.899

8.176

7.944

10

20

0.89

6.156

10.6

8.135

0.8905

5.6055

9.3012

8.2985

Terbaik

8.176

7.321

Terburuk

10.6

9.756

Rata-rata

62

d.



Jumlah Percobaan Kota


Panjang Tur(Jarak)

GA

GA

HGA

HGA

1

25

1.758

11.922

10.823

9.074

2

25

1.647

12.739

10.288

10.003

3

25

1.571

12.62

11.28

9.859

4

25

1.735

13.071

9.915

9.235

5

25

1.825

13.302

9.854

8.807

6

25

1.62

13.663

10.942

10.692

7

25

1.666

12.551

10.791

9.71

8

25

1.869

12.161

11.461

11.375

9

25

1.576

11.868

10.833

10.739

10

25

2.179

12.682

10.479

7.913

1.7446

12.6579

10.6666

9.7407

Terbaik

9.854

7.913

Terburuk

11.461

11.375

Rata-rata

63

e.



Jumlah Percobaan Kota


Panjang Tur(Jarak)

GA

HGA

GA

HGA

1

35

4.960

45.126

12.024

11.326

2

35

5.325

44.329

12.275

12.275

3

35

5.547

45.331

12.691

12.18

4

35

5.322

45.835

12.367

12.999

5

35

5.223

46.189

11.945

11.759

6

35

5.238

48.627

13.171

12.746

7

35

5.376

53.441

13.012

12.985

8

35

5.349

52.412

12.119

12.894

9

35

5.698

47.316

12.072

11.184

10

35

5.702

49.433

14.049

12.373

5.374

47.803

12.5725

12.2721

Terbaik

11.945

11.184

Terburuk

14.049

12.999

Rata-rata

64

4.2 Pembahasan 4.2.1 Perbandingan Hasil Pengujian a.

Perbandingan Hasil Pengujian Jarak Perbandingan jarak terbaik, jarak terburuk dan jarak rata-rata yang dihitung

menggunakan algoritma genetika tanpa pencarian lokal dan algoritma genetika hibrida dengan skema pencarian lokal adaptif untuk case1, case2, case3, case4 dan case5 yang disajikan pada tabel 4.6. Tabel 4.6 Perbandingan Hasil Pengujian Jarak No

Data

Jumlah

Panjang Perjalanan (jarak)

Kota

GA Terbaik Terburuk

HGA Rata-Rata

Terbaik Terburuk

Rata-Rata

1

Case1

7

4.785

5.226

4.955

4.785

4.785

4.785

2

Case2

14

6.936

8.840

7.749

6.936

7.616

7.216

3

Case3

20

8.176

10.600

9.301

7.321

9.756

8.298

4

Case4

25

9.854

11.461

10.666

7.913

11.375

9.740

5

Case5

35

11.945

14.049

12.572

11.184

12.999

12.272

-

Perbandingan jarak perjalanan case1 Pada tabel 4.6 menunjukkan bahwa jarak terbaik, jarak terburuk dan jarak

rata-rata yang dihasilkan oleh algoritma genetika dalam percobaan case1 berturutturut yaitu 4.785, 5.226 dan 4.955. Sedangankan jarak terbaik, jarak terburuk dan jarak rata-rata yang dihasilkan oleh algoritma genetika hibrida dalam percobaan case1 berturut-turut yaitu 4.785, 4.785 dan 4.785.

65

-


rata-rata yang dihasilkan oleh algoritma genetika dalam percobaan case2 berturutturut yaitu 6.936, 8.840 dan 7.749. Sedangankan jarak terbaik, jarak terburuk dan jarak rata-rata yang dihasilkan oleh algoritma genetika hibrida dalam percobaan case2 berturut-turut yaitu 6.936, 7.616 dan 7.216. -






rata-rata yang dihasilkan oleh algoritma genetika dalam percobaan case5 berturut-

66

turut yaitu 11.945, 14.049 dan 12.572. Sedangankan jarak terbaik, jarak terburuk dan jarak rata-rata yang dihasilkan oleh algoritma genetika hibrida dalam percobaan case5 berturut-turut yaitu 11.184, 12.999 dan 12.272. Jadi dari kedua algoritma tersebut, algoritma genetika hibrida dengan skema pencarian lokal adaptif mampu mendapatkan hasil jarak terbaik pada pengujian case3, case4 dan case5, sedangkan pada case1, case2 jarak terbaik yang dihasilkan sama dengan jarak terbaik yang dihasilkan oleh algoritma genetika tanpa pencarian lokal. Algoritma genetika hibrida mendapatkan hasil yang optimal dibandingkan algoritma genetika tanpa pencarian lokal pada jarak rata-rata yang didapatkan dari rata-rata jarak 10 percobaan pada case1, case2, case3, case4 dan case5. Algoritma genetika tanpa pencarian lokal mendapatkan jarak terburuk pada pengujian case1, case2, case3, case4 dan case5. b.

Perbandingan Hasil Pengujian Waktu Komputasi Perbandingan

rata-rata

waktu

komputasi

yang

dibutuhkan

dalam

perhitungan jarak TSP menggunakan algoritma genetika tanpa pencarian lokal dan algoritma genetika hibrida dengan skema pencarian lokal adaptif untuk case1, case2, case3, case4 dan case5 yang disajikan pada tabel 4.7. Tabel 4.7 Perbandingan Hasil Pengujian Waktu Komputasi No

Data

1 2 3 4 5

case1 case2 case3 case4 case5

Jumlah Kota 7 14 20 25 35

Rata-Rata Waktu Komputasi (detik) GA HGA 0.0364 0.1516 0.362 1.4918 0.8905 5.6055 1.7446 12.6579 5.374 47.8039

67

Pada tabel 4.7 menunjukkan bahwa rata-rata waktu komputasi yang diperlukan algoritma genetika hibrida untuk melakukan perhitungan TSP lebih lama dibandingkan dengan algoritma genetika tanpa pencarian lokal pada semua data percobaan case1, case2, case3, case4 dan case5.

4.2.2 Analisis Hasil Pengujian a.

Analisis Perbandingan Jarak Berikut grafik perbandingan jarak yang dihitung menggunakan algoritma

genetika tanpa pencarian lokal dan algoritma genetika hibrida dengan skema pencarian lokal adaptif untuk case1, case2, case3, case4 dan case5. -

Analisis perbandingan jarak pada case1

Gambar 4.8 Grafik Jarak Perjalanan pada Case1 Pada gambar 4.8 menunjukkan perbandingan jarak untuk 7 kota pada case1 yang dihasilkan pada 10 kali percobaan oleh algoritma genetika dan algoritma

68

genetika hibrida. Jarak terbaik dihasilkan sama oleh kedua algoritma, algoritma genetika tanpa pencarian lokal mendapatkan jarak terbaik pada percobaan ke 1, 2, 3, 4, 5, 7, sedangkan jarak terbaik yang dihasilkan oleh algoritma genetika hibrida pada semua percobaan. Jarak terburuk dihasilkan oleh algoritma genetika tanpa pencarian lokal pada percobaan ke 6, 8, 9. -


Gambar 4.9 Grafik Jarak Perjalanan pada Case2 Pada gambar 4.9 menunjukkan perbandingan jarak untuk 14 kota pada case2 yang dihasilkan pada 10 kali percobaan oleh algoritma genetika dan algoritma genetika hibrida. Jarak terbaik dihasilkan sama oleh kedua algoritma, algoritma genetika tanpa pencarian lokal mendapatkan jarak terbaik pada percobaan ke-4, sedangkan jarak terbaik yang dihasilkan oleh algoritma genetika hibrida pada percobaan ke-2, 3, 4, 7, 10. Jarak terburuk dihasilkan oleh algoritma genetika tanpa pencarian lokal pada percobaan ke-9.

69

-


Gambar 4.10 Grafik Jarak Perjalanan pada Case3 Pada gambar 4.10 menunjukkan perbandingan jarak untuk 20 kota pada case3 yang dihasilkan pada 10 kali percobaan oleh algoritma genetika dan algoritma genetika hibrida. Jarak terbaik dihasilkan oleh algoritma genetika hibrida pada percobaan ke-2. Sedangkan jarak terburuk dihasilkan oleh algoritma genetika tanpa pencarian lokal pada percobaan ke-10. -


Gambar 4.11 Grafik Jarak Perjalanan pada Case4

70

Pada gambar 4.11 menunjukkan perbandingan jarak untuk 25 kota pada case4 yang dihasilkan pada 10 kali percobaan oleh algoritma genetika dan algoritma genetika hibrida. Jarak terbaik dihasilkan oleh algoritma genetika hibrida pada percobaan ke-10. Sedangkan jarak terburuk dihasilkan oleh algoritma genetika tanpa pencarian lokal pada percobaan ke-8. -


Gambar 4.12 Grafik Jarak Perjalanan pada Case5 Pada gambar 4.12 menunjukkan perbandingan jarak untuk 36 kota pada case5 yang dihasilkan pada 10 kali percobaan oleh algoritma genetika dan algoritma genetika hibrida. Jarak terbaik dihasilkan oleh algoritma genetika hibrida pada percobaan ke-9. Sedangkan jarak terburuk dihasilkan oleh algoritma genetika tanpa pencarian lokal pada percobaan ke-10.

71

Berdasarkan analisis pengujian jarak, algoritma genetika hibrida dengan skema pencarian lokal adaptif mampu mendapatkan hasil jarak terbaik dalam 3 dari 5 (60%) pengujian data sampel TSP yaitu pada pengujian case3, case4 dan case5, sedangkan pada case1, case2 jarak terbaik yang dihasilkan sama dengan jarak terbaik yang dihasilkan oleh algoritma genetika tanpa pencarian lokal. Dalam hal ini tidak berarti bahwa performa dari algoritma genetika hibrida tidak lebih baik daripada algoritma genetika tanpa pencarian lokal karena pada case1 jumlah kota kecil yang mencerminkan masalah yang sederhana. Dalam pengujian dengan data yang lebih kompleks terutama dimana jumlah kota lebih dari 17, algoritma genetika hibrida mendapatkan hasil yang lebih baik dibandingkan algoritma genetika tanpa pencarian lokal. Secara keseluruhan algoritma genetika hibrida mampu mengungguli algoritma genetika tanpa pencarian lokal pada jarak rata-rata yang didapatkan dari jarak rata-rata 10 percobaan pada case1, case2, case3, case4 dan case5. Algoritma genetika menunjukkan performa yang buruk ditunjukkan dalam mendapatkan jarak terburuk pada semua pengujian case1, case2, case3, case4 dan case5.

b.

Analisis Perbandingan Waktu Komputasi Berikut grafik perbandingan waktu komputasi yang dihasilkan dari 10

percobaan menggunakan algoritma genetika tanpa pencarian lokal dan algoritma genetika hibrida dengan skema pencarian lokal adaptif untuk case1, case2, case3, case4 dan case5.

72

-

Analisis perbandingan waktu komputasi pada case1

Gambar 4.13 Grafik Waktu Komputasi pada Case1 Pada gambar 4.13 menunjukkan perbandingan waktu komputasi untuk 7 kota pada case1 yang dihasilkan pada 10 kali percobaan oleh algoritma genetika dan algoritma genetika hibrida. Algoritma tercepat dalam menyelesaikan TSP pada case1 adalah algoritma genetika dengan rata-rata waktu komputasi 0,036 detik. Sedangkan algoritma genetika hibrida membutuhkan waktu komputasi rata-rata 0,151 detik. -


Gambar 4.14 Grafik Waktu Komputasi pada Case2

73

Pada gambar 4.14 menunjukkan perbandingan waktu komputasi untuk 14 kota pada case2 yang dihasilkan pada 10 kali percobaan oleh algoritma genetika dan algoritma genetika hibrida. Algoritma tercepat dalam menyelesaikan TSP pada case2 adalah algoritma genetika dengan rata-rata waktu komputasi 0,362 detik. Sedangkan algoritma genetika hibrida membutuhkan waktu komputasi ratarata 1,4918 detik. -


Gambar 4.15 Grafik Waktu Komputasi pada Case3 Pada gambar 4.15 menunjukkan perbandingan waktu komputasi untuk 20 kota pada case3 yang dihasilkan pada 10 kali percobaan oleh algoritma genetika dan algoritma genetika hibrida. Algoritma tercepat dalam menyelesaikan TSP pada case3 adalah algoritma genetika dengan rata-rata waktu komputasi 0,890 detik. Sedangkan algoritma genetika hibrida membutuhkan waktu komputasi ratarata 5,605 detik.

74

-


Gambar 4.16 Grafik Waktu Komputasi pada Case4 Pada gambar 4.16 menunjukkan perbandingan waktu komputasi untuk 25 kota pada case4 yang dihasilkan pada 10 kali percobaan oleh algoritma genetika dan algoritma genetika hibrida. Algoritma tercepat dalam menyelesaikan TSP pada case4 adalah algoritma genetika dengan rata-rata waktu komputasi 1,744 detik. Sedangkan algoritma genetika hibrida membutuhkan waktu komputasi ratarata 12.657 detik. -


Gambar 4.17 Grafik Waktu Komputasi pada Case5

75

Pada gambar 4.17 menunjukkan perbandingan waktu komputasi untuk 35 kota pada case5 yang dihasilkan pada 10 kali percobaan oleh algoritma genetika dan algoritma genetika hibrida. Algoritma tercepat dalam menyelesaikan TSP pada case5 adalah algoritma genetika dengan rata-rata waktu komputasi 5.374 detik. Sedangkan algoritma genetika hibrida membutuhkan waktu komputasi ratarata 47.803 detik. Berdasarkan analisis pengujian waktu komputasi, algoritma genetika mendapatkan hasil waktu komputasi tercepat pada semua pengujian data sampel TSP yaitu case1, case2, case3, case4 dan case5. Sedangkan algoritma genetika hibrida mendapatkan hasil waktu komputasi lebih lama dibandingkan algoritma genetika tanpa pencarian lokal, dalam hal ini dikarenakan pada algoritma genetika hibrida diperlukan perhitungan cosine similarity dan penggunaan pencarian lokal hill climbing yang membutuhkan waktu dalam masing-masing prosesnya sehingga waktu keseluruhan pada algoritma genetika hibrida menjadi lebih lama.

4.2.3 Analisis Penggunaan Pencarian Lokal dalam HGA Analisis penggunaan teknik pencarian lokal dalam algoritma genetika hibrida (HGA) dibagi menjadi dua bagian utama yaitu algoritma genetika yang menggunakan pencarian lokal dan algoritma genetika tanpa menggunakan pencarian lokal. Dihitung dalam satu proses evolusi dengan jumlah generasi yang telah ditentukan sebelumnya. Berikut presentase penggunaan pencarian lokal:

76

-

Penggunaan pencarian lokal dalam HGA pada case1

Gambar 4.18 Presentase Pencarian Lokal dalam HGA pada Case1 Hasil diperoleh dari proses perulangan 70 generasi pada case1, dengan mengidentifikasi berapa banyak pencarian lokal yang digunakan dalam proses perulangan

tersebut.

Presentase

yang

ditunjukkan

oleh

Gambar

4.18,

menunjukkan penggunaan pencarian lokal dalam GA sebesar 97,14%, dan GA yang tidak menggunakan pencarian lokal sebesar 2,86%. -


Gambar 4.19 Presentase Pencarian Lokal dalam HGA pada Case2

77

Hasil diperoleh dari proses perulangan 140 generasi pada case2, dengan mengidentifikasi berapa banyak pencarian lokal yang digunakan dalam proses perulangan

tersebut.

Presentase

yang

ditunjukkan

oleh

Gambar

4.19,

menunjukkan penggunaan pencarian lokal dalam GA sebesar 95.71%, dan GA yang tidak menggunakan pencarian lokal sebesar 4.29%. -



tersebut.

Presentase

yang

ditunjukkan

oleh

Gambar

4.20,

menunjukkan penggunaan pencarian lokal dalam GA sebesar 5,50%, dan GA yang tidak menggunakan pencarian lokal sebesar 94,50%.

78

-



tersebut.

Presentase

yang

ditunjukkan

oleh

Gambar

4.21,

menunjukkan penggunaan pencarian lokal dalam GA sebesar 5,20%, dan GA yang tidak menggunakan pencarian lokal sebesar 94,80%. -


Gambar 4.22 Presentase Pencarian Lokal dalam HGA pada Case5

79

Hasil diperoleh dari proses perulangan 350 generasi pada case5, dengan mengidentifikasi berapa banyak pencarian lokal yang digunakan dalam proses perulangan

tersebut.

Presentase

yang

ditunjukkan

oleh

Gambar

4.22,

menunjukkan penggunaan pencarian lokal dalam GA sebesar 4,86%, dan GA yang tidak menggunakan pencarian lokal sebesar 95,14%.

4.2.4 Komparasi dengan penelitian lain Algoritma genetika hibrida dengan skema pencarian lokal adaptif untuk menyelesaikan traveling salesman problem pada android telah secara efektif diterapkan seperti pada penelitian - penelitian berikut. Peneliti

Penelitian Lain

Algoritma genetika hibrida dengan Yun Y, et al., 2009. Algoritma genetika skema

pencarian

diimplementasikan salesman problem.

lokal pada

adaptif hibrida dengan skema pencarian lokal traveling adaptif diimplementasikan pada supply chain problem. Hasil yang didapatkan HGA mengungguli algoritma pembanding (metode enumerasi dan GA) dalam permasalahan supply chain. Rafsanjani,

et

al.,

2015.

Algoritma

genetika hibrida diimplementasikan pada traveling salesman problem. Hasil yang didapatkan

HGA

mengungguli

GA

80

sederhana

dalam

menemukan

solusi

optimal pada TSP. Algoritma genetika hibrida dengan Anupriya dan Saxena, 2013. Aplikasi skema pencarian lokal adaptif untuk android penyelesaian problem

traveling

salesman menggunakan

diimplementasikan

android.

navigasi

google

algoritma

maps genetika

pada sederhana untuk menyelesaikan traveling salesman problem. Hasil yang didapatkan GA dapat diimplementasikan pada google maps android untuk menyelesaikan TSP. Berninger,

2014.

Algoritma

genetika

diimplementasikan pada vehicle routing problem berbasis android. Hasil yang didapatkan

GA

mampu

diimplementasikan pada android untuk menyelesaikan TSP.

4.2.5 Hambatan Penelitian Dalam penelitian algoritma genetia hibrida dengan skema pencarian lokal untuk menyelesaikan traveling salesman problem pada android ini, terdapat hambatan dalam penelitian. Hambatan - hambatan tersebut diantaranya: 1.

Kesulitan mendapatkan akses download ke jurnal-jurnal internasional yang berkualitas, seperti sciencedirect dan ieee.

81

2.

Kesulitan mendapatkan buku-buku tentang algoritma genetika, pencarian lokal dan kesamaan kosinus di kampus Universitas Negeri Semarang.

3.

Keterbatasan pada perangkat keras dalam mengembagkan aplikasi android seperti laptop dengan spesifikasi tinggi untuk menjalankan software ADTBundle dan emulator Genymotion.

BAB V PENUTUP

5.1 Simpulan Sistem untuk menyelesaikan Traveling Salesman Problem dengan menggunakan metode algoritma genetika hibrida dengan skema pencarian lokal adaptif telah diimplementasikan dan dilakukan pengujian untuk membandingkan hasil yang didapatkan dengan algoritma genetika sederhana. Simpulan yang diperoleh adalah algoritma genetika hibrida dengan skema pencarian lokal adaptif efektif dalam menemukan jarak minimal pada penyelesaian Traveling Salesman Problem terutama dalam kasus dengan masalah yang lebih kompleks. Akan tetapi komputasi algoritma genetika hibrida membutuhkan waktu yang lebih lama dibandingkan algoritma genetika sederhana.

5.2 Saran Berdasarkan simpulan yang telah dikemukakan, dapat diajukan saran dalam pengembangan sistem lebih lanjut sebagai berikut: 1.

Melakukan pengujian dengan jumlah populasi dan kondisi berhenti yang berbeda untuk mengoptimalkan waktu komputasi dari algoritma genetika hibrida dengan skema pencarian lokal adaptif.

2.

Memperoleh jarak dari Google Maps API untuk mendapatkan perencanaan perjalanan yang nyata. 82

83

DAFTAR PUSTAKA Ahmed, Z.H. 2013. An experimental study of a hybrid genetic algorithm for the maximum traveling salesman problem. Mathematical Sciences, Springer Open Journal. Albayrak, M and Allahverdi, N. 2011. Development a new mutation operator to solve the Traveling Salesman Problem by aid of Genetic Algorithms. Expert Systems with Applications 38 (2011) 1313–1320. Anupriya dan Saxena, M. 2013. An Android Application for Google Map Navigation System Implementing Travelling Salesman Problem. International Journal of Computer & Organization Trends, Volume3 Issue4. Berninger, I. 2014. Vehicle Routing Problem on Android/iOS. Bachelor Thesis, University Innsbruck. Bryant, K. 2000. Genetic Algorithms and the Traveling Salesman Problem. Master's thesis, Harvey Mudd College. Changdar, C., Mahapatra, G.S., dan Pal, R.K. 2014. An efﬁcient genetic algorithm for multi-objective solid travelling salesman problem under fuzziness. Swarm and Evolutionary Computation. Chang, P.C., Huang, W.H., dan Ting, C.J. 2010. Dynamic diversity control in genetic algorithm for mining unsearched solution space in TSP problems. Expert Syst Appl 37:1863–1878. Davendra, D. 2010. Traveling salesman problem, theory and applications. InTech, Croatia. Developer Android. 2015. Get Started with Android http://developer.android.com/index.html. Akses: 26-07-2015.

Studio.

Fajardo, J.T.B., dan Oppus, C.M. 2010. A Mobile Disaster Management System Using the Android Technology. Wseas Transactions on Communications, Volume 9. Gupta, S., dan Panwar, P. 2013. Solving Travelling Salesman Problem Using Genetic Algorithm. IJARCSSE: Volume 3, Issue 6, June 2013. Homaifar, A., Guan, S., dan Liepins, G E. 1992. Schema analysis of the traveling salesman problem using genetic algorithms. Complex Systems, 6(2): 183– 217. Kusumadewi, S. 2003. Artificial Intelligence (Teknik dan Aplikasinya). Yogyakarta: Graha Ilmu. Larranaga, P., Kuijpers, C.M.H., Murga, R.H., Inza, I., dan Dizdarevic, S. 1999. Genetic algorithms for the travelling salesman problem: a review of representations and operators. Artif Intell Rev 13:129-170.

84

Liu, R., Jiang, Z., dan Geng, N. 2014. A hybrid genetic algorithm for the multidepot open vehicle routing problem. OR Spectrum (2014) 36:401–421. Manjoo, F. 2015. A Murky Road Ahead for Android, Despite Market Dominance. The New York Times. http://www.nytimes.com/2015/05/28/technology/per sonaltech/a-murky-road-ahead-for-android-despite-market-dominance.html? r =1. Akses: 27-07-2015. Michalewicz, Z. 1994. Genetic Algorithms + Data Structures= Evolution Program. Springer, Berlin. Rafsanjani, M.K., Eskandari, S., dan Saeid, A.B. 2015. A similarity-based mechanism to control genetic algorithm and local search hybridization to solve traveling salesman problem. Neural Comput & Applic (2015) 26:213– 222. Rani, K., dan Kumar, V. 2014. Solving Travelling Salesman Problem Using Genetic Algorithm Based On Heuristic Crossover and Mutation Operator. International Journal of Research in Engineering & Technology, Vol. 2, Issue 2, Feb 2014, 27-34. Razali, N.M. dan Geraghty, J. 2011. Genetic Algorithm Performance with Different Selection Strategies in Solving TSP. Proceedings of the World Congress on Engineering 2011 Vol II WCE 2011, July 6 - 8, 2011, London, U.K. Reese, A. 2009. Random number generators in genetic algorithms for unconstrained and constrained optimization. J Nonlinear Anal 71:679–692. Suyanto. 2005. Algoritma Genetika dalam MATLAB. Yogyakarta: C.V Andi Offset. Wang, Y. 2014. The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem. Comput Ind Eng 70:124–133. Yun, Y., Moon, C., dan Kim, D. 2009. Hybrid genetic algorithm with adaptive local search scheme for solving multistage-based supply chain problems. Comput Ind Eng 56:821–838. Yun, Y. 2006. Hybrid genetic algorithm with adaptive local search scheme. Computers & Industrial Engineering 51: 128–141. Zhao, F.G., Sun, J.S., Li, S.J., dan Liu, W.M. 2009. Hybrid Genetic Algorithm for the Traveling Salesman Problem with Pickup and Delivery. International Journal of Automation and Computing. Zukhri, Z. 2014. Algoritma Genetika: Metode Komputasi Evolusioner untuk Menyelesaikan Masalah Optimasi. Yogyakarta: C.V Andi Offset.

85

LAMPIRAN

85

Lampiran 1. Hasi Sistem Algoritma Penyelesaian TSP

Halaman Login Admin

Halaman Admin Edit Kota

Halaman Beranda Admin Halaman Admin Lihat Kota

Halaman Admin Tambah Kota

Halaman Awal User

86

Halaman User Memilih Kota

Halaman Penanda Kota

Halaman User Memilih Algoritma

Halaman Hasil Algoritma

Halaman Hasil Rute Perjalanan

Halaman Informasi User

87

Lampiran 2. Hasil Rute Perjalanan Optimal Menggunakan HGA

Rute Optimal HGA pada Case1





88

Lampiran 3. Grafik Nilai Fitness HGA

Grafik Fitness HGA pada Case1



Grafik Fitness HGA pada Case


89

Lampiran 4. Hasil Penggunaan Pencarian Lokal -

Penggunaan Pencarian Lokal pada Case1

Generasi Scosine(P) 1 0,99998 2 0,99999 3 0,99996 4 0,99999 5 1 6 0,99998 7 0,99999 8 0,99998 9 0,99999 10 0,99999 11 0,99999 12 0,99998 13 0,99999 14 0,99998 15 0,99998 16 0,99999 17 0,99999 18 0,99999 19 0,99997 20 0,99998 21 0,99998 22 0,99999 23 0,99999 24 0,99999 25 0,99998 26 0,99999 27 1 28 0,99999 29 0,99998 30 0,99998 31 1 32 0,99999 33 0,99999 34 0,99999 35 0,99999

Pencarian Lokal ya ya tidak ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya

Generasi Scosine(P) 36 0,99999 37 0,99998 38 0,99999 39 0,99999 40 0,99998 41 0,99998 42 0,99996 43 1 44 0,99999 45 1 46 0,99999 47 0,99998 48 0,99998 49 0,99999 50 1 51 1 52 0,99998 53 0,99999 54 0,99998 55 0,99999 56 0,99997 57 0,99999 58 0,99999 59 0,99998 60 1 61 0,99998 62 0,99999 63 0,99999 64 0,99998 65 0,99999 66 0,99999 67 0,99999 68 0,99999 69 0,99999 70 0,99999

Pencarian Lokal ya ya ya ya ya ya tidak ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya

90

-


Genera si 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

Scosine( P) 0,99995 0,99996 0,99997 0,99996 0,99996 0,99997 0,99996 0,99997 0,99998 0,99999 0,99998 0,99998 0,99997 0,99997 0,99998 0,99998 0,99998 0,99998 0,99997 0,99998 0,99998 0,99998 0,99997 0,99998 0,99998 0,99998 0,99998 0,99998 0,99998 0,99998 0,99996 0,99998 0,99998 0,99998 0,99998 0,99999 0,99998 0,99998

Pencarian Lokal tidak tidak ya tidak tidak ya tidak ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya tidak ya ya ya ya ya ya ya

Genera si 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108

Scosine( P) 0,99998 0,99998 0,99998 0,99998 0,99999 0,99999 0,99998 0,99998 0,99999 0,99998 0,99997 0,99998 0,99998 0,99998 0,99998 0,99999 0,99998 0,99998 0,99999 0,99999 0,99998 0,99998 0,99998 0,99998 0,99998 0,99999 0,99998 0,99999 0,99998 0,99998 0,99998 0,99998 0,99998 0,99999 0,99999 0,99998 0,99998 0,99998

Pencarian Lokal ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya

91

39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 -

0,99998 0,99998 0,99998 0,99999 0,99999 0,99999 0,99998 0,99998 0,99998 0,99998 0,99999 0,99998 0,99998 0,99998 0,99999 0,99999 0,99999 0,99998 0,99998 0,99998 0,99998 0,99998 0,99998 0,99999 0,99998 0,99998 0,99998 0,99998 0,99999 0,99998 0,99998 0,99998

ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya

109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140

0,99998 0,99998 0,99998 0,99998 0,99998 0,99999 0,99998 0,99998 0,99999 0,99999 0,99998 0,99998 0,99998 0,99998 0,99998 0,99998 0,99998 0,99998 0,99998 0,99998 0,99999 0,99999 0,99998 0,99999 0,99998 0,99998 0,99998 0,99998 0,99999 0,99999 0,99999 0,99998

ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya


Generasi Scosine(P) Pencarian Lokal Generasi Scosine(P) 1 0.99995 tidak 101 0.99998 2 0.99996 tidak 102 0.99998 3 0.99996 tidak 103 0.99998 4 0.99996 tidak 104 0.99998 5 0.99996 tidak 105 0.99998

Pencarian Lokal ya ya ya ya ya

92

6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

0.99996 0.99996 0.99997 0.99997 0.99998 0.99998 0.99997 0.99997 0.99998 1.99998 2.99998 3.99998 0.99997 0.99999 0.99998 0.99998 0.99998 0.99996 0.99996 0.99997 0.99997 0.99997 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99997 0.99999 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99996 0.99998

tidak tidak ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya tidak tidak ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya tidak ya

106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146

0.99998 0.99999 0.99998 0.99998 0.99998 0.99997 0.99998 0.99998 0.99999 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99999 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998

ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya

93

47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87

0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99999 0.99998 0.99997 0.99998 0.99997 0.99998 0.99996 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998

ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya tidak ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya

147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187

0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99999 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99999 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99999 0.99998 0.99998 0.99998 0.99998


94

88 89 90 91 92 93 94 95 96 97 98 99 100 -

0.99998 0.99998 0.99998 0.99999 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998

ya ya ya ya ya ya ya ya ya ya ya ya ya

188 189 190 191 192 193 194 195 196 197 198 199 200

0.99998 0.99998 0.99998 0.99998 0.99999 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998

ya ya ya ya ya ya ya ya ya ya ya ya ya


Generasi Scosine(P) Pencarian Lokal Generasi Scosine(P) 1 0.99995 tidak 126 0.99998 2 0.99994 tidak 127 0.99998 3 0.99995 tidak 128 0.99998 4 0.99995 tidak 129 0.99998 5 0.99995 tidak 130 0.99998 6 0.99996 tidak 131 0.99998 7 0.99996 tidak 132 0.99998 8 0.99996 tidak 133 0.99998 9 0.99996 tidak 134 0.99998 10 0.99996 tidak 135 0.99998 11 0.99996 tidak 136 0.99998 12 0.99996 tidak 137 0.99998 13 0.99997 ya 138 0.99998 14 0.99997 ya 139 0.99998 15 0.99998 ya 140 0.99998 16 0.99998 ya 141 0.99998 17 0.99998 ya 142 0.99998 18 0.99997 ya 143 0.99998 19 0.99997 ya 144 0.99997 20 0.99997 ya 145 0.99998 21 0.99997 ya 146 0.99998 22 0.99997 ya 147 0.99998 23 0.99998 ya 148 0.99998 24 0.99998 ya 149 0.99998

Pencarian Lokal ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya

95

25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

0.99998 0.99998 0.99998 0.99997 0.99997 0.99997 0.99997 0.99997 0.99998 0.99998 0.99998 0.99996 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99998 0.99998 0.99998

ya ya ya ya ya ya ya ya ya ya ya tidak ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya

150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190

0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99997 0.99997 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99997 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99997


96

66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106

0.99998 0.99998 0.99997 0.99997 0.99997 0.99998 0.99998 0.99998 0.99998 0.99998 0.99997 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99999 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99997 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998


191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231

0.99997 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99997 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99999 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99999 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99999 0.99998


97

107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 -

0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998

ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya

232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250

0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998

ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya


Generasi Scosine(P) Pencarian Lokal Generasi Scosine(P) 1 0.99995 tidak 176 0.99998 2 0.99994 tidak 177 0.99998 3 0.99995 tidak 178 0.99998 4 0.99995 tidak 179 0.99998 5 0.99995 tidak 180 0.99998 6 0.99996 tidak 181 0.99998 7 0.99996 tidak 182 0.99997 8 0.99996 tidak 183 0.99997 9 0.99996 tidak 184 0.99998 10 0.99996 tidak 185 0.99997 11 0.99996 tidak 186 0.99997 12 0.99996 tidak 187 0.99997 13 0.99996 tidak 188 0.99998 14 0.99996 tidak 189 0.99999 15 0.99998 ya 190 0.99999 16 0.99996 tidak 191 0.99998 17 0.99996 tidak 192 0.99998 18 0.99996 tidak 193 0.99997

Pencarian Lokal ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya

98

19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

0.99996 0.99996 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99997 0.99998 0.99998 0.99998 0.99998 0.99998 0.99997 0.99997 0.99997 0.99998 0.99998 0.99998 0.99998 0.99998 0.99997 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998

tidak tidak ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya

194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234

0.99998 0.99998 0.99998 0.99999 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99999 0.99998 0.99997 0.99997 0.99998 0.99997 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99999 0.99999 0.99998 0.99997 0.99997 0.99997 0.99997 0.99997 0.99998 0.99998 0.99998 0.99998


99

60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

0.99999 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99997 0.99998 0.99998 0.99998 0.99999 0.99999 0.99999 0.99999 0.99998 0.99998 0.99998 0.99999 0.99999 0.99999 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998


235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275

0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99997 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99997 0.99998 0.99998 0.99998 0.99998 0.99999 0.99999 0.99998 0.99999 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99999 0.99999


100

101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99999 0.99999 0.99999 0.99999 0.99998 0.99998 0.99999 0.99998 0.99998 0.99999 0.99999 0.99998 0.99997 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99997 0.99997 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998


276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316

0.99999 0.99998 0.99998 0.99999 0.99998 0.99999 0.99998 0.99998 0.99999 0.99999 0.99998 0.99998 0.99999 0.99999 0.99998 0.99998 0.99999 0.99998 0.99999 0.99998 0.99998 0.99998 0.99999 0.99998 0.99999 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998


101

142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175

0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99997 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99997 0.99997 0.99998 0.99999 0.99999 0.99998 0.99998 0.99998 0.99997 0.99997 0.99998

ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya

317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350

0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998 0.99998

ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya ya

102

Lampiran 5. Surat Penetapan Dosen Pembimbing

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

Recommend Documents