基于改进的RNGA算法求解两阶段分布鲁棒优化群体共识模型
Solving a Two-Stage Distributionally Robust Optimization Group Consensus Model Based on an Improved RNGA Algorithm
摘要: 作为一种既考虑数据的概率分布信息,又能保证结果不会过于保守的求解方法,分布鲁棒优化方法的研究越来越多。本文在最小成本共识模型的基础上,提出一种考虑风险成本的两阶段分布鲁棒最小成本共识模型。首先,考虑到风险的不确定性,使用CVaR来对第二阶段风险成本进行刻画。其次,通过Wasserstein距离定义一个包含经验分布周围所有分布可能的不确定集。针对问题中的风险度量部分给模型造成难以求解的后果,给出一种改进的RNGA算法来对模型进行更好地求解。最后,为了评价所提模型的鲁棒性,将TSDRO-MCCM-CVaR与SP-MCCM进行了比较。案例分析证明,SP-MCCM结果过于乐观,性能不理想,而本文提出的模型的解决方案更加鲁棒。既有更好的性能,又有足够的抗风险性。
Abstract: As a solution method that considers the probability distribution information of the data while ensuring that the results are not too conservative, distributionally robust optimization methods are increasingly studied. In this paper, based on the least-cost consensus model, a two-stage distributionally robust least-cost consensus model that considers the cost of risk is proposed. First, CVaR is used to characterize the second-stage risk cost considering the uncertainty of risk. Secondly, an uncertainty set containing all possible distributions around the empirical distribution is defined by Wasserstein distance. To address the consequences of the risk measure part of the problem that makes the model difficult to solve, an improved RNGA algorithm is given to solve the model better. Finally, to evaluate the robustness of the proposed model, TSDRO-MCCM-CVaR is compared with SP-MCCM. The case study proves that the SP-MCCM results are too optimistic and the performance is not satisfactory, while the solution of the model proposed in this paper is more robust. It has both better performance and sufficient risk resistance.
文章引用:许乃祥. 基于改进的RNGA算法求解两阶段分布鲁棒优化群体共识模型[J]. 应用数学进展, 2022, 11(3): 914-922. https://doi.org/10.12677/AAM.2022.113098

1. 引言

群体决策是当今决策科学中一个非常活跃的研究领域,已经得到了众多研究者的关注。群体决策(Group Decision Making, GDM) [1] 是通过整合参与共识的决策者(Decision Makers, DMs)的意见而实现的。经过几轮的谈判和协调,获得所有参与者一致同意的群体决策意见,从而获得决策问题的最佳解决方案。上述过程被称为达成共识的过程(Consensus Reaching Processes, CRPs) [2] 。通过适当转换思维角度可以发现,决策的过程往往也是一个需要考虑成本影响的过程。结合经济学知识可以理解,研究者通常希望决策者能够以较小的补偿成本尽快达成共识,通过合理利用有限的补偿资源获得最优决策。因此,对最小成本共识模型(Minimum Cost Consensus Model, MCCM)的研究是非常必要的。为此,Ben-Arieh和Easton首次提出了MCCM [3] ,以线性成本计算DMs前后意见偏差产生的决策成本。

现有研究中对不确定性的MCCM模型设计进行了广泛的研究。一种研究方法是基于随机规划(SP)进行建模,Zhang等人 [4] 基于这种优化方法对一定置信度下的最小共识预算进行建模。然而,在SP方法下,模型的最优解不会随着不确定参数的概率分布的不确定变化而变化,所以所寻求的最优解在某些条件下可能不成立。另一种研究方法是使用鲁棒优化(Robust Optimization, RO)模型 [5] 。Han等人 [6] 通过考虑成本的数据扰动对模型最优解造成的影响,提出了一种基于四个不确定集的鲁棒共识模型。RO方法最早由Soyster提出 [7] 。它通常用于不确定参数的确切分布信息不为人知的优化模型中。通过考虑模型的最坏情况下的最优解。其最优解避免了各种可能的不确定因素的影响,但其结果过于保守。另外,传统的RO方法有一个固定形式的不确定集,很难描绘出具体的概率分布信息,使得模型的鲁棒性更差。

近年来,分布鲁棒优化(Distributionally Robust Optimization, DRO)方法 [8] [9] [10] 逐渐成为研究重点。该方法将鲁棒优化和随机规划的优点相互结合起来,实现优势互补。本文令不确定参数视为随机变量,假设随机参数的概率分布未知,研究了一种考虑风险成本的两阶段分布鲁棒优化模型。通过Wasserstein距离 [11] [12] 定义了一个以经验分布为中心的不确定集。为了便于计算,将最坏情况下的带有风险度量两阶段优化问题转化为一个线性规划问题。针对目标函数中存在的风险度量是非光滑优化问题,提出了一种改进的RNGA方法进行求解。最后通过与SP-MCCM模型进行对比验证了本文模型的有效性。

2. 模型构建

两阶段随机规划群体决策问题可以表述如下:

min x X c T x + E [ Q ( x , ξ ) ] (1)

其中 Q ( x , ω ) 是下面第二阶段追溯问题的最优值,

min y q ( ξ ) T y ( ξ ) (2)

s .t . W ( ξ ) y ( ξ ) + T ( ξ ) x = h ( ξ ) , (3)

A x b , (4)

x 0 , y ( ξ ) 0 , (5)

在(1)~(5)中,x是第一阶段优化问题的决策向量, q ( ξ ) n 2 , W m 2 × n 2 , T ( ξ ) m 2 × n 1 , h ( ξ ) m 2 是第二阶段优化问题的随机向量和随机矩阵。问题(1)中的期望是关于随机变量 ξ 计算的。 c n 1 , A m 1 × n 1 b m 1 分别是确定的向量和矩阵。

由(1)可知,两阶段分布鲁棒优化问题的一般形式如下:

TSDRO min x c T x + sup P P E P [ Q ( x , ξ ) ] (6)

这里 P 表示包含真实分布的不确定集,且概率分布 P P 具有有限支撑 Ξ Q ( x , ξ ) 是第二阶段追溯问题(2)~(5)的最优值。

2.1. 不确定集的构造

不确定集 P 的构建是研究任意分布鲁棒优化模型的关键。本文采用Wasserstein距离来度量真实概率分布和经验分布之间的差异性。其定义为:

d W ( 1 , 2 ) : = inf { Ξ 2 ξ 1 ξ 2 p Π ( d ξ 1 , d ξ 2 ) } 1 p

其中, Π ( d ξ 1 , d ξ 2 ) 是包含分布 1 和分布 2 二者联合分布所有可能结果的集合, d W ( 1 , 2 ) 表示 1 2 之间的Wasserstein距离。 · 表示范数,一般常用1范数,即 p = 1

由于基于Wasserstein距离的不确定集可以通过历史数据结合数据驱动的方法进行构建。且从Wasserstein距离的定义可以发现,距离的计算过程不需要使用任何统计推理方法来得出,计算结果可以有效避免数据的波动性对不确定集造成的不确定性影响。所以,当 Ξ 是一个有限集,基于Wasserstein距离的不确定集定义如下:

P ( ^ N ) : = { M ( Ξ ) : d W ( ^ N , ) θ } (7)

这里 ^ N 表示历史数据的经验分布,其概率函数为 p 0 P ( ^ N ) 是基于Wasserstein距离构建的以 ^ N 为球心的概率球, θ 0 表示半径,即允许的误差,反映了真实分布和经验分布之间的差异和模型的保守性,由决策者事先确定。

2.2. 分布鲁棒优化共识模型

在CRPs中,大部分现有研究仅考虑DMs的决策意见调整成本,最后获得群体最小成本下的共识意见。但在实际决策情形下,风险的影响是不容忽视的,甚至可能会影响最终的共识成本。将历史数据作为考量,通过使用数据驱动的方法,将风险成本的影响进行刻画。由于风险因素的不确定性,最后很难得到固定的最小共识成本。因此,本文通过使用DRO方法研究风险成本的波动范围,以获取最低的决策总成本。考虑风险因素的两阶段分布鲁棒优化MCCM模型可以表示如下:

TSDRO-MCCM min x i I c i x i + λ sup P P E P [ Q ( x , ξ ) ] (8)

s .t . x i = | o ¯ i o i | (9)

| o ¯ i o | ε i , ε 0 (10)

其中 Q ( x , ξ ) 代表共识决策结果所带来的意外风险。 λ [ 0 , 1 ] 表示风险系数,当 λ = 0 ,问题(8)~(10)退化为一般的MCCM模型。

Q ( x , ξ ) : = max y i I h i y i (11)

s .t . y i θ , i I (12)

x i + y i o ˜ i 0 , i I , (13)

y i 0 , o ˜ i 0 , i I (14)

其中:

(11)为第二阶段目标函数,表示第i个决策者的风险成本量;

(12)为风险约束,表示当达成共识时,第i个决策者的决策风险影响量为 y i

(13)为总决策约束,表示第i个决策者的意见调整量 x i 和其带来的风险影响量 y i ,不能超过其个人的容忍上限 o ˜ i

基于1-Wasserstein距离的最差情景下期望问题可以转化为一个容易求解的线性规划问题。

定理 1假定 f ( x , ω ) : n 1 × Ω m .给定常数 θ 0 和一个经验概率函数 p 0 + m

sup p P E p [ f ( x , ξ ) ] (15)

可以等价地转化为下列一个线性规划问题

inf z , z + , z , π θ z + i = 1 m p i 0 ( z i + z i ) + π (16)

s .t . z i + + z i z 0 , i = 1 , , m , (17)

f ( x , ξ ) z i + z i + π , i = 1 , , m , (18)

z + , z + + m , z + m , π (19)

证明:令对每一个 ξ i Ξ ,最差情下的期望可以表示为:

sup P P E P [ f ( x , ξ ) ] = sup p + m , h + m i = 1 m p i f ( x , ξ i ) (20)

s .t . i = 1 m h i θ , (21)

p i p i 0 h i , i = 1 , , m , (22)

p i 0 p i h i , i = 1 , , m , (23)

i = 1 m p i = 1. (24)

(20)~(24)式的拉格朗日对偶可以表示为:

inf z , π , z + , z θ z + i = 1 m p i 0 ( z i + z i ) + π

s .t . z i + + z i z , i = 1 , , m ,

f ( x , ω i ) z i + z i + π , i = 1 , , m ,

z + , z + + m , z + m , π ,

这里 z , z + = ( z 1 + , , z m + ) + m , z = ( z 1 , , z m ) + m π 分别是(21)~(24)式对应的拉格朗日乘子。通过

选择 θ 0 ,存在一个概率质量函数 p 0 属于不确定集 P 的内部,即Slater条件成立。因此,(15)可以等价地转换为(16)~(19)。

2.3. 模型的鲁棒等价表达式

通过历史数据获取随机变量 ω 的经验分布,本文使用CVaR来对期望值进行逼近。其结果表示如下:

λ sup P P E P [ Q ( x , ξ ) ] = λ sup P P min κ { κ + E P [ 1 1 β ( Q ( x , ξ ) κ ) + ] } . (25)

利用定理1将带风险规避的两阶段分布鲁棒优化模型转换成相应的鲁棒等价式。

定理2:假定样本概率函数 p 0 是已知的。给定的 λ [ 0 , 1 ] β ( 0 , 1 ) ,则TSDRO-MCCM模型(8)~(10)等价于下面线性规划问题:

TSDRO-MCCM-CVaR min c T x + λ κ + θ z + i = 1 m p i 0 ( z i + z i ) + π (26)

s .t . W ( ξ ) y i + T ( ξ i ) x = h ( ξ i ) , i = 1 , , m , (27)

z i + + z i z , i = 1 , , m , (28)

λ 1 β v i z i + z i + π , i = 1 , , m , (29)

q ( ξ i ) T y i κ v i , i = 1 , , m , (30)

η , z + , z + + m , z + m , π , v + m , (31)

x X , y i Y , i = 1 , , m (32)

证明:显然函数

χ ( x , p , η ) : = λ κ + i = 1 m p i [ λ 1 β ( Q ( x , ξ i ) κ ) + ]

关于 ξ 是凸的,关于p是凹的(实际上是线性的)。由于 P 是紧集, χ ( p , ζ ) 在集合 P × 上有强极大-极小的性质,因此可以交换公式(25)中算子 sup p P min η 的顺序,得到如下的等价目标函数形式:

sup p P min κ χ ( x , p , κ ) = min κ sup p P χ ( x , p , κ ) = min κ λ κ + max p P i = 1 m p i [ λ 1 β ( Q ( x , ξ i ) κ ) + ]

根据定理1可得,

max p P i = 1 m p i [ λ 1 β ( Q ( x , ξ i ) η ) + ] (33)

= inf z , z + , z , π θ z + i = 1 m p i 0 ( z i + z i ) + π (34)

s .t . z i + + z i z 0 , i = 1 , , m , (35)

λ 1 β v i z i + z i + π , i = 1 , , m , (36)

Q ( x , ξ i ) κ v i , v i 0 , i = 1 , , m , (37)

z + , z + + m , z + m , π (38)

将(8)式中的 λ sup P P E P [ Q ( x , ξ ) ] 用(34)~(38)替换,并与第二阶段的约束条件结合起来即可得要证明的

等价式。显然,当 λ = 0 时,TSDRO-MCCM-CVaR模型退化成一般两阶段分布鲁棒优化共识模型。当 θ = 0 时,TSDRO-MCCM-CVaR模型就变成考虑风险度量的两阶段随机规划共识模型。当m的值比较小的时候,即决策群体规模较小时,可以通过求解线性规划问题(26)~(32)得到TSDRO-MCCM-CVaR问题的精确解。但是,当参与决策人数较多的时候,直接求解这个大规模的线性规划是不太明智的。

3. 利用改进的GA算法求解TSDRO-MCCM-CVaR

在本节中,设计了一个实数编码的遗传算法(RNGA) [13] [14] 来优化对TSDRO-MCCM-CVaR的求解。这样一来,GA的结构(基因、染色体、生成过程、评价等)就适应了这个问题,每个染色体包含一个DM的决策信息。优化过程由三个主要部分组成。

1) 输入数据和种群初始化准备。首先,准备输入数据,包括算法的设置和固定参数的输入。在种群初始化方法中,种群不是以完全随机和不规则的方式产生的。在随机初始化过程中,可能会出现大量的违反约束条件的情况。而这些问题要到算法的整体迭代结束时才能解决。因此,在不限制搜索空间的情况下,将种群设定为一个共识成本问题。通过这样做,可以有效地生成高质量的初始群体。对于染色体的编码选择,为了避免二进制编码在计算过程中产生的算术偏差。根据本文的实际研究背景,最终采用实数编码方案。

2) 排序与选择过程。在对上一代的种群进行评估后,应通过遗传操作产生一个新的种群。首先,根据个体的适应度值对其进行排序。选择概率通过根据个体的等级进行分配。一旦个体被排序,个体将以半随机的方式被选择。在GA的背景下,精英主义指的是通过种群找到能够存活到下一代的最佳解决方案。在选择过程中,每一代都会从种群中随机挑选出部分个体,作为下一代种群。这个过程不断重复,直到为交叉和变异做好准备。

3) 交叉方法和变异过程。由于在算法进行的不同时期,固定不变的交叉概率和变异概率会对算法的性能造成很大的影响。所以本文采用自适应的概率因子调整方法,来对模型求解进行进一步优化。在计算前期,适当增大交叉概率和变异概率的值来加快对于种群的搜索速度,保证种群的多样性;到后期,为了保存筛选出的精英个体,需要适当地降低二者概率的值,让充满优良个体的种群整体趋向于稳定状态,且避免相似的基因结构而可能陷入局部最优解的情况。

由于主问题和子问题都是线性规划问题,本文算法求解效率比较高,计算代价不会由于增加了分布不确定性而显著增加。

4. 数值案例分析

基于上述的TSDRO-MCCM-CVaR模型,为了验证所提出的Waserstein分布鲁棒共识模型的有效性和算法的高效性。所有的数值计算是在一台酷睿i5处理器,主频2.30 GHz,内存32 GB的电脑上进行。对于本文的实际数值案例,采用了天然林保护工程(Natural Forest Protection Project, NFPP)的谈判案例[10]。假设所有成本都具有合适的单位,NFPP谈判中包括地方政府G和20个农民 F = { f 1 , f 2 , , f 20 } 。共识阈值 ε = 1 ,Wasserstein不确定球集的半径 θ { 0.01 , 0.02 , 0.04 , 0.06 , 0.08 , 0.1 } ,风险系数 λ { 0.2 , 0.4 , 0.6 , 0.8 , 1 } 。农民和地方政府的初始意见,以及相应的成本系数见表1。假设从历史数据可知,政府期望的最大共识意见和最小共识意见分别是9.5和6.5。通过将区间[6.5, 9.5]划分成3个小区间,对应3种可能的离散需求情景。根据历史需求数据,首先估计出不确定需求的参考分布,然后以该参考分布为中心,以Wasserstein距离为度量工具确定一个不确定集,同时利用经验分布随机生成规模为 N = 100 , 200 , , 3000 的样本数据。

Table 1. Initial information data for decision makers

表1. 决策者初始信息数据

Table 2. The best Results of TSDRO-MCCM-CVaR model with different values of parameters

表2. TSDRO-MCCM-CVaR模型在不同参数取值下的最优结果

通过对不同参数下的TSDRO-MCCM-CVaR模型进行大量的数值实验,从表2可以看出,Wasserstein不确定球集半径 θ 的细微变化,会对模型的求解结果产生较大的影响。 θ 从0.01增长到0.1,共识成本虽有波动,但总体呈上升趋势。表明最优目标成本值随着 θ 的增大而增大,换言之,Wasserstein不确定球集的半径越大,模型表型的越保守。从表中还可以看出,伴随着 λ 的增大,模型的结果也是越来越保守的,逐渐呈现风险规避的形式。与之而来的影响,是决策群体为了对抗可能发生的共识风险,需要花费更多的成本。

Figure 1. Comparison of the results of SP-MCCM and TSDRO-MCCM-CVaR

图1. SP-MCCM和TSDRO-MCCM-CVaR的结果对比图

λ = 0 , θ = 0 时,TSDRO-MCCM-CVaR退化成为SP-MCCM模型,该模型不考虑决策风险所带来的可能影响。本文选取 λ = 0.2 , θ = 0.01 时的TSDRO-MCCM-CVaR与SP-MCCM进行对比。从图1中可以看出,由于TSDRO-MCCM-CVaR的不确定集合构建受到经验数据的影响,所以结果呈现一定的波动性,在样本数为2900时,达到最优目标解27.75,而SP-MCCM的结果恒为26.72。虽然从结束上来看,后者成本更小,但是后者因为未考虑风险的不确定性影响,模型更加保守。从实际决策环境的角度考量,本文提出的模型更加符合现实中复杂的决策背景,且决策者可以根据当下的风险偏好,灵活选择不同的风险系数,得到相应的决策结果。

5. 结束语

本文在研究最小成本共识模型时,考虑到眼下决策环境的风险不确定性。DMs的决策偏好和决策风险受到可能社会因素或者其他可能因素的影响,难以事先确定。在建立模型时充分考虑了风险成本对于最后的共识决策造成的影响。本文DMs的不确定性来自于历史经验数据,反之,在数据的帮助下,也可以有效地衡量DMs的风险成本。但是,考虑到这种方法具有一定的风险不确定性。因此,本文转而采用分布鲁棒优化模型进行建模,进一步提高了模型的鲁棒性,增强了模型的有效对冲风险能力。当不确定集的分布信息不能精确获取的前提下,通过历史经验数据,以Wasserstein距离作为度量基础,构造Wasserstein不确定性球集。该集合包含了以经验分布为中心,一定统计距离半径内的所有分布,不再使用单一分布来进行刻画,在一定程度上降低了决策的风险。紧接着,又提出一种改进的RNGA算法来对本文模型进行有效地求解。数值模拟表明,TSDRO-MCCM-CVaR模型更加符合现实中复杂的决策背景,且决策者可以根据当下的风险偏好,灵活选择不同的风险系数,得到相应的决策结果。

参考文献

[1] Kiesler, S. and Sproull, L. (1992) Group Decision Making and Communication Technology. Organizational Behavior and Human Decision Processes, 52, 96-123.
https://doi.org/10.1016/0749-5978(92)90047-B
[2] Szmidt, E. and Kacprzyk, J. (2003) A Consensus-Reaching Process under Intuitionistic Fuzzy Preference Relations. International Journal of Intelligent Systems, 18, 837-852.
https://doi.org/10.1002/int.10119
[3] Ben-Arieh, D. and Easton, T. (2007) Multi-Criteria Group Consensus under Linear Cost Opinion Elasticity. Decision Support Systems, 43, 713-721.
https://doi.org/10.1016/j.dss.2006.11.009
[4] Zhang, N., Gong, Z. and Chiclana, F. (2017) Minimum Cost Consensus Models Based on Random Opinions. Expert Systems with Applications, 89, 149-159.
https://doi.org/10.1016/j.eswa.2017.07.035
[5] Ben-Tal, A. and Nemirovski, A. (2002) Robust Optimization-Methodology and Applications. Mathematical Programming, 92, 453-480.
https://doi.org/10.1007/s101070100286
[6] Han, Y., Qu, S., Wu, Z. and Huang, R. (2019) Robust Consensus Models Based on Minimum Cost with an Application to Marketing Plan. Journal of Intelligent & Fuzzy Systems, 37, 5655-5668.
https://doi.org/10.3233/JIFS-190863
[7] Soyster, A.L. (1973) Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming. Operations Research, 21, 1154-1157.
https://doi.org/10.1287/opre.21.5.1154
[8] Delage, E. and Ye, Y. (2010) Distributionally Robust Optimization under Moment Uncertainty with Application to Data-Driven Problems. Operations Research, 58, 595-612.
https://doi.org/10.1287/opre.1090.0741
[9] Huang, R., Qu, S., Gong, Z., Goh, M. and Ji, Y. (2020) Data-Driven Two-Stage Distributionally Robust Optimization with Risk Aversion. Applied Soft Computing, 87, Article ID: 105978.
https://doi.org/10.1016/j.asoc.2019.105978
[10] Han, Y., Qu, S. and Wu, Z. (2020) Distributionally Robust Chance Constrained Optimization Model for the Minimum Cost Consensus. International Journal of Fuzzy Systems, 22, 2041-2054.
https://doi.org/10.1007/s40815-019-00791-y
[11] Mohajerin Esfahani, P. and Kuhn, D. (2018) Data-Driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations. Mathematical Programming, 171, 115-166.
https://doi.org/10.1007/s10107-017-1172-1
[12] Kuhn, D., Esfahani, P.M., Nguyen, V.A. and Shafieezadeh-Abadeh, S. (2019) Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning. In Operations Research & Management Science in the Age of Analytics (pp. 130-166). Informs.
https://doi.org/10.1287/educ.2019.0198
[13] 金菊良, 杨晓华, 丁晶. 基于实数编码的加速遗传算法[J]. 四川大学学报: 工程科学版, 2000, 32(4): 20-24.
[14] Qu, S., Li, Y. and Ji, Y. (2021) The Mixed Integer Robust Maximum Expert Consensus Models for Large-Scale GDM under Uncertainty Circumstances. Applied Soft Computing, 107, Article ID: 107369.
https://doi.org/10.1016/j.asoc.2021.107369