1.1 智能计算方法概述

在科学研究和工程技术中，许多问题最后都可以归结为求取最优解的问题，即最优化问题，如最优设计问题、最优控制问题等，这都是在众多方案中寻找最优方案，即在满足一定的约束条件下，寻找一组参数值，以使某些最优性度量得到满足，或者使系统的某些性能指标达到最大或最小。最优化问题是一个古老的问题，一直以来，人们对最优化问题进行了探讨和研究。早在17世纪，英国的Newton和德国的Leibnitz发明了蕴含优化内容的微积分，而法国数学家Cauchy首次采用最速梯度下降法解决无约束优化问题，后来针对约束优化问题又提出了Lagrange乘数法。最优化问题成为一门独立的学科是在20世纪40年代末，在1947年，Dantzig提出求解一般线性规划问题的单纯形以后，线性规划、整数规划、非线性规划、动态规划、多目标规划等许多分支理论研究迅速发展，实际应用日益广泛。在计算机应用的推动下，最优化理论与方法在科学研究和工程技术上得到了广泛的应用，成为一门十分活跃的科学。

对于最优化问题而言，目标函数和约束条件种类繁多：有的是线性的，有的是非线性的；有的是连续的，有的是离散的；有的是单峰值的，有的是多峰值的。随着研究的深入，人们逐渐认识到，在很多复杂的最优化问题中要想完全精确地求出最优解，既不可能，也不现实。

传统的优化方法如牛顿法、共轭梯度法、模式搜索法、单纯形法、Rosenbrock法和Powell法等，在面对某些大型问题时，需要遍历整个搜索空间，从而会产生搜索的组合爆炸，无法在多项式时间内完成搜索。如许多工程优化问题，由于其性质十分复杂，常常需要在复杂而庞大的搜索空间中寻找最优解或者准最优解，这样会导致在计算速度、收敛性和初值敏感性等方面都远不能满足要求，工程优化问题的求解表现得非常困难，因此，寻找高效的优化算法成为科学工作者的研究目标之一。

随着生物学中的进化论被广泛地应用于工程技术、人工智能等领域中，形成了一类新的进化计算模型，并在许多实际问题中得到了广泛应用。进化计算是由生物进化规律而演化出来的一种搜索和优化的计算方法，它包括遗传算法、进化策略、进化规划和遗传编程，也被称为广义遗传算法。

遗传算法是在二十世纪六七十年代由美国Michigan大学的J.H.Holland教授及其学生和同事在研究人工自适应系统中发展起来的一种随机搜索方法，Holland在A.S.Fraser和H.J.Bremermann等人研究的基础上提出了位串编码技术。这种编码技术既适用于变异操作，又适用于杂交操作，并且强调将杂交作为主要的遗传操作。随后，Holland将该算法用于自然和人工系统的自适应行为的研究中，并于1975年出版了开创性著作Adaptation in Natural and Artificial Systems。之后，Holland等人将该算法加以推广，应用到优化及机器学习等问题中，并正式定名为遗传算法（Genetic Algorithm，简称GA）。遗传算法的通用编码技术和简单有效的遗传操作为其广泛、成功的应用奠定了基础。1971年，Hollstein最先尝试将遗传算法应用于函数优化问题，用实验的方式研究了五种不同选择方法和八种交换策略。1975年，De Jong在其博士论文中针对各种函数优化问题设计了一系列遗传算法的执行策略和性能评价指标，对遗传算法性能进行了大量的分析。在Holand和De Jong的研究基础上，1989年，D.E.Goldberg对遗传算法进行了系统的阐述，奠定了现代遗传算法的基础。

为了提高遗传算法的性能，克服实际问题中遇到的困难，近年来，在算法设计与执行策略方面有了很大进展。另外，将遗传算法与其他优化算法相结合，利用启发信息或领域有关的知识也是目前改善遗传算法性能的常用手段，如与模拟退火算法、禁忌算法、局部搜索方法等算法的结合。同时，还有大量的改进的遗传算法，如混乱遗传算法、混合遗传算法、分岔遗传算法、统计遗传算法和广义遗传算法等。

遗传算法的理论分析主要集中在算法的收敛性分析、收敛速度的估计和计算效率分析等方面。遗传算法早期的基础理论主要是Holland提出的模式定理，以及由此所派生的积木块假设与隐含并行性分析，阐释遗传算法是如何有效地工作，由模式定理、积木块假设和隐含并行性一起构成了遗传算法的模式理论，该理论长期被接受为遗传算法的基本理论。特别注意，模式定理和积木块假设被用来解释算法的搜索机理，而隐含并行性被用来解释遗传算法的有效性。但是在模式理论中，除模式定理外，大多数理论没有得到严格的证明，因此也引起一些有关模式欺骗性的研究。国内徐宗本等人从算子的搜索能力角度详细地讨论了遗传算法的搜索机理，将遗传算法的收敛性分析所用的研究方法和数学工具大致分为四类，即马氏链模型、Vose-Liepins模型、公里化模型与连续（积分算子）模型。张文修和梁怡对遗传算法的数学基础进行了比较系统的论述，徐宗本、陈志平、章祥荪综述了遗传算法基础理论研究的最新进展。

二十世纪六十年代初，柏林工业大学的I.Rechenberg和H.P.Schwefel等在进行风洞实验时，由于设计中描述物体形状的参数难以用传统的方法进行优化，他们因此利用生物变异的思想来随机地改变参数值，并取得了较好的结果。随后，他们便对这种方法进行了深入的研究，最终发展成为演化计算的另一个分支——进化策略。进化策略主要用于求解多峰非线性函数的优化问题，随后，学者们根据算法的不同选择操作机制提出了多种进化策略。

进化规划是由美国学者L.J.Fogel根据求解预测问题提出来的一种有限状态机模型，基本思想是基于生物界的自然遗传和自然选择的生物进化原则，利用多点迭代算法来代替普通的单点迭代算法，并根据被正确预测的符号数来度量适应值。通过变异，父辈群体中的每个个体产生一个子代，父代和子代中最好的那一半被选择生存。L.J.Fogel提出的方法与遗传算法有许多共同之处，但是不像遗传算法那样注重父代与子代在遗传细节（基因及其遗传操作）上的联系，而把侧重点放在父代与子代表现行为的联系上。1992年，D.B.Fogel基于高斯分布变异，将进化规划扩展到求解实值问题。1999年，X.Yao等人利用柯西分布代替进化规划中的高斯分布变异，提出了快速进化规划，更有利于跳出局部最优点，收敛到全局最优点。2002年，M.Iwamatsu基于Lévy-type分布提出了推广进化规划。理论上，柯西分布和高斯分布是Lévy-type分布的两种特殊情况，算法能够更好地收敛到全局最优解。

类似于遗传算法，进化策略和进化规划也是近年来极其热门的研究方向，特别是二十世纪九十年代以来，进化策略和进化规划也逐步被学术界重视，并开始用于解决一些实际问题，大体研究包括如下几方面：（1）有关算法的数学基础，大量的文章对算法的收敛性进行了分析，同时在收敛速度及算法的计算复杂性等方面展开了研究。（2）有关算法与其他技术的比较与融合及算法的改进。（3）有关算法的并行化实现与相关理论基础的研究。

这几种方法在实现手段上各有特点，但又各不相同，它们所遵循的进化原则是一致的。它们主要是模仿生物学中进化和遗传过程，遵循达尔文“适者生存、优胜劣汰”的竞争原则，从一组随机生成的初始可行解群体出发，借助复制、重组及突变等遗传操作，在搜索过程中自动获取并积累解空间的有关知识，逐步向问题的最优解或者准最优解逼近。因此，作为宏观意义下的仿生算法，它们的本质特征是以群体的方法进行自适应搜索，并且充分利用交叉、变异和选择等运算策略，有效地避免局部最优解，降低求解目标函数性能的限制，减少了人机交互的依赖。正是因为它们所具有的独特优势，所以它们是一类可用于复杂系统优化计算的鲁棒搜索算法，广泛应用于各领域。进化计算因其算法简单，在组合优化问题和复杂的函数优化问题上有很强的计算能力，近年来得到了国际学术界普遍重视。与传统的算法相比，最主要的差别在于进化计算具有智能性和并行性特征，采用进化计算方法求解优化问题有如下优势：（1）基于群体操作，优化结果基本不依赖初值的选取；（2）对搜索空间和被优化函数的性质没有特殊的要求；（3）计算相对简单，易于实现。但进化计算仍有一些有待研究和改进的地方，如其理论不完善（参数的设定、非概率收敛性证明等）。另外，其收敛速度慢、早熟收敛也是待攻克的难题。

近几十年来，随着免疫学的不断发展，人们逐渐对生物免疫机理有了更深刻的认识，免疫系统的众多特性引起了人们的注意，人们开始模仿免疫系统的一些行为特性，并将其应用于其他领域的研究，这些受免疫系统启发而建立的人工系统被称为人工免疫系统（Artificial Immune System，AIS）。于是，把IA和EA结合起来的免疫进化计算也越来越受到人们的重视。

Mori等人提出一种模仿免疫系统的优化方法，结合遗传算法来解决多峰值优化问题。其主要思路是将抗原对应于目标函数和约束条件，将抗体对应于搜索空间的解，用抗原和抗体之间的亲和力来对解进行评价和选择。在该算法中，使用了传统遗传算法的交叉和变异算子生成新个体以保持抗体的多样性，当某种抗体的数量大于某个阈值时，产生抗体的细胞将分化为抑制性细胞和记忆细胞。抑制性细胞抑制这种抗体的进一步增加，记忆细胞则将这种抗体对应的解记为局部最优解。该算法已经应用于一个复杂生产过程自适应调度问题的求解。

Tazawa等人提出了一种将免疫系统原理和遗传算法结合起来的免疫遗传算法（IGA），该算法的核心思想是将总的种群划分为一系列的子群，对每一个子群进行交叉和变异运算，然后根据亲和力选择并调整各子群的大小。该调整机制类似于生物免疫网络的调整机制，将该方法用于VLSI电路布线设计问题，结果证明该散法优于遗传算法。

Chun等人在利用遗传算法试图解决电磁器件的形态优化问题时，为提高算法的整体搜索能力，在借鉴自然免疫形态中的免疫应答机制和细胞个体之间离散度与亲和度等机理的基础上提出了一种新的免疫遗传算法。该算法将抗原作为目标函数，将抗体作为求解结果，将抗原和抗体之间亲和度作为解答的联合强度。

在国内，中国科技大学的刘克胜等人基于免疫学的细胞克隆选择学说和Jerne的网络调节理论，设计出一种人工免疫系统模型及算法，并将其应用于自主式移动机器人的行为控制研究，这属于早期国内有关网络模型和应用的研究。华中科技大学的罗攀人根据Jerne的免疫网络模型提出了一种面向对象的人工免疫系统模型，并将该模型应用于自主车辆的多传感器信息融合中。

王磊、焦李成等人提出了一系列新的算法——基于免疫机制的进化算法，并且证明了这些算法是收敛的。所提出的算法的核心在于免疫算子的构造，而免疫算子又是通过接种疫苗和免疫选择两个步骤完成的。免疫算子的作用是在解决工程实践中一些难度较大的问题时，将有关先验知识和背景理论与已有的一些智能算法有机地结合起来，以较好地解决原进化算法中出现的退化问题，从而提高了算法的整体性能。

杜海峰等人借助生物免疫学的克隆选择机理，构造了一种抗体修正克隆算子，并形成相应的人工免疫抗体修正克隆算法。相关实验表明，该算法能成功解决类似0/1背包问题这样的组合优化问题，而且性能优于相应的进化算法。刘若辰、杜海峰和焦李成则基于细胞克隆选择学说的克隆算子，将其应用于进化策略，并利用柯西变异替代传统进化策略中的高斯变异，提出了改进的进化策略算法——基于柯西变异的免疫单克隆策略算法，并利用Markov链的有关性质，证明了该算法的收敛性。理论分析和仿真实验表明，与传统的进化策略算法及免疫克隆算法相比，基于柯西变异的免疫单克隆策略算法不仅有效克服了早熟问题，保持了解的多样性，而且收敛速度比前两者都快。

杨孔雨和王秀峰集成免疫记忆和免疫调节两种机制，通过对免疫进化机制进行深入系统的分析，结合免疫系统的动力学模型，基于免疫细胞在自我进化中的亲和度成熟机理，提出了一种全新的多模态免疫进化算法（MIEA），即通过智能模拟高亲和度抗体的正选择、记忆细胞产生、免疫细胞超变异和抗体相似性抑制等进化机制，最终找出多模态问题的所有最优解，或一个最优解和尽可能多的局部优化解。

庄健和王孙安设计了基于人工免疫网络理论的移动机器人（AMR）的路径规划算法，此算法在仿真实验中显示了高度的智能性，实验表明该算法能够完成系统所要求的任务，并且算法柔性好，能够适应不同规划环境。通过对比实验，还证明了该算法较其他的规划算法具有更好的智能性，并采用马尔可夫链从数学上证明了该算法的收敛性。

浙江大学的罗小平借鉴免疫系统的机理提出了一种免疫遗传算法，该算法包括隔离小生境、免疫重组、免疫变异、免疫网络的浓度控制、免疫代谢、混沌增殖和免疫记忆等算子，并且应用有限状态Markov链的理论对算法的全局收敛性进行了证明。该算法结合了免疫网络理论和隔离小生境遗传算法，具有防止早熟的能力。目前，该算法已经成功地应用于冗余机器人的轨迹规划和连续搅拌反应釜的控制。

二十世纪五十年代以来，以生物特性为基础的进化算法的发展及其在最优化领域中的成功应用，进一步激发了研究人员对生物群落行为及生物社会性的研究热情，从而出现了基于群智能（Swarm Intelligence）的优化理论。群智能是一种新兴的进化计算技术，出现于二十世纪九十年代初，它是以生物社会系统（Biology System）为依托的，模拟由简单个体组成的群落与环境及个体之间的互动行为。目前，群智能理论研究领域有两种主要的算法：蚁群算法和粒子群算法。

蚁群算法是对蚂蚁群落觅食过程的模拟，是由意大利学者Dorigo等人于1991年提出的，蚁群算法具有分布计算、信息正反馈和启发式搜索的特征，最初用于求解旅行商问题，此后在多种组合优化问题中获得了广泛的成功应用，并已被扩展用于连续时间系统的优化。但蚁群算法在解决连续优化问题方面的优势不强，其最成功的应用还是组合优化问题：一类是静态组合优化问题，其典型代表有TSP、二次分配QAP、图着色问题、车间调度问题、车辆路由问题和大规模集成电路设计问题等；另一类是动态组合优化问题，例如通信网络中的路由问题及负载平衡等问题。目前，对多目标蚁群算法的研究还只局限于组合优化问题，理论研究不够深入，同时在如何扩展其应用领域，如何将其应用于函数优化问题，以及如何处理高维优化问题等方面还有待深入。

粒子群优化（PSO）算法是一种随机全局搜索方法，它从鸟群觅食的社会行为中得到启发，于1995年由美国社会心理学家Kennedy和Eberhart博士首次提出，主要用于处理连续空间中的函数优化问题。在粒子群算法中，表示问题潜在解的集合被称为种群，初始种群通常是随机产生的、解空间上的均匀分布，然后种群在解空间中通过模拟鸟群觅食的聚集过程进行迭代搜索。在搜索过程中，所有粒子之间进行全局信息的交换，通过这种信息交换，每个粒子能共享其他粒子当前的搜索结果。由于其基本思想简单直观，容易实现，PSO算法自提出以来一直受到研究者的关注，并被扩展到广泛的领域，包括多目标优化问题、最小-最大问题、整数规划问题及大量的工程应用问题等。但是，PSO算法的发展历史尚短，在理论基础与应用推广方面还存在不少问题。譬如，当PSO算法应用于复杂函数优化或高维、超高维复杂问题优化时，往往会遇到早熟收敛的问题，也就是种群在还没有找到全局最优点时就已经聚集到一点停滞不动。早熟收敛不能保证算法收敛到全局极小点，这是由于PSO算法早期收敛速度较快，但到寻优的后期，其结果改进则不甚理想，即缺乏有效的机制使算法逃离极小点。因而，算法早熟收敛研究也是一个值得研究的问题。

群智能方法具有并行性高、鲁棒性强、扩展性好等优点，而且对问题定义的连续性也无特殊要求，相比于进化算法，群智能方法易于实现，算法流程简单，需要调整的参数少，目前已经成为越来越多研究者关注的焦点，并且在数据分类、数据聚类、模式识别、电信QoS管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持及仿真和系统辨识等领域得到了成功应用。

人类在发掘生物进化机制，进行“仿生”研究的同时，也受物理学的启发而萌发了“拟物”探索。二者相互渗透、取长补短，产生了许多成功的理论，模拟退火算法就是由物理学推动发展的动力系统得到生物进化思想完善的产物。量子力学是二十世纪最惊心动魄的发现之一，它为信息科学在二十一世纪的发展提供了新的原理和方法。由于量子硬件实现的难度较大，量子计算机还不能在短期内实现，但是它对人类思维和学习方法所带来的革命性作用及量子计算所特有的性质对经典理论的冲击，都是不可忽略的。我们能否将量子理论运用到经典的算法中，通过对经典的算法做一些调整，使其具有量子理论的优点，从而进行一些类量子的计算来实现更为有效的计算呢？目前还没有证据证明在生物细胞的繁殖过程中，染色体与染色体之间的相互作用存在量子效应，但是，从整个生物界的发展演化看，生物物种存在多样性，其演化存在混沌和并行的特点，这些特点与量子的特征是相似的。这一相似性促使人们尝试将量子理论与进化算法进行结合，以实现更加高效的、以量子计算的形式工作的进化算法。

量子进化算法领域的研究主要集中在两类模型上：一类是基于量子多宇宙特征的多宇宙量子衍生遗传算法（Multiuniverse Quantum Inspired Genetic Algorithm），另一类是基于量子比特和量子态叠加特性的遗传量子算法（Genetic Quantum Algorithm，GQA）。量子多宇宙理论源于对托马斯·杨著名的双缝干涉实验的解释。量子多宇宙理论认为，任何量子系统同时存在于多个并行的宇宙（Universe）中，在不同的宇宙中系统呈不同的运动状态，宇宙之间存在相互影响（相当于量子纠缠），其运动结果也不相同，一旦对它实施测量，它将坍塌到一个宇宙，并得到一个确定解。Ajit Narayanan和Mark Moore将量子多宇宙的概念引入遗传算法，提出了一个量子衍生遗传算法（Quantum Inspired Genetic Algorithms，QIGA），并用它求解TSP问题。基于多宇宙概念的量子衍生遗传算法从其算法机理上看属于隔离小生境遗传算法，利用多个种群的并行搜索，增大搜索的范围，利用种群之间的联合交叉实现种群之间信息的交流，将多个种群各自分散的搜索联系起来，以从整体上提高算法搜索的效率。然而，基于量子多宇宙概念的遗传算法基本上还是属于常规遗传算法的范畴，其多个宇宙是通过分别产生多个种群得以实现的，在计算上并没有用到量子计算机的叠加态并行处理，因而距离真正的量子算法还有很大的距离。

K.H.Han等人提出了一种遗传量子算法，他们将量子的态矢量表达引入遗传编码，利用量子旋转门实现染色体基因的调整，使该算法将来在量子计算机上执行成为可能，给出了一个基因调整策略，并以此策略实现了0/1背包问题的求解，且求解的结果要优于传统遗传算法。但该算法主要用来解决0/1背包问题，编码方案和量子旋转门的演化策略不具有通用性，尤其是由于所有个体都向一个目标演化，如果没有交叉和变异操作，极有可能陷入局部最优。

中国科技大学的庄镇泉教授和李斌博士在该算法基础上提出了基于量子计算模式的量子遗传算法（Quantum Genetic Algorithm，QGA），并首次提出了量子交叉和量子变异的新概念及其实现方法。通过典型函数优化问题的求解证明了该算法的有效性，并将量子计算的概念和方法应用于数据挖掘，实现了基于量子遗传算法的时间序列频繁结构模式的发掘，取得了良好的实验结果。杨俊安博士和庄镇泉教授又提出了一系列改进的量子遗传算法（Novel Quantum Genetic Algorithm，NQGA），并应用于盲源分离，效果显著。西安电子科技大学智能信息处理研究所的杨淑媛和焦李成教授提出了一种新的理论框架——量子进化理论及其学习算法，他们不仅在理论上证明了这一理论框架的全局收敛性，而且用仿真计算也证实了此算法的优越性。

李映博士和焦李成教授将之前提出的免疫思想引入到量子进化算法中，提出了一种新型的进化算法——免疫量子进化算法（Immune Quantum Evolutionary Algorithm，IQEA）。免疫量子进化算法在保留原量子进化算法优良特性的前提下，力图有选择、有目的地利用待求问题中的一些特征信息或先验知识，抑制或避免求解过程中的一些重复或无效的工作，以提高算法的整体性能。

游晓明博士结合免疫系统的动力学模型及免疫细胞在自我进化中的克隆选择和亲和度成熟机理，提出了一种基于免疫算子的量子进化算法（MQEA），通过抗体的克隆选择、记忆细胞产生、免疫细胞自适应交叉变异、抗体的促进与抑制和抗体相似性抑制等进化机制，最终可找出最优解。不仅用Markov随机过程理论证明了该进化算法的收敛性，而且用仿真实验证明了该进化算法的优越性。随后在此基础上提出了多宇宙并行免疫量子进化算法（MPMQEA），MPMQEA采用多宇宙并行结构，不同的宇宙向着各自的目标演化，宇宙之间采用基于学习的移民和模拟量子纠缠的交互策略交换信息，具有比MQEA更快的收敛速度。