Estimation of Distribution Algorithm Based on Lévy Flight for Solving the Set-Union Knapsack Problem

Abstract

This article investigates how to use the estimation of distribution algorithm based on Lévy flight to solve the set-union knapsack problem (SUKP). First, the mathematical model of the SUKP is introduced. Then, a quadratic greedy repair and optimization algorithm (Q-GROA), which deals with infeasible solutions, is proposed. Thereby, a new approach, the estimation of distribution algorithm based on Lévy flight (LFEDA) combined with the Q-GROA is also proposed to solve the SUKP. A number of experiments are performed on the SUKP datasets to evaluate the performance of our proposed model. The results verify that the proposed method is significantly better than other algorithms with respect to the solution's performance.

Keywords

• Set-union knapsack problem
• estimation of distribution algorithm
• Lévy flight
• repair and optimization