發(fā)布時(shí)間：2018-06-09 06:10

  本文選題：組合優(yōu)化問(wèn)題 + 局部搜索算法��； 參考：《東北師范大學(xué)》2017年博士論文

【摘要】：組合優(yōu)化問(wèn)題是計(jì)算機(jī)科學(xué)與運(yùn)籌學(xué)的一個(gè)重要分支,主要是通過(guò)對(duì)數(shù)學(xué)方法的研究去尋找離散事件的最優(yōu)分組、編排、篩選或次序等。組合優(yōu)化問(wèn)題在信息技術(shù)、交通運(yùn)輸、通信網(wǎng)絡(luò)、經(jīng)濟(jì)管理等領(lǐng)域有著重要的應(yīng)用。求解組合優(yōu)化問(wèn)題的算法包括精確算法和啟發(fā)式算法,精確算法能夠求出問(wèn)題的最優(yōu)解,但是隨著問(wèn)題規(guī)模逐漸增大,求解這些問(wèn)題最優(yōu)解所需的計(jì)算量與存儲(chǔ)空間呈指數(shù)增長(zhǎng),會(huì)帶來(lái)所謂的“組合爆炸”現(xiàn)象,使得在現(xiàn)有的計(jì)算能力下,使用精確算法求得最優(yōu)解幾乎變得不可能。在這種情況下,一些啟發(fā)式算法應(yīng)運(yùn)而生,如局部搜索算法、松弛算法等。對(duì)于難解問(wèn)題實(shí)例,局部搜索算法可以在合理的時(shí)間內(nèi)找到近似最優(yōu)解或最優(yōu)解。同時(shí)局部搜索算法具有簡(jiǎn)單、高效、容易并行等優(yōu)點(diǎn)。局部搜索算法很容易實(shí)現(xiàn),對(duì)于優(yōu)化問(wèn)題,只要定義好解空間的鄰居結(jié)構(gòu),就可以用局部搜索算法來(lái)求解。目前已有很多研究表明了局部搜索算法的高效性,尤其在求解NP難問(wèn)題的較大實(shí)例,局部搜索算法有很大的潛力。由于很多局部搜索算法都加入了隨機(jī)策略,不同隨機(jī)種子的運(yùn)行就可實(shí)現(xiàn)并行。本論文中,我們對(duì)局部搜索算法進(jìn)行研究,并根據(jù)具體問(wèn)題的特點(diǎn)設(shè)計(jì)高效的算法。具體來(lái)說(shuō),我們選擇最小加權(quán)頂點(diǎn)覆蓋問(wèn)題、最小有容量支配集問(wèn)題和最小連通支配集問(wèn)題作為研究對(duì)象,設(shè)計(jì)高效的局部搜索算法。本文的主要研究工作和貢獻(xiàn)如下:(1)提出基于動(dòng)態(tài)打分策略和加權(quán)格局檢測(cè)策略的局部搜索算法(DLSWCC)求解最小加權(quán)頂點(diǎn)覆蓋問(wèn)題。在DLSWCC算法中,動(dòng)態(tài)打分策略在搜索陷入局部最優(yōu)時(shí)更新邊的權(quán)值,進(jìn)而改變頂點(diǎn)的分?jǐn)?shù),從而使搜索跳出局部最優(yōu)并向更優(yōu)的方向進(jìn)行;加權(quán)格局檢測(cè)策略考慮了每個(gè)頂點(diǎn)的環(huán)境信息,用來(lái)減少局部搜索中的循環(huán)問(wèn)題;結(jié)合以上兩個(gè)策略我們提出了頂點(diǎn)選擇方法,確定在局部搜索過(guò)程中加入或移出候選解的頂點(diǎn)。我們?cè)诖罅康臉?biāo)準(zhǔn)實(shí)例上對(duì)DLSWCC算法進(jìn)行了測(cè)試,實(shí)驗(yàn)結(jié)果表明DLSWCC算法要優(yōu)于現(xiàn)有最優(yōu)算法。(2)提出基于頂點(diǎn)懲罰策略和兩種模式的被支配頂點(diǎn)選擇策略的局部搜索算法(LS_PD)求解最小有容量支配集問(wèn)題。在LS_PD算法中,頂點(diǎn)懲罰策略在搜索陷入局部最優(yōu)時(shí)增加當(dāng)前未被支配頂點(diǎn)的罰值,罰值的改變會(huì)影響頂點(diǎn)的分?jǐn)?shù),使得算法跳出局部最優(yōu);兩種模式的被支配頂點(diǎn)選擇策略以的概率隨機(jī)選擇加入候選解的頂點(diǎn)支配哪些頂點(diǎn),以1-的概率貪心選擇;同時(shí)用強(qiáng)化策略來(lái)提高每個(gè)頂點(diǎn)容量的利用率,從而提高算法的性能。我們?cè)诠潭ㄈ萘亢妥兓萘康囊话銏D及UDG圖上對(duì)LS_PD算法進(jìn)行了對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明,無(wú)論是一般圖還是UDG圖,LS_PD算法都具有較高性能。(3)提出基于候選頂點(diǎn)集合和解的連接元素集合的GRASP算法求解最小連通支配集問(wèn)題。在GRASP算法中,在構(gòu)造初始候選解時(shí),加入候選頂點(diǎn)集合中的頂點(diǎn)不會(huì)破壞候選解的連通性;在搜索過(guò)程中,加入解的連接元素集合中的頂點(diǎn)會(huì)使不連通的候選解變?yōu)檫B通;此外,我們還使用評(píng)估函數(shù)定義了每個(gè)頂點(diǎn)的分?jǐn)?shù),禁忌策略來(lái)避免局部搜索重復(fù)訪(fǎng)問(wèn)以前搜索過(guò)的解。我們將GRASP算法與現(xiàn)有最優(yōu)啟發(fā)式算法和精確算法進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果表明GRASP算法在LPRNMR實(shí)例和隨機(jī)實(shí)例上效果很好,在MLSTP實(shí)例上只有少數(shù)稀疏圖效果不是很好。
[Abstract]:Combinatorial optimization is an important branch of computer science and operational research. It is mainly through the study of mathematical methods to find the optimal grouping, arrangement, selection and order of discrete events. The combinatorial optimization problem has an important application in the fields of information technology, transportation, communication network, economic management and so on. The algorithm includes the exact algorithm and the heuristic algorithm, and the exact algorithm can find the optimal solution of the problem. However, as the scale of the problem is increasing, the amount of computation and storage space for solving the optimal solutions of these problems is increasing exponentially, which will bring the so-called "combination explosion" phenomenon, making the exact algorithm under the existing computing power. In this case, some heuristic algorithms have come into being, such as local search algorithm, relaxation algorithm and so on. In the case of difficult problem, local search algorithm can find the approximate optimal solution or the optimal solution in a reasonable time. Meanwhile, the local search algorithm has the advantages of simple, efficient and easy to parallel. The local search algorithm is easy to implement. As long as the neighbor structure of the solution space is defined, the local search algorithm can be used to solve the problem. At present, many studies have shown the efficiency of the local search algorithm. In particular, the local search algorithm has great potential to solve the problem of NP difficult problem. In this paper, we study local search algorithms and design efficient algorithms based on the characteristics of the specific problems. In this paper, we choose the minimum weighted vertex cover problem, the smallest capacity domination set problem and the minimum connected dominating set question. The main research work and contribution of this paper are as follows: (1) a local search algorithm (DLSWCC) based on dynamic scoring strategy and weighted pattern detection strategy (DLSWCC) is proposed to solve the minimum weighted vertex cover problem. In the DLSWCC algorithm, the dynamic scoring strategy is updated when the search is in the local optimum. The weight of the edge changes the score of the vertex, thus making the search out of the local optimal and in the better direction. The weighted pattern detection strategy takes into account the environmental information of each vertex, and uses it to reduce the circulation problem in the local search. In combination with the above two strategies, we propose a vertex selection method to determine the addition of the local search process to the local search process. We enter or remove the vertices of the candidate solutions. We test the DLSWCC algorithm on a large number of standard instances. The experimental results show that the DLSWCC algorithm is superior to the existing optimal algorithm. (2) the local search algorithm (LS_PD) is proposed to solve the minimum capacity dominating set problem based on the vertex penalty strategy and the two patterns of the dominant vertex selection strategy (LS_PD). In the LS_PD algorithm, the vertex penalty strategy increases the penalty value of the current non dominated vertex when searching for local optimal. The change of penalty will affect the points of the vertex and make the algorithm jump out of the local optimal. The probability random selection of the two modes of the dominant vertex selection strategy is the vertex dominated by the candidate solution and the probability of 1- Greedy choice; at the same time using the strengthening strategy to improve the utilization of each vertex capacity, and thus improve the performance of the algorithm. We compare the LS_PD algorithm with the general diagram of the fixed capacity and the change capacity and the UDG diagram. The experimental results show that both the general and the UDG diagram, the LS_PD algorithm has high performance. (3) proposed based on the weather condition. In the GRASP algorithm, the vertices in the set of candidate vertices will not destroy the connectivity of the candidate solutions in the construction of the initial candidate solutions in the GRASP algorithm. In the search process, the vertices of the join element set in the solution will change the disconnected candidate solutions. In addition, we also use the evaluation function to define the scores of each vertex, the tabu strategy to avoid the repeated access to the previously searched solutions. We compare the GRASP algorithm with the existing optimal heuristic algorithm and the exact algorithm. The experimental results show that the GRASP algorithm has a good effect on the LPRNMR instance and the random instance, in M Only a few sparse graphs on LSTP instances are not very effective.
【學(xué)位授予單位】：東北師范大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2017
【分類(lèi)號(hào)】：O22

【參考文獻(xiàn)】

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

1 王辰尹;倪耀東;柯華;;模糊環(huán)境下的最小權(quán)頂點(diǎn)覆蓋問(wèn)題[J];計(jì)算機(jī)應(yīng)用研究;2012年01期

，

本文編號(hào)：1999311