【学术论文】自然计算研究进展

第6卷第6期 智能系统学报 Vol.6 No.6 2011年12月 CAAI Transactions on Intelligent Systems Dec.2011 doi:10.3969/j.issn.16734785.2011.06.011 自然计算研究进展 莫宏伟 (哈尔滨工程大学自动化学院，黑龙江哈尔滨150001) 摘要：自然计算是计算机科学与人工智能领域中重要的研究内容之一经过几十年的发展，已经逐渐发展成为涉 及多个学科的新兴交叉研究领域，其研究目的在于从自然界中寻求解决人类所面临的复杂问题的方法.早期自然计 算主要集中在进化计算、人工神经网络、模糊系统3个主要方面，近20年研究人员提出群体智能、人工免疫系统 DN计算等新方法.对群体智能等新方法的研究现状、发展趋势、存在的问题进行分析，指出未来发展重点和方向. 关键词：自然计算；生物启发的计算；群智能：分子计算 中图分类号：TP3.05文献标志码：A文章编号：16734785(2011)060544-12 Research advance on natural computing MO Hongwei College of Automation,Harbin Engineering University,Harbin 150001,China) Abstract:Natural computing is one of the important research areas in the field of computer science and artificial in- telligence.It is a new research field which involves many disciplines following development spanning several dec- ades.The aim of natural computing is to seek for the solution to difficult problems faced by humans from nature. Natural computing focused on evolution computing,artificial neural networks,and fuzzy systems in its early days. Over the last two decades,several new natural computing methods,such as swarm intelligence,artificial immune systems,and DNA computing have been proposed.In this paper,it presents research situations,development tendencies,and other matters surrounding new methods such as swarm intelligence were analyzed.Areas of future emphasis and direction in development were also pointed out. Keywords:natural computing;biology-inspired computing;swarm intelligence;molecular computing 自然计算是自然解决各种问题的理论.遗传算。一种求解多目标优化的免疫算法一非支配邻域免 法、人工神经网络、模糊系统等经典方法从诞生至今 疫算法们，是该期刊创刊以来国内学者在该刊物发 已经各自演变成相对独立的人工智能研究领域，保 表的第2篇论文.唐珂、王勇等一批国内青年学者在 持着长久不衰的生命力，半个多世纪以来不断得到进化计算研究领域发表了一批高水平论文24，取 改进，衍生出众多新方法.特别是最近20余年，有关 得国际瞩目的成果.有关多目标进化算法的研究也 进化计算的学术论文逐年增加，主要发表在《EEE 渐成体系56.近年来，进化计算的研究已相对成 Transactions on Evolutionary Computation)》和《Evolu- 熟，基本算法设计、基本理论研究方面趋于完善，一 tionary Computation》等杂志以及在CEC、GECCO、 些基于演化原理的、为更好解决实际问题的算法，如 PPSN、FOGA和EuroGP等国际学术会议上.焦李成 多目标演化算法、协同演化算法、约束优化演化算法 等人20O8年在《Evolutionary Computation》,上提出了 以及将演化计算与神经网络等方法、技术相结合引 起了研究者们广泛的兴趣). 收稿日期：20110401. 基金项目：国家自然科学基金资助项目(61075113)：中央高校基本科研 人工神经网络近些年在理论和应用2个方面都 业务自由探家基金资助项目(H0110441). 取得了丰硕成果.例如在神经网络与认知科学的结 通信作者：莫宏伟.E-mail:honwei2004@126.com. 合、神经网络与量子理论的结合、神经网络与进化算

国家自然科学基金资助项目(61075113)；中央高校基本科研 业务自由探索基金资助项目（HEUCF110441）

第6期 莫宏伟：自然计算研究进展 ·545 法的结合、神经网络与生物医学的结合、神经网络与 BB0)[27]、人群搜索算法[]、萤火虫算法9]、野草入 灰色系统的结合以及与其他多种智能技术结合的各 侵优化算法∞、量子群智能算法、生态系统算 种混合神经网络.代表性研究成果有：脉冲耦合神经 法「3]、化学计算[8]等新方法不断涌现，使自然计算 网络8]、神经网络集成9]等.应用技术研究不断深 家族不断壮大. 入，涉及民用和军用领域[10」 上述所有自然启发的计算可以分成：生物启发 经过40多年的发展，模糊集已经成为一个理论 的计算[3]，包括受各种生物系统启发而设计的多种 基础雄厚、学术影响深远的交叉学科.理论研究方 算法；受物理现象或规律启发的计算，包括模拟退火 面，模糊分析学、模糊代数学和模糊拓扑学等分支成 算法3、量子计算36、磁场优化算法1等；化学启 果丰硕.应用研究方面，模糊控制、模糊聚类分析、模 发的计算是利用化学反应过程实现问题求解.如果 糊模式识别、模糊神经网络和模糊专家系统等发展 从广义的角度把人类社会及思维看作是自然界生物 迅速.国际模糊集理论研究，主要集中在模糊集理 的一部分，则受人类社会启发的计算也应该看作是 论、模糊集以及与其他理论的交叉融合技术等方 自然计算的一部分，比如智能主体、形式语言等.这 面7， 3种类型的计算的共同特征具有较高的智能性， 在上述3种经典自然启发的计算算法基础上， 自然启发的计算实际上是自然计算的一部分 从20世纪90年代起，基本每10年左右就会涌现一 根据文献[38]的观点，自然计算内容扩展如图1所 批新的自然计算方法，20世纪90年代初代表性的 示.主要包括3方面：1)受自然启发，用现代计算机 有蚁群算法(ant colony optimization,AC0)[2]、粒 高级编程语言来实现，应用范围广泛；2)利用现代 子群算法(partice war optimization,PS0)【B)、免 计算机建立自然系统的模型和仿真系统，研究自然 疫算法4、文化算法16、DNA计算u、细胞膜计 界及生物本身，如人工生命、人工植物；3)利用生物 算1s1o]、Memetic算法o),前2种算法又形成一个新 或物理、化学性能或机制设计能够突破冯氏计算机 的自然计算分支—群体智能，其中粒子群算法影 结构限制的装置、设备，如分子计算机、生物计算机、 响最大[21).2000年以后的10年，人工免疫系统发展 量子计算机、光子计算机等.本文限于篇幅，不能一 迅速a1,这一时期，人工鱼群算法(artificial fish 一阐述所有自然计算内容，只以生物启发的计算中 swarm optimization,AFS0)[2s4、细菌觅食算法 相对更为活跃的群体智能以及效率更高的分子计算 (bacteria algorithm,BA）)I2s]、蜂群算法s]、生物地理 为重点，阐述自然计算发展的趋势、特点以及存在的 优化算法(biogeography-based optimization algorithm, 问题，并对未来的发展方向进行探讨. 自然计算 白然启发的计算 自然仿真或模拟 利用白然物质计算 生物启发的计算 人工生命 DNA分子 遗传算法 人工世界 莎 菌 人工神经网路 人工社会 细 胞 模制系统 人工动物 行机分子 人工免疫系统 人工植物 化学反应 群智能 量 子 物理启发的计算 电 化学启发的计算 光 子 补会启发的计算 图1自然计算的内容 Fig.1 Content of natural computing

·546 智能系统学报 第6卷 1生物启发的计算 研究趋药性算法的先驱是Brenermann及其同 事3].基本BCA依赖于单个细菌的运动行为，它不 生物启发的计算的研究有双重目的：可以解决 断地感受它周围的环境变化并且只利用它过去的经 生物学以外的工程和科学问题；反过来，这些方法又 验来寻找最优点，具有较强的简单性、鲁棒性.但基 能提供新的工具和技术用于研究解决生物学本身的 本BCA性能只和基本的遗传算法相当，在某些情况 问题， 下性能还要比一些改进的遗传算法差.李威武等在 1.1群体智能 BCA基础上提出了BCC算法2，这种算法将群体 群体智能(swarm intelligence,SI)是一种模仿 智能的思想引入到BCA,使用多条细菌组成的菌群 自然界动物昆虫觅食筑巢行为的计算技术，研究由 进行寻优.BCC算法虽然提高了BCA的优化能力， 若干简单个体组成的分散系统的集体行为，其中每 但必须使用大量细菌才能使算法的优化能力有所 个个体与其他个体以及环境都有相互作用.。 高，文献[53]借鉴了微遗传算法的思想，将之应用 Bonabeau定义群智能为：任何受到社会昆虫群体和 于菌群算法，提出了一种微细菌群趋药性(M-BCC) 其他动物社会集体行为启发所设计的算法或者分布 算法.在M-BCC算法中有2个菌群，一个菌群是寻 式问题求解设备9].群智能算法着眼于自然界中的 优菌群，另一个菌群是库存菌群.M-BCC算法在寻 生物社会群落，比如蚁群、鸟群、乃至人群等社会群 优能力方面要优于BCC算法.文献[54-55]分别对 体行为.目前SI包括粒子群优化算法、蚁群算法、人 该种算法进行了简单综述和改进研究， 工鱼群算法、蜂群算法、细菌算法以及生物地理优化 1.1.2蜂群算法 算法等。 蜂群也是一种典型的群体昆虫，与其他社会昆 1.1.1细菌优化算法 虫有类似的结构.一些研究人员提出模拟蜜蜂群体 细菌为了觅食采取必要的行动使每单位时间摄 的特殊智能行为的模型，应用于组合优化问 取的能量最大化，自然界中的细菌觅食策略行为实 题[6]，Tereshko把蜂群看成动态系统，搜集来自环 际上可看作是一种优化策略，隐含的思想可以用于 境的信息，根据这些信息调节其行为.Tereshko 解决实际优化问题.在细菌群体觅食行为中，具有一 和Loengarov研究了一种基于蜜蜂觅食思想的机器 种趋药性，这种性质促使细菌试图运动到营养浓度 人群体协同机制.实验显示类昆虫机器人在实际机 高的地方以避免有害物质并从经过的物质中搜索路 器人任务中是成功的.他们开发了觅食选择的最小 径.基于细菌觅食和趋药性概念，Muller和Passino 模型，导致集体智能的涌现.该系统由食物源、工蚁 分别提出细菌觅食优化算法(bacteria foraging opti- 和非工蚁3个基本组成，定义了2个行为模式：恢复 mization algorithm,BFOA)[o]和细菌趋药性算法 食物源和放弃食物源[7s8].Tereshko还提出在求解 (bacterial chemotaxis algorithm,BCA)[lT.这2个算 复杂交通和运输问题采用群智能开发人工系 法虽然在实现步骤上有很大不同，但在模拟生物机 统90]以及蜂群优化元启发算法，能求解组合优化 制上存在交叉.文献[42]提出变化环境细菌觅食方 问题以及不确定组合问题611.Dias等人引入一个 法，利用基于个体的模型方法模拟细菌活动和细菌 新的智能方法或者元启发方法，称为蜂群优化(bees 群体的进化；文献[43]提出基于BFOA独立主元素 swarm optimization,BS0),并用它解决最大权满足 分析，该算法产生的均方差性能比约束遗传算法的 问题(max-sat)[.类似地，Benatchba等人引入基于 ICA更好；文献[44]提出经典梯度下降搜索模式下 蜜蜂繁殖过程的元启发解决3-sat问题[a].Wedde 模拟趋药性的数学分析；文献[45]提出GA和 等人受到蜂蜜过程、交流和评价方法的启发提出一 BFOA混合，提出的算法在几个数值测试上和PID 个新的路径算法，称为BeeHive61.在该算法中，蜜 控制器设计上超过GA和BFOA;文献[46]提出一 蜂主体通过称为觅食区的网络区域巡游，在它们的 个模糊参考模式，选择最优趋药步骤，得到模糊细菌 路径上，网络状态的信息不断分配，用于更新局部路 聚集BF,该方法不适合优化测试函数：文献[47] 由表 将BFOA与PSO混合的细菌群体优化，统计意义上 上述都是组合优化问题.有3个连续优化算法， 比经典方法好.BFOA已经成功用于控制器设 基于蜂群算法的智能性s6].Yang6s]开发了虚拟蜜 计】、股票预测9、电力系统问题0，本文作者将 蜂算法(VBA)优化二维数值函数，算法产生一群虚 BFOA优化K-means聚类中心，得到细菌觅食聚类 拟蜜蜂，通过这些蜜蜂的相互作用强度获得问题的 算法并用于图像分割，取得较好效果51 解.Pham等[66提出应用几个控制参数的蜜蜂算法

第6期 莫宏伟：自然计算研究进展 ·547 对于优化多变量和多模态函数，Karaboga1提出可 法结合的新算法.文献[87]采用群计算技术处理图 人工蜂群算法(ABC),Basturk和Karaboga在有限测 像分类，文中使用一个新的群数据聚类方法，该方法 试问题上比较了ABC和GA[s]、PSO和PS-EA[9]以 基于人工蜜蜂花簇授粉进行卫星图像像素的聚类， 及DE、PS0和EA的性能o.ABC算法已经应用到 使用该方法获得了高精确度卫星图像分类.文献 约束优化问题、神经网络训练)、设计R滤 [88]利用该算法解决经济负载分配问题.本文作者 波器41和叶约束最小生成树问题51.文献[76]将 将BBO算法用于求解TSP问题，通过多个旅行商 ABC算法与遗传算法和其他群智能算法在50个不 (TSP)经典测试问题证明生物地理学思想是一种求 同类型函数问题上进行了大规模全面比较和分析， 解TSP问题新的有效手段[] 结果显示ABC算法性能好于或者近似其他群智能 1.1.4群体智能发展问题 算法，优势在于算法控制参数较少， 自然计算的启发源于微小的细菌、活跃的蜜蜂， 1.1.3生物地理优化算法 发展到大规模动物迁移，并已经开发出相应的有效 生物地理优化算法(biogeography-based optimi- 算法.上述多种群体智能算法在理论和应用方面发 zation,BB0)是美国学者Simon于2008年正式提出 展程度不一，但都远未达到成熟阶段.所有群体智能 的一种新型优化算法，是一种新的生物地理学启发 算法的一个共同特征是候选解以群体形式向着搜索 算法，用以解决全局最优解.它主要通过物种的 空间中更好的解区域移动，共同挑战是如何结合生 迁移算子来实现信息资源共享，BB0是在生物地理 物群智能以加速向最优解收敛，避免局部最优解，这 学的数学模型基础上实现的一种全局性优化方法. 也是所有自然计算优化求解的共性问题.群体智能 文献[27]介绍了如何基于生物地理学的基本 发展主要有以下几个方面的问题值得关注： 理论设计该优化算法，给出了算法的基本理论框架 1)观察和发现生物群体中新的行为模式，借鉴 和步骤.在所给出的8个典型函数和一个飞机发动 生物学成果进行建模和分析，以进一步改进现有算 机传感器选择的实际问题上进行的测试表明，该算 法和开发新的SI算法.比如生物学上对一种趋磁性 法虽然结构比较简单，但在多数测试问题上表现均 细菌的研究的关注[0] 优于现有的遗传算法、粒子群算法、蚁群算法等其他 2)数学理论基础相对薄弱，缺乏具备普遍意义 7个常用的优化算法.文献[77]提出了对立生物地 的理论性分析！ 理学优化算法.马海平]推广了生物地理理论中的 3)充分发挥其固有的强并行性，与最新计算软硬 物种平衡数，探讨了6种不同的迁移模型，通过实验 件技术尤其是嵌入式系统相结合，服务于实际应用 表明正弦迁移曲线性能最优.龚文银等[]扩展了原 4)同其他的进化算法一样，群体智能也是概率算 有的BB0,提出一种实数编码的BB0方法，同时引 法，对于解决实际问题而言存在可靠性方面的风险， 进邻域搜索算子，杜大伟等[0]融合进化策略，同时 5)学习、推理、知识处理在群体智能中的应用 提出一种设定阈值的移民拒绝方法.龚文银等还将 研究 BB0融入DE,提出一种混合的差异进化方法，该方 1.2分子计算 法有效地结合了DE的探索能力和BBO的开采能 分子计算是一个跨学科的研究领域.这里的计 力，另外也研究了种群的规模、维数、不同的变异方 算不只局限于狭义的算法，而是泛指在自然界中物 案和自适应控制参数对该混合方法的影响[81].马海 理、化学以及生物分子水平上研究新的计算模式和 平[2推广了生物地理理论中的物种平衡数，讨论了 方法.分子计算就是试图研究分子在信息处理方面 4种不同的迁移模型，通过实验表明线性迁移率比 的计算能力.分子计算思想直到1994年Adleman对 常数迁移率的优化效果更好.Dan Simon对BB0进 一般目的的DNA分子计算机方面取得突破性进 行了简化，提出了3种简化的BB0算法理论模型， 展1，才被证实. 对群体进行概率分析，证明了算法在不同简化形式 1.2.1DNA计算 下得到最优解所需要的代数和期望的改进量，而且 DNA计算的研究内容包括：DNA计算的通用模 这些量都与群体数量相关[8]，发展了BB0的马尔 型、DNA链大规模并行性计算模型、不同自然发生 可夫分析，对比了BBO和简单遗传算法的马尔可夫 结构的DNA计算模型（尤其是循环和其他非线性 分析，对精英策略的选择也进行了讨论[4].在BB0 结构)、在细胞层次上利用自然发生的生物操作的 应用方面，文献[85]提出利用BB0进行天线阵列分 分子计算模型[] 析的算法.文献[86]则提出了量子与生物地理学算 DNA计算模型主要划分为非限制性模型和限制

·548 智能系统学报 第6卷 型模型.非限制模型的操作对象是单个DNA串（基 身结构适应自身功能.折叠机制确保一个蛋白质分 因)，而限制型模型的操作对象是DNA串的状态集合 子的独特性质，这个独特性编码表现在蛋白质链灵 (染色体).许多研究学者不仅研究了各种DNA算法来 活的连接变化中.这些特征确保一个蛋白质分子的 提高DNA的计算能力和降低其复杂性，而且也提出了 折叠更迅速无误，以提供具有必要的功能和灵活性 与电子计算模型对应的分子模型的DNA算法，如DNA 的蛋白质。 加、DNA算术与逻辑运算、分子矩阵乘和因式分解法 蛋白质能选择性识别合适的模式或者拒绝不合 等.利用DNA的分子计算的优点是每个DNA分子可 适的模式，这种识别能力能够改变其空间结构，这个 以作为一个单独的处理器功能，这意味着极大加快了 现象称为变构效应.由于变构效应，蛋白质有时能结 解决复杂问题的速度9则 合以前不能结合的一个蛋白质或者另一个分子，这 DNA分子计算的优势还在于其远远超越电子 样能够结合新蛋白质形成所谓的分子环或免疫网 计算的存储容量以及极小的能量消耗。 络5] 文献[92]提出一种DNA计算启发计算模型， 目前，关于蛋白质计算的研究并不多，有许多空 可以在液体环境中漂浮的双链结构上进行计算，通 白点值得挖掘，像DNA计算等其他分子计算一样， 过类似DNA计算的重写规则实现，并提出利用膜计 有希望成为未来分子计算的研究热点.文献[96]利 算作为实现这些规则的生物技术手段， 用概率转换树对模拟蛋白质计算进行了研究，提出 DNA计算主要问题集中在DNA计算的形式模型 了一种新的通用的计算技术，基于蛋白质相互作用 复杂问题求解、DNA的计算复杂性、DNA计算机实现 的仿真，设计大规模并行分布式概率计算方法，并用 (比如如何降低试管操作的复杂性)等多方面.可以借 于特征图象识别.文献[97]将DNA计算与蛋白质 用DNA机制与自然启发的计算结合或融合，但如果 特性结合起来，证明蛋白质可以表示DNA计算所得 DNA算法只在电子计算机上实现，显然失去了开发这 到的解 种计算模式的生物优势和意义. 1.2.3分子计算现状 1.2.2从计算观点看蛋白质 自然界的生命系统层次简单地分为分子、细胞、 蛋白质作为神经元的受体和神经元介质控制大 组织（尤其是脑）、个体、社会和生态系统，每个层次 脑的电子活动，也是免疫系统的主要元素.从计算观 都是计算生命科学研究的主题和目标.分子计算也 点看，现有所有的生物系统的信息基础由统一的编 属于“计算生命科学”这个研究领域的一部分.计算 码 一个缩氨酸表组成，其中的词就是蛋白质分 生命科学的目的是从计算理论观点理解生命系统， 子.在计算机术语中，可以说基因编码是软件（指导 并应用这个研究结果到生物工程.这里，分子计算考 或者编程)，而蛋白质看作硬件（执行程序的生物物 虑如何建立人工系统，研究生命系统的最基本层次， 理装置)「31 从计算角度，分子计算重点在于研究分子的计 虽然基因编码蛋白质非常简单，但这些生物物 算能力，尤其是生物分子的计算能力，以便利用其实 理机制不容易发现.存储遗传编码的DNA双螺旋结 现信息处理，希望信息处理运算更快、更小（纳米尺 构的空间结构是由同一平面中非常精确的分子形态 度)，以及提高成本、效率（节省能量），也希望出现 之间的弱相互作用形成的.空间结构是生物分子中 新的信息处理计算模型，基于新的计算模型设计不 几何对应的最显著的例子之一.在蛋白质情况，这个 同类型的计算机.分子计算考虑的不仅是计算机也 层次的理解还没有达到.但如下原理是显然的4： 包含其他应用，如纳米机器、微机械、生物系统中的 1)蛋白质的空间配置由其氨基酸（字母）线性序列 信息处理等.复杂纳米机构的自治信息也被认为是 (词)组成：2)空间配置决定任何蛋白质的功能 一种计算形式，这种分子自组织也是分子计算的重 在编码和蛋白质配置之间的第1个对应是原初 要主体之一.这样的技术是分子电子的基础，分子计 形式由自我组装或者折叠机制确定.一个蛋白质的 算在设计一般分子计算机中更基础.在美国，生物分 功能和空间配置之间的第2个对应是由分子识别机 子计算协会在DARPA和NSF支持下成立于1997 制实现的，如双螺旋结构，这些机制基本基于蛋白质 年.协会不仅研究高性能大规模并行性分子计算，也 分子的不同部分之间和不同蛋白质分子之间的弱相 研究利用在纳米尺度上的反应节省能量的计算. 互作用 纳米制作装配技术是分子计算应用中活跃的领 自我装配（或者折叠）是蛋白质分子链的能力 域，被认为是纳米技术的一部分.由于DNA是流行 蛋白质以独特的、精确的方式利用重叠能力调节自 的分子工具，人们称它为DNA纳米技术.Winfree提