基于混合遗传算法的虚拟装配作业过程规划

焦玉民,徐 婷,刘 斌,于光亮

(1.94679部队,南京210038; 2.陆军工程大学 野战工程学院,南京 210007)

国家自然科学基金青年基金资助项目(51505498)

焦玉民(1984—),男,工程师,博士.E-mail:602093540@qq.com

基于混合遗传算法的虚拟装配作业过程规划

焦玉民1,徐 婷2,刘 斌2,于光亮1

(1.94679部队,南京210038; 2.陆军工程大学 野战工程学院,南京 210007)

提出了一种基于回报机制和逆向求解机制的装配作业规划方法.使用遗传算法与Q学习算法相结合,共同对作业过程规划问题进行求解.构建适合信息融合和进化计算的“维修元”模型,并将“维修元”进行排列组合,构成装配作业序列,解决装配作业过程中的信息融合问题.为保证作业序列的可行性和维修元的可操作性,将特征匹配机制作为启发机制,避免不可行序列参与进化计算,提高进化效率,解决了虚拟装配过程中多要素融合条件下的规划问题.

混合遗传算法; 虚拟装配; 过程规划; 维修元

虚拟维修训练系统作为一种智能化的训练手段,以其突出的特点和优势,成为训练模式向现代化发展的必然趋势.虚拟维修训练过程设计越来越注重训练内容的完整性和实用性[1-2].拆卸与装配是训练过程模型设计的重要内容,但对比于拆卸过程,装配过程涉及的维修要素类型复杂很多.目前，在具备规划功能的虚拟维修训练系统中,规划方法均较注重结果的有效性,忽视了操作者的作用,对于与操作者紧密联系的工艺性内容(维修工具选择、维修行为选择、装配类型判断等)涉及较少.如何将众多不同种类的信息进行融合,并应用于作业过程的实时规划,是装配作业过程规划研究的重点.

有向图方法凭借图形化描述和参数化表达的优势,能够较为完整地记录维修作业过程中发生的事件,因此常被用于过程建模[3-4];但由于该方法缺乏智能特性,难以将不同类型的信息进行规划,对操作者的指导意义有限.智能算法作为目标优化问题的求解方法,被广泛应用于作业规划问题[5-6];但智能算法的编码方式很难做到表达全部的维修知识信息,更重要的是,对于装配过程这类工程类问题,运算过程会频繁得到不可行解,极大地影响了进化效率和准确率[7].Q学习算法作为一种逆向求解的学习算法[8],支持从结果向原因逆向推理,借助启发机制,可以有效避免不可行序列参与进化计算.

针对上述问题,选取虚拟维修作业过程中与操作者相关的典型要素(维修工具、维修行为、装配类型)作为规划内容,构建“维修元”模型作为信息融合设计方案,使用遗传算法和Q学习算法共同对规划问题进行求解.为避免不可行序列参与进化计算,使用零件空间干涉机制和任务特征匹配机制作为启发机制,避免在复杂虚拟维修环境中,得到不符合操作规程的装配序列,增强规划结果对操作者的指导意义.

1 基于Q学习算法的装配作业过程模型

本文将虚拟维修过程离散化为“状态—动作”反复转换的过程,该过程中操作者可以按照某种先后顺序或策略完成虚拟训练过程中的维修任务.相应地,本文将装配作业过程中涉及的装配工具选择、装配行为选择、装配类型选择形式化为“动作”概念,与Q学习模型保持一致.为便于描述,在对规划问题进行求解之前,将虚拟装配过程形式化描述为三元组U={S,A,R},其中:S={s1,s2,…,sn}表示虚拟装配作业状态空间;A={a1,a2,…,an-1}∈{L,F,G}表示导致状态发生变化的动作备选集;R={r(s1,a1),r(s2,a2),…,r(sn,an)}表示“动作”的立即回报值.动作备选集中,L表示工具类备选集,L={lj|j= 1,2,…,J},〈s1,lj〉表示虚拟人在状态s1选择工具lj进行作业;F表示行为类备选集,F={fk|k=1,2,…,P},〈s1,fk〉表示虚拟人在状态s1选择行为fk进行作业;G表示装配类型备选集,G={gh|h=1,2,…,H},〈s1,gh〉表示虚拟人在状态s1选择装配类型gh进行装配,参数J,P,H分别表示对应各“动作”节点数量.如状态s1表示端盖螺栓,工具lj表示套筒扳手,行为fk表示使用行为,装配类型gh表示螺栓紧固,则在状态s1处,单次装配操作可描述为O=〈s1,lj∪fk∪gh〉.过程规划通常是对状态序列进行规划[9],但在虚拟场景中,评价虚拟人是否准确完成装配作业,是通过其是否选择正确的动作来判断的.因此,本文将状态序列规划转化为动作选择规划,即将状态积累回报转换成动作积累回报,改善虚拟维修环境中状态转移未知的问题.令sn为装配作业目标状态,装配作业过程规划步骤如下:

(1) 初始化状态集S和动作集A;

(2) 在每个离散时间点t,系统处于当前状态st,选择动作at,到达一个新状态st+1=δ(st,at),能够得到回报值rt=r(st,at);

(4) 设Q(si,ai)为计算机在状态si下选择动作ai获得的回报值,Q值函数定义如下:

Q(si,ai)=r(si,ai)+

(1)

maxQ(si+1,ai+1)=argmaxV(π)

(2)

为防止虚拟装配过程中重复选择动作导致回报值Q(s,a)无限增大,出现无法收敛到最优策略的情况,引入回报折算因子γ,0≤γ<1.若γ=0,则只考虑立即回报;若γ接近1,则增强后续回报的重要程度.式(1)和式(2)中,当前回报值与后续回报值直接相关,采用这种倒序的迭代算法,经过数次的动作选择,总能使作业策略收敛到一稳定值,即策略中每个动作a的积累回报值Q(s,a)都是最大的.然而,使用此算法存在风险[10-11],作业策略可能过度束缚在早期具有较高Q值的动作,而不能探索到其他有更高Q值的动作.因此,本文建立基因组模型,将遗传算法与Q学习算法相结合,共同对装配作业过程规划问题进行求解,保证装配过程信息的全面性和全局收敛效率.

2 面向虚拟装配作业过程的混合遗传算法

以差速器装配为例(见图1),将装配动作中包含的零件、行为、工具和装配类型等要素融合为一个维修元,一个维修元可表示为

C={B,L,F,G}

式中:B,L,F,G是维修元中4个基本要素,分别为部件、装配该部件所使用的维修工具、执行的装配行为和装配类型.维修元支持对维修要素的扩充,具有较好的通用性和可扩展性.为便于描述,将待装零件抽象为“状态”概念,将工具、行为、装配类

图1 差速器装配体三维分解图Fig.1 Decomposition of differential gear structure

型抽象为“动作”概念,对算法进行描述,具体步骤如下:

(1) 组建初始维修元,并通过维修元的排列组合构建初始装配作业序列,如图2所示.

图2 初始装配作业序列Fig.2 Assembly operation sequence

(2) 根据已知回报值r(s,ai),更新每一个动作ai的Q值,

(3)

令s←s′,直到s为目标状态,即装配完毕,得出初始Q值表.

(3) 采用实值编码的方式,将图2中的维修元xi作为基因值,构建遗传算法的初始化染色体X0=[x1x2…xn].

(4) 构造值函数Qi向适应度函数Fi的映射.

(6) 以概率Pc进行交叉操作,

X′←Crossover[X0]

(4)

(7) 分别以概率Pml和Pmf对维修元和维修序列进行变异操作,

X″←Mutation[X′]

(5)

(8) 终止原则.若连续几代Q值的差异小于某一较小的阈值或者到达指定的进化代数后,就停止运算.

3 装配作业过程规划求解步骤

3.1进化策略表示

为便于识别,避免频繁的译码解码,本文采用实值编码的方式对问题空间进行编码.1条染色体即对应了1个装配作业序列,使用几何约束方法和特征匹配方法作为约束条件,保证该作业序列为可行序列,可行序列表示方法如图3所示.

图3 可行序列表示方法Fig.3 Representaiton of feasible sequence

3.2适应度函数与选择操作

本文采用Q值函数作为遗传算法的适应度函数,之所以使用Q值函数而不是直接使用回报值r作为适应度函数,因为Q值是从全局角度衡量作业效率,而回报值r仅是对局部状态进行分析,适应度函数F(x)定义如下:

(7)

式中:Qt为第t次迭代时的Q值估计,t为进化代数,染色体复制方法采用轮盘赌选择法[12].

3.3交叉操作

装配可行性是交叉时需要考虑的重要问题,因此，交叉操作一要强调继承父代维修元的相对次序,二要强调继承父代维修元的绝对位置.本文在两点交叉的基础上,采用变长度的方式对交叉片段进行选取,既提高染色体的变化能力,又保证种群的多样性.具体步骤如下:

(1) 设待装配部件数目为6,产生一个随机数σ=2(σ∈[1,5]).

(2) 随机在父代选取交叉区域,交叉长度为2,父代种群如图4所示.

(3) 将交叉区域维修元插入到另一个体交叉区域维修元之前,交叉前与交叉后染色体变化如图5所示.

(4) 这样交叉后的染色体出现重复的维修元(见过渡个体),在非交叉区域依次删除与交叉区域维修元相同的维修元,得到子代种群,如图6所示.

图4 父代种群表达Fig.4 Discription of parent population

图5 交叉操作Fig.5 Crossover operatior

图6 删除操作Fig.6 Delete operator

上述交叉过程满足了基因重组的要求,并将父代部分序列遗传至子代,产生了适合进一步进化的子代个体.

3.4变异操作

对于由维修元构成的染色体,变异操作既要考虑装配序列的改变,也要考虑装配要素的改变,因此,本文对整体(装配序列)和个体(维修元)两部分进行变异操作,步骤如下:

(1) 装配序列变异.对于选定的染色体Xt=[x1x2…x6],采用逆转方法进行变异操作,即随机选取基因段中的两个点d1和d2作为逆转点,将两个逆转点的基因值对调得到新染色体,如图7所示.

图7 逆转变异算子示意Fig.7 Reverse mutation operator

(2) 维修元变异.逆转变异是在全局角度对作业序列进行改变,而对序列中包含多类要素的维修元,同样需要实施变异操作.针对维修元局部信息,本文采用选择变异算子对父代染色体进行操作,构建每个部件的匹配特征表.表中包含了每个零件在装配过程中的可用工具集、可用行为集和可用装配类型集,使用表中的元素对父代维修元中要素进行替换,达到要素变异的目的,变异方式如图8所示.

图8 选择变异算子示意Fig.8 Selection mutation operation

由图8可见,首先确定某一维修元(虚线部分)执行选择变异操作,如对零件b2执行变异操作,根据零件编号b2搜索特征匹配表中可用工具、行为和装配类型,并将原有要素进行替换,这样既保证了选定维修元中各要素能够随机的发生变化,又保证了维修元内部各要素的匹配合理性.

4 规划实例与结果分析

4.1规划实例

采用混合遗传算法对装配作业过程规划进行求解,并做出比较分析.以图1中差速器为例,构建差速器装配作业过程特征匹配表,如表1所示.

表1 差速器装配过程特征匹配表Tab.1 Task characteristic match Table for gear adjustment

注:“/*”表示匹配内容为空,可选工具为空即为徒手操作.

差速器虚拟装配作业过程中,状态转移过程即在初始状态下执行一系列“维修元”后(即执行一个策略π=(a1,a2,…,an),包括使用工具lj、选择操作行为fk、选择装配类型gh)到达目标状态的过程.装配目标为装配完毕,且目标函数值最大.

对混合遗传算法进行验证之前,设定折算回报因子γ=0.9,回报值r(s,a)根据式(1)进行求解.设定作业序列中维修元交叉概率Pc=0.8,变异概率Pm=0.02;维修元中工具要素变异概率Pml=0.02,行为要素变异概率Pmf=0.02,装配类型要素变异概率Pmf=0.02;回报函数中工具选择、行为选择、装配类型选择的权重均设定为1,即λ1=λ2=λ3=1;设定回报函数奖励因子α=2.迭代的每一步,均选取每组染色体中回报值r(s,a)较高的维修元所代表的动作,参与状态转移过程.设最大进化代数G=100,种群规模设定M=20.为保证初始种群中染色体均由可行序列组成,20个染色体均由操作者自主拆卸产生,使用4元数对维修元进行表达,即b1l1f1g1表达为(1 1 1 1);使用连续4元组对染色体进行表达,初始种群中,一个可行装配序列染色体表达如下:(7 0 2 1)(5 3 2 2)(4 2 2 2)(6 2 2 2)(3 1 2 2)(2 2 3 2)(9 3 4 2)(1 0 1 1)(10 0 1 1)(8 2 2 2)(11 5 4 1).其中对于维修元中的某一位,若无匹配内容,则使用0表示.该作业序列适应度函数为F(X)=532,nl=9,nf=5,ng=4.使用本文所述方法和Q学习算法分别对规划问题进行计算,得到进化结果,如图9所示.

算例中Q学习算法仅找到次优解,混合遗传算法无论在收敛速度和收敛性能方面都比Q学习算法优越,得到最优作业序列:(7 0 2 3)(4 2 2 2)(5 2 2 2)(3 2 2 2)(6 2 2 2)(8 2 2 2)(9 2 3 2)(2 2 3 2)(1 0 2 1)(10 0 2 1)(11 2 2 1).该序列中,适应度值F(X)=590,工具更换次数、行为更换次数、装配类型更换次数分别为nl=3,nf=2,ng=2.

图9 混合遗传算法与Q学习算法的性能比较Fig.9Performance comparison between hybrid geneticalgorithm and Q-learning algorithm

5 结语

混合遗传算法之所以能够快速收敛,源于它的逆向求解机制和回报机制,它总能在解序列的源头对规划问题进行分析,因此,相对较容易避免不可行序列的计算.多次验算发现,使用Q学习算法难以使规划结果快速收敛,主要局限在于:缺少特征匹配机制容易导致不可行装配序列持续增长,降低了算法的效率,可以预料,若装配体干涉情况复杂、特征匹配内容数目多,使用Q学习算法必须更多的迭代次数.这对实时性要求较高的虚拟维修环境来说是不实际的.仿真结果表明,即使在信息含量较大的情况下,混合遗传算法依然具有较高的全局收敛性,为多信息融合条件下的装配作业规划问题提供了一种实用的解决方法.

[1] LI J R,KHOO L P,TOR S B.Generation of possiblem multiple components disassembly sequence for maintenance using a disassembly constraint graph[J].International Journal of Production Economics,2006,102(1):51-65.

[2] 于海全,彭高亮,刘文剑.基于虚拟环境的维修性信息模型的建立[J].兵工学报,2010,31(7):998-1002.

YU H Q,PENG G L,LIU W J.Research on the maintainability information model based on VR[J].Acta Armamentarii,2010,31(7):998-1002.

[3] FREY G.Assembly line sequencing based on Petri-net T-invariants[J].Control Engineering Practice,2000,8(1):63-69.

[4] YEE S,VENTURA J A.A Petri net model to determine optimal assembly sequences with assembly operation constrains[J].Journal of Manufacturing System,1999,18(3):203-213.

[5] CHUNG C,PENG Q.An integrated approach to selective-disassembly sequence planning[J].Robotics and Computer-Integrated Manufacturing,2005,21(4/5):475-485.

[6] 高金莲,杨杰,李春书.基于遗传算法的装配作业优化[J].机械设计,2007,24(1):43-45.

GAO J L,YANG J,LI C S.Optimization of assembling operation based on genetic algorithm[J].Journal of Machine Design,2007,24(1):43-45.

[7] 杨鹏,刘继红,管强.面向装配序列优化的一种改进基因算法[J].计算机集成制造系统,2002,8(6):467-471.

YANG P,LIU J H,GUAN Q.An improved genetic algorithm for assembly sequence optimization[J].Computer Integrated Manufacturing Systems,2002,8(6):467-471.

[8] WATKINS C J,DAYAN P.Q-learning[J].Machine Learning,1992,8(3):279-292.

[9] MITCHELL T M.机器学习[M].北京:机械工业出版社,2003.

MITCHELL T M.Machine learning[M].Beijing:China Machine Press,2003.

[10] JONATHAN D,PARRIS K E,DAVID C.Enhancing computer graphics through machine learning:a survey[J].The Visual Computer,2007,23(1):24-43.

[11] GUO M Z,LIU Y,MALEC J.A new Q-learning algorithm based on the metropolis criterion[J].IEEE Trans on System,Man and Cybernetrics,2004,34(5):2140-2143.

[12] 陈有青,徐蔡星,钟文亮,等.一种改进选择算子的遗传算法[J].计算机工程与应用,2008,44(2):44-49.

CHEN Y Q,XU C X,ZHONG W L,et al.Genetic algorithm with improved selection operator[J].Computer Engineering and Applications,2008,44(2):44-49.

Hybridgeneticalgorithm-basedplanningmethodforvirutalassemblyoperation

JIAOYumin1,XUTing2,LIUBin2,YUGuangliang1

(1.94679 Troop,Nanjing 210038,China; 2.College of Field Engineering,PLA Army Engineering University,Nanjing 210007,China)

To aid in finding the optimal strategy,sequence constraint mechanism and characteristics matching mechanism are proposed,which are suitable for the condition of multi-information fusion.In order to make planning content be more abundant,the concept of maintenance unit is presented,which is suitable for information integration and evolutionary computation.Based on maintenance unit,the assembly sequence model is established.To solve this model,an assembly process planning method based on hybrid genetic algorithm is put forward.To aid in finding the optimal strategy,sequence constraint mechanism and characteristics matching mechanism are proposed,which are suitable for the condition of multi-information fusion.

hybrid genetic algorithm; virtual assembly operation; process planning; maintenance unit

TP 391.9

A

1672-5581(2017)04-0342-06