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

发布时间：2017-01-02 09:23

  本文关键词：基于GPU加速的细粒度模型并行免疫算法研究，，由笔耕文化传播整理发布。

《大连理工大学》 2009年

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

张立花  

【摘要】： 免疫系统是目前已知的最精妙复杂的身体抵御外部有害物质的系统,它犹如一支训练有素的精锐部队,捍卫机体的健康。免疫细胞会对入侵者产生记忆,当下次同样的抗原入侵时,便以此抗体将其消灭,这正是“疫苗预防接种”的基本原理。人工免疫系统作为人工智能研究的一个新领域,期望借鉴生物免疫系统的信息处理机理和功能,进一步丰富人工智能能的研究手段,也可以说,生物免疫学的发展推动了人工智能的研究。 免疫系统的特点和作用机理对工程应用中许多复杂问题的求解有重要的启示和借鉴作用,作为一种智能优化计算方法,在实际工程中表现出巨大的潜力。但是在数值建模和优化计算等领域中,在处理大量数据和求解大规模复杂问题时,免疫算法(ImmuneAlgorithm,IA)仍然需要大量的计算时间,而并行的IA算法能极大地降低问题求解时间。 针对IA在解决大规模优化问题时需要消耗大量的时间无法达到实时性的问题,结合GPU的高速并行性,本文提出了一种基于GPU(Graphics Processing Unit,GPU)加速的细粒度并行免疫算法。本算法借助CUDA(Compute Unified Device Architecture,CUDA)统一架构,将实现过程转化成CUDA线程块并行计算过程,使得免疫算法在GPU中加速执行,在取得较好的优化效果的同时,解决了细粒度并行的群体规模限制问题,提高了算法的运行速度。本文的重要工作如下: (1)回顾了免疫算法的研究背景,产生与研究现状以及研究趋势,同时阐明了利用GPU来研究免疫算法的意义,阐述了本文的免疫算法研究模型。 (2)回顾GPU的发展,对GPU的通用计算以及应用做了一个大概的阐述,对NVIDIA GPU的统一计算设备架构(CUDA)的执行模型,存储模型以及通信模型做了简要的概述。 (3)阐述了免疫算法的生物学机理,对生物学整体上的认识可以有助于我们更好的对算法模型理解。 (4)针对传统算法在优化大规模等问题时计算量大和计算速度慢的问题,提出了基于GPU加速的细粒度并行免疫算法,通过图形硬件的并行性,将传统的递归算法转化成并行计算,大幅度提高了算法的执行速度,节约了计算时间。对算法进行程序实现,对算法在CPU和GPU中的时间进行比较,给出结果分析,证明了算法的可行性与实用性。

【关键词】：
【学位授予单位】：大连理工大学
【学位级别】：硕士
【学位授予年份】：2009
【分类号】：TP18
【目录】：

摘要4-5

Abstract5-9

引言9-11

1 免疫算法综述11-18

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

1.2 免疫算法产生与研究现状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 统一设备架构CUDA20-23

2.2.1 何为CUDA20

2.2.2 CUDA执行模型20-21

2.2.3 CUDA存储模型21-22

2.2.4 CUDA中的通信22-23

2.3 生物学基础以及人工免疫系统23-27

2.3.1 生物学基础23-25

2.3.2 人工免疫系统概述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 免疫算子的执行算法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中数据存储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中内存的优化50-52

3.9 GPU并行IA模型52-53

3.10 试验结果及分析53-55

3.11 本章小结55-56

结论56-57

参考文献57-61

攻读硕士学位期间发表学术论文情况61-62

致谢62-63

下载全文 更多同类文献

CAJ全文下载

(如何获取全文？ 欢迎：购买知网充值卡、在线充值、在线咨询)

CAJViewer阅读器支持CAJ、PDF文件格式

【引证文献】

中国期刊全文数据库 前1条

1 赵涛;王海帆;吴勇标;刘忆宁;;基于CUDA的口令字恢复系统设计与开发[J];保密科学技术;2012年08期

中国硕士学位论文全文数据库 前2条

1 张珩;基于GPU的图像粒子拟合及分类算法研究及应用[D];北京化工大学;2011年

2 李运赫;声场时域信号预报并行算法研究[D];哈尔滨工程大学;2012年

【参考文献】

中国期刊全文数据库 前10条

1 王磊,潘进,焦李成;免疫算法[J];电子学报;2000年07期

2 张四海,曹先彬,王煦法;基于免疫识别的免疫算法[J];电子学报;2002年12期

3 罗文坚,曹先彬,王煦法;用一种免疫遗传算法求解频率分配问题[J];电子学报;2003年06期

4 邵学广,孙莉;免疫-遗传算法用于混合物重叠核磁共振信号解析[J];高等学校化学学报;2001年04期

5 葛红;免疫算法综述[J];华南师范大学学报(自然科学版);2002年03期

6 张军,刘克胜,王煦法;一种基于免疫调节和共生进化的神经网络优化设计方法[J];计算机研究与发展;2000年08期

7 刘克胜,曹先彬,郑浩然,王煦法;基于免疫算法的TSP问题求解[J];计算机工程;2000年01期

8 张海峰,梁意文,代文;计算机免疫识别规则的演化挖掘[J];计算机工程;2001年11期

9 吴恩华,柳有权;基于图形处理器(GPU)的通用计算[J];计算机辅助设计与图形学学报;2004年05期

10 王磊,潘进,焦李成;免疫规划[J];计算机学报;2000年08期

中国博士学位论文全文数据库 前1条

1 王磊;免疫进化计算理论及应用[D];西安电子科技大学;2001年

【共引文献】

中国期刊全文数据库 前10条

1 吴大宏,赵人达;基于遗传算法与神经网络的桥梁结构健康监测系统研究初探[J];四川建筑科学研究;2002年03期

2 张安勤;数据挖掘与进化算法[J];安徽教育学院学报;2002年03期

3 尹峰,邓小鹏,许四毛;生物免疫机理在计算机安全领域的应用与发展[J];安徽电子信息职业技术学院学报;2004年Z1期

4 程家兴,陈万里;列车控制问题的计算分析及自适应算法[J];安徽大学学报(自然科学版);2002年02期

5 蒋中;遗传算法在PID参数优化中的应用[J];安徽建筑工业学院学报(自然科学版);2000年01期

6 阮怀忠,张建中;基于改进遗传算法的TSP问题求解[J];安徽建筑工业学院学报(自然科学版);2003年04期

7 陈杰,周冬华;浮点数编码的遗传算法在模糊控制器参数寻优中的应用[J];安徽建筑工业学院学报(自然科学版);2004年02期

8 方潜生;硬件进化(EHW)的研究与进展[J];安徽建筑工业学院学报(自然科学版);2004年06期

9 杨益;;基于FPGA的背包问题的求解[J];安徽建筑工业学院学报(自然科学版);2010年04期

10 周蕾;;人工免疫技术在农业信息化建设中的应用[J];安徽农业科学;2009年13期

中国重要会议论文全文数据库 前10条

1 杨益;方潜生;汪力君;;基于Handel-C的数字芯片的设计方法研究与实现[A];2005年“数字安徽”博士科技论坛论文集[C];2005年

2 胡杨林;蒋洁琼;王明煌;曾勤;邱岳峰;邹俊;陈红丽;FDS team;;聚变裂变混合堆长寿命锕系废料嬗变处理的中子学优化分析[A];安徽新能源技术创新与产业发展博士科技论坛论文集[C];2010年

3 孙燕;孙峥;黄鹍;;基于模拟退火机制的隔离小生境混合遗传算法[A];第二十六届中国控制会议论文集[C];2007年

4 孙燕;孙峥;;利用正交遗传算法优化交通检测点分布[A];第二十六届中国控制会议论文集[C];2007年

5 曹春红;张斌;王利民;李文辉;;基于免疫神经网络的几何约束求解技术的研究[A];第二十七届中国控制会议论文集[C];2008年

6 郭玉堂;刘路路;;基于佳点集遗传算法的边缘检测[A];第二十七届中国控制会议论文集[C];2008年

7 刘向;邹逢兴;张湘平;高政;;面向节能的混合流水车间调度方法的研究[A];第二十七届中国控制会议论文集[C];2008年

8 龚涛;杜常兴;;免疫计算研究的进展[A];中国自动化学会控制理论专业委员会A卷[C];2011年

9 汪民乐;高晓光;;GA早熟问题的定量分析及其预防策略[A];'2003系统仿真技术及其应用学术交流会论文集[C];2003年

10 田占东;张振宇;;用遗传算法确定反应速率方程参数[A];第三届全国爆炸力学实验技术交流会论文集[C];2004年

中国博士学位论文全文数据库 前10条

1 孙晓华;基于聚类的文本机会发现关键问题研究[D];哈尔滨工程大学;2010年

2 时长江;豆科类杂草种子图像识别系统研究[D];中国海洋大学;2009年

3 韩艳玲;可能性构造空间理论与计算机作曲思维模型研究[D];华中科技大学;2010年

4 彭北青;第三方物流配送车辆路径问题模型及算法研究[D];华中科技大学;2009年

5 黄林峰;多目标进化算法研究[D];中国科学技术大学;2009年

6 刘飞;四足机器人步态规划与平衡控制研究[D];中国科学技术大学;2010年

7 岑健;基于人工免疫系统的机组复合故障诊断技术研究[D];华南理工大学;2010年

8 杨红;污水生化处理的智能建模与优化控制策略应用研究[D];华南理工大学;2010年

9 魏建香;学科交叉知识发现及其可视化研究[D];南京大学;2010年

10 吴锋;基于GPU并行计算的数值模拟与燃煤锅炉系统的优化研究[D];浙江大学;2010年

中国硕士学位论文全文数据库 前10条

1 蒋慧;改进的遗传算法在电力系统无功优化中的应用[D];安徽工程大学;2010年

2 赫英毅;毫米波段基于TE_（21）模差网络设计[D];中国工程物理研究院;2009年

3 万成;动态环境下的元胞遗传算法研究[D];南昌航空大学;2010年

4 李坤;参数参与进化的自适应遗传算法研究[D];南昌航空大学;2010年

5 吴香庭;基于遗传算法的K-means聚类方法的研究[D];山东科技大学;2010年

6 王辉;基于改进遗传算法的物流配送路径优化研究[D];山东科技大学;2010年

7 纪二云;基于改进遗传算法的电力系统无功优化的研究[D];山东科技大学;2010年

8 施晓坤;煤炭企业人才结构优化[D];山东科技大学;2010年

9 王林吉;基于CIELAB均匀颜色空间和聚类算法的混纺测色研究[D];浙江理工大学;2010年

10 马宗梅;遗传算法在考试系统组卷中的应用与研究[D];郑州大学;2009年

【同被引文献】

中国期刊全文数据库 前10条

1 王握文;陈明;;“天河一号”超级计算机系统研制[J];国防科技;2009年06期

2 闫方;赵熠;李高;;细胞给药系统研究进展[J];国际药学研究杂志;2008年04期

3 张楠;;HPC标准“试水”石油勘探[J];石油石化物资采购;2009年09期

4 张鸿燕;耿征;;Levenberg-Marquardt算法的一种新解释[J];计算机工程与应用;2009年19期

5 肖江;胡柯良;邓元勇;;基于CUDA的矩阵乘法和FFT性能测试[J];计算机工程;2009年10期

6 范培勤;笪良龙;谢骏;;远程跨平台水下声场并行计算系统的实现[J];计算机工程;2009年20期

7 乐德广;常晋义;刘祥南;郭东辉;;基于GPU的MD5高速解密算法的实现[J];计算机工程;2010年11期

8 范培勤;笪良龙;卢晓亭;;面向水下声场计算的PC集群构建[J];计算机仿真;2007年12期

9 钱悦;;图形处理器CUDA编程模型的应用研究[J];计算机与数字工程;2008年12期

10 谭冬莲,肖汝诚;基于Levenberg-Marquardt算法的桥梁结构静力参数识别[J];交通运输工程学报;2005年03期

中国博士学位论文全文数据库 前1条

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

中国硕士学位论文全文数据库 前10条

1 张美香;贝叶斯文本分类器的研究与改进[D];太原理工大学;2005年

2 张丽丽;基于分布式计算的对称密码算法的暴力破解[D];西安电子科技大学;2008年

3 彭绍鑫;基于GPU的硬件加速方法及其在积分方程数值解中的应用[D];电子科技大学;2008年

4 彭俊杰;基于CUDA平台地震数据处理研究[D];湖南大学;2009年

5 张舒;模式识别并行算法与GPU高速实现研究[D];电子科技大学;2009年

6 苏丽丽;基于CPU-GPU集群的分子动力学并行计算研究[D];大连理工大学;2009年

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

8 周洁;基于GPU的WPA/WPA2-PSK高速破译方法研究[D];西安电子科技大学;2010年

9 谭霜;基于GPU微体系结构的高性能计算研究[D];国防科学技术大学;2009年

10 孙长征;数值天气预报云计算服务应用系统研究与实现[D];国防科学技术大学;2009年

【二级参考文献】

中国期刊全文数据库 前10条

1 周伟良,何鲲,曹先彬,程慧霞;基于一种免疫遗传算法的BP网络设计[J];安徽大学学报(自然科学版);1999年01期

2 陈立军;计算机病毒免疫技术的新途径[J];北京大学学报(自然科学版);1998年05期

3 胡朝阳,文福拴;免疫算法与其它模拟进化优化算法的比较研究[J];电力情报;1998年01期

4 谢敬东,王磊,唐国庆;遗传算法在多目标电网优化规划中的应用[J];电力系统自动化;1998年10期

5 谢敬东,唐国庆,吴新余;进化规划在电网规划中的应用[J];电力系统及其自动化学报;1998年02期

6 文福拴,韩祯祥;基于Tabu搜索方法的输电系统最优规则[J];电网技术;1997年05期

7 王磊,潘进,焦李成;免疫算法[J];电子学报;2000年07期

8 王磊,焦李成,刘芳,张艳宁;免疫进化子波网络及其学习算法[J];电子学报;2001年S1期

9 曹先彬,庄镇泉;一个基于启发式经验的立体布局进化策略[J];电子科学学刊;1998年03期

10 蔡文生,邵学广,潘忠孝;遗传算法用于化学结构图的同态研究[J];高等学校化学学报;1999年01期

【相似文献】

中国期刊全文数据库 前10条

1 张四海,曹先彬,王煦法;基于免疫识别的免疫算法[J];电子学报;2002年12期

2 谢开贵,周家启;基于免疫算法的配电网开关优化配置模型[J];电力系统自动化;2003年15期

3 李金城;张国忠;滕红丽;周晟;吴红霞;;免疫算法研究[J];沈阳航空工业学院学报;2005年05期

4 左兴权,李士勇;一种用于优化计算的自适应免疫算法[J];计算机工程与应用;2003年20期

5 梁鸿生,郝勇娜,王凯,柴继河;免疫算法[J];昆明理工大学学报(理工版);2003年05期

6 张礼兵,金菊良,王军;一种免疫遗传算法研究及应用[J];合肥工业大学学报(自然科学版);2004年07期

7 周凤岐,高康林;免疫计算在求解约束优化问题中的应用[J];微电子学与计算机;2004年11期

8 胡小明,吴耿锋,樊建;基于时间栅格法和免疫算法的机器人动态路径规划[J];计算机应用;2005年03期

9 吴进波;熊盛武;徐宁;;免疫模拟退火算法求解TSP[J];计算机工程与应用;2006年28期

10 钱红建;叶洛华;杜翠娣;王淑萍;;基于遗传免疫算法的网络入侵检测的研究[J];信息化建设;2006年10期

中国重要会议论文全文数据库 前10条

1 龚涛;杜常兴;;免疫计算研究的进展[A];中国自动化学会控制理论专业委员会A卷[C];2011年

2 沈冠町;徐本柱;刘晓平;;改进的免疫算法在作业车间调度中的应用[A];全国第21届计算机技术与应用学术会议（CACIS·2010）暨全国第2届安全关键技术与应用学术会议论文集[C];2010年

3 周德义;左春柽;李静;苗菲;张舟;;基于免疫算法的齿轮减速器区间优化研究[A];走中国特色农业机械化道路——中国农业机械学会2008年学术年会论文集（下册）[C];2008年

4 许殿;史小卫;;基于免疫算法的微波电路优化技术[A];2003'全国微波毫米波会议论文集[C];2003年

5 王玮;占荣辉;张军;;基于免疫算法的距离像长度估计[A];第十四届全国信号处理学术年会(CCSP-2009)论文集[C];2009年

6 苏兆品;蒋建国;尹翔;夏娜;李勇;;一种基于免疫的敏捷供应链形成算法[A];全国先进制造技术高层论坛暨制造业自动化、信息化技术研讨会论文集[C];2005年

7 孟科;李绍军;钱锋;;实数编码免疫算法在溶剂脱水塔软测量中的应用[A];'2006系统仿真技术及其应用学术交流会论文集[C];2006年

8 吕岗;赵鹤鸣;;一种优化前向神经网络权值的免疫算法[A];2003年中国智能自动化会议论文集（上册）[C];2003年

9 余建军;孙树栋;;模拟退火免疫混合算法[A];全国第16届计算机科学与技术应用（CACIS）学术会议论文集[C];2004年

10 任伟建;霍凤财;王爱军;;人工免疫系统原理及其应用[A];2004中国控制与决策学术年会论文集[C];2004年

中国博士学位论文全文数据库 前10条

1 勾轶;基于免疫算法和多传感器信息融合的电机故障综合诊断方法研究[D];沈阳工业大学;2010年

2 叶莲;基于免疫算法的分类方法及其应用研究[D];重庆大学;2012年

3 李运江;基于免疫算法的音乐厅形体优化[D];华南理工大学;2014年

4 吕岗;免疫算法及其应用研究[D];中国矿业大学（北京）;2003年

5 叶剑锋;基于免疫优化算法的阵列天线综合的研究[D];哈尔滨工程大学;2009年

6 葛红;免疫算法及核聚类人工免疫网络应用研究[D];华南理工大学;2003年

7 王磊;免疫进化计算理论及应用[D];西安电子科技大学;2001年

8 宋晓琳;基于免疫算法的汽车主动悬架控制技术研究[D];湖南大学;2007年

9 刘智超;复杂信号解析与建模方法研究[D];南开大学;2009年

10 孙凯;基于免疫算法与分散搜索的钢铁生产调度研究[D];上海交通大学;2009年

中国硕士学位论文全文数据库 前10条

1 李子韵;基于免疫算法的配电网电容器优化配置[D];河海大学;2003年

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

3 张志伟;仿生算法在第三代移动通信多用户检测中的应用[D];哈尔滨工程大学;2005年

4 原进凯;制造车间生产调度及其算法研究[D];武汉理工大学;2008年

5 贾凡;混合语音信号盲分离的算法研究[D];西安电子科技大学;2004年

6 胡德昆;基于人工免疫原理的邮件过滤系统研究与实现[D];电子科技大学;2005年

7 闫旺;基于免疫算法的物流配送车辆优化调度研究[D];长安大学;2005年

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

9 夏洁;基于免疫算法的混合智能系统在异常检测中的应用研究[D];中南大学;2007年

10 刘明;求解作业调度问题优化算法的研究[D];吉林大学;2006年

  本文关键词：基于GPU加速的细粒度模型并行免疫算法研究，由笔耕文化传播整理发布。

本文编号：231430