算法炼金术：在外汇中利用图论
在寻找有利可图的货币交易方式时，玩转图遍历算法
如果您熟悉金融科技（FinTech）初创企业行业，您可能听说过 Revolut，这是一家总部位于英国伦敦的知名金融科技巨头。Revolut 成立于 2015 年，已获得大量投资，并成为英国增长最快的初创企业之一，为许多欧洲公民提供银行服务。
虽然银行业务在如何产生收入方面通常笼罩着神秘的面纱，但 Revolut 在 2020 年和 2021 年的一些关键数据却揭示了其收入来源。
如您所见，这家新银行（neobank）的收入有很大一部分来自外汇（FX）、财富管理（包括加密货币）和卡片服务。值得注意的是，在 2021 年，外汇成为最赚钱的业务。
我的一位朋友，也是一名软件工程师，曾分享过他几年前在 Revolut 软件工程部门技术面试中遇到的一个有趣的故事。他被要求开发一个算法，以识别利用一种或多种中间货币来最有利可图地兑换两种货币的方法。换句话说，他们正在寻找一种货币套利（Currency Arbitrage）策略。
货币套利是一种交易策略，货币交易者通过多次交易来利用不同经纪商为特定货币对提供的不同价差。
任务中明确提到，该算法的基础必须根植于图论。
外汇基础知识
外汇（FX）在全球贸易中扮演着至关重要的角色，是支撑我们互联世界运转的基础。显而易见，外汇在使银行成为最富有的组织之一方面也发挥着重要作用。
外汇产生的利润主要是买入（BID）价和卖出（ASK）价之间的差价（spread）。虽然每次交易的差价可能看起来微不足道，但考虑到日常交易量，它可以累积成数百万美元的利润。这使得一些公司仅凭这些高度自动化的金融业务就能蓬勃发展。
在外汇（Foreign Exchange）领域，我们总是处理货币对，例如 *EUR/USD*。在大多数情况下，这些兑换是双向的（即，*EUR/USD* 和 *USD/EUR*），并且每个方向的汇率值是不同的。
套利货币对代表两种货币（例如欧元和美元）价值之间的数值比率，它决定了它们之间的汇率。
潜在地，我们可以使用多种中间货币进行有利可图的交易，这被称为稳赚（sure bet）。
套利稳赚是一组以循环方式使用的货币对。 了解更多。
许多提供商采用数学建模和分析来确保自身的利润并阻止他人从中获利。因此，这里强调了“潜在地”这个词。
稳赚长度（Sure bet length）是指构成潜在套利机会集合的货币对数量。
在现实世界中，不同银行或兑换平台的汇率可能会有所不同。游客为了找到最好的汇率而穿梭于城市是很常见的事情。有了计算机软件，当您能够访问提供商列表时，这个过程可以在毫秒内完成。
在实际有利可图的交易中，多步操作可能涉及通过不同交易平台上的各种货币进行兑换。换句话说，套利循环（Arbitrage Circle）可能会非常庞大。
套利循环是指获取一种货币，将其转移到另一个平台，兑换成其他货币，最终再换回最初的货币。
通过一种或多种中间货币兑换两种货币的汇率计算为这些中间交易汇率的乘积。
一个示例
例如，假设我们要购买美元兑换瑞士法郎，然后将法郎兑换成日元，最后再将日元兑换成美元。在 2023 年秋季，我们有以下汇率：
- 我们可以用 1 美元购买 0.91 瑞士法郎 (CHF)。
- 我们可以用 1 瑞士法郎购买 163.16 日元。
- 我们可以用 1 日元购买 0.0067 美元。
我们用表格来展示一下
1 USD | 1 CHF | 1 YEN
0.91 CHF | 163.16 YEN | 0.0067 USD
----------------|-------------------|--------------
1.098901099 | 0.006128953 | 149.2537313
现在，我们需要找到这些值的乘积。当该乘积产生的值小于一时，交易序列*就变得有利可图*。
1.098901099 * 0.006128953 * 149.2537313 = 1.005240803
正如我们所见，结果大于一，所以看起来我们损失了 0.05% 的资金。但具体损失了多少？我们可以这样计算：
0.91 CHF * 163.16 (YEN per 1 CHF) * 0.0067 (USD per 1 YEN) = 0.99478652 US Dollars
所以，在开始时卖出 1 美元后，我们最终得到 0.994 美元，少于 1 美元。
简单来说，当一个单位的货币可以用少于一个单位的同种货币获得时，套利循环就是有利可图的。
假设我们在初始交易中找到了用 1 美元购买 0.92 瑞士法郎的机会，而不是 0.91 瑞士法郎。
1 USD | 1 CHF | 1 YEN
0.92 CHF | 163.16 YEN | 0.0067 USD
----------------|-------------------|--------------
1.086956522 | 0.006128953 | 149.2537313
乘积将小于 1。
1.086956522 * 0.006128953 * 149.2537313 = 0.994314272
这意味着，在实际货币中，这将给我们带来超过 1 美元。
0.92 CHF * 163.16 (YEN per 1 CHF) * 0.0067 (USD per 1 YEN) = 1.00571824 US Dollars
瞧，我们赚到了一些利润！现在，让我们看看如何通过图分析来实现自动化。
因此，检查 3 个套利货币对的套利循环中的利润或亏损的公式如下所示：
USD/CHF * CHF/YEN * YEN/USD < 1.0
图表示
为了实现这些过程的自动化，我们可以使用图。前面提到的表格可以自然地转化为图的矩阵表示，其中节点代表货币，边代表双向兑换。
因此，用矩阵表示两个货币对的兑换是很简单的：
EUR USD
1 1 EUR
1 1 USD
根据涉及的货币对数量，我们的矩阵可以扩展：
EUR USD YEN CHF
1 1 1 1 EUR
1 1 1 1 USD
1 1 1 1 YEN
1 1 1 1 CHF
因此，即使只有两种货币，如果我们考虑更多的兑换平台和资源，我们的表格也会变得相当大。
为了解决实际的货币套利问题，通常会使用一个完整的图来包含所有货币报价关系。三货币兑换表可能如下所示：
USD CHF YEN
{ 1.0, 1.10, 0.0067 } USD
{ 0.91, 1.0, 0.0061 } CHF
{ 148.84, 163.16, 1.0 } YEN
我们可以使用简单的 图数据结构 在内存中表示我们的货币对。
class GraphNode
{
public:
string Name;
};
class Graph
{
public:
vector<vector<double>> Matrix;
vector<graphnode> Nodes;
};
现在，我们只需要找出如何遍历这个图并找到最有利可图的循环。但仍然存在一个问题……
数学拯救我们，再次
经典的图算法不适合处理*边长乘积*，因为它们旨在寻找由**这些长度之和**定义的路径（请参阅任何经典的路径查找算法 BFS、DFS、Dijkstra 甚至 A-Star 的实现）。
然而，为了规避这一限制，有一种数学方法可以从乘积过渡到总和：对数。如果一个乘积出现在对数下，它可以转换为对数的总和。
在此方程的右侧，所需的数字小于一，这表明该数字的对数必须小于零。
LogE(USD/CHF) * LogE(CHF/YEN) * LogE(YEN/USD) < 0.0
这个简单的数学技巧使我们能够将寻找边长*乘积*小于一的循环，转变为**寻找边长总和小于零的循环**。
我们的矩阵值转换为 LogE(x) 并保留小数点后两位，现在看起来是这样的：
USD CHF YEN
{ 0.0, 0.1, -5.01 } USD
{ -0.09, 0.0, -5.1 } CHF
{ 5.0, 5.09, 0.0 } YEN
现在这个问题变得更容易用经典的图算法解决了。我们需要遍历图，寻找最有利可图的兑换路径。
图算法
每种算法都有其局限性。我在我之前的文章中提到了其中一些。
我们不能应用经典的 BFS、DFS 甚至 Dijkstra，因为我们的图可能包含负权重，这可能在遍历图时导致负环。负环对算法构成挑战，因为它在每次迭代中不断找到更好的解决方案。
为了解决这个问题，Bellman-Ford 算法只是限制了迭代次数。它遍历图中的每个边，最多进行 V-1 次松弛（其中 V 是节点数）。
因此，Bellman-Ford 算法是这个套利系统的核心，因为它能够发现图中两个节点之间满足两个基本标准的路径：它们包含负权重且不属于负环。
虽然这个算法在理论上很简单（您可以在网上找到大量关于它的视频），但实际实现起来需要一些努力。让我们深入研究一下。
Bellman-Ford 算法实现
由于本文的目的是计算机科学，我将使用虚构的汇率，这些汇率与真实汇率无关。
为了更顺畅地介绍算法，让我们使用一个根本不包含负环的图。
graph.Nodes.push_back({ "USD" });
graph.Nodes.push_back({ "CHF" });
graph.Nodes.push_back({ "YEN" });
graph.Nodes.push_back({ "GBP" });
graph.Nodes.push_back({ "CNY" });
graph.Nodes.push_back({ "EUR" });
// Define exchange rates for pairs of currencies below
// USD CHF YEN GBP CNY EUR
graph.Matrix = { { 0.0, 0.41, INF, INF, INF, 0.29 }, // USD
{ INF, 0.0, 0.51, INF, 0.32, INF }, // CHF
{ INF, INF, 0.0, 0.50, INF, INF }, // YEN
{ 0.45, INF, INF, 0.0, INF, -0.38 }, // GBP
{ INF, INF, 0.32, 0.36, 0.0, INF }, // CNY
{ INF, -0.29, INF, INF, 0.21, 0.0 } }; // EUR
下面的代码示例在图中不存在负环的情况下，使用 Bellman-Ford 算法查找两个节点之间的路径。
vector<double> _shortestPath;
vector<int> _previousVertex;
void FindPath(Graph& graph, int start)
{
int verticesNumber = graph.Nodes.size();
_shortestPath.resize(verticesNumber, INF);
_previousVertex.resize(verticesNumber, -1);
_shortestPath[start] = 0;
// For each vertex, apply relaxation for all the edges V - 1 times.
for (int k = 0; k < verticesNumber - 1; k++)
for (int from = 0; from < verticesNumber; from++)
for (int to = 0; to < verticesNumber; to++)
if (_shortestPath[to] > _shortestPath[from] + graph.Matrix[from][to])
{
_shortestPath[to] = _shortestPath[from] + graph.Matrix[from][to];
_previousVertex[to] = from;
}
}
为人民币运行此代码会填充 `_previousVertex` 数组，并产生类似这样的结果：
Path from 4 to 0 is : 4(CNY) 3(GBP) 0(USD)
Path from 4 to 1 is : 4(CNY) 3(GBP) 5(EUR) 1(CHF)
Path from 4 to 2 is : 4(CNY) 3(GBP) 5(EUR) 1(CHF) 2(YEN)
Path from 4 to 3 is : 4(CNY) 3(GBP)
Path from 4 to 4 is : 4(CNY)
Path from 4 to 5 is : 4(CNY) 3(GBP) 5(EUR)
如您所见，它识别出了人民币与其他各种货币之间的最优路径。
同样，我不会专注于只找到一个最佳路径，因为这是一个相对简单的任务，并非本文的目标。
上述实现虽然在理想情况下运行良好，但在处理包含负环的图时却力不从心。
检测负环
我们真正需要的是识别图是否包含负环的能力，如果包含，则找出问题所在。这些知识可以帮助我们缓解这些问题，并最终发现有利可图的链。
迭代次数不一定非要精确到 V - 1。如果在 (N+1) 次循环中没有发现比第 N 次循环更好的路径，则认为找到了解决方案。因此，存在一些优化空间。
前面提到的代码可以得到增强，不仅可以找到路径，还可以检测图是否包含负环，包括我提到的优化。
vector<double> _shortestPath;
vector<int> _previousVertex;
bool ContainsNegativeCycles(Graph& graph, int start)
{
int verticesNumber = graph.Nodes.size();
_shortestPath.resize(verticesNumber, INF);
_previousVertex.resize(verticesNumber, -1);
_shortestPath[start] = 0;
// For each vertex, apply relaxation for all the edges V - 1 times.
for (int k = 0; k < verticesNumber - 1; k++)
{
updated = false;
for (int from = 0; from < verticesNumber; from++)
{
for (int to = 0; to < verticesNumber; to++)
{
if (_shortestPath[to] > _shortestPath[from] + graph.Matrix[from][to])
{
_shortestPath[to] = _shortestPath[from] + graph.Matrix[from][to];
_previousVertex[to] = from;
updated = true;
}
}
}
if (!updated) // No changes in paths, means we can finish earlier.
break;
}
// Run one more relaxation step to detect which nodes are part of a negative cycle.
if (updated)
for (int from = 0; from < verticesNumber; from++)
for (int to = 0; to < verticesNumber; to++)
if (_shortestPath[to] > _shortestPath[from] + graph.Matrix[from][to])
// A negative cycle has occurred
// if we can find a better path beyond the optimal solution.
return true;
return false;
}
现在我们来处理一个包含负环的更复杂的图。
graph.Nodes.push_back({ "USD" }); // 1 (Index = 0)
graph.Nodes.push_back({ "CHF" });
graph.Nodes.push_back({ "YEN" });
graph.Nodes.push_back({ "GBP" });
graph.Nodes.push_back({ "CNY" });
graph.Nodes.push_back({ "EUR" });
graph.Nodes.push_back({ "XXX" });
graph.Nodes.push_back({ "YYY" }); // 8 (Index = 7)
// USD CHF YEN GBP CNY EUR XXX YYY
graph.Matrix = { { 0.0, 1.0, INF, INF, INF, INF, INF, INF }, // USD
{ INF, 0.0, 1.0, INF, INF, 4.0, 4.0, INF }, // CHF
{ INF, INF, 0.0, INF, 1.0, INF, INF, INF }, // YEN
{ INF, INF, 1.0, 0.0, INF, INF, INF, INF }, // GBP
{ INF, INF, INF, -3.0, 0.0, INF, INF, INF }, // CNY
{ INF, INF, INF, INF, INF, 0.0, 5.0, 3.0 }, // EUR
{ INF, INF, INF, INF, INF, INF, 0.0, 4.0 }, // XXX
{ INF, INF, INF, INF, INF, INF, INF, 0.0 } }; // YYY
我们的程序会简单地停止并显示一条消息。
Graph contains negative cycle.
我们已经能够指出问题所在，但是，我们需要绕过有问题的图段。
避免负环
为了实现这一点，我们将属于负环的顶点标记为常量值 `NEG_INF`。
bool FindPathsAndNegativeCycles(Graph& graph, int start)
{
int verticesNumber = graph.Nodes.size();
_shortestPath.resize(verticesNumber, INF);
_previousVertex.resize(verticesNumber, -1);
_shortestPath[start] = 0;
for (int k = 0; k < verticesNumber - 1; k++)
for (int from = 0; from < verticesNumber; from++)
for (int to = 0; to < verticesNumber; to++)
{
if (graph.Matrix[from][to] == INF) // Edge not exists
{
continue;
}
if (_shortestPath[to] > _shortestPath[from] + graph.Matrix[from][to])
{
_shortestPath[to] = _shortestPath[from] + graph.Matrix[from][to];
_previousVertex[to] = from;
}
}
bool negativeCycles = false;
for (int k = 0; k < verticesNumber - 1; k++)
for (int from = 0; from < verticesNumber; from++)
for (int to = 0; to < verticesNumber; to++)
{
if (graph.Matrix[from][to] == INF) // Edge not exists
{
continue;
}
if (_shortestPath[to] > _shortestPath[from] + graph.Matrix[from][to])
{
_shortestPath[to] = NEG_INF;
_previousVertex[to] = -2;
negativeCycles = true;
}
}
return negativeCycles;
}
现在，如果我们在 `_shortestPath` 数组中遇到 `NEG_INF`，我们可以显示一条消息并跳过该部分，同时仍然识别其他货币的最优解。例如，对于节点 0（代表美元）：
Graph contains negative cycle.
Path from 0 to 0 is : 0(USD)
Path from 0 to 1 is : 0(USD) 1(CHF)
Path from 0 to 2 is : Infinite number of shortest paths (negative cycle).
Path from 0 to 3 is : Infinite number of shortest paths (negative cycle).
Path from 0 to 4 is : Infinite number of shortest paths (negative cycle).
Path from 0 to 5 is : 0(USD) 1(CHF) 5(EUR)
Path from 0 to 6 is : 0(USD) 1(CHF) 6(XXX)
Path from 0 to 7 is : 0(USD) 1(CHF) 5(EUR) 7(YYY)
哇！尽管我们的数据“有点脏”，但我们的代码仍然能够识别出一些有利可图的链。
上面提到的所有代码示例以及测试数据都已在 我的 GitHub 上与您共享。
即使微小的波动也很重要
现在让我们总结一下我们学到的东西。给定三种货币的汇率列表，我们可以轻松检测负环。
graph.Nodes.push_back({ "USD" }); // 1 (Index = 0)
graph.Nodes.push_back({ "CHF" });
graph.Nodes.push_back({ "YEN" }); // 3 (Index = 2)
// LogE(x) table: USD CHF YEN
graph.Matrix = { { 0.0, 0.489, -0.402 }, // USD
{ -0.489, 0.0, -0.891 }, // CHF
{ 0.402, 0.89, 0.0 } }; // YEN
from = 0;
FindPathsAndNegativeCycles(graph, from);
结果
Graph contains negative cycle.
Path from 0 to 0 is: Infinite number of shortest paths (negative cycle).
Path from 0 to 1 is: Infinite number of shortest paths (negative cycle).
Path from 0 to 2 is: Infinite number of shortest paths (negative cycle).
然而，即使汇率稍有变化（即矩阵的调整），也可能导致显著的差异。
// LogE(x) table: USD CHF YEN
graph.Matrix = { { 0.0, 0.490, -0.402 }, // USD
{ -0.489, 0.0, -0.891 }, // CHF
{ 0.403, 0.891, 0.0 } }; // YEN
from = 0;
FindPathsAndNegativeCycles(graph, from);
看，我们找到了一条有利可图的链。
Path from 0 to 0 is : 0(USD)
Path from 0 to 1 is : 0(USD) 2(YEN) 1(CHF)
Path from 0 to 2 is : 0(USD) 2(YEN)
我们可以将这些概念应用于涉及多种货币的更大图。
graph.Nodes.push_back({ "USD" }); // 1 (Index = 0)
graph.Nodes.push_back({ "CHF" });
graph.Nodes.push_back({ "YEN" });
graph.Nodes.push_back({ "GBP" });
graph.Nodes.push_back({ "CNY" }); // 5 (Index = 4)
// LogE(x) table: USD CHF YEN GBP CNY
graph.Matrix = { { 0.0, 0.490, -0.402, 0.7, 0.413 }, // USD
{ -0.489, 0.0, -0.891, 0.89, 0.360 }, // CHF
{ 0.403, 0.891, 0.0, 0.91, 0.581 }, // YEN
{ 0.340, 0.405, 0.607, 0.0, 0.72 }, // GBP
{ 0.403, 0.350, 0.571, 0.71, 0.0 } }; // CNY
from = 0;
runDetectNegativeCycles(graph, from);
因此，我们可能会找到多个获利机会。
Path from 0 to 0 is : 0(USD)
Path from 0 to 1 is : 0(USD) 2(YEN) 1(CHF)
Path from 0 to 2 is : 0(USD) 2(YEN)
Path from 0 to 3 is : 0(USD) 2(YEN) 3(GBP)
Path from 0 to 4 is : 0(USD) 2(YEN) 4(CNY)
但是，有两个重要因素：
- 时间是在执行套利交易时的一个关键因素，主要是因为货币价格的快速波动。因此，稳赚的有效期非常短。
- 平台会收取每笔交易的佣金。
因此，**最小化时间成本**和**减少佣金**至关重要，这可以通过限制稳赚的长度来实现。
经验表明，可接受的稳赚长度通常在 2 到 3 个货币对之间。超过这个范围，计算需求就会增加，交易平台也会收取更高的佣金。
因此，要想获得收入，光有这样的技术是不够的，还需要获得低级别的佣金。通常，只有大型金融机构才能掌握这种资源。
通过智能合约实现自动化
我已经深入研究了外汇交易的逻辑以及如何从中获利，但我还没有触及用于执行这些交易的技术。虽然这个话题有点跑偏，但我忍不住要提一下智能合约。
使用智能合约是当今进行外汇交易的最具创新性的方式之一。智能合约可以实现实时的外汇交易，无需延迟或人工干预（除了创建智能合约本身）。
Solidity 是用于创建智能合约的专业编程语言，这些智能合约可以自动化涉及加密货币的金融交易。智能合约的世界是动态的，并且会受到技术快速变化和不断变化的法规的影响。这是一个充满炒作但同时也与钱包和法律合规性相关的重大风险的领域。
虽然无疑有才华的个人和团队正在这个领域获利，但也有监管机构在努力确保市场规则得到遵守。
我们为什么要研究这个问题？
尽管全球经济复杂、模糊且不可预测，但外汇仍然是金融世界的隐形驱动力。它是使全球数千家公司和数百万个人能够以和平的方式进行合作、提供服务并互利共赢的关键要素，它超越了国界。
当然，政治、法规和中央银行等各种因素会影响汇率和外汇效率。这些复杂性使得金融格局错综复杂。然而，我们必须相信，这些复杂性是为了共同利益而服务于更宏大的目标。
大量科学论文探讨了全球经济中汇率的存在和确定，仅举几例：
- Importers, Exporters and Exchange Rate Disconnect
- Currency choice and exchange rate pass-through
- Exchange rate puzzles and policies
这些论文揭示了外汇的一些基本机制，尽管这些机制仍然难以理解并纳入一个模型。
尽管如此，通过编写代码并尝试解决实际问题，我对我有了更清晰的认识。我希望您像我一样享受这次小小的探索之旅。
敬请期待！
链接
- 所有这些示例的源代码
- Sedgewick R. - Algorithms in C, Part 5: Graph Algorithms
- Bellman Ford 算法代码实现
- William Fiset 的 GitHub 示例 - Bellman Ford On Adjacency Matrix
- William Fiset 的 GitHub 示例 - Bellman Ford On Edge List
历史
- 2023 年 10 月 2 日：初始版本