泛化頂點覆蓋問題的局部搜索算法研究

《泛化頂點覆蓋問題的局部搜索算法研究》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在學術論文-天天文庫。

1、學校代碼：２０１４１０２５２０：１０２００研巧生學號分類號：無：笠型密紋東於多碩：ｔ學位論文寒化頂巧巧巧部＆聚其變ＳｔｕｄｏｎｔｈｅＬｏｃａｌＳｅａｒｃｈＡｌｇｏｒｉｔｈｍｙｆｏｒＧｅｎｅｒａｌｉｚｅｄＶｅｒｔｅｘＣｏｖｅｒＰｒｏｂｌｅｍ作者；方度指穿教師：段明巧專業(yè)學位類別：工程碩±專業(yè)學位領域：計ｇ機技術學位類型：?；T±東北師范大學學位評定委員會２０１６年４月？■學校代碼：１０２００研究生學號；２０１４１０２５２０分類號：ＩＥ巡密級：無馨《批

2、畔聾碩±學位論文備化頂點覆黃問題的局部投索莫法研兜Ｓ化ｄｙｏｎ化ｅＬｏｃａｌＳｅａｒｃｈＡｌｇｏｒｉｔｈｍ化ｒＧｅｎｅｒａｌｉｚｅｄＶｅｒｔｅｘＣｏｖｅｒＰｒｏｂｌｅｍ作者：方旣指導教師：殷明浩專業(yè)學位類別：工程碩±專業(yè)學位領域：計算機技術學位類型：專業(yè)碩±東北師范大學學位評定委員會２０１６年４月獨創(chuàng)性聲明本人鄭重聲明：所提交的學位論文是本人在導師指導下獨立進行研究工作所取得的成果。據(jù)我所知，除了特別加Ｗ標注和致謝的地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果。對本人

3、的研巧做出重要貢。獻的個人和集體，均己在文中作了明確的說明本聲明的法律結(jié)果由本人承擔。學位論文作者簽名：日期：學位論文使用授權書本學位論文作者完全了解東北師范大學有關保留、使用學位論文的規(guī)定，即：東北師范大學有權保留并向國家有關部口或機構送交學位論文的復印件和電子版允許論文被査閱和借閱。本人授權東北師范大學可隊格學位論文的全部或部分內(nèi)容編入有關數(shù)據(jù)庫進行檢索、，可Ｗ采用影印縮印或其它復制手段保存、匯編本學位論文。（保密的學位論文在解密后適用本授權書）沒奪Ａ學位論文作者簽名：氣帶指導教師簽名：－－日

4、期：Ｐ化ＩｒＨ／日期：ｙ、化學位論文作者畢業(yè)后去向：工作單位：電話：通訊地址；郵編：摘要一頂點覆蓋問題是人工智能中個重要的研究領域。，其計算復雜性為ＮＰ最小頂點覆蓋（ＭＶＣ）問題、最小權頂點覆蓋（ＭＷＶＣ）問題、泛化頂點覆蓋（ＧＶＣ）問題均為頂點覆蓋的延伸問題。泛化頂點覆蓋問題在很多領域例如網(wǎng)絡工程、通信工程和生物信息工程中都有廣泛的應用。因此研究泛化項點覆蓋問題有著很重要的理論意義和實際價值。求解泛化頂點覆蓋問題可Ｗ使用精確算法和啟發(fā)式算法。精確算法能夠求出精確解，啟發(fā)式算法雖然不能求出精確解，但是可從

5、能夠求出較優(yōu)的解。但是當求解問題規(guī)。模較大時，精確算法很難在較短時間內(nèi)求出精確解，而啟發(fā)式算法的求解的時間卻很短因此對于求解大規(guī)模問題，大部分使用啟發(fā)式算法，啟發(fā)式算法中最主要的是局部捜索算法。本文的工作主要集中在設計求解泛化頂點覆蓋問題的局部搜索算法。本文提出一個基于禁忌策略和干擾機制的送代局部捜索算法求解泛化頂點覆蓋問題（簡稱為ＬＳＴＰ算法）。本文提出的ＬＳＴＰ算法是在局部捜索中加入為禁忌策略、頂點選擇和干擾機制這Ｈ個策略。ＬＳＴＰ算法中加入禁忌策略是防止局部捜索立即回到之前訪問過的候選解ＬＳＴＰ一，避免循環(huán)問題的出孤算法中

6、設計個計算頂點翻轉(zhuǎn)后對目標值的改變量公式，選擇出需要翻轉(zhuǎn)的頂點，并與禁忌策略結(jié)合進行頂點翻轉(zhuǎn)；ＬＳＴＰ算法中加入干擾機制是為了避免算法陷入局部捜索最優(yōu)解，增加解的多樣性。本文采用的實例由原有文獻中的算法隨機生成，同時擴大實驗中泛化頂點覆蓋問題實例的取值范圍。ＬＳＴＰ，用來解決較大規(guī)模的泛化頂點覆盞問題本文將算法與Ｍｉｌａｎｏｖｉｃ提出的ＧＡ算法進行實驗對比，實驗的結(jié)果表明，在相同參數(shù)條件下，ＬＳＴＰ算法比ＧＡ算法性能要好。本文將加入ＬＳＴＰ算法中的禁忌策略和干擾機制進行實驗分。析，證明了加入這兩個策略的有效性關鍵詞；泛化頂點

7、覆蓋問題；局部捜索；禁忌策略；干擾機制ＩＡｂｓｔｒａｃｔＶｅｒｔｅｘｃｏｖｅｒｒｏｂｌｅｍｉｓａｎｉｍｏｒｔａｎｔａｒｅａｏｆｒｅｓｅａｒｃｈｉｎａｒｔｉｆｉｃｉａｌｉｎｔｅｌｌｉｅｎｃｅａｎｄｉｔｓｐｐｇｃｏｍｐｕｔａｔｉｏｎｃｏｍｐｌｅｘｉｔｙｉｓＮＲＴｈｅｍｉｎｉｍｕｍｖｅｒｔｅｘｃｏｖｅｒｐｒｏｂｌｅｍ，ｗｅｉｇｈｔｅｄｍｉｎｉｍｕｍｖｅｒｔｅｘｃｏｖｅｒｐｒｏｂｌｅｍ，ｇｅ打ｅｒａｌｉｚｅｄｖｅｒｔｅｘｃｏｖｅｒｐｒｏｂｌｅｍａｒｅａｎｅｘｔｅ打ｓｉｏｎｏｆｔｈｅ

8、ｖｅｒｔｅｘｃｏｖｅｒｒｏｂｌｅｍ．Ｇｅ打ｅｒａｌｉｚｅ