（计算机应用技术专业论文）基于gpu加速的细粒度模型并行免疫算法研究.pdf

大连理工大学硕士学位论文 摘要 免疫系统是目前已知的最精妙复杂的身体抵御外部有害物质的系统，它犹如一支训 练有素的精锐部队，捍卫机体的健康。免疫细胞会对入侵者产生记忆，当下次同样的抗 原入侵时，便以此抗体将其消灭，这正是“疫苗预防接种”的基本原理。人工免疫系统 作为人工智能研究的一个新领域，期望借鉴生物免疫系统的信息处理机理和功能，进一 步丰富人工智能能的研究手段，也可以说，生物免疫学的发展推动了人工智能的研究。 免疫系统的特点和作用机理对工程应用中许多复杂问题的求解有重要的启示和借 鉴作用，作为一种智能优化计算方法，在实际工程中表现出巨大的潜力。但是在数值建 模和优化计算等领域中，在处理大量数据和求解大规模复杂问题时，免疫算法( h n m u n e a l g o r i t l l l l l ，i a ) 仍然需要大量的计算时间，而并行的认算法能极大地降低问题求解时 间。 针对n 在解决大规模优化问题时需要消耗大量的时间无法达到实时性的问题，结 合g p u 的高速并行性，本文提出了一种基于g p u ( g r a p h i c sp r o c e s s i n gu n i t ，g p u ) 加 速的细粒度并行免疫算法。本算法借助c u d a ( c o m p u t eu n i f i e dd e v i c ea r c h i t e c t u r e ， c u d a ) 统一架构，将实现过程转化成c u d a 线程块并行计算过程，使得免疫算法在 g p u 中加速执行，在取得较好的优化效果的同时，解决了细粒度并行的群体规模限制问 题，提高了算法的运行速度。本文的重要工作如下： ( 1 ) 回顾了免疫算法的研究背景，产生与研究现状以及研究趋势，同时阐明了利 用g p u 来研究免疫算法的意义，阐述了本文的免疫算法研究模型。 ( 2 ) 回顾g p u 的发展，对g p u 的通用计算以及应用做了一个大概的阐述，对 n v i d i ag p u 的统一计算设备架构( c u d a ) 的执行模型，存储模型以及通信模型做了 简要的概述。 ( 3 ) 阐述了免疫算法的生物学机理，对生物学整体上的认识可以有助于我们更好 的对算法模型理解。 ( 4 ) 针对传统算法在优化大规模等问题时计算量大和计算速度慢的问题，提出了 基于g p u 加速的细粒度并行免疫算法，通过图形硬件的并行性，将传统的递归算法转 化成并行计算，大幅度提高了算法的执行速度，节约了计算时间。对算法进行程序实现， 对算法在c p u 和g p u 中的时间进行比较，给出结果分析，证明了算法的可行性与实用 性。 关键词：免疫算法；c p u ；g p u ；c u d a ；并行 基于g p u 加速的细粒度模型并行免疫算法研究 ap a r a l l e l i m n m ea l g o r i t h mb a s e do nf i n e - 伊a i n e dm o d e lw i t h g p u a c c e l e r a t i o n a b s t r a c t a tp r e s e n ti m m u n es y s t e mi s t l l em o s ts u b t l e t yc o m p l e xs y s t e mt h a tb o d yw i t h s t a n d s d 锄a g e s 缸o me x t e m a le n v i r o m n e n ta sw ea l lk n o w ，m ei m m u i l es y s t e l l li sl i k eaw e l l 一慨n e d e l i t e 臼o o p sa r l dp r o t e c tb o d yh e a l m i l l l m u n ec e l l sw o u l dg e i l e r a t em e l t l o 巧t 0i i l t m d e r ，w h e n t l l es 锄ea i l t i g e i l si n v a d eb o d yn e x tt i m e ，m ea i l t i b o d i e sw i l lp 西s hn l ea 1 1 t i g e n sa c c o r d i n gt o m 锄。巧t h i si st h e 向n d 锄e n t a lp 血c i p l eo fi m m u n ev a c c i n ei n o c u l a t i o n a n i f i c i a li m m u n e s y s t e m 勰an e w r e s e a r c ho fa r t i f i c i a li i l t e l l i g e n c ec a nb eam e a n sw t l i c hi sf m h e re 1 1 r i c ht h e s t u d yo fa r t i 6 c i a li n t e l l i 髀l c ea c c 0 r d i n gt ot l l ei m m u n es y s t e l l lo fb i o l o 西c a li n f o 订n a t i o n p r o c e s s i n gm e c h 锄i s m ，i no t l l e r 、阳r d s ，b i o l o 酉c a li i m u i l o l o g yp r o m o t e sm ed e v e l o p m e n to f 啦i f i c i a li n t e l l i g e i l c er e s e a r c h t h ec h a r a c t “s t i c sa l l dm n c t i o nm e c h a i l i s mo fi m m u n es y s t e i nh a v ea i li m p o r t a i l t i n s p i r a t i o na n dr e f 打e n c ef o rs o l v i n gm a n yc o m p l e xp r o b l e m si ne n 西n e e r i n g 印p l i c 撕o n s ， i m m u n ea l g o r i t l l mi sp u tf 1 0 n v a r da i li n t e l l i g e i l to p t i m i z a t i o nm e t h o da c c o r d i n gt ob i o l o g y i m m u l l em e c h a n i s m ，i th a sp r o v e i lt ob eap o w 曲l 舀o b a lo p t i m i z a t i o nm e m o da 1 1 ds h o w s 莎e a tp o t e n t i a li l lp m c t i c e h o w e v e r ，i ts t i l ln e e d sp l e n t yo fc o m p u t i n g t i m ew h e ni tp r o c e s s e s m u c hd a t aa n dw h e nl a r g e - s c a l ec o m p l i c a t e dw o r ki si r o l v e di nw l l i c hm a mm o d e l i n ga n d o p t i m i z a t i o na r eh i 曲l yd e m a n d e d ，w h e r e a sp a r a l l e l 认c o m e si n t ob e i n ga j l db e c o m e sah o t s p o ts i n c ei tc a nr e d u c ew o r k i n g - o u tt i m ed 删【n a t i c a l l y a 1 f t e ru n d e r s t a l l d i n gt h ed e v e l o p m e i l tt r e n do fm ec u r r e l l t 认a th o m ea 1 1 da b r o a d ，a i m i n g a t 吐l ep r o b l e r l lt h a t 认c a i lc 0 n s u m ep l e n t yt i m ew h e l ls e t t l e m e n to fl 魍g e s c a l eo p t i m i z a t i o n p r o b l e m s ，w er a i s e daf i n e - 伊a i n e d 认a 1 9 0 r i s mb a s e do ng p ua c c e l e r a t i o n ，w em a l 【eu s e o f c u d at ot h ec a l c u l a t i n gp r o c e s so fw o r l 【i n g - o u ti n t op a m l l e lp r o c e s so ft 1 1 r e a db l o c ka s a c h i e v i n gag o o do p t i m i z a t i o ne 贷e c t ，i ta l s oi n c r e a s e st l l ei ai nt h e6 n e - 伊a i n e dp a r a l l e l i s m ， s p e e d su pi t sm n n i n ga n dp r 0 v i d e so r d i n a u u s e rw i t haf e a s i b l ei as o l u t i o n f i r s t l y ，w er e c a l lt h ei m m u n ea l g o r i t h i i lr e s e a r c hb a c k 孕d u n d ，t h eg e n e r a t i n gp r o c e s s ， c 硼r e n ts t a t ea n dt r e n do fi a ，a i l dw ee x p l a i nt h es i 印i 6 c a i l c em a tw em a k eu s eo fg p ut o r e s e a r c hi aa n di am o d e l i n g s e c o n d l y ，i n t r o d u c i n gt h ed e v e l o p m e n to fg p ua n di l l u s t r a t i n gg e n e m lp u r p o s e c o m p u t a t i o na i l di t sa p p l i c a t i o n ，w eh a v e 百v e nab r i e fo v e n ，i e wa b o u tn v i d i ac u d a e x e c u t i o nm o d e l ，s t o r a g em o d e la n dc o m m u n i c a t i o nm o d e l 一i i 大连理工大学硕七学位论文 t h i r d l y ，d e s c r i b i n gt h eb i o l o 西c a lm e c h a n i s mo fi m m u n ea l g o r i t h mi no r d e rt ob e t t e r u n d e r s t a n d i n gi am o d e l f i n a l l y ，a i m i n ga tm ee x i s t i n gp r o b l e n l ss u c ha sh e a 、7c a l c u l a t i o na n dl o ws p e e di n o p t i m i z i n gp r o b l e i i lt h i sp a p e rr a i s eap a r a l l e l i m m u n ea l g o 订t b a s e do nf i n e g r a i n e dm o d e l w i t l lg p u a c c e l e r a t i o n ，t a k i n ga d v a j l t a g eo fg p u p a r a l l e l i s m ，c o n v e n i n gt h er e c u r s i v ei n t o c o n c u r r e n t c o m p u t a t i o n ， t 1 1 e l lt h ea l g o r i t h mi n c r e a s e s p e e d “i d e n t l y m e a n w h i l e ，t l l e c o m p 撕s o no fc p ua n dg p u t i m ec o n s 啪i n gi ss h o w e di n “sp a p e r ，t h er e s u l ts h o w st h a tt h e n e w a l g o r i t h mi sf b a s i b i l i t ya n dp r a c t i c a l i t y k e yw o r d s ：i a ；c p u ；g p u ；c u d a jp a r a e i i i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 作者签名： 查重鱼型塑堕鱼塑塑鏖塑叠塑鱼壅昱! 坌塑垦 型垦堑日期：吐年旦月j l 日 大连理t 大学硕十学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：趟鱼! 塑壅鱼塑垫巡鲎鱼垒垂簋塑窒 作者签名：塾童查日期：! ! 年旦月生日 ，、厂 导师签名：q 型迸 日期：型年生月j l 日 大连理丁大学硕士学位论文 引言 随着现代科学技术的不断发展，现在已经是一个信息化的社会，在当今全球信息化 社会中，很多学科只在自己的领域中发展已经落伍了，而且只利用本学科的知识已经不 能对社会的发展做出太大的贡献，因此在人类需求不断提高的今天，只是利用单学科领 域的知识解决实际的问题已经显得力不从心，而现在计算机又是相当的普及，所以采取 了其它学科与计算机相结合的研究路线【l 】，因此多学科相互交叉，相互渗透成为学科发 展的趋势。 人工智能( a n i f i c i a li n t e l l i g e i l c e ，a i ) 是计算机发展到一定程度的产物，随着计算 机的发展和普及，人们开始用计算机来模拟生物体的智能【2 】。自人工智能产生以来，与 生物技术、空间技术一起成为世界的三大尖端技术，以人工智能为龙头，以各种高新技 术产业为主体的智能时代将会彻底改变人类的生活方式，智能时代才是真正的知识经济 时代。但是作为人类历史上最复杂、最困难的学科之一，人工智能在最初的发展时候错 误的假定了真实世界的复杂性，认为人工智能存在一个像物理学一样简单的普适理论【3 】， 可能用一个简单的数学模型来近似的表示真实世界，事实证明这样假设是不正确的，用 这种简单的数学模型表现出来的行为与智能还有很大的距离，所以智能行为是不能用简 单的数学模型来表述的，许多学者认为既然人工智能是模拟生物的行为，那么就应该从 生物学的角度去研究【4 】，沿着这种思路所以仿生模拟成为了许多学者争相研究的方向， 也取得了很好的效果。 人工免疫系统( a n i f i c i a li i t l m u l l es y s t e i n ，a i s ) 是模拟生物体免疫系统功能的一种 仿生智能模拟方法，它是受生物体免疫系统的启发，通过学习外界物质的自然防御机理 的学习技术，提供噪声忍耐、无教师学习、自组织、记忆等进化学习机理，结合进化算 法、神经网络等形成了新颖的解决问题的方法和途径，免疫系统作为一种内在的并行处 理系统，其独特的机理和高效的效率已在控制5 1 、规划【6 1 、设计【7 1 、组合优化【8 】、图像处 理【9 1 、数据处到10 1 、知识挖掘【1 1 1 、机器人f 1 2 】、故障检测【1 3 1 以及网络【1 4 】方面展现出了不 可低档的魅力。虽然广大学者对免疫系统应用人工智能领域进行了很多的研究，但是将 其作为智能算法也是近十几年的事情，人工免疫系统是新兴的研究领域。 旅行商问题即t s p ( t r a v e l i n gs a l e s m a j lp r o b l e m ，t s p ) 是数学著名的n p c ( n o n d e t e r n l i n i s t i cp o l y n o m i a lc o m p l e t e l y ) 问题，该问题是一个组合优化问题，此问题 可以证明具有n p c 计算复杂性，是最复杂的问题，所以任何能使该问题的求解得以简化 的方法都会受到高度的评价和关注。当然当城市数目n 比较小时可以用列举的方式将全 部的可行解全部列出来求得最短的路径，但是我们知道随着城市数n 的急剧增长，使得 基丁g p u 加速的细粒度模型并行免疫算法研究 计算所有可能路径的长度变得不切实际，因为路径数为n ! ，从这里看出当n 很大时， 列举所有路径是不可能的。通过计算证明，不用人工而通过计算机来计算所有路径的长 度所需要的时间也是不能忍受的，所以很多人就想到不计算所有路径的长度，只计算一 个跟最优解近似的解也就是可行解。得到可行解的方法很多，其中遗传算法来解决t s p 问题是非常经典的方法【l5 1 6 】，此方法得到的优化结果比最原始的方法有了很大的改进， 但是传统的遗传算法有两大缺点，第一：在处理城市数目很多时速度还是很慢，实时性 不高，第二：标准的遗传算法早熟的概率较大。 本文要做的工作就是要解决上述的两大缺点，所以本文的创新有两点：其一，为 了提高寻求最优解的速度，我们利用g p u ( g r a p h i cp r o c e s su i l i t ，g p u ) 加速的方法， 大大提高了求解速度。其二，利用新兴的研究领域a i s 来代替传统的只是用单纯的遗传 算法来模拟t s p 问题，因为a i s 比较擅长局部搜索而且能够有目的有选择的利用待求信 息的特征来抑制搜索过程中出现的早熟现象，所以模拟效果比标准遗传算法要更好一 些，基于这两点我们提出了基于g p u 加速的细粒度并行人工免疫算法的方法，该方法 充分的利用n v i d i ag p u 的统一计算设备架构( c o m p u t eu n i f i e dd e v i c ea r c k t e c t l l r e ， c u d a ) ，将模拟人工免疫算法的过程转化为c u d a 线程块的并行模拟过程，使得寻求 较优解的过程完全在g p u 中进行，实验证明我们在保证较好解的同时，也保证了很高 的求解速度，可以在一些实际应用中，达到实时性的要求。 本文第一部分介绍免疫算法的研究背景、研究现状、趋势以及意义，第二部分则重 点介绍一下g p u 的通用计算，最新的g p u 并行技术统一计算设备架构c u d a 、如何利 用c u d a 进行并行编程以及免疫算法的生物学基础，第三部分是我们工作的重点，讲 述了基于g p u 加速的并行细粒度免疫算法模型，对实验的优化结果进行分析，给出了 相应的加速比，最后总结全文，指出其中的不足以及以后需要进一步的研究的问题。 大连理t 大学硕士学位论文 1 免疫算法综述 免疫系统( h 皿u n es y s t e m ，i s ) 是继进化计算、神经网络之后一种新的智能计算研究 方向，在伴随着科学技术日新月益的同时，对一些经典的n p 问题人类仍然不能解决， 在很多情况下仅仅依靠单学科的理论和方法仍然很难得到满意的答案，甚至是没有办法 解决，那么就促使人们去寻找新的方法和手段，人类利用其它领域，其它学科的理论， 方法和技巧来解决一些难以解答的问题领域，在这种趋势下多交叉学科成为研究的潮 流。而作为仿生学被研究的免疫系统是生命科学与计算机科学相交叉而形成的新的学 科，是很多学者研究的热点，其研究主要通过深入探索生物免疫系统所蕴含的信息处理 机制，从而建立相应的工程模型与算法，然后将这些模型与算法应用到各个方面，并取 得了很好的效果。 1 1免疫算法研究背景 在生命科学研究领域中，人们开始对遗传自然现象进行广泛深入的研究，六十年代， b a 西e y 和r o s e n b e r g 等先驱在对这些成果进行分析与理解的基础上，借鉴其相关内容及 知识，特别是遗传学方面的理论与概念，将其成功应用于工程科学的某些领域，得到了 很好的效果。但是就遗传算法本身而言，由于自然进化和生命现象的“测不准”性，遗 传算法不可避免地存在概率算法的缺陷，例如，在对算法的实施过程中两个主要遗传算 子都是在一定发生概率的条件下，随机地、没有指导地迭代搜索，因此它们在为群体中 的个体提供了进化机会的同时，也不可避免的产生了早熟、种群多样性减少等退化现象， 在实践中，遗传算法最明显的缺点就是它的收敛问题，包括收敛速度慢和未成熟收敛【1 7 】， 还有，更实际的问题就是每一个待求的实际问题都会有自身一些基本的、显而易见的特 征信息或是先验知识，然而，遗传算法的交叉和变异算子在求解问题时可变的灵活程度 较小，但是这些信息或者先验知识对算法的通用性是非常有好处的，但是在标准的遗传 算法中却很难发挥问题的特征信息对求解问题时的指导作用，特别是在求解一些复杂问 题时，这种忽视所带来的损失往往就比较明显。实践也证明，仅仅使用遗传算法或者以 其为代表的进化算法，在模仿人类智能处理事物的能力方面远远不足。 进化算法的不足也为其进一步研究指明了方向。许多学者认为，从求解问题本身特 点出发，对算法的改进思路至少包括三个方面，第一，对进化算法本身算子的改进和丰 富，以形成新的进化算法；第二，基于智能综合集成的观点，强调多智能系统的相互协 作，实现优势互补，构成新的智能混合系统；第三，由于以遗传算法为代表的进化算法 在模仿生物系统的能力方面还远远不够，因此有必要更广泛地挖掘与利用生物系统的智 基于g p u 加速的细粒度模型并行免疫算法研究 能信息处理特征，发展新的仿生智能系统，而受到生物体免疫系统启发所提炼出来的免 疫算法正符合人们在工程中的研究需要，因此免疫算法在这样的需求背景下越来越受到 广大学者的重视。 1 2 免疫算法产生与研究现状 最早的与免疫算法相关的理论可以追溯到1 9 5 9 年澳大利亚一位学者名叫b u m e t 提 出的基于生物抗体的克隆选择学说【l 引，这一学说观点是基于对生物体免疫系统的认识 而提出来的，也就是在生物体受到细菌侵入时，生物体就会自动识别出细菌也就是抗原， 从而受体会使免疫细胞活化，繁殖，分化，经过这些步骤后生物体内就会出现抗体和免 疫记忆细胞，这样等下次再遇到相同细菌的时候，机体就会在短时问内使抗体的浓度迅 速增加，这样就达到了保护生物体的效果。这时只是学说涉及到免疫的一些初步理论， 并没有形成系统的理论，也没有提出一个模型。第一个模型的提出是在1 9 7 3 年美国诺 贝尔奖获得者j e m e 提出了特型网络理论【1 9 】，给出了免疫算法的数学框架，并且采用的 是微分方程来仿真淋巴胞的动态变化，独特型网络观点认为：生物体内的淋巴细胞并不 是孤立存在的，不同种类的淋巴细胞之间是相互联系的，抗体与抗体之间，抗体与抗原 之间是相互作用的，通过这种相互的反应会形成一个动态且平衡的网络，随后又出现了 另外一种方法来描述这独特型网络学说即：概率方法【2 0 1 ，此方法是p e r e s l o n 提出来的， 这种方法比前面用微分方程的方法简单了一些所以此方法在自适应控制以及故障检测 诊断等方面得到了广泛的应用。 以上讲述的理论是非常早期的研究成果，之后相当长的一段时间由于多种原因免疫 系统并没有得到很好的发展。在1 9 8 6 年的时候，f a m e r 等人对生物体免疫系统中所蕴 含的丰富的信息处理机制进行了充分的认识，从而提出了基于免疫网络学说的免疫系统 动态模型【2 ，他们的做法是：先用一组随机产生的微分方程建立起人工免疫系统，然后 通过采用适应度阈值过滤的方法去掉方程组中不合适的方程，对于保留下来的方程则采 用交叉、变异、逆转等操作产生新的微分方程，然后不断的进行迭代计算直到找到一组 合适的方程为止，这种算法成功的运用到了机器人运动路径规划中。在1 9 9 6 年的1 2 月， 在日本举行了关于免疫系统的国际性专题讨论会，在这个会议上提出了“人工免疫系统” 的概念，可以说拉开了人工免疫系统研究的序幕。随后，人工免疫系统进入了兴盛发展 时期，人工免疫系统著名研究学者d d a s g u p t a 和丁永生等人认为人工免疫系统已经成 了人工智能领域中继神经网络、进化计算之后的又一个研究热点，并且相关的论文和研 究成果正在逐年增加，图1 1 和图1 2 分别是从1 9 9 4 年丌始，中国期刊网e i 和i e e e 分 一4 一 大连理工大学硕士学位论文 别收录免疫算法论文的情况。1 9 9 7 和1 9 9 8 年i e e es y s t e m s ，m a na i l dc y b 啪e t i c s 国际 会议还组织了相关专题讨论，并成立了“人工免疫系统及应用分会 ，在2 0 0 1 年时 c o n g r e s so ne v o l u t i o n a r yc o m p u t a t i o n 国际学术会议决定每年开始都举办一届有关人工 免疫系统和免疫算法的专题讨论会。 图1 1中国期刊网e i 收录情况 f i g 1 1 c n e ip a p e r 图1 2i e e e 收录情况 f i g 1 2 i e e ep a p e r 在j e n l e 提出免疫网络模型之后k e p h a n 、b e r s i n i 、v a r e l a 等一些免疫理论学者都相 继发表了有关论文【2 2 - 2 4 1 ，d a s g u p t a 等人基于非选择算法提出了一种时序数据异常检测算 法【2 5 】和实值非选择算法【2 6 1 ，e n d o h s ，t o m a n ，y 锄d a k 等在1 9 9 8 年的时候最早提出了 用免疫优化算法来解决t s p 问题【27 1 ，可以说这三个人为免疫算法的应用做出了很大的 贡献，d e a t o nr 等人利用免疫算法“自我与“非自我的生理特性提出了一种d n a 的计算【2 引，h o f h l e y r 等人提出的人工免疫系统具有分布式、鲁棒性、动态性以及多样性 和自适应性等特剧删，这种免疫系统对于保护计算机免于受到非法入侵具有很好的作 用。m 撕u s zo s z u s t 和m 撕a i lw y s o c k i 两位学者利用免疫算法分布式的特性来解决优化 问题【3 0 】，取得了很好的效果。s a s a l 【im 和1 w a 剐【( um 等人提出了基于免疫反馈机制的 一种自适应学习神经网络控制器【3 ，在神经网络控制器中加入免疫算法使得控制器能够 快速的对外界进行反应。h e d e r 和h e l i o 编写的s 叫i e si nc o m p u t a t i o n a lh l t e l l i g e n c e 一书中在一章中介绍了用人工免疫算法来解决优化问题时所涉及到的一些算法【3 2 1 ，比 如：克隆选择算法、免疫网络算法、混合免疫算法等等，对这些算法的应用情况以及每 种算法的优缺点进行了详细的分析。g o n z a l e z 提出了一种自适应性非选择免疫算法，主 要思想是采用自适性变异技术来调节检测器集合进化过程中的变异概率【3 引。a y a r a 等人 研究了用于非选择的各种不同的检测器生成方法，并对比分析了时间与空间复杂度【3 引。 基丁：g p u 加速的细粒度模型并行免疫算法研究 由于国内现在对免疫系统的机理认识还不是十分系统和深入，所以现在有关免疫算 法的研究主要是集中在利用其机理以改进其它的算法，如：免疫遗传算法、免疫神经网 络等等，对于人工免疫算法本身的研究成果并不是很多，主要是基于克隆选择原理的克 隆选择算法、基于阴性选择原理的阴性选择算法等等。在国内，以中国科技大学的王 煦法教授，曹先彬等人为首开展了人工免疫算法的研究，他主要是研究免疫遗传算法、 进化计算、入侵检测、优化计算等领域【3 5 舶】，对免疫算法进行一些改进，他们的改进克 服了遗传算法早熟现象，得到了满意的效果，他们借鉴生物体免疫中的独特性网络调节 理论，将进化个体对应为免疫系统中的抗体，群体适应度作为抗原，提出了一种改进的 遗传算法，实现了种群在群体收敛性和个体多样性之问动态平衡的调整，成功解决了装 箱问题和成功实现了t s p 优化问题，王磊从不同角度研究利用免疫生物机理来改进遗传 算法【4 5 1 。目前在人工免疫系统研究方面国内除了王煦法教授领导的团队外，浙江大学， 哈尔滨工程大学，武汉大学，西安电子科技大学，西安交通大学，华中科技大学，四川 大学等多所图内高等院校都有专门的研究人员从事该领域的研究，其中成就较大的高校 应该是西安电子科技大学以焦李成教授为代表的研究实验室，以焦李成教授为领导的整 个团队从事这个领域的研究，做出了很大的成绩，焦李成教授不仅较早的在 i c s p 9 8 ( i n t e m a t i o n a lc 锄ps t a f r p r o 蓼a m ) 上首先提出了一种免疫遗传算法并应用在典型 的优化问题的求解中m 钠】，而且还提出了具有较完善的理论基础的免疫克隆算法以及一 系列的改进算法并且还在2 0 0 6 年的时候出版了免疫优化计算、学习与识别一书， 对国内免疫算法的研究起到一个向导的作用，可以说焦李成教授的成绩是非常卓越的， 武汉大学提出了基于多代理的计算机安全免疫系统检测模型，并在自己和非己的识别规 则上做了深入研究，提出了用演化挖掘的方法提取规则【5 0 1 ，武汉大学提出了基于主机安 全扫描的计算机免疫系统模型【5 ，四川大学李涛教授领导的团队也提出了有效的免疫算 法模型【5 引。由于免疫算法是源于免疫系统的启示而构造的新型多峰值寻优算法，针对免 疫系统的识别多样性的特性会有不同的免疫算法的具体实现形式，葛红对这些算法进行 了总结归纳筘引，对现在算法进行了分类并且对各类算法的形式、特性和应用情况进行了 综述。潭j 砬政等人提出的基于精英策略的免疫遗传算法以及应用【5 4 】，该算法是提出了新 颖的精英策略的选择和精英交叉操作，此改进方法收到了较好的效果。 一6 一 大连理工人学硕士学位论文 1 3 免疫算法研究趋势以及意义 1 3 1 免疫算法研究趋势 免疫算法自从被作为智能计算研究之r 起到目前为止已经产生了很多的研究成果， 但是由于其理论之新，还没有对免疫系统理论进行更深入的认识和发掘，所以在以后的 免疫算法研究中将会在建模、算法设计以及应用领域还会有相当大的作为。以后人工免 疫系统的研究热点本人认为将会集中在以下几个方面： ( 1 ) 免疫智能计算。虽然从一开始免疫系统就被作为智能计算而提出来的，到现 在为止也有一些的研究成果，但是利用免疫系统进行智能计算并没有做到真j 下意义上的 智能，有很多只是给研究的方向上穿上了一层智能计算的外衣，虚而不实。从现在国外 研究的文献上来看，根据生物免疫系统来发展一些新的免疫智能计算方法和建立一些新 型的免疫计算系统模型特别是用智能化技术来增强免疫算法的异己识别能力是未来在 免疫智能计算上的发展趋势。 ( 2 ) 建立混合智能系统。这些混合智能计算的缺点是只是利用了很少的免疫系统 机制来改进其它算法以及其算法的搜索性能。在未来的研究中应该将免疫系统抗体多样 性的遗传机制以及免疫学习机制有机的结合在一起来更大程度上的改进人工神经网络， 模糊系统，以及遗传算法等等。 ( 3 ) 免疫算法有效性的研究。就像人的免疫系统的抗病能力，人工系统的免疫算 法必须是有效的，必须能够有效的自适应地减弱或者是消除外来的损害，比如杀毒。 ( 4 ) 免疫理论的研究。免疫系统作为智能计算的理论研究还相当的少，其主要是 借助于数学、混沌、计算智能、智能主体等理论深入研究人工免疫系统的机制以及免疫 计算原理等。到目前为止免疫算法都是针对特定问题而提出来的，对算法的时间复杂度 以及空间复杂度估计、收敛性的证明等深刻而具有普遍意义的研究成果还是很少。在未 来的研究当中，很多学者会对此进行进一步的研究。 ( 5 ) 免疫算法的智能效果和并行性的研究。将免疫算法引入到应用系统当中能否 增强系统的整体智能性能是评价算法成败的一个重要指标。免疫算法的并行化是算法发 展的必然趋势并且正在成为研究的热点，而免疫系统潜在的并行处理能力无疑为免疫算 法并行化奠定了根本的生物基础。 1 3 2 免疫算法的研究意义 任何一个研究成果都是与实践分不开的，一个新理论的出现都是由于在实践中需要 找出解决问题办法而产生的，新的理论成果在实践中得到应用才有价值。同样免疫算法 的出现就是为了解决实际中比如调度问题，优化问题，网络等问题所遇到的问题，在这 基丁g p u 加速的细粒度模型并行免疫算法研究 些领域都得到了很好的应用。在实践工程中很多问题其实都可以归结为优化问题。优化 问题大体上可以分为两类：函数优化问题和组合问题，其中优化问题的对象是一定区间 内的连续变量，而组合优化的对象是解空i 日j 的离散状态。 随着人类需求的不断提高，很多问题比如：旅行商问题，布线问题、图着色问题、 分配问题等呈现出非线性、不可导、非凸的特点，利用传统的方法很难得到满意的答案， 有些方法虽然可以得到准确的答案但是却又需要消耗大量的时间，人们无法忍受，所以 从实际应用的角度出发，能够得到满意解的近似算法或者是以较高的概率保证解的质量 的随机算法得到了广大学者的重视。近几十年以来，人们从不同的角度出发对生物系统、 人类自身以及其行为特征进行模拟与研究，开发出了很多通用性的智能算法比如：遗传 算法( g a ) ，模拟退火算法( s a ) 、粒子群算法( p s o ) ，此类算法在优化问题上得 到了广泛的应用，特别是在难求解的组合优化问题上成果更显著，其所求的结果虽然有 些时候比传统的算法好，但是这些算法存在一些很大的缺点而且本身是无法克服的，比 如：全局收敛和局部收敛的矛盾以致造成早熟问题，致使上述算法的应用受到很大的限 制。 但是依据生物系统研发出来的免疫算法却有效的解决的上述缺陷。第一：免疫系统 具有特异性，一种抗体只能强烈的结合几种类似的抗原决定基，当病毒入侵时，抗体首 先进行免疫识别，然后快速的产生抗体来消灭病毒，与生物进化过程相比，这是一个快 速的过程，一般只有几分钟到几天的时间。第二，据生物学家研究免疫系统大概有1 0 8 种 蛋白质，但是外部的潜在的抗原或者是待识别的模式有1 0 1 6 种之多，但是这些模式并不 一定是对抗体进化都是有效的，就需要对一些无效的抗体进行剔除工作，那么抗体多样 性的产生机制用于进化算法中，不但可以剔除多余的抗原识别模式，可以克服算法早熟 收敛问题，从而找到更好的全局最优解。 随着免疫算法在信息化快速发展和人工免疫算法理论研究不断深入，基于人工免疫 原理提出的各种模型和算法会逐渐被广泛运用到科学研究和工程实践当中，现在已经在 很多方面取得了很好的效果。基于免疫原理的人工免疫算法在组合优化的求解当中显示 出了强大的能力。在大多数情况下，免疫算法取得了比现有启发式算法更好的求解结果， 尤其是在全局收敛方面和求解效率方面，显示出人工免疫算法在智能优化领域具有更广 阔的应用前景。 一8 大连理工大学硕士学位论文 1 3 3 利用g p u 来研究免疫算法的意义 从前面对免疫算法的介绍来看，我们可以看出免疫算法无论是对现代科学研究还是 实践工程都具有非常重要的作用，尽管免疫算法比传统的启发式算法有很多的优点比 如：全局收敛性好，尽管求解速率也比智能领域其它算法快，但是传统的解决免疫算法 的方法还是不能达到实时性的要求，在求解t s p 规模达到5 1 个城市的时候，在c p u 中 运算所需要的时间已经是不能接受的了，况且多数情况下都是对大于5 1 个城市的问题 进行求解。不能进行快速的对问题进行求解是免疫算法在很多时候很多地方使用受到限 制的原因，也致使一些领域的发展受到阻碍。有的人也许会想到用并行计算机来解决， 但是用并行机来解决这样的问题开销太大，有些得不偿失，针对这个问题本文所提出的 基于g p u 加速的免疫算法仅需要一个好显卡，这样第一是开销非常小、第二解决了传 统的免疫算法求解问题不能达到实时性的缺陷。 1 4 本文免疫算法模型 本文在了解了免疫算法的研究背景，免疫算法产生的过程以及研究现状之后，同时 结合免疫算法的研究趋势以及本文的研究目标( 准确率高并且能够时实的计算结果) 展 开工作，提出了基于人工免疫系统模型和g p u 加速的免疫算法仿真模型。基本思想是 把非常复杂的生物体和人体的免疫系统提炼转化成能够用数学模型来描述并且能够用 计算机来实现的模型作为仿真模型，在此基础上充分利用g p u 的并行特性来仿真人工 免疫系统。 基丁g p u 加速的细粒度模型并行免疫算法研究 2 理论知识基础 2 1 g p u 的通用计算 最早期的电脑上用的显卡是不带有g p u 的，随着人们生活水平和欣赏水平的提高， 对图形图像处理的要求也越来越高。而通用的c p u 处理速度已经慢慢地跟不上图形处 理的要求，这样就使得在显卡上慢慢地引进了c p u 中的处理功能。原有c p u 上的任务 提取出给g p u ，c p u 能空闲下来处理别的事务，二者的分工协作不仅使得现代的图形 影像播放顺畅而清晰而且使得处理图形数据的速度得到了极大的提高。最早可编程的 g p u 是在2 0 0 2 年，到了2 0 0 4 年n v i d 从发布了划时代的产品g e f o r c e6 8 0 0u l t r a 。 近年来，g p u 正在以大大超过摩尔定律的速度高速发展，极大的提高了计算机图形 处理的速度和质量，不但促进了图像处理、虚拟现实、计算机仿真等相关应用领域的快 速发展，同时也为人们利用g p u 进行图形处理以外的通用计算提供了良好的运行平台。 下图2 1 为g p u 与c p u 浮点运算能力的比较。 獭 t l l l 婚* so f f l i o 矾n g - p o i n f o p 蔷r 曹l o k s ，s 暑c 0 0 5 0 盘 薹 t 拍寓y艄囊p 纯t 黼t3 o 罅 图2 1g p u 与c p u 的浮点计算速度 f i g 2 1f l o p so f g p u a n dc p u 我们可以看出，目前g p u 的浮点运算能力已经达到了接近3 7 0g f l o p s ，而c p u 却只有3 2g f l o p s ，二者对比差别很大，另外，g p u 有更大的内存带宽，目前已经达 到了8 6 4 g b s ，相当于c p u 的1 0 倍。如果能够充分利用这种计算能力和存取能力，那 么g p u 将能够更好地体现其价值。 j 下是由于g p u 具有高效浮点运算能力，越来越多的研究人员和商业组织丌始利用 g p u 完成一些非图形绘制方面的计算，并开创了一个新的研究领域：基于g p u 的通用 大连理t 大学硕士学位论文 计算( g p g p u ，g e n e r a l p u r p o s ec o m p u t a t i o no ng p u ) ，其主要研究内容是如何利用g p u 在图形处理之外的其他领域进行更为广泛的科学计算。目前已成功应用于运动规划、代 数运算、优化计算、偏微分方程、数值求解、流体模拟、数据库应用、频谱分析等非图 形应用领域，甚至包括智能信息处理系统和数据挖掘工具等商业化应用。同时，也产生 了一些针对g p u 开发的通用计算工具包，能够基于g p u 平台对f f t 、b l a s 、排序及 线性方程组求解等科学计算进行优化实现。 基于g p u 的通用计算已成为近几年人们关注的一个研究热点。将g p u 用于通用计 算的主要目的是为了加速计算，加速的动力来自g p u 在高性能计算方面所具有的优势： ( 1 ) 高效的并行性。这一功能主要是通过g p u 多条绘制流水线的并行计算来体现 的。在目前主流的g p u 中，配置多达1 6 个片段处理流水线，6 个顶点处理流水线。多 条流水线可以在单一控制部件的集中控制下运行，也可以独立运行。g p u 的顶点处理流 水线使用m i m d 方式控制，片段处理流水线使用s i m d 结构。相对于并行机而言，g p u 提供的并行性在十分廉价的基础上，为很多适合于在g p u 上进行处理的应用提供了一 个很好的并行方案。 ( 2 ) 高密集的运算。g p u