A novel binary fruit fly optimization algorithm for solving the multidimensional knapsack problem

摘要

In this paper, a novel binary fruit fly optimization algorithm (bFOA) is proposed to solve the multidimensional knapsack problem (MKP). In the bFOA, binary string is used to represent the solution of the MKP, and three main search processes are designed to perform evolutionary search, including smell-based search process, local vision-based search process and global vision-based search process. In particular, a group generating probability vector is designed for producing new solutions. To enhance the exploration ability, a global vision mechanism based on differential information among fruit flies is proposed to update the probability vector. Meanwhile, two repair operators are employed to guarantee the feasibility of solutions. The influence of the parameter setting is investigated based on the Taguchi method of design of experiment. Extensive numerical testing results based on benchmark instances are provided. And the comparisons to the existing algorithms demonstrate the effectiveness of the proposed bFOA in solving the MKP, especially for the large-scale problems.