## Analisis  Perbandingan Algoritma
Particle Swarm Optimization Dan Firefly Algorithm  Dalam Menentukan Minimum Spanning Tree
Desi Novianti 1) , Dewi Anggraini Puspa Hapsari 2)
1 Teknik dan Ilmu Komputer, Universitas Indraprasta PGRI, Depok-Jawa Barat email: desi.novi4nti@gmail.com
2 Ekonomi, Universitas Gunadarma, Jonggol – Jawa Barat email: dewi_anggraini@staff.gunadarma.ac.id
Abstract: Tujuan dari penelitian ini adalah untuk menganalisis perbandingan akurasi   dalam penyelesaian masalah minimum spanning tree  dengan menggunakan algoritma PSO dan FA. Sehingga mendapatkan akurasi terbaik dari keduaalgoritma tersebut. Menganalisis algoritma adalah  untuk  menemukan  karakteristik  dalam  rangka  untuk  mengevaluasi  kesesuaian  untuk berbagai aplikasi atau membandingkannya dengan algoritma lain untuk aplikasi yang sama. Selain  itu,  analisis  algoritma  dapat  membantu  kita  memahami  lebih  baik,  dan  dapat menyarankan  perbaikan  diinformasikan.  Algoritma  cenderung  menjadi  lebih  pendek, sederhana,  dan  lebih  elegan  selama  proses  analisis.  Minimum  spanning  tree  merupakan adalah Spanning Tree dengan jumlah bobot terkecil yang berguna untuk membantu mengatasi problem seperti  menentukan untuk merentangkan jaringan kabel listrik yang menghubungkan sejumlah lokasi dengan panjang kabel yang digunakan sependek-pendeknya mungkin,  melihat pengelompokan  data  yang  tersebar  pada  suatu  ruang,  Perencanaan  jaringan transportasi/distribusi  barang.  Dan  masih  banyak  problem  lainnya.  Algoritma PSO  dan  FA merupakan  beberapa  algoritma  yang  digunakan  untuk  implementasikan  problem  minimum spanning  tree. Dimana  hasil  yang  diperoleh  dari  penelitian  ini  adalah  algoritma  PSO  lebih baik daripada algoritma FA dalam segi kompleksitas waktu eksekusi. Sehingga mendapatkan akurasi terbaik dari kedua algoritma tersebut..
Keywords: Algortima PSO, Algoritma FA, Minimun Spanning Tree
PENDAHULUAN
1.1 Latar Belakang Minimum Spanning Tree (MST) merupakan  adalah  Spanning  Tree  dengan jumlah  bobot  terkecil  yang  berguna  untuk membantu mengatasi problem seperti menentukan  untuk  merentangkan  jaringan kabel  listrik  yang  menghubungkan  sejumlah lokasi dengan panjang kabel yang digunakan sependek-pendeknya  mungkin,    melihat pengelompokan  data  yang  tersebar  pada suatu ruang,
Perencanaan jaringan transportasi/distribusi barang. Penyelesaian  eksak  terhadap  persoalan
ini akan melibatkan algoritma yang mengharuskan  untuk  mencari  kemungkinan semua  solusi  yang  ada.  Sebagai  akibatnya, kompleksitas  waktu  dari  eksekusi  algoritma ini  akan  menjadi  eksponensial  terhadap ukuran  dari  masukan  yang  diberikan. Permasalahan  yang  melibatkan  algoritma demikian lebih dikenal sebagai permasalahan
yang  bersifat  Nondeterministic  Polynomial- time Complete (NP-Complete).
Algoritma PSO  dan  FA merupakan beberapa  algoritma  yang  digunakan  untuk implementasikan problem minimum
spanning tree.
Algoritma  particle  swarm  optimization adalah  metode  pencarian  yang  didasarkan populasi  dan  merupakan  algoritma  optimasi global  yang  dihubungkan  dengan  masalah yang mana solusi terbaik dapat direpresentasikan  sebagai  titik  atau  surface diarea n-dimensional. Firefly algoritma adalah algoritma metaheuristik  yang  terinspirasi  karakteristik kunang-kunang.  Algoritma  ini  pertama ditemukan  oleh  Dr  Xin-She  Yang  di Universitas  Cambridge  pada  tahun  2007. Pada algoritma ini terdapat 3 acuan dasar :
1. Semua  kunang-kunang  adalah  unisex jadi  satu  kunang-kunang  tertarik  dengan kunang-kunang  lain  terlepas  dari  jenis kelamin mereka.
2. Daya tarik sebanding dengan kecerahan, maka  kunang-kunang  dengan  kecerahan lebih  redup  akan  bergerak  ke  arah kunang-kunang  dengan  kecerahan  lebih terang  dan  kecerahan  berkurang  seiring dengan  bertambah  jarak.  Apabila  tidak ada  kunang-kunang  yang  memiliki kecerahan  paling  cerah  maka  kunang- kunang akan bergerak random.
3. Kecerahan kunang-kunang dideterminasikan oleh tempat dari fungsi objektif kunang-kunang Kedua  algoritma  memiliki  akurasi masing-masing, sehinggauntuk mempermudah dalam menentukan akurasi  terbaik  dari  kedua  algoritma tersebut dibutuhkan analisi perbandingan akurasi  untuk    penyelesaian  masalah minimum  spanning  tree    Sehingga mendapatkan  akurasi  terbak  dari  ketiga algoritma tersebut.
1.2 Permasalahan Yang Akan Diteliti
1. Bagaimana  menerapkan  algoritma PSO  dan  FA  untuk  menyelesaikan masalah MST?
2. Bagaimana mendapatkan waktu
eksekusi,  dan  rute  terpendek  dari problem MST  dengan  implementasi
PSO dan FA?
3. Bagaimana mendapatkan akurasi terbaik  dari  algoritma  PSO  atau  FA dalam menyelesaikan masalah MST?
1.3 Tujuan  Penelitian Tujuan  dari  penelitian  ini  adalah menganalisis  perbandingan  akurasi      dalam penyelesaian  masalah  minimum  spanning tree  dengan  menggunakan  algoritma  PSO dan  FA.    Sehingga  mendapatkan  akurasi terbaik dari kedua algoritma tersebut.

## METODE PENELITIAN
Metode yang digunakan dalam memecahkan masalah  pada  penelitian  ini  adalah dengan menggunakan langkah-langkah berikut :
1. Studi Literatur Mencari  dan  mempelajari  literatur- literatur yang ada sesuai dengan permasalahan meliputi karakteristik permasalahan minimum  spanning  tree , konsep  algoritma  PSO  dan  FA,  serta informasi  lainnya  yang  menunjang penelitian ini.
2. Analisa dan Pemrograman Pada  tahap  analisis  dilakukan  langkah- langkah  untuk  penyelesaian  masalah, yaitu:
a. Menerapkan  algoritma  PSO  dan  FA pada  masalah minimum  spanning tree dengan  menggunakan tools MATLAB
b. Menganalisis algoritma PSO dan  FA pada  masalah minimum  spanning tree dengan  menggunakan tools

## MATLAB

## HASIL DAN PEMBAHASAN
Data  diambil  dari  bilangan  random  dari angka  0  sampai  150.  Dimana  terdapat  10 data  X  dan  10  data  Y,  sebagai  koordinat simpul. Data tersebut dapat dilihat pada tabel 4.1.
Perbandingan  hasil  algoritma  PSO  dan FA  dalam  menentukan minimum  spanning tree, daapat dilihat pada tabel 4.2.
Dari  hasil  yang  didapat,  algoritma PSO  dan  FA  menghasilkan  jarak  terpendek yang  sama  namun  jarak  yang  dihasilkan ditemukan  pada  saat  iterasi  yang  berbeda. Iterasi  yang  menggunakan  algoritma  PSO lebih  sedikit  dibandingan  iterasi  algoritma FA.  Sehingga  dapat  dikatakan  algoritma PSO lebih baik daripada algoritma FA dalam segi kompleksitas waktu eksekusi. Tabel 4.1 Tabel Koordinat Simpul Data1 X1 79 60 84 40 43 73 20 25 76 85 Y1 20 43 5 9 61 77 92 28 99 43 Data2 X2 124 55  118 98  116  101 98 75  147  124 Y2 75 90  129  125  112 70 73  142 82  123 Data3 X3 100  140  124 66  144 90 94  122  113  138 Y3 147  103 99  138  112  115  148  106  120  132
Data4 X4 43 29 20 26 38 46 22 45 36 41 Y4 27 37 29 37 30 29 47 32 27 41 Data5 X5 54 80 71 62 43 37 75 68 76 49 Y5 40 59 32 35 67 31 70 55 30 70 Data6 X6 117  140  114  110  144  125  113  148  119  132 Y6 142  143  133  104  121  117  103  121  114  113 Data7 X7 8 10 2 6 6 4 0 1 1 9 Y7 6 2 2 3 5 10 3 5 0 2 Data8 X8 10 8 7 3 9 10 4 12 5 3 Y8 11 12 10 11 7 8 3 3 5 7 Data9 X9 38 11 48 26 19 0 17 86 59 30 Y9 77 6 9 25 40 68 77 39 87 91 Data10 X10 43 88 47 5 17 12 68 55 3 95 Y10 19 87 22 90 93 92 24 12 18 51 Tabel 4.2 Perbandingan Hasil PSO dan FA Data Jarak terpendek Iterasi ke Gambar MST PSO FA PSO FA 1 491.8828  491.8828  Iteration 13  Iteration 20 2 522.0028  415.779 Iteration 28  Iteration 42 3 320.9281  320.9281  Iteration 23  Iteration 24 4 122.4505  122.4505   Iteration 15  Iteration 36 5 239.4149  239.4149  Iteration 19  Iteration 38
6 200.2978  200.2978  Iteration 20  Iteration 38 7 48.9577 49.2296 Iteration 22  Iteration 25 8 54.1479 54.1479 Iteration 16  Iteration 27 9 455.8807  461.7157  Iteration 19  Iteration 15 10 468.0015  468.0015  Iteration 18  Iteration 27

## SIMPULAN
Kesimpulan dari penelitian ini adalah,  perbandingan  akurasi      dalam penyelesaian  masalah  minimum  spanning tree  dengan  menggunakan  algoritma  PSO dan  FA.  Dimana  algoritma  PSO  lebih  baik daripada algoritma FA dalam segi kompleksitas waktu eksekusi. Sehingga  mendapatkan  akurasi  terbaik  dari kedua algoritma tersebut.

## DAFTAR PUSTAKA
Irene,  Ho  Sheau  Fen,  Deris,  Safaai,  and Hasiml, Siti Zaiton Modh, June 2009, “ Incorporating  Of  Constraint  Based Reasoning  Into  Particle  Swarm  Of Computer Science Letters, Vol. 1, Johor – Malaysia.
Robert  Sedgewick.,  Kevin  Wayne.  2011. “Algorithms  (4th  Edition)  ”.  Addison-
Wesley Professional. Singapore
Robert  Sedgewick , Philippe  Flajolet .  2013.
“  An  Introduction  to  the  Analysis  of Algorithms  (2nd  Edition)”.  Addison- Wesley Professional. Singapore Yang Xin-She. 2010. ”Engineering Optimization”,  A  Jhon  Wiley  &  Sons, New Jersey