时间戳

首页 > 解决方案 > 使用或工具在约束空间中实现无偏随机化

python - 使用或工具在约束空间中实现无偏随机化

问题描述

我有一个带有or-tools的简单代码，我尝试随机化 3 个变量，使它们的总和是一个常数。我还添加了随机提示，以便求解器每次都会给出不同的结果。但是，当我尝试查看不同值的频率时，只有第一个变量似乎是无偏的或遵循均匀分布，而所有其他变量都偏向 0。

这是代码

from ortools.sat.python import cp_model
import numpy as np
import matplotlib.pyplot as plt

model = cp_model.CpModel()

mx = 500
x = model.NewIntVar(0, mx, 'x')
y = model.NewIntVar(0, mx, 'y')
z = model.NewIntVar(0, mx, 'z')

freqX = [0] * (mx + 1)
freqY = [0] * (mx + 1)
freqZ = [0] * (mx + 1)

model.Add(x + y + z == mx)
solver = cp_model.CpSolver()
solver.parameters.cp_model_presolve = False

for i in range(10000):
    model.ClearAssumptions()
    model.ClearHints()
    model.AddHint(x, np.random.randint(0, mx))
    model.AddHint(y, np.random.randint(0, mx))
    model.AddHint(z, np.random.randint(0, mx))
    
    status = solver.Solve(model)
    
    freqX[solver.Value(x)] += 1
    freqY[solver.Value(y)] += 1
    freqZ[solver.Value(z)] += 1

plt.subplot(311)
plt.bar(range(mx+1), freqX, width=1.0)
plt.subplot(312)
plt.bar(range(mx+1), freqY, width=1.0)
plt.subplot(313)
plt.bar(range(mx+1), freqZ, width=1.0)
plt.savefig('foo.svg')

这是输出

在此处输入图像描述

使变量遵循均匀分布/无偏的最具可扩展性的方法是什么

PS：下面是我在评论中建议的带有无效提示的分布。

在此处输入图像描述

标签： pythonor-tools

解决方案

提示的工作方式如下：

  • 搜索按顺序获取提示，并尝试在提示中的值上进行分支。
  • 如果该值当时不是变量域的一部分，则选择下一个变量
  • 当失败发生时，它会回溯并选择另一个值/变量。
  • 在 10 次失败后，它逐渐恢复到默认启发式（最小域，最小值）。

所以：

  • 如果问题很简单，提示是有效的，分布会很好
  • 如果约束开始传播，并使提示无效，由于变量的顺序，最后一个将偏向于 (a) 有效部分和 (b) 启发式值。

结论：

  • 只需尝试随机化提示中的变量顺序 :-)

推荐阅读