适应度地形分析
文章目录
TAGS: Artificial Intelligence、Computational Finance、Fitness Landscape Analysis、Machine Learning、Stochastic Processes
PS: 由于疫情在家研究智能算法，看完这篇文章觉得能够直观了解优化问题，并且十分有趣，决定汉化搬运分享。如果感兴趣请支持原文，侵删。
PS: 这篇文章想要做的是如果在求解优化问题之前审视优化问题的适应度地形状况，可以指导选择什么样的优化算法、配置什么样的参数才能得到更好的效率。对于直观的认识遗传算法等智能优化算法选取的测试函数有很大帮助，什么样的测试问题可以体现算法的优缺点，避重就轻，在验证算法性能时合理选择测试集很重要。
正文:
适应性地形分析技术是计算智能研究小组（CIRG）提出的一些新研究，适用于众多金融计算和机器学习优化问题。 适应度地形分析旨在表征与优化问题相关的高维适应度地形。 这样做是为了使研究人员可以就选择合适的优化算法做出更明智的决定。
本文讨论了优化问题并解释了为何求解优化问题很复杂，同时也介绍了一些期刊中的适应度地形分析技术。讲述一些关于适应度地形分析的研究以及Katherine Malan博士和Andries Engelbrecht教授提出的一些可能方法 。最后讨论了为什么这些技术与计算金融相关。 本文简化了本文，并且（可能）对原始文献造成了不公正，因此，如果您发现此有趣的话，请阅读原始文献。
优化理论
When taken to its logical conclusion, fitness landscape analysis could enable researchers to preemptively determine which classes of optimization algorithms might perform better on the problem at hand and possibly even preemptively determine what parameter configurations for a specific algorithms will perform the best - Key Takeaway
优化问题包括要优化某些量的目标函数，影响目标函数值的一组未知数或变量，以及未知变量的一组约束。 优化算法是一种搜索方法，这种算法是为找到使目标函数最大化或最小化的未知数的可行解。
优化问题的一个例子是投资组合优化。目标函数（适应度）可量化投资组合的良好程度。常用的目标函数是经过风险调整的收益率的度量标准，例如夏普比率（Sharpe Ratio，又被称为夏普指数 — 基金绩效评价标准化指标，理性的投资人选择投资标的与投资组合的主要目的为：在固定所能承受的风险下，追求最大的报酬；或在固定的预期报酬下，追求最低的风险。）未知变量是权重，代表分配给每种资产的资本比例。约束条件包括分配所有资本（等式约束），每种资产的最大权重和最小权重（边界约束）以及最小数量的非零权重（基数约束）。
除了马上要讨论的目标函数的形状外，还包括变量的数量（问题的维数），变量的类型（连续还是离散），使用的约束的数量和类型，以及（例如多目标优化的）最优化判据的数量，这些因素使优化问题更加复杂且难以解决。
我想说的是，尽管优化问题以其最简单的形式表述起来可能很简单，但是考虑现实世界中的诸多因素，优化问题就变得很复杂。例如投资组合优化问题，当考虑为资产类别和单个资产分配边界约束，在目标函数中加入线性和非线性交易成本，添加二次VaR约束以及与风险相关的其他目标或约束时，包括流动性和信贷等因素，优化问题就变得更加棘手 。
均方差投资组合优化框架的许多实际扩展都可能导致更复杂的优化问题
http://web.mit.edu/alo/www/Papers/liquid5.pdf
适应度地形分析定义了难以解决的适应性地形特征问题。 它还为我们提供了有用的指标，这些指标可以指示优化问题是否具有这些特征。 得出合理的结论，适应度分析可以使研究人员提前手工确定哪些类别的优化算法在当前问题上可能表现更好，甚至可以预先确定特定算法的哪些参数配置将表现最佳。话虽如此，这个目标仍然很遥远，仍然需要进行大量研究。
复杂度和适应度地形分析
目标函数的“形状”对不同优化算法的性能影响很大。 我的主管在他们的论文中确定了目标函数的11个特征，这些特征使它们或多或少难以解决。 这些特征包括变量之间的依赖程度，噪声，适应度分布，搜索空间中的适应度分布，最佳地形结构（模态），指导搜索和欺骗的信息，整体地形结构（漏斗形），崎岖性，中立性，对称性以及可搜索性。
这些特性不是独立的，因此一个特性的增加可能会导致另一个特性的改变。 例如，增加的噪音也将增加适应度地形的形态和崎岖性。 其他研究人员认为，仅凭崎岖性，平滑性和中立性就可以充分说明适应度地形。 尽管这这样说不错，但从不同的角度考虑问题也可以提供一些启示。
本节的其余部分使用许多基准优化问题来解释这些特征。尽管基准测试问题对于比较算法当然很有用，但我个人不希望使用它们，因为我认为它们没有任何意义，而且可能过于复杂。 在本文结尾处已说过，我将证明某些现实世界中可能表现出困难特征的优化问题。
绘制基准优化问题的许多图像归功于Python的DEAP（分布式进化算法包），其他一些则来自Wikipedia或Wolfram Alpha。
1. 变量的相互依赖程度（包括上位性）
在遗传学中，上位性（epistasis）是指染色体中各个基因（变量）之间的依赖性程度（解通常被编码为载体）。 如果变量独立地影响解决方案的适用性，那么系统的上位性就很低。 另一方面，如果一个变量的值影响其他变量，则系统具有较高的上位性。 这也称为变量的非线性可分离性。
当一个优化问题中的变量相互依赖时，就不可能独立地找到每个变量的最优值。 投资组合优化是高上位性问题的一个示例，因为资产权重的任何增加都必须由一个或多个其他资产权重的同等减少来抵消。 一些研究人员认为上位性会影响优化问题的难度。
确定上位性的技术包括上位性差异，按位优化措施和按位差异。上位差异通过构造简单的线性回归来近似给定解向量的适应度值。 回归输出与实际适应度函数之间的差异在某种程度上衡量了非线性问题，而这些问题可能存在非线性可分离性和上位性。
2. NOISE 噪声
噪声是因为目标函数中存在随机性。在计算金融学中，当目标函数使用仿真方法并且随机数生成器没有为每个目标函数调用提供相同的随机种子时，很容易引入噪声。大量的噪声会“混淆”基于梯度的启发式优化算法，而事实证明，少量的噪声实际上有利于优化算法。人们普遍认为，进化算法在噪声多的优化问题中表现良好。
下面两张图片是有噪声和无噪声二次方程的适应度地形图。
处理嘈杂的适应度地形的一种方法是多次对目标函数进行重新采样，然后取结果的平均值。 如果目标函数中的随机性是高斯噪声，意味着它的均差为零，那么平均值将是无偏的。 类似地，对于给定的一组输入，对目标函数进行的调用的标准差为非零，表明存在噪声。
3. 适应度分布
适应度值分布的统计分析可用于更好地了解当前的问题。 确定适应度分布的最大挑战是适应度值通常需要进行采样，这可能会导致抽样统计偏差。使用适应度分布来确定有关优化问题的信息的一种有用的适应度地形分析技术是状态密度技术。
状态密度技术使用Boltzmann采样方法来构造整个适应度地形的适应度值的概率密度函数。 此分布可用于对优化问题进行分类。 根据原始论文，该技术还可以用于大致确定针对未解决问题的最佳适应度值。 这对于确定不同优化算法的有效性特别有用。 另外，概率密度函数的特征可以与适应度地形的特征相关联，这意味着它对于地形的推理是有用的。
例如，证明状态密度快速衰减（峰度非常高的概率密度函数）的最大化问题可能表明，在适应度图中找到更好解的可能性将快速衰减。 这意味着该问题将很难解决。
4. 搜索空间中的适应度地形
表征优化问题的另一种方法是测量适应度值如何在搜索空间中分布。 这与适应度分布技术的不同之处在于保留了适应度地形的拓扑。 在我看来，执行此操作的一个显而易见的方法是尝试使用自组织映射神经网络（PS: SOM，可以对数据进行无监督学习聚类）。对于二进制表示问题，可以使用“汉明距离”（HDIL）和“汉明之间的距离”（HBDL）度量（汉明距离是使用在数据传输差错控制编码里面的，对两个字符串进行异或运算，并统计结果为1的个数，那么这个数就是汉明距离）。有关更多信息，请参见这篇文章。
SOM近似于问题的潜在概率密度函数，同时保持景观的拓扑结构（在高维空间中靠得很近的模式在SOM网格中靠得很近）
SOM的高度可能表明健身和密度相结合
请注意，我不确定这是否会真正起作用。 这只是我的主意。
5. 模态和最优地形结构
单峰适合度地形是仅存在一个局部最优值的全局最优值（例如二次函数）。多模态适应度地形是存在许多局部最优的一个或多个局部极小，其中一个或多个可能是全局最优。局部搜索算法无法找到全局极小值，因为缺少跳出局部最优之外进行搜索的信息。 换句话说，它们可能会被困在局部最优的区域。
除了局部极小的数量和形状之外，它们的深度和分布也会增加分析优化算法适应度地形的复杂度。具有相对较少吸引力的盆地的适应度地形被称为孤立地形。单峰函数的一个示例是Sphere基准函数，而独立多模态函数的两个示例是Shekel和H1函数。 有关基准功能的更多信息，请单击此处，此处，此处，此处或此处。
确定适应度地形模态的技术包括：计算局部极小值的数量和分布的技术，用于测量组合优化问题的局部最优盆地面积的逃逸率度量，以及将适应度地形压缩为一张图的技术，该图称为局部最优网络。 局部最优网络用作适应度地形的表示以及局部最优在适应度地形的分布。 下面是一个简单的示例。
[此摘录来自先前有关局部最优网络的链接论文]
6. 指导搜索和欺骗的信息
一些优化问题会生成适应度地形，其结构将更容易将解引导至全局最优。为了使优化算法效果更好，适应度地形应该在正确的搜索方向上提供更多高质量的信息。欺骗性（搜索方向偏离）是存在误导性信息，可能会导致算法偏离全局最优值。
局部最优的位置和密度会对全局最优的适应度地形的欺骗性产生影响。 孤立的多模式适应度地形，如谢克尔函数（如前所示）具有很大的欺骗性。话虽如此，导致欺骗性的因素将取决于所使用的优化算法及其所使用的启发式方法或元启发式方法。欺骗随机梯度下降算法的因素可能不会欺骗遗传算法或粒子群优化程序，反之亦然。
7. 全局地形结构（漏斗形）
漏斗形是由聚类的局部最优组成的整体盆地形状。 适应度地形可以具有单个或多个漏斗。 单个和多个漏斗的地形都可以表现出多种模态。 例如，Rosenbrock函数是单峰的单个漏斗状地形，Rastrigin函数是单峰多漏斗状地形。Schwefel函数是多峰多漏斗地形。
对于仅依赖于局部信息的算法，漏斗可能会带来问题，因为它们可能会陷入次优的漏斗中。估计适应度场景中漏斗的存在的有用技术是离散度量。离散度量要求在不同解之间计算距离，例如欧几里得距离，曼哈顿距离或明可夫斯基距离。假设这样做是正确的，则度量的工作方式如下：
“给出低于适应度阈值的两个样本点：如果阈值的降低导致样本中低于阈值的点的离散度增加，则表明地形中存在多个漏斗。度量的是样本解之间的两两距离的平均值。离散度等于样本中最适点子集的离散度减去其他解集的离散度。” -K. Malan。 有关此指标的更多信息，请参见此文。
8. 崎岖性及平稳性
崎岖性是指局部最优的数量和分布。如果相对接近的解的适应度相差很大，这可能是由于解的周围大量的局部最优，并且局部最优的密度较高，这意味着适应度地形被认为是非常崎岖的。一般而言，所有优化算法的适应度地形都是崎岖不平的（如Griewank和Rastrigin函数（如前所示））。一种考虑崎岖性的模型是NK模型。Himmelblau函数是具有挑战性但又平滑的适应度地形。
随机游走（也称为随机过程）是由一系列特定步长的随机步组成的路径。 我们可以通过沿着适应度地形构建具有不同步长的多个随机游走，并在每个连续点采样计算适应度值来估算适应度地形的崎岖程度。 如果适应度地形平滑，则适应度值将相对缓慢地变化，而如果适应度地形崎不平，则适应度值变化将相对较快。可以使用自相关函数来测量此行为。有关更多信息，请参见相关和不相关的适应度状况以及如何区分两者。
这种确定崎岖性的方法的问题是，它很大程度上取决于随机游走覆盖搜索空间的能力。换句话说，理想地，随机游走应该代表适应度地形。简单的无偏随机游走（例如Brownian Motion）不能满足此要求，因此通常最好使用渐进式随机游走。有关更多信息，请参阅用于对连续适应度地形进行采样的渐进式随机游走算法。下面显示了本文中2D的比较，
表征崎岖性的替代方法是通过适应度地形随机行走的第一和第二个熵度量，以及基于傅立叶分析的振幅谱度量。
9. 中立性
当适应性地形中的相邻解具有相等或接近相等的适应度值时，就说具有中立性。中性区域通常在适应度地形中表现为高原或山脊。 对于优化算法而言，中立性是一个问题，因为在适应度地形的中性组合中移动可能会被误解为局部最优。此外，平面上的梯度为零，这意味着基于梯度的算法可能会在适应度地形的次优区域。 展现中立性的三个基准函数是Egg holder，Schaffer和Easom基准函数。
识别适应度地形中立性的两种技术是中立游走和神经网络分析。中性游走从搜索空间中的一个位置开始，并生成该位置的所有中立邻居，并且距指定点的距离会增加。 重复此过程，直到没有中性邻居，这种方法使得从起始位置开始的总距离增加。中立程度是通过此随机游走的步数来衡量的（有关更多信息，请参见此文）。神经网络分析仅适用于离散的适应性地形。它通过生成所有神经网络的集合来工作。 神经网络是解的子集，这些解具有相等的适应度值，该适应性值通过平均中立比，平均适应度增益或非劣解等方法衡量（有关更多信息，请参见此文）。
10. 对称性
适应度地形中的对称性是指许多点具有相同的适应度值。这导致大量的等价类（在离散数学中，等价关系是指定义在集合A上的关系，满足自反的、对称的和传递的等性质）。对称性一种是当适应度地形相对于维数（轴向偏移）对称，另一种是适应度地形相对于与最佳点有固定距离的任何点对称。一些研究表明，对称性可能会导致遗传算法的性能下降，这可能是因为两个相等适应度的解的组合导致了较差的子集。
11. 可搜索性
最重要的一点是，可搜索性反应的是优化算法向有更好适应度值的区域移动的能力。可搜索性在很大程度上取决于所使用的优化算法。换句话说，某些适应度地形可以通过某些优化算法进行搜索，而不能通过其他算法进行搜索。 这种现象引起了Wolpert和Macready进行搜索和优化的著名的No-Free-Lunch定理。 这些定理指出，没有任何一种优化算法始终比另一种算法优越（PS: 也就是说最好的算法不存在）。 例如，虽然梯度下降法可以很好地训练凸面，连续的适应度地形（例如在神经网络中发现的那些），但在任何包含山脊，中性区域或多个最优值的适应度地形上，其效果都较差。
应用于计算金融
您将在词典中找到对计算金融的无聊定义，是应用计算机科学的一个分支，它处理金融业的实际利益问题。我个人不喜欢这个定义，因为它没有告诉您什么是计算金融，因此我更想告诉人们，计算金融涉及实现定量金融模型的软件的设计、开发、测试和应用。
尽管适应度地形分析已经存在了数十年，但几乎从未在实践中应用过。就我个人而言，我认为这可能是因为没有任何好的开源软件包可以使这些技术对公众开放…这些技术只是应用到包括但不限于运筹学、机器学习和数据科学领域，实在令人遗憾。
投资组合优化的鲁棒性
我的硕士研究旨在确定复杂投资组合优化问题的约束条件，以保证使用诸如粒子群优化算法和遗传算法之类的智能优化算法，而不是像Levenberg- Marquardt和顺序最小二乘编程（SLSQP）。
这项研究涉及使用适应度地形分析来调查因素的影响，这些因素包括但不限于现实世界中的约束条件，例如流动性，信贷和VaR，多目标，固定和浮动利率交易成本，模拟方法以及其他风险因素，例如外汇，以及使用风险调整后的收益时目标函数的选择，这会遇到投资组合优化的鲁棒性问题。这些信息应使我能够评论更传统的数学优化算法的适用性。
随机过程校准
我最近遇到的另一个计算金融优化问题，从适应度角度来看，这是一个相当大的挑战，它是复杂随机过程（例如Merton跳扩散过程）的校准。这是我的朋友和量化研究员Wilson Mongwe的硕士研究主题。他很友善地分享了他在研究过程中得出的这种优化的最大似然目标函数。我不会假装理解所有这些，但是我可以自信地说它很复杂，
该模型具有五个不可分离的参数，即sigma（回报的波动率），sigma跳跃（跳跃的波动率），mu（平均每日回报），mu跳跃（平均跳跃大小）和lambda（瞬时跳跃概率）。 模型校准的问题是找到这些参数的最佳值，以使模型产生的收益类似于现实世界中看到的收益。从某种意义上说，这是一种金融图灵测试。如果我们可以区分模型和市场产生的收益，则模型将失败。
为了找到最佳参数，我们将使用一种优化算法，或者使用一大堆优化算法，希望它们能起作用。 但是我们无法知道此函数在高维空间中表现出的特征。 为了说明这一点，它很可能具有本文讨论的许多具有挑战性的特征，我已经四次绘制了函数，并每次固定了三个参数，
现在，尽管这些适应度地形可能看起来并不像某些基准函数那样复杂，但要记住，每个图像仅代表全部五个维度中的三个，并且它们仅从1到5求和，而不是模型中指定的无穷大。要了解此适应度地形的特征是什么，我们需要在所有5个维度上应用本文讨论的适应度地形分析技术。
适应度地形分析的真正好处在于，它可以使研究人员避免费时的搜索优化算法及其参数配置的过程，而优化算法及其参数配置是通过反复试验而起作用的。
总结
适应度地形分析定义了使得优化问题复杂的特征，并为研究人员提供了有用的指标，这些指标可以指示优化问题是否表现出那些特征。研究人员可以在运筹学，计算金融，机器学习和数据科学等许多领域中使用此信息，明白哪些算法以及哪些算法的参数在优化问题上表现良好。我认为，在给定一组参数值的情况下，适应度的特征与任何特定算法的性能之间的这种关系可以通过其他机器学习模型（例如人工神经网络）来学习。
适应度地形分析的真正好处在于，它可以使研究人员避开耗时的反复试验方法来解决优化问题，而将注意力集中在优化问题本身上。话虽如此，尽管适应度地形分析已经存在了数十年，但在实践中并未广泛使用。这种情况可能是由于缺乏适用于适应度地形分析的开源软件包所致。
为，在给定一组参数值的情况下，适应度的特征与任何特定算法的性能之间的这种关系可以通过其他机器学习模型（例如人工神经网络）来学习。
适应度地形分析的真正好处在于，它可以使研究人员避开耗时的反复试验方法来解决优化问题，而将注意力集中在优化问题本身上。话虽如此，尽管适应度地形分析已经存在了数十年，但在实践中并未广泛使用。这种情况可能是由于缺乏适用于适应度地形分析的开源软件包所致。