本文關鍵詞：基于GPU加速的細粒度模型并行免疫算法研究，，由筆耕文化傳播整理發(fā)布。

《大連理工大學》 2009年

基于GPU加速的細粒度模型并行免疫算法研究

張立花  

【摘要】： 免疫系統(tǒng)是目前已知的最精妙復雜的身體抵御外部有害物質(zhì)的系統(tǒng),它猶如一支訓練有素的精銳部隊,捍衛(wèi)機體的健康。免疫細胞會對入侵者產(chǎn)生記憶,當下次同樣的抗原入侵時,便以此抗體將其消滅,這正是“疫苗預防接種”的基本原理。人工免疫系統(tǒng)作為人工智能研究的一個新領域,期望借鑒生物免疫系統(tǒng)的信息處理機理和功能,進一步豐富人工智能能的研究手段,也可以說,生物免疫學的發(fā)展推動了人工智能的研究。 免疫系統(tǒng)的特點和作用機理對工程應用中許多復雜問題的求解有重要的啟示和借鑒作用,作為一種智能優(yōu)化計算方法,在實際工程中表現(xiàn)出巨大的潛力。但是在數(shù)值建模和優(yōu)化計算等領域中,在處理大量數(shù)據(jù)和求解大規(guī)模復雜問題時,免疫算法(ImmuneAlgorithm,IA)仍然需要大量的計算時間,而并行的IA算法能極大地降低問題求解時間。 針對IA在解決大規(guī)模優(yōu)化問題時需要消耗大量的時間無法達到實時性的問題,結合GPU的高速并行性,本文提出了一種基于GPU(Graphics Processing Unit,GPU)加速的細粒度并行免疫算法。本算法借助CUDA(Compute Unified Device Architecture,CUDA)統(tǒng)一架構,將實現(xiàn)過程轉(zhuǎn)化成CUDA線程塊并行計算過程,使得免疫算法在GPU中加速執(zhí)行,在取得較好的優(yōu)化效果的同時,解決了細粒度并行的群體規(guī)模限制問題,提高了算法的運行速度。本文的重要工作如下: (1)回顧了免疫算法的研究背景,產(chǎn)生與研究現(xiàn)狀以及研究趨勢,同時闡明了利用GPU來研究免疫算法的意義,闡述了本文的免疫算法研究模型。 (2)回顧GPU的發(fā)展,對GPU的通用計算以及應用做了一個大概的闡述,對NVIDIA GPU的統(tǒng)一計算設備架構(CUDA)的執(zhí)行模型,存儲模型以及通信模型做了簡要的概述。 (3)闡述了免疫算法的生物學機理,對生物學整體上的認識可以有助于我們更好的對算法模型理解。 (4)針對傳統(tǒng)算法在優(yōu)化大規(guī)模等問題時計算量大和計算速度慢的問題,提出了基于GPU加速的細粒度并行免疫算法,通過圖形硬件的并行性,將傳統(tǒng)的遞歸算法轉(zhuǎn)化成并行計算,大幅度提高了算法的執(zhí)行速度,節(jié)約了計算時間。對算法進行程序?qū)崿F(xiàn),對算法在CPU和GPU中的時間進行比較,給出結果分析,證明了算法的可行性與實用性。

【關鍵詞】：
【學位授予單位】：大連理工大學
【學位級別】：碩士
【學位授予年份】：2009
【分類號】：TP18
【目錄】：

摘要4-5

Abstract5-9

引言9-11

1 免疫算法綜述11-18

1.1 免疫算法研究背景11-12

1.2 免疫算法產(chǎn)生與研究現(xiàn)狀12-15

1.3 免疫算法研究趨勢以及意義15-17

1.3.1 免疫算法研究趨勢15

1.3.2 免疫算法的研究意義15-17

1.3.3 利用GPU來研究免疫算法的意義17

1.4 本文免疫算法模型17-18

2 理論知識基礎18-28

2.1 GPU的通用計算18-20

2.2 統(tǒng)一設備架構CUDA20-23

2.2.1 何為CUDA20

2.2.2 CUDA執(zhí)行模型20-21

2.2.3 CUDA存儲模型21-22

2.2.4 CUDA中的通信22-23

2.3 生物學基礎以及人工免疫系統(tǒng)23-27

2.3.1 生物學基礎23-25

2.3.2 人工免疫系統(tǒng)概述25-27

2.4 本章小結27-28

3 基于GPU加速的細粒度人工免疫算法28-56

3.1 免疫遺傳算法的提出28-29

3.2 CPU免疫算法29-34

3.2.1 疫苗接種31

3.2.2 免疫疫苗的作用機制31-33

3.2.3 免疫選擇33

3.2.4 免疫算子的執(zhí)行算法33-34

3.3 CPU免疫算法的流程34-35

3.4 CPU中免疫算法存在的問題35-36

3.5 免疫算法的改進方案36-37

3.6 并行免疫算法技術要點37-41

3.6.1 測試實例旅行商問題(TSP)問題描述37-38

3.6.2 GPUIA適應度的計算38-39

3.6.3 GPU中數(shù)據(jù)存儲39-40

3.6.4 最佳適應值更新搜索40-41

3.7 基于GPU加速的免疫算法并行化模型41-50

3.7.1 CUDA編程41-42

3.7.2 GPU中疫苗的提取過程42-45

3.7.3 GPU中抗體交叉和變異操作45-47

3.7.4 GPU中抗體疫苗注射與免疫檢測47-49

3.7.5 GPU中種群更新49-50

3.8 GPU中內(nèi)存的優(yōu)化50-52

3.9 GPU并行IA模型52-53

3.10 試驗結果及分析53-55

3.11 本章小結55-56

結論56-57

參考文獻57-61

攻讀碩士學位期間發(fā)表學術論文情況61-62

致謝62-63

下載全文 更多同類文獻

CAJ全文下載

(如何獲取全文？ 歡迎：購買知網(wǎng)充值卡、在線充值、在線咨詢)

CAJViewer閱讀器支持CAJ、PDF文件格式

【引證文獻】

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

1 趙濤;王海帆;吳勇標;劉憶寧;;基于CUDA的口令字恢復系統(tǒng)設計與開發(fā)[J];保密科學技術;2012年08期

中國碩士學位論文全文數(shù)據(jù)庫 前2條

1 張珩;基于GPU的圖像粒子擬合及分類算法研究及應用[D];北京化工大學;2011年

2 李運赫;聲場時域信號預報并行算法研究[D];哈爾濱工程大學;2012年

【參考文獻】

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

1 王磊,潘進,焦李成;免疫算法[J];電子學報;2000年07期

2 張四海,曹先彬,王煦法;基于免疫識別的免疫算法[J];電子學報;2002年12期

3 羅文堅,曹先彬,王煦法;用一種免疫遺傳算法求解頻率分配問題[J];電子學報;2003年06期

4 邵學廣,孫莉;免疫-遺傳算法用于混合物重疊核磁共振信號解析[J];高等學校化學學報;2001年04期

5 葛紅;免疫算法綜述[J];華南師范大學學報(自然科學版);2002年03期

6 張軍,劉克勝,王煦法;一種基于免疫調(diào)節(jié)和共生進化的神經(jīng)網(wǎng)絡優(yōu)化設計方法[J];計算機研究與發(fā)展;2000年08期

7 劉克勝,曹先彬,鄭浩然,王煦法;基于免疫算法的TSP問題求解[J];計算機工程;2000年01期

8 張海峰,梁意文,代文;計算機免疫識別規(guī)則的演化挖掘[J];計算機工程;2001年11期

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

10 王磊,潘進,焦李成;免疫規(guī)劃[J];計算機學報;2000年08期

中國博士學位論文全文數(shù)據(jù)庫 前1條

1 王磊;免疫進化計算理論及應用[D];西安電子科技大學;2001年

【共引文獻】

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

1 吳大宏,趙人達;基于遺傳算法與神經(jīng)網(wǎng)絡的橋梁結構健康監(jiān)測系統(tǒng)研究初探[J];四川建筑科學研究;2002年03期

2 張安勤;數(shù)據(jù)挖掘與進化算法[J];安徽教育學院學報;2002年03期

3 尹峰,鄧小鵬,許四毛;生物免疫機理在計算機安全領域的應用與發(fā)展[J];安徽電子信息職業(yè)技術學院學報;2004年Z1期

4 程家興,陳萬里;列車控制問題的計算分析及自適應算法[J];安徽大學學報(自然科學版);2002年02期

5 蔣中;遺傳算法在PID參數(shù)優(yōu)化中的應用[J];安徽建筑工業(yè)學院學報(自然科學版);2000年01期

6 阮懷忠,張建中;基于改進遺傳算法的TSP問題求解[J];安徽建筑工業(yè)學院學報(自然科學版);2003年04期

7 陳杰,周冬華;浮點數(shù)編碼的遺傳算法在模糊控制器參數(shù)尋優(yōu)中的應用[J];安徽建筑工業(yè)學院學報(自然科學版);2004年02期

8 方潛生;硬件進化(EHW)的研究與進展[J];安徽建筑工業(yè)學院學報(自然科學版);2004年06期

9 楊益;;基于FPGA的背包問題的求解[J];安徽建筑工業(yè)學院學報(自然科學版);2010年04期

10 周蕾;;人工免疫技術在農(nóng)業(yè)信息化建設中的應用[J];安徽農(nóng)業(yè)科學;2009年13期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 楊益;方潛生;汪力君;;基于Handel-C的數(shù)字芯片的設計方法研究與實現(xiàn)[A];2005年“數(shù)字安徽”博士科技論壇論文集[C];2005年

2 胡楊林;蔣潔瓊;王明煌;曾勤;邱岳峰;鄒俊;陳紅麗;FDS team;;聚變裂變混合堆長壽命錒系廢料嬗變處理的中子學優(yōu)化分析[A];安徽新能源技術創(chuàng)新與產(chǎn)業(yè)發(fā)展博士科技論壇論文集[C];2010年

3 孫燕;孫崢;黃鹍;;基于模擬退火機制的隔離小生境混合遺傳算法[A];第二十六屆中國控制會議論文集[C];2007年

4 孫燕;孫崢;;利用正交遺傳算法優(yōu)化交通檢測點分布[A];第二十六屆中國控制會議論文集[C];2007年

5 曹春紅;張斌;王利民;李文輝;;基于免疫神經(jīng)網(wǎng)絡的幾何約束求解技術的研究[A];第二十七屆中國控制會議論文集[C];2008年

6 郭玉堂;劉路路;;基于佳點集遺傳算法的邊緣檢測[A];第二十七屆中國控制會議論文集[C];2008年

7 劉向;鄒逢興;張湘平;高政;;面向節(jié)能的混合流水車間調(diào)度方法的研究[A];第二十七屆中國控制會議論文集[C];2008年

8 龔濤;杜常興;;免疫計算研究的進展[A];中國自動化學會控制理論專業(yè)委員會A卷[C];2011年

9 汪民樂;高曉光;;GA早熟問題的定量分析及其預防策略[A];'2003系統(tǒng)仿真技術及其應用學術交流會論文集[C];2003年

10 田占東;張振宇;;用遺傳算法確定反應速率方程參數(shù)[A];第三屆全國爆炸力學實驗技術交流會論文集[C];2004年

中國博士學位論文全文數(shù)據(jù)庫 前10條

1 孫曉華;基于聚類的文本機會發(fā)現(xiàn)關鍵問題研究[D];哈爾濱工程大學;2010年

2 時長江;豆科類雜草種子圖像識別系統(tǒng)研究[D];中國海洋大學;2009年

3 韓艷玲;可能性構造空間理論與計算機作曲思維模型研究[D];華中科技大學;2010年

4 彭北青;第三方物流配送車輛路徑問題模型及算法研究[D];華中科技大學;2009年

5 黃林峰;多目標進化算法研究[D];中國科學技術大學;2009年

6 劉飛;四足機器人步態(tài)規(guī)劃與平衡控制研究[D];中國科學技術大學;2010年

7 岑健;基于人工免疫系統(tǒng)的機組復合故障診斷技術研究[D];華南理工大學;2010年

8 楊紅;污水生化處理的智能建模與優(yōu)化控制策略應用研究[D];華南理工大學;2010年

9 魏建香;學科交叉知識發(fā)現(xiàn)及其可視化研究[D];南京大學;2010年

10 吳鋒;基于GPU并行計算的數(shù)值模擬與燃煤鍋爐系統(tǒng)的優(yōu)化研究[D];浙江大學;2010年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 蔣慧;改進的遺傳算法在電力系統(tǒng)無功優(yōu)化中的應用[D];安徽工程大學;2010年

2 赫英毅;毫米波段基于TE_（21）模差網(wǎng)絡設計[D];中國工程物理研究院;2009年

3 萬成;動態(tài)環(huán)境下的元胞遺傳算法研究[D];南昌航空大學;2010年

4 李坤;參數(shù)參與進化的自適應遺傳算法研究[D];南昌航空大學;2010年

5 吳香庭;基于遺傳算法的K-means聚類方法的研究[D];山東科技大學;2010年

6 王輝;基于改進遺傳算法的物流配送路徑優(yōu)化研究[D];山東科技大學;2010年

7 紀二云;基于改進遺傳算法的電力系統(tǒng)無功優(yōu)化的研究[D];山東科技大學;2010年

8 施曉坤;煤炭企業(yè)人才結構優(yōu)化[D];山東科技大學;2010年

9 王林吉;基于CIELAB均勻顏色空間和聚類算法的混紡測色研究[D];浙江理工大學;2010年

10 馬宗梅;遺傳算法在考試系統(tǒng)組卷中的應用與研究[D];鄭州大學;2009年

【同被引文獻】

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

1 王握文;陳明;;“天河一號”超級計算機系統(tǒng)研制[J];國防科技;2009年06期

2 閆方;趙熠;李高;;細胞給藥系統(tǒng)研究進展[J];國際藥學研究雜志;2008年04期

3 張楠;;HPC標準“試水”石油勘探[J];石油石化物資采購;2009年09期

4 張鴻燕;耿征;;Levenberg-Marquardt算法的一種新解釋[J];計算機工程與應用;2009年19期

5 肖江;胡柯良;鄧元勇;;基于CUDA的矩陣乘法和FFT性能測試[J];計算機工程;2009年10期

6 范培勤;笪良龍;謝駿;;遠程跨平臺水下聲場并行計算系統(tǒng)的實現(xiàn)[J];計算機工程;2009年20期

7 樂德廣;常晉義;劉祥南;郭東輝;;基于GPU的MD5高速解密算法的實現(xiàn)[J];計算機工程;2010年11期

8 范培勤;笪良龍;盧曉亭;;面向水下聲場計算的PC集群構建[J];計算機仿真;2007年12期

9 錢悅;;圖形處理器CUDA編程模型的應用研究[J];計算機與數(shù)字工程;2008年12期

10 譚冬蓮,肖汝誠;基于Levenberg-Marquardt算法的橋梁結構靜力參數(shù)識別[J];交通運輸工程學報;2005年03期

中國博士學位論文全文數(shù)據(jù)庫 前1條

1 白洪濤;基于GPU的高性能并行算法研究[D];吉林大學;2010年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 張美香;貝葉斯文本分類器的研究與改進[D];太原理工大學;2005年

2 張麗麗;基于分布式計算的對稱密碼算法的暴力破解[D];西安電子科技大學;2008年

3 彭紹鑫;基于GPU的硬件加速方法及其在積分方程數(shù)值解中的應用[D];電子科技大學;2008年

4 彭俊杰;基于CUDA平臺地震數(shù)據(jù)處理研究[D];湖南大學;2009年

5 張舒;模式識別并行算法與GPU高速實現(xiàn)研究[D];電子科技大學;2009年

6 蘇麗麗;基于CPU-GPU集群的分子動力學并行計算研究[D];大連理工大學;2009年

7 顏瑞;基于CUDA的立體匹配及去隔行算法[D];浙江大學;2010年

8 周潔;基于GPU的WPA/WPA2-PSK高速破譯方法研究[D];西安電子科技大學;2010年

9 譚霜;基于GPU微體系結構的高性能計算研究[D];國防科學技術大學;2009年

10 孫長征;數(shù)值天氣預報云計算服務應用系統(tǒng)研究與實現(xiàn)[D];國防科學技術大學;2009年

【二級參考文獻】

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

1 周偉良,何鯤,曹先彬,程慧霞;基于一種免疫遺傳算法的BP網(wǎng)絡設計[J];安徽大學學報(自然科學版);1999年01期

2 陳立軍;計算機病毒免疫技術的新途徑[J];北京大學學報(自然科學版);1998年05期

3 胡朝陽,文福拴;免疫算法與其它模擬進化優(yōu)化算法的比較研究[J];電力情報;1998年01期

4 謝敬東,王磊,唐國慶;遺傳算法在多目標電網(wǎng)優(yōu)化規(guī)劃中的應用[J];電力系統(tǒng)自動化;1998年10期

5 謝敬東,唐國慶,吳新余;進化規(guī)劃在電網(wǎng)規(guī)劃中的應用[J];電力系統(tǒng)及其自動化學報;1998年02期

6 文福拴,韓禎祥;基于Tabu搜索方法的輸電系統(tǒng)最優(yōu)規(guī)則[J];電網(wǎng)技術;1997年05期

7 王磊,潘進,焦李成;免疫算法[J];電子學報;2000年07期

8 王磊,焦李成,劉芳,張艷寧;免疫進化子波網(wǎng)絡及其學習算法[J];電子學報;2001年S1期

9 曹先彬,莊鎮(zhèn)泉;一個基于啟發(fā)式經(jīng)驗的立體布局進化策略[J];電子科學學刊;1998年03期

10 蔡文生,邵學廣,潘忠孝;遺傳算法用于化學結構圖的同態(tài)研究[J];高等學�；瘜W學報;1999年01期

【相似文獻】

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

1 張四海,曹先彬,王煦法;基于免疫識別的免疫算法[J];電子學報;2002年12期

2 謝開貴,周家啟;基于免疫算法的配電網(wǎng)開關優(yōu)化配置模型[J];電力系統(tǒng)自動化;2003年15期

3 李金城;張國忠;滕紅麗;周晟;吳紅霞;;免疫算法研究[J];沈陽航空工業(yè)學院學報;2005年05期

4 左興權,李士勇;一種用于優(yōu)化計算的自適應免疫算法[J];計算機工程與應用;2003年20期

5 梁鴻生,郝勇娜,王凱,柴繼河;免疫算法[J];昆明理工大學學報(理工版);2003年05期

6 張禮兵,金菊良,王軍;一種免疫遺傳算法研究及應用[J];合肥工業(yè)大學學報(自然科學版);2004年07期

7 周鳳岐,高康林;免疫計算在求解約束優(yōu)化問題中的應用[J];微電子學與計算機;2004年11期

8 胡小明,吳耿鋒,樊建;基于時間柵格法和免疫算法的機器人動態(tài)路徑規(guī)劃[J];計算機應用;2005年03期

9 吳進波;熊盛武;徐寧;;免疫模擬退火算法求解TSP[J];計算機工程與應用;2006年28期

10 錢紅建;葉洛華;杜翠娣;王淑萍;;基于遺傳免疫算法的網(wǎng)絡入侵檢測的研究[J];信息化建設;2006年10期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 龔濤;杜常興;;免疫計算研究的進展[A];中國自動化學會控制理論專業(yè)委員會A卷[C];2011年

2 沈冠町;徐本柱;劉曉平;;改進的免疫算法在作業(yè)車間調(diào)度中的應用[A];全國第21屆計算機技術與應用學術會議（CACIS·2010）暨全國第2屆安全關鍵技術與應用學術會議論文集[C];2010年

3 周德義;左春檉;李靜;苗菲;張舟;;基于免疫算法的齒輪減速器區(qū)間優(yōu)化研究[A];走中國特色農(nóng)業(yè)機械化道路——中國農(nóng)業(yè)機械學會2008年學術年會論文集（下冊）[C];2008年

4 許殿;史小衛(wèi);;基于免疫算法的微波電路優(yōu)化技術[A];2003'全國微波毫米波會議論文集[C];2003年

5 王瑋;占榮輝;張軍;;基于免疫算法的距離像長度估計[A];第十四屆全國信號處理學術年會(CCSP-2009)論文集[C];2009年

6 蘇兆品;蔣建國;尹翔;夏娜;李勇;;一種基于免疫的敏捷供應鏈形成算法[A];全國先進制造技術高層論壇暨制造業(yè)自動化、信息化技術研討會論文集[C];2005年

7 孟科;李紹軍;錢鋒;;實數(shù)編碼免疫算法在溶劑脫水塔軟測量中的應用[A];'2006系統(tǒng)仿真技術及其應用學術交流會論文集[C];2006年

8 呂崗;趙鶴鳴;;一種優(yōu)化前向神經(jīng)網(wǎng)絡權值的免疫算法[A];2003年中國智能自動化會議論文集（上冊）[C];2003年

9 余建軍;孫樹棟;;模擬退火免疫混合算法[A];全國第16屆計算機科學與技術應用（CACIS）學術會議論文集[C];2004年

10 任偉建;霍鳳財;王愛軍;;人工免疫系統(tǒng)原理及其應用[A];2004中國控制與決策學術年會論文集[C];2004年

中國博士學位論文全文數(shù)據(jù)庫 前10條

1 勾軼;基于免疫算法和多傳感器信息融合的電機故障綜合診斷方法研究[D];沈陽工業(yè)大學;2010年

2 葉蓮;基于免疫算法的分類方法及其應用研究[D];重慶大學;2012年

3 李運江;基于免疫算法的音樂廳形體優(yōu)化[D];華南理工大學;2014年

4 呂崗;免疫算法及其應用研究[D];中國礦業(yè)大學（北京）;2003年

5 葉劍鋒;基于免疫優(yōu)化算法的陣列天線綜合的研究[D];哈爾濱工程大學;2009年

6 葛紅;免疫算法及核聚類人工免疫網(wǎng)絡應用研究[D];華南理工大學;2003年

7 王磊;免疫進化計算理論及應用[D];西安電子科技大學;2001年

8 宋曉琳;基于免疫算法的汽車主動懸架控制技術研究[D];湖南大學;2007年

9 劉智超;復雜信號解析與建模方法研究[D];南開大學;2009年

10 孫凱;基于免疫算法與分散搜索的鋼鐵生產(chǎn)調(diào)度研究[D];上海交通大學;2009年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 李子韻;基于免疫算法的配電網(wǎng)電容器優(yōu)化配置[D];河海大學;2003年

2 東方;基于免疫算法的物流配送VRP研究[D];大連海事大學;2006年

3 張志偉;仿生算法在第三代移動通信多用戶檢測中的應用[D];哈爾濱工程大學;2005年

4 原進凱;制造車間生產(chǎn)調(diào)度及其算法研究[D];武漢理工大學;2008年

5 賈凡;混合語音信號盲分離的算法研究[D];西安電子科技大學;2004年

6 胡德昆;基于人工免疫原理的郵件過濾系統(tǒng)研究與實現(xiàn)[D];電子科技大學;2005年

7 閆旺;基于免疫算法的物流配送車輛優(yōu)化調(diào)度研究[D];長安大學;2005年

8 胡春霞;免疫微粒群算法的研究[D];太原科技大學;2007年

9 夏潔;基于免疫算法的混合智能系統(tǒng)在異常檢測中的應用研究[D];中南大學;2007年

10 劉明;求解作業(yè)調(diào)度問題優(yōu)化算法的研究[D];吉林大學;2006年

  本文關鍵詞：基于GPU加速的細粒度模型并行免疫算法研究，由筆耕文化傳播整理發(fā)布。

本文編號：231430