何时使用约束求解而不是机器学习( 二 ) _机器学习

文章插图

同理，可以转化为一个整数不等式:

文章插图

最后，可以将此约束添加到模型中。

# 每个人最多只能睡一张床for k in range(n_patients):inner_sum = []for i in range(n_hospitals):inner_sum.Append(sum(x[(i,j,k)] for j in range(n_beds_in_hospitals[i])))model.Add(sum(inner_sum) <= 1)

软约束接下来是软约束。这些都是非常需要的：我们的解决方案必须尽可能满足它们，但它们不是找到解决方案的必要条件：

每个病人都应该躺在床上
每个人都应该由最近的医院处理
病床不足时，应先处理病情严重的病人

当硬约束被建模为等式或不等式时，软约束是最小化或最大化的表达式。
设Ω为满足硬约束的所有解的集合。

文章插图

每一个病人都应该被安排在一张床上，这意味着最大限度地增加被占用的床的数量。

文章插图

每个人都应该由最近的医院处理，以尽量减少每个病人与其指定医院之间的距离。

文章插图

如果没有足够的床位，应首先处理病情严重的病人，以最大限度地提高所有处理病人的总严重程度。通过表示sev(k)患者k的严重程度：

文章插图

然后我们可以将所有软约束简化为一个目标：

文章插图

需要注意的是：这些软约束没有相同的定义域。

患者最大化约束范围从0到n，其中n是患者数，
病情严重性限制范围从0到5n
距离约束范围从0到所有i和k的最大欧几里得距离。

考虑到所有这些约束具有相同的优先级，我们必须定义惩罚因子来平衡不同的约束。
下面是相应的代码：

# 整数的距离函数idist = lambda xy1, xy2: int(((xy1[0]-xy2[0])**2 + (xy1[1]-xy2[1])**2)**0.5)gain_max_patients = 140gain_severity = int(140/5)gain_distance = -1#最大化的目标soft_csts = []for i in range(n_hospitals):for j in range(n_beds_in_hospitals[i]):for k in range(n_patients):factor =gain_max_patients+ gain_distance * idist(hospitals_loc[i], patients_loc[k])+ gain_severity * patients_severity[k]soft_csts.append(factor * x[(i,j,k)])model.Maximize(sum(soft_csts))

求解现在我们可以启动求解器了。它将试图在指定的时间限制内找到最优解。如果无法找到最优解，则返回最近的次优解。
solver = cp_model.CpSolver()solver.parameters.max_time_in_seconds = 60.0status = solver.Solve(model)在我们的例子中，求解器在2.5秒内返回一个最优解。

文章插图

结论要创建这个解决方案，只需要1小时的研究和30分钟的编程。
如果使用深度学习，要进行几天的数据清理，至少一天测试不同的架构，另一天进行训练。
此外，如果模型良好，CP-SAT模型是非常健壮的。下面是不同模拟参数的结果。结果在许多不同的情况下仍然是一致的，随着模拟参数的增加（3000名患者，1000张病床），解决方案推断只需不到3分钟。

文章插图

当然，csp几乎不适用于计算机视觉和NLP等主题，在这些主题中，深度学习有时是最好的方法。然而，在物流、调度和计划方面，这往往是可以实现的方法。
深度学习的炒作激发了一些人尝试一些疯狂的举动来获得认可。有时，最好还是通过阅读几篇关于你正在研究的问题的调查报告再想想你应该如何解决。
引用[1] Jingchao Chen, Solving Rubik’s Cube Using SAT Solvers, arXiv:1105.1436, 2011.
[2] Biere, A., Heule, M., and van Maaren, H. Handbook of satisfiability, volume 185. IOS press, 2009a
[3] Knuth, D. E., The art of computer programming, Volume 4, Fascicle 6: Satisfiability. Addison-Wesley Professional, 2015
[4] Vipin Kumar, Algorithms for constraint-satisfaction problems: a survey, AI Magazine Volume 13, Issue 1, 1992.