基于核问题的果蝇优化算法求解多维背包问题

Core-based fruit fly optimization algorithm for solving multidimensional knapsack problem

针对多维背包问题(MKP)维度高、约束强的特点,提出了一种基于核问题的果蝇优化算法(CBFOA).该算法通过求解MKP的线性规划松弛问题(LPR-MKP)的对偶问题得到MKP效用比,并运用核问题降低问题规模;果蝇的生成采用的二级结构和时变的搜索步距有利于前期快速寻优和后期精确搜索,采用的修复补偿策略、一级果蝇交流以及视觉搜索中的突跳机制以提高求解质量.通过标准测试集的测试和算法性能的对比,结果表明CBFOA对于MKP有较强的搜索能力.

A core-based fruit fly optimization algorithm (CBFOA) was proposed for solving multidimensional knapsack problem (MKP),which was characterized as high dimension and strong constraint.By solving the dual problem of the linear programming relaxion of MKP,a pseudo-utility ratio was attained.The core concept was applied to reduce the problem scale.The two-level structure was also employed to widen the search range.Simultaneously,the time varying searching step was employed to balance the searching speed and quality.A repair operator and communication strategy between flies of first level,as well as the mutation mechanism in the visual search were used to improve the quantity of solution.The test experiments conducted on the standard test set and algorithm comparison demonstrates that CBFOA has a strong search capability for MKP.