智能优化算法：分类、特点和未来

TheLudGamer

定义描述

本文从一个经典的优化函数开始，引出智能优化算法的价值。下图为2 维 Schwefel 函数的 3-D 曲面图，其中 x 和 y 的范围均为 [500;500]，且仅取整数。从图上可以看出，除了位于右下角的全局最优解 (421;421) 外， Schwefel 函数还存在大量局部最优解。图中给出了三组局部最优解的实例，分别为 (204;500)、 (421;303) 和 (421;204)。


为了得到上面这个优化问题的全局最优解，最简单粗暴的方法是蒙特卡洛方法（Monte Carlo）。蒙特卡洛方法是指在搜索空间内持续产生随机的尝试解，直至得到全局最优解。该方法通过随机的方式可以有效避免优化过程陷入某个局部最优解，因此具有很好的全局探索性能（Global exploration）。其主要缺点是获得全局最优解需要一定的 “运气”，或显著提高计算量，增加产生随机解的数量。
为了降低计算量，一种直观的策略是增加问题本身的信息来指导算法的求解过程，这里的信息通常是局部的、有限的或不完整的，该类方法称为启发式方法（Heuristics）。其中，最具代表性的启发式算法是贪心算法，它在求解优化问题过程中，只在最有利于提升当前目标函数更优性的方向上进行搜索，因此具有很好的局部开发能力（Local exploitation）。从某种意义上来说，梯度类优化算法中的梯度和海森矩阵都可以被称之为不同层次的启发式信息。通常来说，优化问题获取启发式信息所花费的代价（一般指计算时间或存储空间）越大，则解决特定问题时的效率越高，但适用的问题类型也越窄。例如，牛顿法利用海森矩阵的启发式信息，在局部范围内求解优化问题可以达到二次的收敛速度；反之，算法所利用的启发式信息的代价越小，其求解优化问题时一般效率越低，但适用的问题类型会越广泛，如贪心算法。但是无论是贪心算法还是梯度类算法，针对 Schwefel 函数，由于启发式信息会导致优化过程趋向某个局部最优解，因此该类方法很难直接得到全局最优解。
元启发式（Meta-Heuristics）方法，即本文要说的，智能优化算法，应运而生。它们可以看作是带有随机性的基于群体的启发式方法。一方面他们保持了蒙特卡洛方法的全局探索性能好的特点，另一方面还具有启发式方法的局部开发能力强的优点。
联系与区别

分类简述

从形成原理上来说，元启发式方法可以分为三类：基于进化机制（Evolutionary）、基于物理原理（Physics）和基于群体智能（Swarm Intelligence, SI）。下表给出了部分智能优化算法及其基本分类。


找相同

作为同一大类算法，不同的智能优化算法之间，往往具有以下三个相同点：
（1）都具有跳出局部最优解的能力。这是此类算法的基本要求，采用的手段以增加随机函数为主要方式。
（2）都有超参数需要人为设置。不同类型的算法，超参数的数量有一定的区别。大部分情况下，基于进化机制和基于物理原理的智能优化算法，超参数数量会更少一些。
（3）都需要在全局探索和局部开发上做折中。无限制的全局探索会导致算法不收敛，仅专注局部开发又会使得算法陷入局部最优解，因此在两者之间做折中，是必要的步骤。
找不同

各类智能优化算法的区别，是做算法研究的核心问题之一，也是运筹优化岗位面试中的一个常见问题。不过当前并没有标准答案，博主结合自己的理解给出三点看法：
（1）算法的最初来源不同。从名字基本就可以判断各个算法的来源，此处不再赘述。
（2）在平衡全局探索和局部开发的策略上，有一定区别。举个例子，模拟退火算法主要通过调整一个超参数来平衡两者，蚁群算法则需要同时协调更多参数，而经典差分进化算法则不需要单独设计，因为其核心的差分向量自带平衡能力。
（3）从优化的内涵来说，他们之间的差异也比较大。对优化来说，本质就两件事情：一个是迭代方向，另一个是迭代步长。举个例子，差分进化算法中，迭代方向由差分向量确定，迭代步长由缩放因子控制；粒子群算法中，方向和步长由粒子的原有速度、粒子局部最优方向和粒子全局最优方向共同确定；遗传算法中，方向仅由部分维度确定，步长可以认为是1。
研究方向

针对智能优化算法的设计和改进，已经是许多硕士或者博士的研究内容和方向。在最终的硕士或者博士论文中，甚至是其中的核心创新点。博主本人也沉浸其中很多年，仅根据自己的经验，歪歪一下：
创新点在哪里？

最高级的创新点，是自己去提出一个新的智能优化算法。当然，这本身不是最难的。有可能随便学一下某种动物的生活或捕食习惯，就可以提出一种新的算法来。个人认为，最有挑战性的内容在如何证明自己提的算法比当前已有的诸多智能优化算法更好，否则新算法就很容易失去价值和意义，创新性也自然要被大打折扣。
次级的创新点，是去改进已有的智能优化算法。虽然很多智能优化算法已经都被提出已久了，但是还远没有达到其优化能力的上限。一个思路是去融合不同的智能优化算法。No free lunch，不同的算法大概率都会有自己更擅长求解的优化问题或者阶段，那么设法去融合它们，就有机会得到性能更优的算法。另一个思路是针对某一个算法进行改进设计。针对算法中的某个算子，或者针对算法中的某些参数设计方法，去进行问题自适应设计，也是一个很热门的研究方向。
最低的创新点，是应用某个智能优化算法去解决某些特定的问题。如果问题足够新颖，或者你运气比较好，恰好没有别人尝试过，那可以定义为，应用创新。不幸的是，想要这种运气，真的需要些运气。在这种情况下，更有意义的创新在于，分析清楚当前问题的特点，从而找到最适合求解该问题的智能优化算法，甚至是在此基础上，做针对性改进，从而更好地求解该问题。
特别说明，以上分类的标准，仅以原创性的程度来区分，不表示看得起或者看不起哪个。
就业前景如何？

从当前的就业经历来看，大部分公司更加注重对优化场景的认识和求解。所以针对算法本身的创新研究，用处并不是很大。相反，如果能有各类优化算法的实践经历，明确各种优化算法所适用的问题类型，应该会对找工作和入职后的进一步发展，更有帮助。
此外，智能优化算法为了得到较好的解，往往需要占据很大的计算机时间和空间资源。然而，在工程应用中，对全局性要求并没有想象中的那么高，在最优性和优化效率上，也更倾向于优化效率。举个简单的例子，美团外卖的订单分配系统，需要秒级输出分配结果。这类需求，智能优化算法很难被直接应用。
科研前景如何？

科研追求的是极致体验。智能优化算法，目标在于高效搜索全局最优解。一个“最”字，足以表达智能优化算法和科研的契合度。在算法选择上，可以选择（1）主流的成熟的智能优化算法。举个例子，连续优化问题选择差分进化算法、组合优化算法问题选择蚁群算法或变邻域搜索算法等；这些算法已经通过别人的经验证明了算法本身卓越的优化能力，自身起点高。（2）最新提出的智能优化算法，这些算法研究的少，有机会让你一夜暴富，前提是你能找到其中比较有潜力的。
想在智能优化算法方面做科研的话，以下三个期刊不容错过：
（1）IEEE Transactions on Evolutionary Computation。虽然近年来，国内人投递得比较多，但是影响因子放在那里，还是很有影响力的。
（2）Swarm and Evolutionary Computation。成立时间不算久，但是论文质量还不错，当前处在上升阶段。
（2）EVOLUTIONARY COMPUTATION等。
同时，标准测试算例数据集也是需要的。针对连续优化问题，可以参见之前的文章：IEEE CEC benchmarks概述；至于离散优化问题，可以参见网址：http://people.brunel.ac.uk/~mastjjb/jeb/info.html。