求解多维背包问题的二级协作果蝇优化算法

针对多维背包问题(MKP)约束性强和复杂度高的特点,提出一种新型二级协作果蝇优化算法(TCFOA).提出一级果蝇和二级果蝇的产生机制,将二级果蝇划分为开发用果蝇和探索用果蝇两类以协调开发与探索之间的平衡;设计果蝇交流策略以及基于全局性价比的解的修复补偿机制,并利用二级结构扩大搜索范围、改善一级果蝇的质量,以提高求解质量.基于MKP两个标准测试集的测试结果和算法性能对比,表明TCFOA在求解MKP方面具有较强的优势.

Two-level cooperative fruit fly optimization algorithm for multidimensional knapsack problem

A novel two-level cooperative fruit fly optimization algorithm(TCFOA) is proposed for the multidimensional knapsack problem(MKP) with the characteristics such as strong constraints and high complexity. The TCFOA is constructed based on the generation mechanism of primary and secondary fruit flies, and the secondary fruit flies are aivided into two types for exploration and exploitation to implement the balance of exploration and exploration. A communication strategy of fruit flies and a compensation mechanism based on global cost/performance ratio are proposed. A two-level structure is used to expand the search range and improve the quality of the primary fruit flies to obtain high quality solutions. The test experiments are conducted on two sets of MKP instances, and the TCFOA is compared with the methods from literature. The results demonstrate the advantages of the TCFOA in solving the MKP.