二次分配问题的精度推进算法

论文摘要

二次分配问题（quadratic assignment problem，QAP）是组合优化问题中最为著名的问题之一，它综合了一大类组合优化问题的典型特征，并以不同的形式存在于医院布局、后挡板布线设计、键盘布局等广泛的应用领域中。QAP问题通常在多项式时间内无法求解，属于NP-难解问题。随着实例规模的不断扩大，解空间呈现组合爆炸特征，无法用常规的方法求解。故求解QAP问题的启发式算法成为计算机科学基础研究的热点之一。对于复杂的难优化问题，若将同一启发式算法作用于QAP问题的不同实例时，其求解性能可能存在较大的差异，故从理论上理解这一差异的原因，对于算法的设计和问题的求解都是极为重要的。适应度地貌分析是近年发展起来的一种研究问题结构与难优化本质的有效方法，该方法通过分析QAP问题的适应度地貌的结构特征，进而指导算法设计和改进算法的优化性能。而且，QAP问题的大多数启发式算法的基础是局部搜索，其将解视为适应度地貌中的点，在当前点的邻域搜索更好的解。因此，适应度地貌的粗糙系数决定了启发式算法的求解性能。本文通过逐步变换QAP实例中的流量矩阵获得一系列不同精度的实例，它们的适应度地貌的粗糙系数随着实例精度下降而逐渐降低。由于不同精度的实例之间差别较小，而粗糙系数低的实例又相对容易获得高质量的解，从而可以利用低精度实例的解来引导高精度实例的求解。根据这一性质，本文提出了求解二次分配问题的精度推进算法（PPA）。PPA算法通过将原始QAP实例的求解转化为一系列精度由低到高的实例的迭代求解，以降低原始实例的求解难度。QAPLIB上大量的测试实验表明，PPA算法在解的质量上比RTS、GH、SA、HAS-QAP和AntSimulated等算法有较显著改进。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 QAP问题的研究现状
• 1.2 本文主要工作和安排
• 2 求解QAP问题的启发式算法
• 2.1 组合优化问题
• 2.2 计算复杂性与NP完全问题
• 2.3 二次分配问题
• 2.4 QAP启发式算法
• 2.4.1 禁忌搜索
• 2.4.2 模拟退火算法
• 2.4.3 遗传算法
• 2.4.4 神经网络
• 2.4.5 蚁群算法
• 3 启发式算法的适应度地貌分析
• 3.1 适应度地貌在启发式算法中的应用
• 3.2 适应度地貌的相关结构分析
• 3.3 随机游走模型的时间序列分析
• 3.4 动态适应度地貌分析
• 4 求解QAP问题的精度推进算法
• 4.1 QAP问题的适应度地貌的相关定义
• 4.2 QAP实例的精度变换
• 4.2.1 精度变换算子
• 4.2.2 时间复杂度分析
• 4.3 不同精度实例的适应度地貌分析
• 4.3.1 QAP问题的自相关函数与粗糙系数
• 4.3.2 实验结果及分析
• 4.4 精度推进算法
• 4.4.1 PPA算法描述
• 4.4.2 时间复杂度分析
• 4.4.3 PPA算法的优点
• 5 实验及分析
• 5.1 实验平台
• 5.2 QAP问题实例
• 5.3 实验描述
• 5.3.1 源文件介绍
• 5.3.2 程序流程
• 5.3.3 相关公式介绍及符号说明
• 5.4 PPA算法的性能分析
• 5.4.1 PPA算法与Tabu算法对比
• 5.4.2 PPA算法与主流启发式算法的性能比较
• 结论
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢