分布估计算法求解集装箱装载问题  

Solving of Container Loading Problem by Estimation of Distribution Algorithm

作　　者：左先亮 郭莉莉[1] 高尚[1] 

机构地区：[1]江苏科技大学计算机科学与工程学院,江苏镇江212003

出　　处：《计算机技术与发展》2014年第8期183-186,190,共5页Computer Technology and Development

基　　金：人工智能四川省重点实验室开放基金(2012RYJ04);江苏省"青蓝工程"资助项目(苏教师[2010]27号)

摘　　要：集装箱装载是一个空间优化分解的布局问题,其约束条件多,属于典型的NP完全问题,求解难度大。在考虑实际应用中的约束条件下,使用三空间分割的布局方法对剩余空间进行分解,并采用空间合并原则将闲置空间与可用空间进行合并达到充分利用,并结合分布估计算法(EDA)求解多约束装箱问题。分布估计算法采用统计学习的方法建立一个描述解分布的概率模型,再对概率模型进行随机采样产生新的种群,如此反复进行,实现种群的进化,最终获取最优解。实验仿真结果表明该算法应用于实际空间规划设计中具有重要的实际意义。Container loading is a layout problem with space optimization and decomposition. With multiple constraints,it’s a typical NP-complete problem and difficult to obtain an optimal solution. Considering some constraints in practical applications,adopt the measures of three-space-dividing to decompose the residual space,use the spatial merge principle to combine the free space with the usable space in order to achieve the full use of container,and combined with the Estimation of Distribution Algorithm （ EDA） ,solve the multi-constrained pacing problem. The EDA establishes a probability model by statistical learning to describe the distribution of solutions. New populations are gotten by sampling the probability model randomly. The algorithm is iterated to realize the evolution and finally to get the best individuals. The simulation results show that the algorithm is of great significance in the practical planning and design of space.

关 键 词：集装箱装载 空间分割 分布估计算法 统计学习 概率模型 

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