江苏龙网

  1. 主页 > 生活百科 > >

何时使用约束求解而不是机器学习

机器学习


何时使用约束求解而不是机器学习

文章插图
 
机器学习和深度学习一直是业界的热门话题 。品牌领先于功能，导致深度学习在许多人工智能应用中被过度使用 。
这篇文章将提供对约束求解的快速理解，这是一个强大但未被充分利用的方法，可以解决人工智能和其他计算机科学领域的大量问题，例如物流和调度时间推理和图形问题 。
解决现实问题让我们来考虑一个事实性的和高度话题性的问题 。
病人人数正在上升 。医院必须迅速组织起来治疗病人 。
【何时使用约束求解而不是机器学习】世界上需要一种算法，在疾病严重程度、患者年龄和位置、医院容量和设备等多个标准下，将感染者和医院匹配起来 。
何时使用约束求解而不是机器学习

文章插图
 
许多人会说，神经网络将是最适合它的：它可以有不同的配置，广泛的参数范围，可以根据需要减少到一个独特的解决方案 。
然而，也有一些不利因素会破坏这个方案：
  • 模型需要训练，因此需要以前案例的历史数据，
  • 清理和整合数据集会浪费很多时间，
  • 各种体系结构都需要通过冗长的训练并且要进行测试 。
另一方面，如果用一个布尔可满足性问题来描述，在不确定多项式时间(NP完全问题)中仍然给出次优解，并且不需要任何历史数据的情况下，不会有上述任何缺点 。
这篇文章帮助你快速一览CSPs 。理论和问题的表述将被忽略 。有关更严格的方法，请参考论文，论文在文章的末尾
抽象问题这篇文章将介绍约束编程，旨在解决这个案例 。上面那张图说明了我们算法的输出，应该该算法将感染者与医院匹配 。现有几个框架用于约束求解 。google Optimization Tools(又称Tools)是一个用于解决组合优化问题的开源软件套件 。我们的问题将使用Python中的这个框架进行建模 。
from ortools.sat.python import cp_modelcolab:https://colab.research.google.com/drive/1vFkt5yIQtyelqvCh2TsJ9UDeM5miXqui
参数现在，让我们将问题简化为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：

上一篇：Python安装库太慢？配置好这个速度飞起

下一篇：花旗参茶的营养价值,怀孕可以吃花旗参茶吗