An Artificial Bee Colony Algorithm for the Multidimensional Knapsack Problem: Using Design of Experiments for Parameter Tuning

An Artificial Bee Colony Algorithm for the Multidimensional Knapsack Problem: Using Design of Experiments for Parameter Tuning

Niusha Yaghini, Mir Yasin Seyed Valizadeh
Copyright: © 2024 |Pages: 23
DOI: 10.4018/IJAMC.350225
Article PDF Download
Open access articles are freely available for download

Abstract

The Multidimensional Knapsack Problem (MDKP) stands as a prominent challenge in combinatorial optimization, with diverse applications across various domains. The Artificial Bee Colony (ABC) algorithm is a swarm intelligence optimization algorithm inspired by the foraging behavior of bees. The aim of this paper is to develop an ABC with the goal of improving the solution quality in comparison to previous studies for the MDKP. In the proposed ABC algorithm, a heuristic method is presented to make employed bees. The roulette wheel and k-tournament methods are investigated for selecting employed bees by onlooker bees. For crossing over, two methods including one-point and uniform are studied. To tune the parameters, the Design of Experiment (DOE) method has been applied. The well-known benchmark test problems have been used to evaluate the proposed algorithm. The results show the absolute superiority of the solutions generated by the proposed algorithm in compared with the previous studies.
Article Preview
Top

1. Introduction

The Multidimensional Knapsack Problem (MDKP) is an extension of the classic knapsack problem, where instead of a single constraint, there are multiple constraints to consider. Each item has multiple attributes or dimensions, and the goal is to maximize the total value of the items selected while staying within the constraints for each dimension. The MDKP is recognized as an NP-Hard integer programming problem (1). The problem can be mathematically defined as equations (1)-(3).

max⁡z=∑j=1ncjxj,(1)∑j=1naijxj≤bi,i∈M=1,2,…,m,(2)xj∈0,1,j∈N={1,2,…,n}.(3)

In Kellerer et al. (2004) study, a set of items n with profits cj≥0 needs to be packed into a knapsack with m dimensions, each having capacities bi≥0. Each item j consumes aij≥0 from each dimension i and binary variables xjdetermine the selection of items to maximize overall profit while adhering to knapsack constraints.

Complete Article List

Search this Journal:
Reset
Volume 15: 1 Issue (2024)
Volume 14: 1 Issue (2023)
Volume 13: 4 Issues (2022): 2 Released, 2 Forthcoming
Volume 12: 4 Issues (2021)
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing