松驰互补分布估计算法求解多维背包问题

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (12): 77-80.

松驰互补分布估计算法求解多维背包问题

杨广益欧阳智敏全惠云

湖南师范大学数学与计算机科学学院湖南师范大学数学与计算机学院

收稿日期:2006-05-29 修回日期:1900-01-01 出版日期:2007-04-20 发布日期:2007-04-20
通讯作者: 杨广益

Relaxed Complemental Estimation of Distribution Algorithms for the Multidimesional Knapsack Problem

Received:2006-05-29 Revised:1900-01-01 Online:2007-04-20 Published:2007-04-20

摘要/Abstract

摘要： 演化计算(Evolutionary Computation 简记为EC) 是受自然界物种进化启发而产生的一类优化技术。分布估计算法(Estimation of Distribution Algorithms 简记为EDAs)是一类基于概率模型的估计与模拟的演化算法，它在参数设置及计算效率上有着其它演化方法难以比拟的优势［1］。受自然界互补机制的启发，本文提出了一种改进的分布估计算法－松驰互补分布估计算法（Relaxed Complemental Estimation of Distribution Algorithm 简记为RCEDA）。在求解Chu 和 Beasley提出的MKP Benchmark[3] 时，算法在较短的时间内找到了大多数目前书籍的最好解，分析和实验结果表明RCEDA是一种较好的演化算法。

关键词: 线性规划, 多维背包问题, 分布估计算法, 松驰互补模型

Abstract: Evolutionary Computation belongs to the algorithms inspired by nature. Estimation of Distribution Algorithms (EDAs) is based on the simulation and inference of probability distribution of population. Practices in reference[1] have showed the advantage of EDAs. Inspired by the complementarity mechanism in nature, this paper present a Relaxed Complemental Estimation of Distribution Algorithm (RCEDA). We carry out experiment studies on the well-know Chu and Beasley MPK benchmark. The analysis and computational results show that our algorithm is competitive

Key words: Linear Programming, Multidimesional Knapsack Problem, Estimation of Distribution Algorithms, Relaxed complemental model.

杨广益欧阳智敏全惠云. 松驰互补分布估计算法求解多维背包问题[J]. 计算机工程与应用, 2007, 43(12): 77-80.

[1]	张惠煜，陈庆新，毛宁. 随机批量物料搬运的制造系统AGV配置优化[J]. 计算机工程与应用, 2021, 57(4): 245-251.
[2]	陈刚，付江月. 军民融合背景下无人机配送中心选址问题研究[J]. 计算机工程与应用, 2019, 55(8): 226-231.
[3]	耿海军. Segment Routing体系结构中的域内路由保护方案[J]. 计算机工程与应用, 2019, 55(8): 80-85.
[4]	宋健，方贤文，王丽丽，刘祥伟. 业务流程隐变迁的拟间接依赖挖掘方法[J]. 计算机工程与应用, 2019, 55(22): 265-270.
[5]	李海燕1，王艳萍1，周建勇2，刘久富2. 部分可控Petri网分布式死锁监控器设计[J]. 计算机工程与应用, 2018, 54(8): 48-54.
[6]	韩晓龙，李上，杨全业. 基于遗传算法的战略供应链集成研究[J]. 计算机工程与应用, 2018, 54(2): 214-221.
[7]	杨小东，康雁，柳青，孙金文. 求解作业车间调度问题的禁忌分布估计算法[J]. 计算机工程与应用, 2017, 53(7): 147-153.
[8]	郑星星，谢明鸿，张亚运. 基于空间划分和线性规划的快速碰撞检测算法[J]. 计算机工程与应用, 2017, 53(23): 236-240.
[9]	孙良旭1，曲殿利2，刘国莉3. 置换流水车间调度问题的两阶段分布估计算法[J]. 计算机工程与应用, 2017, 53(2): 64-71.
[10]	曾兆敏1，管卫利2，潘卫平3. 冲裁件条料最优四块剪切下料方案的生成算法[J]. 计算机工程与应用, 2016, 52(20): 75-79.
[11]	邵良杉1，李永利1，赵琳琳1，温廷新2，孔祥博2. 矿山产能分配的变量模糊线性规划模型[J]. 计算机工程与应用, 2016, 52(20): 227-230.
[12]	邵良杉1，赵琳琳1，张艳菊2. 基于结构元矿山产能分配模糊线性规划模型[J]. 计算机工程与应用, 2016, 52(13): 228-231.
[13]	章宏伟1，汪振利1，杜世民1，2，张川1. 基于ILP的电压岛驱动的多电压分配算法[J]. 计算机工程与应用, 2016, 52(1): 23-28.
[14]	时光，刘健辰，陈忠华，郭凤仪，姜国强. 基于DE-EDA多目标优化的受电弓模糊控制[J]. 计算机工程与应用, 2016, 52(1): 229-232.
[15]	温芝元1，曹乐平2. 最优RGB线性组合颜色模型目标检测方法[J]. 计算机工程与应用, 2015, 51(18): 218-223.