G4算法实现与布局问题的相对熵算法研究

论文摘要

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

论文目录

• 致谢
• 中文摘要
• ABSTRACT
• 1 绪论
• 1.1 布局问题概述
• 1.1.1 布局问题的起源
• 1.1.2 布局问题的分类
• 1.2 布局问题的研究现状
• 1.2.1 布局问题实体建模方法
• 1.2.2 布局问题建模研究现状
• 1.2.3 布局求解方法现状
• 1.3 课题的提出
• 1.3.1 本课题的来源及提出
• 1.3.2 课题的学术及工程意义
• 1.4 作者的主要工作和论文结构
• 1.5 本章小结
• 2 装盘问题的G4算法
• 2.1 动态规划法概要
• 2.1.1 动态规划的基本概念
• 2.1.2 动态规划的基本思想与实质
• 2.2 装盘问题G4算法的主要内容
• 2.2.1 装盘问题G4-结构定义
• 2.2.2 装盘问题G4启发式算法
• 2.3 G4算法相关数据结构和程序框图设计
• 2.3.1 G4算法相关数据结构
• 2.3.2 算法相关程序框图说明
• 2.4 实验验结果和分析
• 2.5 本章小结
• 3 交叉熵算法理论基础
• 3.1 熵、信息熵与交叉熵概念
• 3.1.1 熵的起源发展
• 3.1.2 信息熵与交叉熵
• 3.2 交叉熵模拟小概率事件的基本原理
• 3.3 交叉熵求解优化问题基本原理
• 3.4 交叉熵算法与经典元启发式算法的比较
• 3.5 本章小结
• 4 二维布局问题的交叉熵算法研究
• 4.1 交叉熵求解2D-R-ODP
• 4.1.1 随机样本的生成
• 4.1.2 2D-R-ODP的DROP和DROPF解码原则
• 4.1.3 采用交叉熵求解2D-R-ODP参数的更新
• 4.2 实验结果与对比
• 4.3 结论
• 4.4 本章小结
• 5 集装箱布局的交叉熵算法研究
• 5.1 集装箱布局的编码方法
• 5.2 集装箱布局的解码策略
• 5.3 参数更新方式
• 5.4 试验及其结果
• 5.5 结果分析
• 5.6 本章小结
• 6 总结与展望
• 6.1 全文总结
• 6.2 展望
• 参考文献
• 作者简历
• 学位论文数据集