MKP的一种向量启发信息的设计和实现

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (28): 89-91.

MKP的一种向量启发信息的设计和实现

王介新,吕强,钱培德

苏州大学计算机科学与技术学院,江苏苏州 215006

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-10-01 发布日期:2007-10-01
通讯作者: 王介新

Design and implementation of new vector heuristic information for MKP

WANG Jie-xin,LV Qiang,QIAN Pei-de

School of Computer Science and Technology,Soochow University,Suzhou,Jiangsu 215006,China

Received:1900-01-01 Revised:1900-01-01 Online:2007-10-01 Published:2007-10-01
Contact: WANG Jie-xin

摘要/Abstract

摘要： 多背包问题（MKP）是一个典型的NP-hard组合优化问题。启发信息的设计是众多启发搜索算法解决MKP的关键手段之一。提出了一种新的针对MKP的启发信息设计,利用了向量距离来度量背包容量和物体消耗之间的拟和程度。基于这种启发信息,通过蚁群优化算法ACS实现了对MKP标准测试库30个实例的计算,与ACS现有启发信息相比,该方法有16例找到最优解,并全面优于同类实现。同时与当前MKP最好解决方案GA比较了2例结果,该方法的平均性能都优于该解决方案。

关键词: 多背包问题, 蚁群优化算法, 启发信息

Abstract: The Multiple Knapsack Problem（MKP） is a classic NP-hard static combination optimization problem.The design of heuristic information is one of the key techniques to MKP for most meta-heuristics.This paper proposes a new design of heuristic information for MKP by measuring the vector distance between the capacity of the knapsack and resource of the object.Based on this heuristic information design,this paper re-implements ACS to tackle MKP benchmark.Among the 30 problem instances we are testing,our new approach finds 16 optima,which is overall superior over the current ACS implementation.This paper also compares the results to that of state-of-the-art results coming from GA approach.The testing results show that our new approach has better average quality than GA approach.

Key words: MKP, ACS, heuristic information

王介新,吕强,钱培德. MKP的一种向量启发信息的设计和实现[J]. 计算机工程与应用, 2007, 43(28): 89-91.

WANG Jie-xin,LV Qiang,QIAN Pei-de. Design and implementation of new vector heuristic information for MKP[J]. Computer Engineering and Applications, 2007, 43(28): 89-91.

[1]	张铭，邓文瀚，林娟，钟一文. 改进蚁群优化算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(13): 85-95.
[2]	张海南，游晓明，刘升，刘中强. 交互式学习的布谷鸟搜索算法[J]. 计算机工程与应用, 2020, 56(7): 147-154.
[3]	薛文艳，赵江，郝崇清，刘慧贤. 基于信息素负反馈的超启发式蚁群优化算法[J]. 计算机工程与应用, 2019, 55(4): 163-172.
[4]	姜道银1，2，葛洪伟1，2. 基于信息交流策略的连续域蚁群优化算法[J]. 计算机工程与应用, 2019, 55(11): 153-159.
[5]	姜道银1，2，葛洪伟1，2，袁罗1. 一种动态划分的混合连续域蚁群优化算法[J]. 计算机工程与应用, 2018, 54(7): 144-151.
[6]	陈恒1，2，李冠宇2，孙云浩2. 重排序RDF流三元组模式的蚁群优化方法[J]. 计算机工程与应用, 2017, 53(12): 172-177.
[7]	李泽1，贺利乐1，郭志杰1，郑建校1，吴敏宁2. 改进协同进化算法优化液压集成块管路布置[J]. 计算机工程与应用, 2016, 52(23): 266-270.
[8]	吕金秋1，游晓明1，刘升2. 机器人全局路径规划的混合蚁群系统算法[J]. 计算机工程与应用, 2016, 52(11): 38-43.
[9]	高雷阜，张秀丽，王飞. 改进蚁群算法在SVM参数优化研究中的应用[J]. 计算机工程与应用, 2015, 51(13): 139-144.
[10]	金浩1，刘维宁2. 基于改进蚁群算法的梯式轨道多目标优化研究[J]. 计算机工程与应用, 2014, 50(22): 28-31.
[11]	徐善健，郭有强，戚晓明，夏伟. 混沌蚂蚁群优化求解自由节点B样条曲线拟合[J]. 计算机工程与应用, 2014, 50(16): 177-182.
[12]	田海梅1，黄楠2. 基于ACO-LSSVM的网络流量预测[J]. 计算机工程与应用, 2014, 50(1): 91-95.
[13]	魏平，熊伟清. 求解强异类集装箱装载问题的混合蚁群算法[J]. 计算机工程与应用, 2013, 49(7): 252-257.
[14]	何敏1，周永华2，唐平江2，鲍伟强2. 基于蚁群算法的PCB布线优化[J]. 计算机工程与应用, 2012, 48(9): 226-229.
[15]	钱雪忠，李玉. 求解组合测试用例集的差分进化蚁群算法[J]. 计算机工程与应用, 2012, 48(4): 68-70.