基于和声搜索算法的工艺序列规划方法研究*

夏然飞，褚学征，李新宇

(1.华中科技大学 机械科学与工程学院，武汉　430074; 2.中冶南方工程技术有限公司，武汉　430080)



基于和声搜索算法的工艺序列规划方法研究*

夏然飞1，褚学征2，李新宇1

(1.华中科技大学 机械科学与工程学院，武汉430074; 2.中冶南方工程技术有限公司，武汉430080)

针对加工中心上的工艺序列规划问题，提出了一种以加工时间最短为优化目标的和声搜索求解方法。通过分析加工零件的特征关系，根据加工中心具有自动换刀和工作台转位的功能，从而采用矩阵来储存每个工序对应的刀具编号和工作台转位特征。该算法只需通过改变矩阵数据，就能自动生成所需的工艺方案，并且只用更改零件所对应的约束矩阵，就能快速实现零件的工艺序列优化。实例分析表明，在该模型下的和声搜索算法能很好地求解工艺序列规划问题，优化结果满足约束条件且提高了生产效率。

和声搜索算法; 工艺规划; 特征关系

0　引言

工艺序列优化作为工艺规划中的一个重要的子问题，是根据生产要求对实际生产系统中每一个零件大量柔性的工艺路线进行优化与选择，是一个NP问题。使用新型智能算法求解NP难问题是近些年研究的热点。为了满足省时和省力的生产要求，在数控加工中心上加工箱体等复杂零件时，由于加工中心具有自动换刀和工作台转位的功能，而每次装夹下加工零件的工序数有数十到上百道，工序数越多排序规模就越大。因此，实际生产中工艺路线的拟定是否合理直接影响到零件的加工质量、生产效率和经济性。

近些年来，基于遗传算法(GA)、粒子群优化算法(PSO) 、模拟退火算法(SA)、蚁群算法(ACO)等人工智能技术的工艺路线排序与优化方法成为国内外学者的研究热点。范顺成[1]等采用了基于十进制数的基因编码规则，利用遗传算法解决工艺路线规划问题。但是，该算法收敛较慢，运行时间长，局部搜索能力较弱。GA算法是单点或双点交叉，只有从两个现有的向量作为新的向量。而且，在生成一个新的向量时，遗传算法为了保持遗传结构不能考虑到这个向量中的每一个组成向量，导致对新空间的探索能力有限，也容易收敛到局部最优解。Guo[2]利用PSO算法来对零件的工艺规划建立了数学模型，通过类似于GA的迭代进化机制实现对最优解的空间搜索，但该算法同样容易陷入局部最优。

由于SA算法具有较强的局部搜索能力以及跳出局部极小点“陷阱”的能力，黄伟军[3]采用GA-SA混合算法，以期待获得较好的工艺路线。但是SA算法本身的全局搜索能力差，容易受参数的影响，而且该混合算法比较复杂，计算规模较大。

田颖[4]等人运用蚁群算法进行工艺路线优化，但构造加工顺序对优化目标进行约束时没有建立数学模型，只是单纯地进行知识推理。而且在算法的初始阶段，需要根据零件特征数目手动确定蚂蚁的个数，刀具信息也没有考虑在内。

针对前面的研究，本文设计了一种新的求解方法，基于改进的和声搜索算法求解工艺序列优化问题。根据加工零件的特征关系，提出了用矩阵来储存每个工序对应的刀具编号和工作台转位特征。以加工时间最短为优化目标，采用相应的约束矩阵来体现加工操作之间的优先关系，使用和声搜索算法对零件的工艺序列进行优化排序。

该算法与其他启发式算法相比，它保留了类似禁忌算法的初始向量元素(和声记忆库)的来历，并能够从一开始到结束就以类似于模拟退火算法改变适应率(和声记忆库保留概率)，并且以类似遗传算法的方式能够同步的处理多个向量元素。和声记忆库的解进行多点交叉，可以更好地保留了和声库的最优解，并且能从所有现有的向量(和声记忆库中的所有向量)中生成新的向量。

另外，该算法可使搜索逃离局部最优，保证得出的解是最优解，而且其计算效率较高，从而达到对零件工艺路线的快速选择与优化，并通过实例验证了本方法的可行性和有效性。

1　工艺序列优化问题描述

零件的加工路线决策是计算机辅助工艺规划中最重要的任务之一，同时也是一项多任务决策过程。零件的加工特征种类繁多，但彼此之间却有一定的联系，分类也有规律可循。以箱体类零件为例，可以抽取出以下几大类基本加工特征，其余特征皆可由此组合而成[5]。

(1)平面特征：普遍存在于各类零件中，一般平面、斜面、边框面等均可归类为平面特征，该类型特征对应的加工方法有车、铣、刨、磨等。

(2)槽类特征：主要包括通槽、盲槽、燕尾键槽等。槽的种类较多，形状各异，加工方法一般有磨削、铣削和刨削。

(3)型腔特征：主要包括空腔和封闭的凹陷/凹槽等，一般情况下使用铣削的方式加工。

(4)孔类特征：孔类特征众多，包括圆柱孔、锥孔、螺纹孔、沉孔等。圆柱孔的加工方法一般有钻、扩、铰、镗、磨等。

2　目标函数和约束条件

2.1目标函数的建立

优化目标是找一个最优的工序x′，在满足工艺规划的约束条件下，使得换刀时间和工作台转位时间之和最短。因此，目标函数f(x)由两部分组成：

f(x)=f1(x)+f2(x)

(1)

式中：f1(x)为工序x中所需的换刀时间总和，f2(x)为工序x中所需的工作台转位时间总和。

由于加工中心下一工序要用的刀具总是要提前转到换刀位置，所以每次换刀的时间基本相同，设换刀时间为t1，则f1(x)可以表示为：

(2)

(3)

式中：如果工序oi和oi+1使用不同刀具，则g(oi-oi+1)=1；反之，则g(oi-oi+1)=0。

假设从工序oi到工序oi+1所需的工作台转位时间为t2，则工作台转位时间可以表示为：

(4)

(5)

式中：如果工序oi到工序oi+1工作台需要转位，则h(oi-oi+1)=1；反之，则h(oi-oi+1)=0。

函数f1(x)的值越小，说明刀具越集中；函数f2(x)的值越小，说明方位越集中。因此，该工序优化后的数学模型为：

f(x′)=min{f(x)}

(6)

在计算机程序中，采用0-1矩阵存储刀具信息和工作台转位信息，从而实现工艺序列优化问题中目标函数的自动选择。

2.2约束条件的建立

在加工中心上加工零件时，工艺序列的设计必须遵循加工顺序的约束，即“先粗后精”、“先主后次”、“先基准后其他”、“先面后孔”等原则。

工艺序列结果主要需要达到以下优化目标：

(1)为了减少换刀时间，加工时相同刀具的工序应尽量集中安排在一起。

(2)为了减少工作台的转位时间，尽量将同一方位上的表面加工集中在一起，其中方位为零件在X、Y、Z轴正负向共6个方向。

建立加工工艺的约束条件后，待加工零件在工艺路线中的先后关系可以用一个有向图来表示，这个数目最多可以有n(n-1)个。有向图的每个顶点表示零件的每个加工工序，每一对顶点所对应的有向边来表示顶点之间的优先关系。

图1一对顶点所对应的有向边

3　基于HS算法的工艺序列优化

3.1基本的HS概述

和声搜索(Harmony Search，HS)算法[7-8]由韩国学者Geem ZW等人提出，是一种新型的现代启发式智能优化算法，通过模拟音乐演奏的原理，从而产生一种美妙的声音组合。该算法原理简单、可控参数少、易于实现、具有很强的全局搜索能力[9]。

目前，研究学者对HS算法的改进主要集中在两个方面：一是将和声算法与其他成熟的算法进行融合[10]；二是调节算法的某些参数[11-13]，从而改进算法的搜索机制和性能。本文提出的一种改进的和声搜索算法，改善了算法的局部搜索能力，同时将改进后的算法较好地应用到工艺规划问题中。

3.2算法的主要参数

本文将乐器i类比于优化问题中的第i个变量，各乐器的音调相当于各变量的值，各乐器音调的和声相当于优化问题的第j组解向量，最终的音乐效果类比于目标函数f(xj)。

在本文建立的工艺序列优化模型中，基于和声搜索算法对应的基本参数有[14]：

①工序(变量)个数n；

②各个工序的范围(变量的取值范围)；

③和声记忆库保留概率HMCR，即新解从和声记忆库中保留原来解分量的概率；

④记忆库扰动概率PAR，即每次对部分解分量进行微调扰动的概率；

⑤和声记忆库HM可保存的和声个数HMS(工序数)，HMS应远小于所有可行解数目；

⑥最大迭代次数Tmax，即运算的终止条件。

3.3初始化和声记忆库

由于和声搜索算法主要是基于邻域搜索的，初始解的好坏对搜索的性能影响很大。尤其是一些带有很复杂约束的优化问题，随机给出的初始解很可能是不行的，甚至通过多步搜索也很难找到可行解，这个时候应该针对特定的复杂约束采用启发式方法或其它方法找出一个可行解作为初始解[15]。

随机生成HMS个和声x1,x2,…,xHMS放入和声记忆库中，这里和声记忆库可以类比于遗传算法中的种群。和声记忆库形式如下：

(7)

3.4更新和声记忆库

①保留HM中原有的工艺序列；

②随机产生新的工艺序列；

③对前两种情况的工艺序列进行随机扰动。

对现有的工序加一个随机扰动，包括两种类型:

类型1：将该解的任意两个工序调换位置；

类型2：将该解的某一个工序插到任意的位置。

图2表示在(n=12)情况下的工艺序列扰动图，计算机程序随机选择两种扰动类型的概率为50%。

图2　两种随机扰动类型

由于在最优化过程中并不完全排斥陷入局部最优，因此把两种随机扰动类型引入启发式优化方法中。这样，即使在搜索中落入局部最优点，也能够容易地挣脱出来，这正是该算法的优越性所在。

3.5生成新的工艺序列

根据和声搜索的原理，在Matlab中随机产生0～1的随机数rand，如果rand

这里根据工艺序列的两种随机扰动类型，对HM进行扰动，来防止产生局部最优。若随机数rand<0.5，则采用第一种扰动类型，即调换任意两个工序的位置；反之，则采用第二种扰动类型。如果随机数rand>PAR，则不进行扰动。

最后，判断新解目标函数值是否优于HM内的最差解，若是则更新和声库，并不断迭代，直至达到预定迭代次数为止。对新解的评估如下：

(8)

综上所述，本文设计的算法具体操作流程如图3所示。

图3　改进的HS流程图

4　实例分析

4.1零件的特征关系

在研究工艺序列优化问题时，减少零件的加工时间，对于提高加工中心的生产效率，具有十分重要的意义。图4为调研某企业的零件示意图，该零件有7个加工特征，包括轮廓、面、槽和圆孔，经过加工方法确定和加工方法链分解，共产生14个工艺序列。其中，所用的刀具共有6种，如表1所示。

图4　零件简图及加工特征

刀具标号类型和规格刀具标号类型和规格T1端铣刀ϕ60T4立铣刀ϕ15T2立铣刀ϕ25T5钻头ϕ16T3立铣刀ϕ20T6扩孔钻ϕ16.7

使用的装夹有正面装夹卡具(K1)，反面装夹卡具(K2)，外轮廓铣削卡具(K3)。工艺序列依次为o1～o14，零件加工特征和对应的工序如表2所示。

表2　零件加工操作列表

对于待加工零件特征对应的工序集合，采用n×n的矩阵来储存每个工序对应的刀具编号和工作台转位特征，两个矩阵都是对称的，且对角线元素均为0。取每次换刀时间t1=6s，两个工序之间工作台转位时间t2=2.5s。例如，T13=1说明工序o1和o3需要换刀，而K12=0说明工作台不需要转位。

换刀矩阵为：

(9)

工作台转位矩阵为：

(10)

4.2约束矩阵的建立

表3　优先关系约束表

(11)

按照上述条件，很容易得到图4中工序优先关系图的约束矩阵。由式(11)知，如果工序oi必须在工序oj之前完成，则rij=1；否则，rij=0。约束矩阵是非对称的，并且对角线元素均为0，如下所示：

(12)

4.3参数设置与模型求解

算法参数的设置对工艺系统的优化能力起到关键性作用。HMS决定了算法的全局搜索能力，影响着算法的执行能力和优化效率。因此，采样合适的和声库大小有利于提高算法的收敛速度和解的质量。HMCR的取值区间在0～1之间，它决定了每次迭代过程中新解的产生方式。在和声搜索算法中，因新解产生时每个变量都依赖于HMCR，故HMCR应取较大的值。而扰动概率PAR在和声搜索中起局部搜索的作用，若PAR太大，种群中的解以较大概率进行扰动，容易使较好的解被破坏掉；若PAR太小，种群中的解以很小的概率参与扰动，就会使搜索停滞不前，搜索速度减慢，和声记忆库就失去了多样性。通常取和声记忆库大小HMS=10，和声保留概率HMCR=0.9，扰动概率PAR=0.3。

表4　工艺序列表

其中，换刀次数n1=6，工作台转位次数n2=4，则加工时间为f(x)=t1n1+t2n2=6×6+2.5×4=46s。经验证，该序列满足各项约束关系，即先粗后精、先面后孔、先基准后其他，而且能很快地得到较优的排序结果，较大程度地实现方位集中和刀具集中。

4.4计算结果分析

通过和声搜索算法对数控加工中心的工艺序列进行优化，可以得到工序的近优解。由于在得到近优解的同时，还可以得到多个经过运算后的工序方案，工艺人员可以从中选择出合适的工艺序列。而且，该算法搜索效率高，计算时间短。

为了更直观形象的观察，图5表示经过多次迭代运算后目标函数值的变化趋势。可以看出迭代1000次后目标函数的取值逐渐趋于稳定，且加工时间在45s左右波动，验证了实验结果的有效性。

图5　迭代次数

而在传统的加工方法下，该零件的加工方案至少需要换刀7次，优化后相对减少了一次换刀时间，节约了6s的机加工辅助时间，从而提高了加工效率。在优化结果和计算时间方面都优于常规方法，有效地提高了工艺规划系统的优化能力。

5　结束语

(1)本文设计的算法与现有的和声搜索算法相比，原理简单，容易实现，只需通过改变换刀矩阵和工作台转位矩阵数据，就能自动生成所需的工艺方案。

(2)在解决大规模问题时，尤其是较复杂零件的加工，其计算效率也相对较高。另外，该算法比较通用，可以根据不同的工艺排序问题进行优化和方案选择。

(3)实例验证说明本方法可以得到满足制造条件约束的最优工艺序列。同时这对于提高加工中心的生产效率，具有比较重要的意义。

[1] 范顺成,王进峰,李世杰.基于遗传算法的工艺路线决策与优化[J].制造技术与机床,2012(3):95-99.

[2] Guo Y W, Mileham A R, et al. Operation sequencing optimization for five-axis prismatic parts using a particle swarm optimization approach. Proc. IMechE. Part B: J. Engineering Manufacture, 2009, 223: 485-497.

[3] 黄伟军.复杂零件工艺方案优化关键技术研究[D].武汉:华中科技大学,2012.

[4] 田颖,江平宇,周光辉,等.基于蚁群算法的零件多工艺路线决策方法研究[J].计算机集成制造系统,2006,12(6):882-887.

[5] 杨瑞生,卢继平,樊红丽,等.基于遗传算法的发动机箱体工艺路线优化[J].新技术新工艺,2013(11):104-106.

[6] 范孝良,王进峰,吴学华,等.一种基于遗传算法的工艺规划方法[J].中国管理科学,2014,22(11):51-54.

[7] Geem Z W．State-of-the-art in the structure of harmony Search algorithm [J]. Studies in Computational Intelligence,2010,270(5):1-10．

[8] Das S, et al. Exploratory power of the harmony search algorithm: analysis and improvements for global numerical optimization [J]. IEEE Transactions on systems, Man, and Cybernetics-Part B: Cybernetics, 2011,41 (1):89-106.

[9] 沈绍辉,姚竹亭.和声搜索算法优化支持向量机的柴油机故障诊断研究[J].组合机床与自动化加工技术,2015(9):66-70.

[10] 赵鸿飞,张琦,朱春生,等. 基于改进自适应和声遗传算法的装配序列优化研究[J].计算机应用研究,2013,30(8):2357-2359．

[11] 陈虹,王飞.基于IHS_LSSV的网络安全态势预测方法[J].计算机工程与应用,2014,50(23):91-94．

[12] 杨树欣,李盼池.和声搜索算法的改进研究[J].计算机技术与发展, 2015, 25(4): 93-97.

[13] CHEN J, PAN Q K, LI J Q. Harmony search algorithm with dynamic control parameters [J].Applied Mathematics and Computation,2012,219(2):592-604.

[14] 潘玉霞,谢圣献.和声搜索算法参数研究[J].软件导刊, 2013,12(6):40-42.

[15] 欧阳海滨,高立群,邹德旋,等.和声搜索算法探索能力研究及其修正[J].控制理论与应用, 2014, 31(1): 67-65.

(编辑李秀敏)

Optimization of Process Sequence Based on Harmony Search Algorithm

XIA Ran-fei1, CHU Xue-zheng2, LI Xin-yu1

(1.School of Mechanical Science & Engineering, Huazhong University of Science & Technology, Wuhan 430074, China; 2.WISDRI Engineering& Research Incorporation Limited, Wuhan 430080, China)

To solve the optimal process planning problem on a machining center, an optimal process planning method based on harmony search algorithm and taken minimal processing times as optimization objective is proposed. Because the machining center with automatic tool change and workbench transposition function, according to the characteristics of the relationship between processing components, using the matrix to store the number of tools and workbench transposition characteristics. The algorithm is simple and easy to implement. It can automatically generate the required process by changing the matrix data. With the constraint of this matrix, an optimized process sequence was obtained quickly. An example is given to demonstrate the efficiency of this algorithm for process planning, the results satisfy the constraint and improve the production efficiency.

harmony search algorithm; process planning; feature relationship

1001-2265(2016)09-0138-05DOI:10.13462/j.cnki.mmtamt.2016.09.040

2015-11-14；

2015-12-12

国家自然科学基金(51375004)；国家科技支撑计划(2015BAF01B04)

夏然飞(1990—)，男，武汉人，华中科技大学硕士研究生，研究方向为工艺规划；通讯作者：李新宇(1985—)，男，湖北仙桃人，华中科技大学副教授，博士，研究方向为数字化制造的研究，(E-mail)lixinyu@hust.edu.cn。

TH162;TG506

A