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

被引:162
作者
Wang, Ling [1 ]
Zheng, Xiao-long [1 ]
Wang, Sheng-yao [1 ]
机构
[1] Tsinghua Univ, Dept Automat, Tsinghua Natl Lab Informat Sci & Technol TNList, Beijing 100084, Peoples R China
基金
美国国家科学基金会;
关键词
Multidimensional knapsack problem; Fruit fly optimization algorithm; Binary algorithm; Smell-based search; Vision-based search; MODEL;
D O I
10.1016/j.knosys.2013.04.003
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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. (c) 2013 Elsevier B.V. All rights reserved.
引用
收藏
页码:17 / 23
页数:7
相关论文
共 31 条