本文選題：經(jīng)典最小集合覆蓋問題　切入點(diǎn)：最小加權(quán)集合覆蓋問題　出處：《吉林大學(xué)》2017年博士論文　論文類型：學(xué)位論文

【摘要】：集合覆蓋是一個(gè)重要的組合優(yōu)化問題,被廣泛應(yīng)用于人工智能不同的領(lǐng)域。近年來,其關(guān)鍵性子問題研究主要集中在經(jīng)典最小集合覆蓋問題、最小加權(quán)集合覆蓋問題、極小集合覆蓋問題和最大集合K覆蓋問題,它們具有非常重要的研究意義和廣泛的應(yīng)用領(lǐng)域。本文將圍繞上述四個(gè)集合覆蓋子問題展開,旨在為不同應(yīng)用需求子問題設(shè)計(jì)對(duì)應(yīng)的高效求解方法。針對(duì)集合覆蓋子問題,求解方法主要分成兩大類:精確求解方法和啟發(fā)式求解方法。使用精確求解方法解決時(shí),可以保證得到的候選解是最優(yōu)解。但隨著求解問題規(guī)模不斷擴(kuò)大,精確求解方法的求解時(shí)間呈指數(shù)上升,此時(shí)無法保證在可接受的時(shí)間內(nèi)返回一個(gè)候選解。啟發(fā)式方法在合理的求解時(shí)間內(nèi)能夠獲得一個(gè)盡可能好的候選解,但是不能保證這個(gè)候選解是最優(yōu)解。因此,啟發(fā)式方法適用于大規(guī)模問題以及對(duì)解的質(zhì)量要求不過于苛刻的情況。在實(shí)際應(yīng)用中,經(jīng)典最小集合覆蓋問題,最小加權(quán)集合覆蓋問題和最大集合K覆蓋問題所需要處理的問題規(guī)模往往較大,此時(shí)使用精確求解方法很難進(jìn)行有效求解。針對(duì)這三個(gè)問題,本文針對(duì)其分別提出啟發(fā)式求解方法:針對(duì)經(jīng)典最小集合覆蓋問題,本文提出一種迭代局部搜索求解方法,該方法使用三個(gè)策略:超圖邊配置檢測(cè)策略、權(quán)值變化策略和超圖邊選擇策略;針對(duì)最小加權(quán)集合覆蓋問題,本文提出一種新的局部搜索框架并輔以帶有問題化簡(jiǎn)的預(yù)處理、低復(fù)雜度的初始化策略和多值隨機(jī)選擇策略;針對(duì)最大集合K覆蓋問題,本文提出一種重啟局部搜索方法,該方法使用了隨機(jī)重啟初始化和快速鄰居搜索兩個(gè)策略。由于極小集合覆蓋問題對(duì)解的質(zhì)量要求較高,而啟發(fā)式求解方法得到的候選解精度較低。針對(duì)此問題,本文提出一種精確極小集合覆蓋求解方法,該方法將極小集合覆蓋問題轉(zhuǎn)化為約束可滿足問題,然后再進(jìn)行求解。具體工作如下:1)對(duì)于經(jīng)典最小集合覆蓋問題,提出一種基于迭代局部搜索的uSLC方法。該方法使用超圖形式表示經(jīng)典最小集合覆蓋問題,輔以三個(gè)策略對(duì)問題求解效率進(jìn)行提高:超圖邊配置檢測(cè)策略、權(quán)值變化策略和超圖邊選擇策略。其中,超圖配置檢測(cè)策略阻止uSLC方法陷入局部最優(yōu),且避免局部搜索中循環(huán)問題的發(fā)生;權(quán)值變化策略用于改變被當(dāng)前候選解覆蓋和未覆蓋超圖頂點(diǎn)的權(quán)值,目的是增加uslc方法得到候選解的多樣性;超圖邊選擇策略結(jié)合上述兩個(gè)策略,進(jìn)而更加有效地發(fā)現(xiàn)質(zhì)量更高的候選解。在傳統(tǒng)測(cè)試用例上的實(shí)驗(yàn)結(jié)果表明:uslc方法求解性能在大多數(shù)情況下明顯好于其他方法。當(dāng)uslc方法和其他方法求得最優(yōu)解的質(zhì)量相同時(shí),uslc方法的求解效率相比其他方法快了1到2個(gè)數(shù)量級(jí)。同時(shí),對(duì)于其中11個(gè)傳統(tǒng)測(cè)試用例,uslc方法得到了質(zhì)量更高的最優(yōu)解。2)針對(duì)最小加權(quán)集合覆蓋問題,提出一種基于新局部搜索框架的wscls求解方法。同時(shí),設(shè)計(jì)三個(gè)策略進(jìn)一步提高wscls求解方法的效率:帶有問題化簡(jiǎn)的預(yù)處理、低復(fù)雜度的初始化策略和多值隨機(jī)選擇策略。帶有問題化簡(jiǎn)的預(yù)處理可以化簡(jiǎn)大規(guī)模的測(cè)試問題,進(jìn)而縮減搜索空間;使用低復(fù)雜度的初始化策略可以在更短的時(shí)間內(nèi)得到一個(gè)較好的初始解;在刪除子集過程中,使用多值隨機(jī)選擇策略可以更快更好地找到需要?jiǎng)h除的子集。實(shí)驗(yàn)結(jié)果表明wscls求解方法在大規(guī)模測(cè)試問題上得到解的質(zhì)量好于其它的求解方法。3)針對(duì)極小集合覆蓋問題(也可以稱作極小碰集問題),給出利用csp求解器求解極小碰集的csp-mhs方法。該方法首先用約束可滿足問題的描述形式對(duì)極小碰集問題進(jìn)行表示,然后再調(diào)用csp求解器對(duì)問題進(jìn)行求解。csp-mhs方法屬于精確求解方法,因此可以保證返回候選解的完備性。同時(shí),本文還提出hard-沖突集和soft-沖突集概念,提高求解方法對(duì)于帶有特定特征極小碰集問題的求解效率。實(shí)驗(yàn)結(jié)果表明,對(duì)比目前最好的方法,csp-mhs方法的求解時(shí)間更短。4)針對(duì)最大集合k覆蓋問題,提出一種重啟局部搜索rnkc方法,該方法同時(shí)使用一種改進(jìn)的隨機(jī)重啟策略和一種改進(jìn)的鄰域搜索策略。在初始化過程中,rnkc方法利用一個(gè)隨機(jī)重啟策略處理局部搜索方法中的循環(huán)問題同時(shí)保證初始候選解的多樣性;在構(gòu)造候選解的過程中,rnkc方法使用一個(gè)鄰域搜索策略探索所有鄰域,目的是盡可能多地發(fā)現(xiàn)可行候選解,進(jìn)一步提高候選解的質(zhì)量。rnkc方法和目前求解效率較高的cplex求解器(ibm公司)在大量經(jīng)典測(cè)試用例上的實(shí)驗(yàn)結(jié)果表明,rnkc方法在求解效率和所得最優(yōu)解質(zhì)量上均占優(yōu)勢(shì)。同時(shí)對(duì)于部分用例,rnkc方法可以在更短時(shí)間內(nèi)發(fā)現(xiàn)更好的最優(yōu)解。
[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.

【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2017
【分類號(hào)】：O224

【相似文獻(xiàn)】

相關(guān)期刊論文 前4條

1 陳韜;吳志勇;孫樂昌;張e，

本文編號(hào)：1626150