基于交叉熵方法的布局问题求解算法研究

布局问题是一种经典的组合优化问题,在求解复杂性上具有NP完全性。布局问题不仅在实际工程中具有广泛的应用,而且在理论研究上一直是数学家和计算机算法研究学者的研究热门问题。长期以来,关于求解布局问题的算法不断翻新,分类也相当详细。交叉熵方法是近几年来创立并发展起来的一种新的优化方法,在许多组合优化领域已经取得了很好的效果。本文在理解交叉熵方法的基本思想的基础上,实现交叉熵方法若干布局问题求解中的应用,并用数值实验验证交叉熵方法求解布局问题的有效性。 首先对国内外关于布局问题建模及求解算法的研究现状进行了细致的了解,分析了P、NP、NPH和NPC问题之间的关系,并探讨优化问题最优解及优化方法所具有的统计性,从而引出本课题的研究内容。 接着从信息熵的概念谈起,通过对小概率事件仿真方法的分析,引出交叉熵优化方法的思想。作者概括性地阐述了交叉熵方法的基本理论,探讨了交叉熵方法的全局优化意义。并且从优化思想和过程等方面将交叉熵方法和遗传算法、蚁群算法和模拟退火算法进行了比较,分析它们之间主要的不同点与相同点。 随后是本文的主要工作和贡献,具体给出了交叉熵方法求解部分布局问题的求解算法:(1)采用佰努利分布和样本修正策略给出了0-1背包问题的装填方案和相应的求解算法;(2)用BL装箱策略和基于序列及概率矩阵的样本生成方法来确定装箱方案,给出了参数更新机制;(3)用基于退化的二元组方法和相应的解码策略来生成聚块解方案,并设计概率矩阵更新策略,进而给出完整的求解算法。并对涉及的主要数据结构和伪代码做了说明。 然后通过不同的应用实例验证本文设计的算法。主要是采用目前研究文献中的具体算例,并将求解结果与文献所给最优解相比较,说明本文所提出算法的有效性。 最后,作者对全文的工作进行了总结,并展望了下一步可能进行的研究工作的内容。 本文首次采用交叉熵方法来求解布局问题,数值实验结果表明,求解质量不低于目前一些流行的元启发式方法,而且基于交叉熵的算法具有很好的稳定性。算例及结果真实可靠,而且具有可重复性,可以供以后的研究者参考。