Journal Article

A novel discrete whale optimization algorithm for solving knapsack problems

Li, Zewen, He Yichao, Li, Ya, Liu Xuejing, Guo Xiaohu

2020

Overview

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.

• Publisher: Springer Nature B.V
• Subject: Algorithms / Heuristic methods / Integers / Knapsack problem / Optimization / Optimization algorithms / Solution space