Algoritme Migrating Birds Optimization dan Algoritme Particle Swarm Optimization: Penyelesaian Masalah Knapsack 0-1

Bib Paruhum Silalahi; Mohamad Novanto; Prapto Tri Supriyo

doi:10.21831/pythagoras.v17i1.35660

Algoritme Migrating Birds Optimization dan Algoritme Particle Swarm Optimization: Penyelesaian Masalah Knapsack 0-1

Bib Paruhum Silalahi, Departemen Matematika, IPB University, Indonesia
Mohamad Novanto, Departemen Matematika, IPB University, Indonesia
Prapto Tri Supriyo, Departemen Matematika, IPB University, Indonesia

10.21831/pythagoras.v17i1.35660

Abstract

Permasalahan knapsack merupakan salah satu masalah optimisasi. Masalah knapsack merupakan suatu permasalahan bagaimana memilih objek dari beberapa objek yang akan dimasukkan ke media penyimpanan dengan masing-masing objek memiliki bobot dan total bobot dari objek yang dipilih tidak boleh melebihi kapasitas media penyimpanannya, sehingga diperoleh nilai yang maksimal. Ketika objek yang dimasukkan ke dalam media penyimpanan bersifat harus dimasukkan semua atau tidak sama sekali, permasalahan ini dikenal dengan nama knapsack 0-1. Salah satu metode penyelesaian masalah knapsack 0-1 adalah dengan menggunakan metode meta-heuristic. Terdapat beberapa metode meta-heuristic seperti algoritma migrating birds optimization dan particle swarm optimization. Paper ini membahas bagaimana algoritma migrating birds optimization dan particle swarm optimization digunakan dalam menyelesaikan permasalahan knapsack 0-1. Kemudian dilakukan perbandingan kinerja kedua algoritma tersebut berdasarkan nilai fungsi tujuan untuk beberapa studi kasus. Berdasarkan hasil penelitian ini algoritme migrating birds optimization mempunyai nilai hasil fungsi objektif yang lebih baik dibandingkan dengan algoritma particle swarm optimization.

Migrating Birds Optimization Algorithm and Particle Swarm Optimization Algorithm: Knapsack problem solving 0-1

Abstract

The knapsack problem is one of the optimization problems. The knapsack problem is a problem of how to select objects from several objects to be inserted into the storage with each object having a weight and the total weight of the selected object must not exceed the capacity of the storage so that the maximum value is obtained. When objects that are inserted into the storage have the character of having to be included all or nothing, this problem is known as the 0-1 knapsack. One of the methods of solving the 0-1 knapsack problem is by using the meta-heuristic method. There are several meta-heuristic methods such as the migrating birds optimization algorithm and particle swarm optimization. This paper discusses how migrating birds optimization and particle swarm optimization algorithms are used to solve the 0-1 knapsack problem. Then the performance of the two algorithms is compared based on the objective function values for several case studies. Based on the results of this study, the migrating birds optimization algorithm has better objective function values than the particle swarm optimization algorithm.

Keywords

Masalah knapsack; metode meta-heuristic; migrating birds optimization; optimisasi; particle swarm optimization

Full Text:

PDF

References

Bhattacharjee, K. K., & Sarmah, S. P. (2014). Shuffled frog leaping algorithm and its application to 0/1 knapsack problem. Applied Soft Computing, 19, 252–263. https://doi.org/10.1016/j.asoc.2014.02.010

Bisilisin, F. Y., Herdiyeni, Y., & Silalahi, B. P. (2017). Optimasi K-Means Clustering Menggunakan Particle Swarm Optimization pada Sistem Identifikasi Tumbuhan Obat Berbasis Citra. Jurnal Ilmu Komputer Dan Agri-Informatika. https://doi.org/10.29244/jika.3.1.37-46

Chih, M., Lin, C.-J., Chern, M.-S., & Ou, T.-Y. (2014). Particle swarm optimization with time-varying acceleration coefficients for the multidimensional knapsack problem. Applied Mathematical Modelling, 38(4), 1338–1350. https://doi.org/10.1016/j.apm.2013.08.009

Duman, E., Uysal, M., & Alkaya, A. F. (2012). Migrating Birds Optimization: A new metaheuristic approach and its performance on quadratic assignment problem. Information Sciences. https://doi.org/10.1016/j.ins.2012.06.032

Iryanto, M. P., & Mardiyati, S. (2015). Penyelesaian { 0 , 1 } - Knapsack Problem dengan Algoritma Soccer League Competition. PRISMA, Prosiding Seminar Nasional …, 688–700. https://journal.unnes.ac.id/sju/index.php/prisma/article/view/21531

Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Knapsack Problems. In Knapsack Problems. https://doi.org/10.1007/978-3-540-24777-7

Lalang, D., Silalahi, B. P., & Bukhari, F. (2018). Vehicle Routing Problem Time Windows Dengan Pengemudi Sesekali. Journal of Mathematics and Its Applications, 17(2), 87. https://doi.org/10.29244/jmap.17.2.87-99

Liang, Y., Liu, L., Wang, D., & Wu, R. (2010). Optimizing particle swarm optimization to solve knapsack problem. Communications in Computer and Information Science. https://doi.org/10.1007/978-3-642-16336-4_58

Making, S. R. M., Silalahi, B. P., & Bukhari, F. (2018). Multi Depot Vehicle Routing Problem dengan Pengemudi Sesekali. Journal of Mathematics and Its Applications, 17(1), 75. https://doi.org/10.29244/jmap.17.1.75-86

Mayyani, H., Silalahi, B. P., & Aman, A. (2017). Frequency Determination of Bus Rapid Transit ( BRT ) Applied on Service System of Trans Mataram Metro Bus to Minimize the Operational Cost. International Journal of Engineering and Management Research, 7(6), 134–140. https://www.ijemr.net/DOC/FrequencyDeterminationOfBusRapidTransitBRTAppliedOnServiceSystemOfTransMataramMetroBusToMinimizeTheOperationalCost.pdf

Silalahi, B. P. (2019). Evaluation of interior-point method in Scilab. IOP Conference Series: Earth and Environmental Science, 012040. https://iopscience.iop.org/article/10.1088/1755-1315/299/1/012040/pdf

Silalahi, B. P., Bukhari, F., Aman, A., Khatizah, E., & Fahlevi, N. A. (2019). Comparison of Interior Point Method Execution Time in Solving Linear Optimization Problems using Mathematica and Scilab. International Journal of Statistics & Economics, 20(4), 74–81. http://www.ceser.in/ceserp/index.php/bse/article/view/6196

Silalahi, B. P., Fathiah, N., & Supriyo, P. T. (2019). Use of Ant Colony Optimization Algorithm for Determining Traveling Salesman Problem Routes. Jurnal Matematika “MANTIK,” 5(2), 100–111. https://doi.org/10.15642/mantik.2019.5.2.100-111

Silalahi, B. P., Fatihin, K., Supriyo, P. T., & Guritman, S. (2020). Algoritme Sweep dan Particle Swarm Optimization dalam Optimisasi Rute Kendaraan dengan Kapasitas. Jurnal Matematika Integratif. https://doi.org/10.24198/jmi.v16.n1.27474.29-40

Silalahi, B. P., Pertiwi, S. E., Mayyani, H., & Aliatiningtyas, N. (2020). Aplikasi Zero-One Goal Programming Dalam Masalah Pemilihan Proyek Pemasaran. BAREKENG: Jurnal Ilmu Matematika Dan Terapan, 14(3), 435–446. https://doi.org/10.30598/barekengvol14iss3pp435-446

Singh, R. P. (2011). Solving 0-1 Knapsack problem using Genetic Algorithms. 2011 IEEE 3rd International Conference on Communication Software and Networks, ICCSN 2011. https://doi.org/10.1109/ICCSN.2011.6013975

Ulker, E., & Tongur, V. (2017). Migrating birds optimization (MBO) algorithm to solve knapsack problem. Procedia Computer Science. https://doi.org/10.1016/j.procs.2017.06.012

Wihartiko, F. D., Buono, A., & Silalahi, B. P. (2017). Integer programming model for optimizing bus timetable using genetic algorithm. IOP Conference Series: Materials Science and Engineering. https://doi.org/10.1088/1757-899X/166/1/012016

Zhang, M., Tan, Y., Zhu, J., Chen, Y., & Chen, Z. (2020). A competitive and cooperative Migrating Birds Optimization algorithm for vary-sized batch splitting scheduling problem of flexible Job-Shop with setup time. Simulation Modelling Practice and Theory. https://doi.org/10.1016/j.simpat.2019.102065

Zou, D., Gao, L., Li, S., & Wu, J. (2011). Solving 0-1 knapsack problem by a novel global harmony search algorithm. Applied Soft Computing Journal. https://doi.org/10.1016/j.asoc.2010.07.019

Zouache, D., Moussaoui, A., & Ben Abdelaziz, F. (2018). A cooperative swarm intelligence algorithm for multi-objective discrete optimization with application to the knapsack problem. European Journal of Operational Research. https://doi.org/10.1016/j.ejor.2017.06.058

DOI: https://doi.org/10.21831/pythagoras.v17i1.35660