Jambura Journal of Mathematics Volume 1 Nomor 2, Juli 2019
Journal Homepage: http://ejurnal.ung.ac.id/index.php/jjom , p-ISSN: 2654-5616, e-ISSN: 2656-1344

## Algoritma Ant Colony Optimization pada Quadratic Assignment Problem
Oni Soesanto 1* , Pardi Affandi 2 , Nurul Dasima Astuti 3
1,2,3 Program Studi Matematika Fakultas MIPA, Universitas Lambung Mangkurat, Jl. Ahmad Yani KM. 36, Banjarbaru, Kalimantan Selatan, Indonesia
* Penulis Korespondensi. Email: osoesanto@ulm.ac.id

## ABSTRAK
Quadratic Assignment Problem (QAP) merupakan salah satu perluasan dari masalah penugasan dengan  menetapkan n fasilitas  ke n lokasi  tertentu  untuk  meminimalkan  total  biaya penugasan.  QAP  juga  merupakan  masalah  optimasi  kombinatorial  yaitu  masalah  yang mempunyai himpunan solusi terhingga. Pada dasarnya solusi dari masalah kombinatorial bisa didapatkan  dengan  hasil  yang  tepat  namun  untuk  masalah  kompleks  dengan  ukuran  data yang lebih besar cukup sulit dalam perhitungan karena waktu yang digunakan cukup lama untuk proses penyelesaian. Salah satu algoritma yang diterapkan dalam penyelesaian QAP ini adalah algoritma Ant Colony Optimization (ACO) yaitu algoritma yang  meniru tingkah laku semut dalam mencari makanan dari sarang ke sumber makanan dengan bantuan komunikasi tak langsung yang disebut pheromone , sehingga pheromone ini digunakan untuk mencari solusi optimal  dengan  waktu  yang  cukup  singkat.  Penelitian  ini  menggunakan  ACO  untuk menyelesaikan masalah QAP dengan melibatkan rumus random proportional rule , mendapatkan solusi terkecil dan memperbaharui pheromone hingga penugasan stabil. Solusi yang didapatkan bernilai  tetap  sampai  solusi  maksimum  penugasan.  Memanfaatkan  studi  kasus pada  kasus Nugent  diperoleh  solusi  yang  lebih  minimal  dan  penempatan  fasilitas  kelokasi  yang  tepat melalui  bantuan pheromone dan  disimpan  dalam tabu  list sehingga  semua  fasilitas mendapatkan lokasi yang layak dengan waktu yang cukup singkat dalam penyelesaian.
Kata Kunci:
Quadratic Assignment Problem, Ant Colony Optimization, Tabu List, Pheromone
Diterima: 31-05-2019 Disetujui: 13-07-2019 Online: 30-07-2019

## ABSTRACT
Quadratic Assignment Problem (QAP) is one extension of the assignment problem by setting n facilities to n certain locations to minimize the total assignment costs. QAP is also a combinatorial optimization problem  that  is  a  problem  that  has  a  finite  set  of  solutions.  Basically  the  solution  of  combinatorial problems can be obtained with the right results but for complex problems with larger data sizes it is quite difficult  to  calculate  because  the  time  used  is  long  enough  for  the  completion  process.  One  of  the algorithms implemented in the completion of QAP is the Ant Colony Optimization (ACO) algorithm is an algorithm that mimics the behavior of ants in finding food from the nest to a food source with the help of indirect communication called pheromone, so that pheromone is used to find optimal solutions with quite  a  short  time.  in  this  research  ACO  is  used  to  solve  the  QAP  problem  by  using  a  random proportional of rule formula then getting the smallest solution and renewing the pheromone until the assignment is stable and the solution obtained is fixed until the maximum assignment solution. The results  obtained  to  complete  the  Quadratic  Assignment  Problem  with  the  Ant  Colony  Optimization algorithm to get a solution to the QAP problems tested in the Nugent case resulted in a more minimal
solution and the placement of appropriate location facilities through pheromone assistance and stored in a taboo list so that all facilities get a decent location with a worth it short time in completion.
Keywords:
Quadratic Assignment Problem, Ant Colony Optimization, tabu list, pheromone
Received: 2019-05-31 Accepted: 2019-07-13 Online: 2019-07-30 DOI: http://dx.doi.org/10.34312%2Fjjom.v1i2.2353

## 1.  Pendahuluan
Masalah penugasan adalah salah satu masalah optimasi pengalokasian dari satu sumber (pekerja  atau  mesin)  yang  ditugaskan  ke  suatu  tugas  (pekerjaan  atau  lokasi)  dengan tujuan  untuk  mendapatkan biaya  optimal  [1]. Masalah  penugasan  diperluas  manjadi Quadratic  Assignment  Problem (QAP)  yang  merupakan  masalah  penempatan  fasilitas lokasi.  QAP  diperkenalkan  oleh  Koopmans  dan  Backman  pada  tahun  1957  dengan menetapkan 𝑛 fasilitas (material) ke n lokasi tertentu untuk meminimalkan total biaya aktivitas kegiatan. Masalah QAP juga dikenal sebagai masalah optimasi kombinatorial yang mempunyai himpunan solusi yang terhingga. Secara prinsip solusi dari masalah optimasi kombinatorial bisa didapatkan hasil solusi dengan tepat namun waktu yang diperlukan  cukup  lama dalam  proses  perhitungan  sehingga  kurang  optimal.  Banyak penelitian  mengembangkan  beberapa  metode  yang  efisien  untuk  penyelesaian  QAP salah  satunya  adalah metaheurstik . Metaheuristik yang  dikembangkan  untuk  masalah QAP adalah algoritma Ant Colony Optimization [2]. ACO merupakan algoritma dengan mengambil  contoh  perilaku  semut  yang  bekerja  sama  untuk  mencari  makan.  Semut diketahui mampu untuk menemukan jalur terpendek dari  sarang mereka menuju ke sumber  makanan,  hal  ini  telah  diamati  bahwa  pada  saat  semut  berjalan  mereka meninggalkan  sejumlah  informasi  yang  disebut pheromone sebagai  komunikasi  tidak langsung dan juga pertukaran informasi antar semut. Pada ACO, pheromone digunakan untuk mencari solusi optimal dari perjalanan semut tersebut sehingga proses perjalanan dari  sarang  ketujuan  sumber  makanan  lebih  cepat  [3].  Penelitian  ini  fokus  untuk membahas  bagaimana  penggunaan  Algoritma Ant  Colony  Optimization (ACO)  pada penyelesaian Quadratic  Assignment  Problem dengan  ukuran  data  masalah  yang  lebih besar atau kompleks.

## 2.  Metode
Pada  penelitian  ini  data  yang  digunakan  berupa  data  fasilitas  lokasi  oleh  [7]  yang terdapat  dalam  referensi  QAP-Library  (QAPLIB),  dimana  data  ini  berupa  ukuran matriks yang diujicoba dalam suatu metode untuk mendapatkan solusi, salah satunya algoritma  ACO  dalam  permasalahan  QAP  [8].  Adapun  prosedur-prosedur  yang digunakan dalam penelitian ini adalah sebagai berikut:
1. Mengalikan  jumlahan  matriks  fasilitas  dan  jumlahan  matriks  lokasi  untuk mendapatkan matriks biaya penugasan
2. Penetapan  parameter  awal  dan  pengisian tabu  list untuk  memilih  fasilitas  lokasi dengan rumus Random Proportional Rule .
3. Menghitung biaya fungsi tujuan setelah tabu list penuh dengan persamaan (1) dan dicari nilai terkecil sebagai solusi terbaik.
4. Memperbaharui  matriks pheromone dengan  rumus Global  Pheromone  Updating  Rule , nilai matriks pheromone yang baru akan digunakan untuk penugasan selanjutnya.
5. Jika penugasan sama dengan maksimum penugasan maka penugasan telah berhenti dan mendapatkan solusi QAP. Apabila belum mendapatkan solusi maka kosongkan tabu list dan kembali lakukan langkah 2.
6. Membuat kesimpulan penelitian.

## 3.  Hasil dan Pembahasan
Pengumpulan data membahas tentang tahapan kuesioner untuk mengetahui presepsi mahasiswa  terhadap  dosen.  sedangkan  pada  bagian  pengolahan  data  membahas tentang tahapan  pengolahan data dari kuesioner dengan  menggunakan SPSS 25.
3.1. Ant Colony Optimization (ACO) untuk solusi Quadratic Assignment Problem
Dalam penyelesaian QAP dengan algoritma ACO terdapat fasilitas-fasilitas yang akan ditempatkan ke lokasi-lokasi tertentu untuk suatu penugasan dimana penempatan awal fasilitas  untuk lokasi akan dipilih secara acak kemudian untuk pemilihan fasilitas  ke lokasi  selanjutnya  akan  ditentukan  berdasarkan pheromone yang  dipengaruhi  oleh tetapan intensitas pheromone dan tetapan visibilitas pada persamaan (5), sehingga dari pemilihan  tersebut  akan  terbentuk  urutan  fasilitas-fasilitas  ke  lokasi-lokasi  dalam penugasan,  kemudian  urutan  fasilitas  ke  lokasi  tersebut  akan  di  hitung  total  biaya penugasan, selanjutnya akan dilakukan pembaruan pheromone dengan persamaan (6) untuk penugasan berikutnya.
Dalam  menyelesaikan Quadratic  Assignment  Problem dengan Ant  Colony  Optimization maka dilakukan langkah – langkah sebagai berikut :
Langkah 1 . Pengisian Matriks Biaya pada QAP
Pengisian matriks biaya pada QAP dengan mengalikan jumlahan matriks fasilitas dan jumlahan matriks lokasi. Matriks biaya dapat dinyatakan sebagai matriks 𝑛 𝑥 𝑛 berikut:
𝑪 = [ 𝑐 11 𝑐 12 … 𝑐 1𝑛 𝑐 21 𝑐 22 … 𝑐 2𝑛 ⋮ 𝑐 𝑛1 ⋮ 𝑐 𝑛2 ⋱ ⋮ … 𝑐 𝑛𝑛 ]
Matriks biaya dari fasilitas lokasi akan digunakan untuk memilih fasilitas ke lokasi yang layak dalam algoritma ACO.
Langkah 2 . Penetapan Parameter Awal dan Pengisian Tabu List
Pada  algoritma  ACO  dengan  rumus Ant  System akan  digunakan  nilai  parameter- parameter sebagai berikut:
a) Nilai 𝛼 : Tetapan pengendali intensitas pheromone atau jejak semut ( 𝛼 > 0 ) b) Nilai 𝛽 : Tetapan pengendali visibilitas ( 𝛽 > 0 )
c) Visibilitas antar penugasan (𝜂 𝑖𝑗 = 1 𝐶 𝑖𝑗 ) .
d) Nilai 𝜌 : Koefisien penguapan intensitas pheromone
e) 𝜏 𝑖𝑗 (t) : Intensitas pheromone . Nilai 𝜏 𝑖𝑗 akan diperbaharui pada setiap penugasan dari penugasan pertama sampai penugasan maksimum.
f) Maksimum penugasan: Batas penugasan yang dilakukan.
Pengisian Tabu list
Masing-masing semut secara acak akan memilih fasilitas ‘ i ’ yang ditugaskan ke lokasi ‘ j ’ dengan rumus Random Proportinal Rule pada persamaan (5) dimana probabilitas semut untuk menetapkan fasilitas ' i ' ke lokasi ' j ' pada penugasan ' t. '
𝑝 𝑖𝑗 (𝑡) = [𝜏 𝑖𝑗 (𝑡)] 𝛼 [ 1 𝐶 𝑖𝑗 ] 𝛽 ∑ [𝜏 𝑖𝑗 (𝑡)] 𝛼 [ 1 𝐶 𝑖𝑗 ] 𝛽 𝑗∈ s 𝑘 𝑝 𝑖𝑗 = [𝜏 11 ] 𝛼 .  [ 1 𝐶 11 ] 𝛽 [𝜏 11 ] 𝛼 .  [ 1 𝐶 11 ] 𝛽 + [𝜏 21 ] 𝛼 .  [ 1 𝐶 21 ] 𝛽 + [𝜏 31 ] 𝛼 .  [ 1 𝐶 31 ] 𝛽 + ⋯ + [𝜏 𝑛1 ] 𝛼 .  [ 1 𝐶 𝑛1 ] 𝛽 ⋮ 𝑝 𝑖𝑗 = [𝜏 𝑛1 ] 𝛼 .  [ 1 𝐶 𝑛1 ] 𝛽 [𝜏 𝑛1 ] 𝛼 .  [ 1 𝐶 𝑛1 ] 𝛽 + [𝜏 𝑛2 ] 𝛼 .  [ 1 𝐶 𝑛2 ] 𝛽 + [𝜏 𝑛3 ] 𝛼 .  [ 1 𝐶 𝑛3 ] 𝛽 + ⋯ + [𝜏 𝑛𝑛 ] 𝛼 .  [ 1 𝐶 𝑛𝑛 ] 𝛽
Langkah 3. Menghitung Nilai Fungsi Tujuan Selanjutnya  menghitung  nilai  fungsi  tujuan  tiap  semut  yang  didapatkan  dengan menggunakan  persamaan  (1)  pada  formula  QAP  dimana tabu  list yang  sudah didapatkan merupakan nilai  dari  lokasi  yang dipilih sebagai  penempatan fasilitas ke lokasi. Setelah menghitung semua nilai pada tabu list maka akan dipilih nilai terkecil dan disimpan sebagai solusi terbaik.
𝑧 = ∑ ∑ ∑ ∑ 𝑓 𝑖𝑟 𝑑 𝑗𝑠 𝑥 𝑖𝑗 𝑥 𝑟𝑠 𝑛 𝑠=1 𝑛 𝑟=1 𝑛 𝑗=1 𝑛 𝑖=1 𝑧 = 𝑓 11 𝑑 11 𝑥 11 𝑥 11 + 𝑓 12 𝑑 12 𝑥 12 𝑥 12 + ⋯ + 𝑓 1𝑛 𝑑 1𝑛 𝑥 1𝑛 𝑥 1𝑛 + 𝑓 21 𝑑 21 𝑥 21 𝑥 21 + 𝑓 22 𝑑 22 𝑥 22 𝑥 22 + ⋯ + 𝑓 2𝑛 𝑑 2𝑛 𝑥 2𝑛 𝑥 2𝑛 + 𝑓 𝑛1 𝑑 𝑛1 𝑥 𝑛1 𝑥 𝑛1 + 𝑓 𝑛2 𝑑 𝑛2 𝑥 𝑛2 𝑥 𝑛2 + ⋯ + 𝑓 𝑛𝑛 𝑑 𝑛𝑛 𝑥 𝑛𝑛 𝑥 𝑛𝑛
Langkah 4. Memperbaharui Matriks Pheromone
Jika solusi terbaik sudah dipilih maka akan diperbaharui matriks pheromone baru untuk penugasan selanjutnya dengan rumus Global Pheromone Updating pada persamaan (6) dengan terlebih dahulu menentukan nilai delta ∆𝜏 𝑖𝑗 𝑘 yaitu 𝑄 𝑧 𝑘 , dimana 𝑧 𝑘 merupakan nilai fungsi tujuan yang didapatkan oleh semut ke k dengan memperhatikan fasilitas lokasi yang sudah dipilih untuk mendapatkan nilai pheromone baru sebagai berikut :
𝜏 𝑖𝑗 (𝑡+1) = 𝜌. 𝜏 𝑖𝑗 (𝑡) + ∑ ∆𝜏 𝑖𝑗 𝑘 𝑚 𝑘=1 𝜏 𝑖𝑗 (𝑡+1) = 𝜌. 𝜏 𝑖𝑗 (𝑡) + { 𝑄 𝑧 1 + 𝑄 𝑧 2 + ⋯ + 𝑄 𝑧 𝑛 }
Dengan 𝜏 𝑖𝑗 (𝑡) adalah pheromone awal yang sudah ditetapkan sebelumnya.
Langkah 5. Pengosongan tabu list dan ulangi langkah 2 hingga maksimum penugasan mencapai batas tertentu
Tabu list dikosongkan dan akan diisi kembali setelah mendapatkan pheromone baru pada penugasan  selanjutnya  sampai  nilai  biaya  tetap,  jika  maksimum  penugasan  belum mencapai nilai yang tetap atau stabil maka ulangi langkah berikut dengan mengulang Langkah 2 dengan menggunakan pheromone yang telah diperbahrui.

## 3.2.  Contoh Kasus dan Pembahasan
Penyelesaian QAP menggunakan algoritma ACO  dengan contoh kasus QAP diambil dari data Nugent dalam referensi QAP-Library (QAPLIB) untuk data fasilitas lokasi [7]. Fasilitas  lokasi  yang  digunakan  berupa  matriks  berukuran 8  ×  8 ,  dimana  untuk pengujian kasus ini didapatkan matriks biaya yaitu
𝐶 = [ 288 224 160 368 288
320 304 512
216 168 120 276 216 240 228 384 216 168 120 276 216 240 228 384 288 224 160 368 288 320 304 512 288 224 160 368 288 320 304 512 216 168 120 276 216 240 228 384 216 168 120 276 216 240 228 384 288 224 160 368 288 320 304 512]
Setelah  didapatkan  matriks  biaya  penugasan  kemudian  lakukan  langkah  selanjutnya dengan  parameter  tetapan  yaitu  dengan  5  semut, 𝛼 dan 𝛽 = 1 , 𝜌 = 0,9 , 𝑄 = 10 ,  dan maksimum  penugasan  =  100,  sehingga  untuk  contoh  kasus  dalam  peneltian  ini didapatkan solusi biaya dan penempatan fasilitas lokasi pada Gambar 1.
Gambar 1. Solusi biaya penugasan ukuran 8 fasilitas dan 8 lokasi
Berdasarkan  proses  penugasan  pada  Gambar  1  menujukkan  hasil  solusi  yang didapatkan pada penugasan adalah stabil dengan solusi nilai terakhir pada penugasan ke 51 sampai maksimum penugasan ke 100 yaitu 118 dengan menempatkan fasilitas ke lokasi yang ditunjukkan pada Tabel 1.
0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 penugasan so lu si b ia ya solusi ACO-QAP

## Tabel 1. Fasilitas dan lokasi matriks C
(fasilitas, lokasi)  (5,1) (6,2) (1,3) (3,4) (4,5) (8,6) (7,7) (2,8)
Label  pada  Tabel  1  diatas  menunjukkan  penempatan  fasilitas  lokasi  yaitu  fasilitas  5 berada pada lokasi 1, fasilitas 6 pada lokasi 2, fasilitas 1 ke lokasi 3, fasilitas 3 ke lokasi 4, fasilitas 4 ke lokasi 5, fasilitas 8 ke lokasi 6, fasilitas 7 ke lokasi 7 dan fasilitas 2 ke lokasi 8.

## 3.3.   Perbandingan Solusi QAPLIB dan Algoritma ACO
Pada  pengujian  data  berdasarkan  matriks  ukuran  yang  terdapat  pada  QAPLIB  yang diuji cobakan dengan algoritma ACO untuk data Nugent selain matriks ukuran 8 maka diperoleh hasil yang ditunjukkan pada Tabel 2.
Tabel 2. Hasil perbandingan solusi biaya QAPLIB dan ACO-QAP
Perbandingan  yang  ditunjukkan  pada  Tabel  2  memberikan  informasi  bahwa  solusi menggunakan algoritma ACO bisa mendapatkan solusi minimal dari hasil solusi pada QAPLIB  melalui  data Nugent .  Hal  ini  menunjukkan  bahwa  algoritma  ACO  dengan rumus Ant  System dapat  diterapkan  untuk  menyelesaikan  permasalahan Quadratic Assignment Problem (QAP).

## 4.  Kesimpulan
Alogiritma Ant Colony Optimization menjadi salah satu algoritma alternatif yang dapat diterapkan  pada  penyelesaian Quadratic  Assignment  Problem dengan  ukuran  data masalah  yang  lebih  besar  atau  kompleks.  Algoritma Ant  Colony  Optimization menghasilkan solusi terbaik dengan waktu yang cukup singkat.

## Referensi
[1]  Hillier,  S.F.,  &  Lieberman,  2004,  Introduction  to  Operations  Research,  Eighth Edition, New York: Mc Graw-Hil
[2]  Erlanda,  C.,  1998,  The  Quadratic  Assignment  Problem,  Springer  Science  and Business Media Dordrecht
[3]  Dorigo, M. & Stutzle, T., 2004, Ant Colony Optimization, Massachusetts Institute of Technology
[4]  Hahn, P. & Grant, T., 1998, Lower Bounds for the Quadratic Assignment Problem Based Upon a Dual Formulation, Operation Research, Vol. 46, No. 6
[5]  Bidyarthy,  S.A.  &  Vivek,  G.,  2013,  Ant  Colony  Optimization  for  Quadratic Assignment  Problem  and  School  Bus  Routing  Problem.  Departement  of Mathematics Indian Institute of Technology Guwahati
Percobaan Nugent n x n QAPLIB ACO-QAP 12 x 12 578 345 16 x 16 1610 1035 30 x 30 6124 3950
[6]  Davendra, D. & Zelinka, I., 2009, Optimization of Quadratic Assignment Problem Using Self Organising Migrating Algorithm, Computing and Informatics, Vol. 28: 1001 – 1012
[7]  Christopher,  N.E,  1967,  An  Experimental  Comparison  of  Tech-Niques  for  the Assignment of Facilities to Locations INFORMS
[8]  Axel,  N.,  2014,  Some  Reformulations  for  the  Quadratic  Assignment  Problem,
Department of Chemical Engineering Åbo Akademi University http://www.qaplib/inst.html