5

我正在寻找使用 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 实例。那就足够了吗？

4

1 回答 1

3

没关系！

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

但是，您需要解决一些细微的问题。

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

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

请特别注意表示 CLP(R) 约束的使用=<和正确使用。{}/1Prolog 算术中避开了该标记<=，因为它看起来像一个箭头，通常表示证明者中的暗示。

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

?- 向量（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(zero_to_one, [A,B,C,D,E,F,G]),
   随机（A），
   随机（B），
   随机（C）。

这再次产生false。

方法1：更多相同

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

?- 向量([A,B,C,D,E,F,G]),
   maplist(zero_to_one, [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}。

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

方法二：最大化或最小化

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

?- { X = sin(Y) },
   地图列表（zero_to_one，[X，Y]），
   最大化（X）。
错误的。

乃至：

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

虽然相反：

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

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

?- 向量（Ls），
   Ls = [A,B,C,D,E,F,G],
   地图列表（zero_to_one，Ls），
   随机（F），随机（G）。

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

?- 向量（Ls），
   Ls = [A,B,C,D,E,F,G],
   地图列表（zero_to_one，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 非常适合这种推理，您可以使用它轻松尝试不同的策略。
  • 您可能必须在随机化和确定性优化之间找到一个有效的折衷方案，以实例化剩余的向量分量。权衡也可能取决于向量组件的纠缠。

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

于 2017-05-08T13:27:13.777 回答