## Implementasi Algoritma Genetikapada Pencarian Rute Terpendek Studi Kasus Pengantaran Dokumen Di Universitas Diponegoro Semarang
Bery Orindi *1) , Nurdin Bahtiar *2)
* Departemen Ilmu Komputer/Informatika, Fakultas Sains dan Matematika, Universitas Diponegoro
1) bery.orindi@gmail.com, 2) nurdinbahtiar@gmail.com

## Abstrak
Universitas Diponegoro merupakan salah satu perguruan tinggi negeri yang terdiri atas beberapa  fakultas  dimana  setiap  fakultas  memiliki  lokasi  yang  berbeda.  Selain  fakultas terdapat juga beberapa kantor yang berada di lingkungan Universitas Diponegoro. Pada umumnya,  kantor-kantor  tersebut  menjadi tujuan  pengiriman  dokumen  oleh  orang  yang mewakili  kantor  lainnya.  Dalam  pengiriman  dokumen  diperlukan  seorang  kurir  karena terdapat  kemungkinan  tujuan  dokumen  lebih  dari  satu.  Seringkali,  kurir  tidak  dapat menentukan rute yang dilewati agar menghasilkan jarak terpendek. Algoritma Genetika merupakan  metode  yang  dapat  digunakan  untuk  menyelesaikan  permasalahan  tersebut. Penelitian  pada  Tugas  Akhir  ini  menggunakan  Algoritma  Genetika  dengan    operator seleksi  roulette  wheel,  order  base  crossover  (OX2)  dan  order  based  mutation  (swap mutation).  Implementasi  penyelesian  masalah  dilakukan  dalam  sebuah  aplikasi menggunakan  bahasa  pemrograman  PHP  dan  database  MYSQL  serta  bantuan  Google Maps  untuk  menampilkan  hasil  rute  terpendek.  Hasil  Pengujian  menunjukkan  rata-rata nilai fitness mencapai nilai paling maksimum pada saat nilai probabilitas crossover 30% dan probabilitas mutasi 30%.. Selain itu, rata-rata nilai fitness mengalami kenaikan sesuai dengan semakin besarnya jumlah kromosom awal dan jumlah generasi.
Kata kunci : Algoritma Genetika, Order Based Crossover, OX2, Swap Mutation, Roulette Wheel, Rute Terpendek, Google Maps, Fitness.

## Abstract
Diponegoro University is a University that consist of several faculties where each faculty has  different  location.  In  addition  there  are  also  some  faculty  office  that  located  in Diponegoro University Environtment. Usually, these office became destination document that  send  by  people  who  representing  other  offices.  A  courier  is  needed  to  deliver  the documents  because  there  may  be  more  than  one  destionation  to  deliver  that.  Often,  the courier  can  not  decide  which  route  are  going  to  passed  to  prouduce  the  shortest  path. Genetic  Algorithm  is  a  method  that  can  used  to  solve  that  problem.  This  research  used Genetic  Algorithms  with  operator  roulette  wheel  for  selection,  order  based    crossover (OX2)  and  order  based  mutation  (swap  mutation).  The  solution  to  solved  that  problem implemented  in  a  application  used  PHP  programming  language,  MySQL  database  and Google Maps to display the route that must be passed. Test results showed that the average fitness  value  reaches  the  maximum  value  when  the  probability  of  crossover  30%  and probability mutation 30%. In addition, the average value of fitness increased in accordance with the number of initialitation chromosomes and the number of generations.
Keywords  : Genetic  Algorithm,  Order Based  Crossover,  OX2,  Swap  Mutation,  Roulette Wheel, Shorthest Path, Google Maps, Fitness.

## 1 P ENDAHULUAN
Universitas  Diponegoro  merupakan salah  satu  perguruan  tinggi  yang  memiliki banyak  program  studi  dan  terdiri  dari beberapa  fakultas.  Setiap  fakultas  tersebut memiliki  lokasi  yang  berbeda.  Selain fakultas  terdapat  juga  perkantoran  non fakultas  yang  masih  berhubungan  dengan akademik  tetapi  masih  satu  lingkungan Universitas  Diponegoro.  Masing-masing kantor sering melakukan pengiriman dokumen  yang  tujuan  pengirimannya  bisa lebih dari satu lokasi sehingga sering terjadi permasalahan  pengantar  dokumen  bingung menentukan  lokasi  mana  terlebih  dahulu yang  akan  dikunjungi  agar  jarak  yang ditempuh  merupakan  jarak  terpendek  untuk mengantarkan dokumen tersebut.
Permasalahan  tersebut  hampir  sama dengan Travelling Salesman Problem (TSP).
TSP  adalah  suatu  masalah  klasik  dalam pengiriman barang. Solusi yang ingin dicapai dalam  permasalah  TSP  adalah  menemukan rute jalan terpendek yang akan melalui setiap titik-titik tujuan yang ditentukan dan kembali lagi  ke  titik  awal.  TSP  dapat  diselesaikan dengan berbagai macam algoritma optimasi. Salah  satu  algoritma  yang  dapat  digunakan untuk  menyelesaikan  permasalahan  TSP adalah algoritma genetika.

## 2 T INJAUAN P USTAKA

## 2.1 A LGORITMA G ENETIKA
Algoritma  Genetika  merupakan  suatu metode heuristik yang dikembangkan berdasarkan  prinsip  genetika  dan  proses seleksi  alamiah  Teori  Evolusi  Darwin.
Metode  optimasi  dikembangakan  oleh  John
Holland sekitar tahun 1960-an dan dipopulerkan oleh salah seorang mahasiswanya, David Goldberg, pada tahun 1980-an[2].  Proses  pencarian  penyelesaian atau  proses  terpilihnya  sebuah  penyelesaian dalam algoritma ini berlangsung sama seperti terpilihnya  suatu  individu  untuk  bertahan hidup dalam proses evolusi.
Struktur  dasar  Algoritma  Genetika terdiri atas beberapa langkah yaitu [2]
1. Inisialisasi populasi.
2. Evaluasi populasi.
3. Seleksi  populasi  yang  akan  dikenai operator genetika.
4. Proses  penyilangan  pasangan  kromosom tertentu.
5. Proses mutasi kromosom tertentu.
6. Evaluasi popuasi baru.
7. Ulangi dari langkah 3 selama syarat belum terpenuhi.

## 2.2 S ELEKSI
Metode seleksi yang sering digunakan adalah seleksi dengan mesin roulette. Metode ini merupakan metode yang paling sederahana dan sering dikenal dengan nama stochastic  sampling  with  replacement. Cara kerja metode ini sebagai berikut [1]
1. Dihitung nilai fitness dari masing-masing individu ( f i , dimana i adalah individu ke-1 sampai dengan ke-n).
2. Dihitung total fitness semua individu.
3. Dihitung probabilitas masing-masing individu.
4. Dari  probabilitas  tersebut,  dihitung  jatah masing-masing  individu  pada  angka  1 sampai 100.
5. Dibangkitkan  bilangan  random  antara  1 sampai 100.
Dari bilangan random yang dihasilkan, ditentukan individu mana yang terpilih dalam proses seleksi.

## 2.3 P INDAH S ILANG (C ROSSOVER )
Prinsip  dari  pindah  silang  ini  adalah melakukan  operasi  (pertukaran,  aritmatika) pada  gen-gen  yang  bersesuaian  dari  dua induk  untuk  menghasilkan  individu  baru. Proses crossover dilakukan  pada  invidu dengan probabilitas yang telah ditentukan.
Salah satu crossover untuk representasi kromosom  permutasi  adalah Order  Based Crossover (OX2).  Langkah-langkah  dalam metode ini adalah [5]
1. Pilih posisi gen-gen yang akan dilakukan crossover secara acak.
2. Bentuk kromosom baru hasil penyilangan pertama untuk posisi selain gen-gen yang terpilih  tetap  sama  dengan  induk  yang pertama
3. Untuk  posisi  gen-gen  yang  terpilih urutannya disesuaikan dengan induk yang kedua.

## 2.4 M UTASI
Salah  satu  metode  mutasi  untuk representasi  kromosom  permutasi  adalah order  based  mutation  atau  swap  mutation. Dalam  metode  ini,  proses  mutasi  dilakukan dengan  memilih  acak  dua  posisi  gen  pada kromosom  yang  akan  dimutasi.  Setelah terpilih dilakukan pertukaran antara dua gen tersebut. [5]

## 2.5 E UCLIDEAN D ISTANCE
Euclidean  Distance merupakan  salah satu formula yang digunakan untuk
mengukur jarak 2 titik dengan menggunakan perhitungan matematis. Euclidean
menggunakan metode heuristic yang diperoleh berdasarkan jarak langsung seperti
mendapatkan  nilai  dari  panjang  diagonal pada segitiga. Rumus jarak Euclidean [4]: 𝐵𝐽𝑎𝑟𝑎𝑘 = √(𝐿𝑎𝑡 1 − 𝐿𝑎𝑡 2 ) 2 + (𝐿𝑜𝑛𝑔 1 − 𝐿𝑜𝑛𝑔 2 ) 2 (1)
dimana
𝐿𝑎𝑡 𝑖 = latitude lokasi i 𝐿𝑜𝑛𝑔 𝑖 = longitude lokasi i
Hasil  jarak  tersebut  masih  dalam satuan decimal degree hal ini karena format latitude dan longitude yang digunakan masih dalam satuan decimal degree . Oleh karena itu perlu  penyesuaian  sehingga  hasil  jarak dikalikan  111,319  km  atau  111319  m  (1 derajat bumi = 111.319 km). [4]

## 3 M ETODE P ENELITIAN

## 3.1 P EMODELAN D AN A NALISIS

## 3.1.1 G AMBARAN U MUM
Sistem Pencari Rute Terpendek berbasis web dibangun untuk diimplementasikan pada lingkungan Universitas Diponegoro. Sistem ini
membantu  menentukan  rute  terpendek  yang akan dilalui untuk mengantar dokumen atau barang.  User  memilih  titik  asal,  akhir  dan lokasi  yang  akan  dikunjungi.  Kemudian sistem  akan  menghitung  dan  menampilkan hasil  rute  terpendek.  Arsitektur  Sistem disajikan pada Gambar 1.

## Gambar 1 Arsitektur Sistem

## 3.1.2 S PESIFIKASI K EBUTUHAN

## P ERANGKAT L UNAK

## Tabel 1 Spesifikasi Kebutuhan Perangkat Lunak
No Kebutuhan SRS-SPRT-F01 Sistem dapat melakukan otentikasi dengan proses login ketika akan masuk ke halaman admin SRS-SPRT-F02 Sistem dapat mengelola data admin (menampilkan, menambahkan, mengubah, menghapus) SRS-SPRT-F03 Sistem dapat mengelola data lokasi (menampilkan, menambahkan, mengubah, menghapus) SRS-SPRT-F04 Sistem dapat mengelola data rute (menampilkan, menambahkan, mengubah, menghapus) SRS-SPRT-F05 Sistem dapat menampilkan lokasi marker pada peta sesuai dengan input pengguna SRS-SPRT-F06 Sistem dapat melakukan perhitungan untuk menghasilkan rute terpendek

## 3.2 P ERANCANGAN A LGORITMA

## 3.2.1 S ELEKSI
FOR i=0 sampai i < jumlahkromosomawal Menghitung probabilitas tiap kromosom ENDFOR
FOR i=0 sampai i < jumlahkromosomawal Menjumlahkan probabailitas tiap kromosom disimpan dalam variabel probakumulasi ENDFOR
FOR i=0 sampai i < jumlahkromosomawal Generate angka random 1-100

## ENDFOR
FOR i=0 sampai i < jumlahkromosomawal IF angka random lebih kecil probakumulasi ke i THEN hasil seleksi adalah nilai i
ENDIF ENDFOR

## 3.2.2 P INDAH S ILANG (C ROSSOVER )
//Menentukan 2 kromosom sebagai induk crossover IF jmlkromcrossover genap THEN
lakukan penentuan pasangan induk, satu pasang 2 induk berbeda ELSE lakukan penentuan pasangan induk, satu pasang 2 induk berbeda sisa 1 induk memilih pasangan secara random
ENDIF
//Menentukan lokasi gen yang akan dicrossover
jmlgen  jumlah gen pada induk kromosom jmlgencrossover  angka random minimal 2 sampai (jmlgen–3)
FOR i=0 sampai i < jmlgencrossover
Generate angka random untuk menentukan lokasi gen Menyimpan gen crossover pada variabel tempa dan tempb ENDFOR
//Melakukan crossover FOR i=0 sampai i < jmlgen Urutan gen pada variabel tempa ditukar sesuai urutan indukb, begitu juga sebaliknya
ENDFOR

## 3.2.3 M UTASI
//insialisasi jumlahkromosom  jumlah kromosom dalam himpunan penyelesaian panjangkromosom  jumlah gen pada kromosom dikurangi 2
jumlahtotalgen  jumlahkromosom * panjangkromosom jumlahmutasi  probabilitas * jumlahtotalgen //inisialisasi array mutasi FOR i=0 sampai i < jumlahmutasi
Generate angka random ENDFOR
//melakukan swap gen
FOR i = 0 sampai i < jumlahmutasi
Cek posisi gen yang akan dilakukan mutasi pada kromosom Melakukan pertukaran gen sesua dengan array mutasi dengan gen setelahnya ENDFOR

## 4 H ASIL DAN P EMBAHASAN

## 4.1 I MPLEMENTASI A NTARMUKA
Pada  bagian  ini  dituliskan  hasil  dari eksperimen  yang  telah  dilakukan  dan
berbagai  analisa  terkait  dengan  hasil eksperimen  yang  telah  diperoleh.    Pada bagian  ini  disarankan  untuk  menggunakan ilustrasi  secara  visual  sehingga  lebih mendukung informasi yang ingin disampaikan.
Halaman  ini  akan  menampilkan  data titik  asal  dan  titik  tujuan  dalam  bentuk dropdown . Selain itu terdapat checkbox yang berisi  titik  lokasi  yang  dikunjungi.  Google Maps  akan  menampilkan  titik-titik  pilihan user yang akan diproses untuk pencarian rute terpendek.    Setelah  user  menekan  tombol proses,  proses  perhitungan  untuk  pencarian rute  terpendek  menggunakan  algoritma genetika  dilakukan.  Setelah  proses  tersebut sistem akan memberikan  output berupa rute yang  terpendek  yang  harus  dilewati.  User dapat  memilih  rute  antar  2  titik  untuk ditampilkan  pada  Google  Maps.  Halaman utama dapat dilihat pada Gambar 2.

## Gambar 2 Halaman Utama Aplikasi

## 4.2 A NALISIS P ENGUJIAN

## 4.2.1 A NALISIS P ENGUJIAN P ROBABILITAS C ROSSOVER DAN P ROBABILITAS M UTASI
Pengujian terhadap probabilitas crossover  dan  mutasi  dilakukan  untuk mengetahui pengaruh probabilitas  crossover dan  mutasi  terhadap  nilai  fitness  yang dihasilkan.  Selain  itu  pengujian  juga  dapat dijadikan  dasar  dalam  menentukan  nilai
probabilitas paling optimum untuk menyelesaikan  permasalahan  yang  menjadi studi  kasus.  Pengujian  dilakukan  dengan melakukan  kombinasi  nilai  probabilitas crossover  maupun  mutasi.  Nilai  yang digunakan  adalah  10%,  20%,  30%,  40%, 50%,  60%,  70%,  80%  dan  90%.  Pengujian dilakukan  dengan  jumlah  generasi  atau iterasi sebanyak 25, jumlah kromosom awal 15 dan jumlah pengujian dilakukan sebanyak 10 kali untuk tiap kombinasi. Hasil Pengujian tersaji dalam bentuk grafik pada Gambar 3.
Gambar 3 Hasil Pengujian Probabilitas Crossover dan Mutasi

## 4.2.2 A NALISIS P ENGUJIAN J UMLAH K ROMOSOM A WAL DAN J UMLAH G ENERASI
Pengujian  terhadap  jumlah  kromosom awal  dan  jumlah  generasi  dilakukan  untuk mengetahui  pengaruh  jumlah  kromosom awal  dan  jumlah  generasi  terhadap  nilai fitness yang dihasilkan. Selain itu pengujian juga dapat dijadikan dasar dalam menentukan  jumlah  kromosom  awal  dan jumlah  generasi  paling  optimum  untuk menyelesaikan  permasalahan  yang  menjadi studi  kasus.  Pengujian  dilakukan  dengan kombinasi  nilai  kromosom  awal  dan  nilai generasi.  Nilai  kromosom  awal  yang digunakan  adalah  5,  10,  15,  20,  25  dan  30. Sedangkan  nilai  generasi  yang  digunakan yaitu 25, 50, 75, 100, 125 dan 150. Pengujian dilakukan dengan nilai probabilitas crossover
30%,  nilai  probabilitas  mutasi  30%  dan jumlah pengujian dilakukan sebanyak 20 kali untuk  tiap  kombinasi  nilai.  Hasil  Pengujian tersaji dalam bentuk grafik pada Gambar 4.

## Gambar 4 Hasil Pengujian Jumlah Kromosom Awal dan Generasi

## 5 K ESIMPULAN DAN SARAN

## 5.1 K ESIMPULAN
Kesimpulan  yang  dapat  diambil  dari pelaksanaan  penelitan  ini  adalah  sebagai berikut :
1. Implementasi  Algoritma  Genetika  pada Pencarian  Rute  Terpendek  Studi  Kasus Pengantaran  Dokumen  di  Universitas Diponegoro  berhasil  dibangun  dan  untuk menampilkan rute dapat dilakukan dengan memanfaatkan Google Maps .
2. Secara umum nilai rata-rata fitness cukup bervariasi  pada  setiap  kombinasi  nilai probabilitas crossover dan  probabilitas mutasi.  Namun,  rata-rata  nilai fitness mencapai  nilai  paling  maksimum  pada saat nilai probabilitas crossover 30% dan probabilitas mutasi 30%.
3. Rata-rata nilai fitness mengalami kenaikan sesuai dengan semakin besarnya jumlah  kromosom  awal  dan  jumlah generasi.

## 5.2 S ARAN
Saran-saran  yang  dapat  dilaksanakan untuk pengembangan Sistem Pencarian Rute
Terpendek dengan Algoritma Genetika lebih lanjut  antara  lain  dengan  melakukan penelitian lain menggunakan metode seleksi, mutasi dan pindah silang yang berbeda agar sistem  ini  dapat  menjadi  sistem  pencarian rute  terpendek  yang  lebih  efektif  dan menghasilkan penyelesain terbaik pada kasus ini.

## D AFTAR P USTAKA
[1] Annasir,  A.  W.  (2013). Implementasi
Algoritma  Genetika  untuk  Pencarian Rute  Berdasarkan  Waktu  Tercepat Objek  Wisata  di  Kabupaten  Ngawi. Makalah Program Studi Teknik Informatika  Fakultas  Komunikasi  dan Informatika Universitas Muhammadiyah Surakarta.
[2] Haupt,  R.,  &  Haupt.  (2004). Practical Genetic  Algorithms. New  Jersey:  John Wiley and Sons, Inc.
[3] Shiddiq,  Ahmad,  &  dkk.  (2012). Rancang Bangun Alat Kalibrasi Sensor Menggunakan Metode Euclidean. Seminar  Proyek  Akhir  Jurusan  Teknik Elektronika PENS-ITS.
[4] Widodo  Bagas  P.,  P.  H.  (2016).
Pencangan  Aplikasi  Pencarian  Layanan Kesehatan Berbasis HTML 5
Geolocation. Jurnal  Sistem  Komputer , Vol 6, No 1, Hal 51.
[5] Zukhri,  Z.  (2014). Algoritma  Genetika Metode  Komputasi  Evolusioner  untuk Menyelesaikan Masalah Optimasi. Yogyakarta: ANDI.