A Partition-Based Optimization Approach for Level Set Approximation: Probabilistic Branch and Bound
A Partition-Based Optimization Approach for Level Set Approximation: Probabilistic Branch and Bound
复制标题
DOI：
10.1007/978-3-030-11866-2_6
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Z. Zabinsky;Hao Huang
中科院分区：
文献类型：
--
作者：
Z. Zabinsky;Hao Huang
我们提出了一个基于分区的随机搜索优化算法，称为概率分支和界限（PBnB），近似水平集，实现用户定义的目标。复杂系统通常用计算机模拟来建模，包括确定性和随机性，决策者可能需要一组接近最优的解决方案，例如具有最佳10%整体性能指标的解决方案，而不是全局最优的单一估计。我们的方法是有效的黑箱，结构不良，嘈杂的功能评估，涉及整数和实值的决策变量。PBnB基于目标分位数的更新的置信区间迭代地维护、修剪或分支有界解空间的子区域。不正确的维护或不正确的修剪区域的最大体积上的时间概率界。因此，用户具有输出的统计量化。例如，在概率大于0.9的情况下，最终维护的子区域在目标水平集合内，其中不正确维护的点的体积小于初始集合的体积的2%。在有噪和无噪测试函数上的数值结果证明了PBnB算法的性能。测试球函数，球形水平集，允许理论界和数值结果之间的比较。PBnB已应用于多个应用领域，包括：天气对空中交通流量管理的影响;丙型肝炎筛查和治疗预算分配的政策决定;将便携式超声机与骨科护理的MRI预留使用相结合;以及使用模拟优化配水网络。
We present a partition-based random search optimization algorithm, called probabilistic branch and bound (PBnB), to approximate a level set that achieves a user-defined target. Complex systems are often modeled with computer simulations, both deterministic and stochastic, and a decision-maker may desire asetof near-optimal solutions, such as solutions with performance metrics in the best 10% overall, instead of a single estimate of a global optimum. Our approach is valid for black-box, ill-structured, noisy function evaluations, involving both integer and real-valued decision variables. PBnB iteratively maintains, prunes, or branches subregions of a bounded solution space based on an updated confidence interval of a target quantile. Finite-time probability bounds are derived on the maximum volume of incorrectly maintained or incorrectly pruned regions. Thus, the user has a statistical quantification of the output. For example, with probability greater than 0.9, the final maintained subregion is inside the target level set with the volume of incorrectly maintained points less than 2% of the volume of the initial set. Numerical results on noisy and non-noisy test functions demonstrate the performance of the PBnB algorithm. Tests on a sphere function, with spherical level sets, allow a comparison between the theoretical bounds and numerical results. PBnB has been applied to several application areas including: weather impacts on air traffic flow management; policy decisions on screening and treatment budget allocation for hepatitis C; combining portable ultrasound machines with reserved MRI usage for orthopedic care; and optimizing water distribution networks using simulation.