近似多目标搜索

《Artificial Intelligence》：Approximate Multi-Objective Search

　　张汉|奥伦·萨尔兹曼|T.K. 萨蒂什·库马尔|阿里尔·费尔纳|卡洛斯·埃尔南德斯·乌略亚|斯文·科尼格
美国南加州大学洛杉矶分校

**摘要**
在多目标搜索中，我们考虑一个图，其边带有多个成本成分的注释。一个典型的任务是计算帕累托前沿，即从给定的起点状态到给定终点状态的所有未被支配的路径集合。然而，帕累托前沿的大小可能随着图的大小呈指数级增长，计算整个帕累托前沿可能会非常耗时。因此，在本文中，我们研究了如何根据用户提供的近似因子来找到一个近似前沿。这样的前沿可以比帕累托前沿小得多，从而实现高效的多目标搜索算法设计。我们提出了一个名为A*pex的算法，它使用一种高效但近似的路径表示方法来计算近似前沿。在搜索过程中，该算法避免了显式存储所有路径，从而减少了搜索工作量。我们展示了A*pex如何作为算法构建块来解决其他问题：（1）提供了一个随时版本的A*pex，它能够快速计算出一个初始的近似前沿，然后不断改进以找到更优的近似前沿，最终找到整个帕累托前沿；（2）提供了一个用于近似解决权重约束最短路径（WCSP）问题的A*pex变体，该问题与多目标搜索密切相关。为了评估，我们使用了第9届DIMACS实现挑战赛中的道路网络数据。实验结果表明，A*pex及其WCSP变体在运行时间上比现有的最先进算法快几个数量级。我们还发现，在有限的运行时间内，随时版本的A*pex通常能比最先进算法计算出更好的近似前沿。

**部分摘录**
**引言及相关工作**
在多目标搜索中，我们得到一个图（无论是隐式提供的还是显式给出的）、一个起点状态和一个终点状态。图中的每条边都带有一个由多个成本成分组成的成本向量。解π是从起点状态到终点状态的一条路径，其成本c(π)表示π所经过边的成本之和。如果c(π)的每个成本成分都不大于π′对应的成本，则解π支配解π′。

**术语和问题定义**
粗体字表示向量或向量函数。vi表示向量或向量函数v的第i个分量。两个相同长度N的向量v和v′的和定义为v+v′=[v1+v1′,v2+v2′…vN+vN′]。如果对所有i=1,2…N，都有vi≤vi′，则称v?v′；此时我们说v弱支配v′。如果v?v′且存在某个i∈{1,2…N}使得vi
**算法背景**
在本节中，我们首先回顾了最佳优先多目标搜索框架，因为几乎所有最先进的多目标搜索算法（包括我们的新算法）都是基于这一框架的。具体来说，我们详细描述了ltmoa*和wc-a*。更多背景信息请参见[37]。

**a*pex**
在本节中，我们描述了a*pex，这是一种最佳优先多目标搜索算法，它可以根据用户提供的近似因子ε找到一个ε-近似前沿。虽然像ltmoa*这样的算法是对单个路径进行推理，但a*pex则是针对具有相同结束状态和相似成本的路径集合进行推理，这减少了顶点路径对的扩展次数，从而降低了运行时间。
a*pex的每个节点都是一个所谓的顶点路径对ap=〈a,π〉，其中a是一个n维的集合。

**a-a*pex**
在本节中，我们描述了a-a*pex，这是一种随时多目标搜索算法，它在a*pex的基础上进行了扩展。为简单起见，我们假设a-a*pex对所有目标使用相同的近似因子ε。

**wc-a*pex**
在本节中，我们提出了wc-a*pex，它将a*pex扩展为用于计算wcsp问题实例的(1+ε)次优解，并接受用户提供的ε值。我们首先利用以下观察来说明有界次优wcsp算法与近似双目标搜索算法之间的联系：
**观察1**
对于一个可行的wcsp实例p=〈g,sstart,sgoal,w〉和ε≥0，任何从sstart到sgoal的(ε, 0)-近似前沿π都包含p的一个(1+ε)次优解。

**实验结果**
在本节中，我们报告了a*pex、a-a*pex和wc-a*pex的实验结果。我们使用c++实现了所有算法，并在配备m1 pro芯片和32gb内存的macbook上进行了所有实验。对于所有实验，我们将运行时间限制在了五分钟以内。

**结论**
在本文中，我们提出了a*pex，这是一种多目标搜索算法，它可以找到一个ε-近似的帕累托最优解集。基于a*pex，我们提出了（1）a-a*pex，它是一个随时版本，可以快速计算出一个初始近似前沿，然后不断改进以找到更好的近似前沿，最终找到整个帕累托前沿；（2）wc-a*pex，它是一个用于近似解决权重约束最短路径（wcsp）问题的a*pex变体。

**作者贡献声明**
张汉：撰写——审稿与编辑、撰写——初稿、方法论、调查、形式分析、概念化。奥伦·萨尔兹曼：撰写——审稿与编辑、撰写——初稿、监督、方法论、调查、形式分析、概念化。t.k. 萨蒂什·库马尔：撰写——审稿与编辑、形式分析、概念化。阿里尔·费尔纳：撰写——审稿与编辑、监督、形式分析。卡洛斯·埃尔南德斯·乌略亚：撰写——审稿与编辑、监督。

**利益冲突声明**
作者声明他们没有已知的财务利益或个人关系可能会影响本文报告的工作。 **算法背景** 在本节中，我们首先回顾了最佳优先多目标搜索框架，因为几乎所有最先进的多目标搜索算法（包括我们的新算法）都是基于这一框架的。具体来说，我们详细描述了ltmoa*和wc-a*。更多背景信息请参见[37]。 **a*pex** 在本节中，我们描述了a*pex，这是一种最佳优先多目标搜索算法，它可以根据用户提供的近似因子ε找到一个ε-近似前沿。虽然像ltmoa*这样的算法是对单个路径进行推理，但a*pex则是针对具有相同结束状态和相似成本的路径集合进行推理，这减少了顶点路径对的扩展次数，从而降低了运行时间。 a*pex的每个节点都是一个所谓的顶点路径对ap=〈A,π〉，其中A是一个N维的集合。 **a-a*pex** 在本节中，我们描述了a-a*pex，这是一种随时多目标搜索算法，它在a*pex的基础上进行了扩展。为简单起见，我们假设a-a*pex对所有目标使用相同的近似因子ε。 **wc-a*pex** 在本节中，我们提出了wc-a*pex，它将a*pex扩展为用于计算wcsp问题实例的(1+ε)次优解，并接受用户提供的ε值。我们首先利用以下观察来说明有界次优wcsp算法与近似双目标搜索算法之间的联系： **观察1** 对于一个可行的wcsp实例p=〈G,sstart,sgoal,W〉和ε≥0，任何从sstart到sgoal的(ε, 0)-近似前沿π都包含p的一个(1+ε)次优解。 **实验结果** 在本节中，我们报告了a*pex、a-a*pex和wc-a*pex的实验结果。我们使用c++实现了所有算法，并在配备m1 pro芯片和32gb内存的macbook上进行了所有实验。对于所有实验，我们将运行时间限制在了五分钟以内。 **结论** 在本文中，我们提出了a*pex，这是一种多目标搜索算法，它可以找到一个ε-近似的帕累托最优解集。基于a*pex，我们提出了（1）a-a*pex，它是一个随时版本，可以快速计算出一个初始近似前沿，然后不断改进以找到更好的近似前沿，最终找到整个帕累托前沿；（2）wc-a*pex，它是一个用于近似解决权重约束最短路径（wcsp）问题的a*pex变体。 **作者贡献声明** 张汉：撰写——审稿与编辑、撰写——初稿、方法论、调查、形式分析、概念化。奥伦·萨尔兹曼：撰写——审稿与编辑、撰写——初稿、监督、方法论、调查、形式分析、概念化。t.k. 萨蒂什·库马尔：撰写——审稿与编辑、形式分析、概念化。阿里尔·费尔纳：撰写——审稿与编辑、监督、形式分析。卡洛斯·埃尔南德斯·乌略亚：撰写——审稿与编辑、监督。 **利益冲突声明**>
**算法背景**
在本节中，我们首先回顾了最佳优先多目标搜索框架，因为几乎所有最先进的多目标搜索算法（包括我们的新算法）都是基于这一框架的。具体来说，我们详细描述了ltmoa*和wc-a*。更多背景信息请参见[37]。

**a*pex**
在本节中，我们描述了a*pex，这是一种最佳优先多目标搜索算法，它可以根据用户提供的近似因子ε找到一个ε-近似前沿。虽然像ltmoa*这样的算法是对单个路径进行推理，但a*pex则是针对具有相同结束状态和相似成本的路径集合进行推理，这减少了顶点路径对的扩展次数，从而降低了运行时间。
a*pex的每个节点都是一个所谓的顶点路径对ap=〈a,π〉，其中a是一个n维的集合。

**a-a*pex**
在本节中，我们描述了a-a*pex，这是一种随时多目标搜索算法，它在a*pex的基础上进行了扩展。为简单起见，我们假设a-a*pex对所有目标使用相同的近似因子ε。

**wc-a*pex**
在本节中，我们提出了wc-a*pex，它将a*pex扩展为用于计算wcsp问题实例的(1+ε)次优解，并接受用户提供的ε值。我们首先利用以下观察来说明有界次优wcsp算法与近似双目标搜索算法之间的联系：
**观察1**
对于一个可行的wcsp实例p=〈g,sstart,sgoal,w〉和ε≥0，任何从sstart到sgoal的(ε, 0)-近似前沿π都包含p的一个(1+ε)次优解。

**实验结果**
在本节中，我们报告了a*pex、a-a*pex和wc-a*pex的实验结果。我们使用c++实现了所有算法，并在配备m1 pro芯片和32gb内存的macbook上进行了所有实验。对于所有实验，我们将运行时间限制在了五分钟以内。

**结论**
在本文中，我们提出了a*pex，这是一种多目标搜索算法，它可以找到一个ε-近似的帕累托最优解集。基于a*pex，我们提出了（1）a-a*pex，它是一个随时版本，可以快速计算出一个初始近似前沿，然后不断改进以找到更好的近似前沿，最终找到整个帕累托前沿；（2）wc-a*pex，它是一个用于近似解决权重约束最短路径（wcsp）问题的a*pex变体。

**作者贡献声明**
张汉：撰写——审稿与编辑、撰写——初稿、方法论、调查、形式分析、概念化。奥伦·萨尔兹曼：撰写——审稿与编辑、撰写——初稿、监督、方法论、调查、形式分析、概念化。t.k. 萨蒂什·库马尔：撰写——审稿与编辑、形式分析、概念化。阿里尔·费尔纳：撰写——审稿与编辑、监督、形式分析。卡洛斯·埃尔南德斯·乌略亚：撰写——审稿与编辑、监督。

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