自然启发优化面临的问题与挑战

2020-07-21杨杰蒲亦非

现代计算机 2020年16期

杨杰，蒲亦非

（四川大学计算机学院，成都610065）

0 引言

许多现实世界的应用涉及目标优化，如成本、能源消耗的最小化，性能、效率和可持续性的最大化。在许多情况下，优化问题存在于高度非线性多模态目标场景，受制于一套复杂的非线性约束，这些问题很难解决。即使现代计算机性能不断增强，使用简单暴力破解仍不现实。因此，高效的算法对这类应用至关重要。虽然优化算法种类很多，如基于梯度的算法、内点法、信赖域法等，但大多数都是基于梯度的局部搜索算法[1]，这意味着最终解可能依赖于起始点。此外，导数计算代价非常昂贵，一些问题如非连续目标在某些区域可能不具有导数。近期趋势是使用自然启发优化，可以分成四个大类：进化算法、生物启发算法、基于物理/化学的算法和群智能算法。

在过去的几十年里，出现了各种各样的群智能算法，包括蚁群算法、粒子群算法、蝙蝠算法、萤火虫算法、布谷鸟搜索等[2]。这些自然启发算法往往是全局优化器，使用多个相互作用的代理来生成搜索空间中的搜索行为。这类全局优化器通常简单、灵活，高效，在许多应用和案例研究中得到了证明[2]。在过去的三十年中，自然启发优化已经取得了显著的进展，并出现了各种各样的应用。

尽管自然启发优化的有效性和流行度很高，但仍然存在许多问题。第一，还没有找到开发与探索之间的平衡。第二，还没有统一的数学框架来对这些算法进行分析，深入了解它们的稳定性、收敛性、收敛速度和鲁棒性。第三，自然启发算法中参数的取值会影响算法的性能，但什么是最佳参数取值或设置方案以及如何调优这些参数以获得最佳性能尚不明确。第四，这些算法的对比研究主要基于数值实验，很难证明这种比较是否公平。分析自然启发算法面临的问题和未来的研究方向，很有必要。

1 问题

1.1 多未必佳

自然启发优化首要问题是决定是改进当前社区发现的方法，或是寻找新的启发来源。最近，围绕基于隐喻的方法的争议尚未就社区在该领域应采用的策略达成任何共识，也没有阻止越来越多的基于所谓的创新自然启发的优化技术的出现。令人遗憾的是，这类文献爆发的部分原因是对该领域的实际需求缺乏看法。然而，就如何从理论上（新颖性、特性）和经验上（比较方法、基准问题）评估新算法这一问题不能达成共识，那么就绝对不可能分清良莠。建议重新开始该领域的工作，着重整个自然启发优化的基础范例，这有助于解决社区中有争议的问题。

1.2 统一数学框架、符号和描述

不同的经验观察和数值模拟已经阐明，自然启发优化在实践中表现出色，但我们很少理解为什么它们在给定的条件下对给定类型的问题有效。尽管在理论分析方面取得了一些进展，但迫切需要使用更系统的方法（理想情况下，一个大类别使用一个统一的框架）来分析自然启发算法，以便从数学上深入了解它们的工作机制，评估其性能，帮助解决为给定的问题集选择合适的算法的难题。最近提出的理论研究似乎对分析和理解群智能算法很有希望，例如使用网络科学来表征群智能算法[3]。

围绕新旧自然启发算法之间的类比已经进行了很多讨论，如和声搜索和进化策略；粒子群优化与萤火虫算法；蚁群优化和智能水滴。通过统一描述算法的语义可以避免分歧，新算法的提出也可以利用这种统一描述方式。大量新自然启发算法被提出证明了采用标准符号的重要性，标准符号关注新算法操作符的领域无关性描述以及启发式和元启发式的设计模式。

这种标准化无隐喻的词汇将防止社区混淆当今广泛使用的模糊数学公式和新算法的真实机制。例如，通过无隐喻描述，一个候选解可以被明确地标识，而不是用鸡蛋、水滴或蜂巢来指代。文献[4]将不同蜂群算法的隐喻解码为标准化优化术语，强调了符号唯一性的重要性。除了评估算法之间的异同之外，该标准化过程还可以带来其他好处，例如提高模块化和启发式组件的可重用性，更好地检测非必要算法复杂性的可能来源以及使结果更直接、更可靠、可复现。描述标准化的透明宣言在多年前就已发布[5]，但至今仍未在此方向上产生任何重大进展。

1.3 参数调优

对于拟牛顿法等传统算法，单个参数的调优具有严格的数学基础[1]。而对于自然启发算法，调优主要是根据经验或通过参数研究[6]。一个具有m 个参数pm=(p1,p2,…,pm)的算法可以用以下形式表示：

其中，ε1,ε2,…,εs是s 个不同的随机数，可以来自不同的概率分布。这些随机数一般都是迭代选取的。因此，算法调优主要是跟这m 个参数有关，可以把公式（1）简化成以下形式：

原则上，我们应该使用调优好的算法（或没有任何参数的算法）来调优新算法。但如果我们使用算法B对算法A 进行调优，算法B 最初是如何调优的？因此，关键问题是如何正确地调优未知算法。

如果参数数量很多，暴力调优可能非常耗时。此外，调优好的算法对一种类型的问题有效，不能保证其对另一种类型的问题也有效。算法的参数设置可能同时依赖于算法和问题，而且没有理由不在迭代过程中改变参数。事实上，一些研究表明，参数的变化可能是有利的。例如，自适应差分进化算法似乎比其基本版本性能更高[7]。调优算法的一种方法是将参数调优视为一个双边过程，从而形成一个自调优框架[8]，使算法可以调优自身。但这仍然是一个非常耗时的方法。

如何优化指定算法的参数，使其在给定问题集上达到最佳性能?或者说，如何改变或控制这些参数，以最大限度地提高算法的性能?自然启发算法的参数调优问题，尚需研究。

1.4 合适的基准测试

对于任何一种新自然启发算法，使用基准函数来对比测试新算法与其他算法的性能非常重要。这样的基准测试可以让研究人员更好地了解算法的收敛性、稳定性、优点和缺点。然而，关键问题是应该使用什么基准。

在目前的文献中，基准测试实践似乎使用了一组具有不同属性的测试函数（如振型、可分性和最优局域性）。但是这种基准在实践中并没有太大的用处。这些测试函数通常在常规域上是无约束的或带有简单约束的，而实际应用中的问题可能有许多复杂的非线性约束，并且域可以由许多孤立的区域或岛屿构成。因此，在测试函数表现良好的算法不一定在实际应用中表现良好。

为了正确地验证算法，测试和验证应该包括具有不规则域、受到各种约束的测试函数。例如下面这个看起来很简单的二维函数f(x,y)：

定义域为：

其中i,j都是整数，N=100 ，a=10 。该函数有4(N+1)2个局部峰，但在四个角有4 个最高峰。其定义域由4(N+1)2=40401个独立区域构成。

根据无免费午餐定理[9]，没有一个通用的工具可以用来解决所有或至少绝大多数的优化问题。算法A 解决某些问题的能力优于另一个算法B，那么还有一些其他问题B 会优于A。在实际解决问题时，我们总是关注一组特定的问题，而不是所有的问题。因此，使用有限的算法集和有限的函数集进行基准测试成为一个零和博弈问题[10]。此外，最近的研究似乎表明，免费午餐可能存在，特别是对于持续优化[11]、多目标优化[12]或协同进化[13]。因此，什么类型的基准测试是有用的?免费午餐存在吗?在什么条件下存在?这些问题仍需研究。

1.5 合适公平的性能指标

比较算法性能时，应采用合适、公平的指标。在目前的文献中，比较研究主要关注准确性、计算量、稳定性和成功率。

验证准确性比较好的做法是，对于给定的问题，将算法获取的最优解与已知最优解或其他已被验证表现优秀的算法的最优解进行对比。显然，这取决于算法的停止条件，即使是无效的算法，运行时间足够长也可以获得足够好的结果。因此，为了公平起见，所有算法应使用相同的计算量。

验证计算量，目前大多采用固定精度，将函数调用或求值的数量作为计算成本的度量进行比较。函数求值的次数越少被认为越好。

自然启发算法的结果不是完全可重复的，需要多次运行才能获得有意义的统计数据。因此，一些研究人员使用在最终迭代中获得的最佳目标值，以及它们的平均值、标准差和其他统计数据。这可能会提供有关算法的更完整描述。虽然标准差越小可能表明算法更稳定，但也可能与所考虑的问题有关，此外，算法中使用的初始化总体和概率分布的方式也有可能影响标准差结果，尽管尚不清楚初始化如何确切地影响最终结果。

还有一个用于比较的指标是成功率。多次运行（Nr）算法，可能存在Ns次找到最优解的情况，则成功率是显然，这取决于“成功”的定义。对于函数f(x)，已知其最优解x*和最小化目标fmin(x*)，成功可以由解达到满意的误差界|x-x*|≤δ或|f(x)-fmin|≤δ来定义。但是，搜索域相对平坦与否，会使得标准非常不同。

大部分文献使用一种或多种性能指标，但尚不清楚上述性能指标是否真的公平。我们仍需思考，要公平比较所有算法，最合适的性能度量是什么？是否有可能设计一个统一的框架来公平而严格地比较所有算法？

2 挑战

2.1 效能到效率

全球对能源效率的关注与日俱增，最近创造了所谓的绿色计算概念[14]。在这个规则下的算法以环境可持续性作为设计目标，在它们执行线程的步骤中施加了严格的约束。采用此类设计会在资源分配、内存索引或运行时间等方面产生重要的修改。最重要的是，算法的实现方式对其实际效率也有很大影响，这就要求从算法设计的一开始就采用绿色计算。支持绿色计算的良好做法应该是使社区始终对新的算法执行复杂度分析。在任何情况下，对自然启发算法效率的研究都应该避免报告与算法本身的实现和部署密切相关的度量，例如计时日志或净内存消耗，这些度量会因非算法事项产生巨大偏差。未来还应推导出算法组件的特征与其预期碳足迹之间的对应关系。

2.2 以人为中心的应用中的自然启发算法

以人为中心的应用程序，如视频游戏或虚拟现实/增强现实（VR/AR），目前处于各种场景的前沿，而自然启发计算可以为之提供前所未有的机器智能水平[15]。这类应用以用户和机器之间持续交互为特征，要求底层算法具有用于动态适应、增量学习和有限复杂性的卓越能力。尽管存在这些计算限制，自然启发计算可能给这些应用领域带来的无数机会：从改进自我定位到优化人群仿真或虚拟对象的操作。例如，VR/AR 中的延迟会受到运动到光子阈值（∼20ms）的严重限制，这对任何自然启发优化算法都提出了具有挑战性的设计约束，毕竟这些算法的设计目的是为了改善用户体验或优化来自流服务器的媒体内容的呈现过程。

要勇于在一个巨大的领域中探索未来，释放出新的有趣的范式，如针对多个不断变化的问题语句的持续优化（与持续/终身机器学习[16]明确相关），以及自我影响模型（根据预测采取的行动可能会影响随后的预测结果）。

2.3 自然启发优化和新兴的计算范例

除上述研究途径外，整个社区都应该密切关注即将到来的新计算范式，从大数据架构下的Map/Reduce模型到短暂计算、亿级计算和量子计算。大约十年前，我们没有预料到计算技术的发展速度会像我们后来目睹的那样快，开发出了能够提取、存储和处理海量数据的数据密集型技术。如今，自然启发算法的Map/Reduce 实现可用于在大数据平台上部署[17]。在处理能力方面，类似的趋势可以在当今的短暂计算[18]和亿级计算[19]中看到，它们为扩展复杂的仿生算法提供了有效手段。然而，量子计算仍然处于初级阶段，它已经将其适用性扩展到机器学习领域，并预计可在许多其他领域的处理吞吐量方面将获得惊人的收益，包括机器学习和大规模优化[20-21]。

我们不知道未来还会遇到哪些计算范例，它们将如何影响自然启发优化方法的设计和部署。然而，我们必须沿着这一领域有价值的方向开展研究工作，为它们的最终到来做好准备。除非我们都认识到这种联合力量的迫切需要，并就自然启发优化的真正优先事项达成一致，否则我们将在这一领域毫无进展的渐进式研究道路上徘徊不定，盲目前进。