自调整算法框架

算法的性能在很大程度上取决于算法相关的参数设置。最佳设置应是算法在解决一系列优化问题时都能获得最佳性能。然而,这种参数调整本身就是一个棘手的优化问题。在这一章中,我们提出了一个自调整算法的框架,使得一个要调参的算法能够调节算法自身。

引言

由于所有算法都有算法相关参数,因此算法的性能很大程度上取决于这些参数的设置。理想情况下,应该有一个很好的方法来调整这些参数,使算法的性能可以达到最优,算法可以使用最少的迭代次数和最高的精度找到问题的最优解。然而,这种对算法相关参数的调整本身就是一个非常棘手的优化问题。实质上,这是一个超优化问题,也就是优化的优化。事实上,找出算法的最佳参数设置仍然是一个悬而未决的问题。

有一些关于参数调整的研究。例如,Eiben 提供了对现有研究的综述 [2]。但是,这些研究还很初步。算法中没有自调整的方法。因此,本章的主要目标是为自调整算法提供一个框架,以便可以根据 Yang 等人开发的自调整框架 [8] 自动调整算法自身的参数。就我们而言,这是参数优化中的第一次。

算法分析与参数调整

优化算法本质上是一个迭代过程,从一些初始猜测/解开始,目的是为了找到更好的解或理想解。搜索最优的过程是通用的,尽管细节上可能因算法而异。传统的算法如 Newton-Raphson 法使用确定性的基于轨迹的方法,而现代自然启发式算法通常是使用基于群体的多代理(agent)算法。实质上,这些代理构成一个迭代的动态系统,应该有一些吸引子或稳定状态。另一方面,同一个系统可以被认为是一组马尔可夫链,它们会趋于稳定概率分布。

算法的通用公式

无论从哪个角度看,这种迭代过程的目的都是让系统进化并收敛到一些稳定的最优。在这种情况下,它与自组织系统有很强的相似性。这种迭代的自组织系统可以根据一组规则或数学方程进行演变。结果,这样一个复杂的系统可以相互作用并自组织成某些聚合状态,表现出一些自组织特征。从这个意义上讲,一个有效的优化算法的合理设计就相当于寻找有效的方法来模拟自组织系统的演化 [1, 3]。

从数学的角度来看,对给定的问题,算法 A 倾向于在迭代或时间 t 从当前的解 产生新的更好的解 。在现代元启发式算法中,随机化经常用于算法中,在很多情况下,随机化以一组 m 个随机变量 出现。例如,在模拟退火中,有一个随机变量,而在粒子群优化中,有两个随机变量。另外,算法中通常有一组 k 个参数。例如,在粒子群优化中,有四个参数(两个学习参数,惯性权重与种群规模)。一般来说,我们可以有一个参数向量 。数学上,我们可以写一个 k 参数、m 个随机变量的算法

其中 A 是从给定解(d 维向量 )到新的解向量 的非线性映射。

优化类型

式 1 产生两种类型的最优性:问题的最优性和算法的最优性。对于诸如 的优化问题,存在全局最优解。这是优化问题的最优性。另一方面,对于一个给定的问题 与目标函数 ,有很多算法可以解决。一些算法可能需要比其他算法更少的计算量。(尽管这可能不是唯一的)计算成本最低的可能是最好的算法。但是,这不是我们关心的问题。一旦我们选择了一个算法 A 来解决问题,那么这个算法就有一个最优的参数设置,能够使算法达到最佳的性能。这种最优性取决于算法本身及其解决的问题。在本章的其余部分中,我们将重点放在这种最优性上。

也即,要实现的最优性为

对于给定的问题 和选定的算法 。我们将这种最优性表示为 ,其中 是使得算法性能最优的参数设置。这里,我们用到了一个事实即 是服从已知概率分布的随机向量。因此,随机向量应与算法的最优性相关。

值得指出的是还有另一种潜在的最优性。即对于给定的问题、具有最佳参数设置 的选定的算法,我们仍然可以使用服从不同概率分布的不同的随机数,甚至混沌映射,使得算法达到更好的性能。严格地说,如果算法 随机变量服从均匀分布 或服从高斯分布 ,那么它变成了两个算法 。技术上讲,我们应该将它们当成不同的算法。由于这里我们强调的是参数的调整,因此我们省略了随机方向的影响并关注于

实质上,调整算法涉及调整算法相关参数。因此,参数调整等价于当前上下文中的算法调整。

参数调整

为了调节 以达到其最佳性能,需要参数调节工具,即调节器。与调整高精度机械一样,需要复杂的工具。为了在算法中调整参数,我们可以使用什么工具?一种方法是使用更好的现有工具(比如算法 B)来调整算法 A。那么现在问题可能变成:你怎么知道 B 更好?B 调节好了吗?如果是的话,你是如何调整 B 的?如果我们是使用另一种工具(比如算法 C)来调整 B。那么现在问题再次出现,算法 C 如何被调整?这可以一直持续到一个长链的末尾,比如算法 Q。最后,我们需要一些工具/算法来调整这个 Q,这又回到了原来的问题:我们如何调整算法 A 它使性能最好?

值得指出的是,即使我们有调整算法的好工具,最佳参数设置和最佳性能都取决于调整中使用的性能度量。理想情况下,这些参数对于次要参数变化、随机种子、甚至是问题实例都应该足够健壮。但在实践中它们可能无法实现。根据 Eiben [2],参数调整可分为迭代和非迭代调节器,单级和多级调节器。这些术语的含义是不言自明的。就实际调整而言,现有方法包括抽样方法、筛选方法、基于模型的方法和元启发式方法。它们的成功和有效性可能会有所不同,因此没有完善的通用参数调整方法。

自调整算法框架

超优化

根据我们之前的观察和讨论,很明显,参数调整是优化优化算法的过程。因此,这是一个超优化问题。实质上,调节器是调整算法的元优化工具。

对于一个标准的无约束优化问题,其目的是寻找函数 在 d-维空间的全局最小 。即

一旦我们选择一个算法 A 来解决这个优化问题,算法将会找出可能接近真实全局最小值 的最小解 。对于给定的 tolerance ,可能需要 次迭代来达到 。显然,实际的 很大程度上取决于问题目标 和算法使用的参数 p。

算法调节的主要目的是发现最佳参数设置 ,以使计算成本或迭代次数最小。因此,参数调优作为一个超优化问题可以写成

其最优性是

理想情况下,参数向量 应该足够健壮。对于不同类型的问题, 中的任何轻微变化都不应该对 A 的性能产生太大的影响,这意味着 应该处于一段范围而不是在尖峰。

多目标观点

如果我们从不同的角度来看算法调整过程,可以将它构造成一个多目标优化问题,其目标有两个:一个问题 的目标 ,另一个是算法的目标 。也就是说,

其中 是达到给定 tolerance 所需的(平均)迭代次数,即找到足够接近全局最优 最小 ,以满足

这意味着对于给定的 tolerance ,将存在一组具有最小 的最佳参数设置。因此,双目标将形成帕累托前沿(Pareto front)。原则上,双目标优化问题 (33) 可以用任何适用于多目标优化的方法来解决。但是由于 通常是给定的,所以解决这个问题的一个自然的方法是使用所谓的 约束或 约束法。命名取决于使用的符号,这里我们使用 约束。

对于给定的 ,我们将其中一个目标(如,)变为约束,那么,前面的问题 (33) 就变成一个有约束的单目标优化问题。也就是,

本章的剩下部分我们将设

重要的是我们仍然需要一个算法来求解这个优化问题。然而,与一般单目标问题的主要区别在于,目前的问题包含一个算法 A。理想情况下,一个算法应该独立于该问题,将待解决的目标视为一个黑匣子。这样我们就有 。然而,实际上,算法会被用来求解具有目标 的特定问题。因此,在这里同时使用

自调节框架

这个框架是由 Yang 等人在 2013 年提出的 [8]。原则上,我们可以通过任何有效的或者已经调节好的算法来求解式 8。现在一个自然的问题是:我们可以通过算法 A 本身求解算法调优问题吗?没有理由不能。事实上,如果我们使用 A 求解式 8,就有了一个自调整算法。也就是说,该算法会针对给定的问题目标自动调优自身。这实质上为自调整算法提供了一个框架,如图所示。

这个框架是通用的,任何算法都可以这样调优,任何问题都可以在这个框架内解决。这基本上同时实现了两个目标:参数的调优和最优化的发现。

在本章的其余部分中,我们使用萤火虫算法(firefly algorithm,FA)作为案例研究。

自调节萤火虫算法

现在让我们使用前面概述的框架来调整萤火虫算法,FA 有以下更新方程:

其中包含四个参数: 和种群规模 n。为了简化参数调优,我们设 ,因此要调优的两个参数是 。值得指出的是 控制缩放,而 控制随机性。为了使该算法能够正确收敛,应该逐渐减少随机性,而一种实现这种随机性降低的方法是使用

其中 t 是迭代次数/代数, 是初始随机因子,我们可以设 而不失一般性。因此,要调优的两个参数变为

现在我们对 5 组测试函数来调节 FA。这些函数可以在文献中找到(如,文献 [4])。

Ackley 函数可以写成

在 (0,0, .., 0) 处有全局最小值

最简单的 De Jong 函数也就是所谓的 sphere 函数

在 (0, 0, …, 0) 处有全局最小值 。该函数是单峰凸函数。

Yang’s forest function [4],

高度多峰,并在 (0, 0, …, 0) 处有全局最小

Rastrigin 函数

在 (0, 0, …, 0) 处有全局最小 。该函数高度多峰。

Zakharov 函数

在 (0, 0, …, 0) 处有全局最小

对于每个目标函数,运行 50 次 FA 进行自我调整,使得数据具有统计意义。人口规模设为 n = 20,所有函数维度设为 d = 8。均值和标准差总结在下表中。

从表中我们可以看出, 的变化很大,而 的范围很窄。参数的最佳设置是问题相关的。这些结果意味着:

  • 算法中参数的最优设置在很大程度上取决于问题,并且对于所有问题没有唯一的最佳设置。
  • 的相对较大的标准差意味着 的实际设置对于给定问题并不重要,因此不需要对 进行调优。也就是说,典型值 应该适用于大多数问题。
  • 某些参数比其他参数更敏感。在目前的情况下,由于 较小的标准差, 需要更多的调节。

这些发现证实了早期文献中的观察, 可用于大多数应用 [5-7],而就 而言 需要在逐渐减小。这可能是为什么其他形式的概率分布如 Lévy 飞行可能比正态分布性能更好的原因。

一些备注

参数调整是调整算法以找到最佳参数设置的过程,使得算法可以针对给定的一组问题执行最佳操作。但是,这种参数调整是一个非常棘手的优化问题。事实上,这样的优化过程是优化算法的优化,这需要特别小心,因为最优性取决于要调优的算法和要求解的问题。可以将这个参数调优过程视为一个双目标优化问题,然而,目标涉及到算法,因此这个双目标问题与正常意义下的多目标问题不同。

我们的自调整算法框架是真正的自调整,因为要调优的算法被用于调优自身。我们已经使用了萤火虫算法和一组测试函数来测试所提出的自调整算法框架。结果表明,它确实可以很好地工作。我们还发现一些参数需要微调,但其他参数不需要仔细调整。这是因为不同的参数可能有不同的敏感度,因此会以不同的方式影响算法的性能。只有敏感度高的参数需要仔细调整。

目前的框架虽然成功,但需要通过各种测试函数和许多不同的算法进行更广泛的测试。了解概率分布如何影响调优参数甚至参数调优过程也是可能的。另外,可以预料的是,这个框架对于参数控制也是有用的,所以用于参数调节和控制的更广义的框架可以有广泛的应用。此外,我们目前的框架可能会扩展到多目标问题,算法对于多目标优化可以用类似的方式进行调优。

参考文献

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[1] AshbyWR. Principles of the self-organizing system.In: Von Foerster H, Zopf Jr GW, editors. Principles of self-organization: transactions of the University of Illinois symposium. London, UK: Pergamon Press; 1962. p. 255–78.

[2] Eiben AE, Smit SK. Parameter tuning for configuring and analyzing evolutionary algorithms. Swarm Evol Comput 2011;1(1):19–31.

[3] Keller EF. Organisms, machines, and thunderstorms: a history of self-organization, Part II. Complexity, emergence, and stable attractors. Hist Stud Nat Sci 2009;39(1):1–31.

[4] Yang XS. Firefly algorithm, stochastic test functions and design optimisation. Int J BioInspired Comput 2010;2(2):78–84.

[5] YangXS,GandomiAH. Bat algorithm: a novel approachfor global engineering optimization. Eng Comput 2012;29(5):1–18.

[6] Yang XS, Deb S. Multi-objective cuckoo search for design optimization. Comput Oper Res 2013;40(6):1616–24.

[7] Yang XS. Multiobjective firefly algorithm for continuous optimization. Eng Comput 2013;29(2):175–84.

[8] Yang XS, Deb S, Loomes M, Karamanoglu M. A framework for self-tuning optimization algorithm. Neural Comput Appl; in press. http://dx.doi.org/10.1007/s00521-013-1498-4.
GreatX wechat
订阅公众号,获取更多信息。