一种新的求解多维背包问题的分散算法  

New scatter search algorithm for multidimensional knapsack problem

作　　者：张晓霞[1] 刘哲[1] 

机构地区：[1]辽宁科技大学软件学院,辽宁鞍山114051

出　　处：《计算机应用研究》2012年第5期1716-1719,共4页Application Research of Computers

基　　金：辽宁省教育厅资助项目(L2010196)

摘　　要：为了避免蚁群算法在优化搜索过程中易陷入局部最优和早熟收敛,提出一种求解多维背包问题的新型分散搜索算法。该算法是把蚁群算法的构解方法引入到分散搜索算法中,在搜索过程中,既考虑解的质量,又考虑解的分散性。同时,该分散算法还采用了动态更新参考集与阈值接收算法的阈值参数,以控制搜索空间来加快收敛速度。通过选取国际通用MDKP实例库中的多个实例进行测试表明,该算法可以避免陷入局部最优解,能提高全局寻优能力,其结果优于其他现有的方法,并获得了较好的结果。To avoid falling into local optimal solution and the premature convergence in the process of searching optimization solutions,this paper presented a new scatter search algorithm.The designed algorithm combined the solution construction mechanism of ant colony optimization（ACO） into scatter search（SS）.It considered both solution quality and diversification.Simultaneously,the algorithm adopted the dynamic updating strategy and the parameter criterion of threshold accepting to accelerate the convergence towards high-quality regions of the search space.The performance of the proposed algorithm was tes-ted on MDKP benchmark problems from the OR Library.The experimental results show that the proposed algorithm can avoid trapping in local optimal solution and enhance the ability of global optimization,and it is competitive to solve the multidimensional knapsack problem compared with the other heuristic methods in terms of solution quality.

关 键 词：多维背包问题 蚁群优化 分散搜索 参考集 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]