本文關(guān)鍵詞：基于CUDA的圖頂點著色問題的并行遺傳算法研究

  更多相關(guān)文章： 圖著色 并行遺傳算法 CUDA NP完全問題

【摘要】：圖著色問題是一個經(jīng)典的組合優(yōu)化問題，許多來源于生活的實際問題都可以轉(zhuǎn)化為求解圖著色問題。因此，圖著色問題的求解，，對科學(xué)技術(shù)和工程設(shè)計等領(lǐng)域都具有重要作用。然而，沒有任何算法可以在多項式時間內(nèi)求解出該問題的最優(yōu)解，所以，圖著色問題是一個典型的NP完全問題。 近年來，國內(nèi)外的許多學(xué)者提出各種求解圖著色問題的算法，如隱式枚舉算法、割平面算法等，這類精確算法當(dāng)問題規(guī)模較小的時候效果較好，但是一旦問題規(guī)模變大，無法避免指數(shù)爆炸問題。除了精確算法，遺傳算法、蟻群算法等也被用于求解圖著色問題。然而，由于圖著色問題具有指數(shù)級的解空間規(guī)模，無論是精確算法還是近似算法，都需要花費大量的時間進行計算，無法在讓人滿意的時間內(nèi)求解出問題的解。 如今基于CUDA的高性能并行計算技術(shù)成為研究熱點。本文將CUDA和遺傳算法相結(jié)合，提出一種基于CUDA求解圖著色問題的并行遺傳算法，算法采用顏色序列對問題進行編碼，設(shè)計出并行的種群初始化、選擇算子、交叉算子和變異算子，極大地提高了算法的效率。 實驗結(jié)果表明，和傳統(tǒng)基于CPU的各類算法相比，本文提出的算法可以較大地減少計算時間，找到已知圖例的最小著色數(shù)，可以有效求解更大規(guī)模的實例。
【關(guān)鍵詞】：圖著色 并行遺傳算法 CUDA NP完全問題
【學(xué)位授予單位】：武漢科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5
【目錄】：

• 摘要4-5
• Abstract5-8
• 第1章 緒論8-13
• 1.1 研究背景及意義8
• 1.2 研究現(xiàn)狀8-11
• 1.2.1 圖著色問題的研究現(xiàn)狀8-9
• 1.2.2 遺傳算法的研究現(xiàn)狀9-10
• 1.2.3 CUDA 的發(fā)展現(xiàn)狀10-11
• 1.3 本文的主要工作及組織11-13
• 第2章 遺傳算法和 CUDA 技術(shù)簡介13-24
• 2.1 遺傳算法的介紹13-17
• 2.1.1 遺傳算法的相關(guān)基本概念13-15
• 2.1.2 遺傳算法的基本流程15-16
• 2.1.3 遺傳算法的特點與應(yīng)用16-17
• 2.2 CUDA 并行編程介紹17-23
• 2.2.1 GPU 及 CUDA 的發(fā)展與現(xiàn)狀17-18
• 2.2.2 CUDA 的存儲器層次結(jié)構(gòu)18-19
• 2.2.3 CUDA 編程模型19-20
• 2.2.4 CUDA 中的通信20-21
• 2.2.5 CUDA 編程相關(guān)問題21
• 2.2.6 CUDA 軟件開發(fā)方法及流程21-23
• 2.3 本章小結(jié)23-24
• 第3章 基于遺傳算法的圖著色問題研究24-36
• 3.1 基于頂點序列的遺傳算法24-30
• 3.1.1 圖的存儲方式24-25
• 3.1.2 染色體的編碼25
• 3.1.3 適應(yīng)度函數(shù)的設(shè)計25-28
• 3.1.4 個體選擇的設(shè)計28
• 3.1.5 個體的交叉設(shè)計28-29
• 3.1.6 個體的變異設(shè)計29
• 3.1.7 基于頂點序列的遺傳算法29-30
• 3.2 基于顏色序列的遺傳算法30-33
• 3.2.1 圖的存儲方式30-31
• 3.2.2 染色體的編碼方式31
• 3.2.3 適應(yīng)度函數(shù)的設(shè)計31-33
• 3.2.4 基于顏色序列的遺傳算法33
• 3.3 實驗對比與分析33-35
• 3.4 本章小結(jié)35-36
• 第4章 基于 CUDA 的圖著色并行遺傳算法36-53
• 4.1 引言36
• 4.2 圖的存儲方式36
• 4.3 染色體的編碼36-37
• 4.4 并行遺傳算法描述37-38
• 4.5 染色體子空間的建立38
• 4.6 個體的優(yōu)化38-42
• 4.7 適應(yīng)度函數(shù)的設(shè)計42
• 4.8 遺傳算子的設(shè)計42-45
• 4.8.1 選擇算子43
• 4.8.2 交叉算子43-44
• 4.8.3 變異算子44-45
• 4.9 個體擇優(yōu)45-46
• 4.10 實驗結(jié)果與分析46-53
• 第5章 總結(jié)與展望53-54
• 5.1 總結(jié)53
• 5.2 展望53-54
• 參考文獻54-58
• 致謝58-59
• 附錄 1 攻讀碩士學(xué)位期間發(fā)表的論文59-60
• 附錄 2 攻讀碩士學(xué)位期間參加的科研項目60-61
• 大摘要61-65

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 韓麗霞;王宇平;蘭紹江;;基于有序劃分編碼的圖著色算法[J];電子學(xué)報;2010年01期

2 何利娟;;利用遺傳算法實現(xiàn)病毒生命化[J];福建電腦;2011年02期

3 張楠;蔣海鳳;;圖的染色問題及其應(yīng)用[J];計算機光盤軟件與應(yīng)用;2014年17期

4 吳恩華,柳有權(quán);基于圖形處理器(GPU)的通用計算[J];計算機輔助設(shè)計與圖形學(xué)學(xué)報;2004年05期

5 周勇;王皓;程春田;;使用GPU技術(shù)的數(shù)據(jù)流分位數(shù)并行計算方法[J];計算機應(yīng)用;2010年02期

6 杜文麗;原亮;;遺傳算法的特點及應(yīng)用領(lǐng)域研究[J];科技信息(科學(xué)教研);2008年10期

7 許進;強小利;方剛;周康;;一種圖頂點著色DNA計算機模型[J];科學(xué)通報;2006年04期

8 趙興娜;李文振;;遺傳算法在自動控制領(lǐng)域的應(yīng)用分析[J];科技致富向?qū)?2013年08期

9 田朝薇;宋海洲;楊金勇;;一個組合優(yōu)化問題的求解[J];黑龍江大學(xué)自然科學(xué)學(xué)報;2013年05期

10 張麗;丁曉東;;圖著色問題的逆序蟻群算法研究[J];上海理工大學(xué)學(xué)報;2014年05期

本文編號：1051951