基于目标相对重要性的模糊多目标进化算法

易高明 蒋 艳(上海理工大学管理学院 上海 200082)

0 引 言

在优化中，由于决策变量的隐含条件限制，各个子目标是相互制约的，这和单目标优化问题有着本质的区别，即一般情况下，多目标优化最优解不是唯一的[1]。近十年来，进化算法和群体智能算法等启发式算法已经被成功证明在求解融入偏好的多目标优化问题中具有较高的效率和极大的优越性[2-4]。然而，涌现的多目标进化算法都被设计成旨在寻找一组有着良好分布性和延展性的Pareto最优解集，但在实际工程中，不管是个体还是群体决策者并不需要这么一组众多Pareto最优解，相反决策人只对Pareto前沿面上的若干少数解甚至某一个解有兴趣[5-6]，此时传统框架下用于求解融入决策者偏好的多目标进化方法将不再实用。因为考虑到在众多的Pareto解中二次寻找符合自身偏好的若干少数解不仅会增加求解的复杂度，更会增加决策人的评价负担[7-8]。决策者对进化多目标优化求解的期望已经不仅仅是得到尽可能多的分布性良好的Pareto最优解[9]，而且决策人希望在优化过程中，通过与多目标进化算法时时交互以不断嵌入自身偏好，引导进化个体向特定偏好区域快速逼近来寻求决策人感兴趣的少数实践解[10]。

依据决策人在求解多目标问题时偏好嵌入方式的不同，进化多目标方法分成如下三类[12]：偏好先验嵌入法、偏好后验嵌入法、交互式偏好嵌入法。其中偏好先验嵌入法是决策者在求解之前给出一个偏好向量，然后将多目标优化问题转化为单目标问题求解。关于偏好后验嵌入法，各项研究都是基于开发或者改进一类智能进化算法以更高效率的得到分布均匀、拓展良好的一组Pareto最优解。对于第三种交互方法，文献[13]提出一种双极偏好占优机制的进化个体排序规则，通过设置一个理想解和负理想解，定义远离负理想解且更靠近理想解的进化个体更优的全新锦标赛选择算子。文献[14]提出一种全新的Pareto占优范式r-占优，能够在种群进化当中给出个体的全序关系，以引导种群不断向用户偏好内逼近，其中采用期望水平向量定量刻画决策者的偏好水平和强度并辅以NSGA-II方法寻求决策人满意解。文献[15]提出g-占优的基于参考点的多目标优化算法，主要根据决策者确定的某个参考点，规定位于偏好域的解优于非偏好区域的解，从而使进化个体不断逼近参考点附近的偏好区域。

本文提出的基于目标间相对重要性的交互式进化算法RPT-NSGA-II的创新点：定量刻画决策人的模糊偏好，采用更加符合决策人情感认知的俩俩目标间语义重要性的九级范式表达模糊偏好，并遵循决策人认知规律的模糊性和渐进性，分阶段地刻画更加细致清晰的目标相对重要的表达范式。通过映射到目标空间形成决策者新的偏好区域，最后构建目标相对重要的数学模型，在NSGA-II框架下给出同一非劣层下的个体优劣排序，最终使整个进化种群朝着Pareto最优前沿面上的偏好域内逼近。

1 多目标优化问题

1.1 多目标的数学模型

设最小化多目标优化问题MOP(Multi-objective Optimization Problem)由n个决策变量，k个目标函数和m个约束条件组成，其中x表示决策向量，y表示目标向量，X表示决策向量x形成的决策空间，Y表示目标向量y形成的目标空间[1]。形式如下：

miny=F(x)=(f1(x),f2(x),…,fk(x))T

s.te(x)=(e1(x),e2(x),…,em(x))≥0

x=(x1,x2,…,xn)∈X

y=(y1,y2,…,yk)∈Y

(1)

定义1(Pareto支配) 决策向量xu=(u1,u2,…,un)Pareto支配决策向量xv=(v1,v2,…,vn)：xu≻xv当且仅当∀i=1,2,…,k，fi(xv)≥fi(xu) 且∃j=1,2,…,k，有fj(xv)>fj(xu)。

定义2(Pareto最优解集) 若P*∈{x∈X|∃x*∈X,x*≻x}，则集合P*是Pareto最优解集。

定义3(Pareto前沿) Pareto解映射到目标空间的集合即为Pareto前沿，记为PF*={F(x)|x∈P*}。

1.2 偏好多目标求解方法

从实践的立场来看，多目标的最优解集的基数虽然不唯一，但是决策者仅需要少数甚至一个实践解。经典的进化多目标即偏好后验嵌入法的求解思路是借助于进化算法的并行计算优势，经过一定代数的种群进化，旨在得到一组逼近前沿端的分布性和延展性良好的Pareto解集。然后用户基于个人经验、偏好等其他高层次信息进一步评价这些解的优劣，从中挑选一个满意解。图1给出俩目标最小化优化问题的基本步骤[16]。

步骤1通过进化优化算法找到一组分布性延展性较好的若干非劣解。

步骤2从上面非劣解中挑选一个满意解。

图1 经典后验偏好法求解多目标问题思路

相比较偏好后验嵌入法，偏好先验嵌入法在一开始便由决策者给出一个偏好向量w，偏好向量用于构建一个复合单目标函数，从而将一个多目标优化问题转化成一个单目标优化问题求解。然而在实践中，特别是对于模糊偏好多目标优化问题的求解，决策者事先给出一组偏好向量是困难的。同时合成的目标函数对偏好向量的微调非常敏感，因此偏好先验嵌入法对决策者而言是较为主观的，图2是先验法思路[16]。

图2 先验偏好法求解多目标问题思路

1.3 TOPSIS法的改进

图3 TOPSIS法

其中目标方案Fi的TOPSIS综合评价指数Ci即排队值由大到小依次排列目标方案的优劣次序。

(2)

文献[13]选取的正负理想解是由决策者根据自身偏好而给出,并没有考虑给出两个正负偏好点的可行性，在改进的TOPSIS法里，本文采用基于移动理想点法的正负偏好点更新策略，每一次进化个体的迭代和位置的更新，使TOPSIS法中的理想点和厌恶点也都到自动修正。

2 偏好区域的构建

2.1 目标相对重要性的语义范式

在融入模糊偏好的多目标进化优化过程中，问题的首要任务在于定量动态刻画决策者的偏好。考虑到决策人对目标问题偏好认知的模糊性与渐进性，交互式的重构决策者的偏好表达是求解多目标进化优化问题的关键所在。本文根据Thomas L.Saaty创建的属性间相对重要性等级表[18]，考虑决策人对一般事物认知的规律特点，对俩俩目标进行重要性比较，并且采用符合人的一般认知习惯与判断能力的更加细分的语义描述范式来表达目标之间的相对重要性，在这种范式表达下，决策者可以容易且自然地表达对目标间偏好强度。语义范式如表1所示。

表1 目标间语义感知范式

定义4对于多目标问题中的任意两个目标fi、fj，两者之间相对重要性有：

fi≻wfj(w=1,2,…,9)

当且仅当决策人在偏好程度w下感知目标fi和fj的重要比范式。有代表性的重要范式有：

1) 决策人给出的偏好是fi比fj同等重要，则有fi～fj。

2) 决策者给出的偏好是fi比fj略微重要，则有fi≻3fj。

3) 决策者给出的偏好是fi比fj相当重要，则有fi≻5fj。

4) 决策者给出的偏好是fi比fj明显重要，则有fi≻7fj。

5) 决策者给出的偏好是fi比fj绝对重要，则有fi≻9fj。

基于上述定义以及决策者对目标间重要性认知的渐进性，本文提出将带偏好的进化优化过程划分成三个子阶段来表达决策者偏好。第一阶段称为广义目标相对重要性优化(w=1，5，9)；第二阶段称为一般目标相对重要性优化(w=1，3，5，7，9)；第三阶段称为精准目标相对重要性优化(w=1，2，3，4，5，6，7，8，9)。特别的，第一阶段与第二阶段以a1T为分割点，第二阶段与第三阶段以a2T为分割点。其中T为决策者给点的终止进化代数，且有a1+a2=1，a1,a2∈(0,1)由决策者给定具体数值。在进化过程中决策者可以实时交互式的修正对目标函数的偏好,从而在目标决策空间形成新的偏好域以引导进化个体向偏好域上不断逼近。

2.2 偏好域的等角度划分

将感性的语言范式描述转化为定量的数学模型表达，是衡量多目标进化优化中嵌入决策者偏好意志成功与否的关键所在[19]，因此将上文中的目标相对重要性语言描述以恰当的方式转化为数学模型投射到目标空间的区域是非常必要的。本文对整个目标空间进行等角度偏好域划分，其他具体角度划分由决策者权衡给出。在此基础上建立偏好区域的数学模型。这里示例给出俩目标空间下广义目标相对重要性表达偏好的角度划分，见图4。

图4 广义目标相对重要性对min(fi,fj)等角度划分

考虑图4的广义目标相对重要性划分图,当目标空间被等角度划分五个区域后，根据上述区域划分的数学不等式模型并结合给定的决策者的偏好区域，可以进一步判断进化个体所在区域和决策者偏好区域的位置关系，从而给出同一非支配层中进化个体的优劣比较即处于偏好域内的个体占优偏好域外个体。各个区域的数学不等式分别有：

fi≻9fj⟺0.32fi>fj
fi≻5fj⟺0.32fi≤fj<0.73fi
fi～fj⟺0.73fi≤fj<1.38fj
fj≻5fi⟺1.38fi≤fj≤3.03fi
fj≻9fi⟺fj>3.03fi

(3)

3 进化个体适应值评价

本文给出一种全新的基于目标相对重要性的偏好区域划分排序法。该排序策略分为三个层次：基于分级的快速非劣解排序，同一非劣级别下偏好域占优排序，同一非劣级别下基于双极偏好占优的偏好域外进化个体排序。

定义5(RPT-Dominance) 决策目标空间中任意的两个决策向量X、Y，有XRPT-DominanceY，当且仅当满足如下条件之一(其中Q是决策者修正的偏好区域，Xd、Yd是决策向量X、Y的拥挤度，CX、CY是决策向量X、Y综合评价指数)。

1)XPareto支配Y。

2)X、Y互不支配且X,Y∈Q,Xd>Yd。

3)X、Y互不支配且X∈Q、Y∉Q。

4)X、Y互不支配且X,Y∉Q、CX>CY。

第一个条件解决了两个解位于不同非劣层的情况，即属于更靠前的非支配解集合中的解X优于属于靠后的非支配解集合中的解Y。后面三个条件解决了属于同一层非支配解集合下的解个体优劣问题，即若X、Y均位于决策者偏好域内，则根据它们的拥挤距离进行判别，拥挤距离较大的个体(位于较稀疏区域的个体)优于拥挤距离小的解个体；偏好域内的进化个体优于偏好域内的个体；两个解均位于偏好域外，则根据TOPSIS综合评价指数比较优劣，综合评价指数大的个体优于评价指数较小的个体。

4 基于目标相对重要性与双极偏好融合的RPT-NSGA-II算法

算法思想：融入决策者模糊偏好信息的多目标优化问题，采用目标相对重要的全新语义范式，依据人认知的渐进性，分阶段地让决策者与算法不断交互，允许决策者改变自己的偏好。将优化过程划分为广义目标相对重要性优化，一般目标相对重要性优化和精准目标相对重要性优化表述三个阶段。决策适时给出目标间偏好并在目标空间形成相应的偏好域数学模型，在NSGA-II优化框架下进行种群优化，并根据RPT-Dominance排序算子比较两两个体间优劣，从而引导进化个体不断朝着决策者感兴趣的区域搜索，步骤如下：

Step1随机初始化产生一个规模为N的群体P(t),进化代数t=0。

Step2对进化种群个体进行快速非支配排序，并在不同进化阶段采用2.1节中语义范式来刻画决策者偏好的表达。

Step3依据目标相对重要性建立数学模型，并且判断进化个体与偏好域的位置关系，计算偏好域内个体的拥挤距离和偏好域外个体锦标赛选择策略选择适应值较优的个体组成交配池，并且依概率对其进行交叉变异等遗传操作生成子代群体Q(t)。

Step4R(t)=P(t)∪Q(t)并依据RPT-Dominance锦标赛选择算子选出R(t)中前N个优势进化个体，令其为P(t+1)。

Step5给定算法终止条件，当满足终止条件则输出偏好域内满意解；否则，令t=t+1,转Step 2。

对于引入偏好的多目标遗传算法，本文给出了一种全新的进化个体适应值排序策略，算法流程如图5所示。

图5 RPT-NSGA-II流程

5 实 验

为了验证本文提出的基于RPT-dominance的偏好多目标遗传算法的有效性，将该方法与偏好先验嵌入法和偏好后验嵌入法作比较，三种方法均在NSGA-II框架下进行操作，对于每一个测试函数，三种方法均独立运行30次，五个基准数值测试函数分别为ZDT1、ZDT2、ZDT3、SCH、DTLZ2。

5.1 算法参数设置

三种方法的种群规模均设置为30并采用单点交叉和均匀变异，概率分别为0.9和0.1，两目标函数进化代数N为800，三目标函数的进化代数N为1 000。为表达决策者偏好的分割点设置为a1=0.3、a2=0.7，即在0～0.3N代时采用广义目标相对重要性表达决策者的偏好，在0.3N～0.7N代时采用一般目标相对重要性表达决策者偏好，0.7N后采用精准目标相对重要性表达决策者偏好。决策者初始偏好经过三次修正到达最终偏好，初始偏好即为先验法的决策者偏好，在迭代0.3N代时进行第一次偏好修正，迭代至0.5N代时进行第二次偏好修正，最后一次偏好修正的时间点是0.7N,即为最终偏好，最终偏好也是后验法的决策者偏好，具体设置如表2所示示。

表2 偏好设置

5.2 性能评价指标

1)AD测度：求得的最优解集中X的所有进化个体x到决策者最终偏好域的平均距离，记为:

(4)

式中：AD测度表达的是决策者采用某种进化方式求得的Pareto最优解的满意程度，AD测度值越小则表示决策者对解集X越满意。当最终个体位于偏好域内时，该个体的D(x)为0。

2)T测度：算法求解耗时。T侧度越小则表示对应算法求解的时间效率越高。

3)I测度：进化个体位于最终偏好域内的非劣解个数，I测度值越大，则表示该算法获得决策者最终满意解的能力越强。

5.3 实验结果分析

表3给出了三种不同算法得到的AD测度的均值和方差，由表3可知，与偏好先验嵌入法和偏好后验嵌入法相比较，本文提出的RPT-NSGA-II算法得到的5个测试函数的AD测度最小，即得到的所有最终解到决策者偏好域的平均距离最短，说明本文提出的方法得到的最优解最能反映出决策者的偏好，且本文算法得到的最优解在反映决策者偏好方面显著优于偏好先验法和偏好后验法。对于2目标测试函数ZDT1、ZDT2、ZDT3、SCH，采用先验法得到的AD测度大于后验法得到的AD测度，这表明在2目标测试函数上，后验法得到的最优解在反映决策者偏好的上要优于先验法，但不难发现，只有ZDT3的AD测度表现较为明显的差异，ZDT1、ZDT2、SCH在先验法和后验法得出的AD测度均无显著差异。此外在3目标测试函数DTLZ2问题上，采用先验法得出的AD测度小于后验法得出的AD测度，因此认为先验法和后验法在处理带有模糊偏好的多目标优化问题上具有结果不确定性，在不同类型的优化问题表现出差异性，然而本文提出的交互式RPT-NSGA-II在处理此类模糊偏好优化问题上表现出较为显著的优越性和稳定性。

表3 三种方法对五个测试函数的AD测度

如表4所示，与其他两种方法对比，本文提出的RPT-NSGA-II算法的时间T测度略微大于先验法得出的时间测度值，两者的T测度的差值在3 s以内。但是与后验法相比，本文的RPT-NSGA-II法的算法耗时显著小于后验法求解的耗时，后验法对所有测试函数的求解耗时均是RPT-NSGA-II交互式算法求解耗时的1～2倍。由此可知后验法求解此类问题是非常耗时的。对于本文算法耗时与先验法求解耗时的差异，一方面是RPT-NSGA-II算法考虑了与决策者的交互需求，另一方面在先验法中采用的是所有非劣进化个体的拥挤距离排序，而在本文提出的交互算法中，我们定义了偏好域内的个体采用拥挤距离的排序策略，而在偏好域外，则采用双极偏好占优的排序策略。仿真结果表明，相对于算法的总耗时，先验法和交互法的求解耗时差异是不显著的。另外之所以交互法与后验法的T测度的差异是显著的，这是因为在后验法求得的一组近似Pareto解后，决策者必须再次花费时间进行二次满意解搜索，但是本文提出的算法则是交互式向决策的偏好域逼近，从而大大减少了满意解搜索耗时。

从表5反映本文的RPT-NSGA-II算法在满意解搜索上表现出更强的能力，最终解位于最终偏好域内的解个数，包括平均个数(四舍五入)和最大个数，均显著多于先验法和后验法生成的偏好域内解个数。图6至图10是三种方法对五个测试函数满意解数量分布仿真图，矩形区域内的解是每种方法作用在一个测试函数上的最终偏好域内最大解分布，容易得出本文算法对五种测试函数下的满意解搜索数量的分布都是最好的。

(a) RPT-NSGA-II交互法 (b) 先验法 (c) 后验法图6 三种方法对ZDT1函数的满意解分布

(a) RPT-NSGA-II交互法 (b) 先验法 (c) 后验法图7 三种方法对ZDT2函数的满意解分布

(a) RPT-NSGA-II交互法 (b) 先验法 (c) 后验法图8 三种方法对ZDT3函数的满意解分布

(a) RPT-NSGA-II交互法 (b) 先验法 (c) 后验法图9 三种方法对SCH函数的满意解分布

(a) RPT-NSGA-II交互法 (b) 先验法 (c) 后验法图10 三种方法对DTLZ2函数的满意解分布

6 结 语

针对带模糊偏好的多目标进化优化问题，本文提出一种基于目标相对重要性的交互式多目标进化算法(RPT-NSGA-II)，引入偏好表达的九级自然语义范式，分广义阶段、一般阶段和精准阶段三个子阶段来刻画更加细致清晰的目标相对重要性式。决策者修正的偏好与算法不断交互有效提高了实践需求与算法有效资源分配的匹配度。仿真实验表明，RPT-NSGA-II在五个不同的测试函数上取得较高的求解效率。

本文的交互式进化优化算法将对包括工业和艺术产品的个性化创作设计、语言声音图像处理和快速检索以及目击人在海量人像库中对嫌疑人画像的再指认等寻优领域提供理论支持。

[1] 公茂果, 焦李成, 杨咚咚,等. 进化多目标优化算法研究[J]. 软件学报, 2009, 20(2):271- 289．

[2] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions Evolutionary Computation, 2002, 6(2):182- 197．

[3] Cheng R，Jin Y，Olhofer M．A Reference Vector Guided Evolutionary Algorithm for Many-Objective Optimization[J]．IEEE Transactions on Evolutionary Computation，2016，20(5)：773- 791．

[4] Singh H K, Isaacs A, Ray T. A Pareto Corner Search Evolutionary Algorithm and Dimensionality Reduction in Many-Objective Optimization Problems[J]. IEEE Transactions on Evolutionary Computation, 2011, 15(4):539- 556．

[5] Filatovas E, Kurasova O, Sindhya K. Synchronous R-NSGA-II: An Extended Preference-Based Evolutionary Algorithm for Multi-Objective Optimization[J]. Informatica, 2015, 26(1):33- 50．

[6] Wagner T, Trautmann H. Integration of Preferences in Hypervolume-Based Multiobjective Evolutionary Algorithms by Means of Desirability Functions[J]. IEEE Transactions on Evolutionary Computation, 2010, 14(5):688- 701．

[7] 郑金华, 谢谆志. 关于如何用角度信息引入决策者偏好的研究[J]. 电子学报, 2014, 42(11):2239- 2246．

[8] 张艳梅, 曹怀虎, 贾恒越,等. 考虑用户偏好的多目标服务组合优化算法研究[J]. 小型微型计算机系统, 2016, 37(1):38- 42．

[9] 肖晓伟, 肖迪, 林锦国,等. 多目标优化问题的研究概述[J]. 计算机应用研究, 2011, 28(3):805- 808．

[10] 王丽萍，章鸣雷，邱飞岳，等．基于角度惩罚距离精英选择策略的偏好高维目标优化算法[J]．计算机学报，2018，41(1)：236- 253．

[11] Deb K, Kumar A. Interactive evolutionary multi-objective optimization and decision-making using reference direction method[C]// Conference on Genetic and Evolutionary Computation. ACM, 2007:781- 788．

[12] 巩敦卫, 王更星, 孙晓燕. 高维多目标优化问题融入决策者偏好的集合进化优化方法[J]. 电子学报, 2014, 42(5):933- 939．

[13] 邱飞岳, 吴裕市, 邱启仓,等. 基于双极偏好占优的高维目标进化算法[J]. 软件学报, 2013,24(3):476- 489．

[14] Said L B, Bechikh S, Ghedira K. The r-Dominance: A New Dominance Relation for Interactive Evolutionary Multicriteria Decision Making[J]. IEEE Transactions on Evolutionary Computation, 2010, 14(5):801- 818．

[15] Molina J, Santana L V,Hernández-Díaz A G, et al. G-dominance: Reference point based dominance for multiobjective metaheuristics[J]. European Journal of Operational Research, 2009, 197(2):685- 692．

[16] Burke E K，Kendall G．搜索方法论-优化与决策支持技术入门教程[M]．北京：清华大学出版社，2014．

[17] 王应明，阙翠平，蓝以信．基于前景理论的犹豫模糊TOPSIS多属性决策方法[J]．控制与决策，2017，32(5)：864- 870．

[18] 岳超源．决策理论与方法[M]．北京:科学出版社，2003．

[19] Rachmawati L，Srinivasan D．Incorporating the notion of relative importance of objectives in evolutionary multi-objective optimiation[J]．IEEE Transactions on Evolutionary Computation，2010，14(4)：530- 546.