如何在Z3-Python中使用软约束来表达SAT搜索中的'abstract'偏差:如'I prefer half of the literals to be true and half false'
How to use soft constraints in Z3-Python to express 'abstract' biases in SAT search: such as 'I prefer half of the literals to be true and half false'
我之前在 中问过,在 Z3 (Python) 中是否有办法 'bias' SAT 搜索 'criteria'?
在那post中,我们学习了'simple biases'例如我希望Z3获得一个模型,但不是任何模型:if possible,给我一个有大量否定字面量的模型
这是使用新求解器(Optimize
而不是 Solver
)和软约束(add_soft
而不是 add
)执行的。具体来说,对于每个文字 lit_n
和优化求解器 o_solver
,添加了:o_solver.add_soft(Not(lit_n))
;或者,等价地:o_solver.add_soft(Or(Not(lit1), Not(lit2), ...)
.
不过,我想表达一个'little more complicated biases'。具体来说:如果可能:我更喜欢一半文字的模型为真,一半为假 .
有什么方法可以使用 Optimize
工具来表达这个和类似的 'biases'?
这里有一个可能有用的简单想法。计算正文字的数量并从负文字的数量中减去。取差异的绝对值并使用优化器将其最小化。
这应该找到正负文字数量尽可能接近的解决方案,满足您的“大约一半”软约束。
这是一个简单的例子。假设您有六个文字并且您想要满足它们的析取。惯用的解决方案是:
from z3 import *
a, b, c, d, e, f = Bools("a b c d e f")
s = Solver()
s.add(Or(a, b, c, d, e, f))
print(s.check())
print(s.model())
如果你运行这个,你会得到:
sat
[f = False,
b = False,
a = True,
c = False,
d = False,
e = False]
所以,z3 只是让 a
True
和所有其他 False
。但是您希望正面和负面文字的数量大致相同。那么,让我们对其进行编码:
from z3 import *
a, b, c, d, e, f = Bools("a b c d e f")
s = Optimize()
s.add(Or(a, b, c, d, e, f))
def count(ref, xs):
s = 0
for x in xs:
s += If(x == ref, 1, 0)
return s
def sabs(x):
return If(x > 0, x, -x)
lits = [a, b, c, d, e, f]
posCount = count(True, lits)
negCount = count(False, lits)
s.minimize(sabs(posCount - negCount))
print(s.check())
print(s.model())
注意我们如何“象征性地”计算负文字和正文字并要求 z3 最小化差异的绝对值。如果你 运行 这个,你会得到:
sat
[a = True,
b = False,
c = False,
d = True,
e = False,
f = True]
有 3 个正字面量和 3 个负字面量。如果您有 7 个文字开始,它会发现 4-3 拆分。如果您更喜欢正文字而不是负文字,则可以另外添加以下形式的软约束:
s.add_soft(posCount >= negCount)
以这种方式偏置求解器。希望这能让你开始..
我之前在
在那post中,我们学习了'simple biases'例如我希望Z3获得一个模型,但不是任何模型:if possible,给我一个有大量否定字面量的模型
这是使用新求解器(Optimize
而不是 Solver
)和软约束(add_soft
而不是 add
)执行的。具体来说,对于每个文字 lit_n
和优化求解器 o_solver
,添加了:o_solver.add_soft(Not(lit_n))
;或者,等价地:o_solver.add_soft(Or(Not(lit1), Not(lit2), ...)
.
不过,我想表达一个'little more complicated biases'。具体来说:如果可能:我更喜欢一半文字的模型为真,一半为假 .
有什么方法可以使用 Optimize
工具来表达这个和类似的 'biases'?
这里有一个可能有用的简单想法。计算正文字的数量并从负文字的数量中减去。取差异的绝对值并使用优化器将其最小化。
这应该找到正负文字数量尽可能接近的解决方案,满足您的“大约一半”软约束。
这是一个简单的例子。假设您有六个文字并且您想要满足它们的析取。惯用的解决方案是:
from z3 import *
a, b, c, d, e, f = Bools("a b c d e f")
s = Solver()
s.add(Or(a, b, c, d, e, f))
print(s.check())
print(s.model())
如果你运行这个,你会得到:
sat
[f = False,
b = False,
a = True,
c = False,
d = False,
e = False]
所以,z3 只是让 a
True
和所有其他 False
。但是您希望正面和负面文字的数量大致相同。那么,让我们对其进行编码:
from z3 import *
a, b, c, d, e, f = Bools("a b c d e f")
s = Optimize()
s.add(Or(a, b, c, d, e, f))
def count(ref, xs):
s = 0
for x in xs:
s += If(x == ref, 1, 0)
return s
def sabs(x):
return If(x > 0, x, -x)
lits = [a, b, c, d, e, f]
posCount = count(True, lits)
negCount = count(False, lits)
s.minimize(sabs(posCount - negCount))
print(s.check())
print(s.model())
注意我们如何“象征性地”计算负文字和正文字并要求 z3 最小化差异的绝对值。如果你 运行 这个,你会得到:
sat
[a = True,
b = False,
c = False,
d = True,
e = False,
f = True]
有 3 个正字面量和 3 个负字面量。如果您有 7 个文字开始,它会发现 4-3 拆分。如果您更喜欢正文字而不是负文字,则可以另外添加以下形式的软约束:
s.add_soft(posCount >= negCount)
以这种方式偏置求解器。希望这能让你开始..