ALGORITMA BINARY ANT SYSTEM UNTUK MASALAH KNAPSACK MULTIDIMENSI

BAGUS GILANG R, Dwi Ertiningsih, S.Si., M.Si.

2019 | Skripsi | S1 MATEMATIKA

Multidimentional Knapsack Problem (MKP) merupakan suatu permasalahan optimisasi pada pengalokasian sejumlah barang yang memiliki bobot dan nilai barang (pendapatan) ke dalam sejumlah knapsack dengan kapasitas tertentu sehingga jumlah bobot dari barang tidak melebihi kapasitas knapsack. Pemilihan jumlah barang ke dalam sejumlah knapsack tersebut membutuhkan suatu metode tertentu yang dapat digunakan untuk menyelesaikan permasalahan optimisasi kombinatorik. Pada skripsi ini digunakan pendekatan algoritma Binary Ant System (BAS) yang merupakan modifikasi dari Ant Colony Optimization (ACO) untuk menyelesaikan permasalahan Multidimentional Knapsack Problem (MKP). Algoritma (ACO) adalah suatu algoritma yang mengadopsi perilaku sejumlah semut yang bekerja sama dan berkomunikasi secara tidak langsung saat mencari sumber makanannya. Komunikasi yang digunakan adalah taburan pheromone, yaitu suatu zat kimia yang berasal dari kelenjar endokrin dan digunakan oleh makhluk hidup untuk mengenali sesama etnis, individu lain, kelompok, dan untuk membantu proses reproduksi. Pada algoritma BAS, langkah langkah untuk menyelesaikan permasalahan MKP yaitu dengan menentukan parameter yang akan digunakan seperti nilai evaporasi dan jumlah iterasi maksimal. Selanjutnya dengan mengurutkan barang berdasarkan pseudo utility ratio, membentuk solusi, memperbaiki solusi yang infisible, melakukan perhitungan factor konvergensi (cf), melakukan update pheromone berdasarkan nilai cf, dan melakukan proses restart pheromone ketika nilai cf kurang dari cf5. Untuk mempermudah penyelesaian permasalahan MKP dengan algoritma BAS, dalam skripsi ini dibuat program dengan bahasa pemrograman Python 3.7.4 dan software Microsoft Visual Studio Code.

Multidimensional Knapsack Problem (MKP) is a optimization problem on allocating several goods that have the weight and value of goods (income) into some knapsack with a certain capacity so that the amount of weight from the goods is not exceeded the knapsack capacity. The selection of the number of goods into the knapsack requires a certain method that can be used to solve optimization problems of combinatorial optimization. In this undergraduate thesis, we apply the algorithm of Binary Ant System (BAS) which is a modification of Ant Colony Optimization (ACO) to solve the Multidimensional Knapsack Problem (MKP). Ant Colony Optimization (ACO) is an algorithm that adopts the behavior of several ants which work together and communicate indirectly when searching for food sources. Ants communicate with a sprinkling of pheromone, which is a chemical derived from the endocrine gland and is used by living beings to recognize fellow ethnicity, other individuals, groups, and to assist the reproduction process. In the BAS algorithm, the steps to resolve the MKP problem are specified by the parameters, such as the number of ants, the evaporation value, and the maximum number of iterations. The next step is to sort the items based on the pseudo utility ratio,find the solutions, repair operators of the invisible solution, perform the convergence factor (cf), perform pheromone update based on the value cf, and perform the restart process pheromone when the value of cf is less than cf5. To simplify the problem-solving MKP problems with BAS algorithm, we develop a program by using Python 3.7.4 programming language and Microsoft Visual Studio Code.

Kata Kunci : Ant colony optimization; Binary ant system; Combinatorial optimization; Multidimensional Knapsack problem