（计算机软件与理论专业论文）免疫智能在优化中研究及其在数字图像中应用.pdf

摘要 摘要 生物免疫系统是一种复杂的自适应系统，该系统能有效地使用多种机制防御外部病原体 入侵。具体表现为免疫记忆、抗体的自我识别能力和免疫多样性的优点。同时生物免疫系 统在运行中表现出众多智能特性，如对各种抗原的识别和应答过程实际就是一个进化学习 的过程。因此，结合这些特点提出的人工免疫算法，保留了生物免疫系统的若干特点，如 多样性好、鲁棒性强、隐含并行性等。通过对生物免疫系统的系统学习，同时随着计算机 免疫学的不断发展，免疫优化的思想在高效的优化技术和智能计算这两方面，有着越来越 广泛的应用，其在模式识别、故障诊断、计算机安全等领域得到广泛的实际应用。然而， 类似于其它新型智能算法，人工免疫算法也存在一些不足，如存在早熟收敛、局部搜索能 力不足等。因此，改进的免疫智能的研究，己成为网络、智能、控制、计算等领域研究的 重点和热点之一。 本文在计算机免疫优化的大背景下，主要做了以下三个方面的工作。 首先，对免疫优化进行理论研究，同时结合免疫优化理论，对优化问题、数字图像进 行理论分析。 然后，对基本的优化算法，免疫算法和遗传算法、粒子群算法的原理、实现及其特 点进行研究。同时结合了六个测试函数，从收敛代数、收敛时间、能否达到最优解这三 个方面进行分析比较；在对基本的算法的分析比较基础上，分析了一种基于克隆的免疫 遗传算法、基于高低位变异的免疫算法、基于粒子群优化的免疫算法。主要分析了加入 的算子，对提高整个算法性能的研究，同时结合了改进前的算法进行了仿真实验比较。 最后，在此基础上，分别提出了两个改进的免疫算法。第一个提出了基于粒子群优化 的自适应免疫算法，分别对比分析了基于克隆的免疫遗传算法、基于高低位变异的免疫算 法、基于粒子群优化的免疫算法这三个算法，从改进和未改进这两个角度分析了算法的原 理、实现及其特点。通过对算法机制的分析、研究及改进后，提出了基于粒子群优化的自 适应免疫算法，将改进后的算法应用于数字图像聚类，通过仿真实验证明改进后的算法， 在收敛代数、能够达到最优解这两方面都得到了提高；在收敛时间上，相对于基于粒子群 优化的免疫算法得到了提高。接下来又提出一个两次寻求全局最优解的免疫算法，该算法 是对图像边缘检测巾阈值的寻优，通过二次寻优找到边缘检测的最优阈值，从而得到一个 满意的图像边缘。 关键词：抗体；抗原；最优化；免疫算法：遗传算法；粒子群算法；聚类；边缘检测 a b s t r a c t a b s t r a c t b i o l o g i c a li m m u l l es y s t e mi sac o m p l i c a t e ds e l f - a d a p t i v es y s t e m , w h i c ho w n st h ea b i l i t yo f p r e v e n t i n go u t s i d ep a t h o g e n si n v a d i n gh u m a n sb o d ya c c o r d i n gt ol o t so fm e c h a n i s m i to w n st h e a b i l i t i e sl i k ei m m u n em e m o r y , a n t i b o d y ss e l f - r e c o g n i z i n g a b i l i t ya n di m m l m ed i v e r s i t y m e a n w h i l eb i o l o g i c a li m m u n es y s t e ms h o w sl o t so fi n t e l l i g e n tc h a r a c t e r i s t i c s ，l i k er e c o g n i z i n g a n dr e p l y i n gd i f f e r e n ta n t i g e n c o m b i n gw i t ht h e s ec h a r a c t e r i s t i c s ，i m m u n ea l g o r i t h mh a st h e a b i l i t i e so fe x c e l l e n td i v e r s i t y , r o b u s t n e s sa n di n v i s i b l ep a r a l l e l i s m w i t ht h es t u d yo fb i o l o g i c a l i m m u n es y s t e ma n dd e v e l o p m e n to f c o m p u t e ri m m u n o l o g y , i l n m u n eo p t i m i z a t i o ni sp l a y i n gm o l e a n dm o l ei m p o r t a n tr o l ei nt h ea r e a so fe f f i c i e n to p t i m i z a t i o na n di n t e l l i g e n tc o m p u t i n g i th a s b e e na p p l i e di nm a n ya r e a s ，l i k ep a r e mr e o r g a n i z a t i o n , f a u l td i a g n o s i sa n dc o m p u t e rs a f e t y h o w e v e r , c o m p a r i n gw i t ho t h e ri n t e l l i g e n ta l g o r i t h m s ，i m m u n ea l g o r i t h ma l s oo w l i ss o m e d i s a d v a n t a g e ，l i k ep r e m a t u r ec o n v e r g e n c ea n dp o o ra b i l i t yi nl o c a lo p t i m i z a t i o n t h e r e f o r e ，t h e i m p r o v e dr e s e a r c ho fi n l m u n ei n t e l l i g e n c eh a sb e c o m et h em a i na n dt h em o s tw e l c o m ea r e ai n n e t w o r k , i n t e l l i g e n c e ，c o n t r o la n dc o m p u t e r i nt h i st h e s i s ，im a i n l yr e s e a r c hi nt h e o r yo fi m m u n eo p t i m i z a t i o nu n d e rt h eb a c k g r o u n do f c o m p u t e ri m m u n o l o g y , a n dt h ef o l l o w i n gt h r e ea s p e c t sa r em yr e s e a r c h i n gc o n t e n t f i r s t l y , ia n a l y z ea n dr e s e a r c ht h em e c h a n i s mo fa l g o r i t h m , a n dc o m b i n ei tw i t ht h et h e o r y o fo p t i m i z a t i o ni s s u e sa n dd i g i t a li m a g e s s e c o n d l y , ir e s e a r c ht h et h e o r y , c o d ea n dc h a r a c t e r i s t i c so fb a s i ca l g o r i t h m so fi m m u n e a l g o r i t h m , g e n e t i ca l g o r i t h ma n dp a r t i c l es w a r mo p t i m i z a t i o n c o m b i n gw i t ht h es i x t e s t i n gf u n c t i o n s ，ia n a l y z et h r e ea s p e c t si nc o n v e r g e n c et i m e ，c o n v e r g e n c et i m e sa n da b i l i t y o fr e a c h i n gt h eo p t i m a lv a l u e o nt h i sb a s i s ，ia n a l y z ei m m u n ea l g o r i t h mb a s e do nc l o n e ， i l l l m u n ea l g o r i t h mb a s e do nh i 曲a n dl o wp o s i t i o na n di m m u n ea l g o r i t h mb a s e do n p a r t i c l es w a r mo p t i m i z a t i o n t h em a i na n a l y s i so ft h r e ei m p r o v e da l g o r i t h m si so nt h e a r i t h m e t i co p e r a t o r st h a ts h o ws i g n i f i c a n tr o l e si nt h ei m p r o v e da l g o r i t h m s a l s oic o m p a r e t h et h r e ea l g o r i t h m sw i t hb a s i sa l g o r i t h m sa c c o r d i n gt os i m u l a t i o ne x p e r i m e n t s f i n a l l y , o nt h ea n a l y s i so ft h e s ea l g o r i t h m s ，ip r o p o s et w oa l g o r i t h m s t h ef i r s te n h a n c e d a l g o r i t h mn a m e da d a p t i v ei m m u n ea l g o r i t h mb a s e d o i lp a r t i c l es w a r mo p t i m i z a t i o n ic o m p a r e i tw i t ht h et h r e ea l g o r i t h m st h a ta r ei m m u n ea l g o r i t h mb a s e do nc l o n e ，i m m u n ea l g o r i t h m b a s e do nh i 曲a n dl o wp o s i t i o na n di m m u n ea l g o r i t h mb a s e do np a r t i c l es w a r mo p t i m i z a t i o n a f t e rt h ea n a l y s i so fa l g o r i t h mm e c h a n i s m , ia p p l yi ti n t ot h ei m a g ec l u s t e r i n g n es e c o n d i m p r o v e di m m u n ea l g o r i t h mip r o p o s ei si nt h ew a yo fs e e k i n gt h eg l o b a lo p t i m i z a t i o n a f t e rt w o t i m e so fs e e k i n gg l o b a lo p t i m a lt h r e s h o l d , ic a nu s et h i st h r e s h o l dt og e tas a t i s f i e de d g ei m a g e k e y w o r d s ：a n t i b o d y ；a n t i g e n ；o p t i m i z a t i o n ；i m m u n ea l g o r i t h m ；g e n e t i ca l g o r i t h m ；p a r t i c l e s w a r mo p t i m i z a t i o na l g o r i t h m ；c l u s t e r i n g ，e d g ed e t e c t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意 签名： 坌釜玉鱼 日 期： z 妒& jp 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采周影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致 保密的学位论文在解密后也遵守此规定 签名： 销瓷 导师签名： l 羔童j 造 日 期： 坦篁：墨：f ! 第一章绪论 第一章绪论 1 1 研究背景 科学技术发展的今天，计算机科学与技术已经占有了不可动摇的地位。与此同时计算 机科学技术从未停止它的脚步，因此，我们研究也要不断的继续。计算机免疫学就是在计 算机科学和生物免疫学的基础上，发展起来的一门新兴计算机科学技术。计算机免疫学发 展到现在，其在高效的优化技术和智能计算方面，已经拥有很大的前景。 传统的优化算法由于本身存在一些局限性和不足，已经难以满足复杂问题的优化求解 要求的缺点。因此，从2 0 世纪8 0 年代以来，一些新颖的优化算法先后出现，如人工神 经网络、混沌、遗传算法、进化规划、模拟退火、禁忌搜索、群智能、e d a 算法以及混合优 化策略等，同时免疫算法也作为其中的一分子。免疫优化思想主要是在了解应用需求，在 实现问题建模的基础上，采用其设计优化器，寻求问题的最佳解决方案。免疫算法具备许 多特有的优点，如全局优化、鲁棒性好、易于并行处理、智能度高等。其已经得到广泛的 应用，如在优化求解雎1 、杀毒、故障诊断、鲁棒控制、智能网络、防止黑客人侵口1 、容错、 匹配、分类与决策等领域。与此同时其必将成为网络、智能、控制、计算等领域研究的重 点和热点之一h 3 。 因此，免疫算法作为计算机免疫学的一小分枝，其在优化算法中也越来越受众多研究 人员关注。 1 2 最优化问题 优化问题是人们在工程技术、科学研究和经济管理的诸多领域中经常碰到的问题。例 如：结构设计要在满足强度要求等条件下使所用材料的总重量最轻；资源分配要使各用户 利用有限资源产生的总效益最大。在工程实际中，很多问题都可以转化为函数优化问题。 因为从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的 条件下，使系统的目标函数达到极值，即最大值或最小值哺1 。 其数学模型可以看成这样的问题：设它有价输入，其解是价输入的某些子集。这些 子集要满足一定的约束条件见式1 2 。满足约束条件的子集称为该问题的可行解。可行解可 能有很多个。为了衡量可行解的优劣，事先给出了定的标准。这些标准一般以函数形式 给出，称这些函数为日标函数见式1 1 。那些使目标函数取极值( 极大或极小) 的可行解，称 为最优解。 n l i 矿“，x 2 ，毛) 或m a x f ( x , ，吻，矗) ( 1 】) g ， j ，工2 ，x 。) t 或t ，f = j ，2 ，m ( 1 2 ) 其中：z ，( j ，以) 为输入变量，厂，g 是日标函数和约束函数，r 是常量。 解决实际生活中的优化问题的手段大致有以下几种：一是靠经验主观判断；二是做实 验方案，比优劣定决策；三是建立数学模型，求解最优策略。随着数学方法和计算机技术 的进步，用建模和数值模拟解决优化问题，越米越显示出它的优越性。冈此，近年来发展 起米的优化算法，如人t 神经网络、混沌、遗传算法、进化规划、模拟退火、禁 江南人学硕f i ? 学位论文 忌搜索、群智能、e d a 算法以及混合优化策略等，越来越得到应用。 1 3 国内外数字图像处理研究的现状及发展方向 数字图像处理的研究内容概括地说主要有：图像分割、图像压缩、图像增强和复原、 图像识别。应用于图像处理领域中的常用算法有很多，接下来作个分类概叙瞄1 。 1 图像分割是数字图像处理中的关键技术之一h 1 。图像分割是将图像中有意义的特征 部分提取出来，其有意义的特征有图像中的边缘、区域等，这是进一步进行图像识别、分 析和理解的基础。虽然月前已研究出不少边缘提取、区域分割的方法，如灰度阈值法分割。、 聚类、边缘检测法1 和区域生长呻1 等。这些方法的前提是目标与背景相比有明显的灰度变 化，但是只适用于比较简单的图像，而对十复杂的c t 图像、遥感图像、声纳图像等却无能 为力。因此，对图像分割的研究还在不断深入之中，是目前图像处理中研究的热点之一。 2 图像压缩技术可减少描述图像的数据量( 即比特数) ，以便节省图像传输、处理时 间和减少所占用的存储器容量。压缩可以在不失真的前提下获得，也可以在允许的失真条 件下进行。编码是压缩技术中最重要的方法，它在图像处理技术中是发展最早且比较成熟 的技术。经典压缩算法有脚缩算法、t t u f f m a r 码、脯码。 3 图像增强和复原的目的是为了提高图像的质量，如去除噪声，提高图像的清晰度等。 图像增强不考虑图像降质的原因，突出图像中所感兴趣的部分。如强化图像高频分量，可 使图像中物体轮廓清晰，细节明显；如强化低频分量可减少图像中噪声影响。主要方法有 直方图增强、伪彩色增强法和灰度窗口等技术。图像复原要求对图像降质的原因有一定的 了解，一般讲应根据降质过程建立降质模型，再采用某利一滤波方法，恢复或重建原来的图 像，主要有均值滤波、中值滤波、维纳滤波等算法。 4 图像识别是图像处理领域中另一个很重要的内容，在很多领域中得到了应用，如人 脸和指纹鉴别、字符识别、医学诊断等。简单地说，图像识别是图像中的物体的模式分类， 图像经过某些预处理( 增强、复原、压缩) 后，进行图像分割和特征提取，从而进行判决 分类。传统方法主要是统计模式识别、光学模式识别、分形方法识别、信息嫡识别方法。 但这些传统方法自适应能力很差，而且是在没有噪声干扰的情况下进行，近年来新发展起 来的模糊模式识别和人工神经网络模式分类在图像识别中也越来越受到重视。 1 4 本课题的任务 本文主要是从免疫优化的思想出发，在免疫算法的基础上，对其中的算法机制进行分 析研究。同时分析其它的优化算法，遗传算法和粒子群算法，借鉴其中的优越点，结合免 疫优化的思想，进行算法的改进。在理论结合实际这一块，将改进的算法，应用于数字图 像的聚类和边缘检测的分析研究。 本文的研究内容主要如下： 1 在计算机免疫学的大背景下，对免疫优化进行理论研究。同时对优化问题、数字图 像进行理论分析。 2 对免疫算法和遗传算法、粒子群算法的原理、实现及其特点进行研究。进行了六个 测试函数分析比较，丰要在收敛代数、收敛时问、能否达到最优解这三个方面进行分析比 较。在对艇本的算法的分析比较j 去础上，分析了罐于克隆的免疫遗传算法、皋十高低位变 2 第一章绪论 异的免疫算法、基于粒子群优化的免疫算法，主要分析了加入的算子，对提高整个算法性 能的研究。 3 在对算法的分析基础上，提出两个改进的算法应用到数字图像中。其中，基于粒子 群优化的自适应免疫算法的模糊聚类，主要在免疫算法的基础上，加入了高低位算子和粒 子群算子进行了改进。同时将其它三个算法：基于克隆的免疫遗传算法、基于高低位变异 的免疫算法、基于粒子群优化的免疫算法，进行仿真实验的分析比较。在基于改进的免疫 算法的边缘检测阈值自动选取中，提出了二次搜索的机制，进行免疫算法在数字图像的边 缘检测中阈值的寻优。 江南火学硕i j 学位论文 第二章计算机免疫学 2 1 生物免疫系统机理 免疫学认为：人体内存在一个负责免疫功能的完整解剖系统，即免疫系统，与神经系 统和内分泌系统等一样，该系统有着自身的运行机制，并可与其它系统相互结合、相互制 约，共同维持机体在生命过程中总的生理平衡。主要表现在，免疫防御、免疫自稳、免疫 监视。 免疫系统是抗击病源入侵的首要防御系统，包括许多补体种类的免疫细胞及制造这些 免疫细胞的免疫器官，为数最多的免疫细胞是淋巴细胞。主要包括曰细胞和丁细胞，能被， 细胞及曰细胞识别并刺激7 及曰细胞进行特异性应答的病原体，称为抗原。在骨髓中的曰 细胞和在胸腺中的，细胞从不活跃、未成熟经自体耐受发展为成成熟的免疫细胞，一旦人 体受到攻击时，迅速做出免疫应答。巨噬细胞等特异提呈细胞立即获取消化病原体，把它 们分解在细胞表面展示出来，形成, 慨- c 分子。删分子激活成成熟，细胞，将病原体抗原提 呈给丁细胞识别。丁细胞识别特异抗原后，一方面丁细胞复制并激活杀伤丁细胞，杀伤丁细 胞杀死任何被特异抗原感染的细胞；另一方面通过辅助丁细胞激活口细胞。激活后的口细 胞识别特异抗原，并克隆扩增分化为浆细胞形成抗体。抗体与抗原结合，通过两种方式杀 死抗原。口细胞、，细胞在从未成熟到成熟期问，将经历自体耐受，在识别杀死抗原后将形 成免疫记忆，产生免疫反馈。 免疫机制主要分三个阶段：自体耐受、免疫应答、免疫反馈。 1 免疫耐受是指免疫活性细胞接触抗原性物质时所表现的一种特异性的无应答状态。 2 免疫应答是指抗原进入机体后，免疫细胞对抗原分子的识别、活化、分化和效应过 程。这个过程是免疫系统各部分生理功能的综合体现，包括了抗原提呈、淋巴细胞活化、 特异识别、免疫分子形成、免疫效应，以及形成免疫记忆等一系列的过程。 3 免疫反馈是指当抗体产生后，抗体与相应抗原结合形成的免疫复合物可结合到占 细胞的表面上，向细胞内传入抑制信号，影响曰细胞的活化和抗体的产生。 免疫系统基本特征：生物免疫系统得最大特点是免疫记忆、抗体的自我识别能力和免疫 多样性。免疫系统具有以下的特征：耐受性、学习和认知、分布性、鲁棒性和适应性、免 疫反馈和自组织性等。 1 免疫耐受性是指免疫活性细胞接触抗原性物质时所表现的一种特异性的无应答状 态。它是免疫应答的一利，重要类型。 2 免疫学习和认知是指系统能够学习抗原的结构，将来同一抗原再次出现时，反应会 更快更强烈。学习和认知的结果是免疫细胞的个体亲和力提高，群体规模扩大，并且最优 个体以免疫记忆的形式得到保存。 3 免疫分布性是指应答的抗原是散布在整个免疫体内，效应细胞监测抗原的过程。 4 免疫鲁棒形是指免疫系统具有多样性、分布性、动态性和容错性的结果。免疫适应 性是指学习识别和戍答新的抗原，保存对这些抗原的记忆。 5 免疫反馈是对系统i i ，存在的内部的外部的不确定性，促进免疫系统对抗原的快速应 答，并同时保持免疫系统的相对稳定性。 4 第二章计算机免疫学 6 免疫自组织是指免疫系统不需要外界的管理和维护，通过采用更替被损坏细胞的办 法来修补自己，消除抗原。 2 2 计算机免疫学基本原理 基于生物免疫系统的这些特点，激发人们探索其运行机理，并构造人工系统来模拟生 物免疫系统得优良特性。本节主要对形态空间模型、免疫细胞模型、计算机免疫系统进行 介绍。 形态空间模型：为了定量地描述免疫系统，p e r e l s o n 和o s t e r 提出的所有的免疫事件都 在形态空间s 中发生，这是个多维空间，每个轴表示一个物理化学的测量方法，用该方法 可以描述一个分析形态。分子结构表示一个点s s ，因而在三维空间中，可将一个点定为 决定抗体和抗原相互作用的特征集。 形态空问是指抗体和与之结合的分子之间的结合程度，以及描述抗原可能性区域的高 维空间。形态空间本质上是免疫系统所确认的属性的抽象，通过它能建立和评价免疫系统 得模型。在形态空间的每个抗体有一个特定位置，抗原的细小变异都会改变它在形态空间 中的位置，所以免疫细胞要发挥作用，必须在形态空间覆盖足够大的区域，使大多数的变 异无法规避。 免疫细胞主要在骨髓和胸腺中形成，从产生到成熟并进入免疫循环，需要经历一系列 复杂的变化。基于生物免疫系统构建的人工免疫细胞模型，主要包括自体耐受、克隆、变 异、记忆及死亡的过程。 免疫细胞在骨髓中产生，其需要经历一个耐受过程，在耐受期内与自体发生匹配，就 会死亡并被新的免疫细胞代替。经过耐受期后，成熟的免疫细胞被排出骨髓，进入免疫循 环。若遇抗原产生匹配，且累计足够的亲和力，则被激活转变为记忆细胞，并进行克隆， 产生大量的免疫细胞，抵御抗原的入侵。若成熟免疫细胞在生命周期内未能累计足够的亲 和力，则走向死亡，并被新的成熟免疫细胞取代。这样的机制保准了抗原空问的持续搜索 能力，保留好的免疫细胞。记忆细胞具有更长的生命周期，记忆细胞在再次匹配抗原后就 会被再次激活并克隆自己。克隆生成的新细胞加入成熟细胞集。一部分符合条件的免疫细 胞还能进行变异，使系统具有了学习进化的能力。 免疫细胞的产生过程见图2 - 1 ： 江南人学硕士学位论文 图2 - 1 免疫细胞的生命周期 f i g 2 1l i f e c y c l eo f i m m u n ec e l l 2 3 基于群体的免疫算法 本节阐述了免疫算法的基本架构，同时基于免疫算法，分别介绍了否定选择算法、肯 定选择算法、克隆选择算法。 在用免疫算法解决具体问题时，首先需要将问题的有关描述与免疫系统的有关概念及 免疫原理对应起来，定义免疫元素的数学表达式，然后设计相应的免疫算法，其中用到的 公式如下。 在生物体内要保存抗体的多样性，这样的日的是为了抵抗不同的抗原。在整个免疫系 统中，抗原和抗体，抗体和抗体保持一个微妙的平衡。信息熵被引入作为判断抗体的多样 性和免疫优化中等位基因改变的概率。 设一个免疫系统是由个抗体组成，每个抗体由m 个等位基因组成。在整个 r 个抗 体中第j 位基因的信息熵如下： n 1 勺2 舌乃1 。g 石 ( 2 1 ) 其中：乃是在第位基冈位置的总数日，岛是第_ ，位取第f 个等位基因的概率。 随机两个抗体的亲和体可以定义为如下： 4 2 南 ( 2 2 ) 其中：e ( 2 ) 是两个抗体的平均信息熵，t 是抗体。 ( 2 ) 2 击萎幺 ( 2 3 ) 6 第二章计算机免疫学 抗原和抗体的亲和力被定义为抗体的适应度： 【彳w ) = g f ( z )r i ) d 、 其中：蜀【叫是第f 个抗体的适应度方程，y 是抗原。 一般地，免疫算法由以下几个步骤： 1 定义抗原：将需要解决的问题抽象成符合免疫系统处理的抗原形势，抗原识别则对 应为问题的求解。 2 产生初始抗体：将抗体的群体定义为问题的解，抗体与抗原的之间的亲和力对应问 题的评估，其亲和力越高，说明解越好。 3 计算亲和力：计算抗体和抗原的亲和力大小。 4 克隆选择：与抗原有较大亲和力的抗体得到优先繁殖，抑制浓度过高的抗体，淘汰 低亲和力。为获得多样性，抗体在克隆时经历变异。 5 评估新的抗体种群：若不能满足停止条件，则转向第3 步，重新开始；反之，则当 前的抗体种群为问题的最优解。 其算法流程图见图2 - - 2 ： 图2 - 2 免疫算法的基本流程 f i g 2 2 b a s i cf l o wo fl m m u n ea l g o r i t h m 免疫系统扮演的主要角色是保护组织免收疾病的威胁，并消除细胞残骸和发生功能异 样的细胞。为了达到这样的门的，首先要解决的事情就是对自身的细胞和那些不是自身的 冗素进行区分。在人_ 丁免疫系统巾，通过否定选择算法去除那些对自体产生应答的免疫细 江南火学硕士学位论文 胞，实现自体的耐受。其算法是对免疫细胞的成熟过程模拟，经历耐受的检测器模拟成熟 的免疫细胞。主要包括了两个阶段：耐受和检测。耐受是负责成熟检测器的产生；检测是 检测器检测受保护的系统以发现变化。 其算法流程图见图2 - 3 ： 图2 - 3 否定选择算法 f i g 2 3n e g a t i v es e l e c t i o na l g o r i t h m 那些能识别自体分子的丁细胞能被激活，是依赖于丁细胞自身的肯定选择。这个过程 产生自体分析的限制，即一种，细胞属性，只有与自体分子有联系的，细胞才能识别抗原。 肯定选择算法与否定选择算法非常相似，作用却刚好相反。在否定算法中，与自体匹 配的免疫细胞必须清除，而在肯定选择算法中却被保留。 其算法流程图见图2 4 ： 图2 - 4 肯定选择算法 f i g 2 4 p o s i t i v es e l e c t i o na l g o r i t h m 克隆选择原理被用来解释免疫系统是怎么与抗原作战的。当外部细菌入侵机体后，占 细胞开始大量克隆并消灭入侵者，那些能识别抗原的细胞根据识别的程度通过无性繁殖达 到增生的j 的：与抗原具有越高的亲和力，该细胞就能产生更多的后代。在细胞分裂的过 程中，个体细胞还经历了一个变异的过程，其结果使它们与抗原具有更高的亲和力：父代 细胞与抗原具有越高的亲和力，它们就经历越小的变异。 其算法流程图见2 - 5 ： 8 第二章计算机免疫学 图2 - 5 克隆选择算法 f i g 2 5 c l o n es e l e c t i o na l g o r i t h m 通过对基本免疫算法和基于免疫的否定选择算法、肯定选择算法、克隆选择算法介绍 后，我们将其与遗传算法、粒子群算法进行分析比较。 9 江南火学硕1 ：学位论文 第三章免疫算法和最优化问题 3 1 最优化算法 所谓优化算法，是一种搜索过程或规则，它是基于某种思想和机制，通过一定的途径 或规则来得到满足用户要求的问题的解。从优化算法的优化机制与行为角度，目前工程中 常用的优化算法可以分为：经典算法、构造型算法、改进型算法、基于系统动态演化的算 法和混合型算法等n 2 | 。 1 经典算法：包括线性规划、动态规划、整数规划和分枝定界等运筹学中的传统算法， 其算法计算量一般很大，只适于求解小规模问题，在工程中往往不实用。 2 构造型算法，用构造的方法快速建立问题的解，通常算法的优化质量差，难以满足 工程需要。譬如，调度问题中的典型构造型方法有：j o h n s o n 法、p a l m e r 法、g u p t a 法、c d s 法、d a u n e n b r i n g 的快速接近法、 7 ：j 强，法等。 3 改进型算法，或称邻域搜索算法。从任一解出发，通过对其邻域的不断搜索和当前 解的替换来实现优化。根据搜索行为，它又可分为局部搜索法和指导性搜索法。 局部搜索法，以局部优化策略在当前解的邻域中贪婪搜索，如只接受优于当前解的 状态作为下一当前解的爬山法；接受当前解邻域中的最好解作为下一当前解的最陡 下降法等。 指导性搜索方法，利用一些指导规则来指导整个解空间中优良解的搜索，如模拟退 火、遗传算法、粒子群算法、免疫算法、进化规划、进化策略、遗传规划、禁忌搜 索等。 4 基于系统动态演化的方法。将优化过程转化为系统动态的演化过程，基于系统动态 的演化来实现优化，如混沌搜索等。 5 混合型算法。指上述各种算法从结构或操作上相混合而产生的各种算法。 随着学术的不断发展，目前优化算法的研究主要集中于指导性搜索方法和系统动态演 化方法以及各种混合算法，研究热点为以遗传算法为代表的进化计算方法，同时新的优化 算法也不断出现，如人工免疫算法、群智能、e d a 算法、d n a 算法等。 3 2 进化算法 进化算法是基于模拟自然进化思想而发展起来的一类随机搜索技术，是将自然界生物 学原理应用于科学研究的智能信息处理技术。进化算法是以群体为基础，模拟生物遗传进 化过程，通过保留适应度高的个体( 可行解) ，并利用选择、交叉、变异等操作产生新的个 体，如此反复以提高群体的适应度水平，实现群体收敛，寻求问题的最优解。 3 2 1 遗传算法 进化算法的最初经典以遗传算法为代农。在2 0 世纪6 0 年代，美国芝加哥大学教 授1 - 1 h o l l a n d 在研究自适应系统时最先提出遗传算法u 利。2 0 世纪八、九十年代之后，计 算机技术的高速发展大大促进了各利计算智能的研究，遗传算法的相关研究更为普遍，新 的研究成果不断出现。其已经在已经在函数优化引、组合优化、生产调度、自动控制、机 器人学、图像处邢“引、机器学习、数据挖掘_ 力等领域得到应川。然而在些应川研究- i 一却 1 0 第三章免疫算法和最优化问题 发现g a 存在着明显的不足，如早熟与欺骗问题、搜索效率低、不能很好地保持个体的多样 性等。 标准遗传算法流程图如图3 1 所示。 图3 - 1 标准遗传算法流程图 f i g 3 一l f l o wc h a r to fs t a n d a r di m m u n ea i g o d t h m 3 2 2 粒子群算法 是 1 9 9 5 年k e n n e d y 和e b e r h a r t 受到鸟群捕食行为的研究结果启发，提出了粒子群优化算 法引。其算法具有执行速度快、受问题维数变化影响小等优点，迅速得到了人们的重视。 到现在为止，此算法已得到广泛应用，如多元函数的优化问题，包括带约束的优化问题， 优化的人工神经网络，动态问题。同时其算法也存在一些不足，如个体多样性不好，无法 稳定地获得全局最优解等u 引。 标准粒子群算法流程图如图3 2 所示。 图3 - 2 标准粒子群算法流程图 f i g 3 2 f l o wc h a r to fs t a n d a r dp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m 江南大学顾l 学位论文 3 2 3 免疫算法与其它算法的仿真实验结果与分析 本小节用实例说明人工免疫算法的优化过程，按照函数凸性和非凸性，单峰性和多峰 性，二次函数和高次函数，低维函数和多维函数，连续和非连续的分类标准，选择了六种 测试函数对标准遗传算法、粒子群算法和免疫算法的性能进行了仿真实验对比。 s p h e r e 函数刷硝限蓦彳 ( 3 1 ) 算法的参数设置如下：种群规模为5 0 ，变异率为0 0 5 ，交叉率为0 9 ，染色体编码是 2 2 位长的二进制串；粒子数为2 0 ，维数为2 2 。两个加速常数为2 ，惯性冈子随进化代数从 0 9 线性减小到0 5 。同时该函数是二次多维凸函数，它在t 2 d 有全局最大值2 5 n , 此函数 中，z = 3 。每个算法都进行1 0 0 次实验。其实验结果见表3 1 。 表3 1 s p h e r e 函数优化结果比较 t a b 3 1 c o m p a r i n go p t i m i z a t i o no fs p h e r ef u n c t i o n 2 g e n e r a l i s e d r o s e n b r o c k 函数：舷= l o o ( x y 2 夕2 + “矽2 ( 3 2 ) 算法的参数设置如下：种群规模为1 0 0 ，变异率为0 0 5 ，交叉率为0 9 ，染色体编码是 2 2 位长的二进制串；粒子数为2 0 ，维数为2 2 。两个加速常数为2 ，惯性因子随进化代数从 0 9 线性减小到0 5 。函数自变量取值范围：一2 x 2 , - 2 y 2 ，函数在x = j ，j ，= j 时有 全局最小值0 。每个算法都进行1 0 0 次实验。其实验结果见表3 2 。 表3 2g e n e r a l i s e dr o s e n b r o c k 函数优化结果比较 t a b 3 2 c o m p a r i n go p t i m i z a t i o no fg e n e r a l i s e dr o s e n b r o c kf u n c t i o n 3 w a v e 函数：倒= 1 0 + 仅o 1 6 ) 2 十o ，1 ( 3 3 ) 算法的参数设置如下：种群规模为2 0 ，变异率为0 0 5 ，交叉率为0 9 ，染色体编码是 2 2 位长的二进制串；粒子数为2 0 ，维数为2 2 。两个加速常数为2 ，惯性因子随进化代数从 0 9 线性减小到0 5 。函数自变量取值范围：0 0 是根据待解决的 问题和经验来决定。从上式可以看出，抗体适应度越大，复制选择概率越大，抗体浓度越 大，选择的概率越小。这样不仅保留了优秀的个体，而且减少了相似抗体的选择，确保了 个体的多样性。 抽取疫苗按照如下的方法：设一个抗体有p 个符号可供选择：毛，k 2 ，在种群中第 i 等位基因上为勺的概率p 驴： 1 芒 p u2 il a j 户1 ( 3 8 ) i l ，g ( f ) = 七， 其中： 【o , o t h e r w i s p ，g ( f ) 为种群中第f 等位基因上的符号，为种群的个体数量。 将该等位基因上最大概率大于某个设定阈值的凡j 作为该等位基因上的疫苗片段，最终抽取 b：j乃，m越(丹)丁i 疫苗为b = ( b l ，6 2 ，也) ， 【o o t h e r w i s e ，r 为阈值。 根据上述得到的疫苗，在抗体变异结束后，按照接种概率对选中的抗体的基因，依次 进行接入，从而得到新的抗体。 基于克隆的免疫遗传算法流程图如图3 3 所示。 算法测试：用基于克隆改进的免疫遗传算法对下面的测试函数进行仿真实验，参数设 置如下：种群规模为3 0 ，变异率为0 0 5 ，交叉率为0 9 ，染色体编码是2 2 位长的二进制串， 接种概率为0 5 ，阈值为0 5 ，s = 2 ，算法停止条件最优解误差小于1 0 或迭代次数小于2 0 0 。 测试函数如下：函数在点( 1 ，1 ) 、( 1 ，一1 ) 、( - 1 ，1 ) 、( - 1 ，- 1 ) 有全局最大值0 9 7 4 7 3 2 ， 其中一j 五y j 职，2 d ”：，i ；。+ ( x 删2 + z 矿上l 呐2 - o s ( 3 9 ) 在对算法的性能分析中，将其与遗传算法( 和免疫算法( 脚进行比较分析。分别对 算法独立运算1 0 0 次，具体数据可以见表3 7 。从表中，我们看到遗传算法收敛代数比较多， 而免疫算法用了较少的收敛代数，却没有在时问开销上比较大。基于克隆改进的免疫遗传 算法可以综合免疫算法和遗传算法的优缺点，用了相对较少的收敛代数，同时在收敛时问 上大大缩减，可见收敛速度要比其他两个算法快的多。在图3 - - 8 和图3 - - 9 - i ，能够直观的 江南人学硕l 学位论文 看到三个算法的适应值和平均适应值变化，可见基于克隆改进的免疫遗传算法具有较快的 收敛速度。同时，在图3 - 4 、3 5 、3 6 、3 7 中可以直观的看出来，基于克隆改进的免疫遗 传算法融合了免疫算法的特点，很好的克服了遗传算法局部收敛的缺点。 图3 - 3 基于克隆的免疫遗传算法 f i g 3 3 i n l m u l l eg e n e t i ca l g o r i t h mb a s e do nc l o n e 表3 7 基于克隆的免疫遗传算法) 优化结果比较 t a b 3 7 c o m p a r i n go p t i m i z a t i o no fi m m u n eg e n e t i ca l g o r i t h mb a s e d0 1 3c l o n e 1 6 塑二童量丝墨堡苎墨垡些型些 圈3 4g a 的柳始化田 f i g3 4 i n i t i a l g a 图36 1 1 g 的柳始化囤 f i g3 6 i n i t i a l g ；。萋， 、一百f f 囤3 - 5g a 达到置饨值的图 f i g 3 + 50 m v a l u e o f g a 吣。 弋姆夕 、 。0 看 圈37 珊达到最扰值的图 f i g3 7o d 自珊】v d 吐o f l i g 图3 8 三种算法适应值比较 f i s3 8c m m 啪t o o f f i m e v a l u e t h r e e a l g o r i t h m - 、 1赫一 i 江南火学硕1 ：学位论文 图3 - 9 三种算法平均适应值比较 f i g 3 9c o m p a r i s o no f a v e r a g ef i m e s sv a l u eo f t h r e ea l g o r i t h m s 3 3 2 基于高低位变异的免疫算法 在对本节的算法介绍前，需要对免疫算法中的变异率进行一定的分析。变异是免疫算 法中重要的遗传操作。较大的变异率可以使免疫算法具有较