【毕业学位论文】免疫进化算法在函数优化中的应用-计算机软件与理论

分类号 密级 U D C 编号 士学位论文 论文题目 免疫进化算法在函数优化中的应用 学科、专业 计算机软件与理论 研究生姓名 罗 一 丹 导师姓名及 专业技术职称 蔡自兴 教授 日 期 2008 年 5 月 12 日 函数优化问题（ 科学和工程应用领域经常会遇到的一类数学规划问题， 因而对其研究具有十分重要的理论和实际意义。免疫算法 (基于近年来新兴的计算智能人工免疫系统 (台而发展起来的一类仿生算法。进化算法（ 一类模拟自然进化机制而发展起来的随机搜索算法。近年来免疫进化算法已被广泛地应用于函数优化问题，并提出了大量的函数优化方法。 本文首先介绍了免疫算法的生物背景、相关理论及其应用。接着描述了进化计算的起源、发展、三个主要分支（即遗传算法、进化规划和进化策略） 及其应用领域， 然后提出了两种不同的免疫进化算法。本文主要工作如下： 1) 提出了一种新的免疫进化算法，该算法针对克隆选择算法在求解高维函数优化问题时，易陷入局部最优以及收敛速度较慢的弱点， 提出了基于生物免疫系统内部学习优化机制以及进化算法的免疫进化算法。它包括：正交交叉、单形交叉、克隆、多极变异、选择。新算法将进化计算的思想融入到克隆选择中， 提出了一种新的变异算子，在保证种群多样性的同时提高了算法的全局寻优能力。理论分析证明了算法的收敛性，并将算法应用于不同的测试函数进行仿真实验，结果表明该算法是有效的。 2) 基于免疫算法与差异进化算法，提出了一种新的基于局部搜索机制的免疫进化算法。该算法首先 初始化种群；接着采用单形交叉算子来对当前群体进行交叉操作；为 了提高算法的局部搜索能力，提高其收敛速度，提出了一种新的差异 进化算法，然后结合新的差异进化策略设计了局部搜索算子，最后借鉴免疫算法的更新策略更新种群，理论分析证明了算法的收敛性 ，并通过不同的测试函数验证了算法的可行性和有效性。 关键词 免疫进化算法，函数优化，全局搜索，局部搜索 I to a of in of So on it is in a of a of a of of to of As is by as 1) of in a of of by on of of a of to to 2) on on is is to to a is to of of a to of is to to 要. I . 一章 前言 .题研究背景 . 全局优化问题的概述 . 免疫算法 . 进化算法 .究现状 . 免疫优化算法的研究现状 . 进化算法的研究现状 . 免疫进化算法的研究现状 .文研究内容 .二章 免疫算法 .物免疫技术 .工免疫系统 .工免疫系统的应用领域 .章小结 .三章 进化算法 .化算法的特点 .化算法的主要分支 . 遗传算法 . 进化策略 . 进化规划 .化算法的应用领域 .章小结 .四章 一种新的免疫进化算法在函数优化中的应用 .隆选择算法的介绍 .关研究 .法的描述 . 进化算子 . 选择算子 . 克隆算子 . 多极变异算子 .法步骤 .法的收敛性证明 .验结果分析 .章小结 .五章 一种新的基于局部搜索机制的免疫进化算法在函数优化中的应用 .异进化的介绍 .关研究 . 种新的差异进化算法 .种新的基于局部搜索机制的免疫进化算法的描述 . 单形交叉算子 . 局部搜索 .法的步骤 .法的收敛性证明 .验分析 . 实验 1. 实验 2.章小结 .六章 总结和展望 .考文献 .谢 .读学位期间主要的研究成果 .士学位论文 第一章 前言 1第一章 前言 题研究背景 化技术是一种以数学为基础，用于求解各种实际问题的应用技术。它广泛应用于工业、农业、国防、工程、交通、金融、化工、能源、通信等许多领域。优化作为人们一个强有力的思想方法，迅速发展成为一门重要的应用数学学科，并且与分析、几何、代数、概率及计算机科学、系统科学、自动化等有密切联系，同时相互促进。在经济、金融、工程技术、分子生物、现代化管理、信息与控制等领域经常会遇到复杂的全局优化问题这些问题的数学模型可描述为 )x其中 x 称为决策变量 ,称为可行域， f 称为目标函数，构成 D 的条件( ) 0, 1, 2,i m=L 称为约束条件。当时称为无约束优化问题。对于x D 如果 0， 使得 (,) I 都成立 () ()f ， 称 x为 f 在 D 上的局部最优解 ,相应地 ()f x称为局部最优值。对于 x D ，如果对 x D 都成立() ()f 称为 x为 f 在 D 上的全局最优解，相应地 ()f x称为全局最优值。寻找目标函数全局最优解的问题称为全局优化问题。当 ()f x 和 (), 1,2, ,m= 题称为凸规划问题，此时只需通过求解其 题相对简单。但只要 ()f x 或 (), 1,2, ,m= L 中至少有一个非凸， 问题即成为非凸规划问题， 此时 般情况下它未必是全局最优解，甚 至连局部最优解都不是。当 ()f x 或(), 1,2, ,m= L 中至少有一个不可微分时，问题称为非光滑优化问题。 许多工程实践中遇到的问题可能更加复杂，它们通常具有精确建模困难、数据有噪声、时变等特征，即使建立出相应的数学模型，其目标函数仍具有多峰、非凸、 非光滑等特点。 传统的优化方法通常需要求解目标函数的梯度 (甚至 ，因而很难处理。如何有效地求解这些 全局优化问题己经成为影响这些领域发展的关键因素之一。 寻求一种适合此类问题的算法已成为最优化方法的一个主要研究目标和引人注目的研究方向。 本文主要研究连续变量的全局优化问题 )x其中 D 满足边界约束 , | ，12(, , , )nx xx x= L ，12(, , , )l= L ，硕士学位论文 第一章 前言 212(, , , )u= L ， f 为目标函数，并且总假定 f 在 D 上存在有限的全局最优解。 传统的优化方法大多数属于局部优化方法， 一般只能得到问题的一个局部最优解，甚至只是一个稳定点，因而并不能使工程实践中遇到的问题得到满意的解决。从上世纪 60年代，人们便开始了对全局优化问题的专门研究。尤其是近些年来，计算机技术的飞速发展，使得全局优化方法成为人们研究实际问题时进行建模和分析的重要手段之一。经过几十年的努力，在理论和算法方面都取得了很大的发展，使全局优化发展成为最优化学科领域中的一个重要分支。 全局优化方法可以分为两大类确定性方法和随机性方法常见的确定性全局优化方法包括区间分析法 (分支定界法 (填充函数法 ( 同伦方法 ( 轨道法 (等。这些方法通常将句题转换为一系列的子问题，然后反复调用传统的局部优化算法来求解这些子问题，以实现向全局优化目标的逼近，这些方法通常有比较好的理论结果（收敛性及收敛阶） ，但由于它们对子问题求解的结果依赖性较强，仍然需要使用目标函数的梯度，算法设计复杂，求解代价也比较高，容易陷入局部最优。尤其当问题规模增大，极小点数目增多时，这些方法仍然难以找到问题的全局最优解，实际求解效果有时并不理想。常见的随机性全局优化方法包括进化算法 (A)、蚁群算法 (1、人工神经网络算法 (模拟退火算法 (改进的击跑配合算法 (、禁忌搜索算法 (等，这些方法经过不断改进 ,逐渐成为解决复杂优化问题的一类有效方法2。 其中，进化计算 (一类以自组织、自适应、自学习、并行性为主要特征的仿生随机算法，是一种现代优化方法3。 0世纪 60年代产生以来，在近几十年里取得了辉煌的成就，涌现出 一批卓有成效的进化算法。 A) 演化策略 (S) 进化规划(P)和遗传程序设计 (P)等等。 编码方式是研究 是影响其算法性能的关键因素之一。 二进制编码、格雷编码、符号编码、实数编码等等许多研究结果都表明离散问题（如：组合优化问题）比较适合采用二进制编码、符号编码等方式进行编码，而连续空间问题（如：连续变量优化问题）比较适合采用实数编码方式进行编码。由于本文主要研究连续变量的全局优化问题，因而本文主要研究实编码进化算法 ( 不需要编码和解码过程 )、稳定性好、便于高精度计算、便于与传统算法融合，因而在科学研究和工程技术中得到了广泛应用。 硕士学位论文 第一章 前言 3不同的编码方案、繁殖算子和选择 算子相结合构成不同的进化算法。 实数编码 )，因而不同 括繁殖算子和选择算子 )。不 同 它们算法结构都比较简单，可以统一在一个算法框架下 :首先，随机产生初始种群为 (0)X， (随机选取若干个点构成初始点集合 )，然后对当前种群 ()X t( 0t )应用进化算子(对当前点集中的点进行某种启发式变换 )生成中间种群()X t， 随后对 ()X t,()X t中的个体进行评价，根据评价结果 (通常较好的个体有较大的生存机会 )实施选择，生成下一代种群 (1) ，直到满足一定的算法停止条件。 设待优化问题为 )x，实编码进化算法 (简单描述如下 : 疫算法 生物免疫系统是一种复杂的自适应系统， 有效地使用多种机制防御外部病原体。生物免疫系统的主要作用是识别所有生物体内的细胞，并将其分类为自体和非自体。 为了诱导合适形式的防御机制， 非自体细胞进一步分类。 通过进化学习，免疫系统在外部病原体和生物体自己的细胞之间进行辨别4。生物免疫系统的重要生理功能就是对“自己”和“非己”的抗原的识别和应答，它有着自身的运行机制，并可与其它系统相互配合、相互制约，共同维持机体在生命过程中总的生理平衡，具体表现为免疫防御、免疫监视、免疫自稳等生理功能。生物免疫系统在运行中表现出很多智能特性， 如对各种抗原的识别和应答过程实际是就是一个进化学习的过程。通过研究生物免疫系统识别“自己”和“非己”以及产生抗体: n, of t = ; 2(0) (0), (0), (0)= L , ,2 ,(0) ( , , , )xx x= L ; : a )X t )X t， 1, 2, , )L in 12() ( (), () (), ();t= L )X t()X t, ( )t , ()t 1) , n )X t()X t; is 图1编码进化算法硕士学位论文 第一章 前言 4对抗外界抗原的过程，研究人员提出了基于免疫原理的人工智能方法，如人工免疫算法（ 。人工免疫算法中的克隆选择算法给了我们很大的启示。 克隆选择算法是由 ，其灵感来自生物获得性免疫的克隆选择原理。克隆选择算法 模拟生物免疫系统的克隆选择原理 ,在生物免疫系统中 ,一旦病原体侵入肌体就被分解为抗原片段 , 同时活化、增殖和分化 ,产生浆细胞 ,通过中和、溶解和调理等作用 ,最终使抗原从体内消除。另有一些 它通过血液、淋巴和组织液循环 ,为下一次快速、高效地消除相同或者类似抗原引起的感染奠定了基础。 人工免疫算法保留了生物免疫系统的若干特点，如多样性好、鲁棒性强、隐含并行性等，同其他启发式优化算法相比具有自身的特点和优势，在近几年引起相关研究人员的普遍关注，并在模式识别、故障诊断、计算机安全等领域得到实际应用。然而，同其他新型智能算法类似，人工免疫算法也存在一些不足，如存在早熟收敛、局部搜索能力不足等，对人工免疫算法的深入研究和改进研究，已经成为优化计算领域的一个重要研究课题。 化算法 进化算法 起源可追溯到 50年代末 70年代以来产生了几种进化方法如：遗传算法 进化规划 和进化策略 适应人工智能技术，是一种具有“生成 +检测”的迭代搜索算法。进化算法 是模拟由个体组成的群体的集体学习过程，其中每个个体表示给定问题搜索空间中的一点，进化算法从任一初始的群体出发，通过随机选择（在某些算法中是确定的）变异和交叉（有时被完全省去）过程使群体进化到搜索空间中越来越好的区域6。该算法中的交叉和变异算子，体现了群体搜索和个体之间信息交换的两大策略，为每个个体提供了优化的机会，从而使整个群体在优胜劣汰的选择机制下保证进化的趋势。进化算法常用的遗传操作有交叉、变异和选择等，其中交叉是模拟有性生殖过程中的染色体交换过程，变异是模拟自然界中生物遗传物质的变异，选择则是模拟自然界的优胜劣汰过程。 究现状 士学位论文 第一章 前言 5目前，优化领域中应用的免疫优化算法主要有以下几种： 1、基于克隆选择原理的免疫优化算法， 这种算法利用免疫系统克隆选择的机制来实现优秀抗体的扩展和增生， 并利用了免疫系统中的记忆机制保证了算法能够最终收敛到全局最优解； 2、基于免疫系统的抗体浓度调节原理的免疫优化算法7，这种算法利用抗体多样性保持机制，改进传统的遗传算法，提高了算法的群体多样性，能有效地抑制早熟现象，使免疫遗传算法具有较好的全局收敛性； 3、基于免疫响应的免疫优化算法8，这种算法引入了免疫记忆和抗体多样性等免疫特性； 4、基于免疫疫苗接种的免疫优化算法，该算法引入疫苗接种的概念，能充分利用问题的先验知识，改善算法的性能，在优 化问题中获得了良好的效果； 5、基于免疫抗体记忆的免疫优化算法9，这种算法将随机搜索过程中的局部搜索和全局搜索采用不同的促进和抑制策略，有效保证了算法的收敛速度。 前，有关进化计算的理论研究基础主要研究以下问题： (1) 进化计算的数学模型和理论基础，如算法的收 敛性、收敛速度及复杂性析。 (2) 确定特别适合采用进化计算求解的问题类型， 以及采用进化计算求解效果不太明显的问题类型。 (3) 从理论上和实际计算效果两方面比较进化计算 方法与其它优化算法的计算效果。 (4) 进化计算与其它优化算法的结合，提出新的混合算法。 (5) 探索在非优化类问题中如何使用进化计算方法。 (6) 从生物进化或自然界的各种现象中获得新的启 发，提出新的方法或对现有进化计算的改进。 针对标准遗传算法存在的缺陷 ,人们提出了很多改进方法 ,例如锦标赛选择和并行遗传算法 ,免疫算法10,基于协调勘探和开采的遗传算法11等。这些方法都取得了较好的效果。 疫进化算法 (受生物免疫系统信息处理方式的启发构造的一类新智能优化算法。 生物免疫机制有一些与进化计算有互补作用的性能，因此，将生物免疫机制融入进化计算就提高了进化计算的性能。 焦李成和王磊等12基于疫苗接种理论提出基于疫苗的免疫遗传算法、 免疫策略和免疫规划； 基于主要组织相溶性复合体 (免疫网络理论提出一种自适应优化的免疫算法13；王煦法和曹先彬等14基于抗体间相硕士学位论文 第一章 前言 6互作用的浓度变化和抗体多样性理论提出了免疫遗传算法、 免疫进化策略和免疫进化规划； 李士勇等基于生物适应性免疫应答中的进化机理提出了一类自适应免疫进化算法15。 免疫进化算法和免疫算法等融入免疫机制的算法具各许多优点16， 如全局优化能力强、鲁棒性好、易于并行处理、智能度高等。但基本上是运用生物免疫机制中的某一个环节或者一种机制构造出相应的免疫进化算法， 生物免疫机制在他们的算法中所起的作用或者是全局搜索、或者是局部搜索。能否将基于生物免疫机制的全局搜索和局部搜索能力同时发挥， 构造一些融入了免疫机制和领域知识诱导的启发式规则的新型进化算法，具有很大的研究价值。 文研究内容 本章对免疫算法、进化计算处理函数优化问题进行了简要的叙述，并简要的介绍了免疫优化算法、进化算法、免疫进化算法的研究现状。本论文的研究内容主要围绕如何设计有高效的进化算法展开，各章节的具体安排如下： 本文第二章首先介绍了生物免疫学的基本概念及背景； 详细介绍了人工免疫系统的背景和免疫特性，人工免疫算法的基本原理和框架，以及当前主要的人工免疫算法类型；最后说明了人工免疫系统的主要应用领域。 第三章对进化计算的起源、发展作了简要回顾。详细阐述了进化算法的三个主要分支，进化计算是一个多学科相融合、具有很高实用价值的研究领域。其它学科研究的深入为进化计算的发展也带来了新的动力， 分化出了许多新的研究分支，如概率进化计算、免疫进化计算、克隆进化计算、协同进化计算等 ;最后说明了进化计算的应用领域。 第四章提出了一种基于生物免疫系统内部学习优化机制以及进化算法的免疫进化算法 时对该算法产生机理、算法中 各个算子进行了讨论。该算法利用正交交叉算子，使初始种群均匀化；随机生成新个体，维持种群多样性；运用单形交叉算子，提高种群的收敛速度；使用精英群体引导整个种群的进化方向；并且提出一种新的变异方法多极变异，此变异方法使得不同变异算子按照不同的概率作用到个体分量或者保持不变。对三种 2f 、317和 8进行比较，结果证明该算法是有效的，它不仅可以跳出局部最优而且能够以较快的速度收敛于或更接近函数全局最优解。 第五章提出了一种新的基于局部搜索机制的免疫进化算法。 该算法基于生物免疫系统内部学习优化机制以及差异进化算法，首先随机初始化种群；接着采用单形交叉算子产生新的子代个体；为了提高算法的局部搜索能力，提高其收敛速度，引入了一种基于种群分割和新的差异进化算法的局部搜索机制；利用免疫更新方法在每一代随机生成新个体，维持种群多样性；使用免疫记忆群体引导整个硕士学位论文 第一章 前言 7种群的进化方向。理论分析证明了算法的收敛性，并通过不同的测试函数验证了算法的有效性。 最后， 在第六章我们对本论文进行了总结并对将来的研究工作进行了分析与展望。 硕士学位论文 第二章 免疫算法 8第二章 免疫算法 本章首先介绍了生物免疫技术的基本特点， 然后阐述了利用生物免疫系统的思想产生的人工免疫系统相关理论、算法和结构，包括阴性选择算法、克隆选择算法、免疫 法以及免疫 法，接着说明了人工免疫系统的应用领域。 物免疫技术 生物系统十分复杂，它是一个高度分布、并行和自适应的计算系统。生物系统的很多机制已为人们所了解，这些大自然的 杰作给我们提供了很好的体系模型，生物模拟技术得到了广泛的应用。面对计算机病毒日趋严重的今天，基于生物免疫系统 (的研究给我们提供了一种新型求解优化问题的新方法。生物免疫系统具有学习、记忆、大规模分布式并行处理等特性， 通过淋巴细胞 (包括胸腺的 细胞 )的负选择 (程和二次响应来实现对本体 (非本体 (自适应判别，从工程应用的角度来说，生物免疫系统可以看成是通过 从不同种类的抗体构造自己 般在处理动态环境时发挥作用的19。图 2免疫原理示意图 (此图引用免疫的非线性模型 ，作者：漆安慎，杜婵英 )。 图2免疫”的英文为 意为抗感染不生病。生物体保护自身免受外来病菌的感染和侵害，是通过免疫系统完成的。免疫系统能够识别、消灭和清除硕士学位论文 第二章 免疫算法 9侵入机体的外部抗原 (即来自外部的病毒、细菌或寄生虫等 )，这一过程被称为免疫应答。免疫系统 (由具有免疫功能的器官、组织、细胞和分子组成，是机体免疫机