论文部分内容阅读
布局问题是一个经典的组合优化问题,其现实的实用性和其本身的NP-完全性带来的巨大挑战吸引了来自工程、数学、计算机科学等领域的无数学者对其进行广泛而深入的研究。针对不同的具体问题,其求解方法也层出不穷,G4算法就是求解装盘问题的一个非常高效的算法,所以本文先对该算法进行编程实现,以对其思想进行消化吸收。继而本文提出并采用交叉熵这种较新的元启发式算法来求解2、3维布局问题。本文通过大量的实验,证明了交叉熵求解布局问题的有效性。
首先,本文总结归纳了布局问题的分类和国内外研究现状,提出了本课题的研究内容。
结合企业的需求和G4求解装盘问题的高效性,本文对其进行了重新编程实现,消化吸收了其思想。因为G4算法的理论基础是动态规划法,所以本文在介绍G4算法前对动态规划的基本概念、思想、原理进行了简单介绍。
然后,介绍了熵的起源、发展和信息熵与交叉熵的数学表达。在交叉熵定义的数学表达的基础上,介绍了交叉熵求解小概率事件估计的基本原理。基于优化问题出现最优解一般情况下概率很小,本文给出将优化问题转换为相应的小概率估计问题,然后再采用交叉熵算法来求解的基本原理。为了更好地理解算法的本质,本文对交叉熵算法与经典元启发式算法的共同点与相异性进行了总结与归纳。
然后,在交叉熵求解优化问题的理论可行的基础上提出了采用交叉熵来求解二维布局问题:采用基于概率矩阵的样本生成方法与DROP和DROPF两种解码策略来确定装箱方案,给出了参数更新机制和整个算法。并对DROP和DROPF解码的数据结构做了说明,同时给出了DROPF解码流程图。在充分的理论基础之上进行了大量数值模拟试验,并将实验结果与一些经典的元启发式算法进行了对比,其实验效果非常好,验证了算法的可行性。
继后试探性地将交叉熵算法应用于集装箱布局优化问题中来:采用基于Bernoulli分布的编码原则和基于空间分解的解码策略。在对基于Bernoulli分布的编码原则和空间分解的解码策略进行详细说明之后,采用试验验证了算法的可行性。
最后对全文进行了总结,同时展望了后续的研究方向。