自然计算与智能优化.docVIP

班级班级 研 2128 班 学号学号 1202121326 自然计算自然计算 作作 业业 题题 目目 自然计算与智能优化 学学 院院 电子工程学院 姓姓 名名 王佳利 导导 师师 吴建设 2 自然计算与智能优化自然计算与智能优化 【摘要摘要】 从学科发展的角度来看，自然计算的研究是各类自然学 科和计算机科学相互交叉而产生的研究领域，它的发展完全顺应于 当前多交叉学科不断产生和发展的潮流。而自然计算研究领域的中 的优化问题作为一个重要的科学分支一直受到人们的广泛重视。本 论文在简单介绍自然计算、优化问题理论的基础上，重点介绍了自 然计算中的遗传优化和免疫优化，在组合优化问题上(tsp 问题)比 较了两者优化。也对遗传算法和免疫算法的现状前景、优缺点以及 一些改进的方法做了简单的论述，还重点介绍了一些优化算法在实 际中的最新应用。最后是对自然计算和智能优化算法的展望以及这 学期自己学习自然计算这门课的心得。 【关键字关键字】 自然计算 智能优化 遗传 免疫 组合优化 abstract from the view of the scientific development , nature of all kinds of natural sciences and computer science cross each other resulting in the study area of natural computation.its development completely conform to the current more interdisciplinary continuously produces and development trend. and natural computing research field in the optimization problem as an important branch of science has received widespread attention. this paper briefly in the natural computation, 3 optimization theory, focuses on the natural computing in genetic optimization and immune optimization, in the combinatorial optimization problems ( tsp ) compared both optimization. also on the genetic algorithm and immune algorithm, advantages and disadvantages of present situation prospect and some improved methods are briefly discussed.also introduced the optimization algorithm in the actual application of the latest. finally is on the prospect of the natural computing and intelligent optimization algorithms and during this semester my thoughts about learning natural computing this course. keywords：natural computation，ntelligence optimization ，genetic immunization，portfolio optimization 4 目录目录 1、自然计算4 2、优化5 2.1 最优化问题及其分类6 2.2 优化算法及其分类.6 3、遗传优化7 4、遗传算法8 4.1 改进的遗传算法10 4.2 遗传算法的现状与意义.11 5、免疫优化12 6、免疫算法13 6.1 改进的免疫算法13 6.2 免疫算法的现状与意义14 7、tsp 问题.15 8、优化算法的最新应用18 9、展望20 10、心得体会20 参考文献22 5 1、自然计算 自然计算是指以自然界，特别是生物体的功能、特点和作用机理为基础， 研究其中所蕴含的丰富的信息处理机制，抽取出相应的计算模型，设计出相应 的算法并应用于各个领域。自然计算包括了进化算法、神经计算、生物分子计 算、免疫计算、内分泌计算、生态计算、量子计算和复杂自适应系统（如社会 网络、经济系统、蚁群系统、蜂群系统、物理系统、化学系统）等在内的众多 以自然界机理为算法设计基础的研究领域，具有模仿自然界的特点，通常是一 类具有自适应、自组织、自学习能力的算法，能解决传统计算方法难以解决的 各种复杂问题。自然计算的应用领域包括复杂优化问题求解、智能控制、模式 识别、网络计算与安全、硬件设计、社会经济、生态环境等方面。 较之进化计算，自然计算含义更广。进化计算着重于生物的进化过程。然 而，科学家注意到许多非进化系统的原理和思想也是非常有用的，例如蚁群系 统和进化系统毫无关系，可是抽取出来，在工程应用方面取得了令人瞩目的成 功。此外，除了生物、生态系统，许多经济学、社会学、物理模型、化学模型 都可以抽取成为计算算法。从学科发展的角度来看，自然计算的研究是各类自 然学科和计算机科学相交叉而产生的研究领域，它的发展完全顺应于当前多交 叉学科不断产生和发展的潮流。 自然计算，甚至在其名称出现之前，就开始在生产生活的各个领域发挥其 作用。直到今天，在经历了几十年的发展后，自然计算已经发展为横跨各类自 然科学（特别是生命科学）和计算机科学的一门综合学科，其应用渗透到了各 个学科。不论是出现较早，研究较为透彻，应用较为成熟的遗传算法，神经网 络等技术，还是正迎来第二个 10 年的，应用正逐步展开的蚁群算法粒子群算 法和差分进化算法，亦或是出现不久，正逐渐为人所接受，并探索其适领域的 蜂群算法，蛙跳算法，都散发出无限的活力，帮助科学家和工程师们进行更为 高效，更为节约，更为简单的研究，设计与制造工作。在应用领域，尤其是高 技术领域，总是伴随着通常的数学方法不容易解决甚至无法解决的问题；随着 科学的发展，高新技术领域使用的计算手段只会越来越智能和高效，而自然计 算自身的特性使之成为完美的选择。 不论国内或是国际上，也不论医药还是航空领域，总能发现自然计算技术的 身影。目前国际上对自然计算框架下的各类算法的应用均有研究，且部分算法 的应用，如遗传算法，模糊逻辑，神经网络等，已经达到了成熟的阶段，各类 高层次的，复杂的应用层出不穷；而较为新兴的算法，如差分进化，粒子群算 法等，各类应用的探索也较为全面的展开。国内在科技领域的研究均有成果， 且很多研究领域成果相当丰富，但是与应用研究较为成熟国家相比，仍有许多 不足。1）国内的应用研究很多仅仅停留在实验阶段甚至理论阶段，没有经过实 物的验证，使结论缺乏可靠的根据，也同时阻碍了自然计算技术在实际应用中 的推广。2）国内的应用研究由于缺乏相应的设备与研究平台作为依托，对某一 具体领域的研究往往流于表面，没有进行深入的研究，很多有希望的方向也在 几篇报告发表后失去音讯。没有对特定领域特定问题深入的理解，也就不可能 抓住其精髓使用合适的自然计算技术解决问题，这正是国内一些应用研究的诟 病。自然计算应用的研究，应该立足于具体问题，深入研究，并放眼于方法论 研究，寻找具体问题间共同的特点，以进行算法的移植。注重发展理论的同时， 也注重算法的实际应用，以理论指导实践，也以实际推动理论。 6 2、优化 如今，科学技术正处于多学科相互交叉和渗透的时代。特别是，计算机科 学与技术的迅速发展，从根本上改变了人类的生产和生活。同时，随着人类生 存空间的扩大以及认识与改造世界范围的拓展，人们对科学技术提出了新的和 更高的要求，其中对高效的优化技术和智能计算的要求日益迫切。 优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术， 作为一个重要的科分支一直受到人们的广泛重视，并在诸多工程领域得到迅速 推广和应用，如系统控制、人工智能、模式识别、生产调度、vlsi 技术、计算 机工程等等。实现生产过程的最优化，对提高生产效率与效益、节省资源具有 重要作用。同时，优化方法的理论研究对改进算法性能、拓宽算法应用领域、 完善算法体系同样具有重要作用。因此，优化理论与算法的研究是一个同时具 有理论意义和应用价值的重要课题。 2.1 最优化问题及其分类 优化方法涉及的工程领域很广，问题种类与性质繁多。归纳而言，最优化 问题可分为函数优化问题和组合优化问题两大类，其中函数优化对象是一定区 间内的连续变量，而组合优化的对象则是解空间中的离散状态。 1）函数优化问题 函数优化问题通常可描述为：令为上的有界子集（即变量的定义域） ，s n r 为 n 维实值函数，所谓函数 f 在 s 域上全局最小化就是寻求点rsf: 使得在 s 域上全局最小，即。sx min )( min xf)()(: min xfxfsx 2）组合优化问题 组合优化问题通常可描述为：令为所以状态构成的解空间，, 21n sss 为状态对应的目标函数值，要求寻找最优解，使得)( i sc i s * s 。组合优化往往涉及排序、分类、筛选等问题，它是)(min)(, * ii scscs 运筹学的一个重要分支。 典型的组合优化问题有旅行商问题（tsp） ，加工调度问题(job-shop),0-1 背包问题、图着色问题、聚类问题、装箱问题等。 2.2 优化算法及其分类 所谓优化算法，其实就是一种搜索过程或规则，它是基于某种思想和机制， 通过一定的途径或规则来得到满足用户要求的问题的解。 就优化机制与行为而分，目前工程中常用的优化算法主要可分为：经典算 法、构造型算法、改进型算法、基于系统动态演化的算法和混合型算法等。 1）经典算法。包括线性规划、动态规划、整数规划和分支定界等运筹学中 的传统算法，其算法计算复杂性一般很大，只适于求解小规模问题，在工程中 往往不适应。 2）构造型算法。用构造的方法快速建立问题的解，通常算法的优化质量差， 7 难以满足工程需要。 3）改进型算法，或称领域搜索算法。从任一解出发，对其领域的不断搜索 和当前解的替换来实现优化。根据搜索行为，它又可分为局部搜索法和指导性 搜索法。 4）局部搜索法。以局部优化策略在当前解的领域中贪婪搜素，如只接受优 于当前解的状态作为下一当前解的最陡下降法等。 5）指导性搜索法。利用一些指导规则来指导整个解空间中优良解的搜索， 如 sa、ga、ep、es 和 ts 等。 6）基于系统动态演化的方法。将优化过程转化为系统动态的演化过程，基 于系统动态的演化来实现优化，如神经网络和混沌搜索等。 7）混合型算法。指上述各算法从结构或操作上相混合而产生的各类算法。 优化算法当然还可以从别的角度进行分类，如确定性算法和不确定性算法， 局部优化算法和全局优化算法等。 20 世纪 80 年代以来，一些新颖的优化算法，如人工神经网络、混沌、遗传 算法、进化规划、模拟退火、禁忌搜索及其混合优化策略等，通过模拟和揭示 某些自然现象或过程而得到发展，其思想和内容涉及数学、物理学、生物进化、 人工智能、神经科学和统计力学等方面，为解决复杂问题提供了新的思路和手 段。这些算法独特的优点和机制，引起了国内外学者的广泛重视并掀起了该领 域的研究热潮，且在诸多领域领域得到了成功应用。 3、遗传优化 优化处理的是具有多个变量且通常需要服从等式和不等式约束的最小化或 最大化函数问题。在运筹学、管理科学和工程设计中，优化问题处于非常重要 的地位。许多工业工程的设计问题非常复杂而困难，以至于难以采用传统优化 方法进行求解。近年来，由于遗传算法作为新型优化方法具有良好的潜质，该 算发受到了普遍的关注。遗传算法具有简单、易操作、需求低、并行和全局性 等特点，它已经在非常广泛的领域中取得了成功应用。遗传优化的主要领域有： 全局优化、约束优化、组合优化、多目标优化等。 1）全局优化 全局优化采用在感兴趣的区域内可以区分全局最优解和众多局部最优解的方 法。全局最优问题通常具有无约束优化的形式，即问题除了一个最小化或最大 化函数之外没有其他限制。 传统全局优化方法可以粗略的分为两类：确定性方法和随机性方法。遗传 算法在那些对于传统爬山法和基于导数的方法来说性质恶劣、不可微、不连续 的函数优化方面取得了很多成功。这类问题的例子包括多峰、不可微和不连续 问题。自 20 世纪 70 年代早期遗传算法出现以来，全局优化就是其主要应用目 标之一，同时也为开发有效的全局优化问题算法提供了许多帮助。通常将遗传 算法应用于全局优化问题的方式是将每个决策变量采用二进制方式进行编码。 2）约束优化 非线性规划（或约束优化）处理的是有等式和不等式约束的优化目标函数的 问题。由于许多实际问题无法建模为线性规划问题，因此非线性规划成为在几 乎所有工程、运筹学和数学领域中非常重要的工具。 用于操作染色体的遗传算子通常会产生非线性规划的不可行后代，因此将遗 传算法应用于非线性规划的主要问题就是如何处理约束。最近提出了若干在遗 8 传算法中处理约束的方法。现存的方法可以粗略地分类如下：拒绝方法、修补 方法和罚方法。 3）组合优化 组合优化的特点是可行解的数量有限。在过去 10 年中，遗传算法受到组合 优化界人士越来越多的关注，而且在研究和许多工业工程领域的实际应用中表 现出很强的生命力。 组合优化包含具有不同特征和属性的一大类问题。虽然这些问题彼此不同， 然而问题的本质可以归纳为下列类型之一： 确定与问题有关的某些项的排列 确定某些项的组合 确定某些项的排列和组合 任何带有约束的上述类型 组合优化问题常见的特点是如果排列和组合确定了，就可以方便地通过依 赖于问题的过程来确定解。因此一般采用遗传算法来处理这类问题的方法是： 采用遗传算法来进化所考虑项的排列和组合； 采用启发式方法根据排列和组合来构造一个解。 将遗传算法应用于组合优化问题既是富有挑战性的又是困难的。关键的问 题时如何将问题的解编码为染色体。大多数研究人员最初的努力都是对问题提 出新的有效编码方式，这就诞生了非常活跃的研究领域：基于次序的遗传算法。 4）多目标优化 自 20 世纪 60 年代以来多目标优化（multiobjective optimizations）问 题就受到研究人员越来越多的关注。在多目标优化问题中，多个目标函数需要 同时进行优化。由于目标之间的无法比较和矛盾等现象，导致不一定存在在所 有目标上都是最优的解。某个解可能在一个目标上是最优的但在另一个上是最 差的。因此，多目标问题通常存在一个解的集合，它们之间不能简单的进行比 较好坏。对这种解来说，不可能使得在任何目标函数上的改进不损害至少一个 其他目标函数，这种解称作非支配解（nondominated solutions）和 pareto 最 优解（pareto optimal solutions） 。 在过去的几年中，将遗传算法应用于多目标优化问题成为研究热点，这种 算法通常称作进化多目标优化（evolutionary multionbjective optimization）或遗传)多目标优化（genetic multiobjective optimization） 。 遗传算法的基本特点是多方向和全局搜索，带有潜在解的种群因此能够一代一 代地维持下来。从种群到种群的方法对于搜素 pareto 解来说是有益的。 关于用遗传算法来解决多目标优化问题中涌现出的一个特别问题是，如何根 据多个目标来确定个体的适应值。在过去 10 年广泛研究了适应值分配机制，并 提出和测试了许多种方法。 4、遗传算法遗传算法 遗传算法（ga）是一种基于生命进化机制的新型智能算法，是人工智能的 重要新分支。ga 是根据 darwin 的“适者生存、优胜劣汰”的自然进化规则， 通过模拟自然界生物的进化过程来进行搜索计算和问题求解。1975 年，美国 michigan 大学的 holland 教授的专著 adaptation in natural and aritifical 9 systems 的出版，标志着 ga 的创立。1985 年，在美国 carnegie mellon 大学 召开了第一届国际遗传算法会议 igga85.进入 20 世纪 80 年代后，ga 无论在理 论研究还是应用研究方面都呈现了强劲的发展态势，从 20 世纪 90 年代以来一 直处于不断上升的时期，涌现出很多改进的 ga，如递阶 ga、chc 算法、 messyga、基于实数编码的 ga、基于小生境的 ga、微种群 ga、双种群 ga、自适 应 ga、协同多种群 ga、浑屯 ga 等。 ga 通过参数空间编码并用随机选择作为工具来引导搜索过程向更高效的方 向发展，不需要关于问题的先验知识，能适应不同领域的优化问题的求解，在 复杂优化问题求解中有比较显著的优势。ga 的应用研究比理论研究更为丰富， 已渗透到许多学科，其应用可分为三大部分，基于遗传的优化的算法、基于遗 传的优化编程、基于遗传的机器学习等。目前 ga 以被广泛应用于许多实际问题， 如函数优化、图像识别、机器学习、ann、优化调度等许多领域。 标准 ga 的操作算子一般包括选择、交叉和变异三种形式，它们构成了 ga 强大搜索能力的核心，是模拟自然选择以及遗传过程中发生繁殖、杂交和变异 现象的主要载体。选择是 ga 中最主要的机制，是从当前群体中选择出适应度比 较高的个体用于繁殖下一代。交叉是对两个父代个体的相同位置的基因进行变 换，从而产生新个体。其作用是将原有的优良基因遗传给下一代个体，并生成 包含更复杂基因的新个体。变异操作是模拟生物体进化中染色体上某位基因发 生突变现象，从而改变染色体的结构和物理形状。标准 ga 的具体流程包括编码 设计、产生初始种群、个体评价、选择复制、交叉、变异和中止判断等。对于 许多改进的 ga，主要是对父代个体的选择复制算子、交叉算子和变异算子等进 行改进，使改进后的 ga 具有更好的搜索精度和收敛速度。ga 获取的解为全局 最优解，是一种只考虑输入与输出关系的黑箱方法，适用于处理各种复杂问题。 ga 与传统优化算法相比，具有很多优点： 1)采用群体并行搜索寻找最优解，搜索轨道有多条，覆盖面广，利于全局寻 优。 2)对适应度函数的性质无特殊要求，即使所定义的适应度函数不连续、多峰 或不可导时，也能够以很大概率收敛到全局最优，因此其普遍适用性好。 3)具有极强的容错能力。ga 的初始解带有大量与最优解相差甚远的信息， 通过选择、交叉、变异等操作能迅速排除与最优解相差极大的解，这是优异的 并行滤波机制。因此，ga 具有很高的容错能力。 4)使用概率搜索技术，以增加搜索过程的灵活性。ga 属于一种自适应概率 搜索技术，其选择、交叉、变异等运算均以一定概率进行，增加了其搜索过程 的灵活性。 5)极强的鲁棒性。实践和理论都证明在一定条件下 ga 总是以概率 1 收敛于 问题最优解。 6)克服了容易陷入局部极点的缺点，是一种全局优化算法。 虽然 ga 具有易于实现、普遍适用性好、鲁棒性强等优点，但是随着在各个 领域的大量应用，其不足之处逐渐显露出来： 1）在遗传进化初期，通常会产生一些超常个体，这些个体的适应值大大超 过群体的平均适应值，从而容易控制选择过程，也容易产生早熟现象，影响算 法的全局寻优效果。 2）如果初始种群选择不当，会导致过早陷入局部最优点，影响全局寻优效 果。 10 在遗传进化后期，由于种群的个体适应度差异减小，进入配对集的机会相当， 而且杂交后的新个体也不会有多大变化，从而容易导致进化缓慢。 3）父代个体的选择复制采用“轮盘赌选择”策略，不能保证每个优良个体 都被选择。 4）两个父代个体进行交叉后，不能保证产生的新个体的适应度高于父代个 体，这也会造成进化缓慢的现象 。 经过几十年的发展，ga 已经比较成熟。但是对于上述的不足之处的改进有 限，收敛速度有待进一步提高。在将来，ga 还将继续跟其他学科进行交叉和发 展，相互促进共同发展，以得到更加灵高效的优化算法。 4.1 改进的遗传算法 随着遗传算法研究的发展，人们在 sga 的基础上，为提高算法收敛速度、 防止算法陷入未成熟收敛从而获得全局最优解进行了大量研究，提出了许多改 进的遗传算法，在此，仅对微种群算法、双种群算法和自适应遗传算法加以简 单介绍。 a a 微种群算法微种群算法 微种群法可以很快获得最优解，这种方法不是按照平均特性来评价群体行为， 而是根据“迄今为止”的最好个体来评价和完成算法。此方法先产生小的随机 群体，对它进行遗传操作并收敛之后，把最好的个体传至下一代，产生新的群 体，再进行遗传操作，如此重复，直至完成总体收敛。具体算法可描述如下： （1） 在群体中随机选择 n 个个体组成微群体； （2） 计算适应度并确定最好个体，将其传到下一代，以保证优良的模式信息 不致丢失； （3） 按照联赛选择策略确定其余个体。在该策略中，个体随机编排，相邻的 一对进行竞争以活动最终的字符串； （4） 用概率 1 进行交叉运算，以加速产生确定位高的模式。 （5） 检验收敛条件，如果收敛转至（1） ，否则转至（2） ； 在进化过程中以合理的间隔，通过“启动再启动”过程，不断引入恒定ga 数目的新群体，寻找较好个体，这样可以避免未成熟收敛，并且有较快的收敛 速度。 b b 双种群遗传算法双种群遗传算法 在多模态函数寻优时，为进一步解决遗传算法在解空间中的快速搜索，并避 免陷入局部最优解的矛盾，提出了双种群遗传算法（dpga） 。它是用两个群体分 工协作来解决上述矛盾，一种是全局种群，主要用于寻找可能存在最优解的区 域；另一种是局部种群，其主要任务是仔细搜索全局种的最优价群划分的区域， 找到该区域中的最优解。 全局种群采用 ga 是很自然的，因为它能很快地找到近似最优的区域，且不 会陷入局部极小点；局部种群在含最优解的区域内收敛到最优解的过程也可看 成是小范围的多模态函数寻优，它和全局种群的算法只是搜索范围和编码长度 的不同，所以采用的方法。但是 dpga 比单纯的的搜索速度快，这是gaga 11 因为 dpga 能将寻优范围限制在含有最优解的较小区域内，而不用搜索其他无关 区域，因此收敛速度快。dpga 算法步骤可描述如下： （1） 初始化。 设置进化参数，随机产生全局种群 g，令局部最优值 lopt=0； （2） 在全局种群 g 中搜索若干代得到当前最优解 xx 和最优值 gopt，使得 f(xx)=gopt; （3） 若 goptlopt，则局部种群的搜索中心为 x=xgopt；否则，局部种群的搜 索中心为 x=xlopt; （4） 局部搜索。在搜索中心为 x，宽度为 w 的范围内随机产生初始局部种群 gl，进行遗传搜索，若干代后得到当前最优解和最优值； （5） 令 opt=maxgopt,lopt，若 opt 满足结束条件或者进化代数超过设定值 则进化过程结束；否则转至（2） ； c c 自适应遗传算法自适应遗传算法 在遗传算法中，交叉概率 pc 和变异概率 pm 的选择是关键；1994 年提出的这 种自适应遗传算法（aga）的交叉概率 pc 和变异概率 pm 能够随个体适应度自适 应改变。当群体中的个体适应度趋于一致或局部最优时，增加 pc 和 pm 以跳出 局部最优；当群体个体适应度比较分散时，减少 pc 和 pm，以利于优良个体的 生存。同时，对于适应度高于群体平均适应度值的个体，选择较低的 pc 和 pm，使得该个体能够得到保护而进如下一代；对于度低于群体平均适应度值的 个体，选择较高的 pc 和 pm，以促进该个体被淘汰。自适应遗传算法能够提供 相对于问题解的合适度高于群体平均适应度值的个体，选择较低的 pc 和 pm， 在保持群体多样性的同时，也保证了算法的收敛性。其算法步骤可描述如下： （1） 编程的设计方法同标准遗传算法 sga。 （2） 产生初始群体，群体规模为 n。 （3） 定义适应度函数，计算群体中每个个体的适应度 f； （4） 用轮盘赌方法选择 n 个个体，计算个体平均适应度值 favg 和 fmax。 （5） 将群体中的个体随机搭配成对，对每对个体，根据自适应公式,计算交叉 概率 pc，按 pc 进行交叉操作产生新个体，即在（0,1）区间上生产一个 随机数 r，若 r 值小于 pc 则对该个体对进行交叉操作。 （6） 对群体中的所有个体，按照自适应变异公式计算变异概率 pm，以 pm 对 个体进行变异操作。 （7） 计算新生产个体的适应度值，由新个体和父代个体重新组成新的群体。 （8） 判断是否达到预定结束条件，若是，则结束寻优过程；否则转至（4） ； 4.2 遗传算法的现状与意义 在遗传算法的基础理论联系实际研究方面，人们根据算法的适用性针对问题 的类型进行了划分，尽管遗传算法不能保证在多项式时间内找到 np 完全问题的 最优解，然而它经常能找到组合问题很好的次优解。 在遗传算法是模型方面，人们为了提高遗传算法是搜索能力，提出了几个扩 展的遗传算法模型，关于遗传算子，研究人员提出了杂交算子，提出了通过阻 止类似的个体之间的杂交来防止过早的收敛，还有编码方法的提出、超平面搜 索方法、还有一种更有效的模型就是混乱遗传算法，它生产 k 个短模式，并通 过每次至少改变 k 位来避免落入局部解。 根据遗传算法发展趋势来看，遗传算法作为一种函数优化方法在工程方面的 12 应用比起用于模拟自然更受人们重视。 遗传算法另一个活跃的研究方向是它们在神经网络方面的应用，这包括优化 神经网络的连接权系数和网络的空间结构。在遗传算法与神经网络相结合正成 功的被应用于从时间序列分析来进行财政预算。在这些系统中，训练信号是模 糊的，数据是有噪声的，一般很难正确地克服这个困难。显著的提高系统的性 能，muhlenbein 分析了多层感知机网络是局限性，并猜想下一代神经网络将会 是遗传神经网络。 还有一个值得注意的研究方向是，遗传算法正用于机器学习中的程序设计， 它排除了软件设计中一个最大的障碍-预期先详细说明一个问题的全部特征并 针对问题的特征决定程序应采用的对策。利用模拟演化，研究人员能够“繁殖” 程序来解决那些其结构还无人完全了解的问题。在设计像喷气发动机这样的复 杂系统方面，遗传算法有可能在更大的范围内探究程序的自然选择问题，这方 面的成果将可能会揭示出生命和智能在自然界中演化方式的细节。 尽管遗传算法模拟了生物界中的自然选择，但是目前遗传算法运行规模还远 远小于生物演化规模。holland 等人研制的分类系统含有多达 8000 条规划，但 这个数量只是自然界生物群体能生存的下界。未受危及的大型动物数量可达数 百万个，昆虫群体有万亿之多，细菌的数量更是无法胜数，如此规模的数量极 大地增强了隐含并行性的优势。 随着大规模并行计算机的不断普及，研制数量更加接近自然物种的软件群体 将是可能的。遗传算法固有的并行性使得它非常适合这种大规模并行计算机。 由于遗传算法的操作主要是在单个位串上，至多是一对串之间的杂交，所以可 以让处理机负责处理单个位串，从而可以并行处理整个群体。 虽然现在对遗传算法的效用下断言还为时尚早，但可惜的是，遗传算法已经 引起了计算机界人士的广泛注意。当今计算机科学的各个领域几乎显示出向并 行计算过度这一趋势。在这场变革中，一个鼓舞人心的结果就是新的应用领域 不断发展，诸如格子气流体、神经网络和遗传算法。这些领域的研究从一开始 就是基于并行处理。虽然在遗传算法的研究过程中还将会不断出现新的困难， 但是人们不得不正视大量的研究成果为此研究领域所展示的巨大潜力。 5、免疫优化 使用人工免疫系统解决问题时，一般用抗原表示要解决的问题（如目标约束） ，用抗体表示问题的解，用亲和力表示解的评估，用从记忆细胞产生抗体表示 联想过去的成功解，用淋巴细胞分化表示优良解（记忆）的保持，用抗体抑制 表示非优化解的删除，利用交叉、变异等操作算子产生新抗体表示抗体增加 （搜索最优解）等。 免疫算法属于一类导向性随机全局搜索方法。它本质上具有全局收敛的能力， 但针对不同的问题，算法的实现形式有很大的差异；有时针对同一个问题，算 法是实现形式也不尽相同，所获得的结果也可能相差甚远。下面就影响免疫算 法形式、效率及精度等方面的关键参数和免疫操作算子进行讨论。 1）亲和力度量方式 免疫算法中最复杂的计算是亲和力度量。根据抗原、抗体的编码机制不同， 免疫算法中计算亲和力的方式也不一样。例如 hamming 形态空间的 hamming 距 离，euclidean 形态空间的 euclidean 距离。 13 在免疫算法中采用哪种亲和力度量方法，目前还没有统一的模式，同时每一 种方法都有自己的优缺点，对同一问题，采用不同方法对免疫算法的性能和效 率都有较大影响。 2）克隆选择操作 克隆选择的作用是从当前种群中选出优良个体作为父代以繁殖下一代。免疫 算法在搜索过程中，一方面要选择优良个体，实现优胜劣汰，使搜索收敛于全 局最优解；另一方面，在搜索过程中要保持群体多样性，使搜索空间不断扩大， 避免收敛于局部最优解。因此，克隆选择力度和群体多样性是免疫算法的一对 矛盾。若加大克隆选择力度，能提高收敛速度，但群体多样性将减弱；反之， 减少克隆选择力度，能提高群体多样性，但影响算法的收敛速度。克隆选择算 子是免疫算法重要的算法之一，它在群体多样性和收敛性之间起着动态调整作 用，其性能的好坏直接关系免疫算法的求解质量。因此，如何在免疫算法中设 计一种有效的克隆选择算子操作，是避免有效基因缺失，提高算法全局收敛和 计算效率的关键因素之一。 3）变异操作 免疫算法作为一种搜索算法，变异操作在该算法中显得尤为重要，它不但有 可能恢复在进化中被破坏的较优抗体基因，而且可以产生抗体群中没有的较优 基因。同时变异操作也是免疫算法用来维持抗体群的多样性的主要途径之一， 通过该操作可以使算法最终收敛于多个局部极小点或收敛于全局最优点。另外， 控制抗体是否产生变异的变异率的取值既不能太大也不能太小，太小变异操作 的效果不明显，群体多样性不能保证，因而不能收敛于全局极小点；但是变异 率也不能太大，太大则群体的稳定性变差，搜索过程需要长时间才能收敛，容 易出现震荡。 因此，如何确定合适的变异率使得免疫算 法既可搜索到全部极小点，又可保持稳定收敛的状态，是设计免疫算法过程中 需要重点考虑的因素之一。 4）其他相关参数 抗体群的规模一直是免疫算法的一个重要参数，它是影响算法并行性和群 体多样性的决定性因素之一。如果抗体群的规模设置太大，则并行搜索的范围 太小，难以找到所有极值；如果抗体群的规模太大，又会不必的延长搜索过程 所需要的时间，影响算法的收敛速度。 记忆库规模也是影响免疫算法性能的因素之一。它在免疫算法中作为搜索 结果不仅给下一次同类问题搜素提供初始结果，而且在本次搜索过程中作为每 一代的较优抗体参与下一代群体的竞争。同时，免疫算法的多极值搜索目标使 得记忆库规模对搜索的性能影响较大。 另外，在免疫算法中，抗体浓度阈值的设置对抗体多样性也具有重要影响， 从而影响算法的性能。同时，浓度阈值同种群规模息息相关，通常，对于不同 问题有不同种群规模，其浓度阈值可在一定范围内变化。因此，对于免疫算法 来说，针对问题的特点，选择适当的浓度阈值、记忆库的规模及抗体群规模等 无疑会提高算法的效率和性能。 6、免疫算法 14 免疫算法（immune algorithm,ia）的执行步骤如下： (1)随机产生初始父代种群 al; (2)根据先验知识抽取疫苗； (3)若当前群体中包含最佳个体，则算法停止运行并输出结果；否则，继续； (4)对于目前的第 k 代父代种群 ak 进行交叉操作，得到种群 bk; (5)对 bk 进行变异操作，得到种群 ck; (6)对 ck 进行接种免疫操作，得到种群 dk; (7)对 dk 进行免疫选择操作，得到新一代父代 a（k+1） ，转至（3） 。 6.1 改进的免疫算法 a 自适应尺度混沌免疫优化算法 结合混沌优化算法与免疫算法的特点，提出了一种采用折叠次数无限的自映 射 x=sin(2/x)产生混沌变量的自适应变尺度混沌免疫优化算法，通过自适应变 尺度方法不断调整优化变量的搜索空间，同时采用最大循环次数作为控制指标， 既保证了寻优的准确性，又保证了算法的快速性。 b 量子免疫优化算法 针对传统免疫算法存在的搜索空间较小的不足，充分利用量子计算的高效并 行性，将量子理论和免疫理论的结合，对抗原、抗体采用量子编码，并与克隆 算子相结合，提出了一种新的算法-量子免疫算法，并构造了量子免疫算子和 量子变异策略。其中，量子变异实施于量子抗体，用于加快算法的收敛速度； 量子变异实施于普通抗体，用于克服算法的早熟。 c 矢量距免疫网络聚类算法 ainet 算法生成的网络结构对压缩阈值的选择非常敏感，针对这一问题结合 免疫网络的调节和抑制机制，设计了一种基于矢量距的抗体促进与抑制策略， 并对 ainet 模型进行了改进。 d 目标进化免疫网络聚类算法 针对 ainet 算法中没有定义目标函数、记忆网络动态无规律变化等问题对其 进行改进，提出了基于目标进化的人工免疫网络聚类新算法，将人工免疫网络 压缩聚类抽象为多目标规划问题，定义了记忆网络的整体进化目标，并采用用 疫苗注射策略提升免疫学习质量。 e 免疫融合阴性选择算法 针对阴性选择算法检测器生成效率低、匹配阈值难确定、实际漏检率与期望 漏检率误差较大等问题，提出了基于免疫调节的阴性选择算法，新算法经历克 隆选择使自体相似度较低的检测器成熟，并自适应地确定检测器的匹配阈值， 经历免疫抑制优化成熟检测器的分布。 6.2 免疫算法的现状与意义 免疫算法伴随着人工免疫系统（ais）的发展而来，是基于免疫系统的识别 15 多样性、免疫自我调节和免疫记忆特性而设计的，也是 ais 的重要研究内容之 一。1990 年，bersini 首次使用免疫算法来解决问题。早期比较具有代表性的免 疫算法是 hunt 提出的免疫学习算法。该算法包括骨髓、b 细胞网络、抗原、抗 体等，是完全模拟免疫系统机理而设计的。20 世界末，forrest 等开始将免疫算 法应用于计算机安全领域。同期，hunt 等开始将免疫算法应用于计算机安全领 域。同期，hunt 等开始将免疫算法应用于机器学习领域。目前，已经发展出多 种免疫算法，主要有免疫遗传算法、免疫 agent 算法、阴性选择算法和克隆选 择算法等。近几年来又发展出多种改进型的免疫算法，如基于疫苗的免疫算法、 基于抗体多样性的免疫遗传算法、基于免疫网络理论的免疫遗传算法、基于免 疫更新机制的遗传算法、克隆选择免疫算法等。对免疫算法的研究主要集中在 利用免疫机理来改进其他的控制算法，如免疫遗传算法、免疫神经网络等。从 20 世纪 90 年代末期，出现了多种基于免疫机理的理智的智能控制器或智能算 法，如基于免疫细胞特有的反馈机制的生物智能控制器，利用免疫算法对 pid 控制器的控制参数进行动态优化调整的方案。免疫算法的研究结果已涉及自律 移动机器人、计算机网络安全、智能控制、模式识别、机器学习、数据挖掘、 故障诊断及优化设计等许多领域。 客观地讲，人工免疫系统的相关算法多是在 1997 年后提出后，而且这些算 法几乎都是针对特定问题而言的，对算法设计复杂性估计、收敛性证明等深刻 而具有普遍意义的研究成果还很少。 。因此，现阶段学者们应该着重研究以下方 向： 1、进一步研究免疫系统的各种计算机理。只有对免疫机理有了深刻认识才 能为算法构造提供保障；而且，新机理的发现必将催化新算法的产生。 2、改进已有的人工免疫系统模型。具体点讲，就是利用模型深入理解算法 的执行过程，分析算法的收敛性，计算复杂性，为算法的评价和改进提供依据。 3、为人工免疫系统开辟新的应用领域。应用是方法研究的动力，也是检验 算法优劣的标准。 4、基于人工免疫系统的智能整合集成方法研究。免疫系统机理可以被用于 改进现有的方法，在这一交叉整合过程中诞生的新思想和新方法，又把人工免 疫系统的能力扩展到能应付越来越复杂的问题，人工免疫系统也正以全新的方 式对人工智能等学科做出贡献。 算法设计将是人工免疫系统研究者所关注的主要方向之一，围绕算法研究应 注意以下三个方向：一是发现新的思路，构造新的算法；二是对现有算法进行 改进；三是算法的理论分析。 7 7、tsptsp 问题问题 问题描述 tsp 问题是一个典型的 np 问题，其实质是针对 n 个坐标（假设的 n 个城市 的位置）在一定条件（城市之间相互连通的路径限制）下，寻找一个满足下列 条件的整数排列（其中，代表最佳路径中第 i 个城市的编, 21n ppp i p 号） 16 （7-1）),(lim(),(),( 1, 11 1 1 j n ji ji ini n i i ppdppdppdd 式中，表示 a 和 b 两个城市之间的距离。),(bad 编码与适应度函数 采用对 n 个城市访问次序的排列为 tsp 问题的编码。 适应度函数采用公式 （7-2） i d nl f i 5 . 76 )( 式中，l 为包含所有城市的最小正方形的边长；n 为城市数目；为实 i d 际排列下的路径长度。 交叉与变异算子 随机产生交叉点，采用两点交叉；变异采用一种为部分路径变异法。具体操 作为采用连续 n 次的调换方式，其中 n 的大小由遗传代数 k 决定，具体关系如 下： （7-)exp(/kmnn 3） 式中，n 为城市数目；m 为路径字段的数目； 为常数，表示 n 随 k 变化的 快慢程度。 免疫算子 免疫算子有两种类型，即全免疫和目标免疫。针对 tsp 问题，因为要找到应用 于整个抗原的疫苗是极为困难的，所以采用了目标免疫。 具体而言，在求解问题之前，先从每个城市点的周围各点中选取一个距离/路 径最近的点，以此作为算法执行过程中对该城市点进行目标免疫操作时所注入 的疫苗。每次遗传操作后，随机抽取一些个体注射疫苗，然后进行免疫检测， 即对接种了疫苗的个体进行检测：若适应度提高，则继续；反之，若其适应度 仍不如父代，说明在交叉变异的过程中出现了严重退化现象。这时，该个体将 被父代中所对应的个体取代。 仿真实验中，以著名的 75 城市的 tsp 问题为例，并取群体规模为 100；交 叉概率在 0.5-0.85，变异概率在 0.2-0.01，个体接种疫苗的概率 0.2-0.3，更 新疫苗的概率在 0.5-0.8，且随进化过程自行调整；另外 m 和 分别取 10 和 0.04，退火选择中的退火温度 t 按如下计算 （7-4）100),1ln( 0 0 t k t tk 式中，k 为进化代数。 在基本参数保持不变的前提下，分别应用标准遗传算法和免疫算法对 tsp 问 题进行求解。如果假定群体的最佳适应度值在 100 次连续迭代过程中不断被更 新，则认为该最佳适应度值所对应的个体为最佳个体。计算过程中，每隔 10 代 记录一次进化结果，则免疫算法在第 940 代首次出现最佳个体，而标准遗传算 17 法则在 3550 代才出现该最佳个体。为了更加清楚地表示两种算法中群体的整体 进化程度，分别将它们的子代群体中是最佳适应度值和相应的平均适应度值随 进化过程的变化对比情况如下图： 图 1 标准遗传算法计算曲线 图 2 免疫算法计算曲线 从图中可以看书免疫算法对提高算法是搜索效率，消除标准遗传算法在后 期的振荡现象具有明显效果，并在很多程度上加快了原算法的收敛速度。 可见，基于免疫原理实现的免疫算法在组合优化求解中显示出了强大的能 力，这些问题还包括二次分配问题、装箱问题等。例如，carlos 等分别将克隆 选择算法及免疫遗传算法加以扩充，获得针对车间调度的优化算法，这两种算 法的主要特点在于抗体形成功能、记忆细胞功能、抗体及抗原评价策略设计。 在大多数情况下，免疫算法取得了比现在启发式算法更好的求解结果，尤其在 解的效率方面，显示了免疫优化在智能优化领域具有更广阔的应用前景。另外， 基于免疫学原理开发的处理多目标优化的智能方法也相继出现。carlos 等从克 隆选择原理出发提出一种多目标免疫系统算法，该算法的特点是体现了 pareto 概念，并行处理思想及记忆细胞功能。 进化算法作为一种有向随机搜索的优化方法得到了广泛应用。然而在实际应 用中也存在一些需要改进之处：无法保证收敛到全局最优解，群体中最好个体 的丢失，进化过程的过早收敛等。将进化与免疫结合起来考虑，能得到更有效 的优化算法。 免疫系统通过细胞分裂和分化作用，可产生多样性的抗体来抵御各种抗原； 通过对抗体的抑制和促进作用，免疫系统能自我调节产生适当数量的必要个体， 18 在进化过程中最优个体将被大量繁殖。受该特性的启发，免疫算法把外来侵犯 的抗原和免疫产生的抗体分别与实际求解问题的目标函数以及问题的解相对应， 生成的抗体能有效地排除抗原，对与抗原亲和力高的抗体进行记忆促进快速求 解。免疫算法实质是具有免疫功能的遗传算法，它继承了遗传算法的部分特性， 增加了抗原识别、记忆功能和调节功能，并且具有遗传算法所不具的多样性维 持和记忆保持机制。它保留了遗传算法的全局搜索特性，克服遗传算法由于交 叉搜索而在局部搜索空间上效率较低的特点，在很大程度上避免未成熟收敛， 表现出较好的寻优效果。免疫算法是在个体基础上发展的，克服了标准遗传算 法收敛方向无法控制的缺陷。免疫算法和遗传算法相比，有很多相似和不同之 处： 免疫算法起源于宿主和宿原之间的内部竞争，其相互作用的环境既包括外部 也包括内部环境；而遗传算法起源于个体与自私基因之间的竞争。 在免疫算法中，基因组合是为了获得多样性，且在同一代个体进行进化，一 般不用交叉操作；而遗传算法后代个体通常是父代个体交叉的结果。 免疫算法和遗传算法都是启发随机搜索算法，都属于模拟自然现象的计算智 能方法。 免疫算法和遗传算法在形式上很相似，都采用重组变异等算子操作。遗传算 法以交叉为主，变异为辅；而免疫算法以交叉为辅，变异为主。 免疫算法和遗传算法一样，也存在难以确定控制参数和收敛速度慢的特点。 在已有的免疫模型和免疫算法中，免疫机制的引入非常有限，只是模拟了免疫 系统的很小部分功能。因此，ais 还具有很大的发展空间。将来应从不同的角 度对人体免疫系统所特有的信息处理机制进行建模，以期得到更广更深的研究 和应用。 8 8、优化算法的最新应用、优化算法的最新应用 通过阅读最近的报刊杂志，我对一些算法的具体实际应用也有了一定了解， 从而对一些算法的实质内容有了更进一步掌握，感受最大的是，优化算法永远 是最新的算法，结合实际