PENERAPAN ALGORITMA GENETIKA UNTUK PENCARIAN LOKASI ATM TERDEKAT BERBASIS ANDROID (Studi Kasus : Kota Tanjungpinang) Reza Kurniawan Mahasiswa Jurusan Teknik Informatika, Fakultas Teknik, Universitas Maritim Raja Ali Haji (
[email protected])
Hendra Kurniawan, S.Kom., M.Sc.Eng Dosen Program Studi Teknik Informatika, Fakultas Teknik, Universitas Maritim Raja Ali Haji
Muhamad Radzi Rathomi, S.Kom., M.Cs Dosen Program Studi Teknik Informatika, Fakultas Teknik, Universitas Maritim Raja Ali Haji
Abstrak : Kebutuhan akan informasi telah menjadi kebutuhan pokok masyarakat. Salah satu informasi yang dibutuhkan masyarakat adalah informasi yang berkaitan dengan tempat atau fasilitas umum seperti ATM (Automatic Teller Machine). Namun keberadaan ATM yang tersebar dalam suatu daerah menjadi kendala lain bagi masyarakat, dikarenakan jumlah ATM yang banyak tetapi tidak disertai informasi ATM jarak terdekat. penulis mencoba untuk mengembangkan suatu aplikasi yang menyediakan informasi mengenai pencarian lokasi ATM terdekat, dengan menggunakan Algoritma Genetika yang berbasis android. Ditunjukkan. ukuran pc yang digunakan selanjutnya 0.4 dengan nilai rata-rata fitness 0.0189458, Nilai rata - rata fitness yang dihasilkan pada proses pengaruh nilai pm menaik secara signifikan pada nilai pm 0.4 akan tetapi pada nilai pm 0.8 terjadi penurunan nilai fitness, hal ini disebabkan pemilihan kromosom secara acak pada proses crossover yang membuat jalur terpendek serta nilai fitness terbaik menjadi jalur yang optimal. Kata Kunci : Algoritma Genetika, ATM. Abstract : The need for information has become a basic necessity of society. One of the information needed by the public is information related to public places or facilities such as ATM (Automatic Teller Machine). But the existence of ATM scattered in a region to another obstacle for the community, due to the number of ATMs that many but not accompanied by the nearest ATM information. The author tries to develop an application that provides information about searching for the nearest ATM location, using an android based Genetic Algorithm. Showed. The pc size used next 0.4 with the average fitness value 0.0189458, the average value of the resulting fitness on the process of the influence of the pm value increased significantly at the value of 0.4 pm but at the value of 0.8 pm there is a decrease in fitness value, this is due to the selection of chromosomes in Random on the mutation process that makes the shortest path and the best fitness value become the path that is not optimal. Keywords: Genetic Algorithm, ATM. I. PENDAHULUAN A. Latar Belakang Kebutuhan akan informasi telah menjadi kebutuhan pokok masyarakat. Salah satu informasi yang dibutuhkan masyarakat adalah informasi yang
berkaitan dengan tempat atau fasilitas umum seperti ATM (Automatic Teller Machine). Namun keberadaan ATM yang tersebar dalam suatu daerah menjadi kendala lain bagi masyarakat, dikarenakan jumlah ATM yang banyak tetapi tidak disertai informasi ATM jarak terdekat. Masalah seperti ini dapat diatasi jika terdapat suatu sistem yang menyediakan informasi lokasi ATM yang tersebar diseluruh kota. Sehingga dapat memudahkan masyarakat yang ingin mengakses ATM terdekat. Terlebih pada saat ini hampir semua orang menggunakan teknologi smartphone yang mana hal tersebut dapat lebih mempermudah masyarakat untuk menyelesaikan persoalan diatas. Salah satu contoh kasus yang sering dijumpai adalah permasalahan tentang pencarian rute minimum yang dikenal dengan model kasus Shortest Path Problem atau disingkat dengan SPP. Penelitian tentang pencarian suatu lokasi tertentu sebenarnya sudah banyak diteliti oleh para peneliti terdahulu, dengan menggunakan berbagai macam metode dan teknik yang ada. Oleh karena itu pada penelitian ini, penulis mencoba untuk mengembangkan suatu aplikasi yang menyediakan informasi mengenai pencarian lokasi ATM terdekat, dengan menggunakan Algoritma Genetika yang berbasis android. Berdasarkan permasalahan diatas, maka diambil sebuah judul yaitu “Penerapan Algoritma Genetika
untuk Pencarian Lokasi ATM terdekat Berbasis Android “ B. Rumusan Masalah Berdasarkan uraian latar belakang di atas, maka dapat dirumuskan permasalahan penelitian yakni: 1. Bagaimana menyediakan informasi lokasi ATM terdekat yang ada di Kota Tanjungpinang. 2. Bagaimana mencari lokasi ATM terdekat menggunakan metode Genetika yang berbasis android. C. Batasan Masalah Adapun batasan masalah sebagai berikut: 1. Variabel yang digunakan adalah posisi user, posisi ATM, jarak antara simpang ke simpang dan simpang ke ATM. 2. Pada penelitian ini menggunakan perhitungan jarak yang diambil dari data titik simpang yang terhubung pada google map. 3. Penelitian ini dilakukan di Kecamatan Tanjungpinang Timur dan Kecamatan Bukit Bestari.
Menurut E. Satriyanto, 2009 dalam jurnal Sukaton, Algoritma Genetika beberapa definisi penting dalam Algoritma Genetika adalah sebagai berikut: a. Gen Sebuah nilai yang menyatakan satuan dasar yang membentuk arti tertentu. Dalam Algoritma Genetika, gen ini dapat berupa nilai binner, float, integer maupun karakter, atau kombinatorial. b. Kromosom Merupakan gabungan gen-gen yang membentuk nilai tertentu. c. Individu Menyatakan satu nilai atau keadaan yang menyatakan salah satu solusi yang mungkin dari permasalahan yang diangkat. Dalam beberapa masalah yang dapat dipecahkan dengan algoritma genetika, individu ini dapat juga merupakan kromosom itu sendiri. d. Populasi Merupakan sekumpulan individu yang akan diproses bersama dalam satu siklus proses evolusi. e. Generasi Menyatakan satu siklus proses evolusi atau satu iterasi di dalam algoritma genetika.
D. Tujuan Penelitian III. METODE PENELITIAN Tujuan dari penelitian ini adalah untuk mengembangkan suatu aplikasi berbasis Android pada perangkat mobile phone untuk memberikan informasi rute terpendek, serta bagaimana mencari lokasi ATM terdekat menggunakan Algoritma Genetika. E. Manfaat Penelitian Dapat membantu pengguna dalam mencari sebuah lokasi ATM terdekat, berdasarkan lokasi pengguna, sehingga memberikan informasi rute terpendek. II. TINJAUAN PUSTAKA A. Algoritma Genetika Algoritma Genetika merupakan solusi yang baik, tapi tidak mungkin dibuktikan secara deterministic. Algoritma Genetika mungkin tidak selalu mencapai hasil yang terbaik, tetapi biasa berharga dalam memecahkan masalah. Algoritma Genetika yang baik secara dramatis bisa mengurangi waktu yang diharuskan dalam memecahkan masalah. Meski tidak menjamin selalu dapat memecahkan masalah, tetapi seringkali memecahkan masalah dengan cukup baik untuk kebanyakan masalah. (Alamsyah, 2010).
Pada bab ini akan dipaparkan metodologi penelitian yang terdiri dari beberapa sub bab yaitu berupa obyek dan lokasi penelitian, metode pengumpulan data, metode pengembangan sistem, alat dan bahan penelitian dan kerangka pikir penelitian yang digunakan dalam menyelesaikan masalah penelitian. IV. PERANCANGAN DAN IMPLEMENTASI Pada bab ini akan dipaparkan metodologi penelitian yang terdiri dari beberapa sub bab yaitu berupa obyek dan lokasi penelitian, metode pengumpulan data, metode pengembangan sistem, alat dan bahan penelitian dan kerangka pikir penelitian yang digunakan dalam menyelesaikan masalah penelitian. A. Teknik Pengkodean Dalam algoritma genetika pengkodean sangatlah penting dikarenakan proses ini perkaitan dalam proses kromosom sebagai representasi penyelesaian masalah. Pengkodeaan ini tidak memiliki aturan khusus dapat dirancang dengan kode-kode tertentu dengan syarat dapat diproses oleh operator genetika untuk menyelesaikan masalah yang akan dioptimasikan. Teknik pengkodean adalah mengkodekan gen dari kromosom yng berisikan jumlah kode informasi yang
tersimpan dalam kromosom. Proses ini menggunakan teknik pengkodean int/varchar. Gen merupakan kombinasi dari kode simpang dan jarak. Diasumsikan dalam studi kasus ini yaitu: (a) Kode simpang :RHFxxx,DIPxxxdan AYxxx. (b) KodeATM:DIPBSMxx,DIPRIAxx,DIPBNIxx,DI PMNDxx,DIPDNMxx,DIPBIIxx,DIPBCAxx,DIP BRIxx,DIPBTNxx,DIPBKPxx,DIPBPRxx,RHFB CAxx,RHFMNDxx,RHFBNIxx,RHFBRIxx, RHFRIAxx, Jarak : xxxm (bilangan riil) Dalam hal ini dimana x merupakan bilangan ril yang digunakan untuk mengkodekan masing-masing komponen pencarian rute terpendek. Menentukan populasi awal dengan cara membangkitkan sejumlah kromosom dengan teknik random pada representasi gen. Dalam satu kromosom memiliki gabungan dari gen berdasarkan kode gen itu sendiri seperti kode simpang. Menenetukan populasi awal dengan cara membangkitkan sejumlah kromosom dengan teknik random pada representasi gen. Dalam satu kromosom memiliki gabungan dari gen berdasarkan kode gen itu sendiri seperti kode simpang, kode ATM, dan jarak. Tabel 1 Titik ATM KODE DIPBCA02 DIPBCA03 DIPBII01 DIPBII03 ......... ......... ......... RHFBRI02 RHFMND01 RHFMND02 RHFRIA01
ATM Jalan D.I pandjaitan, Bank Central Asia 02 Jalan D.I pandjaitan, Bank Central Asia 03 Jalan D.I pandjaitan, Bank International Indonesia 01 Jalan D.I pandjaitan, Bank International Indonesia 03 ......... ......... ......... Jalan R.H Fisabilillah, Bank Rakyat Indonesia 02 Jalan R.H Fisabilillah, Bank Mandiri 01 Jalan R.H Fisabilillah, Bank Mandiri 02 Jalan R.H Fisabilillah, Bank Riau 01
(Sumber :Data Titik Simpang dan Titik ATM diperoleh dari Google Maps 2016 ) Tabel 2. Hasil Jalur Terpendek DIP014 ke DIPBNI04 Rute
Jarak (m)
NIlai Fitness
DIP014 -> DIPBRI02
52
0.019230
Diasumsikan satu populasi memiliki 3 (tiga) node dan masing – masing node memiliki panjang gen yang berbeda-beda jumlahnya disesuaikan dengan kemungkinan jalur yang akan dilewati, dimana node tersebut terdiri dari gabungan beberapa variabel Kode Simpang, Kode ATM dan Jarak.
B. Pencarian Lokasi ATM terdekat dari titik awal Sebelum pembangkitan populasi awal pada kromosom langkah awal yaitu mencari semua lokasi ATM berdasarkan lokasi yang dipilih oleh user, kemudian pada masing-masing ATM dihitung semua jarak agar mendapatkan lokasi ATM yang terdekat. Lokasi ATM yang terdekat akan dicari rute terpendek menggunakan algoritma genetika dan algoritma djikstra. Diasumsikan lokasi yang dipilih user adalah DIP014 sedangkan lokasi ATM yang berada pada titik DIP014 adalah DIPBNI03, DIPBNI05 dan RHFBTN01 dengan jarak yaitu : DIPBNI03 = 350 m, DIPBNI05 = 400 m dan RHFBTN01 = 979 m, maka lokasi ATM yang terdekat dari DIP014 adalah DIPBNI03, kemudian dilanjukan dengan proses algoritma djikstra yang berfungsi sebagai mencari jalur-jalur yang kemungkinan dilewati setelah itu menggunakan algoritma genetika. C. Pembangkitan Populasi Awal dan Kromosom Pada pencarian kromosom awal menggunakan algoritma djikstra, yang mana mendapatkan jalur jalur yang dilewati dari titik awal yaitu titik DIP014 mendapatkan titik ATM terdekat DIPBNI04 yang berjarak 63 m, , DIPBKP01 berjarak 90 m, dan DIPBRI02 93 m. Tabel 3. Pembangkitan Populasi Awal DIP014 ke titik ATM DIPBNI04, DIPBKP01, DIPBRI02 KROMOSO M1 JARAK KROMOSO M2 JARAK KROMOSO M3 JARAK KROMOSO M4 JARAK KROMOSO M5 JARAK KROMOSO M6 JARAK KROMOSO M7 JARAK KROMOSO M8 JARAK KROMOSO M9 JARAK
DIP0 14 0 DIP0 14 0 DIP0 14 0 DIP0 14 0 DIP0 14 0 DIP0 14 0 DIP0 14 0 DIP0 14 0 DIP0 14 0
DIP015 60 DIP031 70 DIPBNI 04 63 DIBKP 01 54 DIP031 70 DIP015 60 DIPBRI 02 52
DIP031 14 DIPBNI 04 7
DIPBNI 04 7 DIP015 0
DIP015 0
DIP031 0
DIP015 0 DIBKP 01 16
DIP031 0
DIP031 14
DIP031 70
DIP015 0 DIPBRI 02 19
DIP015 60
DIP031 14
DIP015 0 DIBKP 01 16 DIP031 0 DIP015 0 DIPBRI 02 19
DIBKP 01 0 DIBKP 01 0 DIBKP 01 0 DIPBNI 04 0 DIPBNI 04 0 DIPBNI 04 0 DIPBNI 04 0 DIPBNI 04 0 DIPBNI 04 0
DIPBRI 02 0 DIPBRI 02 0 DIPBRI 02 0 DIPBRI 02 0 DIPBRI 02 0 DIPBRI 02 0 DIBKP 01 0 DIBKP 01 0 DIBKP 01 0
D. Menghitung Nilai Fitness Nilai fitness berfungsi untuk mengukur masingmasing kualitas kromosom dan menandakan seberapa optimal solusi yang diperoleh. Hasil dari nilai fitness akan digunakan pada proses selanjutnya pada tahapan
seleksi untuk mencari kromosom terbaik yang akan menjadi solusi terbaik dalam penyelesaian masalah menggunakan persamaan fungsi objektif. Kemudian untuk masing-masing kromosom dihitung total jarak, seperti persamaan 1. Dalam penelitian ini dihitung nilai fitness masingmasing kromosom, diasumsikan dalam mencari rute terpendek dari titik simpang DIP014 ke ATM BNI DIPBNI04 memiliki 9 kromosom dan masing-masing kromosom dihitung nilai fitnessnya dengan menggunakan fungsi objektif seperti tabel 4 berikut :
digunakan untuk kawin silang adalah nilai acak yang dibawah 0.4. (b) Menentukan titik potong crossover secara acak antara [0.N] dimana N merupakan jumlah gen dalam 1 kromosom, diasumsikan terdapat 6 gen dalam 1 kromosom, maka bilangan acak (c) Menukar gen – gen antara 2 (dua) induk node untuk menghasilkan offspring. Tabel 6. Membangkitkan Bilangan Acak Lebih Kecil dari Pc (0.5) KROMOSOM 1 2 3 4 5 6 7 8 9
Tabel 4. Menghitung Nilai Fitness menggunakan Fungsi objektif KROMOSOM
TOTAL JARAK
1 2 3 4 5 6 7 8 9
81 m 77 m 63 m 54 m 86 m 90 m 52 m 89 m 93 m
NILAI FITNES Jan-81 Jan-81 Jan-63 Jan-54 Jan-86 Jan-90 Jan-52 Jan-89 Jan-93
0.012345679 0.012987013 0.015873016 0.018518519 0.011627907 0.011111111 0.019230769 0.011235955 0.010752688
E. Seleksi Seleksi merupakan proses yang dilakukan untuk menyaring semua node hasil dari proses fitness sebelumnya dengan mengambil nilai fitness terbesar untuk membentuk susunan populasi baru dengan menggunakan metode elitism, dimana nilai fitness terbesar menempati kromosom awal. Tabel 5. Total nilai fitness KROMOSOM
Nilai fitness
1
0.019230769
2 3 4 5 6 7 8 9
0.018518519 0.015873016 0.012987013 0.012345679 0.011627907 0.011235955 0.011111111 0.010752688
F. Crossover (Pindah Silang) Pada penelitian ini crossover menggunakan metode single-point Crossover. Langkah – langkah metode one cut-point Crossover adalah : (a) Menentukkan besar Pc (Probilitas Crossover) dan Pc diset 0,5. Membangkitkan bilangan acak antara [0,1] untuk masing – masing kromosom, diasumsikan bilangan acak yang di bangkitkan [0,2;0,3;0.5;0,6;0,6;0,7;0,8;0,9;0.7]. Maka diketahui bilangan acak yang dibangkitkan adalah kromosom 1 (0,2) dan kromosom 2 (0,3) dikarnakan nilai Pc 0,5 maka kromosom yang
BILANGAN ACAK 0.4867061243092472 0.3819988833369491 0.8660740478019899 0.6630592589235064 0.5591515702791332 0.8331413208219536 0.7892259575538446 0.7432265288894959 0.7987308579907719
Maka dapat dilihat dari pembangkitan bilangan acak dari Pc 0,5 terjadi pada kromosom 1 dan kromosom 2 dikarenakan memiliki nilai kecil dari Pc 0,5. Berikutnya mementukkan titik potong secara acak [0,5] tabel 7 berikut : Tabel 7. Menentukan Titik Potong Secara Acak (Diasumsikan titik potong secara acak 3) KROMOS OM 1 KROMOS OM 2 KROMOS OM 3 KROMOS OM 4 KROMOS OM 5 KROMOS OM 6 KROMOS OM 7 KROMOS OM 8 KROMOS OM 9
DIP0 14 DIP0 14 DIP0 14 DIP0 14 DIP0 14 DIP0 14 DIP0 14 DIP0 14 DIP0 14
DIP031
DIPBK P01
DIP015
DIP031
DIP015
DIP031 DIPBRI 02
DIP031 DIP015 DIP031 DIPBK P01 DIPBNI 04 DIPBRI 02
DIP031 DIPBNI 04
DIP015 DIPBK P01 DIPBNI 04 DIP015 DIPBRI 02 DIP015
DIP015
DIP031
DIP015
DIP031
DIP015
DIP031
DIPBN I04 DIPBN I04 DIPBK P01 DIPBNI 04 DIPBNI 04 DIPBK P01 DIPBNI 04 DIPBK P01 DIPBNI 04
DIPBR I02 DIPBR I02 DIPBRI 02 DIPBK P01 DIPBK P01 DIPBRI 02 DIPBRI 02 DIPBRI 02 DIPBK P01
Maka dapat dilihat titik potong terjadi pada gen DIPBKP01 (gen ke 3) yang ditentukan secara acak. Sehingga menghasilkan crossover kedua kromosom seperti Tabel 8 berikut : Tabel 8. Sebelum Kawin silang :
Sebelum Kawin Silang: KROMOS OM 1 KROMOS OM 2 KROMOS OM 3 KROMOS OM 4 KROMOS OM 5
DIP0 14 DIP0 14 DIP0 14 DIP0 14 DIP0 14
DIP031
DIPBK P01
DIP015
DIP031
DIP015 DIPBK P01 DIPBNI 04
DIP015
DIP031
DIP031
DIPBRI 02
DIP015
DIP031
DIPBRI 02
DIP015
DIPBNI 04 DIPBNI 04 DIPBK P01 DIPBNI 04 DIPBNI 04
DIPBRI 02 DIPBRI 02 DIPBRI 02 DIPBK P01 DIPBK P01
KROMOS OM 6 KROMOS OM 7 KROMOS OM 8 KROMOS OM 9
DIP0 14 DIP0 14 DIP0 14 DIP0 14
DIP031 DIPBK P01 DIPBNI 04 DIPBRI 02
DIPBNI 04
DIP015
DIP015
DIP031
DIP015
DIP031
DIP015
DIP031
DIPBK P01 DIPBNI 04 DIPBK P01 DIPBNI 04
DIPBRI 02 DIPBRI 02 DIPBRI 02 DIPBK P01
Tabel 9. Sesudah Kawin Silang Sesudah Kawin Silang: KROMO SOM 1 KROMO SOM 2 KROMO SOM 3 KROMO SOM 4 KROMO SOM 5 KROMO SOM 6 KROMO SOM 7 KROMO SOM 8 KROMO SOM 9
DIP01 4 DIP01 4 DIP01 4 DIP01 4 DIP01 4 DIP01 4 DIP01 4 DIP01 4 DIP01 4
DIP03 1 DIP01 5 DIP01 5 DIP03 1 DIP01 5 DIP03 1 DIPB KP01 DIPB NI04 DIPB RI02
DIPB KP01 DIP03 1 DIP03 1 DIPB RI02 DIP03 1 DIPB NI04 DIP01 5 DIP01 5 DIP01 5
DIPB KP01 DIP0 15 DIPB NI04 DIP01 5 DIPB RI02 DIP01 5 DIP03 1 DIP03 1 DIP03 1
DIPB NI04 DIPB NI04 DIPB KP01 DIPB NI04 DIPB NI04 DIPB KP01 DIPB NI04 DIPB KP01 DIPB NI04
DIPBRI 02 DIPBRI 02 DIPBRI0 2 DIPBKP 01 DIPBKP 01 DIPBRI0 2 DIPBRI0 2 DIPBRI0 2 DIPBKP 01
G. Mutasi Mutasi dalam penelitian ini menggunakan reciprocal exchange mutation yaitu dengan cara memilih kromosom secara acak dan memilih 2 (dua) gen secara acak pada kromosom kemudian menukar nilai 2 (dua) gen tersebut, diasumsikan kromosom yang terpilih kromosom 5, maka proses informasi yang akan di ubah adalah titik simpang dan jarak seperti tabel 10 berikut :
KROMO SOM 9
DIP 014
DIPBR I02
DIP0 15
DIPBNI 04
DIP031
DIPB KP01
Maka setelah didapatkan susunan populasi setelah mutasi dilakukan evaluasi fungsi fitness dari kromosom baru di peroleh masing - masing nilai fitness kromosom tersebut. Tabel 12. Hitung Nilai Fitness setelah Mutasi
KROMOSOM
Total Jarak
1 2 3 4 5 6 7 8 9
86 74 81 89 81 77 54 63 52
Fitness Jan-86 Jan-74 Jan-81 Jan-89 Jan-81 Jan-77 Jan-54 Jan-63 Jan-52
0.011627 0.013513 0.012345 0.011235 0.012345 0.012987 0.018518 0.015873 0.019230
Tabel 13. Perbandingan Hasil Nilai Fitness Populasi Awal dan Nilai Fitness Offspring KROMOSOM 1 2 3 4 5 6 7 8 9
Nilai Fitness Populasi awal 0.01234 0.01298 0.01587 0.01851 0.01162 0.01111 0.01923 0.01123 0.01075
Nilai Fitness offspring 0.011627 0.013513 0.012345 0.011235 0.012987 0.018518 0.015873 0.019230 0.011627
Dari 1 (satu) iterasi proses algoritma genetika dapat dilihat nilai fitness suatu node mendekati lebih baik atau optimum. Tabel 14. Pengecekan jarak pada DIPBNI04
Tabel 10. Sebelum mutasi KROMOS OM 1 KROMOS OM 2 KROMOS OM 3 KROMOS OM 4 KROMOS OM 5 KROMOS OM 6 KROMOS OM 7 KROMOS OM 8 KROMOS OM 9
DIP 014 DIP 014 DIP 014 DIP 014 DIP 014 DIP 014 DIP 014 DIP 014 DIP 014
DIP0 31 DIP0 15 DIP0 15 DIP0 31 DIP0 15 DIP0 31 DIPB KP01 DIPB NI04 DIPB RI02
DIPB KP01 DIP03 1 DIP03 1 DIPB RI02 DIP03 1 DIPB NI04 DIP01 5 DIP01 5 DIP01 5
DIPB KP01 DIP01 5 DIPB NI04 DIP01 5 DIPB RI02 DIP01 5 DIP03 1 DIP03 1 DIP03 1
DIPBNI 04 DIPBNI 04 DIPBK P01 DIPBNI 04 DIPBNI 04 DIPBK P01 DIPBNI 04 DIPBK P01 DIPBNI 04
DIPBRI 02 DIPBRI 02 DIPBRI 02 DIPBK P01 DIPBK P01 DIPBRI 02 DIPBRI 02 DIPBRI 02 DIPBK P01
Tabel 11. Sesudah Mutasi KROMO SOM 1 KROMO SOM 2 KROMO SOM 3 KROMO SOM 4 KROMO SOM 5 KROMO SOM 6 KROMO SOM 7 KROMO SOM 8
DIP 014 DIP 014 DIP 014 DIP 014 DIP 014 DIP 014 DIP 014 DIP 014
DIP03 1 DIP01 5 DIP01 5 DIP03 1 DIP01 5 DIP03 1 DIPB KP01 DIPB NI04
DIPB KP01 DIP0 31 DIP0 31 DIPB RI02 DIP0 31 DIPB NI04 DIP0 15 DIP0 15
DIPBK P01 DIP015 DIPBN I04 DIP015 DIPBN I04 DIP015 DIP031 DIP031
DIPBNI 04 DIPBNI 04 DIPBKP 01 DIPBNI 04 DIPBRI 02 DIPBKP 01 DIPBNI 04 DIPBKP 01
DIPB RI02 DIPB RI02 DIPB RI02 DIPB KP01 DIPB KP01 DIPB RI02 DIPB RI02 DIPB RI02
KROMOSOM 1 2 3 4 5 6 7 8 9
Total Jarak 86 74 81 89 81 77 75 63 73
Fitness 0.011627 0.013513 0.012345 0.011235 0.012345 0.012987 0.013333 0.015873 0.013698
Tabel 15. Pengecekan jarak dan nilai fitness pada DIPBKP01 KROMOSOM 1 2 3 4 5 6 7 8 9
Total Jarak 86 Tidak Valid 81 89 81 77 54 93 73
Fitness 0.0116279 Tidak Valid 0.0123459 0.0112359 0.0123456 0.0129870 0.0185185 0.0107526 0.0136986
Tabel 16. Pengecekan jarak dan nilai fitness pada DIPBRI02 KROMOSOM 1 2 3
Total Jarak 86 74 81
Fitness 0.011627 0.013513 0.012345
4 5 6 7 8 9
89 81 77 75 93 52
0.011235 0.012345 0.012987 0.013333 0.010752 0.019230
Tabel 21. Hasil Uji Coba 1 nilai PC
H. Elitisme Sebuah metode untuk mengumpulkan semua individu dalam populasi parent dan offspring dalam satu penampungan, ukuran populasi individu terbaik dalam penampungan akan lolos untuk masuk kedalam generasi selanjutnya dan mempertahankan hasil fitness terbaik. Tabel 17. Hasil Nilai fitness terbaik Kromosom 9
DIP014
DIPBRI02
Nilai Fitness
JARAK
0
52
0.019230
I. Syarat Berhenti Dalam penelitian ini yang dikatakan syarat berhenti proses algoritma genetika ialah iterasi/generasi mencapai nilai maksimum dan mendapatkan hasil rute terpendek. Diasumsikan kromosom 9 memiliki hasil rute terpenek. Tabel 18. Solusi yang Terpilih Kromosom 9 (Sembilan) Kromosom 9
DIP014
DIPBRI02
Nilai Fitness
0
52
0.019230
JARAK
Fitness Percobaan Ke-
Pc = 0.2, Pm = 0.25
Pc = 0.4, Pm = 0.25
Pc = 0.8, Pm = 0.25
0.0192307 0.0158730 0.0192307 0.0158730 0.0158730
0.0192307 0.0185185 0.0192307 0.0185185 0.0192307
0.0185185 0.0185185 0.0185185 0.0185185 0.0192307
0.017216
0.0189458
0.018661
1 2 3 4 5 Rata – Rata Fitness
Uji coba 1 yang dilakukan pada rute DIP014 ke DIPBRI02 mendapatkan hasil pada tabel 24. Pada tabel 21 ditunjukkan bahwa nilai rata – rata fitness menghasilkan nilai yang berbeda dengan ukuran nilai pc yang digunakan yaitu 0.2 dan nilai rata-rata fitness sebesar 0.017216 kemudian ukuran pc yang digunakan selanjutnya 0.4 dengan nilai rat-rata fitness 0.0189458, ukuran pc yang digunakan selanjutnya 0.8 dengan nilai rata-rata fitness 0.018661. Gambar 1. Grafik Perbandingan Nilai PC
Maka rute terpendek dari titik simpang DIP014 yang terpilih dari rute kromosom 9 adalah seperti berikut : Tabel 19. Rute terpendek dari titik simpang DIP014 ke DIPBNI04 Kromosom 9 JARAK
DIP014
DIPBRI02
Total Jarak
Nilai Fitness
0
52
52
0.019230
V. ANALISA DAN PEMBAHASAN Pada bab ini akan dijelaskan tentang analisa dari pembahasan pada bab-bab sebelumnya, maka pada bab ini dapat diambil analisa bagaimana cara mencari rute terdekat menggunakan Algoritma Genetika dengan 2 uji coba. Uji coba 1 yaitu pengaruh kombinasi ukuran pc uji coba ini akan dilakukan 5 kali percobaan. Pengujian dilakukan di Kota Tanjungpinang dengan rute yang digunakan adalah DIP014 ke DIPBTN03. A. Hasil Percobaan
Gambar 1 menunjukkan hasil perbandingan ukuran pc terhadap rata – rata nilai fitness yang dihasilkan. Nilai rata - rata fitness yang dihasilkan pada proses pengaruh nilai pc tidak tetap / stabil. Hal ini disebabkan pengaruh proses acak pada crossover yang memilih kromosom untuk dijadikan sebagai kandidat, terpilihnya kromosom sebagai kandidat pada proses crossover dipengaruhi oleh nilai pc, apabila nilai random pada kromosom dibawah nilai pc, maka 2 kromosom yang akan dilakukan proses crossover yang mengakibatkan nilai fitness berubah-ubah.
1. Hasil dan Analisa Uji Coba 1 Pengaruh Nilai PC
2. Hasil dan Analisa Uji Coba 2 Pengaruh Nilai PM
Parameter yang digunakan pada uji coba 1 ini ditunjukkan seperti pada tabel 23.
Parameter yang digunakan pada uji coba 2 ini ditunjukkan seperti pada tabel 22.
Tabel 20. Parameter Uji Coba 1 No 1
Pc 0.2, 0.4, 0.8
𝑷𝒎 0.25
Iterasi 15
Tabel 22. Parameter Uji Coba 2 No 1
Pc 0.4
𝑷𝒎 0.2, 0.4, 0.8
Iterasi 15
Uji coba 2 yang dilakukan pada rute DIP014 ke DIPBRI02 mendapatkan hasil pada tabel 23. Tabel 23. Hasil Uji Coba 2 nilai PM Percobaan Ke-
Fitness Pc = 0.4, Pm = 0.2 0.01923 0.01587 0.01923 0.01923 0.01587 0.01066
1 2 3 4 5 Rata – Rata Fitness
Pc = 0.4, Pm = 0.4 0.03333 0.01923 0.01851 0.01923 0.05263 0.0986
Pc = 0.4, Pm = 0.8 0.01923 0.0625 0.01851 0.0625 0.01923 0.0363
Gambar 2. Grafik Perbandingan Nilai PM
Gambar 2 menunjukkan hasil perbandingan ukuran pm terhadap rata – rata nilai fitness yang dihasilkan. Nilai rata - rata fitness yang dihasilkan pada proses pengaruh nilai pm menaik secara signifikan pada nilai pm 0.4 dan nilai pm menurun pada nilai pm 0.8. Hal ini disebabkan pengaruh proses acak pada mutasi yang memilih kromosom untuk dijadikan sebagai kandidat, terpilihnya kromosom sebagai kandidat pada proses mutasi dipengaruhi nilai pm. 3. Hasil dan Analisa Uji Coba 3 Pengaruh Nilai Generasi Tabel 24. Hasil Uji Coba 3 Pengaruh nilai generasi Percobaan Ke-
1 25 50 100 200 Rata Rata Fitness
Fitness Pc = 0.4, Pm = 0.4 0.05263 0.00833 0.00456 0.00555 0.00833
Pc = 0.4, Pm = 0.4
Pc = 0.4, Pm = 0.4 0.00833 0.00833 0.00833 0.00555 0.00833
Pc = 0.4, Pm = 0.4 0.00555 0.00833 0.00555 0.00456 0.00833
Pc = 0.4, Pm = 0.4 0.00555 0.00555 0.00833 0.00833 0.00456
0.00555 0.00555 0.00833 0.00833 0.00833 0.007219
0.007774
0.00646
0.00646
Gambar 3. Grafik Perbandingan Nilai Generasi
Gambar 3 menunjukkan hasil perbandingan ukuran nilai generasi terhadap rata – rata nilai fitness yang dihasilkan. Nilai rata - rata fitness yang dihasilkan pada proses pengaruh nilai generasi menaik secara signifikan pada generasi 1 dengan fitness 0.01581 dan nilai fitness menurun pada generasi ke 25 dengan fitness 0.007219. Hal ini disebabkan pengaruh proses acak pada mutasi yang memilih kromosom untuk dijadikan sebagai kandidat, terpilihnya kromosom sebagai kandidat pada proses mutasi dipengaruhi nilai pm dan hal ini juga disebabkan pengaruh proses acak pada crossover yang memilih kromosom untuk dijadikan sebagai kandidat, terpilihnya kromosom sebagai kandidat pada proses crossover dipengaruhi oleh nilai pc, apabila nilai random pada kromosom dibawah nilai pc, maka 2 kromosom yang akan dilakukan proses crossover yang mengakibatkan nilai fitness berubah-ubah. 4. Solusi Optimum Berdasarkan jalur yang digunakan pada penelitian ini yaitu DIP014 ke DIPBRI02 didapatkan solusi terbaik atau rute terdekat menggunakan Algoritma Genetika yaitu dengan jarak terpendek 52 meter serta nilai fitness terbaik 0.019230. Berikut merupakan jalur terpendek menggunakan algoritma genetika pada rute DIP014 ke DIPBRI02.
– 0.01581
Gambar 4. Hasil jalur terpendek DIP014 ke DIPBNI04 pada peta
VI. PENUTUP 6.1. Kesimpulan Berdasarkan hasil Analisa dan pembahasan bab sebelumnya maka dapat disimpulkan beberapa hal, diantaranya: 1. Hasil Pencarian lokasi ATM terdekat menggunakan Algoritma Genetika dipengaruhi oleh nilai random pada probabilitas crossover. 2. Hasil Penerapan Algoritma Genetika dalam penelitian Pencarian Lokasi ATM terdekat pada perangkat mobile phone dapat memberikan informasi berupa jalur terpendek. 6.2. Saran Dari penelitian yang dilakukan ada beberapa saran yang akan diberikan untuk pengembangan lebih lanjut, diantaranya yaitu: 1. Pada penelitian selanjutnya cukup menggunakan Algoritma Djikstra, algoritma ini cocok digunakan untuk pencarian rute terpendek dan menghemat waktu pencarian rute terpendek. 2. Penelitian selanjutnya perlu dikembangkan dengan membandingkan Algoritma Djikstra, Genetika, Ant Colony serta Bee Colony berdasarkan waktu proses Algoritma, tujuannya agar memudahkan user untuk mencari rute terpendek pada Lokasi ATM. REFERENSI Alamsyah, 2010. Pemanfaatan Metode Heuristik Pada Pencarian Jalur Terpendek dengan Algoritma Genetika, Jurnal SMARTek, 8(4), 1-10. Anupriya., dan Saxena., M., 2013.An Android Application for Google Map Navigation System Implementing Travelling Salesman Problem. International Journal of Computer & Organization Trends, 3(4), 1-4. Hannawati, A., Thiang., Eleazar., 2002. Pencarian Rute Optimum Menggunakan Algoritma Genetika, Jurnal Mahasiswa Program Studi Teknik Elektro, 2(2), 1-6. Ichwan, M. dan Hakiky, F., 2011. Pengukuran Kinerja Goodreads Application Programming Interface (API) pada aplikasi Mobile Android, Jurnal Mahasiswa Program Studi Teknik Informatika. Institut Teknologi Nasional Bandung 2(2), 1-9 Joni, I.D.M.A.B., dan Nurcahyawati, V., 2012. Penetuan Jarak Terpendek Pada Jalur Distribusi Barang di Pulau Jawa dengan Menggunakan Algoritma Genetika, Jurnal Nasional Pendidikan Teknik Informatika, 1(3), 1-15. Lengkong, H.N., Sinsuw, A.A.E., Lumenta, A.S.M., 2015. Perancangan Penunjuk Rute pada Kendaraan Pribadi menggunakan Aplikasi Mobile GIS Berbasis Android Yang Terintegrasi pada Google Maps, Jurnal Mahasiswa Teknik Elektro dan Komputer.
Mahmudy, W.F., 2013. Modul Algoritma Evolusi, Malang, Program Teknologi Informasi dan Ilmu Komputer. Universitas Brawijaya. Nurzaki., M.T., Wijanarto 2015. Routing Otomatis Berbasis Algoritma Genetik untuk Pengelolaan Tanggap Darurat Bencana, JurnalTechno.COM, 14(2), 1-9. Rillaningrum, Y., dan Marji. Rancang Bangun Aplikasi Andoid untuk Pencarian Lokasi ATM terdekat di Kota Malang, jurnal mahasiswa program studi Informatika/ilmu Komputer. Universitas Brawijaya Sukaton, R.M,. 2011. Penggunaan Algoritma Genetika Dalam Masalah jalur tependek pada jaringan data, Skripsi Mahasiswa Program Studi Sarjana Matematika. Universitas Indonesia, 4(1), 1-5. Tahyudin, I., Susanti, I,. 2015. Pencarian Rute Terbaik pada Obyek Wisata di Kabupaten Banyumas Menggunakan Algoritma Genetika Metode TSP (Travelling Salesman Problem), Jurnal Mahasiswa Program Studi Sistem Informasi. STIMIK AMIKOM, 3(4), 1-9 Utami, P.Y., Suhery, C., Ilhamsyah., 2014. Aplikasi Pencarian Rute Terpendek Menggunakan Algoritma Genetika, Jurnal Coding Sistem Komputer Universitas Tanjungpura, 2(1), 1-7. Yulia, W.E., Istiadi, D., Roqib, A., 2015. Pencarian SPBU terdekat dan penentuan jarak terpendek menggunakan Algoritma Djikstra, Jurnal Mahasiswa Program Studi Sistem Informasi. Universitas Jember 4(1), 1-5.
