多目标随机仿真模型的帕累托排序识别方法

《Computers & Operations Research》：Pareto ranking identification for multi-objective stochastic simulation models

　　摘要
多目标随机模拟广泛用于评估具有冲突性能指标的候选设计，但模拟噪声使得可靠地确定帕累托优势关系变得成本高昂。排序和选择（R&S）方法通过选择性分配模拟重复次数来降低这一成本；然而，现有的多目标R&S方法主要关注于选择第一个帕累托集。实际上，决策者可能还需要较低帕累托排名的备选方案，因为最终决策可能会受到模拟模型无法捕捉到的定性、操作性或政治因素的影响。本研究提出了一种R&S方法，用于识别帕累托排名集，这些集被定义为连续的非支配备选方案层，直到用户指定的排名?。所提出的方法评估观察到的帕累托排名结构的统计证据，并顺序地为排名仍不确定的设计分配额外的重复次数。实验表明，与等量分配和顺序帕累托集选择基线相比，所提出的方法所需的重复次数显著较少。额外的结果显示，该方法在目标相关性存在的情况下以及在实际模拟案例研究中仍然有效。此外，将其与非支配排序遗传算法II（NSGA-II）结合使用可以提升噪声环境中的多目标进化优化性能。

引言
离散事件动态系统的模拟模型通常通过随机输出来捕捉现实世界系统中的不确定性和随机性（Dagkakis等，2019；Li等，2021；Tsai等，2023）。然而，当使用模拟模型分析和优化系统性能时，这种随机性可能会引发效率问题。特别是，可能需要大量的模拟重复次数来减少输出噪声并准确估计系统设计的平均性能，例如决策变量的配置（Jalali等，2017）。当设计数量适中（例如几百个）时，可以采用排序和选择（R&S）中的模拟预算分配方法。基于序数优化的R&S方法并不试图高精度地估计所有设计的平均性能。相反，它们将模拟资源集中在可能有最优解的有希望的设计上，从而减少了正确选择所需的预算。为此，分配方法迭代地为当前模拟结果提供额外的重复次数，以加强选择最优设计的统计证据（Chen & Lee，2011）。
已经开发了多种R&S方法，主要基于三种方法：无差异区（IZ）方法（Kim & Nelson，2006）、最优计算预算分配（OCBA）（Chen等，2000）和期望值信息（EVI）（Chick & Inoue，2001）。每种方法都有其优缺点，详细比较可以在Branke、Chick和Schmidt（2007）中找到。此外，最近还提出了一种基于假设检验的不确定性评估（UE）方法（Choi & Kim，2018b）。尽管这种方法有些启发式，但它因对噪声具有高度鲁棒性而实用。此外，使用速率估计器的优化采样标准（SCORE）方法最近在多目标领域受到了关注（Pasupathy等，2014；Applegate等，2020；Feldman和Hunter，2018）。表1总结了基于这些方法的几种主要问题类别的代表性R&S方法（Xu等，2015）。
虽然大多数现有研究都集中在选择最优设计上，但少数研究考虑了根据所有设计的平均性能来识别其完整排名，因为排名信息在许多应用中是有用的（Xiao、Gao和Lee，2020）。Beirlant、Dudewicz和Van Der Meulen（1982）提出了一种基于IZ方法的两阶段分配方法来识别完整排名。Xiao、Lee和Ng（2014）开发了一种基于OCBA的方法，并额外考虑了输入不确定性（Xiao、Gao和Lee，2020）。Choi和Kim（2020a）提出了一种基于UE的方法来选择最优子集并对其元素进行排名，当子集涵盖整个集合时，可以扩展到完整排名识别。完整排名识别允许从业者在考虑模拟未捕获的条件（如定性标准和政治可行性）的情况下选择最合适的設計（Xiao、Lee和Ng，2014）。它还可以与基于群体的搜索算法（如进化算法）结合使用，以在噪声环境中提高其性能（Schmidt等，2006）。
尽管完整排名识别很有用，但现有研究主要关注单目标领域。然而，在实践中，许多问题需要同时考虑多个性能指标，例如排队系统中的过程利用率和等待时间。一种应用单目标排序方法的方法是使用多属性效用函数等函数将多个指标合并为一个指标（Butler、Morris和Mullarkey，2001）。然而，所得到的排名在很大程度上取决于所选的组合函数，而且找到合适的函数往往很困难（Lee等，2010a）。或者，可以使用基于帕累托最优性的帕累托排名（Deb，2001）。在帕累托排名中，属于帕累托集的设计被赋予第一排名。然后，在剩余的设计中，属于帕累托集的设计被赋予第二排名，其他较低排名的集合以相同的方式获得。图1(a)展示了一个帕累托排名的例子。
类似于单目标领域的完整排名，帕累托排名可以为多目标领域的最终决策提供有用的信息。例如，在确定共享自行车系统的运营策略时，应同时考虑多个性能指标，如运营成本、市民便利性和利用率（Bae等，2024）。即使某些策略属于第一个帕累托集，由于模拟模型未明确捕捉到的实际因素（如政治可行性、环境条件或管理偏好），它们也可能难以实施。在生产调度和重新调度中也会出现类似的情况，基于模拟指标（如完工时间、延误次数和延误作业数量）得出的第一排名帕累托调度在考虑车间中断或调度稳定性后可能难以实施（Holguin Jimenez等，2024；Tai等，2024）。在这种情况下，较低帕累托排名的集提供了仍符合模拟目标的备选方案。
是否需要较低排名的集取决于决策背景。在多目标领域，多个设计可能属于同一个帕累托排名，如图1(a)所示。如果第一个帕累托集已经包含足够多的可接受设计，则识别较低排名的集可能是不必要的。然而，当第一个帕累托集较小、部分不可行或在实际筛选后不足时，帕累托排名就变得有用，因为它提供了更多有希望的备选方案。同时，识别所有帕累托排名集通常是不切实际且不必要的，特别是当较低排名的设计在最终决策中不太可能被考虑时。这激发了只识别用户指定排名?的帕累托排名的需求，而不是要求完整的帕累托排名。
帕累托排名对于多目标进化算法（MOEAs）也很重要，例如在噪声环境中的非支配排序算法II（NSGA-II）（Deb等，2002）。由于NSGA-II基于帕累托排名选择父代，因此准确识别群体内的排名可以减少模拟噪声的不利影响。
在这项研究中，我们提出了一种模拟预算分配方法，用于识别通过多目标随机模拟模型评估的设计的帕累托排名。与表1中现有的帕累托集选择方法不同，这些方法关注的是排名1的非支配集，所提出的问题考虑了分层的帕累托排名集。从这个意义上说，它将完整排名识别从单目标R&S扩展到了多目标设置，其中排名结构由多个帕累托排名集表示，而不是单个设计的总顺序。反映上述实际动机，所提出的方法只识别给定?-th排名内的帕累托排名。
所提出的方法基于UE方法，该方法对噪声具有高度鲁棒性，非常适合实际应用。与基于OCBA的方法（如MOCBA（Lee等，2010a）和MOCBA+（Li等，2018）（Choi & Kim，2020b）相比，它在多目标领域的分配计算中也提供了较低的计算复杂性。这一优势对于需要重复搜索的MOEAs尤为重要。所提出的方法旨在在有限的模拟重复次数下，即在固定预算设置中，最大化正确识别?-th排名???{?????}的概率（Branke等，2007；Xu等，2015）。遵循UE方法，它评估每个设计的当前模拟结果，以确定它们是否为观察到的帕累托排名结构提供了足够的统计证据，并在必要时分配额外的重复次数。实验结果证明了所提出方法的效率，其与NSGA-II的结合进一步表明它可以在噪声环境中提高MOEA的性能。
本文的其余部分组织如下。第2节阐述了问题，第3节介绍了所提出的帕累托排名识别方法。第4节报告了实验结果，第5节总结了本文。

问题阐述
表2总结了本研究中使用的基本符号。粗体符号表示向量。

假设1
每个目标的模拟输出遵循具有未知均值和方差的正态分布。在模拟之前，没有关于这些参数的先验信息。
在随机模拟中，输出通常被定义为平均值或批次均值。因此，根据中心极限定理（Chen & Lee，2011），正态性假设是合理的。

假设2
对于任何两个不同的设计????和

所提出的方法
本节介绍了所提出的模拟预算分配方法。第3.1节定义了支配关系的成对不确定性分数。第3.2节推导了正确识别帕累托排名集的充分条件。第3.3节使用这些结果定义了设计级别的不确定性，3.4节描述了分配策略，3.5节描述了顺序更新程序。

数值实验
为了证明帕累托排名识别中模拟效率的提高，我们使用了三个用于评估多目标领域R&S方法的基准问题（Lee等，2010a；Lee等，2010b；Chen和Lee，2011；Choi和Kim，2020b；Andradóttir和Lee，2021）。这些基准问题最初是为帕累托集选择设计的，主要目标是排名1的非支配集。因此，帕累托集之外的设计之间的区分并不是重点。

结论
本研究提出了一种模拟预算分配方法，用于在多目标随机模拟中识别用户指定排名?的帕累托排名集。与关注排名1非支配集的现有帕累托集选择方法不同，所提出的方法考虑了分层的帕累托排名结构，并旨在在有限的模拟预算下提高正确识别的概率???{?????}。我们首先推导了指定支配关系的充分条件。

作者贡献声明
Byeong Soo Kim：撰写——原始草稿，软件，调查，形式分析，数据管理。
Seon Han Choi：撰写——审阅与编辑，验证，项目管理，方法论，资金获取。

利益冲突声明
作者声明他们没有已知的竞争财务利益或个人关系可能影响本文报告的工作。

致谢
这项工作得到了韩国国家研究基金会（NRF）的资助，该基金会由科学和ICT部（MSIT，韩国）资助（RS-2025-23523897；RS-2026-25490339），以及由中小企业和初创企业部（MSS，韩国）资助的启动增长技术研发计划（RS-2025-23822975）的部分支持。

Byeong Soo Kim
Seon Han Choi
首尔国立科学技术大学应用人工智能系，韩国首尔01811