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

Relaxed complemental estimation of distribution algorithm for the multidimesional knapsack problem

作　　者：杨广益[1] 欧阳智敏[1] 全惠云[1] 

机构地区：[1]湖南师范大学数学与计算机科学学院,长沙410081

出　　处：《计算机工程与应用》2007年第12期77-80,共4页Computer Engineering and Applications

摘　　要：演化计算(Evolutionary Computation简记为EC)是受自然界物种进化启发而产生的一类优化技术;分布估计算法(Estimation of Distribution Algorithms简记为EDAs)是一类基于概率模型的估计与模拟的演化算法,它在参数设置及计算效率上有着其它演化方法难以比拟的优势[1]。受自然界互补机制的启发,提出了一种改进的分布估计算法-松驰互补分布估计算法(Relaxed Complemental Estimation of Distribution Algorithm简记为RCEDA)。在求解Chu和Beasley提出的MKP Benchmark[3]时,算法在较短的时间内找到了大多数目前书籍的最好解,分析和实验结果表明RCEDA是一种较好的演化算法。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 referencet have showed the advantage of EDAs.Inspired by the complementarity mechanism in nature,this paper presents a Relaxed Complemental Estimation of Distribu- tion Algorithm （RCEDA）.We carry out experiment studies on the well-know Chu and Beasley MPK benchmark.The analysis and computational results show that the algorithm is competitive.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]