摘要

经过几十年的发展，智能优化算法（metaheuristics）取得了长足的进展。在回顾课程讲授内容的基础上，我们阅读了2018年出版的Handbook of Heuristics一书中关于元启发的历史的部分，提炼出作者主要观点，并做出评价。本文将有助于增进读者对智能优化算法发展历程的了解，为后续研究提供借鉴。

引言

课程实际进度（2018年）。

日期 内容
9.18 （导论）优化为控制提供设定值；优化问题按目标数量、决策变量类型的分类；优化方法的分类；智能优化算法取得了搜索时间与搜索质量的均衡；丰田just in time的思想与美团外卖；工业工程系模型驱动的优化；CPLEX、SPSS等软件
9.20 （导论）过程控制所“两高一深”（高炉、高铁、深海）的研究方向及其中优化问题举例；玻璃厂与二维切割问题、三维切割问题；传统优化方法建模难、评价费时的困难；不确定优化举例，有拥堵区域或拥堵时间的TSP
9.25 （导论）多目标优化目标间的相关性与冲突性，确定权重的困难，变权重法与Pareto支配法；优化问题的挑战：全局性（非线性、多极小）、高效性（大规模、评价慢）、鲁棒性（不确定、动态）、可行性（强约束）、均衡性（多目标）；传统优化算法质量低、效率低、对初值依赖性强；2011年Science 2篇与2015年Nature 1篇论文；智能优化定义、思想；目前问题，NFL定理，混合算法
9.27 （导论）Computational Intelligence包括神经网络、进化计算、模糊系统，奇数年各自开会，偶数年合并开会；IEEE Computational Intelligence Society，IEEE相关期刊；3个考核作业
10.9 （模拟退火）优化算法分为经典算法、构造方法、改进型方法；待发展的方向包括算法理论、算法设计机制、学习型算法、问题知识融合、人机交互式算法等；模拟退火（SA）算法的背景，物理机制，算法流程，马氏链模型
10.11 （模拟退火）模拟退火的操作与参数设计，在TSP和PID整定中的应用，改进
10.16 （遗传算法）noising method（没有比SA好用）、nested partitioned algorithm（多用于组合优化）、variable neighborhood search (VNS)、variable neighborhood descent (VND)；遗传算法的基本概念，群体进化、适者生存的机制，进化计算的4个分支，算法流程；SGA的Schema定理；GA的收敛性；具体操作与参数设计
10.23 （遗传算法）GA的操作与参数设计；将GA的变异操作用SA代替形成GASA；京东挑战赛的运输问题（1600个城市，强约束）与供货问题；GA的改进，GAMAS模型；粒子群优化（PSO）的起源、算法、改进，利用个体与群体信息确定下一步搜索；差分进化（DE）的实现比PSO复杂，二者是目前使用效果最好的算法
10.25 （禁忌搜索）禁忌搜索（TS）引言，用禁忌准则避免迂回搜索，用藐视准则赦免一些被禁忌的优良状态；概念；流程；缺点是对初始解有较强依赖性；算法设计，具有参数较少的优点
10.30 （人工神经网络）ANN的历史；结构上氛围前馈、反馈、竞争神经网络；Hebb规则和Delta规则；多层网络的结构，BP算法，MATLAB nnd demo
11.1 （人工神经网络）反馈神经网络Hopfield网络，动力学系统与Lyapunov判稳，连续Hopfield网络模型
11.6 （个人研究）调度问题中的智能优化

回顾课程学习，笔者的一大感受是虽然对智能优化的动机、经典算法、未来发展有一定的认识，但面对众多的名字，感到对这一领域缺乏系统的理解。为此，笔者选取新近出版的[@martí2018handbook]中由Kenneth Sörensen等人编写的A History of Metaheuristics一章[@sorensen2018history]进行阅读。智能优化在国外文献中多称为元启发（metaheuristics），这两个概念在下文不做区分。

元启发的发展

在这一部分，笔者将该文献中的主要观点进行概括。

元启发的定义

作者对元启发的定义是：

元启发是高层次的不依赖特定问题的算法框架，这种框架为开发启发式的优化算法提供了一系列的指导或策略。这个术语也被用来指在上述框架的指导下，针对特定问题而实现的启发式优化算法。

可见，元启发可以指代两个完全不同的事情，第一个是一个高层次（high-level）的框架，本身不是一种算法，而是一系列的概念与策略，这些概念与策略混合在一起，为优化算法的开发提供指导。例如，变邻域搜索（variable neighborhood search, VNS）[@mladenovic1997variable]就是一种这样的框架，它的思想是使用不同的邻域搜索算子（邻域结构）和一个扰动算子，每轮迭代在以当前解为中心的邻域中随机扰动后局部搜索，依照搜索到的解与当前解的优劣比较决定更新当前解还是扩大邻域范围。这种方法动机非常清楚，在实践中也显示出了极大的威力。

元启发的第二个意思是基于元启发框架的一种特定的优化算法实现。为了区分，将第一个意思称为元启发框架，而将第二个意思称为元启发算法。

一部元启发的历史最简单的书写形式就是按时间顺序将这些算法列举出来，但这样的列举本身不能提供任何对学科的洞见，因此，作者采取的历史书写思路是，按照研究者们看待元启发的视角将元启发的发展分为5个阶段：

  • 前于理论的阶段（pre-theoretical period），至约1940年，启发甚至是元启发被使用但没有被正式地研究。
  • 早期阶段（early period），约1940年至约1980年，关于启发的最早的正式研究。
  • 以方法为中心的阶段（method-centric period），约1980年至约2000年，元启发领域腾飞，许多不同的方法被提出。
  • 以框架为中心的阶段（framework-centric period），约2000年至今，越来越多的人持有把元启发看作是框架而不是具体算法更加有用的看法。
  • 科学阶段（scientific period），未来，元启发的设计成为一门科学而不是艺术。

除以上5个阶段，作者还指出了一个与以框架为中心的阶段并存的以借喻为中心的阶段，作者对这类研究持强烈的批评态度，认为这种大体无用的新的基于借喻的方法被遗忘得越快越好。在[@sorensen2015metaheuristics]中，作者对由自然或人造事物的借喻而造出的元启发方法进行了更加具体完整地批判。

第0阶段：前于理论的阶段（至约1940年）

上亿年的进化使得地球上的许多生物都具有了解决优化问题的能力，人是其中的杰出代表。在我们进化的环境中，往往需要在很短的时间内做出决策，例如以何种方式对猛犸象掷出长矛，这种情况下，快速性比最优性重要得多。一路发展，我们已经具有了强大的直觉，来帮助我们快速找到近似好的解。元启发在这时的代表包括类比、手段-目标分析等，这些本身并不能解决具体的问题，但却为思考解决问题的方法提供了指导。当然，当时的人们还没有以一种科学的视角去审视这种直觉。

第1阶段：早期阶段（约1940年至约1980年）

1945年，匈牙利数学家波利亚出版了他著名的《怎样解题》一书，其中明确指出，问题可以通过有限的通用的策略去解决，这些策略包括类比法、归纳法、辅助问题法等，这种方法从某种意义上来说，也属于元启发的范畴，因为这些策略可以指导具体方法的开发。

在这一时期，其他一些高层次的想法也开始出现。通过构造的方式得到好的解就是一个典型的例子，简单的构造规则包括贪婪规则即选取最好的，和后悔规则即选取如果不选就损失最大的，在前者指导下的著名算法包括Prim最小生成树算法、Dijkstra最短路算法，在后者指导下的著名算法包括处理运输问题的Vogel近似法。贪婪策略与后悔策略可视作两种元启发框架。

早期阶段，人们清楚地意识到了高层次策略的存在及其在开发优化问题启发式算法中的重要作用。随着计算机的普及，这些发展终于将元启发带入了下一个历史阶段——以方法为中心的阶段。

第2阶段：以方法为中心的阶段（约1980年至约2000年）

早期的元启发模仿人解决问题、学习教训的方式，而20世纪60年代起，一类截然不同的研究开始了。这些研究类比了生命解决问题的方法——进化。早期的进化算法的目的不是解决优化问题，而是研究自然进化的现象，最初用于优化的进化策略没有使用种群或交叉，后来的进化编程也是如此。John Holland于1975年设计出新的进化算法（遗传算法），第一次将这两个概念引入优化中。尽管他的Schema定理后来受到批评，但进化算法引领了一时的潮流，研究论文呈指数增长。

20世纪80年代，不基于自然进化的通用的解决问题的框架开始被提出，其中的典型代表是模拟退火，这一算法从物理过程借喻。阈值接收是模拟退火的一种变体，表明借喻对于开发一个通用的优化框架而言并不必需。而与早期阶段类似、使用人解决问题的想法的元启发则包括小步移动、禁忌搜索等。1986年提出禁忌搜索的论文[@glover1986future]也创造出“元启发（metaheuristics）”一词，这一强调框架的用语后来渐渐代替了当时的“现代启发（modern heuristics）”一词。

神经网络力图模拟大脑的运转，也是80年代末有限的几种有限的元启发框架之一。到1995年，元启发研究的发展创造了它自己的会议和期刊。

90年代早期提出的其他框架包括GRASP（greedy randomized adaptive search procedure），思想是每轮选择时不必选择最好，而在最好的几个中随机选择一个；蚁群优化（ant colony optimization），引入了解与解之间交换信息的思想。去除进化算法中的随机性的重要努力包括分散搜索（scatter search）、路径重连（path relinking）等。

第3阶段：以框架为中心的阶段（约2000年至今）

研究者将元启发视作框架的转变反映在2000年以后混合算法的开发上，这一阶段也可被称为“混合元启发阶段（hybrid metaheuristic period）”。研究者们从不同框架中借用想法，形成新的启发算法，一些典型代表包括使用启发式构造算法去生成局部搜索算法的初始解；使用GRASP产生解，再将解用路径重连组合。用局部搜索改进进化算法得到的解的方法甚至有了一个新的名字——模因算法（memetic algorithm）。2004年，以混合元启发为名字的系列会议开办。

元启发的混合不只意味着元启发与元启发的混合，而也意味着元启发和任何可能的辅助方法的混合，包括有约束规化、线性规划、混合整数规划等。元启发和精确方法的组合被称为“数学启发（matheuristics）”。2006年，数学启发会议第一次举办。

随着研究者渐渐将元启发视作通用的概念集合（框架），而不是部分元素可被借用的算法，“混合”一词就多余了，因为元启发框架的概念就意味着它们是存在一定内在联系的想法（idea）的集合，而想法之间自然是可以自由组合的。哪些特定的组合适合哪些问题自然受到关注。人们发现，车辆路径问题（vehicle routing problem，TSP的扩展）的几乎任何变体都可以使用多邻域（例如VNS）加局部搜索解决。

在这一阶段，研究者不再必须通过提出新算法来发表论文，他们可以组合先有的高效算子；可以研究元启发框架的一个方面，例如终止条件。

最近出现了对简单得多但在多数情况下效果没有下降很多的算法的关注，例如交替使用一个局部搜索算子和一个扰动算子的迭代局部搜索（iterated local search）一直都很流行；与之对应的构造算法迭代贪婪（iterated greedy）在近来受到关注。当一个元启发被简化为一些简单的规则时，它们的流行程度反而上升了。

元启发目前很看重算法性能。算法性能只有在超过一些基准时，才被认为是好的，这使得元启发研究成为了一种追求胜人一筹的游戏。一些研究者已经指出这种衡量标准的副作用，近来的一些论文正促使元启发研究向科学阶段的转变。

以借喻为中心的阶段

从20世纪80年代起，一部分研究误入歧途，着重在使用自然或人造过程的借喻开发新的元启发方法上。尽管借喻曾激发了早期元启发框架的开发，但很显然，借喻仅仅是借喻，迟早将在某一点失效。并不是所有东西都能被转化为一种有用的元启发框架，至少这种借喻应当在进行某种优化，例如退火最小化能量水平，自然选择最小化生物与环境要求的差异，蚁群最小化蚁穴与食物间的距离，而下述的很多例子根本不具备这一条件，例如鞭炮、煤矿爆炸、云的形成。下面是一个使用过的借喻的不完备罗列。

蚂蚁、蜜蜂、白蚁、细菌、入侵杂草、蝙蝠、苍蝇、萤火虫、鞭炮、煤矿爆炸、青蛙、狼、猫、布谷鸟、顾问、鱼、磷虾、猴、无政府社会、帝国社会、锦标赛、云、海豚、埃及秃鹫、绿鹭、花的授粉、蟑螂群袭、水波、光学、黑洞、洛伦兹变换、闪电、电磁学、重力、音乐制造、智能水滴、河流形成，等等。

第4阶段：科学阶段？

这一阶段尚未到来，但作者设想将有这样一个阶段，研究者将重点放在对元启发科学的理解上。这一阶段需要做的事情包括：建立测试标准，对元启发进行元分析（系统的综述），开发类似CPLEX的启发算法平台，等等。这些努力将带来更好、更高效、能在实验室外使用的启发算法。

对该文献的评价

贡献方面

  • 有洞见的回顾

    尽管作者在开头、结尾都强调，任何历史都不可能是中立的，但可以看到，这部对元启发的历史的叙述对元启发的发展做了有洞见的回顾。作者通过对几十年来甚至更久远的历史的回顾，为我们展示了人类对元启发不断加深的认知过程，显示出作者广泛的了解与深入的思考。

  • 指出未来方向

    在读这一文献前，笔者的感受是，智能优化领域已经有太多的工作，太多的名字，以至于已经复杂得不适合继续研究。但这篇文献改变了笔者的看法。它批判了滥用借喻的现象，并指出当前真正的关键问题所在，让笔者看到这一领域新的希望。

不足方面

  • 这篇文献受限于篇幅，自然不可能对元启发进行面面俱到的回顾，但一些重要的遗漏可能包括性能优异的粒子群优化（PSO）等。
  • 该文献虽然指出当下是以框架为中心的阶段，元启发被视作有内在联系的想法的集合，但没有为这些重要的想法进行诸如列表形式的梳理，是一个遗憾。
  • 部分地方存在引用不足的问题。例如在以框架为中心的阶段的最后，作者在指出近来的一些论文正显示着向科学阶段转变时没有为这些论文添加引用。

参考文献

  • [1] Fred Glover. Future paths for integer programming and links to artificial intelligence. Computers & operations research, 13(5):533–549, 1986.

  • [2] R. Martí, P. Panos, and M. Resende. Handbook of Heuristics. Springer International Publishing, 2018.

  • [3] Nenad Mladenović and Pierre Hansen. Variable neighborhood search. Computers & operations research, 24(11):1097–1100, 1997.

  • [4] Kenneth Sörensen. Metaheuristics — the metaphor exposed. International Transactions in Operational Research, 22(1):3–18, 2015.

  • [5] Kenneth Sörensen, Marc Sevaux, and Fred Glover. A history of metaheuristics. Handbook of heuristics, pages 791–808, 2018.