英语原文共 14 页

摘要：近年来，针对多目标不确定优化问题提出了若干鲁棒性概念，但解决方法较少。本文介绍了基于标量化的最小鲁棒高效解的两种方法:最小排序法和最大排序法。证明了最大序方法可以找到基于点的最小鲁棒弱有效解，最小序方法可以找到基于集合的最小-最大鲁棒弱有效解，其中一些是以前发展的基于标量化的方法所不能找到的。研究了一类具有特殊不确定集的多目标不确定组合优化问题的尺度化问题。摘要针对有界不确定性(又称预算不确定性或r不确定性)的多目标扩展，建立了一种紧凑的混合整数线性规划公式。对于区间不确定性，我们证明了所得到的问题可以归结为已知的单目标问题。

介绍

当将优化技术应用于实际问题时，常常会遇到这样的困难，即需要同时优化多个目标，而且并非所有参数都是预先知道的。在多目标优化中，通过选择一种(帕累托)ef-ficient溶液，同时对多个目标进行优化。鲁棒优化是一种处理不确定性的方法，不需要假设任何概率分布的信息，以对冲(所有)可能的结果。在过去的几年里，这些领域的概念被结合到多目标鲁棒优化中。

提出了多目标优化中如何定义鲁棒解的几个概念。Tin-Tax鲁棒性的公共(单目标)概念旨在找到在最坏情况下最小化目标函数的解决方案。Kuroiwaand Lee(2012)首先提出了多目标优化的一种推广，我们称之为基于点的最小税鲁棒效率。它们独立地考虑每个目标的最坏情况，从而得到一个具有瓶颈目标函数的确定性多目标问题，称为鲁棒可数部分。然而，解决方案的最坏情况点可能与可能的结果有很大不同。因此，Ehrgott、Ide和Schobel(2014)对多目标的最小-最大鲁棒性进行了二次推广。他们查看每个场景下解决方案的结果集，并将这些集相互比较，以找到所谓的基于集合的最小税稳健有效的解决方案。Ide和Schobel(2016)以及wiecek和Dranichak(2016)对这两个概念和其他鲁棒效率概念进行了比较。

在确定性情况下，即没有不确定性的情况下，寻找有效解的常用方法是所谓的标度化方法，即将多目标问题转化为一类单目标问题，其解对原问题的有效性(弱)。通过解决产生的问题，可以找到几种不同的(可能是所有的)有效的解决方案。有关标量化方法的概述，请参见Ehrgott(2006)。

在不确定的情况下，已经开发了几种基于标量化的求最小二乘最优解的方法:基于加权和和a约束的标量化(Ehrgott et al, 2014)，基于增广加权舍比雪维化(lde(2014))和基于p·范数的标量化(Bokrantz amp;Fredriksson, 2017)。基于点的最小-最大鲁棒有效解扫描也可以通过将确定性sc al方法应用到鲁棒对应物中来找到(参见Fliege amp; Werner, 2014;哈桑-扎德，Nemati， amp; Sun, 2013;Kuroiwa amp; Lee, 2012)。

在本文中,我们介绍两个新方法找到最小maxrobust高效解决方案基于数值:马克斯orderingand min -排序方法,导致形成极大极小问题的最大分别最小最大值最小值。最小值的-订购problemcan因此被解释为一个所谓的可调健壮prob-lem(Ben-Tal,Goryashko Guslitzer 8 Nemirovski,2004),在那上面的一部分必须做出决策之前realizationof不确定的参数。

在鲁棒优化中，考虑的不确定性集，即，不确定参数所能获得的可能值，对由此产生的ro-bust问题的w.r.t.可解性和复杂性起着至关重要的作用。摘要研究了具有特定未知污染集的多目标最小-最大鲁棒组合优化问题的最小排序和最大排序优化问题:一个流行的假设是cach参数在给定区间内具有一个独立于实现的值。其他参数(iinterval不确定性)。在此基础上，Bertsimas和Sim(2003)引入了有界不确定性的(单目标)概念，假设参数以区间变化，但并不是所有参数si=同时变化的最坏情况。简略的概念已被广泛的研究鲁棒优化也下budgeteduncertainty的名字或r-uncertainty,不确定性集基于有界不确定性的多objectiveoptimization一直consideredin杜利特尔,Kerivin,和Wiecek(2012)和Wang,叮,太阳,和王(2017)(只考虑约束)的不确定性和Hassanzadeh et al。(2013)和Raith,施密特Schobel,andThom(2018 b)(导致一组objective-wise不确定性)。摘要针对多目标优化中存在的不确定性不是相互独立的情况，将有界不确定性推广到多目标优化中。

Raith等人(2018b)提出了具有目标有界不确定性的多目标最小-最大鲁棒组合问题的求解方法。Kuhn, Raith, Schmidt, and schobel(2016)针对若干鲁棒性概念，考虑具有有限和多面不确定性集的双目标鲁棒组合问题lems。Raith、Schmidt、Schobel和Thom (2018a)考虑了具有有限不确定性集的最短路径问题的多目标鲁棒版本，其中对标记算法进行了扩展，以找到鲁棒有效的解决方案。

本文的结构如下:首先，给出了多目标鲁棒优化的一个简短介绍。在第三节中，我们介绍了最小序优化问题和最大序优化问题，并给出了它们的一般性质。在第4节中，我们考虑了带有粒子不确定性集的组合多目标优化问题，并研究了由此产生的最小序和最大序问题的复杂性和可解性。

2、准备工作：

在这一节中，我们将介绍一些通用的符号，并简要介绍多目标优化和多目标鲁棒优化。

在本文中,我们使用这些符号lt;(严格小于)和lt;=(小于或等于)比较值r .另外，用来表示集合M的边界，用i属于[k]来表示i属于{1,2，hellip;hellip;，k}.

2.1多目标鲁棒优化

定义1：给定一组x为可行解且，于是我们可以称以下是一个多目标优化问题（MOP）：

如果k=1，我们说这个问题是一个单目标问题。对于kgt;=2，同时最小化所有目标的解决方案通常不存在。因此，我们使用有效解的概念。

定义2：对于两个向量，我们使用如下定义：

同时，我们也定义。

定义3：解决方案对于MOP问题来说是一个强还是弱的有效解决方案，要看是否有。请注意，解决方案[弱/·/严格]有效的前提是且仅当没有与

我们现在假设输入数据是不确定的，即，并不是所有的参数都是事先确切知道的。相反，他们依赖于一个可能的情况，只有在一个人选择了一种解决方案后才会显露出来。所有可能情形的集合U称为不确定性集合。

定义4：给定一套可行的解决方案x,一个不确定性集合u,和一个多目标函数 ，那么这类的多目标优化问题就被称作不确定性的多目标优化问题（MOUP）。

在下面，我们假设X和U是紧致的，非空的，Z是连续的，在X和y中。如果一个问题或一个问题的一部分不受不确定性的影响，我们说它是确定性的，例如，对于U=1的a (MOUP)的情况。

注意，定义4中的提法只考虑了目标函数中的不确定性。如果约束条件，即(见bental amp; Nemirovski, 1998;Soyster, 1973)。为此，在所有情形下的可行解集合可以提前相交，得到一组鲁棒可行解(deter-ministic)集合。因此，在下面，我们假设可行集X是确定性的。

对于一个多目标不确定的问题，决定什么是一个好的解决方案并非易事。在单目标鲁棒优化中，寻找所谓的鲁棒最优解。其中有10个定义为具有最小最坏情况值的解，即(见，如Ben-Tal,El Ghaoui， amp; Nemirovski, 2009)。这一概念已经以各种方式推广到多目标问题的鲁棒效率(例如，Ehrgott et al.， 2014;(Kuroiwa amp; Lee, 2012)，因为在多目标情况下，最坏情况的概念并不明确。

我们提出了两个最常见的最小二乘鲁棒效率概念:基于点的最小二乘鲁棒效率和基于集的最小二乘鲁棒效率。对于基于点的最优鲁棒效率，我们分别确定每个解x和满射i的最坏情况，并比较解w.r.t.和结果点Z(x)。对于基于集合的最小-最大鲁棒效率,我们正在寻找是否存在一个解决方案使 。

定义5 (Ehrgott et al.， 2014;Kuroiwa amp; Lee, 2012)。给出了一个多目标不确定优化问题的定义如下：

解是基于点的最小最大鲁棒[弱/·/严格]对(MOUP)有效(缩写:pointMR[弱/·/严格]效率)，如果是对应于鲁棒的[弱/·/严格]有效解，即，没有，使得成立

定义函数，解决方案是基于集合的最小最大鲁棒[弱/·/严格]对(MOUP)有效解。即，没有，使得成立。

当k = 1时，这两个概念都可归结为最小-最大鲁棒性，即，则点MR有效解和集合MR有效解与的解相同。注意，如果(MOUP)在目标上是不确定的，那么每个点MR[弱/严格]有效的解决方案也对集合MR[弱/严格]是有效的，并且这两个概念在和两个条件成立的情况下是一致的。

例6设多目标不确定优化问题为,且

下图1a表示了和，下图1b表示了和，

图1a(左)、图1b(右)

所有的三种方法对集合MR解决都是有效的，但是只有对点MR是有效的。下面的引理描述了集合MR有效解决方案的特征。

引理7 (Ehrgott et al.， 2014)。给出了一个多目标不确定优化问题(MOUP)。对于所有的都有。

2.2基于标量化的鲁棒高效解

在(确定性)多目标优化中，通常使用一种标量化方法找到一组有效的解，即，通过解决一系列单目标的，所谓的规模化的问题(见，例如，Ehrgott, 2006)。为了找到有效的pointMR解决方案，这些方法可以直接应用于对应鲁棒的。在基于集合的最优鲁棒效率的情况下，标量化方法的扩展就不那么简单了，因为其鲁棒对偶是一个集值问题。本文提出了一种基于标量的求解setMR有效解的方法。

Ehrgott et al.(2014)介绍了基于标量的两种方法:加权和标量化方法和E -constraint方法，它们是确定性情况下相应方法的扩展。结果表明，两种方法都能找到setmr弱有效解。如果权值的选取严格大于零，则加权和问题的解甚至是有效的。用e -约束法得到的解总是点mr的弱有效解。结果表明，这两种方法并不总是能找到相同的解，并且存在着setMR有效解，而这两种方法都不能找到setMR有效解。

Ide(2014)提出了一种基于参考点0 (augmented)加权切比雪夫标量化的方法。Ide （2014)表明，该(增权)加权Chebyshev方法找到的所有解均为setMR弱有效解。在客观不确定性的情况下，Ide(2014)中的规模化问题与Hassanzadeh等人(2013)的规模化问题是一致的，（如果可以选择Hassanzadeh等人(2013)的健壮乌托邦点为0）其中确定性增加权Chebychev方法应用于鲁棒对应的，以找到pointMR有效解。

Bokrantz和Fredriksson(2017)考虑了订单保留的标量化函数及其结果的标量化问题。结果表明，对于所谓的强递增的可伸缩函数，可伸缩问题的求解是有效的。在一个应用中，他们将加权的p-范数作为标量化函数，从而得到了p- normscalalization方法(如p= 1的加权和标量化方法)。

3.多目标不确定问题的最小排序和最大排序方法

自Bowman(1976)以来，最大排序问题一直是多目标优化研究的热点。max-order方法已经被使用，例如，用于inEhrgott、Nickel和Hamacher(1999)的多目标定位问题，以及用于Ehrgott和Skriver(2003)的双目标社区问题。我们也参考了toEhrgott(2005)。在这一节中，我们利用最大序和最小序标量化来确定鲁棒有效解。

定义8：令

是一个多目标不确定优化问题。对于一个给定的权向量和参考点我们定义相应的最小排序优化问题为，和相应的最大排序优化问题为。我们进一步对于给定的客观价值为

。

注意和存在于所有。因为U是紧凑和非空的并且有限多函数是连续的。值和也有一个几何解释,我们在3.1节详细。

在章节3.2和3.3中,我们表明,最佳的解决方案(P-min (r,lambda;)和(P-max (r,lambda;))是setMR弱效率和解决方案(P-max (r,lambda;))甚至pointMR弱有效。与2.2节中讨论的现有方法类似，我们得到一个最小排序研究。最大排序数值方法找到一组快速的高效解决方案通过改变参数r,lambda;和解决由此产生的问题(P-min (r,lambda;))、(P-max(r,lambda;))。max- ordered标量化方法类似于Ide(2014)中给出的多目标鲁棒问题(以及Hassanzadeh et al.(2013)中的目标不确定性问题)中的加权Cheby-shev方法，但具有任意参考点。

之前调查性质的解决方案(P-min(r,lambda;)和(P-max(r,lambda;)),我们提供了一个简单的例子给原始的直觉的有意义的问题:考虑一个学生组织在几个大学城镇为学生提供廉价的午餐并且决定将提前订一道菜定义为。他们可以为每一个镇的菜定价不同，因为利润很小，价格取决于镇超市的原料价格。他们的目标是同时将所有城镇的午餐价格降到最低。, 在i城里是x菜的价格,价格不确定性的发展是取决于xi;isin;U。在 的条件下解决(P-max (r,lambda;))问题的意思是，在最坏的情况下，将任何城镇的学生所付餐费的最高价格降至最低。解决(P-min (r,lambda;)相同的r,lambda;意味着减少组织可以提供最好的价格在假设最坏的情况的价格的发展。I.e，即，这是他们

资料编号：[4166]