多目標(biāo)情景樹算法研究及應(yīng)用

張惠秋，包振強(qiáng)，楊雨露，李寧川，任曉青

（1.揚(yáng)州大學(xué) 信息工程學(xué)院，江蘇揚(yáng)州 225009；2.揚(yáng)州大學(xué) 體育學(xué)院，江蘇 揚(yáng)州 225009）

多目標(biāo)情景樹算法研究及應(yīng)用

張惠秋1，包振強(qiáng)1，楊雨露1，李寧川2，任曉青1

（1.揚(yáng)州大學(xué) 信息工程學(xué)院，江蘇揚(yáng)州 225009；2.揚(yáng)州大學(xué) 體育學(xué)院，江蘇 揚(yáng)州 225009）

針對(duì)傳統(tǒng)情景樹只能產(chǎn)生單一優(yōu)化解的缺點(diǎn)，提出了一種多目標(biāo)情景樹算法。運(yùn)用Pareto進(jìn)行多目標(biāo)排序，并從歷史復(fù)雜情景中找到與問題情景相似的非支配解集，從而避免了傳統(tǒng)單組權(quán)值計(jì)算產(chǎn)生的單一優(yōu)化。相對(duì)于傳統(tǒng)情景樹算法，該方法得出的非支配解集更接近問題情景，更滿足實(shí)際需求。通過居民健康管理系統(tǒng)的應(yīng)用實(shí)例，充分驗(yàn)證了該算法的有效性和實(shí)用性。

多目標(biāo)；情景樹；Pareto；相似度；非支配解集

0 引言

情景生成是一種在不確定性決策中常用的方法。情景的數(shù)量和結(jié)構(gòu)直接關(guān)系到模型的復(fù)雜度和可靠度。情景生成的根本目的是構(gòu)建很多情景，合理地代表眾多可能結(jié)果。近年來有很多人研究情景樹算法，并得到了一定成果。Hoyland等［1］提出了一種非線性規(guī)劃方法來生成情景樹。Hoyland等［2］提出了解決情景樹中的套利機(jī)會(huì)的方法。Gulplnar等［3］提出了模擬法、優(yōu)化法和模擬優(yōu)化混合法。Kouwenberg［4，5］通過隨機(jī)抽樣事件樹、每個(gè)節(jié)點(diǎn)的適合收益分布均值和方差的事件樹研究了情景生成。而國(guó)內(nèi)對(duì)于多階段情景生成的研究剛起步。李偉等［6］運(yùn)用動(dòng)態(tài)情景模擬法進(jìn)行風(fēng)險(xiǎn)評(píng)價(jià)。葛文雷等［7］結(jié)合實(shí)物期權(quán)和情景分析方法分析投資決策。丁進(jìn)等［8］基于情景模擬方法，提出了一種參考?xì)v史數(shù)據(jù)的修正模型。吉小東等［9，10］提出了一種基于聚類分析的多階段情景生成方法，為研究情景生成提出了一種新思路。

但是，當(dāng)需要對(duì)通過樣本庫(kù)得到的幾種典型權(quán)值組進(jìn)行共同運(yùn)算優(yōu)化時(shí)，傳統(tǒng)的情景樹算法只能產(chǎn)生單一優(yōu)化，而遠(yuǎn)遠(yuǎn)無(wú)法滿足把所有權(quán)值組考慮在內(nèi)的現(xiàn)實(shí)需求。因此引入多目標(biāo)算法來解決這類問題成為當(dāng)下的迫切需求。本文設(shè)計(jì)了多目標(biāo)的情景樹算法：當(dāng)情景樹中有多個(gè)對(duì)于最終決策影響較大的因素時(shí)，能夠運(yùn)用Pareto排序，找到共同優(yōu)化的結(jié)果。

1 情景樹模型的構(gòu)建

1.1 情景樹模型

定義1 情景樹（Scenario Tree，ST）是一種描述設(shè)計(jì)知識(shí)情景的樹結(jié)構(gòu)，擁有一個(gè)描述設(shè)計(jì)知識(shí)整體情景的根結(jié)點(diǎn)、多個(gè)描述情景構(gòu)面的中間結(jié)點(diǎn)和多個(gè)刻畫情景項(xiàng)的葉子結(jié)點(diǎn)。根節(jié)點(diǎn)RN（Root Node）以下，葉子節(jié)點(diǎn)LN（Leaf Node）以上，每個(gè)中間節(jié)點(diǎn)存在一個(gè)父節(jié)點(diǎn)PN（Parents Node），而且存在1個(gè)或多個(gè)葉子節(jié)點(diǎn)CN（Child Node）［11］。情景與樹結(jié)構(gòu)對(duì)應(yīng)關(guān)系如表1所示。

表1 情景與樹結(jié)構(gòu)對(duì)應(yīng)關(guān)系

定義2 情景構(gòu)面（Scenario Aspect，SA），是對(duì)設(shè)計(jì)知識(shí)情景的多層次劃分，反映設(shè)計(jì)知識(shí)情景的不同方面。情景可以分為多個(gè)不同的情景構(gòu)面，一個(gè)情景構(gòu)面又可以分為多個(gè)小的情景構(gòu)面。

定義3 情景項(xiàng)［12，13］（Scenario Item，SI）是知識(shí)情景中不可再細(xì)分的情景構(gòu)面，描述知識(shí)情景的具體的、詳細(xì)的不可再分的信息、知識(shí)。當(dāng)情景構(gòu)面分到最小單位、不能再細(xì)分的時(shí)候，情景構(gòu)面稱為情景項(xiàng)。

情景樹實(shí)質(zhì)上是一種分類工具，為了便于對(duì)外部設(shè)計(jì)知識(shí)進(jìn)行有效刻畫并對(duì)知識(shí)的可獲取性進(jìn)行定量分析。

1.2 情景查找及匹配

1.2.1 相似度

相似度是刻畫事物α與β的相似程度，記為θ(α，β)，θ∈[0，1]。當(dāng)θ＝0時(shí)，表示α與β沒有任何相似之處，是完全不同的；當(dāng)θ＝1時(shí)，表示α與β是完全相同的；θ∈（0，1）時(shí)，表示α與β有一定的相似度，θ值越大，表示相似程度越大。在目標(biāo)對(duì)象α明確的情況下，可簡(jiǎn)記為θ（β）。本文中情景相似度通常指歷史情景與問題情景的相似度。

1.2.2 結(jié)點(diǎn)相似度

Nv表示問題情景中結(jié)點(diǎn)v的描述，Nv′表示歷史情景中對(duì)應(yīng)結(jié)點(diǎn)v′的描述，則結(jié)點(diǎn)之間的相似度計(jì)算可分為以下幾種情況［14］：

①標(biāo)稱概念的幾種可能取值之間無(wú)任何相似性、非此即彼的情況，如性別，相同即相似度為1，不同即為0。

②數(shù)量概念，如果屬于正指標(biāo)，即當(dāng)用戶希望Nv越大越好時(shí)，S(v，v′)＝(Nv′－Nv)Nv′，若S＜0，令S＝0；如果屬于負(fù)指標(biāo)，即當(dāng)用戶希望Nv越小越好時(shí)，S(v，v′)＝(Nv－Nv′)Nv，若S＜0，令S＝0；

③模糊概念，按其級(jí)別高低設(shè)定一個(gè)［0，1］內(nèi)的數(shù)值表示，級(jí)別越高數(shù)值越大。Zv和Zv′分別是Nv和Nv′對(duì)應(yīng)的模糊量，則S（v，v′）＝Zv′／Zv。一般來說，滿足條件的程度越高越好，因此當(dāng)Zv′＞Zv，即S（v，v′）＞1時(shí)，令S（v，v′）＝1。

1.3 Pareto最優(yōu)

在完全競(jìng)爭(zhēng)條件下，由市場(chǎng)供求所形成的均衡價(jià)格，能夠引導(dǎo)社會(huì)資源實(shí)現(xiàn)有效配置，使任何2種產(chǎn)品對(duì)于任何2個(gè)消費(fèi)者的邊際替代率都相等。任何2種生產(chǎn)要素對(duì)任何2種產(chǎn)品生產(chǎn)的技術(shù)替代率都相等，從而達(dá)到任何資源的再配置都已不可能在不使任何人的處境變壞的同時(shí)，使一些人的處境變好。這就是所謂的帕累托最優(yōu)狀態(tài)。

數(shù)學(xué)定義：多目標(biāo)問題的一個(gè)矢量解x是Pareto最優(yōu)解當(dāng)且僅當(dāng)不存在另一個(gè)矢量解y，使得f（y）Pareto支配f（y）。所有的Pareto Optimal解統(tǒng)稱為Pareto Optima解集。

2 多目標(biāo)情景樹算法

傳統(tǒng)的情景樹通過設(shè)置每個(gè)節(jié)點(diǎn)的權(quán)重計(jì)算相似度，從而得出相似度最高的歷史情景。但是傳統(tǒng)的情景樹只是單純地從相似度之和來計(jì)算，沒有考慮多目標(biāo)的問題，這就導(dǎo)致了得出的歷史情景是片面的，沒有全面考慮。因此，本文從多目標(biāo)的角度考慮，提出了多目標(biāo)情景樹優(yōu)化算法，從更全面的角度得出相似度高的歷史情景。

2.1 Pareto排序法

Pareto［15］排序的具體過程如下：

①找出當(dāng)前種群中非支配最優(yōu)解并分配等級(jí)Ⅰ；

②將這些個(gè)體從種群中移出，在剩余個(gè)體中找出新的非支配解，再分配等級(jí)為Ⅱ；

③重復(fù)上述過程，直至種群中所有個(gè)體都被設(shè)定相應(yīng)的等級(jí)，如圖1所示。

圖1 Pareto排序具體過程

2.2 多目標(biāo)情景樹算法

2.2.1 基于Pareto排序的多目標(biāo)情景樹

對(duì)于傳統(tǒng)情景樹無(wú)法滿足多個(gè)節(jié)點(diǎn)相似度同時(shí)優(yōu)化問題，提出了多目標(biāo)情景樹算法。首先，設(shè)情景樹有n個(gè)節(jié)點(diǎn)，接著把樣本庫(kù)分成i類，通過權(quán)值算法，計(jì)算出i組權(quán)值K，則

式中，kin為情景樹第i組第n個(gè)節(jié)點(diǎn)的權(quán)值。

假設(shè)問題情景為M＝(m1，m2，m3，…，mn)，其中mn為問題情景第n個(gè)節(jié)點(diǎn)。樣本庫(kù)中的歷史情景為集合T，T中任一歷史情景為N＝(n1，n2，n3，…，nn)，其中nn為歷史情景第n個(gè)節(jié)點(diǎn)。則問題情景與歷史情景某個(gè)節(jié)點(diǎn)的相似度為：

式中，fn為第n個(gè)節(jié)點(diǎn)的相似度；maxn為歷史情景中第n個(gè)節(jié)點(diǎn)的最大值。

假設(shè)Fi為第i組權(quán)值的相似度和，則通過式（1）和式（2）求得對(duì)于第i組權(quán)值歷史情景的相似度為：

設(shè)F＝{F1，F(xiàn)2，…，F(xiàn)i}為歷史情景的相似度集合。

通過歷史情景的相似度集合得出非支配解集。非支配排序建立在Pareto最優(yōu)的基礎(chǔ)上，其基本過程是：對(duì)于每個(gè)個(gè)體分別計(jì)算其非支配分級(jí)序號(hào)ranki（初始值為1），則對(duì)于解a，歷史情景相似度集合為Fa＝{Fa1，F(xiàn)a2，…，F(xiàn)ai}，其非支配分級(jí)序號(hào)ranka。如果存在解b，歷史情景相似度集合為Fb＝{Fb1，F(xiàn)b2，…，F(xiàn)bi}，其非支配分級(jí)序號(hào)rankb。

如果Fa1＞Fb1，F(xiàn)a2＞Fb2，…，F(xiàn)ai＞Fbi，則ranka＋1。反之，rankb＋1。

經(jīng)過上述計(jì)算，如果ranka＞rankb，則解a優(yōu)于解b，解a支配解b。如果經(jīng)過比較，解a沒有被任何解支配，則a為非支配解。

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

2.2.2 過程算法

多目標(biāo)情景樹優(yōu)化算法是在傳統(tǒng)情景樹算法的基礎(chǔ)上，運(yùn)用Pareto排序，找出多目標(biāo)最優(yōu)解集，再?gòu)慕饧羞x擇最優(yōu)樣本來滿足實(shí)際需求。具體步驟如下：

①創(chuàng)建情景樹，利用式（1）計(jì)算情景樹權(quán)值組K＝｛K1，K2，…，Kn｝，其中Ki＝｛k1，k2，…，kn｝（kn為第n個(gè)節(jié)點(diǎn)的權(quán)值）。

②利用式（2）計(jì)算每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的相似度f(wàn)i。

③利用式（3）計(jì)算總相似度集合F＝｛f1，f2，…，fn｝。

④對(duì)于求得的相似度集合F，進(jìn)行Pareto排序，求得非支配解集Tn。

3 實(shí)例分析

本文提出的算法已初步應(yīng)用于實(shí)踐中，開發(fā)了一套居民健康管理系統(tǒng)，可得出運(yùn)動(dòng)、膳食處方。根據(jù)處方產(chǎn)生的特點(diǎn)，將情景維度確定為：年齡（D1）、性別（D2）、身高（D3）、體重（D4）、血壓（D5）和血糖（D6）等，并將已有的設(shè)計(jì)方案按各個(gè)維度建模后存儲(chǔ)到情景庫(kù)中。

根據(jù)居民基本信息，分析得到的情景樹如圖2所示。

圖2 居民信息情景樹

居民信息是根節(jié)點(diǎn)，屬于整體情景；基本信息和體檢信息是一層節(jié)點(diǎn)，屬于情景構(gòu)面；基本信息的年齡和性別以及體檢信息的身高、體重、血壓和血糖是葉子節(jié)點(diǎn)，屬于情景項(xiàng)。對(duì)于每個(gè)葉子節(jié)點(diǎn)，根據(jù)4種常見的健康類型（正常、肥胖、高血壓和糖尿?。┻\(yùn)用權(quán)值算法，通過樣本庫(kù)信息計(jì)算權(quán)重，得到設(shè)置權(quán)重組：

其中每列分別代表年齡、性別、身高、體重、血壓和血糖的權(quán)值。而問題情景的居民基本信息如下：年齡：26歲；性別：女；身高：167 cm；體重：65 kg；上壓：113 mmHg；下壓：68 mmHg；血糖：5.83 mmol／L。

根據(jù)多目標(biāo)情景樹算法求解步驟得到相似度最高的樣本處方信息，如表2所示。通過傳統(tǒng)情景樹算法得出的樣本處方信息如表3所示。

表2 多目標(biāo)情景樹算法解

表3 傳統(tǒng)情景樹算法解

現(xiàn)將表2和表3對(duì)應(yīng)的相似度通過圖形展示，如圖3所示。通過圖3可以很明顯地看出，傳統(tǒng)情景樹算法解中年齡與下壓的相似度都非常底，年齡的相似度大概在0.85，而下壓的相似度不到0.9，根本無(wú)法滿足實(shí)際需求。而基于多目標(biāo)情景樹算法得出的解每個(gè)節(jié)點(diǎn)的相似度都在0.9以上，波動(dòng)幅度也相對(duì)平穩(wěn)，這就更符合實(shí)際需求。故多目標(biāo)情景樹算法在考慮可信度的情況下，得出的健身處方更能滿足實(shí)際需求。

圖3 多目標(biāo)情景樹與傳統(tǒng)情景樹結(jié)果比較

4 結(jié)束語(yǔ)

設(shè)計(jì)了基于Pareto的多目標(biāo)情景樹優(yōu)化算法，設(shè)置權(quán)值組，分別計(jì)算相似度，通過Pareto排序，得到一組非支配解，再通過最終權(quán)值計(jì)算相似度，最終得到與問題情景相似的歷史情景。居民健康管理網(wǎng)站的實(shí)例證明，該算法更接近實(shí)際需求，更具有實(shí)踐性和有效性。

［1］王新云.第三方物流供需聯(lián)盟構(gòu)建研究［D］.西安：長(zhǎng)安大學(xué)，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］趙玉雙，李 軍.淺析第三方物流合作中的支付函數(shù)［J］.科學(xué)技術(shù)與工程，2004（3）：229－231.

［4］劉志學(xué)，許澤勇.基于非對(duì)稱信息理論的第三方物流合作博弈分析［J］.中國(guó)管理科學(xué)，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ì)分法評(píng)價(jià)物流企業(yè)績(jī)效［J］.港口經(jīng)濟(jì)，2003（3）：45－46.

［7］任建標(biāo)，許志焱，季建華.第三方物流服務(wù)績(jī)效評(píng)價(jià)體系設(shè)計(jì)與應(yīng)用［J］.上海管理科學(xué)，2002（4）：45－47.

［8］王 勇，楊文慧.關(guān)于企業(yè)物流管理績(jī)效評(píng)價(jià)體系的探討［J］.商業(yè)研究，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］蘇東水.產(chǎn)業(yè)經(jīng)濟(jì)學(xué)［M］.北京：高等教育出版社，2010.

［12］莊新田，劉 洋.基于情景樹的多期模糊層次資產(chǎn)配置［J］.管理工程學(xué)報(bào)，2011（1）：177－182.

［13］馮俊文.決策分析的情景樹方法及其應(yīng)用［J］.管理工程學(xué)報(bào)，2000（3）：70－72.

［14］施星國(guó)，張 丹，包振強(qiáng)，等.基于知識(shí)情景的知識(shí)重用與創(chuàng)新機(jī)制研究［J］.管理工程學(xué)報(bào)，2009（2）：7－10.

［15］席 斌，李 帥，侯媛媛.基于多目標(biāo)粒子群算法的異構(gòu)網(wǎng)接入控制［J］.無(wú)線電通信技術(shù)，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

張惠秋，包振強(qiáng)，楊雨露，等.多目標(biāo)情景樹算法研究及應(yīng)用［J］.無(wú)線電工程，2015，45（11）：9－12.

張惠秋女，（1988—），碩士研究生。主要研究方向：知識(shí)管理。

2015-08-02

揚(yáng)州市科技攻關(guān)項(xiàng)目基金資助（YZ2011101）。

包振強(qiáng)男，（1962—），博士，教授。主要研究方向：智能調(diào)度、管理信息系統(tǒng)。