An Improved Hybrid Encoding Firefly Algorithm for Randomized Time-varying Knapsack Problems

In this paper, an improved hybrid encoding firefly algorithm (IFA) is proposed for solving randomized time varying knapsack problems (RTVKP). The RTVKP is an extension from the generalized time-varying knapsack problems (TVKP) by dynamically changing the profit and weight of items as well as the capacity of knapsack. In IFA, two-tuples composed of real vector and binary vector is used to represent the individuals in a population, and two principal search processes are developed: the current global best-based search process and the trust region-based search process. Moreover, a novel and effective repair operator is adopted to modify infeasible solutions, optimize feasible solutions and calculate the fitness of individual. The performance of IFA is verified by comparison with FA, cuckoo search (CS), shuffled frog leaping algorithm (SFLA), genetic algorithms (GAs) and differential evolution (DE) over three instances of RTVKP. The results indicate that IFA outperformed the other five methods in most cases and the proposed IFA is an efficient algorithm for solving randomized time-varying knapsack problems.