基于UML与CCSP的产品配置方法

CNKI出版 日期 ：20l3.04.27 http：//kcms/detail/11.2127.TP20130427.1412.001.html2 Computer Engineering andApplications计算机工程与应用解速度怏 ；缺点在于配置知识与求解知识被嵌入规则之中，导致规则库的维护困难，通用性差 。基于资源的产品配置方法中 ，组件提供或消耗某种资源；配置任务的目标在于找到-组满足所有约束条件的组件，并使该组组件所提供和消耗的资源总量达到-种平衡状态。由于基于资源的配置方法仅考虑了组件问功能上的依赖关系，因此该方法所获得的结果最终只能产生-组覆盖所有预定功能范围的组件，而并不能产生被配置产品的结构与拓扑信息。基于案例推理的产品配置方法在配置客户所需产品时，其思想是通过从历史产品中检索出与客户需求最相似的产品，然后对该产品进行修改以满足客户的需求 。其优点在于即使配置知 不完备的条件下也能有效地处理客户的配置需求，缺点在于所获的产品配置方案并不能保征是最优的方案，吲时该方法也不能获得所有符合客户要求的产品配置解。基于约束的产品配置方法将-个配置uJ题视 为-个约束满足 Uj题 (Constraint SatisfactionProblem，CSP)，其中：变量包括组件的类型变量、端[l变量和属性变量 ；约束包括初始的用户需求和在组件 目录中面每个组件定义的约束。由于基于CSP的产品配置方法不能直接建模问题中变量依条件参与求解的动态性，如豪华型汽车需要配置天窗而标准型不必配置天窗，Mittal S和Falkenhainer B对CSP进行了扩展，提出了经典的动态约束满足问题模型(Dynamic Constraint Satisfaction Prob-lems，DCSP) (注：为了区别文献中已有的另-类动态约束满足廿J题 ，Sabin M后来将Mital S提出的DCSP更名为条件约束满足问题(Conditional Constraint SatisfactionProblems.CCSP)[10-1 )。DCSP将变量集划分为初始变量集和非初始变量集，并引入激活性约束建模初始变量与非初始变量、以及非初始变量问的条件依赖关系；通过激活性约束动态地控制非初始变量的状态，使之依条件动态参与问题求解并出现在最终解集中。鉴于基于约束的产品配置方法中大多仅考虑了变量取值离散型的情7兑，Xie H和Henderson P等 从工程产品配置的特征出发，对传统基于CSP的产品配置方法进行了拓展，将变量划分为独立性变量和依赖性变量，提出了可建模并求解离散变量、连续变量、算术约束及可计算程序约束等的产品配置方法。上述面向ⅡJ题求解的产品配置方法，在建模产品配置问题时均较少考虑可配置产品的复杂结构和拓扑信息，因而在直接建模大规模产品配置问题时面临了种种局限。另-个问题是随着可配置产品结构的复杂化、新技术的不断出现和产品的更新换代速度加快 ，使得配置知识库的维护变得愈lJu困难。为了方便配置知识的重用以及配置建模与配置求解的分离 ，研究者的重心开始转移到配置知识1人J在结构的识别与表示上，即配置建模问题。Soininen T和Tiihonen J等” 从配置本体构建的角度对产品配置建模问题做了开创性的工作；通过将产品配置知识划分为配置模型知识 、配置解知识与客户需求规范知识，并对相应领域的本体进行系统阐述，提出了-个通用的非形式化的产品配置本体论。Dong Yang和Ming Dong等 也提出了-个相似的产品配置本体论，并采用网络本体语言对产品配置模型进行形式化表示。基于本体的产品配置方法通过利用产品配置本体论，统-的对配置知识进行概念化表示，建立-个统-的产品配置模型，从而增加了对产品配置知识的共享与重用 ，方便 了产品配置模型的维护 ；不足之处在于配置求解效率不高。面向对象的产品配置方法” 将配置 问题视为-个分类问题 ，该方法通过特化”与封装 ”机制强有力地改善了配置知识库的维护工作。在面向对象的产品配置建模中，通过UML(统-建模语言)中的扩展机制和嵌入机制(如对象约束语言OCL)对产品配置中各种类型的配置知识进行概念化表示，能使所建立的产品配置模型清晰易懂，可重用性强 ；但其不足之处在于产品配置求解的效率不太高，求解方法不够丰富。基于描述逻辑的产品配置方法 ” 。 采用面向对象建模及基于框架结构方法描述配置知识，能够较好地处理层次结构与分类知识；缺点是推理求解能力较弱，往往需要借助于基于规则的系统提高推理能力。

产品配置建模方法和产品配置求解方法曾较长的时间作为两个独立的研究领域而孤立存在；近年来，为了开发-个理想的产品配置系统，以期充分发挥产品配置建模方法和产品配置求解方法的各自优势，这两个领域的有效映射机制开始引起研究者们的关注。Dong Yang和MingDongt 等对配置廿J题中-类特殊的具有基数约束的包含性配置规则进行了研究，并通过配置图建立了其产品配置模型 ，然后将配置模型映射至 CSPuJ题 ，通过对 CSP的求解以间接实现配置问题的求解。Dong Yang和Ming Dong采用UML对配置问题进行建模 ，然后将其映射至DCSP问题，其中配置约束如包含性约束、排斥性约束等映射为兼容性约束，结构约束如部分整体关系、父子类关系、部件属性关系等映射为激活性约束。相比于以端LI-连接型为基础的产品配置方法- ，该方法的优势在映射过程中产生的DCSP变量空间规模减少 ，增加了搜索过程求解效率 ；缺点在于难以从所获配置解中还原产品的结构关系，尤其是整体部分关系的还原识别。

因此，本文 目的在于开发-种较理想的产品配置方法，以便能够通用地 、概念化地 、系统地表示产品配置知识，方便配置模型的建立 、维护和快速求解。全文组织如下：首先概要地阐述条件约束满足问题模型 ；然后给出基于UML与条件约束满足的产品配置框架，并定义UML表示的产品配置概 念与CCSP中对应概念的映射规则 ，建立基于CCSP表示的产品配置模型 ；最后采用可配置医用监测器案例验证本文所提方法的可行性与有效性。

2 条件约束满足问题条件约束满足问题(Conditional Constraint SatisfactionProblem，CCSP)是-个五元组 P( ，VI，D，C， )，其中：(1)集合 表示-组变量，即 Vil∈1，2，， ，n表示不同变量个数。对于任-变量v， V，存在三种可能状态，即活动变量、非活动变量与未定义变量。处于活动袁际军，黄敏镁 ：基于UML与CCSP的产品配置方法 3状态的变量参与问题求解 ，且在求解过程中需指派域值；处于非活动状态的变量在求解过程中禁止指派域值；处于未定义状态的变量指该变量此时尚未激活，不参与问题求解。

(2)集合 ，表示-组非空初始变量 ，且有 ， V。对于任-变量 v， ，，均处于活动变量状态。

(3)集合 D表示-组与变量相对应的值域 ，即 DD(v )li∈1，2，， )。其中，D(v )表示变量v 的值域。

(4)集合c表示-组兼容性约束，即cc，I∈l，2，，lc1)As(c ) V，lCl表示不同兼容性约束个数，变量集合(cf)称为第-，个约束c，的作用范围。对于vs(cj)vj li1，2，，IsOI，则有C， D( 1)×D(V，2)××D(V (c， )成立。

如果兼容性约束 c.作用范围中所有变量处于活动变量状态，则该约束称为被激活的兼容性约束；在求解过程中，仅被激活的兼容性约束参与问题求解。

(5)集合 表示-组激活性约束。激活性约束分为包含性约束和排斥性约束。

①包含性约束形如：C。 (v --，v，)>I11v ，其中条件变量为 -.，V，，目标变量为v ，且有V v ，v ，，V 。当条件变量 ( -，v，)的-组指派与约束条件 Ccond( -，V，)- 致时，目标变量 v 将被触发为活动变量状态。

②排斥性约束形如：Ccond(v -，v，) v ，其中目标变量v v ，v ，，v，。当条件变量(v -，v，)的-组指派与约束条件 Cco.a(v -，v，)-致时，目标变量 v 将被触发为非活动变量状态3 基于UML与CCSP的产品配置建模产品配置知识包括产品配置模型知识、配置解知识和客户需求规范知识。为了合理地组织各种不同类型的配置知识，-种有效的方法是对酉己置知识进行概念化 ，并从概念层面组织各类配置知识。在产品配置概念模型中，主要存在的概念有：组件类型 、属性值类型、产品复合结构 、组件连接结构、资源类型和各种约束等1 3l。UML作为-种面向对象的建模工具，非常适于用来构建图形化表示的产品配置概念模型u 。然而，UML并不具有推理功能 ，不能对所建立的产品配置概念模型进行直接的知识推理求解；为了能对建立的配置模型进行求解，需要将基于UML的产品配置概念模型转化为-种具有较强推理功能的形式化语言所表示的知识模型。在此，条件约束满足问题能够被利用来扮演这种角色 。条件约束满足问题中的主要概念包括约束变量、变量值域、兼容性约束、包含性约束和排斥性约束。本文将利用UML对产品配置概念知识进行图形化表示 ；然后，定义 UML表示的产品配置概念与CCSP中对应概念的转换规则，建立基于CCSP表示的产品配置模型，再采用适合CCSP的算法进行快速求解。

- 个值得关注的问题是条件约束满足问题中约束变量所表示的建模对象通常是面向个体域，而产品配置概念模型所面向的对象通常是概念层，即在UMLl主要表现为类图；因此，产品配置概念模型向基于CCSP的产品配置模型的转化具有保真性 ，反之则不然。与利用UML中的图形化符号建模产品配置概念模型-样，本文将提出-种面向条件约束满足问题模型的图形化表示符号，并利用这种图形化符号建模条件约束满足问题模型，使得采用该种图形化符号表示的产品配置模型能够直接转化为用条件约束满足问题表示的知识模型。下面将详细阐述产品配置概念模型中的概念、UML建模符号、面向CCSP的建模符号和CCSP形式化语言表示的知识模型之间的对应与映射关系。

3.1 组件类型到CCSP的映射规则在配置问题中，组件类型的外延由具有同-组件类型的不同组件个体构成。在基于条件约束满足问题的产品配置模型中，组件建模为组件变量，其值域为所有预先指定的相关组件类型。如果该组件类型的外延指称 个不同的组件个体，则需预先定义，z个不 的组件变量，-个组件变量代表了-个组件个体。在以分类层次组织的组件类型层次树中，组件变量的值域则为类型层次树中与根类型相关的所有叶子节点上的具体组件类型。组件的属性在条件约束满足问题中建模为属性变量；依据组件变量的不同赋值，即赋予组件变量不同的组件类型，则与组件类型相关的组件的属性变量将被激活并被添加到待求解的问题中。每个属性变量必须预先定义，属性变量的书写格式为 ：组件变量名”.”属性名”。

图 1中，令M是-个组件类型名，M1和M2分别是它的子类型 名(即M1与M2和M均是is-a关系)，a1和a2分别是属性名 ，其 中，与a1和 a2分别对应的属性值类型是val valI2，，val。 和val21，val ，，val2 ，为枚举类型；则与该概念模型对应的CCSP模型可表述如下：定义m 为组件变量，其中下标i取值为正整数，若在配置模型中组件类型 M的实例数最多为 个，则需预先定义 个组件变量。组件变量m 的值域为fM1，M2。当组件变量m 取值为M1时，属性变量m .al被激活；当组件变量m 取值为M2时，属性变量m .a2被激活(图1包含性约束A1和A2)。它们之间的映射关系如图 1所示。

3.2 复合结构到CCSP的映射规则产品通常由-些子装配体组成，而子装配体又由其下- 级子装配体组成，由此形成了产品的装配层次结构。产品配置概念建模中，产品的这种装配结构在UML中可利用复合聚合关系进行建模，这种复合聚合关系在此被称为产品的复合结构关系。

图2中，M1、M2、M21和M22分别为组件类型，M21和M22分别是 M2的子类型 ，M1和M2之问是复合结构关系。pa为复合端口名，pb为面向成分组件类型的成分端口名。基数范围 1.1表示M2的1个组件实例只能与Ml的 1个组件实例连接，基数范围 1.2表示M1的-个组件实例可与M2的1至2个组件实例连接；因此，可为M1的每个组件4 Computer Engineering andApplications计算机工程与应用o：is.a关系：包含性约束A：组件变量 [二] ：变量值 <二> ：属性变量图 1 组件类型到CCSP的映射规则基数 摹数端口名 part-of关系组件变量复合端口变量变量值， ：、 誊 藿 三-，- 、 ： 茬 三C图2 复合结构到CCSP的映射规则实例分别定义2个端口名如pa 和pa ，每个端121均具有相同的连接功能。

在基于CCSP的产品配置建模中，假定组件变量m 代表组件类型M1的实例，则定义变量m。的值域为M1；组件变量m 、m 分别代表组件类型M2的实例，由于组件类型M2有两个子类型M21和M22，则定义变量m：、m，的值域分别为M21，M22。若组件变量m 赋值为M1，则与其相关的端口变量m。.pa 和m .pa：将被激活并参与求解。由于端121 pa 和pa∩保持为连接或未连接状态，因此定义端口变量m，.pa。和m，.pa：的值域分别为conn，unconn，其中，如果变量m .pa。取值conn，则表示与该变量相对应的端口pa 保持连接状态，并假定组件变量m：对应的组件实例与该端口pa 相连接，则该组件变量将被触发为活动变量状态；若变量m、.pa 取值unconn，则表示与该变量相对应的端口保持未连接状态，因而.组件变量m：将被触发为非活动状态，不参与配置问题的求解。同理，对端口变量m。.paz的分析也厂， J 、 袁际军，黄敏镁：基于UML与CCSP的产品配置方法 5与上述类似，区别仅在于变量m 将变为活动状态或非活动状态。

根据基数范围1..2可知，组件变量m。对应的组件实例的两个端口pa 和pa2，至少有-个保持连接状态，则必须在端口变量m..pa。和m .pa2之间定义-个兼容性约束，使得若在其中-个端口变量赋值为unconn时，另-个端口变量只能取值conn；而若其中-个变量先赋值为conn时，则另-个变量可取conn和unconn中任-个值。这些概念之问的映射关系及图形符号定义如图2所示。

3.3 连接结构到CCSP的映射规则产品的连接结构是指构成产品的各组成部件间通过端口相互连接所形成的连接关系。在产品配置概念建模中，端口被抽象为端口类型的实例，每个组件类型的组件实例拥有各自对应的端口类型的端口实例，具有连接关系的各组件实例通过相兼容的端口实例相连接。

图3中，组件类型M1的实例与组件类型M2的实例通过端口类型P1的实例和端 VI类型P2的实例相连接，pa和pb分别是连接端口名。与M1相对的面向P1-侧的基数范围1..1，表示M1的组件实例具有-个端口类型P1的端口实例，该端VI实例名定义为pa。。与M2相对的面向P2-侧的基数范围2.2，表示M2的组件实例具有端口类型为P2的两个端 VI实例，该端VI实例名分别定义为pb。和pb 。与P2相对的面向P1-侧的基数范围 1.1，表示M2的组件实例其端口必须保持连接状态。与P1相对的面向P2-侧的基数范围0-1，表示M1的组件实例其端口可保持为连接或未连接状态。

在基于CCSP的产品配置建模中，假定组件变量m。和m 分别代表组件类型M1的实例，则变量m，和FB 的值域分别为M1l；组件变量m 代表组件类型M2的实例 ，则变量m，的值域为M2。当组件变量m，被赋值M1时，与其相关的端口变量m。.pa～被激活，由于端口变量m..pa。所对应的组件其端口具有连接或未连接两种状态，因此端 口变量m。.pa。的值域为conn，unconn；同理，端VI变量m：.pa.的值域为conn，unconn。当组件变量m 被赋值M2时，与其相关的端口变量m，.pb 和m .pb 将被激活，由于M2的组件实例其端口须保持为连接状态 ，因此 ，端 口变量 m，.pb。和m，.pb：的值域分别为conn。在建模时，事先假定组件变量m。对应的组件实例仅与端口变量m，.pb。对应的端口实例相连，组件变量m。对应的组件实例仅与端口变量m，.pb 对应的端口实例相连；因此，可定义如图3所示的包含性约束和排斥性约束。

3.4 资源约束到CCSP的映射规则在配置领域中，常存在某些组件提供某种抽象资源，如能量、硬盘空间或功率等，而另-些组件则需要消耗此种资源。并且，所消耗的资源数量不能大于所产生的资源数量。资源的这种产生与消耗关系被称为资源约束。

图4中，组件类型M1和M2的组件实例分别产生类型为R的资源r，而组件类型M3和M4的组件实例则分别消耗类型为R的资源r；其中，M1、M2的每个实例分别提供、厶单位数量的资源r，而M3、M4的每个实例则分别消耗厶、厶单位数量的资源r。在-个最终的配置结果中，M3和M4的所有组件实例所共同消耗的资源r的数量，不大于M1和M2的所有组件实例所产生的资源r的数量。

在基于CCSP的产品配置建模中，假定存在组件变量m。和m。 分别代表组件类型M1的实例，则m .和m. 的值域分别为M1；组件变量m： 和m：分别代表组件类型M2的实例，则变量m ，和m。的值域分别为M2；组件变量m 。代表组件类型M3的实例，则变量m 。的值域为M3；组件变量m 代表组件类型M4的实例，则变量m 的值域为M4。

当组件变量m ，被赋值M1时，则与其相关的资源属性变量图3 连接结构向CCSP的映射规则、， J 、，、袁际军，黄敏镁：基于UML与CCSP的产品配置方法 2013.49(14) 7图5 基于UML的可配置医用监测器概念模型b4.disp1：conn；unconn；b4.disp2：corm；unconn；b5。

sigl：conn；b5.sig2：conn；b6.displ：conn；unconn；b7。

sig1：conn；b8.sigl：conn；b8.sig2：conn(7)兼容性约束CI：C(hm1.color，hm1.materia1)White，Plastic；White，Iron；Black，Plastic；Black，Iron；Metal，IronC2：C(hm1.mdl，hm1.md2，hm1.rod3)conn，conn，conn；conn，conn，unconn；conn，unconn，conn；unconn，conn，connC3：C(hm1.priml， 1.prim2)court，COBB；conn，unconn；unconn，conn(8)资源约束C4：b1.slot1b1.slot2b1.slot3b1.slot4b2.slotlb2。

slot2b2.slot3b2.slot4b3.slotlb3.slot2b3.slot3b3.slot4≤b4.slotC 5：b5.power1b5.power2b8.powerlb8.power2≤b4。

powerlC6：b7.powerl≤b6.powerl(9)包含性约束inclA1：hm 1Hmonitor>hm.colorA2：hrn1Hmonitor>hm1.xgalinclA3：hm1Hmonitor>hm1.sec11nclA4：hmlHmonitor：>hm1.mdllnclA5：hm1Hmonitor二>hm1.prim1lnclA6：hm1Hmonitor>hm1.bs11nclA7：hmlHmonitor hm1.md3ine1A8：hm 1Hmonitor>hm 1.materialinclA9：hm1Hmonitor>hm1.md21nclA mo：hm1.xgalconn>b61nclAl l：b6 XGA-disp-card>b6.disp 11nc1Al2：b6.disp1conn b71nc1AI 3：b7.siglconn>b6inelAI4：b7 Displ-21>b7.sigl1nclA15：hm1.see1conn>b7inclAl6：hm1.md1conn>b18 2013，49(14) ComputerEngineeringandApplications计算机工程与应用图6 基于CCSP的可配置医用监测器图形化模型Al7：hm1.md2conn>b2inclAI 8：hm1.md3conn>b3inclAl9：hm1bs1conn>b4incA20：hm1.primlconn>b5inclA21：b5Displ-1 0 b5.siglinclA22：b5 Displ-14 b5.sig2inclA23：b4Base unit>b4.displlticlA24：b5.siglconn>b4inclA25：b5.sig2 conn b4inclA26：hm1Hmonitor>hm1.prim21nclA27：b6 XGA-dispcard>b6.powerlinclA28：b7：Disp-2 1>b7.powerlinclA29：b5Displ-10 b5.powerlA3o：b5 Displ-14>b5.power21nc1A31：b3M AHD b3.slotlinclA32：b3M NM >b3.slot21nc1A3：b3M S>b3.slot31nc1A34：b3M RS b3.slot4inc1A35：b2M AHD b2.slotllnclA36：b2M NM >b2.slot2lnclA3 ：b2M S>b2.slot31nclA38：b2M RS b2.slot41nclA39：b1M AHD >b1.slotlinclA40：b1M NM >b1.slot2lnclA4l：b1M S>b1.slot3lnclA42：b1M RS>b1.slot4袁际军，黄敏镁：基于UML与CCSP的产品配置方法 9表 1 求解结果A43：b4Base unit>b4.disp2inclA4：b4Baseunit>b4.slotinclA45：b4.disp1conn>b5inclA46：b4.disp2conn>b8inclA ：b8Displ 1 0二>b8.powerlinclA48：b8Disp l4>b8.power2inclA49：hm1.prim2conn>b8inelAso：b8Displl 0 b8.sig 1inclA5 b8Displ-14>b8.sig21nclA52：b8.sig1corm>b4inclA53：b8.sig2conn>b4inclA54：b4Base unit>b4.powerl(10)排斥性约束exclEl：hm1.xgalunconn>b6exclE2：b6.displunconn>b7exclE3：hm1.sec1unconn>b7exclE4：hm1.mdlunconn>blexclE5：hm1.md2unconn>b2exclE6：hm1.md3unconn：>63exclE7：hm1.primlunconn>b5exclE8：b4.displunconn>b5exclE9：hm 1.prim2unconn b8exclEl0：b4.disp2unconn b84.2 配置问题求解在将配置问题抽象为条件约束满足问题后，对配置问题的求解等价于对相应的条件约束满足问题的求解。本文采用深度优先的传统回溯算法实现对CCSP的求解。在求解过程中，从非空初始变量集合中挑选-个活动变量进行赋值 ，通过对该变量的赋值使当前的部分赋值状态被扩展，并转变到-个由扩展的部分赋值所表示的状态。在对每-个当前活动变量进行赋值时，相继检查当前状态的部分赋值是否满足激活性约束和兼容性约束，如果满足 ，则继续对下-个新变量进行赋值；如果不满足，则从当前变量值域中挑选另-个域值进行新的赋值，并对产生的新状态再进行约束检查。如果当前赋值变量中所有域值都不能使当前的部分赋值满足所有约束，则该部分赋值将不会出现在问题的任何可行解中，其相应的状态称为无解状态，这时搜索将返回至上-个已赋值变量并重新进行赋值，以试图避免无解状态的产生。程序的终止以求解到所需要的解或发现无解为止。

对条件约束满足问题的求解算法性能的衡量，本文采用如下评价指标：(1)可行解个数；(2)求解时间；(3)回溯次数，是指在求解过程中遇到-个无解状态而不得不回溯至前-求解状态的次数；(4)兼容性约束检查次数，是指在判断当前变量的赋值是否为-个有效的赋值而对兼容性约束进行检查的有效次数；(5)条件约束检查次数，是指对当前变量赋值后，判断目标变量是否被触发而对激活性约束进行检查的次数 。仿真求解的运行环境是WindowsVistaaBusiness，InterCoreTM 2 Duo CPU T7100###1.80 GHz1.80 GHz，内存为 1 014 MB，编程语言为MATLAB 7.1。求解结果见表1所示。

进-步分析可发现，该配置问题的兼容性约束数量很少，对应的是-个较为稀疏的约束网络。随着兼容性约束数量增加，所有评价指标值将会发生较大变化。不过本文并不准备进-步地比较在各种兼容性约束密度和激活性约束密度下算法求解性能的变化；而只是强调在将配置问题映射为条件约束满足问题后，通过适当修改求解约束满足问题的各种算法，可得到许多丰富的求解算法用来求解条件约束满足问题。

5 结束语本文首先概要分析了条件约束满足问题内涵；然后提出了基于UML和CCSP的产品配置建模与求解方法；开发了-套基于CCSP的图形化符号以便可视化地表示产品配置知识。通过定义基于UML表示的产品配置概念知识与基于CCSP的图形化符号表示的对应产品配置知识之间的映射规则，方便了基于CCSP的产品配置模型的快速建立与维护。最后采用了可配置医用检测器案例，对基于UML和CCSP的产品配置方法进行了详述♂果表明本文所提方法能够方便地建模产品配置知识并实现对配置问题的求解；验证了所提方法的可行性与有效性。