Search

As an important and novel model with multitudinous practical applications, the set-union knapsack problem (SUKP) is a challenging issue in combinatorial optimization. In this paper, we present an enhanced moth search algorithm (EMS) for solving SUKP, which introduces an enhanced interaction operator (EIO) by integrating differential mutation into the global harmony search and then Lévy flight is replaced by EIO. Comparative experimental results, which were conducted on three types of 30 popular SUKP benchmark instances, demonstrate that EMS algorithm is superior to or competitive with the other state-of-the-art metaheuristic algorithm. In particular, EMS reaches the best-known solutions for the great majority of test instances and improves the best-known solutions for six instances. Two critical ingredients of EIO is investigated to confirm their impact on the performance of EMS. The results show that both components have an important role in improving the performance of EMS.

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.