基于改进混合遗传算法的工业刀具组合优化算法

郑子仪

摘要：工业刀具被广泛用于CNC制造加工中，但在实际生产过程中存在由于刀具组合不当而导致刀具闲置、利用率不高的问题。为了提升刀具利用率，降低刀具成本，文章提出一种基于改进混合遗传算法的工业刀具组合优化算法，对生产线刀具组合进行优化。实验结果表明，该算法在数据集上表现良好，并且较其他算法性能有所提升。

关键词：遗传算法；模拟退火算法；工业刀具；组合优化问题；工业软件

中图分类号：TP301.6；TP18     文献标识码：A

文章编号：1009-3044（2023）31-0128-04

开放科学（资源服务）标识码（OSID）

0 引言

组合优化问题是一类在离散状态下求极值的最优化问题[1]，本文所述刀具组合优化问题属于其中一类。学术界常用启发式算法解决组合优化问题，如禁忌搜索算法、粒子群算法等。在本文讨论的问题中，某家发动机制造厂拥有多个生产车间，可以同时进行不同工件的生产。本文提出一种基于改进混合遗传算法（Improved Hybrid Genetic Algorithm，IHGA） 的工业刀具组合优化算法，在多生产工单的生产需求的背景下，对每个生产工单使用的刀具组合进行优化，降低刀具的闲置浪费，提升刀具利用率，使得整体上达到最大的经济效益。

1 基于改进混合遗传算法的工业刀具組合优化

1.1 刀具组合问题参数定义

本小节对其中的相关参数和变量的定义与解释如下：

[N]：生产工单总数；

[i]：生产工单的编号（[i=1，2…N]）；

[ni]：表示[i]号生产工单需要生产的工件总数；

[qi]：表示[i]号生产工单中单个工件的报价；

[K]：刀具的种类总数；

[B]：刀具的数量总数；

[j]：刀具的编号（[j=1，2…B]）；

[pj]：表示[j]号刀具的采购价格；

[kj]：表示[j]号刀具的所属种类[（kj=1，2…K）]；

[aj]：表示[j]号刀具的初始寿命（单位：[%]） ；

[mj]：表示[j]号刀具的可修磨次数，若是不可修磨刀具，则[mj=0]；

[tj]：表示[j]号刀具进行单次修磨恢复的寿命，若是不可修磨刀具，则[tj=0]；

[cj]：表示[j]号刀具进行单次修磨的费用，若是不可修磨刀具，则[cj=0]；

[dik]：表示生产一个[i]号生产工单的工件所需[k]类刀具的寿命（%）；

[gij]：0、1变量，刀具组合优化的决策变量，当 [gij]为1时，表示[j]号刀具被用于[i]号生产工单的生产活动；当 [gij]为0时，表示[j]号刀具未被用于[i]号生产工单的生产活动。

1.2 编码设计

编码是遗传算法（Genetic Algorithm，GA） 的重要组成部分，编码实现了组合优化问题解空间到算法搜索空间的转换。IHGA采用二进制编码，一个染色体G代表一种刀具组合方案。每条染色体G包含N段，代表N个生产工单，每段包含B个基因，代表B把刀具。每个基因使用0、1编码，代表该生产工单是否使用该刀具进行生产， 1代表使用，0代表不使用。实例如图1所示，该实例中有3个工单，10把刀具，其中1号生产工单使用1号、4号刀具进行生产，2号生产工单使用2号、9号和10号刀具进行生产，3号生产工单使用3号和8号刀具进行生产。

1.3 目标函数、适应度函数及约束条件

目标函数[AG]是优化的目标，而适应度函数值[FG]是描述种群个体表现优劣的指标，GA的本质就是通过适应度函数值的大小来对种群个体实现“自然选择、优胜劣汰”。适应度函数直接决定搜索群体的进化行为，适应度函数值越大，个体的表现就越好，其基因遗传给下一代的可能性就越大。IHGA的目标函数[AG]如式（1） 所示，其中各个参数的计算如式（2） 和式（3） 所示。

[AG=i=1Nxi×qi-j=1Bpj+mj×cj×zj]  （1）

[xi=mink=1…Kj=1Kgij×aj+mj×tj×fdik]  （2）

[f=1，若cj=k0，若cj≠k ，zj=1，若cj=i=1Ngij>00，若cj=i=1Ngij=0]  （3）

由于目标函数可能出现负数情况，不能直接将目标函数作为适应度函数，需要做目标函数到适应度函数的变换，该过程称为标定。常见的标定方法有线性标定、幂律标定、窗口技术等。IGHA进行的标定如式（4） 所示。

[FG=AG，    若G满足约束条件0，            若G不满足约束条件]    （4）

目标函数主要为每个生产工单任务实际生产工件数与单个工件报价的乘积减去消耗的刀具成本。约束条件如式（5） 所示，对于任意一把刀具，其仅能被一个生产工单的生产活动占用。

[i=1Ngij≤1，∀j]      （5）

1.4 选择算子选择

选择操作是按照预定的选择算子，随机从父代中挑选一些适应度函数值大、表现良好的个体生存下来，其余的个体则被淘汰的过程。常见的选择算子有轮盘赌选择算子（Roulette Wheel Selection，RWS） 、排序选择算子等[2]。IHGA使用RWS，其基本原理如式（6） 所示。其中[R（Gi）]表示[Gi]被选择进下一代的概率，[M]为种群规模。在具体算法实现时，可以随机生成一个范围在0至1之间的随机数[r]，若[0≤r≤R（Gi）]，则[Gi]被选择进下一代；若[R（Gi）<r<1]，则[Gi]被淘汰。

[R（Gi）=A（Gi）i=1MA（Gi）]    （6）

1.5 交叉算子设计

交叉操作是在交叉概率[Pc]下，将选择的两条父代染色体按照预设的交叉算子进行重组，从而获得不同于父代的子代染色体。交叉操作是GA中获得新染色体的重要操作，不同的交叉算子对于算法性能和效率的影响也不同，常见的交叉算子有两点交叉算子（Two-point Crossover Operator， TCO） 、有序交叉算子等[3]。IHGA对TCO进行改进，提出一种整体重组两点交叉算子（Whole Recombination Two-point Crossover Operator，WRTCO） ，并将WRTCO和TCO相结合，应用于IGHA中。

TCO是在两条父代染色体中，以交叉概率[Pc]选择两个固定的交叉点，交换交叉点之间的基因，从而产生两条新的子代染色体。常规两点交叉操作如图2所示，随机生成的交叉点[d1=4，d2=12]，父代染色体A和B交换4号到12号之间的基因，形成子代染色体C和D。

在TCO中，交叉点[d1与交叉点d2]都是随机生成的，而WRTCO对交叉点[d1与交叉点d2]的生成进行了限定，限定条件如式（7） 所示，交叉点[d1]限定在某个生产工单编码的开头，交叉点[d2]限定在该生产工单编码的结尾，从而达到整个生产工单整体编码交叉重组的效果。实例如图3所示，此时交叉点[d1=1]，交叉点[d2=B]，1号基因到B号基因实现整体交叉重组，其代表的实际意义为1号生产工单的两个编码方案实现交换重组，从而获得子代染色体。

[d1=n×B+1，d2=d1+B-1，其中n=0，1...n-1]  （7）

综上所述，IHGA使用的交叉算子设计方案如下：首先进行常规双点交叉操作，以交叉概率[Pc]随机生成交叉点[d1]与交叉点[d2]，交换交叉点[d1]与交叉点[d2]之间的基因从而获得子代染色体。若常规双点交叉操作未发生，则进行整体重组双点交叉操作，以同样的交叉概率[Pc]和限定条件（7） 生成交叉点[d1]与交叉点[d2]，交换交叉点[d1]与交叉点[d2]之间基因的获得子代染色体。同时为了保证染色体的合法性，对于每次交叉产生的子代染色体都要进行合法性检查。

1.6 变异算子设计

變异操作是模拟生物基因突变产生新特征的过程。在GA中，变异算子作用于选择和交叉操作后产生的子代染色体，以交叉概率[Pm]使得染色体的某些基因发生变异，从而获得新染色体。变异操作增强了种群个体的多样性，但由于变异操作带有损害种群个体表现的风险以及高变异率会使得GA向随机搜索算法靠近，[Pm]一般设得较低，过低的[Pm]又会影响种群多样性。常见的变异算子有位翻转变异算子（Bit Flipping Mutation Operator，BFMO）） 、交换变异算子、反转变异算子等。

BFMO是在固定变异概率[Pm]下，对染色体中一个或多个基因进行0、1翻转变异。IGHA基于实际问题背景，基于提升种群个体多样性及算法效率的考虑，提出一种改进位翻转变异算子（Improved Bit Flipping Mutation Operator，IBFMO） 。IBFMO的变异操作如下：在变异概率[Pm]下，首先在每个生产工单基因段随机选择一个基因进行变异，若在不同的生产工单基因段选择了同一基因位，则重新进行选择。若选择的基因是0，则将其翻转为1，且其他生产工单基因段对应位都设置为0；若选择的基因是1，则将其翻转为0，在其他生产工单基因段中任选一段，将其对应基因设置为1。同时，IGHA采取动态变异概率[Pm]，初始变异概率为[Pb]，若某次迭代都发生变异，则将变异概率[Pm]增加0.01，最终变异概率[Pl]但不超过阈值[PM]。示例如图4所示。1号、2号和3号生产工单基因段分别选择了1号基因位、5号基因和8号基因进行翻转操作。1号生产工单基因段将1号基因从1翻转成0，并选择将2号生产工单基因段1号基因从0翻转成1；2号生产工单基因段将5号基因从0翻转成1，并选择将3号生产工单基因段5号基因从1翻转成0；3号生产工单基因段将8号基因从1翻转成0，并选择将1号生产工单基因段8号基因从0翻转成1。

1.7 退火过程与终止条件判定

GA具有良好的全局搜索能力和较快的运算速度，但在搜索过程中有概率陷入局部收敛。IGHA将模拟退火算法（Simulated Annealing Algorithm，SAA）与GA结合，通过SAA的Metropolis准则使得算法可以以一定的概率[Ps]接受较差解[4]，使得算法结果跳出局部最优解。概率[Ps]的计算公式如式（8） 所示，在某次迭代过程中，[G]是种群在经过选择、交叉、变异操作前的最优个体，[G']种群在经过选择、交叉、变异操作后的最优个体。基于Metropolis准则判断，若[G']在适应度函数上的表现优于[G]，则接受[G']为当前种群最优解；若[G']在适应度函数上的表现劣于[G]，则以[e- FG-FG'T]的概率接受[G']为当前种群最优解。在温度[T]值较大时，Metropolis准则判断能以一个较大的概率接受较差解当作当前种群最优解，能够有效地跳出局部最优点。同时，为了避免优良解在算法迭代过程中的丢失，设置具备记忆功能的最优个体[G*]，每一次迭代都会对[G*]进行更新，从而尽可能地保留最优个体。

[Ps=1，FG'>FGe- FG-FG'T，FG'≤FG]   （8）

基于Metropolis准则判断过后是降温过程。初始温度为[T0]，终止温度为[Tf]，降温系数为[r]。IHGA算法使用指数式降温方法[5]，当前温度[T]为[T0]，一轮降温后，当前温度[T]的变化如式（9） 所示，直至[T]小于终止温度[Tf]时停止降温。

[T=T×r]          （9）

在一般的搜索问题中，常见的迭代终止条件有多种，例如设置最大迭代时间，即给算法设置一个运行时间阈值，当算法運行时间到达阈值运行时间时，即便此时算法迭代仍然未结束，强行终止算法的运行并输出此时的最优个体作为输出结果；设置优化目标阈值，根据对问题的具体分析，预先设置一个优化目标阈值，当某个个体达到该目标时停止算法运行并输出结果；设置迭代次数阈值，当算法迭代次数达到该阈值时，停止实验并输出结果。IHGA在终止温度条件基础上，使用双阈值终止条件，设置最优解不变次数阈值[M1]和迭代次数阈值[M2]。当连续超过[M1]次迭代最优解都不变时，停止迭代并输出最优个体[G*]和最优目标函数值[A*]，避免多余的运算；或者当迭代次数达到阈值[M2]时停止实验，避免过长的实验时间。

1.8 算法完整流程

IHAG算法完整步骤如Alg.1所示。

[Algorithm 1： Improved Hybrid Genetic Algorithm （IHGA） Input： Number of workorder N， matrix of workpiece demand quantity by each workorder NI

， matrix of workpiece quotation by each workorder Q， number of tool kinds K， number of tools B， matrix of purchase price of each tool P， matrix of kind number of each tool KT ， matrix of initial life of each tool AJ， matrix of grinding time of each tool MJ， matrix of life recover per grinding of each tool TJ， matrix of tool demand per workorder D， population size S， matrix of population Gs， crossover probability Pc， mutation probability Pm， mutation probability threshold PM， mutation probability increase limit value W， initial temperature T0， final temperature Tf， cooling rate r， optimal individual  invariant degree threshold M1， iteration threshold M2 Output： Optimal individual G*， optimal objective function value A* 1： Initialize Gs ←Generate H individual G randomly with validity checking

For every G in Gs do

A（G） ， F（G）←Calculate objective function and fitness function end 2： Gs ←Select individual G with RWS for S times and update Gs 3： Gs ←At a probability of PC ， update Gs with WRTCO ，TCO and validity checking 4： Gs ←At a probability of Pm ， update Gs with IBFMO

If continuous iterations without mutation reach W and Pm[ <] PM

Then Pm←Pm + 0.01  Endif 5： G’←Sort and get the best Individual from Gs

If A（G）< A（G’）

Then G←G’

Else judge by Metropolis rule

Endif

If A（G*）< A（G）

Then G*←G’，A* ←A（G’）

Else judge by Metropolis rule

Endif 6： Iteration end judgment by M1 and M2

If not reach end condition

Then goto step2

Endif 7： Output G*，A* ]

算法输入为算法所需的一系列参数和数据，输出为最优个体与最优目标函数值，每个步骤具体描述如下：

步骤1：随机初始化种群，对每个个体进行合法性检查以确保每个个体合法，计算每个个体的目标函数值和适应度函数值。

步骤2：基于RWS选择算子进行选择操作，更新种群。

步骤3：基于WRTCO，TCO交叉算子进行交叉操作，更新种群。

步骤4：基于IBFMO变异算子进行变异操作，更新种群，同时基于动态变异概率更新规则更新变异概率。

步骤5：找出新种群的最优个体与原最优个体相比，若是新种群最优个体好于原最优个体，则更新最优个体和最优目标函数值，否则基于Metropolis准则进行判断，同时记录全局最优解和全局目标函数值。

步骤6：通过终止温度条件和双阈值结束条件进行结束判断，若未满足结束条件，则回到步骤2继续执行。

步骤7：输出最优个体和最优目标函数值。

2 实验与结果分析

2.1 数据集准备

本实验的数据来源于某工厂的历史生产数据，为保证实验的有效性，本文删除了部分时间久远的数据和因其他因素导致的异常数据，形成8组数据。以1号数据组为例，如表1所示，1号数据组中总共包括了6个生产工单的相关信息，每行数据记录了一个生产工单要求生产的工件数目、生产每个工件的消耗刀具寿命情况以及每个工件的报价。以2号生产工单为例，该生产工单要求生产1500个工件，生产每一个该种工件需要消耗0.25%寿命的Ⅱ类刀具，0.5%寿命的Ⅲ类刀具以及0.5%寿命的Ⅳ类刀具，且每个工件的报价是0.35元（其中覆盖了原料、人力等方面的成本）。

1号组數据中部分刀具信息如表2所示，每行数据记录了一把刀具的基本信息。以1号刀具为例，该刀具属于Ⅰ类刀具，每把该类刀具的采购价是15.5元，初始寿命为100%，且该刀具属于不可修磨刀具。

2.2 参数设置

依据相关文献研究和问题实际情况对算法参数进行设置，种群规模[M]设定为500，交叉概率[Pc]=0.95，初始变异概率[Pb]=0.05，变异概率增量[∆P]=0.01，变异概率阈值[PM]=0.1。在SAA相关参数设置中，初始温度[T0]=1000，降温系数[r]=0.99，终止温度[Tf]=0.1。在中止条件判断条件设置中，最优解不变次数阈值[M1]=200，迭代次数阈值[M2]=1000。

2.3 算法有效性验证

为了验证IHGA算法的有效性，本小节设置算法有效性实验。本研究使用上述8个数据组进行，每个数据组分别使用随机组合法、传统遗传算法和IHGA进行10次独立重复实验，记录8次实验的平均目标函数值、最优目标函数值和最差目标函数值，形成的结果如表3所示。在同一个实验组内部，相比于随机组合算法，传统遗传算法和IHGA在三个平均目标函数值、最优目标函数值、最差目标函数值三个指标上都有一定的提升，且IHGA的提升效果最大。

以后实验组的平均目标函数值为指标，建立的分组柱状图如图5所示。从中可以看到，在每个数据组中，随机组合算法、传统遗传算法和IHGA在平均目标函数值上的表现呈一个递增的状态，IHGA表现良好。同时通过观察可以发现，相比于刀具数目和种类较少的3、4数据组，IHGA在刀具数目和种类更充裕的6、8数据组提升更明显，这是由于在算法进行时的种群多样性更强，更容易出现优良的个体，提升目标函数值。

3 总结与展望

基于工业刀具组合优化问题，文章将遗传算法和模拟退火算法进行结合，对其中的交叉算子、变异算子、变异概率和结束条件进行优化，提出了一种改进混合遗传算法。提升了传统遗传算法的性能，降低了局部收敛的概率。实验结果表明，该算法具有良好的可行性。

未来预计将其他改进方法应用于本算法，进一步提升算法的性能，并在工业生产中继续应用与检验。

参考文献：

[1] PERES F，CASTELLI M.Combinatorial optimization problems and metaheuristics：Review， challenges， design， and development[J].Applied Sciences，2021，11（14）： 6449.

[2] 葛继科，邱玉辉，吴春明，等.遗传算法研究综述[J].计算机应用研究，2008，25（10）：2911-2916.

[3] 李书全，孙雪，孙德辉，等.遗传算法中的交叉算子的述评[J].计算机工程与应用，2012，48（1）：36-39.

[4] VENKATESWARAN C，RAMACHANDRAN M，KURINJIMALAR R，et al.Application of simulated annealing in various field[J].Materials and Its Characterization，2022，1（1）：1-8.

[5] 陈华根，吴健生，王家林，等.模拟退火算法机理研究[J].同济大学学报（自然科学版），2004，32（6）：802-805.

【通联编辑：梁书】