多目标情景树算法研究及应用

张惠秋，包振强，杨雨露，李宁川，任晓青

（1.扬州大学 信息工程学院，江苏扬州 225009；2.扬州大学 体育学院，江苏 扬州 225009）

多目标情景树算法研究及应用

张惠秋1，包振强1，杨雨露1，李宁川2，任晓青1

（1.扬州大学 信息工程学院，江苏扬州 225009；2.扬州大学 体育学院，江苏 扬州 225009）

针对传统情景树只能产生单一优化解的缺点，提出了一种多目标情景树算法。运用Pareto进行多目标排序，并从历史复杂情景中找到与问题情景相似的非支配解集，从而避免了传统单组权值计算产生的单一优化。相对于传统情景树算法，该方法得出的非支配解集更接近问题情景，更满足实际需求。通过居民健康管理系统的应用实例，充分验证了该算法的有效性和实用性。

多目标；情景树；Pareto；相似度；非支配解集

0 引言

情景生成是一种在不确定性决策中常用的方法。情景的数量和结构直接关系到模型的复杂度和可靠度。情景生成的根本目的是构建很多情景，合理地代表众多可能结果。近年来有很多人研究情景树算法，并得到了一定成果。Hoyland等［1］提出了一种非线性规划方法来生成情景树。Hoyland等［2］提出了解决情景树中的套利机会的方法。Gulplnar等［3］提出了模拟法、优化法和模拟优化混合法。Kouwenberg［4，5］通过随机抽样事件树、每个节点的适合收益分布均值和方差的事件树研究了情景生成。而国内对于多阶段情景生成的研究刚起步。李伟等［6］运用动态情景模拟法进行风险评价。葛文雷等［7］结合实物期权和情景分析方法分析投资决策。丁进等［8］基于情景模拟方法，提出了一种参考历史数据的修正模型。吉小东等［9，10］提出了一种基于聚类分析的多阶段情景生成方法，为研究情景生成提出了一种新思路。

但是，当需要对通过样本库得到的几种典型权值组进行共同运算优化时，传统的情景树算法只能产生单一优化，而远远无法满足把所有权值组考虑在内的现实需求。因此引入多目标算法来解决这类问题成为当下的迫切需求。本文设计了多目标的情景树算法：当情景树中有多个对于最终决策影响较大的因素时，能够运用Pareto排序，找到共同优化的结果。

1 情景树模型的构建

1.1 情景树模型

定义1 情景树（Scenario Tree，ST）是一种描述设计知识情景的树结构，拥有一个描述设计知识整体情景的根结点、多个描述情景构面的中间结点和多个刻画情景项的叶子结点。根节点RN（Root Node）以下，叶子节点LN（Leaf Node）以上，每个中间节点存在一个父节点PN（Parents Node），而且存在1个或多个叶子节点CN（Child Node）［11］。情景与树结构对应关系如表1所示。

表1 情景与树结构对应关系

定义2 情景构面（Scenario Aspect，SA），是对设计知识情景的多层次划分，反映设计知识情景的不同方面。情景可以分为多个不同的情景构面，一个情景构面又可以分为多个小的情景构面。

定义3 情景项［12，13］（Scenario Item，SI）是知识情景中不可再细分的情景构面，描述知识情景的具体的、详细的不可再分的信息、知识。当情景构面分到最小单位、不能再细分的时候，情景构面称为情景项。

情景树实质上是一种分类工具，为了便于对外部设计知识进行有效刻画并对知识的可获取性进行定量分析。

1.2 情景查找及匹配

1.2.1 相似度

相似度是刻画事物α与β的相似程度，记为θ(α，β)，θ∈[0，1]。当θ＝0时，表示α与β没有任何相似之处，是完全不同的；当θ＝1时，表示α与β是完全相同的；θ∈（0，1）时，表示α与β有一定的相似度，θ值越大，表示相似程度越大。在目标对象α明确的情况下，可简记为θ（β）。本文中情景相似度通常指历史情景与问题情景的相似度。

1.2.2 结点相似度

Nv表示问题情景中结点v的描述，Nv′表示历史情景中对应结点v′的描述，则结点之间的相似度计算可分为以下几种情况［14］：

①标称概念的几种可能取值之间无任何相似性、非此即彼的情况，如性别，相同即相似度为1，不同即为0。

②数量概念，如果属于正指标，即当用户希望Nv越大越好时，S(v，v′)＝(Nv′－Nv)Nv′，若S＜0，令S＝0；如果属于负指标，即当用户希望Nv越小越好时，S(v，v′)＝(Nv－Nv′)Nv，若S＜0，令S＝0；

③模糊概念，按其级别高低设定一个［0，1］内的数值表示，级别越高数值越大。Zv和Zv′分别是Nv和Nv′对应的模糊量，则S（v，v′）＝Zv′／Zv。一般来说，满足条件的程度越高越好，因此当Zv′＞Zv，即S（v，v′）＞1时，令S（v，v′）＝1。

1.3 Pareto最优

在完全竞争条件下，由市场供求所形成的均衡价格，能够引导社会资源实现有效配置，使任何2种产品对于任何2个消费者的边际替代率都相等。任何2种生产要素对任何2种产品生产的技术替代率都相等，从而达到任何资源的再配置都已不可能在不使任何人的处境变坏的同时，使一些人的处境变好。这就是所谓的帕累托最优状态。

数学定义：多目标问题的一个矢量解x是Pareto最优解当且仅当不存在另一个矢量解y，使得f（y）Pareto支配f（y）。所有的Pareto Optimal解统称为Pareto Optima解集。

2 多目标情景树算法

传统的情景树通过设置每个节点的权重计算相似度，从而得出相似度最高的历史情景。但是传统的情景树只是单纯地从相似度之和来计算，没有考虑多目标的问题，这就导致了得出的历史情景是片面的，没有全面考虑。因此，本文从多目标的角度考虑，提出了多目标情景树优化算法，从更全面的角度得出相似度高的历史情景。

2.1 Pareto排序法

Pareto［15］排序的具体过程如下：

①找出当前种群中非支配最优解并分配等级Ⅰ；

②将这些个体从种群中移出，在剩余个体中找出新的非支配解，再分配等级为Ⅱ；

③重复上述过程，直至种群中所有个体都被设定相应的等级，如图1所示。

图1 Pareto排序具体过程

2.2 多目标情景树算法

2.2.1 基于Pareto排序的多目标情景树

对于传统情景树无法满足多个节点相似度同时优化问题，提出了多目标情景树算法。首先，设情景树有n个节点，接着把样本库分成i类，通过权值算法，计算出i组权值K，则

式中，kin为情景树第i组第n个节点的权值。

假设问题情景为M＝(m1，m2，m3，…，mn)，其中mn为问题情景第n个节点。样本库中的历史情景为集合T，T中任一历史情景为N＝(n1，n2，n3，…，nn)，其中nn为历史情景第n个节点。则问题情景与历史情景某个节点的相似度为：

式中，fn为第n个节点的相似度；maxn为历史情景中第n个节点的最大值。

假设Fi为第i组权值的相似度和，则通过式（1）和式（2）求得对于第i组权值历史情景的相似度为：

设F＝{F1，F2，…，Fi}为历史情景的相似度集合。

通过历史情景的相似度集合得出非支配解集。非支配排序建立在Pareto最优的基础上，其基本过程是：对于每个个体分别计算其非支配分级序号ranki（初始值为1），则对于解a，历史情景相似度集合为Fa＝{Fa1，Fa2，…，Fai}，其非支配分级序号ranka。如果存在解b，历史情景相似度集合为Fb＝{Fb1，Fb2，…，Fbi}，其非支配分级序号rankb。

如果Fa1＞Fb1，Fa2＞Fb2，…，Fai＞Fbi，则ranka＋1。反之，rankb＋1。

经过上述计算，如果ranka＞rankb，则解a优于解b，解a支配解b。如果经过比较，解a没有被任何解支配，则a为非支配解。

通过上述算法求得非支配解集T。

2.2.2 过程算法

多目标情景树优化算法是在传统情景树算法的基础上，运用Pareto排序，找出多目标最优解集，再从解集中选择最优样本来满足实际需求。具体步骤如下：

①创建情景树，利用式（1）计算情景树权值组K＝｛K1，K2，…，Kn｝，其中Ki＝｛k1，k2，…，kn｝（kn为第n个节点的权值）。

②利用式（2）计算每个节点对应的相似度fi。

③利用式（3）计算总相似度集合F＝｛f1，f2，…，fn｝。

④对于求得的相似度集合F，进行Pareto排序，求得非支配解集Tn。

3 实例分析

本文提出的算法已初步应用于实践中，开发了一套居民健康管理系统，可得出运动、膳食处方。根据处方产生的特点，将情景维度确定为：年龄（D1）、性别（D2）、身高（D3）、体重（D4）、血压（D5）和血糖（D6）等，并将已有的设计方案按各个维度建模后存储到情景库中。

根据居民基本信息，分析得到的情景树如图2所示。

图2 居民信息情景树

居民信息是根节点，属于整体情景；基本信息和体检信息是一层节点，属于情景构面；基本信息的年龄和性别以及体检信息的身高、体重、血压和血糖是叶子节点，属于情景项。对于每个叶子节点，根据4种常见的健康类型（正常、肥胖、高血压和糖尿病）运用权值算法，通过样本库信息计算权重，得到设置权重组：

其中每列分别代表年龄、性别、身高、体重、血压和血糖的权值。而问题情景的居民基本信息如下：年龄：26岁；性别：女；身高：167 cm；体重：65 kg；上压：113 mmHg；下压：68 mmHg；血糖：5.83 mmol／L。

根据多目标情景树算法求解步骤得到相似度最高的样本处方信息，如表2所示。通过传统情景树算法得出的样本处方信息如表3所示。

表2 多目标情景树算法解

表3 传统情景树算法解

现将表2和表3对应的相似度通过图形展示，如图3所示。通过图3可以很明显地看出，传统情景树算法解中年龄与下压的相似度都非常底，年龄的相似度大概在0.85，而下压的相似度不到0.9，根本无法满足实际需求。而基于多目标情景树算法得出的解每个节点的相似度都在0.9以上，波动幅度也相对平稳，这就更符合实际需求。故多目标情景树算法在考虑可信度的情况下，得出的健身处方更能满足实际需求。

图3 多目标情景树与传统情景树结果比较

4 结束语

设计了基于Pareto的多目标情景树优化算法，设置权值组，分别计算相似度，通过Pareto排序，得到一组非支配解，再通过最终权值计算相似度，最终得到与问题情景相似的历史情景。居民健康管理网站的实例证明，该算法更接近实际需求，更具有实践性和有效性。

［1］王新云.第三方物流供需联盟构建研究［D］.西安：长安大学，2001.

［2］LI W L，NELSON J C，CHU C Y，et al.Chromosomal Lo-cations and Genetic Relationships of Tiller and Spike Characters in Wheat［J］.Euphytica，2002，125（3）：357－366.

［3］赵玉双，李 军.浅析第三方物流合作中的支付函数［J］.科学技术与工程，2004（3）：229－231.

［4］刘志学，许泽勇.基于非对称信息理论的第三方物流合作博弈分析［J］.中国管理科学，2003（5）：85－88.

［5］KOSTOPOULOS K.An Ontology-based Framework Aiming to Support Personalized Exercise Prescription［C］∥Application in Cardiac Rehabilitation.33rd Annual Inter-national Conference of the IEEE EMBS Boston，2011：1 567－1 570.

［6］王鹏姬.用平衡计分法评价物流企业绩效［J］.港口经济，2003（3）：45－46.

［7］任建标，许志焱，季建华.第三方物流服务绩效评价体系设计与应用［J］.上海管理科学，2002（4）：45－47.

［8］王 勇，杨文慧.关于企业物流管理绩效评价体系的探讨［J］.商业研究，2003（4）：163－165.

［9］FAMA E.Agency Problems and the Theory of the Firm［J］.Journal of Political Economy，1980，88：288－307.

［10］HOEK R I.The Contribution of Performance Measurement to the Expansion of Third Party Logistic Salliances in the Supply Chain［C］∥International Journalof Operations＆Production，2001：15－29.

［11］苏东水.产业经济学［M］.北京：高等教育出版社，2010.

［12］庄新田，刘 洋.基于情景树的多期模糊层次资产配置［J］.管理工程学报，2011（1）：177－182.

［13］冯俊文.决策分析的情景树方法及其应用［J］.管理工程学报，2000（3）：70－72.

［14］施星国，张 丹，包振强，等.基于知识情景的知识重用与创新机制研究［J］.管理工程学报，2009（2）：7－10.

［15］席 斌，李 帅，侯媛媛.基于多目标粒子群算法的异构网接入控制［J］.无线电通信技术，2012，38（4）：42－45.

Optimized Algorithm of Multi-objective Scenario Tree and Its Application

ZHANG Hui-qiu1，BAO Zhen-qiang1，YANG Yu-lu1，LI Ning-chuan2，REN Xiao-qing1
（1．Information Engineering College，Yangzhou University，Yangzhou Jiangsu 225009，China；2．Physical Culture Institute，Yangzhou University，Yangzhou Jiangsu 225009，China）

Anoptimized algorithm of multi-objective scenario tree is put forward.It finds the non-dominated solution set by using Pareto for sorting multiple objectives，which is similar with the historical complex scenes.The problem of the traditional single optimized way is avoided which calculates similarityby a single weighted set，so the non-dominated solution setgained from the proposed algorithmis closer to the actual demand.Finally，the application exampleof the resident health-management system validates the effectiveness and practicability of the algorithm.

multi-objective；Pareto；similarity；non-dominated solution set

TP18

A

1003－3106（2015）11－0009－04

10.3969／j.issn.1003－3106.2015.11.03

张惠秋，包振强，杨雨露，等.多目标情景树算法研究及应用［J］.无线电工程，2015，45（11）：9－12.

张惠秋女，（1988—），硕士研究生。主要研究方向：知识管理。

2015-08-02

扬州市科技攻关项目基金资助（YZ2011101）。

包振强男，（1962—），博士，教授。主要研究方向：智能调度、管理信息系统。