（控制科学与工程专业论文）克隆选择算法及其在高维全局函数优化中的应用.pdf

己 9 l 譬 m a s t e rd e g r e ec a n d i d a t e i 丕i q 坠g 星照g s u p e r v i s o r 里煦 圣逝卫gg 堑 s c h o o lo fi n f o r m a t i o ns c i e n c e e n g i n e e r i n g c e n t r a ls o u t hu n i v e r s i t y c h a n g s h a h u n a n p r c 吣 8 6 2 原创性声明 本人声明 所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果 尽我所知 除了论文中特别加以标注和致谢的 地方外 论文中不包含其他人已经发表或撰写过的研究成果 也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料 与我共 同工作的同志对本研究所作的贡献均己在论文中作了明确的说明 作者签名 主嗵日期 盟年上月 日 学位论文版权使用授权书 本人了解中南大学有关保留 使用学位论文的规定 即 学校有 权保留学位论文并根据国家或湖南省有关部门规定送交学位论文 允 许学位论文被查阅和借阅 学校可以公布学位论文的全部或部分内容 可以采用复印 缩印或其它手段保存学位论文 同时授权中国科学技 术信息研究所将本学位论文收录到 中国学位论文全文数据库 并通 过网络向社会公众提供信息服务 作者签名 师签缝日期 也年上月王日 摘要 生物免疫系统是一种具有学习 记忆 识别 特征提取等能力的 自适应系统 能有效的识别和排除入侵机体的抗原和突变的自身细 胞 人工免疫算法是受生物免疫系统启发而发展起来的新型算法 克 隆选择算法是人工免疫算法的重要分支 它模拟生物免疫系统的克隆 选择机制 处理优化问题 针对高维的旋转 偏移函数的特点 本文提出了一种改进的克隆 选择算法 贪婪免疫记忆克隆选择算法 构造了贪婪免疫记忆机 制 采用多变异策略和多轮竞争选择 增加种群多样性 防止种群陷 入局部极值点 通过对c e c 2 0 0 5 函数的测试验证了算法的有效性 针对免疫算法全局搜索欠缺的问题 本文提出一种新的改进的克 隆选择算法 基于差异进化的克隆选择算法 将差异进化和克隆超 变异相结合 促进抗体之间的信息融合 使得子代抗体继承父代抗体 信息的同时 携带着不同父代抗体信息 丰富了抗体种群的多样性 实验表明算法具有较强的全局搜索能力 针对基于差异进化的克隆选择算法在全局优化过程中多样性不 足的问题 本文提出一种新的改进的克隆选择算法 基于差异进化 的多样性免疫记忆克隆选择算法 构造了多样性免疫记忆机制 将差 异进化作为变异算子 采用三组经验控制参数组 实验证明算法增加 了种群多样性 增强了全局和局部搜索能力 关键词生物免疫系统 克隆选择算法 进化计算 差异进化算法 免疫记忆 a b s t r a c t b i o l o g i c a li m m u n es y s t e mi sa na d a p t i v es y s t e m w h i c hc a nl e a r n m e m o r y i d e n t i f y a n de x t r a c tf e a m r e t h e s y s t e m c a n e f f e c t i v e l y r e c o g n i z ea n de l i m i n a t ei n v a d i n ga n t i g e n s a r t i f i c i a li m m u n ea l g o r i t h m a i s i san o v e lc o m p u t a t i o n a lf r a m e w o r ki n s p i r e db yb i o l o g i c a li m m u n e s y s t e m s c l o n a ls e l e c t i o na l g o r i t h m c s a i so n eo fi m p o r t a n tb r a n c h e s o fa i s a n di ti su s e dt os o l v i n gd i f f i c u l th i g h d i m e n s i o n a lo p t i m i z a t i o n p r o b l e m s c l o n a ls e l e c t i o na n dh y p e r m u t a t i o nm e c h a n i s m sa r ei t sm a i n c h a r a c t e r i s t i c s a c c o r d i n gt ot h ef e a t u r e so fh i g h e r d i m e n s i o n a lr o t a t e da n ds h i f t e d f u n c t i o n s t h i sp a p e rp r e s e n t san o v e lh e u r i s t i ca l g o r i t h m n a m eg r e e d y i m m u n em e m o r yc s a t op r e v e n tt h ee v o l u t i o n a r ys t a g n a t i o no ft h e p o p u l a t i o n t h ei m m u n em e m o r ym e c h a n i s mi se m p l o y e dt os t r e n g t ht h e e x p l o i t a t i o na b i l i t yo fp o p u l a t i o n m e a n w h i l e am u l t i m u t a t i o ns t r a t e g y a n dam u l t i r o u n dc o m p e t i t i o na r ea d o p t e d as e r i a le x p e r i m e n tc a r r i e s o u tt h r o u g ht h et e s t i n gs u i to fc e c 2 0 0 5 a n dt h er e s u l t ss h o wt h e p r e s e n t e da l g o r i t h mi m p r o v e st h es o l u t i o nq u a l i t y t od e a lw i t ht h ei m m u n ea l g o r i t h m i cd e f e c to ng l o b a ls e a r c h i n g w e d e v e l o pan e wa l g o r i t h m c a l l e dd e c s a t h en o v e la l g o r i t h mi n t e g r a t e s d i f f e r e n t i a le v o l u t i o nt oc s ai no r d e rt oi n f o r m a t i o nf u s i o na m o n g a n t i b o d i e s t h eo f f s p r i n gi n d i v i d u a l si n h e r i te v o l u t i o n a r yi n f o r m a t i o no f m u l t i p l ep a r e n t ss ot h a tt h ed i v e r s i t yo ft h ep o p u l a t i o nc o u l db ee n r i c h e d e x p e r i m e n t si n d i c a t et h a tt h en o v e la l g o r i t h mh a sas t r o n ga b i l i t yi n g l o b a lr e s e a r c h i no r d e rt os t r e n g t h e nt h ee x p l o r ea b i l i t yo f e v o l u t i o n a r yp o p u l a t i o n a ni m m u n em e m o r ym e c h a n i s mi su s e di nd e c s a t h en o v e la l g o r i t h m e m p l o y st h ed i v e r s i t yi m m u n em e m o r ym e c h a n i s m r e g a r d i n gd ea sa m u t a t i o no p e r a t o ra n dt r i p l ec o n t r o lp a r a m e t e r sa r em a i nc h a r a c t e r i s t i c so f t h en e wd e c s a e x p e r i m e n t ss h o wt h en e wd e c s ao u t p e r f o r mt h e p r e v i o u sv e r s i o ni nt e r mo fs o l u t i o nq u a l i t y 1 1 k e yw o r d sb i o l o g i c a li m m u n es y s t e m c l o n a ls e l e c t i o na l g o r i t h m e v o l u t i o n a r yc o m p u t a t i o n d i f f e r e n t i a le v o l u t i o n i m m u n em e m o r y i i i 摘要 1 a b s t r a c t i i 第一章绪论 1 1 1 生物免疫系统 1 1 1 1 生物免疫系统功能 l 1 1 2 生物免疫系统的特点 l 1 1 3 克隆选择学说 3 1 2 免疫算法和模型 5 1 2 1 克隆选择算法 5 1 2 2 基于免疫网络学说的免疫网络模型 5 1 2 3 基于免疫特异性的阴性选择算法 6 1 2 4 免疫进化算法 6 1 3 本文研究内容 7 第二章贪婪免疫记忆克隆选择算法 8 2 1 引言 8 2 2 贪婪免疫记忆克隆选择算法 9 2 2 1 克隆增殖操作 9 2 2 2 克隆变异操作 9 2 2 3 克隆选择机制 1 1 2 2 4 贪婪免疫记忆机制 1 2 2 2 5 种群更新 1 3 2 3g i m c s a 算法框架 1 4 2 3 1g i m c s a 算法流程 1 4 2 3 2g i m c s a 算法整体框架 1 4 2 4 实验及其结果分析 1 5 2 4 1g i m c s a 试验 1 5 2 4 2 对比试验 1 9 第三章基于差异进化的克隆选择算法 2 2 3 1 引言 2 2 3 2 基于差异进化的克隆选择算法 2 3 3 2 1 克隆增殖操作 2 3 i v 3 2 2 克隆变异操作 2 3 3 2 3 贪婪选择操作 2 5 3 3 基于差异进化的克隆选择算法流程 2 5 3 4 仿真实验及其结果分析 2 5 第四章基于差异进化的多样性免疫记忆克隆选择算法 3 0 4 1 引言 3 0 4 2 基于差异进化的多样性免疫记忆克隆选择算法d e i m c s a 3 0 4 2 1 克隆增殖操作 3 0 4 2 2 差异进化 3 0 4 2 3 贪婪选择操作 3 2 4 2 4 多样性免疫记忆机制 3 2 4 3d e i m c s a 算法流程与框架 3 3 4 4 实验及其结果分析 3 4 4 4 1 高维单峰函数 3 4 4 4 2 高维多峰函数 3 5 4 4 3 低维多峰函数 3 6 4 4 4 高维单峰 多峰函数试验 3 7 第五章总结与展望 3 8 参考文献 3 9 致谢 4 5 攻读学位期间主要研究成果 4 6 v 硕士学位论文 第一章绪论 第一章绪论弟一早殆t 匕 1 1 生物免疫系统 1 1 1 生物免疫系统功能 生物免疫系统 是一种极度复杂的分布式协调型的自适应系统 免疫系统对 从外部侵入机体的非我物质 以及对自身内部已经发生突变的细胞 如癌细胞 都具有准确高效识别 免疫应答和有效清除的能力 免疫可分为非特异性免疫和特异性免疫两种 非特异性免疫是机体天然的 与生俱来的防御功能 对各种病原体有一定的 防御作用 但没有特殊的针对性防御作用 它是机体防御外来侵袭的第一道防线 主要由皮肤 粘液等组织完成 特异性免疫是免疫系统在适应环境的过程中不断学习积累起来的 针对特定 的致病物质的防御功能 特异性免疫是机体适应环境的体现 由免疫细胞完成 它是免疫学主要研究对象 免疫系统的主要功能包括三个方面 1 免疫防护功能 机体抵御外部侵入的非我物质的功能 2 自身稳定功能 清除机体内受损伤或已死亡的细胞 维持机体自身的生 理平衡的功能 3 免疫监视功能 对机体内部进行监视 发现并清除已发生突变的细胞的 功能 1 1 2 生物免疫系统的特点 生物免疫系统 具有免疫识别 免疫应答和免疫记忆等特点 免疫识别 是指免疫系统能够精准地识别己知抗原和未知抗原 精细地区分 自我 和 非我 抗体细胞通过其表面受体对抗原表位的绑定 来实现对抗原的 识别 具有两个特征 1 针对不同的抗原 免疫系统产生与之相对应的不同的抗体细胞 这称之 为特异性免疫应答 2 对未知的抗原 免疫系统能产生与之特异性相匹配的免疫抗体细胞 免疫应答 是指免疫细胞对抗原分子的识别 活化 分化和产生免疫效应的 全过程 免疫应答表现为两种类型 1 正向免疫应答 即免疫系统对非我物质的排斥行为 2 负向免疫应答 即免疫系统对自我成分的宽容行为 硕士学位论文 第一章绪论 一般情况 我们将免疫应答分为体液免疫应答和细胞免疫应答两部分 免疫记忆 对已经发生初次免疫应答的抗原 免疫系统对该抗原的记忆将持 续非常长的时间 而这些记忆细胞是如何得以维持存在的 是免疫学面临的挑战 免疫记忆可由长寿命记忆细胞理论 紧急记忆理论 残余抗原理论 免疫网络理 论 异种记忆理论等基础理论进行阐述 1 长寿命记忆细胞理论 l 细胞的寿命远短与整个身体的寿命 细胞不断死亡 并不断更新 一些与抗 硕士学位论文 第一章绪论 t h e o r y 出著名的克隆选择学说 1 7 1 c l o n es e l e c t i o nt h e o r y 该学说认为免疫细胞是随机 q 9 q 抗螽一i l 选择 9 碍卜9 分化 图1 1 克隆选择原理 克隆选择学说的基本观点 1 仅由淋巴细胞能够合成抗体 且各具特异性 抗体结构由基因决定 与 抗原无关 2 淋巴细胞在胚胎期间 反复分裂增殖 同时发生无定向的体细胞高变异 从而形成细胞基因的多样性 3 x 9y 9x o 上9土9 纽忆 上曦 士碱 硕士学位论文 第一章绪论 3 淋巴细胞在胚胎期间 具有识别抗原的能力 但不具备产生抗体的能力 因而遇到抗原反被损伤而死亡 仅当淋巴细胞成熟后 才具有产生抗体的能力 4 在胚胎后期 成熟的自身抗原会使得相应的淋巴细胞受损 形成免疫耐 受 5 胚胎期间 人工给与的非自身抗原 能够产生与自身抗原相似的作用 6 成熟的免疫机制 对进入体内的外来抗原 会有选择性地刺激激活相应 的抗体克隆 分化 形成免疫应答 克隆选择学说的核心论点是 携带有各种受体的免疫活性细胞克隆早己存 在 抗原的作用只是选择并激活相应的克隆 1 1 4 免疫网络理论 1 9 7 4 年 j e m e 提出了免疫网络理论 1 8 1 9 它认为任何抗体或者淋巴细胞的 硕士学位论文 第一章绪论 1 2 免疫算法和模型 1 2 1 克隆选择算法 2 0 0 0 年 d ec a s t r o 等人基于免疫系统的克隆选择理论 提出了克隆选择算 法c s a t 2 0 1 c l o n a ls e l e c t i o na l g o r i t h m 其核心为克隆增殖和克隆变异 在克隆 选择算法中 只有能够识别抗原的抗体将被选择出来进行克隆增殖操作 得到的 克隆体经过变异操作 产生更好的亲和度抗体 进入下一代群体 克隆选择算法 已成功地应用到了数据压缩 聚类应用 高维函数优化等问题中 2 0 0 2 年 k i m 等人在h o f i n e y r 的基础上 提出了一种动态克隆选择算法 d y n a m i c s 川 d y n a m i cc l o n a ls e l e c t i o na l g o r i t h m 能够自适应地适应不断变化 的环境 动态地学习 分辨自我模式和预测新的非我模式 d y n a m i c s 已被成功 地应用于解决连续变化环境中异常探测问题和网络入侵检测问题 而d y n a m i c s 算法更多地模拟了免疫系统的外物识别功能 2 0 0 3 年 t i m m i s 等人受生物免疫系统的连续体细胞高频突变 c o n t i g u o u s s o m a t i ch y p e r m u t a t i o n 启发 提出了b c e l l 算法 2 2 2 0 0 4 年 c u t e l l o 等人设计了多种克隆变异算子 提出了免疫算法o p t i a 2 3 1 免疫系统的极其复杂 目前己有的克隆选择算法都只是对克隆选择机理的简 单模拟 仅给出了算法框架 缺乏对克隆选择机制的深入分析研究和有关收敛性 分析等理论研究 1 2 2 基于免疫网络学说的免疫网络模型 典型的免疫网络模型有独特型网络模型 资源受限人工免疫系统r l a i s a i n e t 免疫网络 1 9 8 4 年 j e m e 1 9 等人基于细胞选择学说 开创了独特型网络模型 i d i o t y p e n e t w o r k s 的理论 p e r e l s o n 在j e r n e 研究工作基础上 从抗体的形态空间理论出 发 提出了独特型网络的概率模型 2 4 1 2 0 0 1 年 t i m m i s 等人在c o o k 和h u n t 的研究基础上 提出了免疫网络算法 资源受限人工免疫系统r l a i s t 2 5 r e s o u r c el i m i t e da r t i f i c i a li m m u n e s y s t e m 和给出了人工识别球a r b a r t i f i c i a lr e c o g n i t i o nb a l l 的概念 2 0 0 1 年 d ec a s t r o 等人提出a i n e t 2 6 免疫网络 其模拟了免疫网络对抗原刺 激的刺激过程 a i n e t 已成功应用于数据挖掘 数据压缩 数据分类及模式识别 等应用领域 目前 免疫网络模型普遍存在自适应能力差 参数多 且过分依赖网络节点 的增减来保持网络动态 缺乏对免疫网络非线性信息处理能力的认识等缺陷 因 此 限制了算法的应用范围 硕士学位论文第一章绪论 1 2 3 基于免疫特异性的阴性选择算法 免疫系统中的t 细胞在胸腺中发育 未成熟t 细胞若与自体蛋白质相结合 而被激活的话 则该t 细胞将会被删除 所以成熟的t 细胞具有忍耐自身的性 质 不对自身蛋白质发生反应 只对外来蛋白质产生反应 以此来识别自己与非 己 这就是所谓的阴性选择原理 1 9 9 4 年 f o r r e s t 2 7 等人基于阴性选择原理 提出了阴性选择 n e g a t i v es e l e c t i o n 算法 并应用于异常检测 算法如图1 3 包括两个步骤 自我串s l 丫 上 拒绝 a 生成检测器集 监视受保护数据 图1 3 阴性选择算法模型 1 9 9 6 年 d h a e s e l e e r 2 8 1 对阴性选择算法进行了理论分析 总结出了算法的优 缺点 2 0 0 0 年 f o r r e s t 2 9 1 等人提出更有效的检测器产生算法 使得集合中检测 器的数量 随数据的长度呈线性增长 1 2 4 免疫进化算法 将进化计算与免疫系统相结合 得到的更有效的优化算法 把这类算法称之 为免疫进化算法 1 9 9 7 年 c h u n t 3 2 1 提出了一种免疫算法 通过引入抗体浓度控制机制 有 效控制了高适应度的抗体扩散速度 同时保持了群体的多样性 2 0 0 0 年 焦李成 王磊 3 3 6 提出了一种免疫遗传算法 通过引入免疫算子 免疫算子包括接种疫苗 提高适应度 和免疫选择 防止种群退化 该算法在 应用之前需根据问题特征信息提取疫苗 6 硕士学位论文 第一章绪论 1 3 本文研究内容 本论文的工作得到国家基础研究项目 多移动体协同与重构技术基础研究 国家自然科学基金重大专项重点项目 高速公路车辆智能驾驶中关键科学问题研 究 教育部博士点基金项目 多目标进化算法的应用研究 的资助 论文分五章 各章题目及主要内容概括如下 概括了生物免疫系统的功能特点 阐述了克隆选择学说和免疫记忆的基础理 论 介绍了经典免疫算法和模型 比较了免疫算法和其他进化计算的异同 简单 讲述本文的研究内容 针对高维的旋转 偏移函数的特点 本文提出了一种改进的克隆选择算法一 一贪婪免疫记忆克隆选择算法 构造了贪婪免疫记忆机制 采用多变异策略和多 轮竞争选择 增加种群多样性 防止种群陷入局部极值点 通过对c e c 2 0 0 5 函 数的测试 同时与n s d e o d e r g a f e p 和m e p 算法在独立运行2 5 次取平 均值进行比较 实验证明了该算法能够有效地优化高维全局旋转 偏移函数 针对免疫算法全局搜索欠缺的问题 本文提出一种新的改进的克隆选择算法 基于差异进化的克隆选择算法 将差异进化和克隆超变异相结合 促进抗体 之间的信息融合 使得子代抗体继承父代抗体信息的同时 携带着不同父代抗体 信息 丰富了抗体种群的多样性 与其他免疫算法s i a c a f c a 和o p t i m m a l g 对照实验 对y a 0 2 3 的1 3 个b e n c h m a r kf u n c t i o n 进行优化 独立运行2 5 次 结 果取平均值进行比较 实验表明算法具有较强的全局搜索能力 针对基于差异进化的克隆选择算法在全局优化过程中多样性不足的问题 本 文提出一种新的改进的克隆选择算法 基于差异进化的多样性免疫记忆克隆 选择算法 构造了多样性免疫记忆机制 将差异进化作为变异算子 采用三组经 验控制参数组 对y a 0 2 3 的2 3 个b e n c h m a r kf u n c t i o n 进行优化 与其他免疫算 法s i a c a f c a 和o p t i m m a l g 对照实验 独立运行2 5 次 结果取平均值 同时对前1 3 个高维函数维数n 3 0 5 0 1 0 0 进行测试 实验证明算法增加了种 群多样性 增强了全局和局部搜索能力 最后总结了论文中三种算法的特点 并展望了下一步的研究方向和工作 7 硕士学位论文第二章贪婪免疫记忆克隆选择算法 第二章贪婪免疫记忆克隆选择算法 2 1 引言 d ec a s t r o 等人提出的克隆选择算法 它的选择策略是依据抗体亲和度高低 来决定抗体是否存活 进入下一代进化种群 即贪婪选择策略 贪婪选择策略 能够有效的促进种群进化 确保不会出现种群进化倒退的现象 但是该策略 很 容易将潜在优秀的抗体给遗弃 而这些潜在的优秀抗体对搜索全局最优解却能起 到举足轻重的作用 c e c 2 0 0 5b e n c h m a r k 函数具有旋转 偏移的特点 在优化函数过程中 优化 函数未发生旋转或偏移之前 离全局最优点最近的抗体 经过旋转矩阵或偏移矩 阵之后 很可能落到距离全局最优点很远的地方 而原本很远的抗体 却很有可 能离全局最优点非常近 如何充分利用好这些潜在优秀抗体 但又不浪费过多的 评价资源 乃求解这类问题的关键所在 针对如何利用充分潜在优秀抗体的问题 t i w a r i 3 7 等人提出免疫记忆采用精 英机制 用于保留进化过程中最好的抗体 c u t e l l o 3 8 等人也采用精英主义思想 提出了淘汰老抗体的消亡操作和种群更新操作 n i t e s hk h i l w a n i 3 9 等人提出一种 快速克隆选择算法f c a f a s tc l o n a la l g o r i t h m 采用了一种新的基于精英机制 的免疫记忆 其中免疫记忆是通过赌轮选择获得 该算法免疫记忆的算法流程图 2 1 如下 p r o c e d u r e f u n c t i o no fi m m u n em e m o r yi nt t h g e n e r a t i o n p a r a m e t e r i m m u n em e m o r ya t 扰hi t e r a t i o n m a6 d u p d a t i o nl i m i t p o p u l a t i o n a tt t hi t e r a t i o n p a6 乞 b e g i n m a 6 i u p d t e m a b 1 p n oo fn e wa n t i b o d d i e si ni mi nt t h i t e r a t i o n i f z d p ab pa n t i b o d i e so i c u r r e n tb e s ta n d p s p r a n d o ma n t i b o d i e s e l s e 一 翌 1 l o g f p a6 砭 xa n t i b o d i e sf r o m m a6 ia n d p s x r a n d o m a n t i b o d i e s r r 1 e n dt 图2 1 免疫记忆算法流程 其中 p a b 为第t 代的抗体种群 p s 为抗体种群大小 i a b m t 为第t 代 8 硕士学位论文 第二章贪婪免疫记忆克隆选择算法 的免疫记忆抗体 d 为更新抗体数目的上限 为第t 代免疫记忆抗体中新的抗 体数 p s p 为随机从抗体种群中选取的抗体数 x 为从免疫记忆抗体中选择的 抗体数 p s d 为随机从抗体种群中选取的抗体数 p 为抗体比例系数 r 为从免 疫记忆中获取抗体的次数 尽管采用了精英机制的免疫记忆 但仍然不能很好的有效的开发潜在的优秀 抗体 而且一旦选择了没有潜力的抗体 将会浪费很多评价资源 针对这样的情 况 本文提出了一种改进的克隆选择算法一一贪婪免疫记忆克隆选择算法 g i m c s a g r e e d yi m m u n em e m o r yc l o n a ls e l e c t i o na l g o r i t h m 它的设计思路是 1 采用多轮联赛选择机制 给潜在的优秀抗体以一定的选择概率进入下一 代进化种群 同时将该父代抗体及其子代中最优秀抗体保存到贪婪免疫记忆种 群中 2 验证被选择的潜在的优秀抗体在进化过程中 能否体现出优秀的特性 如果不能 将以独特的贪婪免疫记忆回溯方式 回溯到该抗体被选择前的状态 提取该状态下保存在贪婪免疫记忆种群的最优抗体取代之 本文提出的贪婪免疫记忆克隆选择算法 g i m c s a 针对c e c 2 0 0 5 b e n c h m a r k 函数的旋转 偏移特点 让每个父代抗体经过克隆增殖产生三个子代 分别采用高斯变异 柯西变异和差异变异三种变异策略 以特殊的多轮竞争选择 机制 使得每个抗体都能够获得一定的进入新一代种群的概率 即让具有潜力的 优秀抗体子代有可能被保留 同时将最好的抗体保存到贪婪免疫记忆机制 如果 出现进化倒退 则以独特的贪婪免疫记忆回溯方式 防止了种群的进化停滞和陷 入局部极值 增强了种群的多样性 确保进化的效率和收敛性 2 2 贪婪免疫记忆克隆选择算法 2 2 1 克隆增殖操作 克隆增殖操作是将进化种群中的父代抗体中a 尼 么 七 分裂成了g f 个相同 的子代抗体口 七 么 尼 克隆增殖算子定义为 r c 彳 尼 r l 以 七 r l 口 七 z 多 口胛 七 7 2 1 其中 t c q i x a k f 1 2 脚 五为元素为l 的g f 维行向量 称为 a f 的g f 克隆 其中n c n p 是与克隆规模有关的设定值 本文中 每个父代抗体 克隆增殖产生3 个子代抗体 经过克隆之后的抗体为 a tt 尼 口f t 七 a i t 后 a i 尼 2 2 2 2 2 克隆变异操作 1 柯西变异 群体中每个抗体都表示成 a i r l i 其中a i 为种群中的抗体 玑为每个抗体中各 9 硕士学位论文第二章贪婪免疫记忆克隆选择算法 维度产生变异的概率标准方差 自适应机制的变异算子参数班更新公式为 味嘲 r l k e r n o i r n k 0 1 k 1 n 2 3 其中u 0 1 和m o 1 代表两个独立的随机数 均服从标准正态分布 参数 f 占和f 一 3 2 瓶j 2 t 万 第f 个抗体的第k 维发生柯西变异形式描述为 a i k a j k l u i k q o 1 2 4 式中q o 1 为柯西分布 k 石 志 0 0 x 0 0 2 5 柯西分布和高斯分布比较图2 2 看 两者形体上有点相似 但柯西分布具有 较高的两翼概率特性 即柯西分布有一条很长的尾巴 由此可见 相比于高斯分 布 柯西分布产生绝对值较大的随机数的概率大得多 容易产生一个远离原点的 随机数 也就意味着柯西变异很快跳出局部极小的区域的概率比较大 具有良好 的局部逃逸能力 保证算法具有良好的全局搜索能力 图2 2 高斯 g a u s s i a n 分布和柯西 c a u e h y 分布比较图 2 高斯变异 高斯分布产生的随机数大致分布在原点的附近 9 9 7 的随机数都将分布在 距离平均值3 个标准差之内的范围 高斯变异具有良好的局部搜索能力 能够确 保算法在较高的精度找到全局最优解 群体第f 个抗体的第k 维发生高斯变异形式描述为 a i k a i 后 r i k n 0 1 2 6 式中n 1 为高斯分布 乞 去唧 圭 等 0 0 x c x p 7 1 0 硕士学位论文第二章贪婪免疫记忆克隆选择算法 3 差异变异 差异变异融合了三个不同母体抗体信息 实现了抗体与抗体间信息的交流 加强多抗体间的相互学习 丰富后代的多样性信息 有利于增加种群多样性 增 强全局勘探能力 提高算法的收敛速度 第f 个抗体的第尼维发生差分变异形式 描述为 a i k a 4 尼 r a n d x a t k 一 后 1 尼 l 2 8 式中 a 加a 口和a d 是从抗体种群中 随机选取的三个互异抗体 本算法只采用了差异变异操作 而没有差异交叉操作 原因在于 差异进化 的交叉操作依赖于坐标轴 也就是说交叉操作不具有旋转特性 而c e c 2 0 0 5 函 数具有旋转 偏移特性 交叉操作产生点受旋转矩阵的影响 交叉操作在未旋转 的选点过程如图2 3 交叉操作在发生旋转后的选点过程如图2 4 憨 箩嘶 m i l i a n iv e u 3 o r 古名托嘁v 咖 图2 3d e 交叉操作在未旋转的选点过程 图2 4d e 交又操作在发生旋转后的选点过程 2 2 3 克隆选择机制 在种群p o p 中随机选取g 个抗体 组成联赛组 抗体经过多轮联赛选择 并 对其进行评级 基于等级来赋予抗体存活的概率 硕士学位论文 第二章贪婪免疫记忆克隆选择算法 任一抗体都将安排g 轮联赛选择 因此 总共有q 1 个不同的等级分配给 各个抗体 具体来说 每个抗体在g 轮联赛中 每次获胜即优于联赛组对象 则 r r l 最后根据比赛的获胜次数 决定抗体等级 其中抗体的等级被定义为 w i n x i r l i 其中眶胁 轨 匀 对于任何给定的等级 同等级的抗体存活率 是一样的 c 用来标识同一等级 的抗体群 基于文献 1 2 1 中的探究 g 通常被 设定为种群大小的平方根 两个选择的规则 规则一 每个抗体 父代和子代 都将分配一个等级m n x i 袖 o o 是服从指数分布的指数参数 决定着抗体的选择进程 抗体的选择概率计算公式描述如下 只 掣 2 9 i 1 克隆选择机制 既防止一些邻近但适应度较好的抗体将在种群中占统治地位 又让一些可能是在最优区域但适应度较差的抗体不会被过早地淘汰 能够保证了 种群的多样性 2 2 4 贪婪免疫记忆机制 所采用的克隆选择机制 为了确保种群的多样性 让适应度较差的抗体进入 种群 也就容易导致抗体进化倒退 为了防止进化倒退现象 又能够保持种群多 样性 本章节引入一个贪婪免疫记忆机制来解决这个问题 原理流程图如图2 5 所示 贪婪免疫记忆机制 是形成一个与进化种群大小一致的免疫记忆种群 用于 存储进化种群中抗体和其子代在克隆选择时 适应度最好的抗体 将其存储在贪 婪免疫记忆种群中 与其在进化种群中的同一位置 在进化下一代抗体的过程中 新产生的适应度最好的抗体 将与贪婪免疫记忆种群中对应的抗体进行适应度比 较 若优于贪婪免疫记忆种群中的抗体适应度 则将其取代 否则 保持原样 若抗体连续进化若干代 其适应度一直次于免疫记忆种群中对应的抗体适应 度 则该抗体可能陷入了局部最优 为防止继续进化倒退 它将被免疫记忆种群 中对应的抗体所取代 恢复到若干代之前的最优位置 1 2 硕士学位论文 第二章贪婪免疫记忆克隆选择算法 2 2 5 种群更新 开始 选择种群中第f 个位置上的父代抗体 聊 初始化卢1 y e s f f4 l k 0 f s n 立 结束 通过高斯变异产生子代抗体 x i 州 评价其适应度值 通过柯两变异产牛子代抗体 x i 川 评价其适应度值 通过差异变异产生子代抗体 x 川i 评价其适应度值 多轮竞争选择机制 让第i 个位置 上每个抗体获得相应的等级0 贪婪免疫记忆机制 将最优抗体与贪婪 免疫记忆种群第i 个位置的抗体比较 如 果适应度更优 则将其取代 否贝l j k k i ksr l k y e s 对种群第i 个位置的抗体 父子代 抗体 进行基于等级的概率选择 砌 茹 更新种群机制 贪婪免疫记忆种群中 第i 位置一卜的抗体取代抗体 i r ii 或 者与最优个体进行交叉操作 图2 5 贪婪免疫记忆机制原理流程图 若某个抗体连续进化若干代 其适应度一直没有改变 则该抗体很大可能陷 入了局部最优 将其与当前代种群中最优抗体进行交叉操作 交叉操作公式描述 如下 t r a n d l n c r 2 1 0 a 七 a 七 xt 七 1 一t 2 1 1 1 3 硕士学位论文第二章贪婪免疫记忆克隆选择算法 2 3g i m c s a 算法框架 2 3 1g i m c s a 算法流程 贪婪免疫记忆克隆选择算法g i m c s a 的具体步骤如下 s t e p l 初始化g i m c s a 算法参数 抗体种群规模 p 抗体维数 免疫记忆种 s t e p 2 s t e p 3 s t e p 4 s t e p 5 群i m 联赛选择轮数q 选择概率指数幂参数a 初始标准方差野 免 疫记忆时限g 交叉概率c r 随机产生初始化种群 彳 o 2 口l o 口z o 口咿 o 设定亲和度成熟条件 设定当前迭代代数k o 计算彳 p 中每个抗体 叩f 的亲和度值厂 口j 七 克隆增殖操作 巧 口 后 口 七 f z 肥五为元素为1 的3 维 行向量 即每个抗体 r h 产生产生3 个子代抗体 多变异策略 对每个抗体 袖的子代分别采用高斯 柯西和差分三种变 异策略产生新的抗体o f 7 从瓴 叩f 瓴 叩f 多轮联赛选择 任一抗体 父子代抗体 都将进行g 轮联赛选择 得到 相应的等级n w i n x f r l i 其中o n p 是与克隆规模有关的设定值 本文取 l v c 3 x n p i n t x 表示大于x 的最小整数 g k 为参与局部搜索的克隆个数 m k 为参与全局搜索的克隆个数 r m k 1 经过克隆之后的种群为 a t 尼 口 尼 a 2 尼 a m t 后 3 5 其中 a l 后 以 y 2 弘 3 2 2 克隆变异操作 免疫学认为 亲合度成熟和抗体多样性的产生主要是依靠抗体的高频变异 在本文的新算法中 将用于局部搜索的自适应高频变异算子和用于全局搜索的差 异进化相结合 从而达到全局和局部搜索的平衡 2 3 巧 d u 4 i t 彳 h 磅 聊i聃土珊i m 锄 硕士学位论文 第三章基于差异进化的克隆选择算法 1 自适应高频变异算子 自适应高频变异算子能够使新抗体围绕在父代抗体周围 做局部精细的搜 索 在算法开始时自适应变异概率为2 变异概率较大 在初期保持抗体多样 性 为了避免早熟现象 随着算法进化 变异算子采用的变异概率将逐步降低 到后期变异率接近踟 能够保留优良抗体 又能够避免最优解遭到破坏 自适应高频变异算子流程如下 s t e p l 产生自适应变异矩阵 m r a n d 1 l 4 变异算子f e 0 2 是一个实常数因数 控制偏差 变量的放大作用 2 4 硕 学位论文第三章基于差异进化的克隆选择算法 s t e p 2 为了增加干扰参数向量的多样性 引入交叉操作 则试验向量变为 y a k 只 七 只 后 7 玉 尼 3 10 小州 n m 嬲 虢 并 i 1 2 妒 j 1 3 d 3 11 式中 r a n d j 是 o l 之间的均匀分布概率 m b f 表示 1 d 2 f o 产生的随机整数 确保 七十1 至少从屹 尼 1 获得一个参数 c r 是交叉算子 取值范围为 o 1 s t e p 3 边界条件处理 确保产生的新抗体在可行域中 即若y i 1 芦 或 y o k 1 咒c 后 主 i 羔篓二苫羔篓二0 三善 c 3 一t 2 3 2 3 贪婪选择操作 按照贪婪准则 将父代抗体各自经过变异后的子代抗体中与父代抗体的亲和 度值进行比较 如果比父代抗体更加优秀 则取代父代抗体 进入新的种群 如 此则能保证下一代中的所有抗体都比当前种群的对应抗体更佳或者至少一样好 吣删 嚣嬲 巍黑 仔 3 3 基于差异进化的克隆选择算法流程 基于差异进化的克隆选择算法d e c s a s t e p l 初始化算法参数 抗体种群规模n p 抗体维数三 变异概率砌 变异 参数f 交叉概率 c r 随机产生初始化种群 s t e p 2 s t e p 3 s t e p 4 s t e p 5 a o a i o a o 口胛 o 设定亲和度成熟条件 设定当前迭代次 数k 0 计算彳 中每个抗体的亲和度值f a 足 克隆增殖操作巧 只 七 为第f 个抗体参与自适应高频变异的克隆抗体数 他 尼 为第f 个抗体参与差异进化的克隆抗体数 克隆变异操作乏 p 助个抗体参与自适应高频变异和加又妨个抗体参与差 异进化 贪婪选择操作砰 计算变异后子代抗体的适应度值 选择最优秀的抗体与 父代抗体进行比较 选择其中优秀者作为新的子代抗体 s t e p 6 条件判断 如果满足终止条件 3 4 仿真实验及其结果分析 则停止进化 否则 跳往s t e p2 2 5 硕士学位论文 第三章基于差异进化的克隆选择算法 为了验证算法的性能 本文将d e c s a 与其他免疫算法s i a t 2 4 l s i m p l ei m m u n e a l g o r i t h m c s a 2 0 1 f c a l 3 9 1 f 弱tc l o n a la l g o f i t h m 和o p t i m m a l g 4 6 吡较 应 用于经典的1 3 个b e n c h m a r k 劬c t i o n 4 7 1 通过比较 理解d e c s a 算法的特点和优 劣势 实验中每个测试函数独立运行2 0 次 评价次数限定为1 0 5 其中参数设置为 n p 2 0 n o 6 0 p m 0 0 2 f 0 7 c r 0 9 3 4 1 高维单峰函数 对于单峰函数f 1 f 5 f 1 函数为非线性的对称单峰函数 而且各维之间是可 以分离的 而函数f 2 f 5 各维之间具有相关性 不可分离 特别是函数f 5 相 邻维度之间具有很强的相关性 是一种很难极小化的典型病态二次函数 其全局 最优与可到达的局部最优之间有一道狭窄的山谷 曲面山谷中的点的最速下降方 向几乎与到函数最小值的最好方向垂直 d e c s a 对它们的优化结果图 如图3 3 图3 4 图3 5 所示 釜 图3 3d e c s a 对f l f 2 函数优化结果图3 4 d e c s a 对f 3 f 4 函数优化结果 图3 5d e c s a 对f l f 2 函数优化结果 d e c s a 与同类免疫算法对单峰高维函数f 1 f 5 的优化结果比较 如表3 1 所示 o p t i m m a l g 能够找到4 个函数f l f 2 f 3 f 4 的最优值 f c a 能够 找到3 个函数f 1 f 2 f 4 的最优值 c s a 能够找到2 个函数f 2 f 4 的最优值 2 6 硕士学位论文 第三章基于差异进化的克隆选择算法 d e c s a 能够找到1 个函数f 5 的最优值 s i a 能够找到1 个函数f 4 的最优值 针对函数f 1 f 2 d e c s a 性能明显比c s a s i a 效果要好 而比f c a o p t i m m a l g 要差 针对函数f 3 d e c s a 仅次于o p t i m m a l g 明显比其他 效果好 针对函数f 4 相对于其他算法 d e c s a 效果比较差 而在函数f 5 上 d e c s a 效果最好 表明d e c s a 对单模函数具有较强的探测能力 如表3 1 所 示 表3 1d e c s a 与同类免疫算法对高维单峰函数优化比较 3 4 2 高维多峰函数 对于高维 多峰函数f 6 f 1 3 函数f 6 由很多平滑的高地和陡脊组成 只有 一个最小值 且不连续 对于需要梯度信息来指导搜索方向的算法是很难解决这 种函数 函数f 7 含有一个随机噪声变量 通常用来衡量优化算法