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

第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提

第6期 莫宏伟：自然计算研究进展 ·549 出的DNA瓦片就是这样一种具有DNA的纳米技术 机竞争不是好主意，把P完全问题仅看作评估分 (DNA纳米技术).在一个DNA瓦片链末端含有可 子计算机的测试基准.因此将分子计算机与数字计 变序列，这些瓦片能自集合为规模模式，而且能成为 算机相比较是过时的思想.分子计算应该从基本的 一个在单链末端实现的特殊算法指定的结构.这个 理论到应用都得到广泛研究，目的应该是实现分子 形式的自集合可用于设计一个模板，取代分子电子 尺度上的信息处理机制。 学中的分子逻辑门] 1.3 细胞膜计算 另一个有前景的分子计算应用是基因分析，如 细胞膜计算是由Paun开创的一个新领域，是自 DNA指纹.在美国生物分子计算协会的研究中，应用分 然计算的一个新分支.它是一种受活细胞功能的启 子计算智能测量技术提高了DNA芯片的性能， 发的新计算模式，可以看做是受生物细胞启发的计 在欧洲，Rozenberg建立了分子计算协会，总部 算范例.更准确地说，它是一种基于细胞膜系统的分 在Leiden的自然计算中心，许多欧洲研究组织参与 布式并行计算系统（也称为P系统）.细胞膜结构定 到该协会.欧洲的研究组织突出强调分子计算的理 义的区域中，有一系列对象根据一个给定规则进化 论方面，特别是与形式语言理论有关的图灵计算能 并相互作用，计算的结果通常是在给定时间后系统 力和分子反应的计算复杂性得到积极研究，主要研 的全局状态.细胞膜计算开始于1998年，Paun发表 究内容及结果有：Yokomori研究组基于新的计算范 的文章《利用细胞膜计算》是这个新领域的起点标 例得到许多理论结果，如拼接系统和自组织.尤其是 志10o】 他们提出称为“计算=自我集合(assembly)+转换” 如图2所示，一个细胞膜计算系统是一个从活 的新计算模式，阐明了分子的固有计算能力.分子计 细胞处理不同区域结构的化学化合物的方式中抽象 算分析及其设计策略：为了帮助分子算法和反应系 出来的计算模型.在细胞膜定义的区域中，有根据给 统的实验设计，Hagiya、Nishikawa、Arita和Rose仿真 定规则进化的对象.这些对象可用符号或者符号字 研究了分子计算的计算复杂性、反应机制和序列设 符串描述.前者是一种多样性问题，也就是细胞膜结 计，尤其是虚拟核酸仿真器，能够在计算机中复现分 构区域中具有的多个要处理的对象集合，后者是指 子计算，序列设计的标准也得到积极研究。 可以用字符串语言研究这些对象集合或者多字符串 日本科学促进协会早在1996年就开始从不同 的集合表示] 角度研究分子计算机的理论和建设，如通过生物启 外膜 基质膜 发的自适应系统来研究广泛的进化计算.其他正在 进行的相关研究包括：人工细胞设备、化学信息芯 片，该项技术是高性能和大规模分子计算不可缺少 的；生命信息处理器和外部环境接口系统的设计和 制作，重点是信号转换，尤其是细胞膜受体，在其生 物化学方法中，细胞膜蛋白质期望作为未来细胞计 环境 坏境 算机的输入输出设备，信号转换的功能就是活细胞 中的计算 图2膜结构 Fig.2 Structure of membrane 目前，国外的上述研究组织已经开始长期的积 细胞膜计算研究内容包括不同的控制对象从 极交流计划，包括分子记忆等几个联合研究项目正 在进行中].国内在这方面的研究成果还不多见 一个区域到另一个区域的转换方法以及规则应用方 1.2.4分子计算的问题 法，例如溶解、分裂、产生或者移动细胞膜.组织细胞 膜系统、神经细胞膜系统和群细胞膜系统也正在研 分子计算是对量子计算的补充，寻求在单个分 子内读写、处理信息的方法.目前的研究结果使人们 究中 不再相信DNA计算机将比传统数字计算机更快地 这些方法中的一些改进产生的通用计算系统， 解决NP完全问题.现代计算机能没有误差地解决 还有具有增强的并行性的改进方法，能够解决多项 超过几百个变量的可满足性问题.要达到同样的速 式时间NP完全问题. 度和质量，DNA计算机要在算法及执行上经历不可 不同形式的细胞膜系统统称为P系统，P系统 估量的量的突破： 也可以是所有没有应用于实际的细胞膜系统理论模 研究人员现在认识到用分子计算机与数字计算 型].目前有许多P系统已经公式化，但从理论和 实际应用角度有更多问题还需要研究11.主要集

·550 智能系统学报 第6卷 中在证明具有较少数量的细胞膜系统的计算通用 络、神经信息处理、基因调节、DNA转译与转换、变 性，用于解决诸如布尔满足问题、旅行商问题等NP 异、重组、免疫系统等，化学系统的组合性质可以通 难问题，近2年在图像处理1m]、大气环境建模1] 过实际的化学计算，即利用实际的分子进行计算，如 等领域得到应用.文献[104]提出一种膜计算优化 DNA计算.人工化学计算是化学引喻作为设计新硬 调度算法，将膜计算启发的优化算法用于汽油混合 件和软件结构的范例.化学系统可做为信息处理器. 调度.P系统还可以用于解释活细胞中的自然过程， 3)领域是优化，利用人工化学范例发现组合问 理论上可以硬件实现.其他类型的应用包括计算机 题的解.与进化计算密切联系，进化算法可看作是特 图形学、密码学、优化等领域1s] 殊的人工化学系统.形式上，人工化学可定义为一 2 化学反应计算 个三元组(M,R,A),其中M是人工分子集合，R是描 述分子之间相互作用的规则集合，A是驱动系统的 人工化学是人工生命的一个子领域，研究生命的 算法.M中的分子可以是抽象的符号、字符串、二进 基本机制以及组织的起源和进化.主要有3个方向： 制位符串等.文献[33]提出了基于人工化学系统的 1)建模，包括生物系统、进化系统、社会系统等 旅行商问题求解算法.文献[106]提出了首个化学 领域； 反应启发的优化算法(chemical reaction optimiza- 2)信息处理，自然界的许多化学过程可以解释 ion),仿真结果证明该类算法与现有的优化算法相 为执行计算的过程，如控制细菌运动的化学反应网 比有很强的竞争力，成为一种新的优化算法。 表1自然计算原型与人工模型对照m) Table 1 Comparison of natural computing and original type 自然计算的种类 自然计算原型 自然层次 人工模型 神经网络 细胞 神经计算系统 免疫系统 细胞、分子 人工免疫系统 内分泌系统 分子 内分泌计算 生物细胞 细胞 细胞自动机 生物启发的计算 细胞膜 细胞 细胞膜计算 DNA 分子 DNA计算 蛋白质 分子 蛋白质分子计算 基因 分子 遗传算法 妈蚁、鸟群、鱼群、蜂群、细菌 生物群 群智能 自然语言 左脑半球 形式逻辑与语言 人脑思维 人脑 人工脑 社会启发的计算 人类社会文化 社会文化 文化算法 人类社会中的相互作用 社会活动 社会计算 量子 量子 量子计算 光子 光子 光子计算 物理启发的计算 混沌现象 普遍存在 基于混沌的计算 退火现象 原子 模拟退火算法 化学计算 化学反应 分子 化学（优化）计算 3 结论与展望 有发展潜力的研究趋势进行综述与分析，包括群体 智能、分子计算、细胞计算和化学计算，涉及分子、细 本文对目前自然计算的几种典型范例和未来具 胞和生物社会群体等生物乃至化学领域，当然，物理

第6期 莫宏伟：自然计算研究进展 .551· 启发的计算也是自然计算的一个重要内容，限于篇 科学的进步.这个过程中的某个步骤可能促使我们 幅，没有过多展开叙述.如果从更广义的角度把人类 重新审视自然启发的计算或自然计算，可能自下而 社会与人类思维看作是自然界的一部分，从表1可 上重新发明新的计算方法，每个学科都可能做出自 以看出，目前自然计算的启发原型多种多样，从无机 己的贡献，为人类解决能源、信息、材料、人工智能等 物到有机物，从自然界到人类社会，从人脑到细胞和 重大领域的问题提供更有效的手段 分子，在范围、尺度、内容、形式上都有很大差别，在 各种启发原型上发展的具体技术则多数表现为现代 参考文献： 计算机中的算法、逻辑语言等.应用领域则存在交 [1]GONG Maoguo,JIAO Licheng,DU Haifeng,et al.Mul- 叉，比如都可用于智能信息处理、优化等领域，许多 tiobjective immune algorithm with nondominated neighbor- 技术本身就属于人工智能的分支.按照表1中的模 based selection[J].Evo Comput,2008,16(2):225-255. 式，未来出现其他新型的自然计算模型是肯定的.由 [2]CHEN Tianhi,TANG Ke,CHEN Guoliang,et al.Analysis of computational time of simple estimation of distribution al- 于这些原因，目前还没有关于自然计算的统一理论、 gorithms [J].IEEE Trans on Evolutionary Computation, 方法、原理、技术。 2010,14(1):1-22 未来自然计算主要从理论、应用和学科交叉几 [3]WANG Y.Differential evolution with composite trial vector 个方面展开研究工作，在注重理论研究的同时，更应 generation strategies and control parameters J].IEEE 该将研究的重点放在应用产品研发和与其他学科交 Trans on Evolutionary Computation,2011,15(1):55-67. 叉融合上 [4]CHEN Weineng,ZHANG Jun,CHUNG H S H,et al.A 1)要加强自然计算工程技术可行性研究.只有 novel set-based particle swarm optimization method for dis- 加强自然计算工程技术开发方法研究，建立自然计 crete optimization problems[J].IEEE Transactions on Evo- 算工程技术可行性论证理论，才能尽可能降低开发 lutionary Computation,2010,14(2):278-300. [5]崔逊学.多目标进化算法及其应用[M].北京：国防工 风险.到目前为止，大多数自然计算技术开发的投入 业出版社，2006：1-10. 和产出都不成正比，更谈不上成为高新技术的支柱 [6]郑金华.多目标进化算法及其应用[M].北京：科学出 型产业.在不断研究新的算法同时，研究人员也应妥 版社，2007：1-10. 善认真考虑这个问题， [7]中国科学技术协会.智能科学与技术学科发展报告[R], 2)以硅为基础的计算机对人类的工作、娱乐、 北京：中国科学技术出版社，2010. 交流产生了巨大影响，对社会经济、文化的影响也是 [8]马义德，李廉，王亚馥，等.脉冲耦合神经网络原理及 有目共睹.但是今天的计算机有其物理空间上的局 其应用[M].北京：科学出版社，2006：1-25. 限性.因此，研究替代现有计算机系统的自然计算系 [9]ZHOU Z H,WU J X,JIANG Y,et al.Genetic algorithm 统意义重大 based selective neural network ensemble[C]//Proc of the 3)自然计算是一个庞大的研究领域，有许多具 17th International Joint Conference on Artificial Intelligence (IJCAI01).Seattle,USA,2001,2:797802, 体的研究方向和子领域，需要来自数学、物理、化学、 [10]史忠植.神经网络[M].北京：高等教育出版社， 生物等基础学科以及基因、电子、信息、纳米领域专 2009:1-205. 家的通力合作，更好地促进自然计算的发展.面对千 [11]LIU Y M,CHEN GQ,YING M S.Fuzzy logic,soft com- 差万别的启发原型，建立自然计算的统一模型和理 puting and computational intelligence[M].Berlin:Spring- 论，目前看还不现实，但在具体的自然计算分支中寻 er-Verlag,2005:1-10 求基本的理论、算法模型应该是可行的， [12]DORIGO M,MANIEZZO V,COLORNI A.The ant sys- 当前科学发展的一个重要特征是，不同学科的 tem:optimization by a colony of cooperating agents[J]. 技术和概念之间不断地双向流动甚至多重交叉流 IEEE Trans Sys,Man,and Cybernetics,1996,26(1):1- 动，这样一个趋势意味着新的计算方法的突破不再 [13]KENNEDY J,EBERHART R.Particle swarm optimization 是盲目的，而是有方向性的、必然的.因此综合利用、 控制论、信息论、协同论、耗散论、复杂系统等现代理 [C]//IEEE Int Conf on Neural Networks.Piscataway, USA,1995:1942-1948. 论以及其他新理论研究自然计算理论是必要的.21 [14]王磊，潘进，焦李成。基于免疫策略的进化算法[J]. 世纪的新科学哲学观念表明，在系统层次上，不同学 自然科学进展，2000,10(5)：451455 科之间的边界必须被超越，甚至被推翻.实际上，系 WANG Lei,PAN Jin,JIAO Licheng.Evolutionary algo- 统生物学的发展正不断推动生物学、工程和计算机 rithm based on immune strategy[J].Progress of Nature

.552. 智能系统学报 第6卷 Science,2000,10(5):451455. global numerical optimization[J].Joumal of Systems En- [15]HUANG S J.An immune-based optimization method to gineering and Electronics,2011,21(2):300-311. capacitor placement in a radial distribution system[J]. [29]YANG Yan,ZHOU Yongquan,GONG Qiaoqiao.Hybrid IEEE Trans on Power Delivery,2000(15):744-749. artificial glowworm swarm optimization algorithm for solving [16]DURHAM W.Co-evolution:genes,culture,and human system of nonlinear equations[J].Journal of Computation- diversity[M].Palo Alto,USA:Stanford University Press, al Information Systems,2010,6(10):3431-3438 1994:3545, [30]MEHRABIAN A R,LUCAS C.A novel numerical optimi- [17]ADLEMAN L M.Molecular computation of solutions to zation algorithm inspired from weed colonization[J].Eco combinatorial problems [J].Science,1994,226(11): logical Informatics,2006(1):355-366. 1021-1024. [31]YANG Shuyuan,WANG Min,JIAO Licheng.Quantum [18]PAUN A,PAUN G.The power of communication:p sys- particle swarm optimization[C]//Proc of IEEE Congress tems with symport/antiport[J].New Generation Compu- on Evolution Computation.Washington,DC,USA,2004: ting,2002,20(3):295-305. 320-324. [19]PAUN G.Membrane computing:an introduction [M]. [32]YUCHI M,KIM J H.Ecology-inspired evolutionary algo- Berlin:Springer-Verlag,2002:1-10. rithm using feasibility-based grouping for constrained opti- [20]ONG YS,LIM M H,CHEN X S.Memetic computation: mization[C]//Proc of the IEEE Congress on Evolutionary past,present future[J].IEEE Computational Intelli- Computation.Edinburgh,UK,2005:1455-1461. gence Magazine,2010(5):24-32. [33]JADERICK PP.MICHAEL J M.MENDOZA M,et al. [21 SHI Y,EBERHART R.Evolutionary computation pro- Solving symmetric and asymmetric TSPs by artificial chem- ceedings[C]//IEEE World Congress on Compu Intel. istry[C]//Philippine Computing Science Congress.Phil- New York,USA,1998:69-73. ippine,2004:1-7. [22]莫宏伟，左兴权，毕晓君.人工免疫系统研究进展[J]. [34]PATON R.Computing with biological metaphors M]. 智能系统学报，2009,4(1)：23-29. London:Chapman Hall,2001:1-5. MO Hongwei,ZUO Xingquan,BI Xiaojun.Research on [35 ]KIRKPATRICK S,GELATT C D,VECCHI M P.Optimi- development of artificial immune systems J ]CAAI zation by simulated annealing J].Science,1983,220 Transations on Intelligent Systems,2009,4(1):23-29. (4598):671-680. [23]李晓磊，邵之江，钱积新.一种基于动物自治体的寻优 [36]SHOR P W.Algorithm for quantum computation:discrete 模式鱼群算法[J].系统工程理论与实践，2002,22 logarithms and factoring[C]//Proc of 35th Annual Sympo- (11):32-38. sium on Foundations of Computer Science.New Mexico, LI Xiaolei,SHAO Zhijiang,QIAN Jixin.A fish school op- USA:IEEE Computer Society Press,1994:124-134. timization algorithm based on animal autonomous[J].The- [37]TAYARANI M H N,AKBARZADEH M R T.Magnetic ory and Practice of System Engineering,2002,22(11): optimization algorithms a new synthesis[C]//IEEE Con- 32-38. gress on Evolutionary Computation.Hong Kong,China, [24]BASTOS F,CARMELO J A,LIMA N,De FERNANDO 2008:2659-2665. B.A novel search algorithm based on fish school behavior [38]De CASTRO L N.Fundamentals of natural computing [C]//2008 IEEE Int Conf on Systems,Man,and Cyber- [M].Champman Hall/CRC.Florida,USA,2006:3- netics(SMC 2008).Singapore,2002,22(11):32-38. 20. [25]MUELLER S,MARCHETTO J,AIRAGHI S,KOU- [39]BONABEAU E,DORIGO M,THERAULAZ G.Swarm MOUTSAKOS P.Optimization based on bacterial chemo- intelligence:from natural to artificial systems M].New taxis[J].IEEE Trans on Evolutionary Computation, York,USA:Oxford University Press,1999:2-15. 2002,6(1):16-29. [40]MUELLER S,MARCHETTO J,AIRAGHI S,KOU- [26]TERESHKO V.Reaction-diffusion model of a honeybee MOUTSAKOS P.Optimization based on bacterial chemo- colony's foraging behaviour[J].Parallel Problem Solving taxis[J].IEEE Trans on Evolutionary Computation, from Nature,2000,Computer Science,2000,1917:807- 2002,6(1):16-29. 816. [41]PASSINO K M.Biomimicry of bacterial foraging for dis- [27]SIMON D.Biogeography-based optimization [J].IEEE tributed optimization and control[J].IEEE Control Syst Transactions on Evolutionary Computation,2008,12(6): Mag,2002,22(3):5267. 702-713. [42]TANG W J,WU Q H,SAUNDERS J R.A novel model [28]DAI Chaohua,ZHU Yufeng,CHEN W R.Seeker optimi- for bacteria foraging in varying environments[C]//Proc zation algorithm:a novel stochastic search algorithm for ICCSA.Berlin,Springer-Verlag,2006:556-565

第6期 莫宏伟：自然计算研究进展 ·553· [43]ACHARYA D P,PANDA G,MISHRA S,et al.Bacteria 46. foraging based independent component analysis[C]//Proc [55]张煜东，吴乐南.多态细菌趋药性优化[J].计算机工程 Int Conf Comput Intell Multimedia Applicat.Piscataway, 与应用，2009,45(18)：6-11. USA:EEE Pre8s,2007:527-531. ZHANG Yudong,WU Lenan.Multimodal bacterial chemo- [44]DASGUPTA S,ABRAHAM D A.Adaptive computational taxis optimization[J].Computer Engineering and Applica- chemotaxis in bacterial foraging optimization:an analysis tion,2009,45(18):6-11. [J].IEEE Tran on Evo Comput,2009,13(4):919- [56]TERESHKO V.Reaction-diffusion model of a honeybee 942. colony's foraging behaviour[M].Berlin:Springer-Verlag, [45 ]KIM D H,ABRAHAM A,CHO J H.A hybrid genetic al- 2000:807-816. gorithm and bacterial foraging approach for global optimiza- [57]TERESHKO V,LEE T.How information mapping patterns ion[J].Inform Sci,2007,177(18):3918-3937. determine foraging behaviour of a honeybee colony[J]. 46]MISHRA S.A hybrid least square-fuzzy bacterial foraging Open Systems and Information Dynamics,2002(9):181- strategy for harmonic estimation J].IEEE Trans Evol 193. Comput,2005,9(1):61-73. [58 TERESHKO V,LOENGAROV A.Collective decision- [47]BISWAS A,DASGUPTA S,DAS S,ABRAHAM A.Syn- making in honeybee foraging dynamics [J].Computing ergy of PSO and bacterial foraging optimization:a compara- and Information systems Journal,2005,9(3):1-7. tive study on numerical benchmarks[C]//Proc 2nd Int [59]TEODOROVIC D.Transport modeling by multi-agent sys- Symp Hybrid Artificial Intell Syst (HAIS)Advances Soft tems:a swarm intelligence approach[].Transportation Computing Ser.[S.1.]Springer-Verlag,ASC,2007: Planning and Technology,2003,26(4):289-312. 255-263. [60]LUCIC P,TEODOROVIC D.Transportation modeling:an [48]PASSINO K M.Biomimiery of bacterial foraging for dis- artificial life approach [C]//ICTAI,Washington,DC, tributed optimization and control[J].IEEE Control System USA,2002:216-223. Magazine,2002(6):5267. [61]PHAM D T,GHANBARZADEH A,KOC E,et al.The [49]MAJHI R,PANDA G,SAHOO G.Efficient prediction of bees algorithm-a novel tool for complex optimisation prob- stock market indices using adaptive bacterial foraging opti- lems C]//Proceedings of the 2nd Virtual International mization(ABFO)and BFO based techniques J].Expert Conference on Intelligent Production Machines and Systems Systems with Applications,2009,36 (6):10097-10104. IPROMS 2006).Cardiff,UK:Elsevier,2006:454- [50]LI M S,TANG W J,TANG W H,et al.Bacteria foraging 459. algorithm with varying population for optimal power fow [62]DRIAS H,SADEG S,YAHI S.Cooperative bees swarm [C]//Proc Applications of Evolutionary Computing 2007. for solving the maximum weighted satisfiability problem, Berlin,Springer-Verlag,2007:32-41. computational intelligence and bioinspired systems[C]/ [51]MO Hongwei,YIN Yujing.Image segmentation based on 8th International Workshop on Artificial Neural Networks bacterial foraging and FCM algorithm[J].International (IWANN 2005).Vilanova,Barcelona,Spain,2005:8- Joural of Swarm Intelligence Research,2011,2(3):16- 10. 29. [63 ]BENATCHBA K,ADMANE L,KOUDIL M.Using bees [52]李威武，王慧，邹志君，等.基于细菌群体趋药性的函数 to solve a data-mining problem expressed as a max-sat one 优化方法[J].电路与系统学报，2005,10(1)：5863. [C]//First International Work-Conference on the Interplay LI Weiwu,WANG Hui,ZOU Zhijun,et al.Function opti- Between Natural and Artificial Computation IWINAC mization based on bacterial chemotaxis[J].Journal of E- 2005).Palmas,Canary Islands,Spain,2005:15-18. lectrical Circuit and System,2005,10(1):58-63. [64]WEDDE H F,FAROOQ M,ZHANG Y.Beehive:an effi- [53]吕慧显.基于微细菌群体趋药性的函数优化算法[J], cient fault-tolerant routing algorithm inspired by honeybee 青岛大学学报：工程技术版，2009,24(1)：19-26. behavior,ant colony,optimization and swarm intelligence LU Huixian.Function optimization based on micro bacteri- [C]//4th International Workshop ANTS 2004.Brussels, al chemotaxis[J].Journal of Qingdao University:Engi- Belgium,2004:5-8. neering,2009,24(1):19-26. [65]YANG X S.Engineering optimizations via nature-inspired [54]曹黎侠，张建科.细菌趋药性算法理论及应用研究进展 virtual bee algorithms [C]//Artificial Intelligence and [J].计算机工程与应用，2006,42(1)：4446 Knowledge Engineering Applications:A Bioinspired Ap- CAO Lixia,ZHANG Jianke.Research development of the- proach,Lecture Notes in Computer Science.Berlin/Hei- ory and application of bacterial chemotaxis algorithm[J]. delberg:Springer-Verlag.2005,3562:317-323. Computer Engineering and Application,2006,42(1):44- [66]PHAM D T,GHANBARZADEH A,KOC E,et al.The