## Perbandingan Algoritma Genetika dengan Algoritma Greedy Untuk Pencarian Rute Terpendek
Rizky Berlia Oktaviandi * , M. Sadid Tafsirul Hadi ** , Alanfansyah Ghozy Santoso *** , Nova El Maidah ****
Program Studi Teknologi Informasi, Program Ilmu Komputer, Universitas Jember * berliarizkyy@gmail.com, ** msadidt@gmail.com, *** alfansyahghozysans@gmail.com, **** nova.pssi@unej.ac.id

## ABSTRACT
In  everyday  life  we  often  travel  from  place  to  place.  So  that  we  need  to  consider  the  time  and  cost efficient. Therefore, accuracy is needed to determine the shortest path as a consideration in decision to show  the  path  to  be  taken.  The  results  obtained  also  require  speed  and  accuracy  with  the  help  of  a computer.  Using  or  functioning  a  computer  there  must  be  a  distributed  program  in  it.  The  programs contained  in  the  computer  vary  widely  and  each  program  must  use  an  algorithm.  Algorithm  is  a collection of commands to solve a problem gradually from start to finish. There are various algorithms that can be used to find the shortest route such as Breadth First Search algorithm, Depth First Search, A *, Hill Climbing and others. For that required comparison algorithm which is able to find the shortest route accurately and efficiently. In this journal, the algorithm to be compared is the genetic algorithm and greedy algorithm to find the shortest route on a map. Some aspects to be compared are aspects of the accuracy, speed, and complexity of genetic algorithms and greedy algorithms for the shortest route search.
Keyword: Algoritma Genetika, Algoritma Greedy , Rute terpendek, Perbandingan Algoritma

## 1. Introduction
Transportasi  berperan  terpenting  bagi  masyarakat.  Saat  ini  perkembangan  transportasi  sangat  pesat  dan mengakibatkan bertambahnya volume kendaraan sehingga memicu terjadinya kemacetan. Luasnya jalan raya akan  menyulitkan  masyarakat  dalam  menemukan  rute  optimum,  maka  pencarian  rute  optimum  menjadi masalah terbesar bagi masyarakat saat ini . Banyak jalan yang harus dilewati ketika akan menuju dari tempat satu  ke  tempat  lain.  Guna  dari  pemilihan  jarak  optimal  ini  yakni  meminimalisir  waktu  serta  biaya  yang dikeluarkan  dalam  melakukan  perjalanan  tersebut.  Beberapa  masalah  diatas  dapat  diminimalisir  dengan menggunakan beberapa metode algoritma.
Dalam penelitian yang berjudul "Sistem Pencarian Hotel Berdasarkan Rute Perjalanan Terpendek Dengan Mermpertimbangkan Daya Tarik Wisata Menggunakan Algoritma Greedy” telah menghasilkan sistem yang dapat  memberikan  rekomendasi  rute  dan  urutan  perjalanan  terpendek  antara  hotel  dan  daya  tarik  wisata berdasarkna algoritma greedy.
Penelitian dengan judul “Pencarian Rute Terpendek Menggunakan Algoritma Greedy” telah menghasilkan pencarian  rute  terpendek  dari  node  A  (kecamatan  Ngaliyan)  ke  node  L  (kecamatan  Sampangan)  dengan menggunakan  algoritma  greedy.  Rute  dari  node  A  ke  node  L  yang  paling  optimal  dengan  jarak  terpendek adalah rute A - B - D - G - I - K - J - L dengan jarak 12 km. Penelitian  yang  berjudul “Algoritma  Greedy  Untuk  Menentukan  Lintasan  Terpendek” telah  menghasilkan pencarian  lintasan  terpendek  berdasarkan  jarak  dan  waktu-waktu  terjadinya  kemacetan.  Dimana  sangat membantu masyarakat dalam mencari rute tercepat saat terjadi kemacetan dengan waktu yang efisien. Dalam  penelitian  yang  berjudul “Implementasi  Algoritma  Genetika  Untuk  Pencarian  Rute  Berdasarkan Waktu  Tercepat  Objek  Wisata  Di  Kabupaten  Ngawi” telah  menghasilkan  aplikasi  pencarian  rute  tercepat dalam kemacetan dengan menggunakan algoritma genetika. Dimana sangat membantu masyarakat mencari rute menuju objek wisata di Kabupaten Ngawi.
Penelitian dengan judul “Penentuan Jarak Terpendek Pada Jalur Distribusi Barang Di Pulau Jawa dengan Menggunaka  Algoritma  Genetika” telah  menghasilkan  perangkat  lunak  dengan  mencari  rute  pengiriman barang dengan waktu dan biaya perjalanan yang optimal. Pada data awal nilai fitness pada tahap inisialisasi dari kromosom adalah 931setelah melalui proses algoritma genetika menghasilkan nilai fitness 762. Penelitian  yang  berjudul “Penerapan  Algoritma  Genetika  Dalam  Menemukan  Rute  Terpendek” telah menghasilkan ada 63 tes yang menggunakan 6 titik lokasi. Itu hasil uji menggunakan nilai populasi (10,15),
crossover (0,2, 0,3, 0,5, 0,6, 0,7, 0,8), mutasi (0,1,0,05, 0,4, 0,7) dan iterasi (200.300.400.500) menunjukkan bahwa terpendek rute adalah 239,45 km dan waktu 6,65. Algoritma tingkat akurasi 85,7% dan rute yang bisa dilewati adalah A - C - D - B - E - F - A.
Pada  makalah  ini,  penulis  akan  membandingkan  pemilhan  rute  tercepat  menggunakan  metode  algoritma genetika  dengan  algoritma  greedy.  Diantara  kedua  metode  tersebut  manakah  yang  paling  eifsien  dalam pemilihan rute tercepat dengan tidak membuang waktu dan biaya.

## 2. Research Method

## Gambar 1. Rute Masalah

## Perbandingan Algoritma
Dari  kasus  yang  telah  ditentukan,  akan  dicari  penyelesaian  rute  terpendek  dari  rute  masalah  yang  ada dengan  cara  membandingkan  dari  beberapa  aspek  yang  akan  dibandingkan  dari  algoritma  genetika  dan algoritma greedy.  Aspek yang kan dibandingkan adalah sebagai berikut:
1) Akurasi pencarian rute terpendek
Aspek yang akan dibandingkan pertama kali adalah dari segi akurasi atau ketepatan dalam mencari rute terpendek  yang  dihasilkan  dari  penyelesaian  algoritma  genetika  dan  algoritma  greedy.  Algoritma manakah yang dapat mencari rute terpendek dari permasalahan yang telah ditentukan.
2) Efisiensi pencarian rute terpendek
Perbandingan kedua adalah aspek efisiensi atau kecepatan  dari algoritma genetika dan algoritma greedy dalam  mencari  rute  terpendek.  Algoritma  manakah  yang  dapat  menentukan  rute  terpendek  dengan waktu yang singkat.
3) Kompleksitas pencarian rute terpendek Dalam pencarian rute terpendek, hal yang diperlukan untuk pencarian tidak hanya jarak antara tiap node saja,  akan  tetapi  juga  ada  hal  lain  yang  dapat  digunakan  untuk  menambah  efisiensi  pencarian  rute terpendek. Oleh karena itu akan dibandingkan algoritma manakah yang mempunyai kompleksitas dalam mencari rute terpendek.

## 3. Result and Analysis

## A. Algoritma Genetika
Algoritma genetika merupakan suatu metode pencarian yang didasarkan pada mekanisme dari seleksi dan genetika natural. Secara umum, blok diagram dari mekanisme kerja algoritma genetika ini adalah seperti yang terlihat pada Gambar 2.
Gambar 2. Flowchart Algoritma Genetika
1) Prosedur Algoritma Genetika
-  Prosedur  Angka  Acak  Angka/random  yang  digunakan  dalam  algoritma  genetika  ini  memakai fungsi yang telah disediakan oleh bahasa program pascal
-  Prosedur  Reproduksi  Prosedur  ini  akan  menduplikasi  ulang  kromosom  induk  secara  lengkap sehingga menghasilkan turunan baru yang sama dengan induknya
-  Prosedur Kawin Silang Prosedur ini akan memilih dua krornosom induk yang akan mengalami proses.kawin  silang  secara  acak,  kemudian  menetukan  satu  atau  dua  titik  potong  secara  acak pula.  Setelah  titik  potong  ini  terpilih  maka  dilakukan  proses  penukaran  informasi  dari  kedua kromosom itu berdasarkan titik potong yang telah ditentukan
-  Prosedur  Mutasi  Prosedur  mutasi  yang  akan  digunakan  adalah  mutasi  bit.  Setiap  bit  dari kromosom  tersebut  akan  mempunyai  peluang  sendiri  untuk  mengalami  mutasi.  Probabilitas terjadinya mutasi pada setiap bit ditentukan oleh nilai mutation rate
-  Prosedur  Seleksi  Seleksi  yang  digunakan  dalam  penelitian  ini  adalah  metode  roulette-wheel. Dalam metode roulette-wheel, peluang setiap lcomosom untuk terseleksi sebanding dengan nilai obyektifnya. Semakin besar nilai obyektif, maka semakin besar peluang untuk terseleksi
-  Prosedur  Populasi  Awal  Prosedur  ini  akan  membangkitkan  sejumlah  kromosom  secara  acak untuk membentuk populasi awal. Jumlah kromosom dalam satu polulasi dapat bervariasi sesuai dengan setting awal yang telah ditentukan.
-  Prosedur Penghitungan Generasi Prosedur ini dibuat untuk memeriksa apakah kriteria berhenti dari algoritma genetika sudah dipenuhi atau tidak. Hal ini dilakukan dengan menghitung jumlah generasi sampai batas maksimum yang diberikan. Bila dalam jumlah generasi yang ditentukan tidak ada kromosom yang lebih baik maka algoritma genetika akan berhenti melakukan proses iterasi.
2) Penyelesaian Masalah Rute
Pengujian  proses  algoritma  genetika  dilakukan  dengan  melakukan  perubahan  nilai  parameter  yang digunakan, yaitu nilai crossover rate, nilai mutation rate maupun nilai jumlah lromosom per populasi. Percobaan  dilakukan  dengan  mencari  rute  terpendek.  Bentuk  rute  pengujian  dapat  dilihat  pada Gambar 3. Pengujian yang dilakulan adalah mencari rute paling optimum dari titik spot menuju ke titik spot 32.

## Gambar 3 Rute Masalah Algoritma Genetika
Melalui perhitungan secara manual didapatkan nilai obyektif yang terbaik adalah 569.52 km dan rute yang terpendek adalah rute dari spot 1 - 2 - l8 - 21 -27- 28 - 32. Hasil pengujian sistem yang paling sederhana,  tanpa  menggunakan  syarat,  juga  menghasilkan  nilai  yang  sama  dengan  perhitungan manual. Tabel 1 menunjukkan beberapa hasil pengujian yang telah dilakukan dari pengujian di atas tadi dengan menggunakan metode seleksi roulette-wheel.

## 3) Hasil Algoritma Genetika
Tabel 1. Hasil Pengujian
No Nilai Cross over Nilai
Muta si Wakt u (dt) Obyekt if Terbaik Rute Akhir Gener asi 1 1 0.01 24 569.52 1-2-18-21-27-28-32 2745 2 1 0.05 13 569.52 1-2-18-21-27-28-32 1479 3 1 0.1 13 569.52 1-2-18-21-27-28-32 1408 4 1 0.3 10 569.52 1-2-18-21-27-28-32 1036 5 1 0.5 14 569.52 1-2-18-21-27-28-32 1447 6 1 0.7 10 569.52 1-2-18-21-27-28-32 1164 7 1 0.9 11 569.52 1-2-18-21-27-28-32 1220 8 0.9 0.01 11 651.62 1-2-18-19-20-21-27-28- 32 1188 9 0.9 0.05 10 569.52 1-2-18-21-27-28-32 1109 10 0.9 0.1 13 569.52 1-2-18-21-27-28-32 1447 11 0.9 0.3 14 569.52 1-2-18-21-27-28-32 1443 12 0.9 0.5 10 569.52 1-2-18-21-27-28-32 1138 13 0.9 0.7 11 577.08 1-2-18-21-27-28-32 1141 14 0.9 0.9 10 569.52 1-2-18-21-27-28-32 1139 15 0.8 0.01 11 569.52 1-2-18-21-27-28-32 1257 16 0.8 0.05 12 569.52 1-2-18-21-27-28-32 1348 17 0.8 0.1 10 569.52 1-2-18-21-27-28-32 1065 18 0.8 0.3 10 569.52 1-2-18-21-27-28-32 1118 19 0.8 0.5 13 569.52 1-2-18-21-27-28-32 1368 20 0.8 0.7 10 569.52 1-2-18-21-27-28-32 1043 21 0.8 0.9 10 569.52 1-2-18-21-27-28-32 1030 22 0.6 0.01 23 569.52 1-2-18-21-27-28-32 2788 23 0.6 0.05 16 569.52 1-2-18-21-27-28-32 1742 24 0.6 0.1 13 569.52 1-2-18-21-27-28-32 1384 25 0.6 0.3 11 569.52 1-2-18-21-27-28-32 1207 26 0.6 0.5 10 569.52 1-2-18-21-27-28-32 1095 27 0.6 0.7 11 569.52 1-2-18-21-27-28-32 1175 28 0.6 0.9 13 569.52 1-2-18-21-27-28-32 1399 29 0.4 0.01 9 696.39 1-6-2-18-19-20-19-20- 28-32 1036 30 0.4 0.05 24 569.52 1-2-18-21-27-28-32 2700 31 0.4 0.1 10 569.52 1-2-18-21-27-28-32 1092 32 0.4 0.3 9 577.08 1-2-18-21-20-28-32 1016 33 0.4 0.5 10 569.52 1-2-18-21-27-28-32 1093

## B. Algoritma Greedy
Algoritma  greedy  adalah  algoritma  yang  memecahkan  masalah  langkah  demi  langkah,  pada  setiap langkah:
1. Mengambil pilihan yang terbaik yang dapat diperoleh saat itu
2. Berharap bahwa dengan memilih optimum lokal pada setiap langkah akan mencapai optimum global. Algoritma greedy mengasumsikan bahwa optimum lokal merupakan bagian dari optimum global.

## 1) Lintasan Terpendek (Shortest Path)
Lintasan  terpendek  adalah  lintasan  minimum  yang  diperlukan  untuk  mencapai  suatu  tempat  dari tempat tertentu. Lintasan minimum yang dimaksud dapat dicari dengan menggunakan graf. Graf yang digunakan adalah graf yang berbobot, yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot. Dalam kasus ini, bobot yang dimaksud berupa jarak .
Algoritma greedy untuk mencari lintasan terpendek dapat dirumuskan sebagai berikut: 1. Perikasa semua sisi yang langsung bersisian dengan simpul a. Pilih sisi yang bobotnya terkecil. Sisi ini menjadi lintasan terpendek pertama, sebut saja L(1).
2. Tentukan lintasan terpendek kedua dengan cara berikut: (i) hitung: d(i) = panjang L(1) + bobot sisi dari simpul akhir L(1) ke simpul i yang lain (ii) pilih d(i) yang terkecil Bandingkan d(i) dengan bobot sisi (a, i). Jika bobot sisi (a, i) lebih kecil daripada d(i), maka  L(2) = L(1) U (sisi dari simpul akhir L(i) ke simpul i) 3. Dengan cara yang sama, ulangi langkah 2 untuk menentukan lintasan terpendek berikutnya.

## 2) Penyelesaian Masalah Rute
Rumusan  masalah  saat  ini  adalah  bagaimana  menentukan  rute  optimum  dari  Node  1  ke  Node  32 dengan  menggunakan  Algoritma  Greedy  sehingga  mempunyai  jarak  terpendek.  Graf  dari  node  1 sampai dengan node 32 dan bobot tiap-tiap sisi (bobot menyatakan jarak dari setiap node satu ke node lain) seperti ditunjukkan pada gambar 4 berikut ini :

## Gambar 4 Rute Masalah Algoritma Greedy
Berdasarkan proses algoritma Greedy , didapatkan rute yang paling optimal dari node 1 ke node 32 adalah rute 1- 3 - 4 - 5 - 7 - 11 - 13 - 16 - 23 - 25 - 25 - 26 - 29 - 28 - 32 dengan jarak 834km.
4. Conclusion
34 0.4 0.7 12 569.52 1-2-18-21-27-28-32 1279 35 0.4 0.9 16 569.52 1-2-18-21-27-28-32 1628 36 0.1 0.01 11 634.97 1-2-18-21-27-28-32 1209 37 0.1 0.05 12 569.52 1-2-18-21-27-28-32 1309 38 0.1 0.1 10 569.52 1-2-18-21-27-28-32 1089 39 0.1 0.3 11 569.52 1-2-18-21-27-28-32 1237 40 0.1 0.5 10 569.52 1-2-18-21-27-28-32 1116 41 0.1 0.7 12 569.52 1-2-18-21-27-28-32 1349 42 0.1 0.9 15 569.52 1-2-18-21-27-28-32
1676
Berdasarkan perbandingan yang telah dilakukan, maka dapat diambil kesimpulan sebagai berikut:
1. Rute  yang  paling  terpendek  didapatkan    dengan  menggunakan  algoritma  genetika  yaitu  569,52km, sedangkan algoritma greedy menunjukkan rute optimum sejauh 834km.
2. Algoritma genetika memiliki tingkat akurasi yang tinggi dalam mencari rute terpendek dengan jumlah node yang memiliki banyak percabangan serta bobot yang bervariasi.
3. Algoritma  greedy  kurang  efisien  saat  digunakan  untuk  mencari  rute  terpendek  dengan  banyak node yang bercabang karena algoritma greedy tergantung pada bobot setiap simpulnya, sehingga rute yang dihasilkan kurang optimal.
4. Proses  pencarian  rute  menggunakan  algoritma  genetika  membutuhkan  waktu  yang  cukup  lama dibandingkan dengan algoritma greedy karena harus melalui banyak tahapan proses untuk mendapatkan rute terpendek.

## Acknowledgements
Artikel ini tersusun sebagai syarat tugas project mata kuliah. Terimakasih untuk semua teman yang membantu.

## References
[1] Annasir,  Agus  wahyu.  2013. Implementasi  Algoritma  Genetika  Untuk  Pencarian  Rute  Berdasarkan Waktu Tercepat Objek Wisata Di Kabupaten Ngawi . Universitas Muhammadiyah Surakarta.
[2] Joni I Dewa Made Adi Bagaskara, dan Nurcahyawati, Vivine. 2012. Penentuan Jarak Terpendek Pada Jalur  Distribusi  Barang  Di  Pulau  Jawa  Dengan  Menggunakan  Algoritma  Genetika. Jurnal  Nasional Pendidikan Teknik Inormatika, Vol 1, No. 3, Desember 2012. STMIK STIKOM Indonesia dan STMIK STIKOM Surabaya.
[3] Fallo  Diana,  Santoso  Alb.Joko,  dan  Budiyanto  Djoko.  2015. Penerapan  Algoritma  Genetika  Dalam Menemukan Rute Terpendek. Magister Informatika, Fakultas Teknologi Industri, dan Universitas Atma Jaya Yogyakarta.
[4] Herli  Audrey  Maximillian,  Raharja  Indra  Kharisma,  dan  Purbandini. Sistem  Pncarian  Hotel Berdasarkan  Rute  Perjalanan  Terpendek  Dengan  Mempertimbangkan  Daya  Tarik  Wisata Menggunakan Algoritma Greedy. Journal o Information System Engineering and Business Intelligence, Vol. 1, No. 1, April 2015. Program Studi SIstem Informasi, Fakultas Sains dan Teknologi, Universitas Airlangga.
[5] Hayati  Enty  Nur, da  Yohanes  Antoni.  2014. Pencarian  Rute  Terpendek  Menggunakan  Algoritma Greedy. Program Studi Teknik Industri dan Universitas Stikubank Semarang.
[6] Deindal Irvan Prama, Ariesanda Boyke, dan Christoforus. 2012. Algoritma Greedy Untuk Menentukan Lintasan Terpendek. Departemen Teknik