Modified swarm intelligence based techniques for the knapsack problem

摘要

Swarm intelligence based algorithms have become an emerging field of research in recent times. Among them, two recently developed metaheuristics, cuckoo search algorithm (CSA) and firefly algorithm (FA) are found to be very efficient in solving different complex problems. CSA and FA are usually applied to solve the continuous optimisation problems. In this paper, an attempt has been made to utilise the merits of these algorithms to solve combinatorial problems, particularly 01 knapsack problem (KP) and multidimensional knapsack problem (MKP). In the improved version of CSA, a balanced combination of local random walk and the global explorative random walk is utilised along with the repair operator; whereas in the modified version of FA, the variable distance move with the repair operator of the local search and opposition-based learning mechanism is applied. Experiments are carried out with a large number of benchmark problem instances to validate our idea and demonstrate the efficiency of the proposed algorithms. Several statistical tests with recently developed algorithms from the literature present the superiority of these proposed algorithms.