基于案例库和遗传编程的ETO 产品配置设计方法研究①

沈永康 华尔天 何志国 陈万前 汤守伟

(*浙江工业大学先进制造研究所 杭州 310023)

(**浙江水利水电学院先进水利装备浙江省工程研究中心 杭州 310018)

0 引言

随着客户需求不断向多样化、个性化方向发展,相比于传统的按订单装配(assemble-to-order,ATO)和按订单制造(make-to-order,MTO)类产品,按订单设计(engineer-to-order,ETO)类产品的需求越来越多。产品配置设计技术作为大规模定制的有力工具[1],目前依赖其实现ETO 产品定制的研究中,文献[2]通过分类ETO 产品零部件,将产品的整体配置转化为非精确配置和精确配置两部分,提出了一种减少定制零部件种类的配置设计方法。文献[3]针对ETO 产品不同类型模块的特点,提出了依据强、弱条件规则实现模块精确、相似配置的配置方法,避免了基于实例配置方法中各属性权值和选择阈值难以选定的问题。文献[4,5]运用DCSP 模型表达ETO 产品配置模型的方法,方便了配置问题的求解。文献[6,7]通过构建基于模块化的产品架构配置和基于模块参数的可拓展配置两阶段模型,提出了一种ETO 产品配置设计新思路。文献[8,9]针对ETO 产品配置过程中存在设计知识的变更和创新,提出了开放式配置的概念和架构,拓宽了配置设计思路。上述研究对ETO 产品配置方法和配置模型进行了探索,为ETO 产品的智能化、创新性配置设计提供了思路。

在采用进化算法实现产品智能化配置设计方面,文献[10-12]针对不同产品优化目标构建产品配置优化数学模型,通过遗传算法实现了产品配置的优化求解。文献[13]通过改进设计变异个体和遗传操作提出了改进交互式遗传算法,在产品配置中有效利用了不同用户的偏好,同时减少了用户的疲劳强度。文献[14]结合遗传算法的进化策略改进了粒子群优化算法,提高了产品配置求解的效率和质量。文献[15]基于遗传算法提出了需求驱动、知识制导的产品杂交配置设计算法,实现了产品参数上的变型设计。但针对复杂产品,通过直观表达产品各层次的结构组成关系和柔性配置技术研究,实现ETO 产品配置设计的创新和整体优化尚缺乏有效手段。本文将遗传编程引入到ETO 产品的配置设计中,采用树图模型表达配置产品结构,提出了一种基于案例库和遗传编程的ETO 产品配置设计方法,并在此基础上构建了原型系统,进行了实例验证,力图为产品配置设计提供一种工具化手段。

1 遗传编程和配置设计模型

1.1 遗传编程

进化算法是一种高度并行的、随机的、自适应的搜索算法,能够不受问题性质的限制,有效求解传统方法难以解决的复杂问题。进化算法的特点是:随机生成初始种群,对环境知识依赖少;利用内在进化机制继承优良个体的基因生成新种群,在适应度函数引导下反复迭代逐步向最优种群收敛;在进化过程中淘汰大量不良个体,不需要所有个体参与评价,适合智能化、创新性的求解[16]。遗传编程(genetic programming,GP)作为进化算法的分支,与一般遗传算法不同:采用动态可变的树型结构编码,节点可针对不同问题领域灵活定义;编码结构可携带语义信息,不必考虑编码空间与解空间的映射问题[17],适合处理“开放解”的创新设计问题。产品配置设计方案包含不同层次和特征的构件,其相关信息来自可转化为树型结构的产品物料清单(bill of material,BOM),且配置设计过程中构件数量动态可变,产品整体结构具有不确定性,与GP 树型编码相契合,方便调用已有产品信息和直观描述产品演化过程,是常规定长字符串编码无法具备的优势。

1.2 ETO 产品配置设计模型

ETO 类定制产品的物理构件无法完全预定义,可先通过配置模型选配出完全或部分满足需要的构件实例,确定产品基型和部分参数,再对无法满足客户需求的构件进行变型设计甚至重新设计[18]。为实现ETO 产品智能化、创新性的配置设计,将遗传编程引入到ETO 产品配置设计过程中,通过类比得到如表1 所示的对应关系:初始种群从产品案例库中生成;选择操作对应产品基型和部分参数的确定;交叉、变异操作对应构件结构调整、参数优化及新增构件的添加;约束判定由客户需求、产品配置关系和设计要求进行设置。

表1 遗传编程各环节与ETO 产品配置过程的对应关系

根据上述分析,建立ETO 产品配置设计模型,如图1 所示主要流程为:分析和转化客户需求,从案例库中获取初始种群,并构造产品功能树作为选择算子;对选出的种群个体进行适应度评价,根据评价结果与终止准则,判断是否继续进行进化操作产生新种群,对满足要求的结果进行筛选与转化并结束设计过程,将新得到的产品配置方案纳入产品案例库。

图1 基于案例库和遗传编程的ETO 产品配置设计流程图

2 ETO 产品配置设计关键技术

2.1 客户个性化需求转化

为方便客户需求信息的准确表达、获取和转化,令:

式中,C-Unit为客户需求单元;C-needtype为需求的类型,如功能、结构等需求;C-datatype为需求属性值的类型;C-dataconts为需求属性值的约束;C-datavalue为需求属性值的值域。

定义:实现某一种或几种功能需求的装配体为功能单元。令:

式中,F-Unit为功能单元;F-id为功能单元的唯一标识;F-type为功能单元的类型;F-datavalue为功能单元的属性值;F-instance为功能单元的实例对象信息。以上信息采用事物特性表描述[19],用于客户需求到功能单元的映射。

如图2 所示,将客户需求转化为对应的功能单元或新功能结构,按产品结构和约束关系组织调整为产品功能树。根据式(1)客户需求单元的描述,将需求映射为对应的功能单元实例,可一对一或多对一映射。若已有实例无法完全满足客户需求时,根据事物特性表对已有构件进行参数化或拓扑结构变型设计,派生出符合要求的新实例对象;若无匹配的实例时,通过设计人员设计或知识库搜索获取满足客户需求的新功能结构,并明确与已有构件的约束关系。若该结构与已有构件存在耦合关系,根据公理设计进行降耦和去耦设计[20]。产品功能树为满足客户需求的概念设计结构,并非包含完整构件信息和约束关系的具体产品结构,按2.3 节编码规则将其生成产品功能树图ex。

图2 客户个性化需求转化过程

2.2 案例库模型

案例库模型是在对同类产品构件实例共同特征属性抽象与分类的基础上组织的案例信息模板,由案例模板、案例结构原型、案例等树图组成,各树图由不同类型节点和关系来表示产品不同层次结构组成、分类和配置关系。

如图3 所示,案例模板采用模块化结构表达产品功能结构信息,其树图节点包含必选模块、可替换模块和可选模块3 类,可替换模块具有多个相同接口和功能的子类,如M3有M31和M322 个子类,其他模块的部分构件也可存在多个子类;上述各模块确定后得到多种抽象的案例结构原型;对结构原型各构件进行实例化,即结构选定和参数赋值,派生出多个产品案例。基于企业模块化的产品族设计,将已有产品案例按上述演化关系进行组织,对不同配置结构信息和配置条件,采用包含约束关系、配置规则的事物特性表和决策表描述。案例信息采用式(3)表示,案例模板、案例结构原型也按此方式表示,由于篇幅限制进行省略。

图3 案例库模型

式中,ID为案例唯一标识符;CP={cp1,cp2,…,cpk}(k＞0) 为案例特征参数集,描述产品的外部功能性指标,每个特征参数对应一项客户需求,用于支持初始化种群;M为案例的模块组成和类型,即所属的案例结构原型;C为各模块具体构件的组成和类型;F={f1,f2,…,fl}(l＞0) 为各构件的主要特征参数,如功能属性、结构尺寸等;φ 为各构件特征参数之间的约束集。

2.3 编码规则和初始化种群

根据式(3)的案例信息,结合遗传编程编码规则,定义产品树图编码结构(图4):根节点(C)表示产品,中间节点分层依次表示部件(A)、组件(Z)、零件(P)等构件,末端叶子节点表示不再分的结构,可为不同层次的构件;树图的拓扑结构表示构件间的组成关系,各节点构件编号与案例库构件保持一致,且各节点封装对应构件的特征参数信息。

图4 产品树图编码结构

初始化种群是根据编码规则,在约束条件下随机生成能解决问题的种群个体。根据式(1)的客户需求信息,结合案例库模型中各结构的特征参数,从匹配的案例模板中随机调出满足或接近客户需求的产品案例,按编码规则生成产品树图组成初始种群{e1,e2,…,en}(n＞0)。

2.4 遗传操作

2.4.1 基于相似系统论设计的选择操作

将产品功能树图作为初始种群的选择依据,基于相似系统论筛选出优化的设计案例,作为配置设计的产品基型。由产品树图和产品功能树图的编码结构可知,它们都为包含功能和结构的系统,可采用相似系统论计算两者之间的相似性[21]。选择操作的具体步骤如下。

(1)基于相似系统论计算树图的相似度

现以农业作业机主要配置结构为例,对按上述环节操作构造如图5 所示的产品功能树图A和产品树图B进行相似度计算:将两树图中对应层级的节点构成两集合,如第3 层级A3={a1=变速箱,a2=齿轮}、B3={b1=变速箱,b2=皮带}。将各层级两集合的笛卡尔乘积组成元素组,表示为{(am,bn)|am∈Ai,bn∈Bi}。找出相似节点计算相似度。两树图的相似度为

图5 农业作业机树图结构

式中,Sk为两树图间的相似度;αi为相似节点对两树图相似度的影响程度;num(nodAi∩nodBi)、num(nodAi∪nodBi) 分别为相似节点位置节点交、并集中的元素数量(位置节点为该节点到根节点所经历的节点);0 ≤s(ui)≤1 为相似节点的相似度,由构件各特征参数的相似性决定,如几何形状、尺寸大小、功能信息等。

(2)选择初始种群

将产品功能树图(ex)与初始种群产品树图(en)按照式(4)、(5)进行相似度计算。根据所求相似度大小,对种群个体进行降序排列。

设置相似度阈值为S△=△,以阈值大小为标准选择初始种群,得到子代个体为

2.4.2 交叉

交叉通过产品构件间结构、参数的互换,使新生子代在兼具父代优秀特征的基础上获得新优秀特征[22]。考虑产品树图表达的特殊性及产品设计的约束,交叉操作可分为以下2 种情况。(1)结构交叉:对表示相同功能属性的树图子结构,互换结构及其参数,如图6(a)所示;(2)参数交叉:对表示相同结构的树图子结构,互换相同结构的对应参数,如图6(b)所示。当某节点所有子节点被设置为交叉点时,该节点为非交叉点;当父节点被设置为交叉点时,其下子节点为非交叉点。

图6 交叉操作示例(虚线框中为交叉对象)

2.4.3 变异

变异用于产品预定义构件、参数的调整及新增构件的开放配置,提高个体结构创新性和应用范围。

(1)案例库构件范围内的变异

该变异在案例库构件范围内对产品结构、参数进行调整,可分为以下2 种情况。(1)结构变异:在父代个体中随机选择某个节点,将该节点及其下子结构,用表示相同功能属性的子结构代替,其相应参数也随之调整,如图7(a)所示;(2)参数变异:在父代个体中随机选择某个节点,对其参数重新赋值,如图7(b)所示。

图7 变异操作示例(虚线框中为变异对象)

(2)针对开放配置的变异

根据2.1 节得到的新功能结构构件和约束信息,确定变异节点位置和新增树图子结构。假设某产品案例库内未包含用于移动的结构,针对便于移动的客户需求,可调动此变异操作:CR={移动}={DSD1=车轮、DSD2=制动器、DSP=底座}(CR 为客户需求;KD 为配置知识域;DSD、DSP分别为配置结构、变异节点结构)。根据上述信息,执行变异操作得到如图8 所示的产品树图结构。

图8 变异后的产品树图结构

2.5 导向进化规则和种群约束判定

2.5.1 导向进化规则

导向进化规则描述产品配置设计的判断性知识,用于指导和约束交叉、变异算子,保证进化计算的寻优能力和收敛速度[23]。导向进化规则与案例库模型建立关联关系,采用判断操作的产生式规则描述,规则前件用条件表达式描述构件结构、参数引用的逻辑表达,用于指导获取评价信息后待遗传操作个体的请求操作;规则后件用操作表达式表示“导向进化行为”,即参数变异上按照一定的概率上调、下调或设置某个特征值,结构变异上按照一定概率调整各构件实例,以及“相关诱导行为”,即用关系表达式或赋值表达式描述相关构件、参数的推导关系,在交叉、变异时诱导构件内、构件间参数或构件实例的调整。

2.5.2 种群约束判定

对于进化得到的后代,需要经过关系推演、设计校核,判断其是否满足约束条件,保证种群个体的有效性。(1)关系推演。对后代个体树图进行广度优先遍历,根据构件编号从案例库中调出相关知识信息对其配置、参数关系进行推演,剔除不满足约束条件的个体。产品配置约束关系有相容约束、依赖约束、可选约束等。产品参数约束关系有构件内约束、同级构件约束、父子级构件约束、跨级构件约束等[24]。(2)设计校核。经关系推演后,从产品尺寸、性能、安全性等方面对个体进行设计校核。获取个体需要校验的构件,确定构件样式后按固定模板计算其相关校核信息,若个体满足所有设计校核,则在下一步对其进行适应度评价;若存在不满足的设计校核,保留其相关校核信息,将该个体继承到下一代继续演化;若校核结果有错误提示,将该个体直接剔除。

2.6 基于信息公理的适应度评价函数

适应度评价函数的好坏直接影响所得最佳个体的优劣。信息公理是指在满足独立公理条件下,信息量最小的设计方案为最佳设计方案,不用考虑多属性评价指标的量纲和单位是否一致,也不需要决策者给出指标的权重[25]。因此,针对满足约束条件的多个ETO 产品配置设计方案,基于信息公理构建适应度评价函数。

综合客户、设计者、企业三者不同的关注角度,从功能性、结构性、经济性三方面建立产品设计方案的评价指标。现以机械传动产品评价为例,讨论各评价指标对象的信息量计算。

(1)以传动精度、承载能力等为功能性评价指标对象。

式中,I1、I2分别为传动精度、承载能力的信息量大小;y0、y分别为功能要求和设计方案的传动精度;f为承载能力评价值,大小为[0,1]区间的连续数值,从评价模糊语言转换而得[26]。

(2)以构件的结构复杂性、可制造性等为经济性评价指标对象。

式中,I3、I4分别为结构复杂性、可制造性的信息量大小;k为产品的构件数目;m为构件的可制造性大小,取值区间为[0,1]。对于标准件,m=1,其信息含量为0。

(3)以尺寸限定、安全检核等为结构性评价指标对象。

式中,I5、I6分别为尺寸限定、安全检核的信息量;ai、a01、a02依次为备选方案、理想方案、最劣方案的尺寸值;校核区间为x=[xl,xu],系统范围为(xl+xu-2xmin)/2,公共范围为xmax-xmin。

按产品树图结构计算各评价指标的信息量大小,若产品构件间存在耦合,可通过模糊APH 方法建立有效功能设计矩阵,归一化处理后得到构件的功能耦合度[27],再由下往上逐层计算产品各构件的适应度,直至计算出该评价指标的产品适应度。产品整体适应度函数为

式中,产品ex共有n1+n2+n3=n个评价指标对象;Ig(xi)、Ie(xj)、Is(xk) 分别为产品功能性、经济性、结构性评价指标的信息量大小。

3 原型系统

3.1 系统架构

基于上述设计流程,设计如图9 所示的人机交互原型系统,即方案的生成、进化由计算机完成,其余由人工完成,为产品的配置设计提供一种工具化手段。原型系统由功能相对独立的模块组成,利用人工智能,计算机图形处理能力和模拟生物进化算法相结合,通过人机交互界面输入客户需求和进化参数,经过设计模块的反复迭代、评估、筛选,获得符合设计要求的产品配置设计方案,再通过辅助绘图模块完成具体产品结构的设计呈现。

图9 原型系统架构

3.2 设计知识库

设计知识库由模型库、规则库和数据库组成。模型库中树图编码信息模型用于树图编码与产品案例之间的转化;案例库按2.2 节组织形式储存企业历史和新的产品案例;构件库按功能特征储存构件。规则库中编码规则为树图编码与案例、构件其他图之间的转换规则;配置规则为产品结构、导向进化规则和种群约束判定等相关知识。数据库用来存储客户需求、进化设计参数等数据,方便对设计数据进行访问和管理。

3.3 需求分析模块

需求分析模块由客户需求本体和产品功能单元本体构成,实现客户需求向产品结构的转化。采用本体建模软件Protégé 构建本体模型,对客户需求信息和产品功能结构信息进行规范化表达和组织,再通过两本体间的映射关系和规则,实现信息的传递,完成本体间的互操作,即输入客户需求,经本体检索获取对应的功能单元,再将其组织编码为产品功能树图。

3.4 设计模块

设计模块由案例检索模块、进化计算模块和筛选模块组成。利用Matlab 中GPlab 工具包现有模块实现综合算法,案例检索模块用于对初始种群的选择操作。根据客户需求调用相应产品案例生成初始种群树图,设置相似度阈值,执行2.4.1 节选择操作产生供进化计算模块调用的种群个体。进化计算模块用于对树图结构执行2.4 节中定义的交叉、变异操作,设定相关参数:种群规模N、交叉率Pc、变异率Pm、进化代数n,利用编码运算完成进化设计过程。生成的新子代个体需结合筛选模块,多次迭代后达到终止准则条件,即满足最大进化代数或适应度值条件,最终得到最佳种群。筛选模块用于指导进化计算、优秀个体的筛选,主要实现2.5 节的约束判定及2.6 节的适应度评价。

3.5 进化结果选择与转化

经设计模块获得进化解集,进化解集中解的数目存在以下几种情况。(1)唯一解。直接输出产品BOM 表或通过辅助绘图模块输出具体的产品结构图。(2)多解。进化解集中存在多个解时,排除表示相同产品配置方案的解,剩下的解选择企业便于生产或者更加满足客户某种需求的解。(3)无解。此时需要调整输入参数重新设计。通过辅助绘图模块解码及知识库中树图编码与构件间的转化规则实现进化结果的转化,系统按照设计人员选择的输出形式输出产品的BOM 表或产品结构模型,并存入到产品案例库中。

4 实例验证

堆垛机作为自动化立体仓库中的装载机械(如图10 所示),完成对货物的出入库工作,是物流装备的核心产品。由于客户个性化需求直接影响堆垛机设计方案的结构组成和参数选定,因此堆垛机属于典型的ETO 类定制产品。某物流设备企业现有产品定制主要依赖人工,存在研发周期长、自动化水平低等问题。采用本文提出的方法对堆垛机进行配置设计,弥补企业现有配置设计存在的不足,并验证原型系统的可行性与适用性。由于堆垛机的结构组成较为复杂,列出部分主要结构进行配置演示。

图10 堆垛机示意图

首先通过原型系统输入客户需求,假设客户需求为:C={c1=货物单元长、宽尺寸为1200 mm×1000 mm,c2=货物重量为0.8 t,c3=仓库货架高度为10 m,c4=运行速度为120 m/min,c5=起升速度为30 m/min,c6=存取速度为30 m/min}等。通过需求分析模块转化得到对应功能单元(具体参数省略),组织生成如图11 所示的产品功能树图。

图11 产品功能树图

按2.3 节操作从企业“双立柱有轨巷道堆垛机案例模板”中得到初始种群,设初始个体种群数目N=18,其中结构原型1 中有4 个产品案例,结构原型2 中有5 个产品案例。列出案例e01、e05的产品树图(如图12 所示)和结构原型1、2 中产品各案例构件的部分参数(如表2 所示)。

表2 结构原型1 和2 中产品各案例构件的部分参数

图12 产品案例树图

将产品案例e01、e05树图与产品功能树图相比,在功能结构上,如e01的双立柱上缺少起升导轨、载货台上缺少存取机构,e05的升降组件和存取机构与其组成不同;在功能参数上,可分析出参数的调整趋势,如运行速度和起升速度大小、载货台大小等。

根据2.4.1 节的相似度计算方法,得到如表3所示的各产品树图与产品功能树图的相似度大小。设置相似度阈值S△=0.7840,选择相似度阈值范围内的产品案例{e01,e02,e03,e04,e10,e11,e12,e13,e17,e18}进行后续遗传操作。设定相关进化计算参数:交叉概率Pc=0.6,变异概率Pm=0.4,进化代数n=50。经进化计算模块按照2.3 节所述交叉、变异操作逐步演化,适应度按第2.6 节实例计算,最终得到的最优产品配置方案部分结构、参数如表4所示。

表3 产品案例相似度大小

表4 最优配置方案的部分结构参数

上述配置方案,是在企业已有案例基础上,利用进化计算实现起升电动机、钢丝绳、行走电动机等通用件实例型号的选定,卷筒、货叉等定制件的变型设计,完成了堆垛机的配置设计。该方法减少了传统繁琐的人工设计活动,实现了一定程度的设计自动化,提高了企业产品配置设计的效率。

5 结论

本文提出将遗传编程运用到ETO 产品的配置设计过程中,构建了包含结构性与过程性知识的产品案例库,有效组织、便于重用产品配置知识;采用树图编码产品,结构组成、层次关系清晰,方便产品结构的拓展和进化;制定导向进化规则及约束判定机制,利用进化操作快速实现ETO 产品配置方案的智能化求解,解决了构件设计中大量重复的设计活动,提高了产品配置的效率。在此方法的基础上构造配置设计原型系统,以堆垛机的配置设计为例,验证了该系统的有效性及合理性。本文力求为设计人员提供一种产品配置设计的工具化手段,实现一定程度上的人机混合智能,但在复杂参数优化、权衡配置知识与企业柔性定制能力、开放配置变更影响评估等方面有待进一步研究。