支配集是圖論中的重要概念,支配集的許多變種問題,如獨(dú)立支配集、連通支配集、完全支配集等,在科學(xué)研究和工程實(shí)踐的許多領(lǐng)域有著廣泛應(yīng)用,包括編碼理論、圖像處理、數(shù)值分析、密碼學(xué)、信息檢索,以及通信基礎(chǔ)設(shè)施的布局、城市交通路線規(guī)劃等。人們?cè)谘芯窟^程中發(fā)現(xiàn),支配集的這些變種問題,往往是NP(非確定性多項(xiàng)式,Non-deterministic Polynomial)困難問題,即在多項(xiàng)式時(shí)間內(nèi)難以獲得最優(yōu)解。近年來,啟發(fā)式算法和進(jìn)化算法在求解支配集及其變種問題上取得了較好的效果,盡管如此,它們?cè)谇蠼舛嗉s束、多變量以及高度非線性等性質(zhì)的復(fù)雜優(yōu)化問題時(shí),尤其是對(duì)大規(guī)模圖的實(shí)例仍有不足。因此,本文針對(duì)性地就支配集及其變種問題的求解方面提出有效的優(yōu)化算法,其中包括:最小支配集問題、最小獨(dú)立支配集問題,以及最小完全支配集問題的搜索算法求解。在求解的過程中,我們引入了進(jìn)化算法和局部搜索等策略,針對(duì)這些支配集的問題設(shè)計(jì)高效的求解算法。經(jīng)過在基準(zhǔn)測試數(shù)據(jù)上進(jìn)行的一系列實(shí)驗(yàn)表明,所提出的算法具有顯著效果。本文的主要工作包括以下幾個(gè)方面:(1)最小支配集(Minimum Dominating Set,簡記為MDS)問題是支配集問題的一個(gè)重要子問題。對(duì)于經(jīng)典的最小支配集問題,以往的啟發(fā)式求解方法能夠得到可以接受的解,但是現(xiàn)實(shí)生活中往往是大規(guī)模的組合優(yōu)化問題,面對(duì)這樣問題,這些啟發(fā)式算法的求解表現(xiàn)差強(qiáng)人意�；谏鲜銮闆r,我們重點(diǎn)關(guān)注在大規(guī)模實(shí)例上求解最小支配集問題的方法研究。通過對(duì)大規(guī)模實(shí)例的分析,結(jié)合支配集問題的特點(diǎn),提出了一個(gè)快速高效地求解最小支配集問題的算法FastMDS。在FastMDS算法的求解過程中,首先在預(yù)處理過程中對(duì)問題進(jìn)行了有效化簡,在初始化過程中采用了低復(fù)雜度的策略,在算法迭代過程中引入隨機(jī)算子對(duì)頂點(diǎn)進(jìn)行選擇。通過一系列的實(shí)驗(yàn)表明,我們所提出的FastMDS算法,較目前主流的啟發(fā)式問題求解算法更為高效。(2)最小完全支配集(Minimum Total Dominating Set,簡記為MTDS)問題是經(jīng)典支配集問題的變體。在本文中,我們提出一種結(jié)合局部搜索和遺傳算法的混合進(jìn)化算法來求解最小完全支配集問題。在算法中采用一種新穎的評(píng)分啟發(fā)式方法,以提高搜索效率并獲得了更好的解決方案。針對(duì)MTDS問題求解,在初始化階段,首先創(chuàng)建一個(gè)包括一些初始解的種群,使算法能夠搜索更多區(qū)域。在局部搜索階段,通過迭代地交換頂點(diǎn)來優(yōu)化初始解決方案,并使用基于修復(fù)的交叉算子創(chuàng)建新的解來使算法搜索更多可行的區(qū)域。為了證明算法的有效性和性能,我們?cè)诮?jīng)典的基準(zhǔn)DIMACS上進(jìn)行了一系列的實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明,我們提出的算法較其他算法具有更好的性能。(3)最小獨(dú)立支配集(Minimum Independent Dominating Set,簡記為MIDS)問題是一個(gè)經(jīng)典的組合優(yōu)化問題,并在現(xiàn)實(shí)生活中得到了廣泛的應(yīng)用。針對(duì)MIDS問題求解,設(shè)計(jì)了一種新的基于禁忌策略的局部搜索算法和兩階段移除策略,包括雙檢查移除策略和隨機(jī)多樣性移除策略。雙檢查移除策略對(duì)剛剛移除的頂點(diǎn)的第二層鄰域進(jìn)行檢查并確認(rèn)是否對(duì)該頂點(diǎn)進(jìn)行移除,以打破獨(dú)立性的限制;當(dāng)候選解的質(zhì)量經(jīng)過多次迭代后仍然沒有得到改善時(shí),可以采用隨機(jī)多樣性移除策略,該策略動(dòng)態(tài)貪婪地刪除大量的頂點(diǎn),然后將隨機(jī)游走引入到添加頂點(diǎn)的修復(fù)過程中,以逃離次優(yōu)的搜索空間。我們?cè)贒IMACS和BHOSLIB兩個(gè)經(jīng)典的基準(zhǔn)上進(jìn)行了一系列的實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明,我們所提出的算法在求解MIDS問題上明顯優(yōu)于目前的啟發(fā)式算法。
【學(xué)位單位】：東北師范大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位年份】：2019
【中圖分類】：TP18;O157.5
【部分圖文】：

圖 1. 1 密母算法流程示意圖密母（Memes）一詞代表信息的傳播[23]。密母算法代表了進(jìn)化計(jì)算研究領(lǐng)域的最新發(fā)展，一般是在求解過程中，將進(jìn)化計(jì)算或是其他基于種群的方法，與獨(dú)立個(gè)體學(xué)習(xí)或是局部增強(qiáng)過程相結(jié)合，而對(duì)算法進(jìn)行深入研究[24]。密母算法往往也被稱之為混合進(jìn)化算法（Hybrid Evolutionary Algorithms）、Baldwinian 進(jìn)化算法（BaldwinianEvolutionary Algorithms ） 、 Lamarckia 進(jìn) 化 算 法 （ Lamarckia EvolutionaryAlgorithms）、文化算法（Cultural Algorithms）或是遺傳局部搜索（Genetic LocalSearch）等。對(duì)于復(fù)雜的優(yōu)化問題，許多密母算法的不同實(shí)例已經(jīng)應(yīng)用到廣泛領(lǐng)域，通常能夠較傳統(tǒng)優(yōu)化算法獲得高質(zhì)量的解。與不同智能優(yōu)化算法的結(jié)合，相應(yīng)的密母算法也不同，比較常見的密母算法包括：混合遺傳算法[25]、混合免疫算法[26]、混合粒子群算法[27]、混合蟻群算法[28]、混合蜂群算法[29]等等。進(jìn)一步地，將密母應(yīng)用到計(jì)算框架中，稱為密母計(jì)算（Memetic Computing），對(duì)于求解優(yōu)化問題，特別是在處理與其他確定性優(yōu)化技術(shù)相結(jié)合的進(jìn)化算法領(lǐng)域，密母計(jì)算將密母（Memes）的概念擴(kuò)展到知識(shí)增強(qiáng)過程或表示的概念實(shí)體。

2.1 圖的基本概念1736 年，瑞士數(shù)學(xué)家歐拉在它的一篇論文中討論了哥尼斯堡（Konigsberg）七橋問題，由此產(chǎn)生了一個(gè)全新的數(shù)學(xué)分支——圖論（graph theory）。在此，我們也引用哥尼斯堡七橋問題的例子中的問題啟發(fā)而給出圖的基本定義。除本文定義的術(shù)語外，其他圖論相關(guān)的術(shù)語可以參考《圖論及其應(yīng)用》[43]，Gary Chartrand 和 Ping Zhang 的《Introduction to Graph Theory》[44]和 Douglas B. West 的《Introduction to Graph Theor(Second Edition)》[45]。例哥尼斯堡七橋問題。哥尼斯堡市座落于普魯士的普萊格爾河畔，在它的一個(gè)公園里，有 7 座橋?qū)⑵杖R格爾河中的兩個(gè)島以及島與河的兩岸連接起來，在圖 2.1 的左圖中用 A、B、C、D 分別表示 4 塊陸地區(qū)域。市民們想知道如果他們從這 4 塊陸地區(qū)域中任一塊出發(fā)，經(jīng)過每座橋恰好一次，能否返回原點(diǎn)。該問題被簡化為遍歷圖 2.1 的右側(cè)的圖，圖中黑色頂點(diǎn)表示陸地，線表示橋。

定理 2-3 支配集問題是 NP 完全問題[52]。證明：（1）給定圖 = ( , )，對(duì)于任意頂點(diǎn)集合 和正整數(shù) t，如果滿足條件| | ≤ ，則可以在多項(xiàng)式時(shí)間內(nèi)判斷集合 S 是否為圖 G 的一個(gè)支配集的結(jié)論，即∈ 。（2）引出 3-SAT（boolean SATisfiability problem）問題。給定一個(gè)有窮的布爾變量集合 U 和子句集合 C，是否存在一個(gè)真值賦值，使得子句集合 C 為真，即其中的每個(gè)子句為真。3-SAT 的實(shí)例為 = { , , , }， = { , , , }為每個(gè)變量的賦值，只要驗(yàn)證每個(gè)子句都為真即可。很明顯，可以在多項(xiàng)式時(shí)間內(nèi)完成該驗(yàn)證，即 3SAT 問題為 NP 完全問題。下面，將 3-SAT 變換為支配集問題（ ），如圖 2.2[52]所示。
【相似文獻(xiàn)】

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

1 駱偉忠;馮啟龍;王建新;陳建二;;完全p-支配集的參數(shù)算法[J];計(jì)算機(jī)學(xué)報(bào);2013年09期

2 王康;禹繼國;;無線網(wǎng)絡(luò)中一種簡單的弱連通支配集構(gòu)造策略[J];計(jì)算機(jī)工程與應(yīng)用;2011年20期

3 李鎮(zhèn)堅(jiān);葛啟;王海濤;朱洪;;圖的支配集若干問題的研究[J];計(jì)算機(jī)科學(xué);2007年01期

4 黃民肅;向東;;無線自組網(wǎng)絡(luò)中的基于多個(gè)支配集的路由協(xié)議[J];計(jì)算機(jī)應(yīng)用研究;2007年05期

5 吳迪;梁輝;王光興;;無線自組網(wǎng)簇間網(wǎng)關(guān)支配集優(yōu)化策略[J];計(jì)算機(jī)工程;2007年24期

6 孫立山;郝燕玲;;能量限制的連通支配集分布式構(gòu)造[J];計(jì)算機(jī)工程與應(yīng)用;2006年32期

7 蘇岐芳;圖的支配集的有效算法[J];臺(tái)州學(xué)院學(xué)報(bào);2003年06期

8 張光鐸，王正志;圖論中獨(dú)立支配集的最佳求解算法研究[J];國防科技大學(xué)學(xué)報(bào);1995年02期

9 沈湘鐘;黃友銳;吳建坤;;基于連通支配集的無線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴ǚ抡嫜芯縖J];儀表技術(shù)與傳感器;2016年09期

10 趙學(xué)鋒;;求解最小連通r-跳k-支配集的啟發(fā)式算法[J];計(jì)算機(jī)工程;2012年21期

相關(guān)博士學(xué)位論文 前10條

1 袁福宇;若干支配集優(yōu)化問題求解的方法研究[D];東北師范大學(xué);2019年

2 施韋;移動(dòng)Ad Hoc網(wǎng)絡(luò)中連通支配集若干關(guān)鍵問題的研究[D];浙江大學(xué);2007年

3 汪文勇;無線傳感器網(wǎng)絡(luò)若干節(jié)能關(guān)鍵技術(shù)研究[D];電子科技大學(xué);2011年

4 駱偉忠;無線網(wǎng)絡(luò)中若干NP-難問題的參數(shù)算法[D];中南大學(xué);2012年

5 劉卓;無線傳感器網(wǎng)絡(luò)拓?fù)浣⒎椒ㄅc應(yīng)用技術(shù)研究[D];華中科技大學(xué);2011年

6 陶凱;廣域定向MANET組網(wǎng)關(guān)鍵技術(shù)研究[D];哈爾濱工程大學(xué);2015年

7 鄭瑩;基于樹分解的難解問題的參數(shù)算法研究[D];中南大學(xué);2013年

8 于瑞云;無線傳感器網(wǎng)絡(luò)中面向數(shù)據(jù)采集的支配集算法與策略研究[D];東北大學(xué);2009年

9 張強(qiáng);基于連通性的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)研究[D];天津大學(xué);2011年

10 李睿智;基于局部搜索策略的若干組合優(yōu)化問題求解算法研究[D];東北師范大學(xué);2017年

相關(guān)碩士學(xué)位論文 前10條

1 徐彤;WSN中連通支配集構(gòu)造算法的研究[D];南昌航空大學(xué);2019年

2 齊曉晗;基于多連通支配集調(diào)度機(jī)制的飛行自組網(wǎng)拓?fù)淇刂扑惴╗D];哈爾濱工業(yè)大學(xué);2018年

3 荊瑩;基于時(shí)變連通支配集的多層衛(wèi)星網(wǎng)絡(luò)路由算法[D];哈爾濱工業(yè)大學(xué);2017年

4 劉華麗;若干圖的連通支配問題研究[D];中國計(jì)量大學(xué);2017年

5 劉培麗;基于集序的集優(yōu)化問題的穩(wěn)定性及魯棒性分析[D];重慶大學(xué);2018年

6 徐培培;無線傳感網(wǎng)絡(luò)中強(qiáng)連通支配集的構(gòu)造研究[D];南昌航空大學(xué);2016年

7 任思君;最小連通支配集算法研究[D];上海交通大學(xué);2015年

8 魯?shù)窃?無線傳感器網(wǎng)絡(luò)中連通支配集的構(gòu)造算法研究[D];蘇州大學(xué);2014年

9 林霖;無線傳感器網(wǎng)絡(luò)分布式連通支配集構(gòu)造方法研究[D];電子科技大學(xué);2012年

10 陳蓓瑋;加權(quán)邊支配集問題的參數(shù)算法研究[D];中南大學(xué);2009年

本文編號(hào)：2841085