论文部分内容阅读
本文着眼于元启发方法设计和使用的一般规律，围绕元启发方法研究中受到普遍关注的问题，重点研究了元启发方法和启发式方法之间融合的途径和手段，取得了下面的研究成果：
1.提出利用元启发方法中广泛使用的“交换”概念构造一种全新的距离：交换距离。研究了交换距离的定义、性质、特点、和意义；提出了针对它的若干快速算法，使得其基本操作可以拥有和海明距离一样的时间复杂度。为了将两种距离的优点结合起来，提出了将二者结合起来，产生一种全新邻域结构的途径，并利用这种全新的邻域结构对传统的处理QAP(QuadraticAssignmentProblem)问题的VNS(VariableNeighborhoodSearch)进行了改造，产生出一种处理QAP问题的更高级的VNS方法。数值实验表明，这种新VNS方法在求解质量和求解的稳定性上较之以往的方法有很大的提升，事实上，它已经可以跻身求解QAP问题性能最好的方法之列。这项工作不仅提供了一种求解QAP问题的好方法，而且说明了解空间中良好的拓扑结构对于元启发方法可以产生积极的影响，为改进和提高元启发方法性能提供了一种新思路。
2.针对胜者决定问题，提出了一种简单且快速的GRASP(GreedyRandomizedAdaptiveSearchProcedure)方法，它可以替代现行方法中的基于线性规划松弛法的求下界的方法。数值实验说明这种方法的求解质量和求解时间都要优于现有的线性规划松弛法。这种下界估计方法必然可以进一步提高精确方法的性能。找到并改正了已知最好的求解胜者决定问题的精确算法CABOB的两处错误，其中的一处错误导致这个算法成为一个非精确算法。这项工作提出了一条利用元启发方法提升精确方法性能的途径，这为元启发方法和精确方法的研究都提供了一种新思路。
3.在资源估计问题中引入了“影子约束”和“并发拓扑排序”两个概念，以此为基础，将解空间重构为{0，1}n的形式，并且提出了若干解空间降维的方法，降低了问题求解难度。这种解空间不仅适合应用元启发方法，更重要的是可以使一次搜索过程产生资源估计和调度两种信息。在此基础上构造了一种禁忌搜索方法，数值实验表明，它不仅可以很好的处理资源估计和调度产生这两项任务，而且可以以合理的时间代价求解大规模问题。这使得这个方法具备了很强的应用价值。这项工作对此类问题的解空间的重构和编码提供了一种范例，为处理这类问题提供了一种新思路。
4.提出了一种求解同步通讯模型条件下软硬件划分问题的元启发方法。给出了一种将同步通讯模型进行合理松弛，利用松弛后的模型产生出一种启发式软硬件划分指标的方法。在该指标的帮助下，可以构造一种GRASP方法来求解划分问题，并同时给出某个划分条件下的调度信息。数值实验表明，这种方法在稳定性和求解质量上都很突出。它所具备的求解大规模问题和给出近似最优调度这两个重要特点也使得它具备了很高的实用价值。这项工作给出了一种启发式方法和元启发方法结合的途径，为二者结合途径的研究提供了新思路。