連通頂點(diǎn)覆蓋問題和k-plex問題是兩個重要的難解組合優(yōu)化問題。這兩個問題在網(wǎng)絡(luò)安全、大規(guī)模集成電路、無線網(wǎng)絡(luò)設(shè)計(jì)以及社交網(wǎng)絡(luò)等領(lǐng)域有著重要的應(yīng)用。性能良好的求解算法不僅能夠提高這兩個問題的求解效率和精度,而且能夠提高現(xiàn)實(shí)工業(yè)中的作業(yè)效率,降低時間和勞動力成本,節(jié)約資源,提升產(chǎn)品的利潤空間。本文設(shè)計(jì)了三個局部搜索算法分別用于求解連通頂點(diǎn)覆蓋問題和k-plex問題。其中GRASP-CVC算法和EWGRASP-CVC算法用于求解連通頂點(diǎn)覆蓋問題。在這兩個算法中我們采用貪心策略簡單快速地構(gòu)造出問題的初始可行解,同時為了避免局部搜索算法的循環(huán)搜索問題,格局檢測策略以及帶遺忘機(jī)制的邊加權(quán)策略被應(yīng)用到算法中。對于k-plex問題,我們設(shè)計(jì)了一個多階段局部搜索（PLS）算法進(jìn)行求解。PLS算法主要由三個子階段組成,每個子階段按不同的策略對問題的解空間進(jìn)行搜索。PLS算法通過在這三個子階段之間的切換,使得算法不僅能夠處理不同特點(diǎn)的實(shí)例,而且保證算法能夠搜索到盡可能大的解空間,提升了算法跳出局部最優(yōu)的能力。為了驗(yàn)證我們所設(shè)計(jì)的算法的有效性和高效性,我們將現(xiàn)有算法和本文所提算法進(jìn)行了實(shí)驗(yàn)對比。在大量經(jīng)典實(shí)... 

【文章來源】：東北師范大學(xué)吉林省 211工程院校 教育部直屬院校

【文章頁數(shù)】：59 頁

【學(xué)位級別】：碩士

【部分圖文】：

最小頂點(diǎn)覆蓋和連通頂點(diǎn)覆蓋示例

第四章 PLS 算法求解 k-plex 問題多階段局部搜索[57]（Phased Local Search,記為 PLS）最初是由 Pullan 在動態(tài)局部搜索[43]（Dynamic Local Search，記為 DLS）的基礎(chǔ)上加以改進(jìn)用于求解最大團(tuán)問題的隨機(jī)算法。PLS 算法由三個子算法組成，這三個子算法主要區(qū)別在于選擇頂點(diǎn)的方法以及為克服局部最優(yōu)采用的擾動策略不同，算法在迭代執(zhí)行的過程中不斷地在這三個子算法之間切換。其作者的實(shí)驗(yàn)也充分證明了 PLS 算法在求解最大團(tuán)問題以及最大加權(quán)團(tuán)問題上的有效性，而且與 DLS 算法不同，PLS算法沒有依賴于具體實(shí)例的參數(shù)，這使得 PLS 實(shí)現(xiàn)起來更加便捷，也更具通用性�？紤]到 PLS 的上述優(yōu)點(diǎn)以及 k-plex 問題與最大團(tuán)問題的關(guān)聯(lián)性，采用 PLS算法框架求解 k-plex 問題便是一個很自然的想法。4.1 k-plex 相關(guān)定義及圖化簡原理在對 PLS 相關(guān)子過程進(jìn)行介紹之前，本節(jié)首先對這些子過程運(yùn)行時涉及到的重要概念進(jìn)行說明。


本文編號：3607552