Jurnal Matematika Murni dan Terapan “εpsilon” http://ppjp.ulm.ac.id/journals/index.php/epsilon p-ISSN: 1978-4422 | e-ISSN 2656-7660 Vol.13 No.1 (Juni 2019) Hal. 46-55

## APLIKASI EVOLUTIONARY DISCRETE FIREFLY ALGORITHM DALAM PENYELESAIAN TRAVELLING SALESMAN PROBLEM
1 Nila Cahya, 2 Oni Soesanto, 3 Pardi Affandi
1, 2, 3 Program Studi Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Lambung Mangkurat Jln. A. Yani Km. 36 Banjarbaru, Kalimantan Selatan email: nilacahya97@gmail.com

## ABSTRAK
Proses  distribusi  barang  pada  suatu  industri  memerlukan  bentuk  efisiensi  dalam  pemilihan  jalur terpendek  yang  akan  dilalui  seorang salesman .  Secara  matematis,  pemilihan  jalur  terpendek merupakan  suatu  permasalahan  optimasi  yang  disebut Travelling  Salesman  Problem (TSP).
Terdapat banyak metode yang dapat diterapkan untuk menemukan solusi dari TSP, salah satunya Evolutionary  Discrete  Firefly  Algorithm (EDFA)  yang  merupakan  metode  metaheuristik  terbaru yang ditemukan oleh Jati dan Suyanto (2011) sebagai perkembangan dari Firefly Algorithm (FA) yang  hanya  didesain  untuk  permasalahan  kontinu.  Penelitian  ini  bertujuan  untuk  menjelaskan penerapan EDFA dalam penyelesaian TSP. Data yang digunakan dalam penelitian ini merupakan data  kasus  TSP  berupa  koordinat  titik  kota  yang  diambil  dari  database  TSP Libary (TSPLIB) dengan  7  jenis  kasus  berbeda  yaitu  Ulysses16,  Ulysses22,  Eil51,  Berlin52,  St70,  Rat99,  dan Gr202.  Kasus-kasus  tersebut  diselesaikan  dengan  menerapkan  EDFA  untuk  menemukan  solusi optimalnya melalui beberapa langkah yang terdapat dalam algoritma ini. Penyelesaian kasus TSP melalui  EDFA  juga  dilakukan  menggunakan  bantuan  program  simulasi  untuk  mempermudah pehitungan. Hasil penelitian menunjukkan bahwa EDFA sebagai perkembangan FA telah berhasil diterapkan  untuk  kasus  TSP  yang memiliki  solusi  dalam ruang  diskrit.  Simulasi  program EDFA yang  diterapkan  pada  kasus-kasus  tersebut  memberikan  solusi  lebih  baik  pada  beberapa  kasus dengan hasil  jarak  optimal  yang  lebih  pendek  dibandingkan  jarak  optimal  yang  telah  ditemukan sebelumnya.
Kata Kunci: TSP, EDFA , firefly, solusi optimal.

## 1. PENDAHULUAN
Suatu  industri  memerlukan  beberapa  bentuk  efesiensi  dalam  pelaksanaan kegiatannya  seperti  dalam  proses  pendistribusian  barang.  Salah  satu  faktor  yang mempengaruhi biaya distribusi adalah pemilihan jalur terpendek yang akan dilalui oleh salesman .  Jalur  yang  dilalui  untuk  proses  pendistribusian  barang  di  dalam ilmu  matematika  dapat  direpresentasikan  sebagai  sebuah  graf.  Kota  yang  dilalui seorang salesman dipandang  sebagai  sebuah vertex (titik)  dan  jarak  antar  kota tersebut  dipandang  sebagai edge (sisi).  Jika salesman tersebut  akan  melalui  tiap kota tepat satu kali dan kembali ke kota asal, maka jalur tersebut disebut sebagai sirkuit  Hamilton  [5].  Pemilihan  jalur  terpendek  merupakan  proses  minimasi
sirkuit  Hamilton  dari  suatu  graf  yang  dikenal  sebagai Travelling  Salesman Problem (TSP) . Tujuan dari TSP adalah untuk menemukan jalur perjalanan yang didapat dari permutasi urutan kota dengan total jarak minimum [1].
TSP  memiliki  banyak  metode  penyelesaian  di  antaranya  yaitu  metode  eksak dan  metode  aproksimasi.  Metode  eksak  mendapatkan  solusi  optimal  dan  dapat menjamin  keoptimalannya  namun  hanya  dapat  diterapkan  pada  beberapa  contoh kasus kecil dari permasalahan sulit seperti TSP dengan lima sampai sepuluh rute saja,  sedangkan  metode  aproksimasi  diantaranya  metaheuristik  memungkinkan untuk mengatasi masalah yang lebih kompleks, misalnya solusi untuk TSP dengan ribuan titik kota [7]. Terdapat banyak peneliti telah menyelesaikan permasalahan optimasi  berkaitan  dengan  TSP  yang  diselesaikan  dengan  beberapa  algoritma. Beberapa di antaranya seperti, Genetic Algorithm (GA) oleh Sumarta (2015), Ant Colony  Optimization (ACO) oleh  Bharad  dan  Sureja  (2012)  serta Firefly Algorithm (FA)  oleh  Kumbhara  dan  Pandey  (2013).  Dalam  penelitian  oleh Kumbhara  dan  Pandey  (2013)  didapatkan  kesimpulan  bahwa  FA memberikan hasil yang lebih bagus dibandingkan ACO, Simmulated Annealing (SA), dan GA.
Firefly  Algorithm (FA)  merupakan  salah  satu  metode  metaheuristik  untuk pemecahan  persoalan  optimasi  yang  ditemukan  oleh  Yang  Xin-She  pada  tahun 2008  dengan  inspirasi  dari  pergerakan  kunang-kunang  [8].  FA pada  dasarnya didesain  untuk  menyelesaikan  permasalahan  optimasi  kontinu,  akan  tetapi  juga dapat  didiskritkan  untuk  permasalahan  diskrit  seperti  TSP.  Jati  dan  Suyanto (2011)  mengadopsi  FA untuk  penyelesaian  TSP  dalam  representasi  permutasi yang memiliki solusi optimal dalam ruang pencarian diskrit. Oleh karena itu, FA dikembangkan  menjadi Evolutionary Discrete Firefly Algorithm (EDFA) dengan mengubah beberapa skema di dalamnya. Skema jarak euclid antar firefly dievolusi menjadi  jarak  diskrit  dan  skema  pergerakan  dilakukan  dengan  sistem  mutasi inversi.  Penerapan  EDFA  dalam  penyelesaian  TSP  memberikan  hasil  yang  lebih baik untuk beberapa kasus TSP standar dibandingkan solusi optimal sebelumnya.
Permasalahan  yang  diselesaikan  tersebut  menunjukkan  bahwa  FA  maupun EDFA  dianggap  lebih  mengungguli  beberapa  algoritma  lain  berdasarkan  tingkat akurasinya.  Oleh  karena  itu,  dalam  penelitian  ini  penulis  mengkaji  dan memperkenalkan  penerapan  EDFA  untuk  permasalahan  diskrit  TSP  yang menggunakan  skema  jarak  diskrit  dan  skema  pergerakan  yang  berbeda dibandingkan FA.
2. TINJAUAN PUSTAKA

## 2. 1 Travelling Salesman Problem
Travelling  Salesman  Problem (TSP)  merupakan  salah  satu  permasalahan optimasi kombinatorial. TSP memiliki tujuan untuk mendapatkan jalur perjalanan dari  seorang salesman mulai  dari  lokasi  awal,  mengunjungi  kumpulan  kota
tertentu  dan  kembali  ke  lokasi  awal  sehingga  total  jarak  yang  dilalui  adalah minimum dan setiap kota dikunjungi tepat satu kali, kecuali kota pertama [5].
Definisi 2.1.1 [1] Misalkan 𝐺 = (𝑉, 𝐸) sebuah  graf  dan 𝐹 merupakan  himpunan  semua  sirkuit Hamilton  dalam  G.  Untuk  setiap  sisi 𝑒 ∈ 𝐸 ,  biaya  (bobot) 𝑐 𝑒 ditentukan. Travelling  Salesman  Problem  adalah  untuk  menemukan  jalur  (sikuit  Hamilton) dalam 𝐺 sedemikian  sehingga  total  bobot  dari  sisi-sisi  dalam  jalur  tersebut adalah seminimum mungkin.
Definisi 2.1.2 [1] Misalkan 𝑃 𝑛 adalah  koleksi  semua  permutasi  dari  himpunan {1,2,3, … , 𝑛} .  TSP adalah  menemukan  sebuah 𝜋 = (𝜋(1), 𝜋(2), … , 𝜋(𝑛)) dalam 𝑃 𝑛 sedemikian sehingga 𝑐 𝜋(𝑛)𝜋(1) + ∑ 𝑐 𝜋(𝑖)𝜋(𝑖+1) 𝑛−1 𝑖=1 diminimasi. Dalam kasus ini (𝜋(1), 𝜋(2), … , 𝜋(𝑛)) memberikan urutan kota mana yang dikunjungi, mulai dari kota 𝜋(1) .

## 2. 2 Firefly Algorithm
Firefly  Algorithm atau  Algoritma  Kunang-Kunang  adalah  salah  satu metaheuristik terbaru  yang pertama kali  dikembangkan oleh Xin-She Yang pada tahun  2008  di  Cambridge  University. Firefly  Algorithm adalah  algoritma  yang terinspirasi  dari  cara  berkedip  kunang-kunang,  dan  memiliki  tiga  aturan  ideal yang telah dijelaskan oleh Xin-She Yang [8] sebagai berikut.
1. Semua  kunang-kunang  adalah  unisex  sehingga  suatu  kunang-kunang  akan tertarik  pada  kunang-kunang  yang  lain  tanpa  memperhatikan  jenis kelaminnya.
2. Ketertarikan  antar  kunang-kunang  sebanding  dengan  tingkat  kecerahan kunang-kunang  tersebut.  Dimana  ketertarikan  ini  akan  berkurang  jika  jarak antar  kunang-kunang  bertambah.  Antar  dua  kunang-kunang  yang  saling berkedip, kunang-kunang  yang kurang terang (redup) akan  bergerak  menuju kunang-kunang  yang  lebih  terang.  Jika  tidak  ada  yang  lebih  terang dibandingkan  dengan  yang  lain,  maka  kunang-kunang  akan  bergerak  secara acak.
3. Kecerahan  pada  kunang-kunang  ditentukan  oleh  fungsi  tujuan  dari  masalah yang diberikan.
Berdasarkan tiga aturan  ideal tersebut, langkah-langkah dasar dari Firefly Algorithm dapat dirangkum dalam pseudo code berikut. Fungsi  objektif 𝑓(𝑥) , 𝑥 = (𝑥 𝑖 , … , 𝑥 𝑑 ) 𝑇 . Bangkitkan populasi awal dari 𝑛 firefly 𝑥 𝑖 (𝑖 = 1, 2, … , 𝑛).
Intensitas cahaya 𝐼 𝑖 pada 𝑥 𝑖 ditentukan dengan 1/𝑓(𝑥 𝑖 ) . Definisikan penyerapan cahaya 𝛾 . While ( 𝑡 < 𝑀𝑎𝑥𝐼𝑡𝑒𝑟𝑎𝑡𝑖𝑜𝑛 ), for 𝑖 = 1: 𝑛 (semua 𝑛 firefly ) for 𝑗 = 1: 𝑛 if ( 𝐼 𝑖 < 𝐼 𝑗 )
Gerakkan firefly i menuju firefly j. end if
Ubah ketertarikan dengan jarak 𝑟 melalui 𝑒 −𝛾𝑟 2
Evaluasi populasi baru dan perbarui intensitas cahaya end for j end for i
Urutkan firefly dan temukan global best sementara. end while Tampilkan hasil dan visualisasi.
Adapun parameter-parameter kunci dalam Firefly Algorithm yaitu:
1. Intensitas Cahaya dan Ketertarikan Dalam bentuk sederhana, intensitas cahaya 𝐼(𝑟) berubah-ubah menurut hukum kuadrat terbalik 𝐼(𝑟) = 𝐼 𝑠 /𝑟 2 dimana 𝐼 𝑠 adalah intensitas pada sumber. Pada  medium  yang  diberikan  dengan  koefisien  penyerapan  cahaya 𝛾 , intensitas  cahaya  berubah  bergantung  dengan  jarak 𝑟 .  Yaitu 𝐼 = 𝐼 0 𝑒 −𝛾𝑟 , dimana 𝐼 0 adalah  intensitas  cahaya  mula-mula.  Untuk  menghindari kejanggalan 𝑟 = 0 pada  pernyataan 𝐼 𝑠 /𝑟 2 ,  akibat  gabungan  dari  hukum kuadrat terbalik dan penyerapan dapat didekati menggunakan bentuk Gaussian pada persamaan (1).
𝐼(𝑟) = 𝐼 0 𝑒 −𝛾𝑟 2 … (1)
Karena  ketertarikan firefly sebanding  dengan  intensitas  cahaya  dilihat  dari firefly yang  berdekatan,  dapat  didefinisikan  ketertarikan  suatu firefly seperti pada persamaan (2).
𝛽(𝑟) = 𝛽 0 𝑒 −𝛾𝑟 2 … (2)
dengan 𝛽 0 adalah ketertarikan pada 𝑟 = 0 .
2. Jarak dan Pergerakan
Jarak  antara  dua  kunang-kunang 𝑖 dan 𝑗 pada  posisi 𝑥 𝑖 dan 𝑥 𝑗 merupakan jarak Euclid seperti pada persamaan (3).
𝑟 𝑖,𝑗 = √∑ (𝑥 𝑖 𝑘 − 𝑥 𝑗 𝑘 ) 𝑑 𝑘=1 2 … (3)
dengan 𝑥 𝑖 𝑘 adalah komponen ke- 𝑘 dari 𝑥 𝑖 pada firefly i dan 𝑑 total dimensi dari masalah.  Pergerakan  dari  seekor firefly 𝑖 yang  tertarik  pada firefly lain  yang lebih  menarik  (lebih  cerah)  yaitu firefly 𝑗 serta firefly  i yang  bergerak  secara acak ditentukan dengan persamaan (4).
𝑥 𝑖 ′ = { 𝑥 𝑖 + 𝛽 0 𝑒 −𝛾𝑟 𝑖,𝑗 2 (𝑥 𝑗 − 𝑥 𝑖 ) + 𝛼 (𝑟𝑎𝑛𝑑 − 1 2 ) , 𝑢𝑛𝑡𝑢𝑘  𝑖 𝑚𝑒𝑛𝑢𝑗𝑢 𝑗
𝑥 𝑖 + 𝛼 (𝑟𝑎𝑛𝑑 − 1 2 ) … (5), 𝑢𝑛𝑡𝑢𝑘 𝑖 𝑏𝑒𝑟𝑔𝑒𝑟𝑎𝑘 𝑎𝑐𝑎𝑘 … (4)
dengan 𝑥 𝑖 ′ adalah posisi baru firefly i dan 𝑥 𝑖 adalah posisi sekarang dari firefly i .  Syarat  kedua  pada  pergerakan  menuju firefly lebih  cerah  disebabkan  oleh keterkarikan  sedangkan 𝛼 merupakan  parameter  pengacakan  dan 𝑟𝑎𝑛𝑑 merupakan  sebuah  pembangkit  bilangan  acak  yang  didistribusikan  secara uniform  pada [0,1] .  Pada  kebanyakan  kasus  dalam  penerapannya,  nilai  yang diambil adalah 𝛽 0 = 1 dan 𝛼𝜖[0,1] .
3. METODE PENELITIAN

## 3. 1 Data Penelitian
Data  yang  digunakan  dalam  penelitian  ini  adalah  data  sekunder  berupa koordinat  titik  kota  dalam  permasalahan  TSP  yang  diunduh  dari  TSPLIB  yang merupakan database dari sampel kasus-kasus TSP berbagai sumber. Permasalahan TSP memberikan sejumlah kota dengan masing-masing koordinat. Bilangan yang tercantum  dalam  nama  permasalahan  TSP  menyatakan  jumlah  kota  yang diberikan. Permasalahan TSP yang akan dijadikan data dalam penelitian ini yaitu Ulysses16,  Ulysses22,  Eil51,  Berlin52,  St70,  Rat99  dan  Gr202.  Selanjutnya dilakukan pengidentifikasian data dan merepresentasikan data ke dalam graf.
3. 2 Prosedur Penelitian
Langkah-langkah yang dilakukan dalam penelitian ini untuk menyelesaikan TSP dengan menerapkan EDFA adalah:
1. Menginisialisasi parameter EDFA
2. Membangkitkan populasi awal sebanyak p firefly
3. Menentukan firefly terbaik,
4. Menentukan ketertarikan dari setiap firefly i kepada firefly j, kemudian melakukan pergerakan
5. Memilih p firefly terbaik untuk dijadikan populasi pada iterasi selanjutnya.
6. Mengulangi langkah 3) sampai 5) hingga batas iterasi terpenuhi.

## 4. HASIL DAN PEMBAHASAN
4. 1 Evolutionary  Discrete  Firefly  Algorithm (EDFA)  untuk  Penyelesaian Travelling Salesman Problem (TSP)
EDFA  merupakan  perkembangan  dari  FA  dasar  untuk  menyelesaikan permasalahan  optimasi  yang  memiliki  solusi  dalam  ruang  diskrit  seperti  TSP. Terdapat dua perubahan skema dari FA dasar yang diadaptasi EDFA yaitu untuk menggambarkan jarak diskrit antara dua firefly serta skema movement pada firefly dalam  representasi  permutasi.  Adapun  parameter  yang  mempengaruhi  EDFA dalam  penyelesaian  TSP  adalah  intensitas  cahaya,  ketertarikan,  serta  koefisien penyerapan cahaya.
4. 1. 1. Intensitas Cahaya dan Ketertarikan
Dalam FA dasar, diasumsikan  bahwa ketertarikan suatu firefly ditentukan oleh  kecerahan  (intensitas  cahaya)  yang  bergantung  pada  fungsi  objektifnya. Untuk permasalahan  minimasi  seperti TSP, kecerahan 𝐼 dari firefly x berbanding terbalik  dengan  fungsi  tujuannya,  dengan  kata  lain 𝐼(𝑥) sebanding  dengan 1/ 𝑓(𝑥) .  Fungsi  tujuan  dari  kasus  TSP  untuk firefly 𝑥 = (𝑥(1), 𝑥(2), … , 𝑥(𝑛)) adalah
Min 𝑓(𝑥) = 𝑐 𝑥(𝑛),𝑥(1) + ∑ 𝑐 𝑥(𝑘),𝑥(𝑘+1) 𝑛−1 𝑘=1 … (9)
dengan 𝑛 adalah  total  kota  yang  dikunjungi, 𝑐 𝑖,𝑗 adalah  jarak  antar  kota 𝑖 dan  j, serta 𝑥(𝑘) adalah kota urutan ke 𝑘 untuk 𝑘 = 1,2, … , 𝑛 − 1 . Ketertarikan 𝛽 bersifat  relatif  karena  bergantung  pada  penilaian  dan pandangan  dari firefly lainnya  sehingga  nilainya  akan  bervariasi  karena dipengaruhi  jarak 𝑟 𝑖,𝑗 antara firefly  i dan firefly  j .  Selain  itu,    intensitas  cahaya akan  berkurang seiring dengan  bertambahnya  jarak dari sumber serta mengalami penyerapan  dalam  media  yang  dilaluinya  sehingga  ketertarikan 𝛽 juga
dipengaruhi  oleh  tingkat  penyerapan  cahaya  tersebut.  Dalam  bentuk  yang sederahana,  intensitas  cahaya 𝐼(𝑟 𝑖,𝑗 ) berubah-ubah  menurut  hukum  kuadrat terbalik
𝐼(𝑟 𝑖,𝑗 ) = 𝐼 𝑠 𝑟 𝑖,𝑗 2 … (10)
dengan 𝐼 𝑠 adalah  intensitas  pada  sumber.  Untuk  menghindari  kejanggalan  pada saat 𝑟 𝑖,𝑗 = 0 pada  pernyataan 𝐼 𝑠 𝑟 𝑖,𝑗 2 ,  maka  hukum  kuadrat terbalik  dikombinasikan dengan penyerapan sehingga dapat dilakukan pendekatan dengan
𝑑𝐼 𝑑𝑟 𝑖,𝑗 2 = −𝛾𝐼 ∫ 𝑑𝐼 𝐼 = ∫(−𝛾𝑑𝑟 𝑖,𝑗 2 )
ln 𝐼 = −𝛾𝑟 𝑖,𝑗 2 + 𝑘 𝐼 = 𝑒 −𝛾𝑟 𝑖,𝑗 2 +𝑘 𝐼 = 𝐾𝑒 −𝛾𝑟 𝑖,𝑗 2 .
Untuk 𝑟 𝑖,𝑗 = 0 , diperoleh
𝐼(0) = 𝐼 0 = 𝐾 sehingga
𝐼(𝑟 𝑖,𝑗 ) = 𝐼 0 𝑒 −𝛾𝑟 𝑖,𝑗 2 . … (12)
Karena ketertarikan suatu firefly sebanding dengan intensitas cahaya yang dilihat oleh firefly yang berdekatan, maka ketertarikan 𝛽 suatu firefly dapat didefinisikan sebagai
𝛽(𝑟 𝑖,𝑗 ) = 𝛽 0 𝑒 −𝛾𝑟 𝑖,𝑗 2 … (13)
dengan 𝛽 0 adalah ketertarikan pada 𝑟 𝑖,𝑗 = 0 .
Dalam  EDFA,  skema  perhitungan  ketertarikan 𝛽 tersebut  diadopsi sepenuhnya dalam penyelesaian TSP. 𝛽(𝑟 𝑖,𝑗 ) adalah ketertarikan dari suatu firefly saat  dilihat  pada  jarak 𝑟 𝑖,𝑗 , 𝛽 0 adalah  kecerahan  dari firefly yang  lebih  cerah. Untuk  setiap firefly  i dan firefly  j lain  yang  lebih  cerah,  pertama  dilakukan perhitungan  jarak 𝑟 𝑖,𝑗 antar firefly tersebut  menggunakan  persamaan  (6).  Jika ketertarikan dari firefly j tersebut lebih besar dari kecerahan firefly i , maka firefly i akan  bergerak  menuju firefly  j ,  sebaliknya  maka firefly  i akan  bergerak  secara random.
4. 1. 2. Penyerapan Cahaya
Koefisien  penyerapan  cahaya  ( light  absorption) 𝛾 menggambarkan variasi  dari  nilai  ketertarikan  suatu firefly. nilai  tersebut  sangat  penting  untuk menentukan  kecepatan  konvergensi  dan  bagaimana  tingkah  laku firefly .  Dalam teori, 𝛾𝜖[0, ∞), namun  dalam  kenyataannya  nilai 𝛾 ditentukan  dengan karakteristik dari permasalahan dari kasus yang dioptimalkan.
Dalam  kondisi  saat 𝛾 → 0 ,  ketertarikan  akan  menjadi  konstan  dan 𝛽(𝑟 𝑖,𝑗 ) = 𝛽 0 . Sehingga pada kasus ini, ketertarikan tersebut tidak akan berkurang saat  dipandang  oleh firefly yang  lain.  Jika 𝛾 → ∞ ,  maka  nilai  dari  ketertarikan akan menuju nol saat dipandang firefly lain. Hal ini ekuivalen dengan kondisi saat firefly terbang secara acak di wilayah yang sangat berkabut. Tidak ada firefly yang dapat  dilihat,  dan  setiap firefly menjelajah  dengan  cara  yang  benar-benar  acak. Dengan demikian, hal ini sesuai dengan metode pencarian yang benar-benar acak.
Koefisien  penyerapan 𝛾 menentukan  sebarapa  besar  intensitas  cahaya merubah ketertarikan dari suatu firefly pada jarak tertentu. Dalam EDFA, 𝛾 berada pada inteval [0.01, 0.15] sedemikian sehingga ketertarikan dari suatu firefly yang dilihat  oleh firefly lain  akan  mengikuti  kurva  yang  dibentuk 𝑒 −𝛾𝑟 𝑖,𝑗 2 .  Hubungan antara  koefisien  penyerapan 𝛾 dan  jarak 𝑟 𝑖,𝑗 dilihat  dari  interval 𝑟 𝑖,𝑗 𝜖[1,10] yang mempengaruhi  nilai 𝑒 −𝛾𝑟 𝑖,𝑗 2 . Jika 𝑟 𝑖,𝑗 sangat besar (lebih  dari 10) maka nilai dari 𝑒 −𝛾𝑟 𝑖,𝑗 2 akan mendekati nol, dan ketertarikan juga akan mendekati nol saat dilihat dari firefly lain sehingga firefly akan selalu bergerak secara acak.
4. 2 Prosedur Evolutionary  Discrete  Firefly  Algorithm (EDFA)  untuk Penyelesaian Travelling Salesman Problem (TSP)
1. Inisialisasi Parameter dan Input Data Parameter-parameter  EDFA yang  akan  digunakan  antara  lain  banyaknya firefly  (p) ,  koefisien  penyerapan  cahaya  ( 𝛾 ),  banyaknya  pergerakan  ( 𝑚 ),  dan maksimum  iterasi  yang  diinginkan  ( MaxIterasi ).  Pada  penelitian  ini  banyaknya populasi firefly (𝑝) bervariasi,  koefisien  penyerapan  cahaya  ( 𝛾) = 0.15 ,  dan banyaknya  pergerakan (𝑚) bervariasi.  Selanjutnya  adalah  memasukkan  data berupa koordinat titik setiap kota dalam koordinat kartesius dengan asumsi bahwa kota sebagai simpul pada graf dan jarak antar kota sebagai sisi pada graf.
2. Membangkitkan Populasi Awal Firefly
Pembangkitan  elemen firefly dilakukan  dengan  cara  membangkitkan  secara random permutasi bilangan (1,2, … , 𝑛) dengan 𝑛 adalah banyak kota.
3. Menghitung Fungsi Tujuan (Evaluasi Firefly )
Fungsi tujuan dalam permasalahan TSP adalah total jarak tempuh yang dilalui pada jalur yang diberikan elemen firefly . Perhitungsn fungsi tujuaan setiap firefly dilakukan menggunakan persamaan (9).
4. Menentukan Intensitas Cahaya Firefly
Fungsi tujuan dalam permasalahan TSP adalah total jarak tempuh yang dilalui pada jalur yang diberikan elemen firefly . Perhitungsn fungsi tujuaan setiap firefly dilakukan menggunakan persamaan (9).
5. Membandingkan Firefly dan Menentukan Firefly Terbaik Pada  tahap  ini  nilai  intensitas  cahaya  setiap firefly akan  dibandingkan  untuk memperoleh firefly terbaik.  Jika  intensitas  cahaya firefly rendah,  maka  akan dilakukan movement menuju firefly dengan  intensitas  cahaya  lebih  besar . Sedangkan untuk firefly terbaik akan dilakukan movement secara random.
6. Melakukan Movement Setiap Firefly
Prosedur movement pada  langkah  ini dilakukan  menggunakan konsep Mutasi Inversi.  Pertama,  menghitung  jarak  antar firefly menggunakan  persamaan  (6) . Selanjutnya  menghitung ketertarikan antar firefly i dan firefly j yang  lain dengan persamaan (13). Setelah  mendapatkan firefly j yang paling  menarik (ketertarikan paling  besar)  maka  akan  dilakukan movement dari firefly  i menuju firefly  j menggunakan persamaan (8)
4. 3 Penyelesaian Contoh Kasus Travelling Salesman Problem

## Menggunakan Program EDFA
Penerapan  program  EDFA  pada  kasus  TSP  dilakukan  menggunakan parameter-parameter  terbaik  yang  diperoleh  dari  ujicoba  beberapa  kombinasi parameter  dalam  program.  Ujicoba  ini  dilakukan  pada  kasus  Ulysses16 menggunakan  parameter  banyak  populasi  ( 𝑝 )  bervariasi,  parameter  banyak pergerakan ( 𝑚 ) bervariasi serta koefisien penyerapan cahaya ( 𝛾 ) = 0.15. Program EDFA  kemudian  dijalankan  10  kali  untuk  mencapai  salah  satu  dari  dua  kriteria terminasi  yaitu  menemukan  hasil  optimal  yang  telah  diketahui  atau  mencapai iterasi maksimum ( 𝑀𝑎𝑥𝐼𝑡𝑒𝑟𝑎𝑠𝑖) = 100000 .
Hasil  ujicoba  menunjukkan  parameter  banyak  populasi  ( 𝑝) mempengaruhi waktu komputasi secara kritis dimana populasi  yang  besar tidak dapat  menjamin bahwa  EDFA  akan  mencapai  solusi  terbaik  lebih  cepat.  Banyak  populasi  ( 𝑝 ) terbaik dengan pencapaian optimal terbanyak dan waktu tercepat adalah 15. Hasil ujicoba  juga  menunjukkan bahwa  banyak pergerakan ( 𝑚 ) tidak  menjamin  secara kritis  waktu  komputasi  yang  diperlukan  untuk  mencapai  hasil  optimal  terbaik. Sehingga  banyak  pergerakan  ( 𝑚 )  dengan  rata-rata  waktu  paling  cepat  yang digunakan sebagai parameter dalam penerapan program pada semua kasus adalah 9.  Selanjutnya  dengan  menggunakan  parameter-parameter  terbaik  yaitu 𝑝 = 15 , 𝑚 = 9 serta 𝛾 = 0.15 ,    progam  EDFA  diterapkan  pada  beberapa  jenis  kasus dengan jumlah data yang berbeda-beda diantaranya Ulysses16, Ulysses22, Eil51, Berli52,  St70,  Rat99  dan  Gr202.  Hasil  penerapan  EDFA  pada  kasus-kasus tersebut pada Tabel 10  menunjukkan solusi optimal  yang ditemukan oleh EDFA serta  solusi  yang  telah  ditemukan  sebelumnya  berdasarkan  data  solusi  optimal pada TSPLIB.
Simulasi  program  juga  menunjukkan  performansi  EDFA  terhadap penyelesaian kasus TSP dilihat dari konvergensi.  Konvergensi dari  fungsi tujuan firefly terbaik  pada  kasus  Ulysses16  dan  Eil51  berturut-turut  melalui  simulasi program dengan iterasi maksimum 1000 ditunjukkan pada Gambar 1 dan Gambar 2.
Gambar 1 . Grafik fungsi tujuan dari firefly terbaik pada kasus Ulysses16 0 10 20 30 40 50 60 70 80 90 100 110 120 130 0 50 100 150 f(x ) Iterasi Konvergensi fungsi tujuan f(x) dari firefly terbaik f(x) Optimal yang diketahui
Gambar 2 . Grafik fungsi tujuan dari firefly terbaik pada kasus Eil51
Berdasarkan  grafik  tersebut,  ditunjukkan  bahwa  solusi  dari  setiap  iterasi konvergen menuju solusi optimal yang diketahui sebelumnya (garis merah). Pada kasus  Ulysses16 firefly terbaik  dapat  mencapai  solusi  sedangkan  untuk  kasus Eil51 firefly tidak  dapat  mencapai  solusi  optimal  sehingga  program  berjalan hingga iterasi masksimum. Iterasi terakhir yang dicapai EDFA untuk setiap kasus TSP yang diselesaikan dapat dilihat pada Tabel 1.
Tabel 1 . Hasil penerapan program EDFA pada 7 kasus TSP
Nama kasus Iterasi terakhir Solusi yang diperoleh Solusi yang telah diketahui Ulysses16 134 73.9876 74.109 Ulysses22 128 75.3097 75.665 Eil51 1000 440.7806 426 Berlin52 1000 7740.9 7542 St70 1000 698.8559 675 Rat99 1000 1287.6 1211 Gr202 6304 538.5306 549.998
Tabel  1  menunjukkan  program  EDFA  berhenti  pada  iterasi  terakhir  yang berbeda-beda  pada  setiap  kasus.  Pada  kasus  Ulysses16  dan  Ulysses22  yang memiliki  iterasi  maksimum  1000  berturut-turut  berhenti  pada  iterasi  ke-134  dan iterasi  ke-128  dengan  solusi  yang  lebih  baik  yaitu  73.9876  dan  75.3097.  Pada kasus  Eil51,  Berlin52,  St70  dan  Rat99,  program  EDFA  berjalan  hingga  iterasi maksimum 1000 dan solusi  yang diperoleh tidak  lebih  baik daripada solusi  yang telah diketahui sebelumnya. Pada kasus Gr202 dengan  iterasi  maksimum  10000, program EDFA berhenti pada iterasi ke-6304 dengan solusi yang lebih baik yaitu 538.5306.
Hasil simulasi program EDFA pada semua kasus TSP hingga solusi optimal diperoleh  memiliki  iterasi  terakhir  yang  berbeda-beda.  Hal  ini  disebabkan  setiap
0 200 400 600 800 1000 1200 1400 1600 0 500 1000 1500 f(x ) Iterasi Konvergensi fungsi tujuan f(x) dari firefly terbaik f(x) Optimal yang diketahui
kasus memiliki jumlah data kota yang berbeda sehingga jika jumlah kota semakin banyak  maka  ruang  solusi  akan  semakin  besar.  Namun  semakin  kecil  data  kota tidak  dapat  menjamin  EDFA  akan  berhenti  pada  iterasi  yang  lebih  cepat dibandingkan  kasus  dengan  data  kota  yang  lebih  besar,  hal  ini  disebabkan populasi  awal firefly yang  dibangkitkan  secara  random  dan  skema  pergerakan yang  dilakukan firefly tidak  dapat  menjamin  solusi  baru  yang  lebih  baik  untuk dibangkitkan menjadi populasi awal yang baru.

## 5. KESIMPULAN
Berdasarkan  hasil pembahasan sebelumnya, dapat ditarik kesimpulan  bahwa EDFA sebagai perkembangan FA telah berhasil diterapkan untuk kasus TSP yang memiliki  solusi  dalam  ruang  diskrit  dengan  dua  perubahan  skema  yaitu  pada perumusan jarak antar firefly dan skema pergerakan menggunakan Mutasi Inversi. Simulasi  program  EDFA  diterapkan  pada  beberapa  kasus  TSP  dari  TSPLIB menggunakan parameter-parameter terbaik yang diperoleh dari hasil ujicoba pada kasus  Ulysses16,  yaitu 𝑝 = 15, 𝑚 = 9, dan γ = 0.15 .  Hasil  simulasi  penerapan EDFA  ini  memberikan  solusi  optimal  yang  sangat  baik  pada  beberapa  kasus dengan  hasil  jarak  optimal  yang  lebih  pendek  dibandingkan  jarak  optimal  yang telah  ditemukan  sebelumnya  yaitu  Ulysses16 = 73.9876 ,  Ulysses22 = 75.3097, dan Gr202 = 538.5306 .

## REFERENSI
[1] Gutin,  G.,  Punnen,  A.  P.  2002. The  Travelling  Salesman  Problem  and  Its Variations. Kluwer Academic Publisher, New York.
[2] Jati,  G.  K.,  Suyanto.  2011.  Evolutionary  Discrete  Firefly  Algorithm  for Travelling Salesman Problem. ICAIS 2011, LNAI. 6943: 393–403 .
[3] Jati,  G.  K.  dkk.  2013.  Discrete  Firefly  Algorithm  for  Traveling  Salesman Problem:  A  New  Movement  Scheme. Swarm  Intelligence  and  Bio-Inspired Computation . Elsevier Inc, London.
[4] Kumbhara, S. N., Pandey, G. M. 2013. Solving Travelling Salesman Problem using  Firefly  Algorithm. International  Journal  for  Research  in  Science  & Advanced Technologies, Issues 2. 2: 053-057 .
[5] Ratnasari,  R.  2016. Penerapan  Firefly  Algorithm  dan  Ant  Colony Optimization  pada  Travelling  Salesman  Problem. Skripsi.  Universitas Jember, Jember.
[6] Samana,  E.  dkk.  2015.  Aplikasi  Simulated  Annealing  untuk  Menyelesaikan Travelling  Salesman  Problem. Buletin  Ilmiah  Mat.  Stat.  dan  Terapannya (Bimaster), No. 1.  03: 25-32 .
[7] Talbi,  E.  G.  2009. Metaheuristic:  From  Design  to  Implementation. Luniver Press, Frome.
[8] Yang, X. S. 2010. Nature-Inspired Metaheuristic Algorithms, 2nd Edition . Luniver Press, Frome.