若干集合覆盖问题的方法研究

发布时间：2018-03-17 19:23

本文选题：经典最小集合覆盖问题　切入点：最小加权集合覆盖问题　出处：《吉林大学》2017年博士论文　论文类型：学位论文

【摘要】：集合覆盖是一个重要的组合优化问题,被广泛应用于人工智能不同的领域。近年来,其关键性子问题研究主要集中在经典最小集合覆盖问题、最小加权集合覆盖问题、极小集合覆盖问题和最大集合K覆盖问题,它们具有非常重要的研究意义和广泛的应用领域。本文将围绕上述四个集合覆盖子问题展开,旨在为不同应用需求子问题设计对应的高效求解方法。针对集合覆盖子问题,求解方法主要分成两大类:精确求解方法和启发式求解方法。使用精确求解方法解决时,可以保证得到的候选解是最优解。但随着求解问题规模不断扩大,精确求解方法的求解时间呈指数上升,此时无法保证在可接受的时间内返回一个候选解。启发式方法在合理的求解时间内能够获得一个尽可能好的候选解,但是不能保证这个候选解是最优解。因此,启发式方法适用于大规模问题以及对解的质量要求不过于苛刻的情况。在实际应用中,经典最小集合覆盖问题,最小加权集合覆盖问题和最大集合K覆盖问题所需要处理的问题规模往往较大,此时使用精确求解方法很难进行有效求解。针对这三个问题,本文针对其分别提出启发式求解方法:针对经典最小集合覆盖问题,本文提出一种迭代局部搜索求解方法,该方法使用三个策略:超图边配置检测策略、权值变化策略和超图边选择策略;针对最小加权集合覆盖问题,本文提出一种新的局部搜索框架并辅以带有问题化简的预处理、低复杂度的初始化策略和多值随机选择策略;针对最大集合K覆盖问题,本文提出一种重启局部搜索方法,该方法使用了随机重启初始化和快速邻居搜索两个策略。由于极小集合覆盖问题对解的质量要求较高,而启发式求解方法得到的候选解精度较低。针对此问题,本文提出一种精确极小集合覆盖求解方法,该方法将极小集合覆盖问题转化为约束可满足问题,然后再进行求解。具体工作如下:1)对于经典最小集合覆盖问题,提出一种基于迭代局部搜索的uSLC方法。该方法使用超图形式表示经典最小集合覆盖问题,辅以三个策略对问题求解效率进行提高:超图边配置检测策略、权值变化策略和超图边选择策略。其中,超图配置检测策略阻止uSLC方法陷入局部最优,且避免局部搜索中循环问题的发生;权值变化策略用于改变被当前候选解覆盖和未覆盖超图顶点的权值,目的是增加uslc方法得到候选解的多样性;超图边选择策略结合上述两个策略,进而更加有效地发现质量更高的候选解。在传统测试用例上的实验结果表明:uslc方法求解性能在大多数情况下明显好于其他方法。当uslc方法和其他方法求得最优解的质量相同时,uslc方法的求解效率相比其他方法快了1到2个数量级。同时,对于其中11个传统测试用例,uslc方法得到了质量更高的最优解。2)针对最小加权集合覆盖问题,提出一种基于新局部搜索框架的wscls求解方法。同时,设计三个策略进一步提高wscls求解方法的效率:带有问题化简的预处理、低复杂度的初始化策略和多值随机选择策略。带有问题化简的预处理可以化简大规模的测试问题,进而缩减搜索空间;使用低复杂度的初始化策略可以在更短的时间内得到一个较好的初始解;在删除子集过程中,使用多值随机选择策略可以更快更好地找到需要删除的子集。实验结果表明wscls求解方法在大规模测试问题上得到解的质量好于其它的求解方法。3)针对极小集合覆盖问题(也可以称作极小碰集问题),给出利用csp求解器求解极小碰集的csp-mhs方法。该方法首先用约束可满足问题的描述形式对极小碰集问题进行表示,然后再调用csp求解器对问题进行求解。csp-mhs方法属于精确求解方法,因此可以保证返回候选解的完备性。同时,本文还提出hard-冲突集和soft-冲突集概念,提高求解方法对于带有特定特征极小碰集问题的求解效率。实验结果表明,对比目前最好的方法,csp-mhs方法的求解时间更短。4)针对最大集合k覆盖问题,提出一种重启局部搜索rnkc方法,该方法同时使用一种改进的随机重启策略和一种改进的邻域搜索策略。在初始化过程中,rnkc方法利用一个随机重启策略处理局部搜索方法中的循环问题同时保证初始候选解的多样性;在构造候选解的过程中,rnkc方法使用一个邻域搜索策略探索所有邻域,目的是尽可能多地发现可行候选解,进一步提高候选解的质量。rnkc方法和目前求解效率较高的cplex求解器(ibm公司)在大量经典测试用例上的实验结果表明,rnkc方法在求解效率和所得最优解质量上均占优势。同时对于部分用例,rnkc方法可以在更短时间内发现更好的最优解。
[Abstract]:Set covering is an important combinatorial optimization problem, has been widely used in different fields of artificial intelligence. In recent years, the key sub problems research mainly concentrated in the classical minimal set covering problem, the minimum weighted set covering problem, the minimal set covering problem and the maximum K set covering problem, it has very important research significance and a wide range of applications. This paper will focus on these four sets cover issues, designed for efficient solution method for different application requirements of sub problem corresponding to the design. According to the set cover problem solving method, mainly divided into two categories: exact solution method and heuristic method. To solve the use of exact solution, can be guaranteed the candidate solution is optimal. But with the problem of expanding, the solution time accurate calculating method is rising exponentially, this cannot be guaranteed in the ground By the time returns a candidate solution. The heuristic method can obtain a best possible candidate solutions in solving the reasonable time, but can not guarantee that the candidate solution is the optimal solution. Therefore, the heuristic method is applicable to large-scale problems and solutions to the quality requirements are not too demanding. In practical application. The classical minimum set covering problem, the minimum weighted set covering problem is larger and the maximum set of K coverage problems need to deal with the problem of scale, this time using the precise solving method is difficult to solve. To solve these three problems, this paper proposes a heuristic method for respectively: according to the classical minimum set cover problem, this paper proposes a iterative local search method, the method uses three strategies: edgeset configuration detection strategy, weight change strategy and edgeset selection strategy for the minimum weighted set; He proposed the pretreatment coverage problem, a new local search framework and complemented by the problem of the low complexity initialization strategy and multi valued random selection strategy; for the largest collection of K covering problems, this paper proposes a restart local search method, this method uses random restart initialization and fast neighbor search the two strategy. As minimal set covering problem requires high quality of the solution, and a heuristic method for the candidate solution of low precision. Aiming at this problem, this paper presents an accurate minimal set covering method, the method of minimum set covering problem is transformed into a constraint satisfaction problem, and then solve the specific work. Are as follows: 1) for the coverage problem of classical minimum set, proposes a uSLC iterative method based on local search. The method uses the form of hypergraph covering problem classical minimal set, With the three strategies of solving efficiency: improve the edgeset configuration detection strategy, weight change strategy and edgeset selection strategy. Among them, the allocation of detection strategy to prevent uSLC hypergraph method into local optimum, and avoid the local search in the circulation problem; weight change strategy for changing the current candidate solution is covered and uncovered a hypergraph vertex weights, objective is to increase the uslc method to get the diversity of candidate solutions; the edgeset selection strategy by combining the two strategies, and more effective to find better solutions. In the traditional test cases show that the experimental results: uslc method to solve the performance in most cases is better than other methods when. Uslc method and other methods to obtain the optimal solution of the same quality, for the efficiency of the uslc method compared with other methods by 1 to 2 orders of magnitude. At the same time, for the traditional 11 Test case, uslc method to get the optimal solution of the higher quality.2) according to the minimum weighted set covering problem, put forward a new method to solve the wscls framework based on local search. At the same time, the design of the three strategies to further improve the efficiency of wscls method: pretreatment with problem simplification, low complexity and initialization strategy multi valued random selection strategy. With the problem of pretreatment can simplify large-scale test problems, thus reducing the search space; using a low complexity initialization strategy can get a good beginning early in a shorter period of time; in a subset of delete process, using multiple valued random selection strategy can better and faster to find need to delete the subset. The experimental results show that the wscls method obtained good quality solution to other methods of.3 in large scale test problems) for minimal set covering problem (also available Called to minimal hitting sets), the csp-mhs method is solved by CSP hitting set minimum. This method first uses constraint satisfaction problem described in the form of minimal hitting set problem representation, then call the CSP solver to solve the method of.Csp-mhs problem belongs to the precise solution method, which can ensure the completeness of the candidate returns solution. At the same time, this paper also put forward the hard- set and soft- set the concept of conflict conflict, improve the efficiency of solving method for solving specific features with minimal hitting sets. Experimental results show that, comparing with the current best method, csp-mhs method for shorter time.4) for the largest collection of K coverage problem, propose a restart rnkc local search at the same time, an improved random restart strategy and an improved neighborhood search strategy. In the initialization process, the rnkc method using a random restart Cycle strategy to deal with local search methods in while ensuring the diversity of initial solutions; in the process of constructing candidate solutions, the rnkc method uses a neighborhood search strategy to explore all the neighborhood, the purpose is as much as possible to find the feasible candidate solutions, to further improve the quality of candidate solutions and the.Rnkc method improve the efficiency of solving CPLEX Solver (IBM) in a large number of classic test cases. The experimental results indicate that the rnkc method had an advantage in solving efficiency and the quality of the optimal solution. At the same time, for some cases, the rnkc method can find better optimal solution in a shorter period of time.

【学位授予单位】：吉林大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：O224

【相似文献】