Binary Moth Search Algorithm for Discounted {0-1} Knapsack Problem

Abstract

The discounted {0-1} knapsack problem (DKP) extends the classical 0-1 knapsack problem (0-1 KP) in which a set of item groups is included and each group consists of three items, whereas at most one of the three items can be packed into the knapsack. Therefore, the DKP is more complicated and computationally difficult than 0-1 KP. The DKP has been found many applications in real economic problems and other areas. In this paper, the influence of Lévy flights operator and fly straightly operator in the moth search (MS) algorithm is verified. Nine types of new mutation operator based on the global harmony search are specially devised to replace Lévy flights operator. Then, nine novel MS-based algorithms for DKP are proposed (denoted by MS1-MS9). Extensive experiments on three sets of 30 DKP instances demonstrate the remarkable performance of the proposed nine new MS-based approaches. In particular, it discovers that MS1-MS3 show better comprehensive performance among 10 algorithms. A variety of analyses indicate the important contribution of the individual of memory consideration in MS1-MS9.

Keywords

• Discounted {0-1} knapsack problem
• harmony search
• moth search
• swarm intelligence