作者|Antoine Champion
编译|VK
起源|Towards Data Science

机器学习和深度学习始终是业界的热门话题。品牌当先于性能，导致深度学习在许多人工智能利用中被适度应用。

这篇文章将提供对束缚求解的疾速了解，这是一个弱小但未被充分利用的办法，能够解决人工智能和其余计算机科学畛域的大量问题，例如物流和调度工夫推理和图形问题。

解决事实问题

让咱们来思考一个事实性的和高度话题性的问题。

病人人数正在回升。医院必须迅速组织起来医治病人。

世界上须要一种算法，在疾病重大水平、患者年龄和地位、医院容量和设施等多个规范下，将感染者和医院匹配起来。

许多人会说，神经网络将是最适宜它的：它能够有不同的配置，宽泛的参数范畴，能够依据须要缩小到一个独特的解决方案。

然而，也有一些不利因素会毁坏这个计划：

  • 模型须要训练，因而须要以前案例的历史数据，
  • 清理和整合数据集会节约很多工夫，
  • 各种体系结构都须要通过简短的训练并且要进行测试。

另一方面，如果用一个布尔可满足性问题来形容，在不确定多项式工夫(NP齐全问题)中依然给出次优解，并且不须要任何历史数据的状况下，不会有上述任何毛病。

这篇文章帮忙你疾速一览CSPs。实践和问题的表述将被疏忽。无关更严格的办法，请参考论文，论文在文章的开端

形象问题

这篇文章将介绍束缚编程，旨在解决这个案例。下面那张图阐明了咱们算法的输入，应该该算法将感染者与医院匹配。现有几个框架用于束缚求解。Google Optimization Tools(又称Tools)是一个用于解决组合优化问题的开源软件套件。咱们的问题将应用Python中的这个框架进行建模。

from ortools.sat.python import cp_model

colab:https://colab.research.google...

参数

当初，让咱们将问题简化为4个参数(1)：

  • 感染者所在地
  • 感染者的重大水平
  • 医院地位
  • 每家医院的床位数

让咱们用python定义这些参数：

# 医院数量n_hospitals = 3# 感染者人数n_patients = 200# 每家医院的床位数n_beds_in_hospitals = [30,50,20]# 病人地位，tuple (x,y)patients_loc = [(randint(0, 100), randint(0, 100)) for _ in range(n_patients)]# 医院地位，tuple (x,y)hospitals_loc = [(randint(0, 100), randint(0, 100)) for _ in range(n_hospitals)]  # 病人重大等级 1~5patients_severity = [randint(1, 5) for _ in range(n_patients)]

变量

束缚满足问题由一组变量组成，这些变量必须以满足一组束缚。

  • 令I为医院的汇合
  • 令$J_i$为医院i的床位汇合
  • 令$K$为病人汇合

定义变量的索引族：

如果在医院i中，床j由病人k取走，则$x_{ijk} = 1$。为了将医院的每一张床与一个病人分割起来，咱们的指标是找到一组满足所有约束条件的变量。

咱们能够将这些变量增加到模型中：

model = cp_model.CpModel()x = {}for i in range(n_hospitals):  for j in range(n_beds_in_hospitals[i]):    for k in range(n_patients):      x[(i,j,k)] = model.NewBoolVar("x(%d,%d,%d)" % (i,j,k))

硬束缚

硬束缚定义了模型的指标。它们是必不可少的，如果它们得不到解决，就无奈解决问题：

  • 每张床上最多只能有一个人
  • 每个人最多只能有一张床

让咱们关注第一个硬束缚。对于每家医院的每一张床，我：

  • 要么有一个惟一的病人k，
  • 要么床是空的。

因而，能够用以下形式示意：

咱们的求解器是一个组合优化求解器，它只能解决整数束缚。因而，必须转化为一个整数方程：

这个不等式能够加到咱们的模型中。

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

接下来，第二个硬束缚：对于每个患者k：

  • 要么他在一个惟一的病床上j在一个惟一的医院i
  • 要么他在家。

同理，能够转化为一个整数不等式:

最初，能够将此束缚增加到模型中。

# 每个人最多只能睡一张床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.

原文链接：https://towardsdatascience.co...

欢送关注磐创AI博客站：
http://panchuang.net/

sklearn机器学习中文官网文档：
http://sklearn123.com/

欢送关注磐创博客资源汇总站：
http://docs.panchuang.net/