IEEE Fellow姚新：在多目标动态优化问题中，演化计算仍有独特优势

隔多年，再看图灵在1948年撰写的报告——《Intelligent Machinery》，我们仍然会为这位数学天才对智能机器的想象与痴迷所折服。

在这份报告中，图灵将婴儿的大脑皮层比喻为一台「无组织机器」（an unorganized machine），如同婴儿在后天的教育（或「干预」训练）中能逐渐成为一个「有组织的」成年人，行为规划符合社会人类共识，无组织机器也能通过外界的信息交流干预（「paper interference」），成为一台具有人类特征的、甚至会思考的「有组织机器」。

在第16页，图灵抛出一个观点：

从进化与遗传学的角度来看，将大脑皮层看作「无组织机器」的设想是非常令人满意的。

图灵将机器看作一个生命。如同物种在大自然中经历「优胜劣汰」的选择般，图灵设想了一种「智能搜索」（intellectual searches），在解决包含多类型问题的大类问题 n 时，通过淘汰的方式选出适合的方案：

……按顺序取整数并测试每个整数是否具有所需的属性，直到找到具有某属性的整数... 在各个阶段，下一步的选择可能都不止一个。不过，我们可能会将所有可能的选择按顺序排列，直到机器证明一个定理，并能按自己的方式验证该定理以给出问题的解决方案。

在这份仅有20页的报告中，图灵的许多观点成为现代人工智能的基础。比如，无组织机器的进化思想，便奠定了后来「演化计算」（Evolutionary Computation）的学科基础。演化编程、遗传算法、演化硬件等等不可思议的概念，均沿袭于此。

不过，在90年代以神经网络为代表的连接主义兴起后，演化计算逐渐成为计算机科学、甚至人工智能领域的一个小众分支。从2003年创办至今的CNCC，也是在今年才首次开设了以演化计算为主题的分论坛。

该论坛名为「下一代演化计算发展趋势」，由南方科技大学计算机科学与工程系的系主任、IEEE Fellow姚新出任主席，并请到了徐宗本院士、焦李成院士、丁进良、唐珂与罗文坚等学者作演讲。

图注：姚新

姚新的本科就读于中国科学技术大学少年班，师从陈国良院士与李国杰院士，从上世纪90年代博士期间开始研究演化计算，至今已有三十多年，是我国少数研究演化计算的国际知名学者之一，也是历史上首位获得神经网络最高奖「IEEE Frank Rosenblatt Award」的华人学者。

AI科技评论有幸邀请到姚新教授作为「Fellow来了」系列的第 02 期人物，与我们分享演化计算的研究特点、发展现状与研究意义，尤其是演化计算与神经网络的结合。

1、什么是演化计算？

简单来说，演化计算是一种基于自然选择和遗传变异等生物进化机制的全局性概率搜索算法，能够在不要求函数连续、可微与单峰的情况下，找到问题的近似全局最优解。

基于这些优点，演化计算被广泛用于NP与NPC难题求解、神经网络优化、多目标优化问题求解与其他众多领域。

图注：演化计算示例，通过程序迭代模拟，将要解决的问题看作一个环境，在一些可能的解组成的种群中，通过自然演化寻求最优解。

追溯历史，演化计算与人工智能的发展历程很相似。

1958年的达特茅斯会议被称为「人工智能」的起点，而演化计算方向的许多奠基性工作也是在上世纪60年代末、70年代初出现。继图灵讨论「无组织机器」如何成长后，1966年，Lawrence J. Fogel 在其著作《Artificial Intelligence through Simulated Evolution》中提出「演化编程」，基于有限状态机，用演化计算的方法设计一台学习机，预测1、3、5、7、11……中的下一个整数是不是素数。

「这（预测素数）在数学界都是一个巨大的挑战，但 Fogel 在66年就已经想出用机器来预测，而不是靠人来算。」姚新感叹。

图注：Lawrence J. Fogel

1964年，德国柏林工业大学的两位学生 Ingo Rechenberg 与 Hans-Paul Schwefel 提出进化策略（Evolution strategies）；1975年，美国密歇根大学的 John Henry Holland 借鉴了达尔文的生物进化论与孟德尔的遗传定律思想，提出「遗传算法」（Genetic algorithms）。两者后来均成为演化计算的重要分支。

尤其是遗传算法。在《Adaptation in Natural and Artificial Systems》一书中，John Holland 十分强调「适应性」（adaptation），以及如何用遗传算法来研究计算程序的自适应与自动搜索。基于达尔文物种选择理论的问题分析方法，遗传算法开始于一定数量的初始点，每一个节点均具有随机生成的特征，成功生成的节点会被合并、生成新的「智能体」，该「智能体」具有双亲的特征。

遗传算法的高明之处，一是提供了研究进化论的空间与研究自然现象的独特方法，二是利用进化论的思想进行计算机函数优化，让计算机开始具有通过「繁衍」来适应与学习的机制。

图注：John Henry Holland

不过，由于当时计算机的容量小、运算速度慢、符号AI研究火热等因素，演化计算的这些早期理论并没有引起太多人的注意。

直到80年代，传统人工智能的解题局限性开始凸显；与此同时，计算机的速度得到显著提高，演化计算开始被用于解决实际问题，在机器学习、工程优化与过程控制等领域取得了极大成功，重新吸引了研究者的目光，在许多国家掀起了演化计算的研究热潮。

2006年，NASA的ST-5航天器便使用了演化算法来设计空间、自动寻找更高效的X-band天线设计方案。由两种进化算法（实值参数向量与树结构生成表示）「繁衍」出的性能最优的天线经过构造与测试，均优于手工设计的天线。而且，只需要调整适应函数，他们就可以在不到一个月的时间内快速进化出一套新的天线（如下图）：

此外，2008年北京鸟巢体育馆的钢结构在设计的过程中也使用了演化计算，通过遗传算法迭代而成，整体结构十分稳固：

「而演化计算的最近一次大发展，是在2015年以后。」姚新指出。深度学习崛起后，演化计算与人工智能的其他分支结合，形成新的研究方向，比如「演化神经网络」、「演化机器人」。

姚新指出，学习与进化是生物适应的两大基本形式，两者理应相互增益。他解释：

「大多数深度学习模型首先是设计一个结构，然后训练权值，但实际上，没有一个生物的大脑在学习的过程中是结构固定、权值变化的。所有生物的大脑学习都是结构上的学习，而不是调调参数。从上世纪90年代开始，研究演化算法的人就强调，神经网络的学习应该是结构与参数的同时学习，而不是先设计一个结构、然后再去做参数的优化。」

演化计算至少有4个主要分支：遗传算法、演化编程、进化策略与遗传编程。此外，演化计算中还有一些「小而美」的分支，比如共生演化、差分演化、蚁群算法和粒子群算法等等。姚新指出，AlphaGo与对抗学习的许多思想，与80年代末、90年代初演化计算研究者所提出的对抗性思想完全是同源而生，只是实现的手段不一样。

除了对抗性思想，演化计算在多目标优化与决策问题上也有着独特的优势。比如，将一个大规模的深度学习模型安装在手机上，目标1：高性能；目标2：模型安装要控制在手机耗电量可承受的范围内；目标3：安全…这种场景与运筹学中常遇到的优化问题相似，但是，多目标演化算法可以在一次运行中找到整个Pareto front的近似解集，而不仅仅是一个解。这样可以为决策者提供不同的折衷方案并方便决策者比较各种方案。传统方法的缺点之一就是每次算法运行只能找到一个解。

此外，演化计算还擅长处理不确定环境中的学习与优化问题（又称为「动态优化」问题）。比如，在机器人/自动驾驶车辆的研究中，目标方向是往正北走，但由于传感器或机械臂的操控缘故，机器人的行走方向可能出现偏离，那么，机器便要进行动态优化，适度调整，如将可能偏离45度的方向盘调整为0.0001度。在算法层面上，这样的调整并不是一件容易的事，而演化计算可以通过迭代模拟，找出近似最优的方案。

2、第一届中科大少年班学生

姚新从上世纪80年代末开始研究演化计算，一直坚持到今天。

1978年，在诺贝尔物理奖华人获得者李政道的倡导与邓小平、方毅等国家领导人的支持下，一个特殊的教育班级在中国成立。

如李政道设想，它参考招收与培训芭蕾舞蹈演员的方法，从全国选拔极少数年龄在13岁左右的优秀少年到大学接受教育，目的是培养一支「少而精的基础科学工作队伍」。这个班级，就是后来大名鼎鼎的「中科大少年班」，而姚新是当年（1978年春）全国选拔的21位智商过人的少年之一。

图注：部分中科大少年班首届学生留影

本科毕业后，姚新听从赵振西老师的建议，先是去了北京华北计算技术研究所（即「电子部15所」）攻读硕士、以积累工程经验，「因为中科大偏理论，而赵老师认为，做研究缺乏工程知识总是不好的。」在15所，姚新研究了三年微程序设计。

1985年硕士毕业，姚新读博，又回到中国科学技术大学，师从陈国良院士。陈国良是我国并行算法与高计算计算专家、中国科学院院士，在1995年创建了中国第一个国家高性能计算中心——国家高性能计算中心（合肥）。

读博期间，姚新跟着陈国良学习，中间也花了许多时间到中国科学院计算技术研究所跟着李国杰院士做研究，是李国杰回国后带的第一个学生。姚新回忆：

「两位老师对我的帮助都非常大。在中科大，要上基础课，还有讨论班。我从博士论文开始研究模拟退火和演化计算，后来，陈国良老师还专门写了《遗传算法及其应用》（1996年）一书。

到了计算所跟着李国杰老师后，李老师的博士论文与博士后阶段都是做组合搜索，是现在人工智能中很火的领域。那我想，李老师做组合搜索，我肯定比不过他，那我研究演化计算或模拟退火也挺好，李老师当初也同意，所以我的博士论文是关于模拟退火遗传算法。」

图注：用模拟退火算法解决旅行商推销问题（TSP）

1990年，姚新到澳大利亚国立大学计算机科学实验室（Computer Sciences Laboratory）担任博士后，继续从事模拟退火与演化计算的工作。也是从那时候开始，姚新开始研究遗传算法与神经网络的结合，相关工作发表在1991年澳大利亚神经网络的年会上，引起了许多参会者的注意。

「不久后，昆士兰又有一个小型的论坛，叫『AI and Creativity』。里面有个做人工智能的、偏哲学的英国教授叫Margaret Boden，跟我聊了很多，真的是坚定了我将演化计算与神经网络结合起来的研究方向。一些生物的知识书也是她推荐我去读的，我也是看了这些书才知道，哦，原来生物大脑中的学习不是调参数，而是讲突出的连接在那里变来变去。」

1991年，姚新加入澳大利亚最大的国家级科研机构 CSIRO 担任博士后研究员；1992年开始，分别在澳大利亚国防军学院与新南威尔士大学计算机科学学院担任高级讲师、副教授；1999年，他又去了英国伯明翰大学计算机学院担任讲席教授，直到2016年，在南方科技大学的邀请下回国、参与创立南科大计算机系并担任系主任。

姚新在澳大利亚所结识的另一位人工智能华人先驱张成奇教授在南科大的办公室，便与他在同一栋楼。

在研究上，姚新喜欢聚焦于具体的问题，以实际问题来驱动学术研究。

1999年，姚新提出了具有开创性的快速进化编程（fast evolutionary programming，“FEP”）方法。

进化编程（EP）方法原先用于人工智能的问题研究，后被用于解决数字与组合优化问题。在解决多模态优化问题上，EP方法的优势之一是可以通过缓慢的收敛得到一个出色的近似优解。与经典的EP方法相比，姚新所提出的FEP方法擅长在一个大的领域进行搜索，对黑箱优化有优独特优势，后来被广泛应用于神经网络结构学习、最优路径规划、数字滤波器设计以及新材料的设计，单篇谷歌学术引用次数接近4000。

论文地址：http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.1830&rep=rep1&type=pdf

2000年，基于对约束条件处理的考虑，姚新与合作者又开发了一个随机排序方法，将传统的、看似复杂的惩罚函数与拉格朗日方程简化为简单的排序，在牺牲些许数学收敛性的情况下取得了很好的实际应用效果，是姚新在研究生涯中的一个阶段性成果。cc博客网

论文地址：https://www.cs.bham.ac.uk/~xin/papers/published_tec_sep00_constraint.pdf

凭借在演化计算上的一系列开辟性成果，姚新在2003年当选 IEEE Fellow。

除了早期的两大重要成果，姚新还提到他在2006年将演化计算应用于撒盐车调度的项目。撒盐车的调度涉及到车辆数量、每辆车的吨位、调度范围等等，原属于运筹学的研究范围，但在实际的运行中，假设车队有11辆车，载重范围为2.5吨到9吨，重量不固定，那么传统的数学方法便无法假设一个数值来进行计算，也难以设计算法。cc博客网

「现实生活中的调度问题与书本上的非常不一样。首先路况是随时间变的，车辆行驶速度也不固定，车有可能抛锚坏了，等等。」姚新解释，「对于这类充满不确定性的优化问题，相对传统的数学或运筹学方法，演化计算是有优越性的。它能在复杂的动态环境中找到近似最优解。」

从这个项目开始，姚新一直致力于将演化计算用于在不确定性的环境中做动态优化。除此之外，他与团队着重于研究演化计算如何应用于多目标优化决策。

姚新设想，计算机系统应该是一个可以长期演化的系统：「我可以做初始化的设计，等初始化设计完成后，通过与环境交互，这个系统的软件与硬件应该会一直进化下去，（就像生物一样），在不同的环境中就会进化成不同的系统。」cc博客网(公众号：cc博客网)

能够进化的系统，听起来天方夜谭，但在许多场景中是刚需。比如外太空设备。从地面发射信号到外太空，需要好几分钟，但在地面的遥控者无法预测这几分钟里所发生的事情。这时候，如果系统具备自适应、自演化的功能，就能处理未知的、不确定的环境。再比如无人区的基础设施维护，如果设备具有自适应功能，能够自动更新与重组，那么就可以免去人工检测的成本与风险。

问及系统自动进化的前景，姚新颇有自信地答道：「我觉得在不久的将来就可以部分实现，尤其是在软件层面。现在很多东西都是『软件可定义』，这实际上对演化计算是一个利好消息，就给我们一个发挥能力的基础设施，通过修改软件就能修改硬件的配置。」

3、CNCC分论坛：演化计算的下一代发展趋势

不可否认，目前演化计算在国内仍是一个小众方向。

从本质上看，一个研究方向的规模大小与其在商业上的成功有着莫大关联。比方说，深度学习兴起的最大推手就是企业，深度学习之所以能成功，是因为其在产业中孵化出许多应用，能给企业带来经济效益，而演化计算对产业的影响力有限，「即使用演化计算设计天线，也只是设计直径为1cm的天线，而不是所有天线。」

而第二个原因，是了解演化计算的人不多。姚新感叹：「演化计算在许多场景中适用，但大家一般是先尝试了许多其他方式、发现行不通了，才会想到演化计算。」

为此，作为演化计算的忠实研究者，科研之余，姚新也将一部分的精力放在了演化计算的「布道」上，让更多人了解到研究演化计算的重要性：

在图灵发表于1948年的报告中，他就专门花了2页的篇幅探讨演化计算的思想，这也说明从很早开始，演化计算就已经是计算机科学与人工智能中不可分割的一部分。一直到2015年，Nature推出人工智能专刊时，收录了6篇长文，其中1篇（如下）就是专门讲演化计算。

论文链接：https://research.vu.nl/en/publications/from-evolutionary-computation-to-the-evolution-of-things

姚新介绍，演化计算与机器学习的关系，就相当于自适应的两个基础模式。机器学习是个体学习，研究如何在最短的时间内适应一个训练集，时间粒度比较短，而演化计算是群体学习，通过对解空间采样、做比较与淘汰，时间粒度比较长，两者互补，对人工智能缺一不可。

「在研究演化计算时，你是避不开机器学习的，因为从一开始，演化计算就包含在机器学习领域。早期的演化计算论文也是发表在与机器学习相关的会议与期刊。」姚新回忆，「我与张成奇认识，就是因为参加了他1993年在澳大利亚举办的全澳人工智能会议。」

姚新认为，在未来的人工智能发展中，当个体的快速学习已经研究得差不多时，人们迟早会意识到，个体的学习距离通用人工智能是有一定距离的。这时，人们一定会考虑其他的途径，演化计算便是其中的一个选择。

比方说，南京大学的周志华团队虽然一直研究机器学习，但近年来也在演化计算上有所造诣。2019年，周志华便与他的两个学生（钱超、俞扬）出版了《演化学习：理论和算法的进展》英文版一书。

除了周志华团队，中国研究演化计算的学者还有西安电子科技大学焦李成的研究团队、徐宗本院士团队、原先武汉大学康立三教授的部分学生，以及中国科技大学陈国良院士与王旭法教授所带领的学生。

在即将召开的CNCC分论坛「演化计算的下一代发展趋势」中，姚新便邀请了数位能到现场作演讲的嘉宾，包括徐宗本、焦李成、唐珂、丁庆良等学者。

据姚新介绍，此次论坛的演讲内容颇符合李国杰院士所提出的「顶天立地」的口号。徐宗本院士主要从基础理论出发，解析演化计算与机器学习的关系；丁庆良介绍如何将演化算法应用到工业控制中，解决实际问题；唐珂探讨如何用演化计算自动设计算法，而焦李成则从理论到实践系统地研究演化计算及其应用。

论坛的时长只有3个小时，姚新明白，一次「布道」并不能将问题真正吃透。所以，他更希望这个论坛是一次「播种」，将「演化计算」的种子播撒在参会者的心里。

就姚新个人而言，国内演化计算研究发展的关键点有两个：

一是做有影响力的应用，解决实际问题。与此同时，也要找到适合演化算法解决的问题，「比如2006年NASA的研究员想到用演化计算来设计直径1cm的小型卫星天线就很巧妙。当一个问题无法用数学方程描述、只能通过采样的方法做模拟优化时，演化算法的优越性便显示出来了。」

「我经常讲一个可能不是很恰当的比喻：最适合用演化计算的实际问题，是一些特别难的问题，难到其他方法都觉得毫无头绪，这时，演化计算的相对优越性就出来了。不是说演化计算更好，而是有相对的优越性。」姚新谈道。

其次，演化计算要在理论上有所突破。如周志华团队所做的努力，从理论上分析演化计算的优越性与不足之处，从而对整个领域的发展与应用起到指导性的作用。姚新自己也与合作者在演化算法计算复杂性分析方面耕耘多年，仍在继续努力。

4、结语

国内演化计算的圈子本来就狭小。

问及当年决定回国的原因，姚新谈道：

「做学术的人总想做点更有影响力的工作。南方科技大学地处深圳，IT企业众多，学校希望建设一个有特色的计算机科学与工程系。一张白纸总是画起来更方便。

南科大老师说：你的余生有两个比较大的方向，一是继续留在伯明翰，发论文、培养博士生，二是去创建一个新的计算机系，把你的理念传给本科生，按你的想法做一些你在伯明翰没那么容易做的事情。这一点很吸引我。

做没有做过的事情、从本科阶段就开始培养学生做研究，这对姚新来说都是前所未有的挑战，而按照他的说法，「喜欢科研的人都喜欢面对挑战。」

所以，2016年，姚新选择回国。当年年，南科大就设立了计算机科学与工程系，开始招生，如今已培养出数批计算机专业的本科毕业生。他一边授课，一边带领学生从事演化计算与可信AI的科研，在演化计算与神经网络的结合上继续研究。

作为国内研究演化计算的先行者之一，姚新在科研上严格遵循李国杰院士的四字信条——「顶天立地」。另一方面，他也十分推崇博士后导师Richard Brent的独立科研精神，鼓励年轻学者做自己感兴趣的研究，独辟蹊径。

从上世纪90年代末起，姚新便开始从事演化计算与神经网络的结合研究，远早于深度学习的兴起之时，曾因此工作获得2001年的 IEEE Donald G. Fink Prize Paper Award。那么，在深度学习如此火热的当下，演化计算是否还能给人工智能带来新的启发？亦或者，在人工智能领域，演化计算如何找到自己在新时代的位置？

静待2021年12月17日CNCC分论坛「演化计算的下一代发展趋势」。

参考链接：

1、https://weightagnostic.github.io/papers/turing1948.pdf

2、https://wenku.baidu.com/view/13713b7ba26925c52cc5bfd0.html

3、https://www.alanzucconi.com/2016/04/06/evolutionary-coputation-1/

4、https://ti.arc.nasa.gov/m/pub-archive/1417h/1417%20(Hornby).pdf

5、https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.493.6049&rep=rep1&type=pdf

6、https://www.cnblogs.com/tsingke/p/11252203.html

cc博客网原创文章，未经授权禁止转载。详情见转载须知。