1
Penyelesaian Multiobjective Resource Allocation Problem (MORAP) dengan Menggunakan Algoritma Artificial Bee Colony (ABC) Catherine Febriyanti S., Miswanto, Herry Suprajitno Departemen Matematika, Fakultas Sains dan Teknologi, Universitas Airlangga Kampus C, Jl. Mulyorejo, Surabaya
[email protected] Abstract. Multiobjective resource allocation problem (MORAP) is the process of allocating resources among the various projects or business units to meet the expected objectives. Resources may be manpower, assets, raw materials, capital or anything else in limited supply which can be used to accomplish the goals. Artificial Bee Colony (ABC) algorithm is an algorithm that adopts the way bee colonies in search of food sources. This algorithm process begins with the initialization parameters, generate solution, calculate the value of the objective function, perform the update nondominated set of solution, find neighborhood from the solution, compare solutions, perform trial limit update and update update nondominated set of solution, determine solutions for each one onlooker bee using roulette wheel selection, search a new solution with neighborhood search, compare solutions, perform trial limit update and update update nondominated set of solution, check-out the solution and the process continues until the maximum iteration. The data used is data 6 allocation of resource at 4 activities, 10 allocation of resource at 4 activities, and 12 allocation of resources at 4 activities and completed with the Java programming language NetBeans IDE 7.2. MORAP settlement proceeds by using the ABC algorithm is obtained for is data allocation of 6 resource at 4 activities obtained 3 nondominated solution. As for the data allocation of 10 resource at 4 activities obtained 7 nondominated solution. Then for the data allocation of 12 resources at 4 activities obtained 20 nondominated solution. Keywords : Artificial Bee Colony Algorithm, Multiobjective Resource Allocation Problem
1. Pendahuluan Masalah optimasi multi tujuan (multiobjective) telah mengalami peningkatan sebagai bahan penelitian dengan berbagai latar belakang sejak awal tahun 1960. Dalam masalah optimasi multiobjective, sejumlah fungsi tujuan perlu dioptimalkan secara bersamaan akan tetapi tidak selalu ada solusi yang terbaik karena ketaksebandingan dan konflik diantara tujuan tersebut. Sebuah solusi mungkin menjadi yang terbaik dalam satu tujuan tetapi mungkin juga menjadi yang terburuk di fungsi tujuan yang lain. Oleh karena itu, biasanya ada satu himpunan solusi untuk kasus multiple-objective yang tidak bisa begitu saja dibandingkan satu sama
Jurnal Matematika
2
lain. Untuk solusi tersebut, yang disebut solusi tidak didominasi (nondominated solutions), tidak ada perbaikan yang dapat dilakukan pada semua fungsi tujuan tanpa mengorbankan setidaknya salah satu fungsi tujuan lainnya [2]. Resource Allocation Problem (RAP) adalah proses mengalokasikan sumber daya di antara berbagai kegiatan atau unit bisnis. RAP merupakan persoalan untuk menemukan alokasi optimal dari jumlah terbatas sumber daya pada sejumlah pekerjaan dan mengoptimalkan tujuan yang diinginkan. Sumber daya dapat diasumsikan sebagai orang, aset, bahan, atau modal yang dapat digunakan untuk mencapai tujuan [4]. Multiobjective Resource Allocation Problem (MORAP) membahas masalah untuk menyelesaikan beberapa tujuan yang diharapkan dengan mengalokasikan jumlah terbatas sumber daya pada sejumlah kegiatan. [1] menyelesaikan masalah MORAP menggunakan algoritma Ant Colony Optimization (ACO) dan membandingkannya dengan hybrid Genetic Algorithm (hGA) [4], diperoleh hasil bahwa hasil penghitungan dengan ACO dapat mengungguli 50% solusi nondominated dari hasil hGA. Artificial Bee Colony (ABC) merupakan algoritma yang diperkenalkan pertama kali oleh Karaboga pada tahun 2005. ABC mengadopsi cara koloni lebah dalam pencarian sumber makanan. Dalam metode ini terdapat 3 koloni lebah yaitu employed bee, onlooker bee, dan scout bee. Dimana masing-masing kelompok mempunyai tugas yang berbeda dalam mencari sumber makanan. Karena algoritma ini memiliki sistem pembagian kerja yang baik maka kerja sama yang dibentuk oleh koloni lebah tersebut diyakini lebih efisien dari algoritma lain yang bekerja secara berurutan tanpa spesialisasi. Dalam paper ini, masalah Multiobjective Resource Allocation Problem (MORAP) akan diselesaikan menggunakan algoritma Artificial Bee Colony (ABC).
2. Multiobjective Resource Allocation Problem MORAP membahas masalah untuk menemukan tujuan yang diharapkan dengan mengalokasikan jumlah terbatas sumber daya pada sejumlah kegiatan dengan lebih dari satu fungsi tujuan. Tujuan yang dimaksud (misalnya, meminimalkan biaya, dan memaksimalkan efisiensi) biasanya didorong oleh kebutuhan tertentu di masa mendatang. Menurut [4], MORAP berikut : Jurnal Matematika
untuk dua fungsi tujuan tersebut dapat ditulis sebagai
3
Meminimalkan z = Memaksimalkan z =
, ,
Fungsi Kendala : ≤ =1
, ∀,
= 0 atau 1 ∀ , = 1, 2, … , % dan = 0, 1, 2, … , 1, jika sejumlah pekerja yang dialokasikan untuk pekerjaan ,/ =' 0, yang lain Diasumsikan terdapat N pekerjaan dan M pekerja (sumber daya). adalah biaya adalah akomodasi untuk pekerjaan i ketika sejumlah j pekerja dialokasikan, dan efisiensi untuk pekerjaan i ketika sejumlah j pekerja dialokasikan.
3. Algoritma Artificial Bee Colony Algoritma Artificial Bee Colony diperkenalkan pertama kali oleh Karaboga pada tahun 2005. Algoritma ini mengadopsi cara koloni lebah dalam pencarian sumber makanan. Pada [3], koloni lebah terdiri dari tiga jenis lebah, yaitu: employed bees, onlooker bees, dan scout. Setengah pertama dari jumlah koloni adalah jumlah dari employed bees dan setengah kedua adalah jumlah dari onlooker. Untuk setiap food source hanya ada satu employed bee. Dengan kata lain, jumlah employed bee sama dengan jumlah food source. Employed bee yang meninggalkan food source akan menjadi scout. Pada algoritma ABC, calon solusi dan nilai fitness direpresentasikan sebagai food source dan jumlah nektar. Langkah-langkah pada algoritma ABC adalah sebagai berikut: 1. 2.
Inisialisasi parameter. Membangkitkan solusi awal Solusi dibangkitkan secara random dengan jumlah solusi yang dibangkitkan berupa vekor dengan dimensi sebanyak jumlah parameter optimasi dari
Jurnal Matematika
4
3. 4. 5.
6.
permasalahannya. Jumlah solusi yang dibangkitkan. sebanyak jumlah dari employed bee atau onlooker bee. Menghitung nilai fitness. Mencari solusi baru berdasarkan neighbourhood. Menghitung nilai fitness solusi baru dan membandingkan solusi Jika nilai fitness baru lebih bagus maka solusi baru diingat dan melupakan solusi lama. Menghitung probabilitas solusi berdasarkan nilai fitness Onlooker bee memilih solusi berdasarkan probabilitas dari nilai fitness solusi. menghitung probabilitas menggunakan rumus: Pi =
zi NF
∑z i =1
7. 8. 9. 10.
i
Dengan: 0 : probabilitas calon solusi ke1 : nilai fitness keNF : jumlah calon solusi Onlookerbee menentukan solusi baru berdasarkan neighbourhood dari calon solusi yang terpilih. Menghitung nilai fitness solusi baru dan membandingkan solusi. Mengingat solusi terbaik. Menentukan solusi yang habis jika posisi calon solusi tidak berubah lebih lanjut melalui batas yang sudah ditentukan maka calon solusi diasumsikan habis. Batas dari calon solusi habis dihitung dengan cara: 2 = %3 × 5, Dengan: 2 = Limit habisdarisolusi %3 = Jumlah food source D = Jumlah pekerjaan
4. MORAP dengan Algoritma ABC Dalam menyelesaikan kasus MORAP dengan menggunakan algoritma ABC, terdapat langkah-langkah sebagai berikut : Langkah 1. Inisialisasi parameter Dalam algoritma ABC terdapat parameter sebagai inisialisasi awal. Paramater tersebut adalah jumlah populasi bee Jurnal Matematika
5
Langkah 2.
Langkah 3. Langkah 4.
Langkah 5.
Langkah 6.
Langkah 7.
Langkah 8. Langkah 9.
(CS), jumlah pekerjaan (N), jumlah pekerja (M), jumlah food source (NF), jumlah iterasi (MI). Menurut [6] terdapat parameter limit for abandonment (L) yaitu parameter yang menentukan batas dari food source dapat dinyatakan habis. Membangkitkan bilangan random sebagai calon solusi Calon solusi yang dibangkitkan menggunakan pengkodean nilai dengan bilangan integer non negatif. Menghitung nilai dari masing-masing fungsi tujuan Update himpunan penyelesaian nondominated Menyimpan food source yang merupakan nondominated solution. Setiap employed bee mencari solusi baru berdasarkan neighborhood Pada tahap ini digunakan modifikasi dari heuristic mutation untuk mencari neighborhood dari setiap employed bee. Menghitung nilai fitness solusi baru dan membandingkan solusi Jika nilai fitness baru lebih bagus maka calon solusi baru diingat dan melupakan calon solusi yang lama. Update trial limit Jika solusi lama tidak digantikan oleh solusi baru maka trial limit dari solusi lama akan ditambah satu. Update himpunan penyelesaian nondominated Menghitung probabilitas calon solusi berdasarkan nilai fitness Onlooker bee memilih calon solusi berdasarkan probabilitas dari nilai fitness calon solusi. Menghitung probabilitas menggunakan rumus: 78 6 = ∑?
Langkah 10.
Langkah 11.
;
Dengan: 0 : probabilitas calon solusi ke@A : nilai fitness keSN : jumlah calon solusi Onlooker bee menentukan calon solusi baru berdasarkan neighborhood dari calon solusi yang telah dipilih Pencarian berdasarkan neighborhood dari calon solusi yang telah dipilih sebelumnya. Penentuan calon solusi baru menggunakan proses inversion mutation. Menghitung nilai fitness solusi baru dan membandingkan solusi Jika nilai fitness baru lebih bagus maka calon solusi baru diingat dan melupakan calon solusi yang lama.
Jurnal Matematika
6
Langkah 12. Langkah 13. Langkah 14.
Update trial limit Update himpunan penyelesaian nondominated Menentukan calon solusi yang habis Menurut Stanarevic dkk (2011), jika posisi calon solusi tidak berubah lebih lanjut melalui batas yang sudah ditentukan maka calon solusi diasumsikan habis. Batas dari calon solusi habis dihitung dengan cara: 2 = %3 × %; Dengan : %3 = jumlah @CCD ECFG , % = jumlah pekerjaan 2 = limit
5. Hasil dan Pembahasan Pada penelitian sebelumnya, penyelesaian MORAP telah dilakukan dengan menggunakan beberapa algoritma lain yaitu Genetic Algorithm (GA) [5] untuk pengalokasian 6 sumber daya pada 4 kegiatan, hybrid Genetic Algorithm (hGA) [4] dan Ant Colony Optimization (ACO) [1] untuk pengalokasian 10 sumber daya pada 4 kegiatan. Hasil perbandingan algoritma-algoritma tersebut dengan penyelesaian menggunakan algoritma ABC disajikan pada Tabel 1.
Jurnal Matematika
7
Tabel 1 Hasil perbandingan solusi dengan algoritma lain Data
Algoritma
Jumlah solusi nondominated
GA
3
ABC
3
hGA
7
ACO
4
ABC
7
6 Sumber Daya pada 4 Kegiatan
10 Sumber Daya pada 4 Kegiatan
Food Source 1 2 2 2 2 1 3 0 3 3 1 1 0 3 1 3 1 1 1 3 3 2 3 1
2 2 3 3 2 2 2 2 2 1 1 1 1 2 2 2 1 2 1 1 2 2 2 2
1 1 1 1 1 1 1 6 5 6 6 5 6 1 6 0 6 6 6 6 1 6 0 6
2 1 0 0 1 2 4 2 0 0 2 3 3 3 0 0 1 1 2 0 3 0 0 0
z1
z2
270 275 280 280 275 270 201 197 173 164 212 215 191 175 152 150 202 184 212 164 175 160 150 152
120 126 129 129 126 120 229 210 182 175 241 235 209 222 180 105 234 240 241 187 222 185 105 180
Dari Tabel 1 untuk data 6 sumber daya pada 4 kegiatan jumlah solusi yang dihasilkan algoritma GA dan algoritma ABC memiliki hasil yang sama. Namun pada penyelesaian dengan menggunakan algoritma GA, hasil tersebut diperoleh setelah 60 generasi dengan jumlah population size sebanyak 5. Sedangkan untuk penyelesaian dengan menggunakan algoritma ABC, hasil tersebut diperoleh pada 10 iterasi dengan jumlah populasi bee sebanyak 20. Hasil perbandingan untuk data 10 sumber daya pada 4 kegiatan jumlah solusi nondominated yang dihasilkan oleh hGA dan ABC memiliki jumlah yang sama, tetapi nilai z1 dan z2 yang dihasilkan berbeda. Ketika dibandingkan antara solusi dengan menggunakan hGA dan ABC, diperoleh hasil bahwa dari 7 solusi nondominated yang dihasilkan oleh ABC mampu mendominasi 6 solusi nondominated yang dihasilkan oleh hGA. Sedangkan hasil perbandingan ACO dengan ABC, diperoleh hasil bahwa dari 7 solusi nondominated yang dihasilkan Jurnal Matematika
8
oleh ABC hanya mampu mendominasi 1 solusi nondominated yang dihasilkan oleh ACO dan 3 solusi nondominated dari ACO yang lainnya sama seperti yang dihasilkan oleh ABC. Berdasarkan hasil perbandingan diatas, hasil penyelesaian MORAP dengan menggunakan algoritma ABC mampu mengungguli hasil penyelesaian dengan algoritma lainnya pada jumlah iterasi atau jumlah solusi nondominated yang dihasilkan.
6. Kesimpulan Dengan menggunakan parameter yang bervariasi didapatkan jumlah solusi nondominated yang berbeda. Semakin besar jumlah populasi bee dan jumlah iterasi maka jumlah solusi nondominated yang dihasilkan lebih banyak. 7. Daftar Pustaka 1. Chaharsooghi, S.K. and Kermani, A.H.M., 2008, An Effective Ant Colony Optimization Algoritm (ACO) for Multi-objective Resource Allocation Problem (MORAP), Applied Mathematics and Computation 200 167-177. 2. Fonseca, C.M. and Fleming, P.J., 1995, An overview of evolutionary algorithms in multi-objective optimization, Evolutionary Computation 3 (1). 3. Karaboga, D. and Basturk, B., 2007, On the Performance of Artificial Bee Colony (ABC) Algorithm, Erciyes University, Department of Computer Engineering, Melikgazi, 38039 Kayseri, Turkey. 4. Lin, C. and Gen, M., 2007, Multiobjective Resource Allocation Problem by Multistage Decision-based Hybrid Genetic Algorithm, Applied Mathematics and Computation 187 574-583. 5. Osman, M.S., Abo-Sinna, M.A., and Mousa, A.A., 2005, An Effective Genetic Algorithm Approach to Multi-objective Resource Allocation Problems, Applied Mathematics and Computation 163 755-768. 6. Stanarevic, N., Tuba, M., and Bacanin, N., 2011, Modified Artificial Bee Colony Algorithm for Constrained Problem Optimization, Faculty of Computer Science, Megatrend University, Belgrade, Serbia.
Jurnal Matematika
