一种基于复杂网络技术的产品约束建模及求解方法*

马裕港，刘夫云，刘秀娟，苏其杰

(桂林电子科技大学 机电工程学院，广西 桂林 541004)

一种基于复杂网络技术的产品约束建模及求解方法*

马裕港，刘夫云，刘秀娟，苏其杰

(桂林电子科技大学 机电工程学院，广西 桂林 541004)

针对变型设计中的工程约束满足问题，将工程参数与尺寸参数放入同一个网络，建立了包含尺寸约束和工程约束的网络模型。对该模型进行去环和分层，使其与有向树图有着相似的拓扑结构。通过子图的搜索，在子图中运用回溯算法进行网络的约束求解，使产品满足工程约束条件。最后以轴的设计为例，通过与尺寸驱动的变型设计方法相对比，验证了上述方法的可行性。

变型设计；工程约束；约束求解

0 引言

随着产品数字化设计的发展，变型设计大大缩短了企业的产品设计周期。现有的以尺寸驱动的变型设计很好的表达了几何尺寸与参数之间的关系[1]。目前国内刘夫云将复杂网络理论应用于大批量定制的产品配置领域，在构建的产品尺寸关系网络中，使用子网搜索算法与简单路径搜索算法快速查找需要修改的模块与尺寸[2]。郭于明[3]从变型设计需控制设计变更传播的范围等特性出发，依据变型设计的时间与资源约束条件，给出节点评价方案。满足产品设计质量需求的同时，也能保证控制变型设计传播范围的需求。徐新胜[4-5]等提出基于贝叶斯方法的尺寸变化概率分配模型以及重用零件实例的产品变型设计方法。上述方法是以几何尺寸为基础对产品进行参数配置来实现的变型设计，其中缺少了对尺寸与工程约束之间关系的表达。

但在产品变型设计中，尺寸参数修改往往要受到涉及不同学科的多个工程约束条件[6](如强度、刚度、热力学、零件几何中心等物理约束)的限制。潘双夏[7]对产品尺寸与工程约束进行分析给出了，有效解决工程设计约束的分类及其动态化和智能化处理的方案。刘小平[8]引入了多元约束图，提出了最小约束度优先和最小值域范围优先的约束求解算法大大缩小了搜索范围。但都没有给出尺寸参数与工程约束之间的传递关系。本文以尺寸驱动的参数化模型为基础，将工程参数与尺寸参数放入同一个网络，建立了包含尺寸约束和工程约束的网络模型。用网络遍历算法对参数进行传递，用回溯算法对模型进行求解；使产品在变型设计成功后能满足网络中的工程约束条件。

1 建立网络

变形设计是指提取已存在的设计或设计计划、作特定的修改以产生一个和原设计相似的新产品，其过程一般不考虑尺寸和工程约束的关系。因此在建立网络模型时将尺寸间的约束简化为线性约束。但是在实际过程中的变型设计，尺寸间的约束关系并非都是线性的。其中包括尺寸与尺寸之间的，尺寸与工程条件之间的等非线性关系。也就是说尺寸在变型设计过程中不能完全脱离尺寸与工程约束之间的关系。

为了建立面向工程的约束网络能有效的表达，先要对约束进行分类表示。面向工程的约束在设计过程中可以分为二大类：几何约束模型和知识约束模型。几何约束模型中的约束主要为尺寸约束，其处理不涉及复杂的设计计算和逻辑判断。几何约束模型在网络中的构建方法[9]：以零件尺寸参数为节点，以参数之间的约束为为边，边取加权有向边，约束方向按照尺寸之间的数学约束关系直接转化。例如有约束关系A=0.5B+C+12，从约束关系中可以得到B和C是已知的，A是通过B和C计算得到的。因此在尺寸参数关系网络中，从已知的B出发指向待求的A；从C已知的出发指向待求的A。

在知识约束模型中包括领域设计知识约束和强度刚度约束。其分配过程不涉及任何零部件尺寸参数，但是在设计过程中是非常重要的一步。不同的产品有着不同的领域设计知识，因此其约束的形式也不同。其主要是将产品的性能参数通过数据处理或函数来表达，但是其数据最后还是流向零部件的尺寸参数。强度刚度约束是产品设计中必须满足的，它是产品最基本的约束。约束与尺寸参数有直接关系，一般为约束目标参数必须大于或少于约束源参数所构成的表达式的值。工程约束相对尺寸约束来说其复杂体现在二个方面：一是其约束的复杂性，在工程约束中大多为非线性约束；有些甚至不能用数学表达式来表达。二是其约束关系的复杂性，在工程约束关系中常常会出现约束冲突、耦合等情况。因此在建立网络时只保留保留其节点之间的约束拓扑关系。

通过对网络的节点度的统计规律发现，属于无标度网络。它具有二个重要的特征增长与择优连接。该网络与树有着类似的网络统计参数和拓扑结构，继承了树的一些特性。

2 网络模型相关算法描述

2.1 分层

当约束从线性变成非线性时，就很难用一个通用的公式去表达二个节点之间的约束关系。为了让节点参数在网络中传递，本文提出了一种基于遍历的参数传递方法。当两节点之间的参数无法直接传递时，先通过节点之间的路径搜索得到一条路径后，再在此路径上一个节点一节点进行参数传递。如有如图1所示的一条路径。

当X1=20时，X2=314，X3=5024，X4≈0.08。虽然参数无法直接从X1传到X4，但是通过分步可以让网络适应比较复杂的约束条件。

按照上述方法在网络中进行参数传递，参数的传递其实是对网络节点的一种遍历。在图论中对有向图的没有给出明确的遍历算法，但是对于树给出了相应的遍历算法。对于无向树的遍历有前序遍历、中序遍历与后序遍历，对与有向树的遍历算法却没有说明。利用无向树的遍历算法对上述网络进行遍历，存在一个问题：给出的遍历算法是从根到叶的搜索，在这种情况下往往会遇到枝没有被确定的时候对叶进行计算。上述问题产生的原因是建立的网络不满足树的定义，不是严格意义上的树；主要是因为网络中的约束并不都是二元，即存在简单回路。但是网络图依然有着树图的拓扑结构。

本文在树高的定义上得到启发，提出了一种分层遍历搜索算法。该方法先对树进行分层确定其树高，再对每一层的节点进行遍历。其特点就是在遍历完每一层后再去遍历下一层。如图2所示的无向树，对其进行遍历。

图2 无向树图

用前序遍历得到的结果为：

a

用中序遍历得到的结果为：

g

用后序遍历得到的结果为：

g

用分层遍历得到的结果为：

a

前序遍历的方法在于深度优先进行遍历。虽然每条路径中的节点被遍历的顺序是满足先后要求的；但是在设计过程中约束关系比较复杂，这使前序遍历在参数传递过程中不能保证其深度优先。分层遍历对节点参数在网络中传递是有效的，在有向树中可以得到想要的结果。

区别于树图的树高确定根据路径而来，网络中层高的确定是根据约束关系来的。因为树图中的有向边只有结构关系、没有约束关系。

2.2 去环

在网络的分层中参数的同向传递和逆向传递使网络的分层遇到问题。对其进行分析发现，参数发生同向传递与逆向传递是因为网络中存在环。网络中的环存在二种不同的形式，这里分别将其称为开环与闭环(如图3所示)。

图3 网络中环的形式

环的出现不仅仅使分层出现问题，二点之间的所有简单路径变的搜索也变的非常困难，至今仍没有找到好的解决方法。网络中的边为产品设计的约束条件，删除边来实现的去环可能会丢失产品在设计中的约束条件。通过节点的分层，找到引起参数同向传递或逆向传递的边。为了消除这种现象的同时保留其约束条件，将约束条件进行延时处理。延时处理是将约束暂时不放入参数网络传递中去，等参数传递完成时再回来考虑其约束是否满足要求。这样做的目的是为了保证参数在网络中快速准确传递的同时不丢失约束条件。当网络在分层中遇到环时，对相应的约束进行延时处理。在实际产品设计时发生环的情况一般为约束满足判断或是对之前预设的尺寸进行确认。其不对节点再次赋值，对其约束延时不影响网络中的参数传递。

3 约束求解

变型设计是在原有模型的基础上对其进行修改。然而当某个或某几个尺寸发生变化时，新的模型不能保证其各个尺寸都是满足其原来的约束条件。为了使新的模型能满足其原来的约束，同时不对模型的每个尺寸进行调整。通过搜索变量节点的子图来减少节点数。因为如果一个解X={x1,x2,…,xn}是满足图G的一个解，那么X也满足图G的任何一个子图。当搜索出子图G′的所有解X′时，X⊃X′。在网络中除了可变参数外导出参数与不变参数对网络冲突的影响不大，因此子图G'的解X′与图G的解X相差不是很大。通过对子图G′搜索可以减少回溯算法中节点数量。

因为所建立的网络与树有着类似的网络统计参数和拓扑结构。所以以有向树为例，对网络回溯进行求解。在传递过程中不是所有节点对传递的影响都很大，其影响主要来源于几个参数。而这些参数之间存在一定的适应性。该适应性表现为：假设一个位于4层的节点f。

图4 分层后的有向图

当节点f发生修改时，如果它满足了上下层之间的约束，那么它的改变对整个网络的影响并不大。当打破这个适应能力时，它的改变对网络的影响可以会扩散到整个网络。如果当4层节点f的变化打破与3层节点b之间的约束时；为了满足3、4层之间的约束对3层参数进行修改后，就会扩散到2层。当4层节点f的变化打破与6层的节点h之间的约束时，修改就会向下层扩散；为了满足4、6层之间的约束对6层参数进行修改后，就会扩散到7层。因此，在节点f修改后，对其进行节点的入度进行遍历。遍历出节点f之上的二层对其直接影响的参数如图5所示。

图5 节点f的上层节点的子图

该回溯算法的关键在于，对子图进行约束求解。与原有的回溯算法不同，在子图中，回溯算法用来搜索出上一层节点b和c在不引起节点a变化时的取值对节点f的修改进行适应性的取值。在路径唯一时该算法与传统的回溯算法没有区别。

从以上参数传递的影响来看，参数之间有着一定的适应性与影响区域。从整个网络中看参数影响区域包括了其出度的各个支路，直到出现下层的可变参数或支路的终点。因此在对网络修改时为了不让局部的修改影响到整个网络的修改，对几个主要节点之间的参数调整非常关键。

4 工程实例

以输出轴尺寸为例，对输出轴(如图6所示)中的20个尺寸进行尺寸约束网络建立，可得如图7所示的网络。

图6 输出轴

图7 轴的尺寸约束关系网络

加入工程约束时将得到图8所示的网络。

图8 轴的约束关系网络

对图7、图8中的节点出度进行统计得出其节点度分布图9。

(a)尺寸约束关系 (b)工程约束关系图9 网络节点度分布图

随着网络中节点的增加，其度的分布满足幂律分布，因此该网络是无标度网络的一种。

当对轴进行变型时(其他零件的尺寸约束不变的情况下)，已知变型的n=93.61r/min，T=900N·m。传统的变型设计方法通过计算最小轴径计算得到dmin=52.1mm并考虑联轴器的型号取d=55mm，从而得到键的尺寸为16×10×70。但是σp=129MPa是不符合许用挤压应力[σp]=120MPa>σp的要求。当键不满足强度要求时，通过回溯将对φ1进行修改。当其增大为60mm时，σp≈100MPa<[σp]满足挤压应力的要求。

5 结束语

本文通过建立了一种同时包含尺寸约束和工程约束的网络模型。在此基础上，用回溯法算法对模型进行约束求解，使产品在变型过程中能满足工程约束条件。以轴的设计为例，验证了方法的可行性。对于树形约束结构下的约束求解，可以实现满足工程约束的零件变型设计。为下一步实现满足工程约束条件的变型设计提供了关键技术支撑。

[1] 邓伟刚.面向对象的配置产品变型设计方法研究与实现[D].武汉:武汉理工大学，2010.

[2] 刘夫云,祁国宁,车宏安.复杂网络中简单路径搜索算法及其应用研究[J].系统工程理论与实践,2006(4):9-13,84.

[3] 郭于明,王坚.复杂产品开发网络中变型设计节点方案评价[J].计算机辅助设计与图形学学报,2014,26(2),320-328.

[4] 徐新胜,何晓柯,李丹.基于贝叶斯方法的尺寸变化概率分配及其在产品变型设计中的应用[J].中国机械工程,2011,22(15):1847-1852.

[5] 徐新胜,李丹,严天宏.面向柔性客户需求的产品变型设计方法[J].计算机辅助设计与图形学学报,2012,24(3):394-399.

[6] 侯文彬, 王增飞, 张伟, 等. 基于复杂工程约束的车身梁截面优化设计[J]. 机械工程学报, 2014, 50(18): 127-133.

[7] 潘双夏,张帅.基于工程约束的产品参数化建模策略研究[J].计算机辅助设计与图形学学报,2001,13(9):840-845.

[8] 刘小平,黄永红.工程约束表示模型与求解算法研究[J].计算机学报,1999,22(11):1153-1157.

[9] 孙吉贵, 高健, 张永刚. 一个基于最小冲突修补的动态约束满足求解算法[J]. 计算机研究与发展, 2007,44(12): 2078-2084.

(编辑 李秀敏)

A Method of Product Constraint Modeling and Solving Based on Complex Network Technology

MA Yu-gang, LIU Fu-yun, LIU Xiu-juan, SU Qi-jie

(School of Mechanical and Electrical Engineering,Guilin University of Electronic Technology, Guilin Guangxi 541004, China)

Aiming at the problem of the engineering constrain satisfaction of variant design engineering parameters and dimension parameters are put into a same network and then a network model including parameter constraints and dimension constraints is established. The network model is performed for delete-loop and layering for the sake of its topology similar to directed tree graph’s. In order to make product meet the engineering constraints backtracking algorithm is used for conflict resolution of sub-graph. In the end, compared with variant design method of dimension driven, the feasibility of the method above is verified by taking an example of a shaft.

variant design; engineering constraints; conflict resolution

1001-2265(2017)01-0066-04

10.13462/j.cnki.mmtamt.2017.01.018

2016-03-05；

2016-04-13

国家自然科学基金项目(51265006)；桂林电子科技大学研究生创新项目(GDYCSZ201440)

马裕港(1990—)，男，浙江绍兴人，桂林电子科技大学硕士研究生，研究方向为数字化设计，(E-mail)421956751@qq.com。

TH166;TG506

A