Jurnal Teknik Informatika dan Sistem Informasi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal. 1810-1820 E- ISSN 2503-2933 1810
Optimasi Travelling Thief Problem Menggunakan Algoritma Tree Physiology Optimization Berbasis

## Hiper Heuristik
Lanang Alun Nugraha* 1 , Ahmad Muklason 2 1,2 Jurusan Sistem Informasi Teknologi Sepuluh November e-mail: * lanang.18052@mhs.its.ac.id

## Abstrak
Travelling  thief  problem  (TTP)  merupakan  gabungan  dari  permasalahan  travelling salesman  problem  dan  knapsack  problem.  travelling  thief  problem  sendiri  merupakan permasalahan  NP-Hard  sehingga  permasalahan  sebagian  besar  diselesaikan  menggunakan algoritma heuristic dan terus berkembang seiring berjalanya waktu.. Algoritma yang digunakan pada  penelitian  ini  adalah  simple random  untuk  pemilihan low level heuristic  (LLH)  dan  tree physiology  optimization  (TPO)  untuk  langkah  move  acceptance  dengan  menggunakan  model Hyper-Heuristics.  Pada  penelitian  yang  telah  dilakukan  sebelumnya  algoritma  TPO  mampu menghasilkan  nilai  yang  cukup  kompetitif  dengan  waktu  komputasi  yang  baik,  sedangkan pemodelan  Hyper-Heuristics  dapat  menghasilkan  nilai  yang  konsisten  pada  data  yang beragam.  Penelitian  diawali  dengan  memodelkan  algoritma  TPO  menjadi  Hyper-Heuristics dan  diuji  coba  dengan  data  dari  TSPLib.  Dari  hasil  uji  coba  yang  dilakukan  dapat  dilihat bagaimana performa algoritma baru pada data yang diuji. Berdasarkan hasil yang didapat dari penelitian ini dapat disimpulkan bahwa algoritma LLH TPO dapat mengolah data TTP dengan ukuran  di  bawah  100  dengan  cukup  baik  terbukti  dengan  hasil  yang  lebih  baik  dari  metode genetic programming based  hyper-heuristic  (GPHS)  yang telah  ada  sebelumnya,  namun  pada data di atas 100 performa LLH TPO menurun jika dibandingkan dengan metode GPHS.
Kata kunci — Travelling Thief Problem, Tree Physiology Optimization, Hyper-Heuristic

## Abstract
Ttraveling  thief  problem  is  a  combination  of  the  traveling  salesman  problem  and  the knapsack  problem.  traveling  thief  problem  itself  is  an  NP-Hard  problem,  so  most  of  the problems  are  solved  using  a  heuristic  algorithm  and  it  continues  to  grow  over  time.  The algorithm used in this study is simple random for the selection of low level heuristics (LLH) and tree  physiology  optimization  (TPO)  for  the  move  acceptance  step  using  the  Hyper-Heuristics model..  In  previous  research,  the  TPO  algorithm  is  able  to  produce  competitive  values  with good  computation  time,  while  Hyper-Heuristics  modeling  can  produce  consistent  values  on various data. The research was started by modeling the TPO algorithm into Hyper-Heuristics and tested it with data from TSPLib. From the results of the trials conducted, it can be seen how the performance of the new algorithm on the data being tested. Based on the results obtained from  this  study,  it  can  be  concluded  that  the  LLH  TPO  algorithm  can  process  TTP  data  with sizes  below  100  quite  well,  as  evidenced  by  better  results  than  the  previous  genetic programming  based  hyper-heuristic  (GPHS)  method,  but  the  data  above  100  LLH  TPO performance decreased when compared to the GPHS method.
Keywords — Travelling Thief Problem, Tree Physiology Optimization, Hyper-Heuristic
1811 Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal . 1810-1820 E-ISSN 2503-2933
Lanang Alun Nugraha , et., al [ Optimasi Travelling Thief Problem Menggunakan Algoritma Tree Physiology Optimization Berbasis Hiper Heuristik ]
Title of manuscript is short and clear, implies research results (First Author)

## 1. PENDAHULUAN
Travelling Thief Problem (TTP). TTP merupakan permasalahan yang dirancang dengan menggabungkan  antara Travelling  Salesman  Problem (TSP)  dan Knapsack  Problem (KP). Permasalahan ini pertama kali diusulkan oleh boyandi [1] pada tahun 2013. Permasalahan TTP termasuk  dalam  permasalahan  NP-Hard  karena  tidak  memungkinkan  untuk  penyelesaian menggunakan metode exact dalam waktu yang terbatas. Karena termasuk dalam permasalahan NP-Hard maka penyelesaian yang digunakan untuk TTP merupakan pengembangan dari metode heuristic .  Penyelesaian  permasalahan  menggunakan  metode  yang  berdasar  pada heuristic bertujuan  untuk  mendapatkan  hasil  yang  cukup  hingga  baik  dengan  waktu  pengerjaan  yang terbatas.
Travelling Salesman Problem (TSP) merupakan permasalahan kombinatorial NP-Hard yang  terus  berkembang.  TSP  sendiri  merupakan  permasalahan  untuk  menemukan  cara  terbaik untuk mengunjungi semua kota dan kembali ke titik awal yang meminimalkan jarak perjalanan atau  biaya  perjalanan  [2].  Data  dari  TSP  merupakan  seperangkat  kota  dan  seperangkat  biaya atau  jarak    perjalanan  antar  setiap  pasangan  yang  memungkinkan. Knapsack  Problem (KP) adalah  permasalahan  untuk  membawa  beberapa  barang  dengan  ukuran  yang  berbeda  dengan nilai  yang  berbeda  ke  dalam  sebuah  ransel  dengan  volume  tertentu  dengan  tujuan memaksimalkan  profit  atau  nilai  barang  yang  dibawa  [3].  Dari  kedua  permasalahan  tersebut dihasilkan permasalahan TTP yang bertujuan untuk memberikan  model benchmark yang lebih mendekati  masalah  optimasi  yang  sebenarnya  dalam  berbagai  situasi,  di  mana  permasalahan tersebut terdiri dari sub-sub masalah yang saling berinteraksi [4].
Penelitian  untuk  permasalahan  TTP  telah  dilakukan  dan  berkembang  dalam  beberapa tahun  ke  belakang.  Penelitian  yang  dilakukan  dalam  penyelesaian  permasalahan  TTP menggunakan  berbagai  macam  algoritma  yang  dikembangkan.  Penelitian  yang  dilakukan  oleh Junhua  Wu  [5]  menyelesaikan  permasalahan  TTP  dengan  membandingkan  tiga  algoritma berbeda  menghasilkan  bahwa  metode Dynamic  Programming yang  diusulkan  menghasilkan solusi  yang  optimal  di  sebagian  besar  data  berukuran  sedang  dan  kecil  yang  digunakan. Penelitian  lainya  dilakukan  oleh  Mohamed  El  Yafrani  [4]  menyelesaikan  permasalahan  TTP menggunakan  metode Genetic  Programming  Base  Hyper-Heuristics (GPHS)  yang dibandingkan  dengan  beberapa  metode  yang  lain.  Hasil  dari  penelitian  ini  adalah  bahwa algoritma  yang  diusulkan  mendapatkan  hasil  yang  kompetitif  dibandingkan  algoritma  lain. Selain  permasalahan  TTP  penelitian  sebelumnya  tentang  permasalahan  TSP  yang  merupakan bagian dari permasalahan TTP juga dilakukan. Penelitian yang dilakukan oleh Halim dan Ismail [6]  membandingkan  beberapa  algoritma heuristic pada  permasalahan Travelling  Salesman Problem .  Dari  penelitian  tersebut  disimpulkan  bahwa  algoritma  dengan  waktu  komputasi tercepat  adalah Nearest  Neighbor (NN).  Untuk  algoritma  yang  menghasilkan  nilai  mendekati optimum adalah Tabu Search (TS). Studi lain oleh Halim dan Ismail [7] yang meneliti tentang penyelesaian  masalah  TSP  dan Benchmark  Function  Characteristics menggunakan  algoritma Tree  Physiology  Optimization (TPO)  dan  membandingkan  dengan  beberapa  algoritma  lainya. Dari penelitian ini  disimpulkan  bahwa pada  permasalahan TSP, TPO  menghasilkan  nilai  yang dapat dibandingkan dengan Genetic Algorithm (GA).
Selain  dari  permasalahan  TTP  dan  turunannya,  dilakukan  juga  eksplorasi  pada penelitian  yang  menggunakan  mode hyper-heuristic .  Pada  penelitian  oleh  Bacha  [8]  yang meneliti  tentang  penyelesaian  permasalahan Permutation  Flow  Shop  Problem dengan menggunakan  metode Hyper-Heuristic  Genetic  Algoritm .  Hasil  dari  penelitian  ini  adalah metode Hyper-Heuristic Genetic Algoritm dapat menyelesaikan 50 dari 120 data permasalahan dengan  hasil  paling  optimal  dan  menghasilkan  nilai  yang  kompetitif  pada  data  yang  lainya. Penelitian  lain  oleh  Choong  dan  Li-Pei  Wong  [9]  yang  mengusulkan  metode Hyper-Heuristic
Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal. 1810-1820 E- ISSN 2503-2933 1812
dengan  otomatisasi  desain  pada  komponen high  level  heuristic dengan  menggunakan Q- learning untuk  menetapkan  komponen  yang  ada.  Metode  yang  diusulkan  tersebut  digunakan untuk  menyelesaikan  enam  domain  permasalahan  yaitu, Boolean  Satisfiability (SAT), One- dimensional  Bin-Packing (BP), Permutation  Flow  Shop (FS), Personnel  Scheduling (PS), Traveling  Salesman  Problem (TSP)  dan Vehicle  Routing Problem  (VRP).  Model  QHH  yang diusulkan  dapat  menyelesaikan  tiga  puluh  contoh benchmark dari  enam  domain  masalah  di HyFlex dengan baik.
Berdasarkan  penelitian  yang  telah  ada  sebelumnya  penyelesaian  permasalahan  TTP masih terus berkembang. Pada perkembangan penelitian tersebut belum ada penggunaan metode TPO  dengan  model hyper-heuristic untuk  penyelesaiannya.  Pada  penelitian  yang  dilakukan pada  penelitian  [6]  TPO  sendiri  merupakan  algoritma  nomor  dua  dengan  komputasi  tercepat setelah NN dan nomor nilai paling mendekati optimal setelah TS pada permasalahan TSP. Dari situ  algoritma  TPO  masih  dapat  dikembangkan  untuk  menyelesaikan  permasalahan  TTP  yang merupakan gabungan TSP dan Knapsack Problem . Untuk pengembangan yang dilakukan pada penelitian  adalah  menggunakan  TPO  dalam  model hyper-heuristic. Dengan  menggunakan model hyper-heuristic diharapkan  dapat  meningkatkan  performa  dalam  berbagai  data  yang beragam. Data yang digunakan pada penelitian ini didapatkan dari TSPLib yang juga digunakan pada penelitian [4]. Contoh data yang digunakan dapat dilihat pada tabel 1.
Tabel 1. Contoh Data TTP NAME eil51-TTP KNAPSACK DATA TYPE Uncorrelated NUMBER OF ITEMS 50 CAPACITY OF KNAPSACK  2226 DIMENSION 51 MIN SPEED 0.1 MAX SPEED 1 RENTING RATIO 7.19 EDGE_WEIGHT_TYPE CEIL_2D NODE_COORD_SECTION 1 37 52 2 49 49 3 52 64 . . . 51 30 40 ITEMS SECTION INDEX PROFIT  WEIGHT ASSIGNED NODE NUMBER 1 119 1 2 2 187 896 3 3 997 367 4 - - - - 50 509 885 51
1813 Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal . 1810-1820 E-ISSN 2503-2933
Lanang Alun Nugraha , et., al [ Optimasi Travelling Thief Problem Menggunakan Algoritma Tree Physiology Optimization Berbasis Hiper Heuristik ]
Title of manuscript is short and clear, implies research results (First Author)
2. METODE PENELITIAN
Penelitian  ini  dilakukan  dengan  melalui  beberapa  tahapan  yaitu  desain  algoritma, implementasi, dan analisis hasil.

## 2. 1 Desain Algoritma
Pada  desain  algoritma  ini  terbagi  menjadi  empat  bagian  yaitu  konversi  format  data, penetapan  solusi  awal,  seleksi  pemilihan low  level  heuristic (LLH)  ,  dan  penggunaan  langkah move  acceptance .  Pada  desain  algoritma  ini  akan  menggunakan  sepuluh low  level  heuristic dengan simple  random sebagai  metode  pemilihannya,  sedangkan  untuk  langkah move acceptance menggunakan algoritma tree physiologi optimization (TPO).

## 2. 1.1 Konversi Format Data
Data  yang  digunakan  merupakan  data TTP dengan  format  umum  seperti  pada  tabel  1. Berdasarkan  data  tersebut  diperlukan  konversi  untuk  mengubah  titik  koordinat  kota  menjadi jarak antar kota. Oleh karena itu setiap titik koordinat antar kota dihitung menggunakan rumus euclidean  distance dan dibulatkan  ke  atas  agar sesuai  dengan  format  yang  dapat  diolah  dalam metode.

## 2. 1.2 Inisialisasi Solusi Awal
Solusi  awal  yang  digunakan  dalam  menentukan  rute  kota  didapatkan  dengan menggunakan  metode nearest  neighbor dengan  titik  awal  didapatkan  secara  acak.  Dengan metode  ini  kota  pertama  diacak  dari  semua  kota  yang  ada  lalu  kota  selanjutnya  didapatkan dengan  mencari  jarak  terdekat  dan  belum  pernah  dikunjungi.  Sedangkan  solusi  awal  untuk barang bawaan dibiarkan kosong yang bertujuan untuk mendapatkan hasil yang lebih fleksibel.

## 2. 1.3 Selesksi Pemilihan Low Level Heuristic Menggunakan Simple Random
Solusi  awal  yang  didapatkan  pada  langkah  sebelumnya  akan  diolah  menggunakan sepuluh low level heuristic yang didapatkan dari jurnal [10]. Untuk LLH pada pemilihan barang yang  akan  dibawa  didapatkan  melalui  jurnal  [4].  Metode  pemilihan  menggunakan  metode simple random, pada metode ini akan diacak nilai sebanyak jumlah LLH yang  digunakan dari nilai  tersebut  dipilih  LLH  nomor  berapa  yang  akan  digunakan  pada  pengolahan  dalam  iterasi tersebut.  Pada  setiap  pemilihan  LLH  untuk  rute  akan  selalu  berpasangan  dengan  LLH  untuk barang  bawaan.  Untuk  penelitian  ini  digunakan  dua  skenario  percobaan  yaitu  hanya menggunakan LLH dengan metode Hill Climbing (HC) dan LLH dengan move acceptance atau metode hyper-heuristic .
LLH yang digunakan pada barang adalah memilih secara acak satu titik dan mengganti nilai  titik  tersebut  jika  nilai  awalnya  0  maka  menjadi  1  dan  sebaliknya.  LLH  yang  digunakan dalam perubahan rute sebagai berikut.
LLH1:  Dua  kota  dipilih  dan  bagian  tur  dibalik  antara  dua  kota  yang  dipilih  ini.  Ini dilakukan di setiap kota, mulai dari kota awal.
LLH2: Sepasang kota akan dipilih dari tur. Ini dilakukan di setiap kota, mulai dari kota awal.  Misalnya,  kota  dan  kota  3  dengan  kota  2  dan  kota  6  dan  kota  7  dipilih.  Gerakan  2-opt dilakukan di rute.
LLH3: Perpindahan 2-opt akan dilakukan, tetapi kota-kota dipilih secara acak. LLH4: Dua kota dipilih secara acak dan mereka akan bertukar posisi. Sebagai contoh; kota 2 dan 7 dipilih. Kota 2 dan 7 akan bertukar posisi.
LLH5: beroperasi sama seperti LLH2. Langkah pertama yang menghasilkan perbaikan atas solusi saat ini akan diterima.
Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal. 1810-1820 E- ISSN 2503-2933 1814
LLH6:  Dua  kota  dipilih  dan  membalikkan  tur  antara  dua  kota  yang  dipilih  ini. Contohnya  seperti  di  LLH1,  bagaimanapun,  prosedur  dilakukan  pada  kota  yang  dipilih  secara acak.
LLH7: Dua kota dipilih secara acak dan mereka akan bertukar posisi. Contohnya seperti pada LLH4. Prosedur ini akan diterapkan berulang kali hingga tidak ada perbaikan lebih lanjut.
LLH8:  Dua  kota  mulai  dari  dua  ujung  akan  dipilih  dan  bertukar  posisi.  Kota-kota  di antara akan dibalik. Prosedur ini akan dilakukan di semua kota. Contohnya seperti pada LLH2. Peningkatan terbaik akan dicatat.
LLH9:  Dua  kota  mulai  dari  dua  ujung  akan  dipilih  dan  bertukar  posisi.  Prosedur  ini akan dilakukan di semua kota. Contohnya seperti pada LLH4. Peningkatan terbaik akan dicatat.
LLH10:  Dua  kota  yang  dimulai  dari  dua  ujung  akan  dipilih  dan  kota  di  antara  akan dibalik. Prosedur ini akan dilakukan di semua kota. Contohnya seperti pada LLH1. Peningkatan terbaik akan dicatat.

## 2. 1.4 Move Acceptance dengan Tree Physiology Optimization
Langkah  selanjutnya  ketika  pemilihan  LLH  telah  dilakukan  adalah move  acceptance . Langkah ini dilakukan untuk memenuhi model hyper-heuristik secara umum yaitu mempunyai langkah LLH selection dan move acceptance [11]. Pada langkah move acceptance ini digunakan algoritma tree  physiologi  optimization [7]  untuk  mengolah  data.  langkah move  acceptance ini digunakan jika selama empat iterasi secara beruntun tidak menghasilkan nilai fitness yang lebih baik.  Empat  iterasi  beruntun  ditetapkan  untuk  tetap  memberi  ruang  pada  LLH  yang pengerjaannya  lebih  cepat  namun  tetap  seimbang  dengan  menggunakan  TPO  pada move accepatance untuk menghasilkan nilai yang lebih baik dengan pengerjaan yang lebih memakan waktu daripada LLH. Jika setelah move acceptance dan LLH tetap tidak ada perubahan selama 100  iterasi  beruntun  maka  akan  dilakukan  penukaran  titik  kota  dan  barang  secara  acak  dan menyimpan  nilai fitness terbaik  sementara.  Nilai  ini  akan  dibandingkan  dengan  setiap  nilai fitness yang  dihasilkan  nanti.  Nilai fitness terbaik  akan  diambil  sebagai  hasil  akhir.  Algoritma TPO digunakan untuk mengolah rute yang merupakan permasalahan TSP. Prosedur TPO dapat dilihat pada gambar 1.TPO pada model ini dimodifikasi agar menjadi berbasis solusi tunggal di mana  sebelumnya  berbasis  populasi.  Hal  ini  dilakukan  untuk  membuat  waktu  pengerjaan menjadi lebih cepat dan menyesuaikan dengan mode yang dibuat.
Gambar 1. Algoritma TPO
1815 Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal . 1810-1820 E-ISSN 2503-2933
Lanang Alun Nugraha , et., al [ Optimasi Travelling Thief Problem Menggunakan Algoritma Tree Physiology Optimization Berbasis Hiper Heuristik ]
Title of manuscript is short and clear, implies research results (First Author)
Prosedur  pengolahan  data  menggunakan  metode  LLH  TPO  dengan  pemodelan hyperheuristic dapat  dilihat  pada flowchart di  gambar  2.  Pada  gambar  ini  dijelaskan  bahwa memulai  dengan  membuat  solusi  awal  kemudian  mengolah  solusi  awal  dengan  memilih  LLH dengan  metode simple  random .  Setelah  LLH  yang  telah  dipilih  maka  hasil  akan  di  optimasi berdasarkan langkah LLH yang dipilih. Kemudian hasil optimasi akan dievaluasi apakah lebih baik atau tidak. Jika lebih baik maka dilakukan pemilihan LLH kembali pada iterasi baru. Jika tidak lebih baik selama empat kali beruntun maka diolah menggunakan TPO pada langkah move acceptance . Jika solusi lebih baik maka disimpan jika tidak lebih baik dan beruntun selama 100 iterasi  maka  akan  diolah  dengan  pengacakan  rute  dan  hasil  terbaik  tetap  disimpan  untuk dibandingkan dengan nilai fitness yang baru.
Gambar 2. Flowchart Alur LLH TPO
Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal. 1810-1820 E- ISSN 2503-2933 1816

## 2. 2 Implementasi Algoritma
Algoritma  yang  telah  dihasilkan  diimplementasikan  dalam  bahasa  pemrograman  java dengan  menggunakan  program  NetBeans  IDE  8.2.  Pada  tujuh dataset yang  digunakan  akan dijalankan  pengetesan  sebanyak  sepuluh  kali  pada  setiap dataset .  Waktu  maksimal  setiap pengetesan adalah 10 menit, waktu ini berlaku pada setiap dataset .

## 2. 3 Analisis Hasil
Hasil dari implementasi algoritma yang telah dilakukan pada langkah sebelumnya akan dianalisis  dengan  membandingkan  hasil  pada  skenario  dengan  menggunakan  LLH  HC,  LLH TPO  dan  GPHS  yang  didapatkan  pada  jurnal  [4].  Perbandingan  hasil  penyebaran  10  kali percobaan  tiap dataset pada  LLH  HC  dan  LLH  TPO  yang  dilakukan  akan  disajikan  dalam bentuk grafik boxplot untuk melihat konsistensi hasil pada kedua metode ini.

## 3. HASIL DAN PEMBAHASAN
Setelah  dilakukan  percobaan  pada  tujuh dataset di  mana  setiap dataset dijalankan sebanyak sepuluh kali dengan algoritma LLH HC dan LLH TPO didapatkan hasil berupa nilai fitness dengan  rata-rata  hasil  dan  nilai  terbaik  yang  dapat  dilihat  pada  tabel  2  dan  perubahan nilai LLH HC dibanding LLH TPO dapat dilihat pada tabel 3. Selain itu perbandingan nilai pada setiap  iterasi  dengan  menggunakan dataset Berlin  52  juga  disajikan  dalam  gambar  3. Penyebaran data dalam bentuk boxplot pada kedua algoritma dapat dilihat pada gambar 4 dan 5. Dan hasil dari perbandingan LLH HC , LLH TPO, dan GPHS dapat dilihat pada gambar 6.
Tabel 2. Perbandingan Hasil LLH HC Dengan LLH TPO LLH HC LLH TPO Instance Best Avg Best Avg Eil 51 4033,506  3473,191 4209,285  4081,999 Berlin 52 4031,638  3298,248 4205,059  4129,001 Eil 76 3053,056  2368,944 3695,83 3570,226 KroA 100 4091,145  3048,292 4882,179  4461,281 A280 16365,95 14672,86  16140,99 15105,4 Pr439 29294,63  26290,55 30463 27859,57 Rat768 29689,26  25273,46 31007,75  28557,82 Tabel 3. Perubahan Nilai dari LLH HC Dibanding LLH TPO Instance Best Avg Eil 51 +4,4% +17,5% Berlin 52 +4,3% +25,2% Eil 76 +21,1% +50,7% KroA 100 +19,3% +46,4% A280 -1,4% +2,9% Pr439 +4,0% +6,0% Rat768 +4,4% +13,0%
1817 Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal . 1810-1820 E-ISSN 2503-2933
Title of manuscript is short and clear, implies research results (First Author)
Gambar 3. Hasil Perbandingan Nilai Fitness pada Data Berlin 52
Berdasarkan  hasil  dari  algoritma  LLH  HC  dan  LLH  TPO  /  MA  dapat  dilihat  bahwa algoritma  LLH  TPO  menghasilkan  nilai  rata-rata  yang  lebih  bagus  pada  semua dataset dibandingkan dengan algoritma LLH HC dan untuk nilai terbaik juga unggul di semua dataset kecuali Eil 76. Jika dilihat dari perbandingan hasil fitness tiap iterasi menggunakan data Berlin 52  algoritma  LLH  HC hanyak mengalami  kenaikan  pada  awal  iterasi  hingga  iterasi  ke  557 setelah  itu  hanya  mengalami  sedikit  kenaikan  pada  iterasi  1113,  setelah  iterasi  ke  1113  tidak terjadi  kenaikan  hingga  akhir  iterasi  yang  menandakan  sedang  terjebak  di local  optimum . Sedangkan  pada  algoritma  LLH  TPO  dapat  dilihat  bahwa  perubahan  nilai fitness dari  awal hingga akhir iterasi dinamis yang dapat menandakan juga tidak terjebak dengan local optimum . Untuk  nilai fitiness yang  dihasilkan  juga  lebih  baik  daripada  LLH  HC  dan  dapat  sedikit  demi sedikit  naik  pada  iterasi  yang  besar.  Untuk  kerapatan  hasil  percobaan  yang  dilakukan  10  kali pada  setiap  data  dapat  dilihat  pada  gambar  3  dan  4  jika  algoritma  LLH  TPO  menghasilkan kerapatan  data  yang  lebih  rapat  daripada  LLH  HC.  Pada  data  berukuran  kurang  dari  100 perbedaan  kerapatan  terlihat  cukup  signifikan,  menandakan  bahwa  LLH  TPO  menghasilkan nilai  yang  lebih  konsisten daripada  LLH  HC.  Secara  umum  dapat  dilihat  bahwa  dari  berbagai segi algoritma LLH TPO lebih baik daripada algoritma LLH HC. Hal ini dikarenakan algoritma LLH  TPO  mempunyai  langkah move  acceptance dan  pengacakan  rute  dan  barang  yang memungkinkan  untuk  lepas  dari local  optimum .  Sehingga  ketika  iterasi  dengan  jumlah  besar dijalankan data akan terus berusa mencari nilai global optimum.
Gambar 4. Boxplot Perbandingan Hasil LLH HC Dengan LLH TPO 1
-4000 -2000 0 2000 4000 6000 1 6 2 6 1 2 5 1 1 8 7 6 2 5 0 1 3 1 2 6 3 7 5 1 4 3 7 6 5 0 0 1 5 6 2 6 6 2 5 1 6 8 7 6 7 5 0 1 8 1 2 6 8 7 5 1 9 3 7 6 N il a i F it n e ss Iterasi Perbandingan Hasil Berlin 52 LLH+MA LLH+HC
Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal. 1810-1820 E- ISSN 2503-2933 1818
Gambar 5. Boxplot Perbandingan Hasil LLH HC Dengan LLH TPO 2
Gambar 6. Hasil Perbandingan Fitness TPO LLH, HC LLH, dan GPHS
Berdasarkan  gambar  5  dapat  dilihat  bahwa  pada  data  berukuran  51,52,  dan  100 algoritma  LLH  TPO  mendapatkan  hasil  terbaik  dari  semua  algoritma.  Untuk  data  berukuran 76,280,439,768  nilai  terbaik  dihasilkan  oleh  algoritma  GPHS.  berdasarkan  hasil fitness dapat disimpulkan bahwa algoritma yang diusulkan yaitu LLH TPO dapat bersaing dengan algoritma GPHS  yang  telah  menghasilkan  nilai  tinggi  pada  semua dataset .  Pada  data  rendah  LLH  TPO berhasil mengungguli nilai dari algoritma GPHS.
0 10000 20000
30000 40000 50000 Eil 51 Berlin 52 Eil 76 KroA 100 A280 Pr439 Rat768 Nilai Fitness Perbandingan Hasil TTP GPHS TPO LLH HC LLH
1819 Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal . 1810-1820 E-ISSN 2503-2933
Lanang Alun Nugraha , et., al [ Optimasi Travelling Thief Problem Menggunakan Algoritma Tree Physiology Optimization Berbasis Hiper Heuristik ]
Title of manuscript is short and clear, implies research results (First Author)

## 4. KESIMPULAN
Kombinasi  antara  pemilihan low  level  heuristic (LLH)  dan  algoritma tree  physiologi optimization (TPO)  untuk  permasalahan travelling  thief  probelm (TTP)  diusulkan  pada penelitian  ini. Simple  Random digunakan  pada  proses  pemilihan  LLH  sementara  TPO digunakan  pada  langkah move  acceptance sehingga  memenuhi  kriteria Hyper-Heuristic yang memiliki penyeleksian LLH dan move acceptance . Kesimpulan dari kombinasi algoritma yang diterapkan yaitu:
Kombinasi  dari  seleksi  LLH  dengan simple  random dan  algoritma  TPO  pada  langkah move  acceptance berhasil  diimplementasikan  dan  dapat  memenuhi hard  constraint pada  tujuh dataset TTP yang digunakan. Pada penelitian ini dilakukan dua skenario yaitu LLH dengan hill climbing dan  LLH  dengan  TPO.  Dari  hasil  perbandingkan  dua  metode  tersebut  didapatkan bahwa  penambahan move  accepatance dengan  menggunakan  TPO  dan  pengacakan  rute  dan barang  ketika  hasil  berulang  dapat  meningkatkan  nilai fitness menjadi  lebih  baik,  hal  tersebut terbukti dari peningkatan hasil rata-rata di ketujuh data yang dilakukan. Hasil eksperimen pada dataset berukuran  51,52,dan  100  menunjukkan  bahwa  Kombinasi  dari  seleksi  LLH  dengan simple random dan algoritma TPO pada langkah move acceptance dapat mencapai solusi yang lebih  baik  dari  metode genetic  programming  based  hyper-heuristic (GPHS)  hasil  pada  jurnal [4].
Dari  hasil  ini  dapat  disimpulkan  bahwa  algoritma  LLH  TPO  dapat  mengolah  data dengan  ukuran  sedang  dengan  cukup  baik.  Hasil  eksperimen  pada dataset 76,280,439,786 menunjukkan bahwa algoritma GPHS yang dikembangkan pada jurnal [4] memiliki nilai yang lebih baik dari algoritma LLH TPO yang dikembangkan pada penelitian ini. Dari hasil ini dapat disimpulkan  pada  data  dengan  ukuran  besar  algoritma  LLH  TPO  masih  kurang  baik  dalam mengolah data dibandingkan algoritma GPHS.

## 5. SARAN
Kombinasi  dari  seleksi  LLH  dengan simple  random dan  algortima  TPO  pada  langkah move  acceptance berhasil  diimplementasikan  dalam  kerangka hyper-heuristic namun  pada pengimplementasiannya dengan dataset berukuran besar masih belum mendapatkan hasil yang lebih baik dibanding jurnal [4] .Untuk penelitian selanjutnya diharapkan penyesuaian pemilihan dan variasi LLH serta modifikasi dari TPO dapat dilakukan. Hal ini bertujuan untuk membuat metode menghasilkan nilai yang lebih baik pada data berukuran besar serta kestabilan hasil rata- rata di semua data.

## DAFTAR PUSTAKA
[1] M.  R.  Bonyadi,  Z.  Michalewicz,  and  L.  Barone.  2013, “The  Travelling  Thief  Problem: The  First  Step  In  The  Transition  From  Theoretical  Problems  to  Realistic  Problems,” 2013 IEEE Congr. Evol. Comput. CEC 2013 , pp. 1037–1044.
[2] R.  Matai,  S.  Singh,  and  M.  Lal.  2014, “Traveling  Salesman  Problem:  an  Overview  of Applications,  Formulations,  and  Solution  Approaches,” Travel.  Salesm.  Probl.  Theory Appl. , No. January.
Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal. 1810-1820 E- ISSN 2503-2933 1820
[3] K. W. Ross and D. H. K. Tsang. 1989, “The Stochastic Knapsack Problem,” IEEE Trans. Commun. , Vol. 37, No. 7, pp. 740–747.
[4] M. El Yafrani, M. Martins, M. Wagner, B. Ahiod, M. Delgado, and R. Lüders. 2018, “A hyperheuristic  Approach  Based  on  Low-Level  Heuristics  for  The  Travelling  Thief Problem,” Genet. Program. Evolvable Mach. , Vol. 19, No. 1–2, pp. 121–150.
[5] J. Wu, M. Wagner, S. Polyakovskiy, and F. Neumann. 2017, “Exact Approaches For The Travelling Thief Problem,” arXiv , pp. 110–121.
[6] A. H. Halim and I. Ismail. 2019, “Combinatorial Optimization: Comparison of Heuristic Algorithms in Travelling Salesman Problem,” Arch. Comput. Methods Eng. , Vol. 26, No. 2, pp. 367–380.
[7] A. H. Halim and I. Ismail. 2017, “Tree Physiology Optimization in Benchmark Function and Traveling Salesman Problem,” J. Intell. Syst. , Vol. 28, No. 5, pp. 849–871.
[8] F.  B.-S.  T.  Sarra  Zohra  Ahmed  Bacha,  Mohamed  Walid  Belahdji,  Karima  Benatchba. 2019, “ A New Hyper-Heuristic to Generate E ective Instance GA for the.pdf.” pp. 1365– 1374.
[9] S. S. Choong, L. P. Wong, and C. P. Lim. 2018, “Automatic Design Of Hyper-Heuristic Based On Reinforcement Learning,” Inf. Sci. (Ny). , Vol. 436–437, pp. 89–107.
[10]  Z.  A.  Aziz.  2015, “Ant  Colony  Hyper-heuristics  for  Travelling  Salesman  Problem,” Procedia Comput. Sci. , Vol. 76, No. Iris, pp. 534–538.
[11]   and J. R. W. Edmund K. Burke, Matthew Hyde, Graham Kendall, Gabriela Ochoa, Ender ¨Ozcan.  2010,  “ A  Classification  of  Hyper-heuristic  Approaches,”  Handbook  of Metaheuristics , Vol. 146. p. 648.