An Improved Fruit Fly Optimization Algorithm for Solving Multidimensional Knapsack Problem

In this paper, a novel improved fruit fly optimization algorithm (IFOA) is proposed for solving the multidimensional knapsack problem (MKP), which is characterized as high dimension and strong constraint. Initial swarms are generated according to the probability vector respectively. After the smell-based searching accomplishing, a repair operator granded on the pseudo-utility ratio, which is calculated by solving the dual problem of linear programming relaxion of MKP, is applied to guarantee the feasibility and enhance the quality of solutions. A swarm reduction strategy is used to balance the searching ability and convergence speed. Numerous tests and comparison with other algorithms based on two sets of benchmark problems demonstrate that IFOA is an efficient algorithm to solve MKP.