MODIFIKASI FLOWER POLLINATION ALGORITHM DENGAN REPLACEMENT BERBASIS ILS: PERMASALAHAN QUADRATIC BOUNDED KNAPSACK

(Modified Flower Pollination Algorithm with ILS-Based Replacement: Quadratic Bounded Knapsack Problem)

Abstract

Optimization problems are the most interesting problems to discuss in mathematics. Optimization is used to modeling problems in various field to achieve the effectiveness and efficiency of the desired target. One of the optimization problems that are often encountered in everyday life is the selection and packaging of items with limited media or knapsack to get maximum profit. This problem is well-known as knapsack problem. There are various types of knapsack problems, one of them is quadratic bounded knapsack problem. In this paper, the authors proposed a new modified algorithm, which is Flower Pollination Algorithm (FPA) added with Iterated Local Search (ILS)-based Replacement mechanism. Furthermore, the implementation of the proposed algorithm, MFPA, is compared to the original FPA. Based on the results of this study, the proposed MFPA performs better and produces the best solution than the original algorithm on all data used. The advantage obtained by the MFPA algorithm is better and in accordance with the knapsack capacity. In addition, although the computational of the MFPA takes longer time than FPA with the same number of iterations, MFPA is able to find better solutions faster and able to escape from the local optimum.

Keywords: Flower Pollination Algorithm, Iterated Local Search, Knapsack, Optimization, Quadratic Bounded Knapsack.