针对非确定和大规模限容量弧路径问题的近似算法

发布时间：2018-06-01 01:13

本文选题：组合优化 + 限容量弧路径问题　；参考：《中国科学技术大学》2016年博士论文

【摘要】：限容量弧路径问题是一个经典的组合优化问题。它可以归结为在一个给定的连通图上寻找经过图中某些边并满足特定约束条件的最优回路集。限容量弧路径问题在现实生活中有着极为广泛的应用,如冬季路面撒盐、城市垃圾清理及物流运输等实际应用均可被抽象为限容量弧路径问题。此类问题在现代工业和民生中有着重要的地位。因此,近年来,限容量弧路径问题获得了越来越多的研究关注,发展出各式各样的问题模型与求解方法。然而,研究工作与实际应用间尚存在一定的差距。大部分研究工作均局限于确定性问题模型,且所能求解的问题规模较小,而实际应用中往往存在许多不确定因素,问题规模也往往超出已有方法的能力范围,因而导致这些研究工作无法直接应用于大部分的实际问题。基于此,本文主要研究上述有着广泛应用需求却在一定程度上被研究者们忽视的问题模型—非确定限容量弧路径问题与大规模限容量弧路径问题。本文研究的第一个问题——非确定限容量弧路径问题是近年来提出的新的问题变种。该问题考虑了实际应用中的四个不确定因素：任务的需求量,边的消耗,任务的存在性以及边的存在性,问题目标为求解所有可能的环境下鲁棒性最优的解。相比以往的确定性问题模型,非确定限容量弧路径问题更贴近实际应用,然而,由于其提出时间较晚且求解难度较大,现有的研究中尚不存在针对该问题模型的有效解法。考虑到在许多实际问题中,我们往往无法得知问题所包含随机变量的底层分布,从而无法建立对应的概率模型对其进行求解。因此,本文采用样本近似的方法来对非确定问题进行建模,将原问题表达为一组确定的样本问题,并求解针对样本问题集的鲁棒解。我们首先选择期望性能作为鲁棒性评价标准,提出基于多种群的模因算法(Memetic Algorithm with Multiple Population, MAMP)。MAMP的核心思想在于：对每个样本维护一个种群,在算法运行过程中通过种群选择机制从样本实例层面调控算法的搜索偏好,避免算法陷入较易求解的样本而忽略了较难求解的样本；在局部搜索过程中,使用合并-拆分算子从问题解的层面调控算法的搜索方向,避免算法在单个样本实例解空间中陷入局部最优。实验表明,通过上述两个层面对算法搜索方向的引导,MAMP相比现有算法具有更好的寻求全局最优解的能力。但由于使用了较为耗时的局部搜索算子以及对中间解的适应度评估较为耗时,MAMP算法需要更多的运行时间。随后,我们采用最坏情况下的性能作为鲁棒性评价标准。针对搜索过程中解的适应度评估较为耗时的问题,设计了一个可以避免无效适应度计算的随机局部搜索方法,并将其与分布估计算法结合,得到一个兼顾性能与效率的算法Estimation of Distribution Algorithm with Stochastic Local Search (EDASLS)。该算法通过学习种群中优质个体所蕴含的任务之间紧密度的信息,建立分布模型。然后利用此模型生成新的解并在随机局部搜索中避免无效的适应度计算。实验表明,EDASLS可获得比其他算法鲁棒性更优的解。在算法的运行时间上,EDASLS也表现出较强的优势,在适应度评估次数相同的情况下,EDASLS需要的运行时间更短。更进一步的实验表明,EDASLS的优越性主要归功于随机局部搜索,该方法可以在不影响算法性能的前提下,大大提升算法运行速度。本文研究的另一个问题——大规模限容量弧路径问题本质上是一个基本限容量弧路径问题,但是由于其问题规模较大,现有的研究方法均无法在可接受的时间内给出问题的一个质量上可被接受的解。基于上述原因,本文提出一个基于层次分解的对问题规模具有可扩展性的算法Scalable Approach based on Hierarchical Decomposition (SAHiD),该算法的可扩展性表现在当问题规模(任务数)急速增长时,算法仍能在给定的较短时间(例如30分钟)内给出一个质量较优的解。通过对任务集以层次分解的方式进行组合排序,SAHiD可以快速生成具有较高质量的初始解。上述层次分解操作耗时极短,因而可被嵌入迭代搜索过程中以不断提升解的质量。为了验证SAHiD算法的可扩展性,我们根据合肥市和北京市的真实交通路网生成了两个问题规模逐渐增大的测试集Hefei与Beijing,并在上述问题集上将SAHiD与现有的求解传统限容量弧路径问题的优秀算法和专为大规模问题设计的算法进行了比较。实验结果表明,无论是从(得到质量相当的解需要的)运算时间还是从(给定时间内能求得的)解的质量来看,SAHiD表现出优异的性能,而现有的算法性能则不尽如人意。尤其是在规模较大(任务数超过400)的问题实例上,现有优秀算法均无法在给定时间内给出该问题的一个质量上可被接受的次优解。在现有的规模最大的问题集egl-large上,SAHiD虽然不能得到最优的最终解,但在计算时间相当少的情况下,SAHiD可以得到比其他算法更优秀的解。因此,在需要较快得到问题的解(分钟级甚至是秒级)的情况下,SAHiD是一个更好的选择。
[Abstract]:In recent years , the problem of limited capacity arc path has been more and more closely related to the practical application . However , because of the fact that there are many uncertain factors in the practical application , the problem of limited capacity arc path is not directly applicable to most practical problems . The core idea of MAMP is to maintain a population for each sample . In the process of algorithm operation , the search preferences of the algorithm are adjusted from the sample case level through the population selection mechanism , so that the algorithm is avoided into a sample which is easy to be solved , and the sample which is difficult to be solved is ignored ;
In the process of local search , we use the merging - splitting operator to adjust the searching direction of the algorithm from the plane of the problem solution and avoid the local optimal solution in the solution space of the single sample .
【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP301.6

【相似文献】