Penyelesaian {0,1}-Knapsack Problem dengan Algoritma Soccer League Competition

Article Sidebar

PDF
Published Feb 1, 2017

Main Article Content

Muji Prasetyo Iryanto
Universitas Indonesia
Sri Mardiyati
Universitas Indonesia

Abstract

Knapsack Problem (KP) adalah masalah penempatan item (barang) ke dalam suatu tempat (biasa disebut Knapsack) yang mempunyai kapasitas tertentu, dimana setiap item memiliki berat dan nilai, sehingga total berat dari item-item yang ditempatkan tidak melebihi kapasitas Knapsack dan nilai yang didapatkan maksimum. {0,1}-Knapsack Problem ({0,1}-KP) adalah kasus khusus dari KP dimana setiap item hanya tersedia 1 unit, sehingga keputusannya adalah untuk memasukkan item tersebut ke dalam Knapsack (x=1) atau tidak (x=0). Telah banyak metode yang dikembangkan untuk menyelesaikan {0,1}-KP, salah satunya adalah Algoritma Soccer League Competition (SLC). SLC adalah algoritma ­meta-heuristic yang terinspirasi dari kompetisi pada liga sepakbola. Kompetisi antar tim untuk menjadi juara dan kompetisi internal antar pemain untuk memperoleh kesempatan bermain disimulasikan untuk mencari nilai optimum dari {0,1}-KP. Hasil simulasi pada beberapa permasalahan {0,1}-KP yang telah menjadi benchmark menunjukkan bahwa SLC dapat digunakan untuk menyelesaikan {0,1}-KP, yang mana melampaui hasil dari algoritma lain.

Article Details

How to Cite
Iryanto, M. P., & Mardiyati, S. (2017). Penyelesaian {0,1}-Knapsack Problem dengan Algoritma Soccer League Competition. PRISMA, Prosiding Seminar Nasional Matematika, 688-700. Retrieved from https://journal.unnes.ac.id/sju/prisma/article/view/21531
Issue
2017: Prosiding Seminar Nasional Matematika X 2016
Section
Articles

References

Kellerer, H., Pferschy, U., & Pisinger, D. 2004. Knapsack Problems. New York: Springer-Verlag Berlin Heidelberg.
Li, Z., & Li, N. 2009. A novel multi-mutation binary particle swarm optimization for 0/1 knapsack problem. Chinese Control and Decision Conference (pp. 3090-3095). New Jersey: IEEE Press.
Lin, F.-T. (2008, February 16). Solving the knapsack problem with imprecise weight coefficients using genetic algorithms. European Journal of Operational Research, 185(1), 133-145.
Liu, Y., & Liu, C. 2009. A Schema-Guiding Evolutionary Algorithm for 0-1 Knapsack Problem. International Association of Computer Science and Information Technology - Spring Conference (pp. 160-164). IEEE.
Martello, S., & Toth, P. 1990. Knapsack Problems : Algorithms and Computer Implementations. West Sussex: John Wiley & Sons Ltd.
Moosavian, N. 2015. Soccer league competition algorithm for solving knapsack problems. Swarm and Evolutionary Computation, 20, 14-22.
Pisinger, D. 1995. Algorithms for Knapsack Problems. Copenhagen: Dept. of Computer Science, University of Copenhagen.
Shi, H. 2006. Solution to 0/1 Knapsack Problem Based on Improved Ant Colony Algorithm. International Conference on Information Acquisition (pp. 1062-1066). Shandong: IEE.
Taha, H. A. 2007. Operations Research : An Introduction (8 ed.). New Jersey: Pearson Education, Inc.
Winston, W. L. 2003. Operations Research: Applications and Algorithms. Kentucky: Cengage Learning.
Zou, D., Gao, L., Li, S., & Wu, J. 2011. Solution to 0/1 Knapsack Problem by a Novel Global Harmony Search Algorithm. Applied Soft Computing, 11(2), 1556-1564.