寻找允许约束的分区算法

计算科学 算法 分区
2021-12-11 09:57:28

存在哪些根据黑盒评估函数划分域的算法(可能受到一些假设的影响)?

例子

简单示例

为了更好地解释,我们将体重指数(BMI)视为我们的评估函数,计算为mass/height2(质量和高度分别以千克和米给出)。我们假设域为[30,200]×[1,2.5]R×R.

对于给定的 BMI 阈值2530目标是根据阈值划分域。也就是说,对于mass[30,200],height[1,2.5]我想要以下三个分区:

{(mass,height)mass/height2<25}{(mass,height)25mass/height2<30}{(mass,height)30mass/height2}

复杂示例

以下示例阐明了可能适用于评估函数的假设。请注意,我制作了这个例子;我对森林火灾一无所知。

我们希望通过模拟分析森林大火到达城镇需要多长时间。作为我们考虑的相关参数

  • 风速,
  • 风向,
  • 过去 30 天的湿度和
  • 到城镇的距离。

评估函数和假设: 评估函数测量模拟中森林火灾到达村庄的时间。模拟很复杂,它主要被视为一个黑匣子。然而,我们假设评估函数是稳健的,即小的输入变化只会导致小的输出变化。

目标:我们希望将参数空间分类为区域:

  • 小镇不到6小时,
  • 中间到达的小镇612小时和
  • 城镇到达超过12小时。

我的想法

起初我认为这看起来像一个优化问题,但我在这个方向上找不到任何东西。

编辑 1:添加了第二个带有假设的示例,有助于分析域。

1个回答

如果我正确理解您要查找的内容,您似乎想要计算恒定 BMI 的等高线并将其用作边界来分隔您的域?

一个非常简单的近似算法是行进正方形算法。

该算法的一般前提是将域离散化为矩形单元格,并评估要在该网格上找到轮廓的函数。然后对于每个单元格,确定函数的值是大于还是小于所需的轮廓。

一旦有了这个一般的真/假数组,就可以使用 4 个相邻单元格的查找表来大致确定轮廓在这 4 个单元格中心之间的外观。请注意,您可能需要做一些额外的工作来消除鞍点的歧义(有关更多详细信息,请参阅 Wikipedia 文章)。

这个过程已经被大量用于分析大多数绘图库都内置的科学数据,尽管据我所知,这些库中实际上并没有多少给你提供近似轮廓边界的路径。

这是一个使用 Matplotlib 生成等高线图的示例:

from numpy import *
from matplotlib.pyplot import *

mass,height = meshgrid(linspace(30, 200, 400), linspace(1, 2.5, 400))

bmi = mass / height**2

contourf(mass, height, bmi, [25, 30], extend='both')
colorbar()
xlabel('mass')
ylabel('height')
tight_layout()

在此处输入图像描述

这个算法当然有局限性,特别是如果您为网格选择的分辨率大于任何“岛”轮廓,则根本找不到这些轮廓。