A novel discrete whale optimization algorithm for solving knapsack problems
- PDF / 2,384,039 Bytes
- 17 Pages / 595.224 x 790.955 pts Page_size
- 35 Downloads / 227 Views
A novel discrete whale optimization algorithm for solving knapsack problems Ya Li1 · Yichao He1 · Xuejing Liu1 · Xiaohu Guo1 · Zewen Li1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Whale optimization algorithm (WOA) is a recently proposed meta-heuristic algorithm which imitates the hunting behavior of humpback whales. Due to its characteristic advantages, it has found its place in the mature population-based methods in many scientific and engineering fields. Because WOA was proposed for continuous optimization, it cannot be directly used to solve discrete optimization problems. For this purpose, we first give a new V -shaped function by drawing lesson from the existing discretization methods, which transfer a real vector to an integer vector. On this basis, we propose a novel discrete whale optimization algorithm (DWOA). DWOA uses the new proposed V -shaped function to generate an integer vector, and it can be used to solve discrete optimization problems with solution space {0, 1, . . . , m1 } × {0, 1, . . . , m2 } × . . . × {0, 1, . . . , mn }. To verify effectiveness of DWOA for the 0-1 knapsack problem and the discount {0-1} knapsack problem, we solve their benchmark instances from published literature and compare with the state-of-the-art algorithms. The comparison results show that the DWOA has more superiority than existing algorithms for the two kinds of knapsack problems. Keywords Whale optimization algorithm · Meta-heuristic algorithm · V -shaped function · 0-1knapsack problem · Discounted {0-1} knapsack problem
1 Introduction Knapsack problem (KP) [1–3] is a class of NP-hard problem, which has important theoretical significance and practical value in the fields of industry, economy, and finance. The classical KP is 0-1 knapsack problem (01KP) [3]. In addition, there exist many others knapsack problems which are the extensions of 0-1 KP, such as the multidimensional knapsack problem (MDKP) [4], the quadratic knapsack problem (QKP) [5], the set union knapsack problem (SUKP) [6], the bounded knapsack problem(BKP) [7], the discount 0-1 knapsack problem (D{0-1}KP) [8]. In 0-1 KP [9], given a set of n items and a knapsack with capacity C, each item has a weight wi and a profit pi . The objective is to select a subset of items, such that the overall profit of the selected items is maximize while their total weight not exceeding the knapsack capacity C. Yichao He
[email protected] 1
College of Information and Engineering, Hebei GEO University, Shijiazhuang, 050031, China
Without loss of generality, pi , wi (1 ≤ i ≤ n), C are positive integers. Let X = [x1 , x2 , . . . , xn ] ∈ {0, 1}n denote a feasible solution of the 0-1KP. xi = 1 means that item i is loaded into knapsack, otherwise xi = 0. The 0-1KP is mathematically modeled as follows: Maximize
f (X) =
n
xi pi
(1)
i=1
s.t.
n
xi wi ≤ C, i = 1, 2, · · · , n
(2)
i=1
D{0-1}KP is a novel extension of KP and it was first proposed by Guldan [8]. D{0-1}KP accurately reflects the practical problems in reality a
Data Loading...
