基于张量网络的分布算法估计

《Neurocomputing》:Tensor network estimation of distribution algorithms

【字体: 大 中 小 】 时间:2026年03月09日 来源:Neurocomputing 6.5

编辑推荐:

  约翰·加德纳 | 哈维尔·洛佩兹-皮克雷斯 量子计算倡议,纳斯达克公司,11 Farnsworth St,波士顿,MA 02210,美国 **摘要** 张量网络最初是在多体量子物理的背景下被使用的工具,如今在计算科学领域有着广泛的应用,从数值方法到机器学习都有涉及。

  约翰·加德纳 | 哈维尔·洛佩兹-皮克雷斯
量子计算倡议,纳斯达克公司,11 Farnsworth St,波士顿,MA 02210,美国

**摘要**
张量网络最初是在多体量子物理的背景下被使用的工具,如今在计算科学领域有着广泛的应用,从数值方法到机器学习都有涉及。最近的研究中出现了将张量网络整合到进化优化算法中的方法。本质上,这些方法可以理解为用基于张量网络的生成模型来替代遗传算法中的传统交叉操作。我们从估计分布算法(EDAs)的角度来研究这些方法。我们发现,这些方法的优化性能与生成模型的能力并没有直接的关系。即使生成模型在模拟训练数据来源的分布方面表现更好,也不一定意味着其所支持的优化算法的性能就会更好。这引发了如何最好地将强大的生成模型融入优化流程的问题。基于此,我们发现,在生成模型的输出中添加一个显式的变异操作通常可以提高优化性能。

**引言**
机器学习模型与进化算法之间的互动有着悠久的历史,至少可以追溯到20世纪70年代[1]。这种互动是双向的[2]。进化算法被用来辅助机器学习,例如调整卷积神经网络的超参数[3]、搜索模型架构[4],或优化强化学习算法中的参数[5]。相反,机器学习模型也被用来辅助进化算法,通常作为更大进化算法的组成部分。例如,机器学习模型被用来定义适应度函数[6]、染色体表示[7]、执行“智能”变异[8],以及通过一种复杂的交叉方式从旧个体生成新个体[8]。早期使用机器学习模型作为准交叉组件的例子包括估计分布算法(EDAs)[9]、[10]、[11]、[12]、[13]。EDAs是一类优化算法,其中“父”解决方案被用来拟合或更新一个生成模型,然后从这个模型中采样“子”解决方案。更好的解决方案会被选为下一代的“父”解决方案,即下一代生成模型的训练数据。EDAs可以被视为将传统的交叉(和变异)操作替换为生成模型的遗传算法(GAs)。算法1用伪代码描述了EDA的概要。步骤6包括使用选定的选择方法从种群P中选择N个个体(父代)。常见的选择方法有基于顶级个体适应度的贪婪选择、锦标赛选择以及根据适应度比例选择的Boltzmann选择。步骤7和8对应于从概率模型中学习和采样。在步骤7中,选定的个体种群S被用来获得一个新的生成模型D。这可能涉及将模型拟合到种群S[14]、使用S逐步更新上一代的模型[15],或者更一般地,使用S作为训练数据。步骤9用新的样本P′更新种群P。这可能涉及用P′替换P、将P′添加到P中,或者以其他方式组合它们。

**使用生成模型在进化算法中产生新的“子”解决方案**
在进化算法中使用生成模型具有坚实的概念基础。传统的遗传算法在优化许多类别的函数时存在众所周知的困难。例如,所谓的欺骗性函数[16]、具有上位性的函数[17](其中适应度取决于基因编码中相隔较远的项目之间的相关性),或者具有汉明悬崖的函数[18](其中基因编码中的接近性并不对应于适应度景观中的接近性)。在无监督生成模型的背景下,泛化是指模型从独立同分布(iid)示例数据点中推断出分布的过程[19]。非正式地说,泛化是生成与给定示例有意义相似的新样本的任务。理想情况下,遗传算法中的交叉操作会产生与父代具有有意义且有益特征的子代。从这个角度来看,交叉操作的目的是执行泛化任务。然而,传统的交叉操作有时并不适合这项任务。例如,传统的k点交叉操作会重组基因编码中的连续项目。当定义良好解决方案的属性以块的形式编码时,这种方法效果很好。当然,这是一个强假设;通常,理想的属性可能是非局部编码的。比传统交叉操作更复杂的程序有可能学习到显著特征以及这些特征如何编码理想属性,从而生成与选定父代种群在更多方面有意义相似的子代。EDAs通过用生成模型替换交叉操作来实现这一直觉,并且确实有一些问题实例表明EDAs的性能优于GA[20]。

**EDA的核心是任何类型的生成模型**
EDA的核心可以是任何类型的生成模型,从非常简单的独立伯努利分布[21]到复杂的生成对抗网络(GANs)[22]。我们感兴趣的是基于张量网络的生成模型。张量网络(TNs)是一种将多维数组表示为其他(通常更简单或更小的)数组组合的工具。它们最初是在多体量子物理的背景下被使用的,现在应用范围非常广泛,包括生成建模[23]、[24]。基于张量网络的生成模型的优点包括高效的采样[25]以及相比某些替代方案更高的可解释性[26]。两项最近的研究提出了包含张量网络生成模型组件的进化算法。在[27]中,作者探索了一种称为张量网络生成增强优化(GEO)的算法;在[28]中,作者探索了一种称为概率优化与张量采样(PROTES)的算法。这些算法有所不同,包括所使用的特定张量网络生成模型,但它们都属于EDA框架,即迭代地对选定的种群进行建模,然后从模型中采样以获得新的、希望更好的解决方案。我们将在第2节中更详细地描述这些算法。这样的张量网络EDAs可以扩展以包含显式的变异步骤。虽然变异步骤不是EDA框架的定义部分[14],但之前的研究表明添加显式的变异步骤有助于保持代际间的样本多样性[29]。在图1中,我们展示了包含显式变异步骤的张量网络EDA的流程。

**我们的贡献总结如下:**
- 我们确定了两个使用张量网络[27]、[28]的最新提案,将它们作为解决组合优化问题的进化算法中的概率模型,这些算法属于一个更古老的框架——估计分布算法(EDAs)的子类。
- 我们研究了张量网络生成模型的功能。我们的结果表明,更好的(在泛化能力上)生成模型并不一定导致更好的EDA优化器。实际上,我们一致观察到,在采样后以显式变异步骤的形式向生成模型添加噪声可以提高优化性能。我们建议实践者添加这样的变异步骤,因为它简单且有效。
- 我们比较了不同选择程序、不同概率模型以及有无变异的EDA变体。我们的发现表明,在我们的案例中,一个表达能力较低的概率模型(对应于bond维度为2的矩阵乘积状态的TN和马尔可夫链贝叶斯网络),结合基于历史记录的Boltzmann分布的选择程序,以及对模型采样数据应用的变异操作,可以产生有效的优化器。

**张量网络**
张量网络是一组多维数组,其中某些索引对会被求和[30]、[31]、[32]、[33]。它们可以看作是将矩阵分解的概念推广到更高维数组的一种方式。例如,考虑一个N维张量,其元素为f(x1, x2, …, xN),其中xi∈{0,1},f是定义在{0,1}^N上的标量函数。这种张量的一种流行分解是矩阵乘积状态(MPS)张量网络,其形式为f(x1, x2, …, xN) = ∑l1, l2, …, lN?1 T x1[1] l1 T x2[2] l1 l2 ? T

**使用较差的生成模型实现更好的优化**
许多随机优化算法可以用“利用/探索”二分法来理解。算法利用从先前评估的解决方案中获得的信息来提出有希望的新解决方案,同时也考虑收集更多信息。当在已经识别为有希望的区域内采样与探索新区域之间取得平衡时,算法表现良好。例如,GEO算法就考虑了这种平衡。

**基准测试张量网络EDAs**
在前一节中,我们看到具有0.01变异率的MPS生成模型和具有较低bond维度的MPS模型作为EDA优化器的一部分表现相对较好。在本节中,我们比较了具有0.01比特翻转变异率和bond维度为2的MPS的优化器与其他一系列组合优化问题中的进化算法的性能。选择的基准问题包括两个背包问题,其中N=50和N=100。

**变异步骤**
许多优化算法可以用“利用/探索”二分法来理解。遗传算法明确地将利用和探索功能分为两个不同的操作:交叉和变异。交叉操作提出新的解决方案,这些解决方案旨在类似于之前识别出的良好解决方案,而变异操作则导致探索具有新特征的解决方案。遗传算法的形式使得这种平衡成为可能。

**作者贡献声明**
约翰·加德纳:撰写——审阅与编辑、撰写——初稿、可视化、验证、项目管理、方法论、调查、形式分析、概念化。
哈维尔·洛佩兹-皮克雷斯:撰写——审阅与编辑、撰写——初稿、可视化、验证、方法论、调查、形式分析、概念化。

**利益冲突声明**
作者声明他们没有已知的财务利益或个人关系可能影响本文报告的工作。

**致谢**
作者感谢道格拉斯·汉密尔顿在整个项目中的富有洞察力的讨论和支持。作者还感谢格雷西亚·卡斯特拉佐·马丁内斯和戈登·马对项目早期版本的帮助。
哈维尔·洛佩兹-皮克雷斯是纳斯达克的量子计算研究员。他在马萨诸塞大学阿默斯特分校获得了凝聚态理论物理学博士学位。他的兴趣包括使用张量网络进行组合优化和机器学习。
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号