Application of Combined GSA&sCSO Algorithm to Modified Bounded Knapsack with Multiple Constraints Problem against Uncertain Coefficient

Abstract

Optimization problems are interest and common problems that are often encountered in life. Optimization can be applied to solve various problems, for example development, government, business, social, economic and something related to the limitation of resource capacity. The most frequently encountered, optimization is often used to find the best solution, that is maximizing profits or minimizing production costs. One of the optimization problems that often occurs is the knapsack problem. There are several types of knapsack problems, one of which is Modified Bounded Knapsack with Multiple Constraints (MBKMC) problem. In popular mathematical studies, metaheuristic algorithms are very often used to solve optimization problems. In this paper the authors did not only use one algorithm, but implemented two metaheuristic algorithms which were combined into one, namely the Gravitational Search Algorithm (GSA) and the Cat Swarm Optimization (CSO) algorithm. The combined algorithm uses the entire GSA algorithm mechanism which is added with the CSO algorithm seeking mode to become the GSA&sCSO algorithm. The author uses the GSA&sCSO algorithm to solve the MBKMC problem of uncertain coefficient. Based on the results of this research, the GSA&sCSO algorithm produces a better solution (higher profit) than the GSA algorithm and the CSO algorithm and earn a better advantage in accordance with the knapsack capacity. In addition, the uncertain coefficient greatly affects the solution obtained, i.e if there is a change of the coefficient, then the solution also changes.