random - 将 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]),
map 列表(零到一，[A，B，C，D，E，F，G])，
随机(A)，
随机(B)，
随机(C)。

这再次产生 false .

方法 1:更多相同

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

?- 向量([A,B,C,D,E,F,G]),
map 列表(零到一，[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/1从 CLP(R) 使用约束求解器本身来获得具体的解决方案。这仅适用于 线性 约束，甚至不是所有这些。例如，考虑以下查询:

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

乃至:

?- { X < 1 }，最大化(X)。
错误的。

虽然相反:

?- { X =< 1 }, 最大化(X)。
X = 1.0。

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

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

在此基础上，我们可以写:

?-向量(Ls)，
Ls = [A,B,C,D,E,F,G],
map 列表(零到一，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 非常适合这种推理，您可以使用它轻松尝试不同的策略。

您可能必须在随机化和确定性优化之间找到一个有效的折衷，以实例化剩余的向量分量。权衡也可能取决于矢量分量的纠缠。

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