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

摘要：工业刀具被广泛用于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]时停止降温。