将 Prolog & CLP(R) 用于约束系统

Question

我希望使用 Prolog 生成满足约束系统的随机向量。

例如，我们的用户可能会在运行时向我们的软件提供以下信息：

给定一个向量<x1, x2, x3, ... x30>，我们可能有两个约束：

x1 > x2 + x3 + x4
x5 <= sin(x6 + x7)

我想做的是生成一个大致遵循以下形式的 Prolog 程序：

:- random(0.0, 1.0, X1)
:- random(0.0, 1.0, X2)
#...
# its also concievable that the bounds are different than 0 to 1
:- random(0.0, 1.0, X30)

clp(r) :- constraints { 
   X1 > X2 + X3 + X4,
   X5 <= sin(X6 + X7)   
}

?- [ X1, X2, X3, X4, ... X30 ]

这将在 30 维空间中输出一个均匀随机的向量。

这对 Prolog 可行吗？

还有消耗该输出的问题。我想做的是next()重新生成一个新的向量。具体来说，我需要避免重新编译，因为我希望能够每秒生成大约 10,000 个这些向量。我能达到这种性能水平吗？

我希望在运行我们其余软件的 JVM 上使用嵌入式（进程内）SWI-Prolog 实例。这样就足够了吗？

Answer 1

没关系！

这种方法原则上是可以的，而且我个人认为 Prolog 是完成此类任务的不错选择。

然而，有几个微妙之处需要您解决。

首先，让我们正确理解 CLP(R) 的语法：

向量（[X1，X2，X3，X4，X5，X6，X7]）：-
        { X1 > X2 + X3 + X4,
          X5 =< sin(X6 + X7) }。

特别注意 的使用=<以及正确使用{}/1来表示 CLP(R) 约束。<=在 Prolog 算术中避免使用令牌，因为它看起来像一个箭头，通常在证明者中表示含义。

这足以获得第一个答案，即使它们尚未实例化为具体的解决方案：

?-向量(Ls)。
LS = [_1028, _1034, _1040, _1046, _1052, _1058, _1064],
{_1046=_1028-_1034-_1040-_1088,_1088>0.0},
{_1052-sin(_1058+_1064)=<0.0},
{_1052-sin(_1058+_1064)=<0.0},
{_1052-sin(_1058+_1064)=<0.0}。

使用random/1我们可以将 (0,1) 中的随机浮点数分配给任何变量。例如：

?-向量([A,B,C,D,E,F,G]),
   随机(A),
   随机（B）。
A = 0.33797712696696053，
B = 0.7039688010209147，
{D= -0.3659916740539542-C-_894, _894>0.0},
{E-sin(F+G)=<0.0},
{E-sin(F+G)=<0.0},
{E-sin(F+G)=<0.0}。

这解决了任务的一部分。然而，这种方法在以下情况下会失败：

?-向量([A,B,C,D,E,F,G]),
   随机(A),
   随机（B），
   随机（C），
   随机（D）。
错误的。

在这里，（确定性！）随机数生成与约束发生冲突。有几种方法可以解决这个问题。在展示它们之前，让我们将变量限制在所需的时间间隔内，例如使用以下定义：

Zero_to_one(X) :- { 0 =< X, X =< 1 }。

我们可以简单地将这一约束表述为一项附加要求：

？-向量（[A，B，C，D，E，F，G]），
    maplist（零到一，[A，B，C，D，E，F，G]），
   随机(A),
   随机（B），
   随机（C）。

这又产生了false.

方法 1：更多相同的内容

解决上述问题的一种方法是简单地重复随机分配，直到回溯找到解决方案：

?-向量([A,B,C,D,E,F,G]),
   映射列表（零到一，[A，B，C，D，E，F，G]），
   随机(A),
   随机（B），
   重复，
      随机（C）。
A = 0.9433451780634803，
B = 0.15859272177823736，
C = 0.706502025956454，
{D>=0.0,_2064=0.07825043032878898-D,D<0.07825043032878898},
{E>=0.0，E=<1.0，F>=0.0，F==0.0，G=<1.0，E-sin(...)=<0.0}，
{E-sin(F+G)=<0.0},
{E-sin(F+G)=<0.0},
{E-sin(F+G)=<0.0} 。

因此，我们离具体解决方案又近了一步，即向量的完整实例化。缺点非常明显：在极端情况下，我们永远不会以这种方式找到有效的分配。如果运气好一点，即使是单个附加变量也可能需要多次尝试才能找到具体值。

方法 2：最大化或最小化

解决此问题的另一种方法是使用maximize/1和/或minimize/1CLP(R) 来使用约束求解器本身来获得具体的解决方案。这仅适用于线性约束，甚至不适用于所有这些。例如，考虑以下查询：

?- { X = sin(Y) },
   映射列表（零到一，[X，Y]），
   最大化（X）。
错误的。

乃至：

?- { X < 1 }，最大化（X）。
错误的。

尽管相比之下：

?- { X =< 1 }，最大化（X）。
X = 1.0 。

现在，让我们使用以下技巧来摆脱所有非线性约束：我们简单地将随机浮点数分配给X6和X7，例如使用：

?-向量(Ls),
   Ls = [A,B,C,D,E,F,G],
   映射列表（零到一，Ls），
   随机（F），随机（G）。

在此基础上，我们可以这样写：

?-向量(Ls),
   Ls = [A,B,C,D,E,F,G],
   映射列表（零到一，Ls），
   随机（F），随机（G），
   最大化（A），最小化（B+C+D+E）。
Ls = [1.0, 0.0, 0.0, 0.0, 0.0, 0.9702069686491169, 0.13220925936558517],
A = 1.0，
B = C，C = D，D = E，E = 0.0，
F = 0.9702069686491169，
G = 0.13220925936558517 。

因此，我们获得了满足所有约束并具有一些随机分量的具体解决方案。

结束语

首先，重复一遍，我认为 Prolog 是完成此类任务的不错选择。通过约束求解器进行修剪可以帮助消除大部分搜索空间，并且约束求解器本身可以帮助您通过最小化和最大化来获得具体的解决方案。其次，还有几个问题需要注意：

• 首先，以这种方式（通过任一方法）生成的解决方案不是随机的，因为每个解决方案都有相同的可能性。相反，可能存在比其他解决方案更有可能出现的解决方案簇。
• 如上所示，方程可能需要一些额外的推理和实验，以将它们简化为线性方程并应用适用的优化方向。Prolog 非常适合这种推理，您可以使用它轻松尝试不同的策略。
• 您可能必须在随机化和确定性优化之间找到可行的权衡，以实例化剩余的向量分量。这种权衡还可能取决于载体成分的纠缠。

最后，一个非常重要的评论：隐式随机状态与我们期望的逻辑关系属性背道而驰，因为它们可能导致您的谓词在后续调用中表现得截然不同，从而使调试和系统测试成为一场噩梦。因此，我强烈建议您为随机种子做好准备，或者通过代码携带随机数生成器的显式状态。这将帮助您更好地理解程序的行为并使其完全确定。您稍后可以改变种子以生成不同的解决方案集合。