摘要
针对多选择多维背包问题(MMKP)的特点,设计一种新型混合算法(ACO&PR).该算法将线路重连算法(PR)嵌入蚁群算法(ACO),在搜索过程中既考虑解的质量,又考虑解的分散性.线路重连算法在重连过程中,向导解的属性逐步引入起始解属性中,可快速获得该线路上的最优解.实验结果表明,该算法优于其他现有较好的方法,获得了较好的结果.
For the features of the multipl-choice multidimensinal knapsack problem（MMKP）, a novel hybrid algorithm （ACO＆PR） is designed, in which path relinking （PR） is embeded into the solution construction mechanism of ant colony optimization, and solution diversification is considered besides solution quality in the search process. In the process of the path relinking phase, the attributes of the guiding solution is introduced into the initial solution progressively to obtain the high quality solution as quickly as possible. The experimental results show that the method is very efficient and competitive to solve the MMKP compared with the better existing methods.
出处
《控制与决策》
EI
CSCD
北大核心
2009年第5期729-733,共5页
Control and Decision
基金
国家杰出青年科学基金项目(70425003)
国家863计划项目(2006AA04Z174)
关键词
多选择多维背包
蚁群算法
线路重连算法
Multiple-choice multidimensional knapsack
Ant colony optimization
Path relinking
