基于果蝇优化算法的柔性工艺规划问题研究

李强LI Qiang

（沈阳大学机械工程学院，沈阳110041）

0 引言

工艺规划作为制造系统中的重要环节，是一个系统性的决策过程。由于传统的制造系统向着智能制造系统的转变，柔性工艺规划已经成为了工艺规划研究的重要内容。在智能制造系统中，带有多种柔性的工艺规划研究可以大大的提高车间的柔性，并且为车间提供更加灵活多样的加工方案，在企业的加工生产中起着非常重要的作用。

随着计算机技术的发展，智能优化算法也进入了一个高速发展的时期，越来越多的研究人员通过各种算法对工艺规划问题进行求解。例如蚁狮算法[1]、蝙蝠算法[2]、粒子群算法[3]等。果蝇优化算法（Fruit Fly Optimization Algorithm,FOA）是由台湾学者提出的一种群智能算法[4]。其与原有的进化算法相比，具有参数简单、原理易懂、搜索速度快等优点。在短短几年时间，就被成功地应用于多维背包问题[5]、混合流水车间调度问题[6]等诸多领域。

本文将采用果蝇优化算法对柔性工艺规划问题进行解决。首先，在基本FOA 算法的基础上，根据柔性工艺规划问题的特点，设计特殊的编码解码方式，以及适用于该问题的嗅觉搜索。其次，引入全局协作机制，增强算法的搜索能力。最后，通过实例对所提出算法进行测试，验证了FOA 算法的有效性。

1 柔性工艺规划模型

柔性工艺规划问题可以描述为：每个即将开始生产的工件都有着一种或几种加工特征，任何一个加工特征都含有一个或者多个可以挑选的加工工艺，所有加工工艺又有一个或者多个加工工序，每个加工工序又可被多台机器进行加工，并且零件的不同特征之间存在着先后顺序的约束。该问题的研究目标就是从加工工件的多条可选工艺路线中，选出一条合理可行并且使得某种优化指标最优的工艺路线。关于柔性工艺规划问题，以表1 所给出的零件工艺信息为例。该零件共有6 个加工特征，其中特征2 由两条可以相互替换的加工工艺进行加工。由5 台可选加工设备对零件的不同工序进行加工。同时，各个加工特征在加工时不能违反所存在的次序约束。

表1 某零件加工工艺信息表

本文的数学模型如下：

工件的工序加工时间见公式（1）：

其中n 表示的是待加工工件工艺路线中所包含的工艺数量，PTi表示的是待加工工件第i 道工艺所需要的加工时间。

零件在机器之间转换所需的时间TT 见公式（2）：

其中TTMi，Mi+1表示的是零件在选定的工艺路线中从加工第i 道工序的机器转换到加工第i+1 道工序的机器所需时间。

公式（3）为判断函数，当零件的工艺路线中相邻的两道工序在不更换机器生产的情况下，公式（3）取值为0；当相邻两道工序在不同的机器上进行加工时，式（3）取值为1。

本文的优化目标最小化加工时间见公式（4）：

2 果蝇优化算法求解柔性工艺规划问题

2.1 编码与解码

由于基本的果蝇优化算法通常被用于解决连续优化问题，所以基本的果蝇优化算法是无法直接求解离散型的柔性工艺规划问题。需要根据工艺规划的相关特征设计与之相符合的编码与解码过程才能对柔性工艺规划问题进行求解。在工艺规划中，必须对工序的顺序进行排序，并为每道工序选择合适的机器。种群中的每只果蝇都表示工艺规划的一个解决方案，并且每条工艺路线都由三个部分组成。第一部分是特征串，第二部分是候选工艺串，第三部分是候选机器串。三个部分是相对独立的，它们共同确定零件的加工工艺路线。图1 为表1 零件的一个可行编码方案，该零件具有6 个加工特征，因此特征串和候选工艺串的长度为6，候选机器串则等于总工序的数目，在工件中一共有9 道工序，因此候选机器串的长度为9。

图1 零件对应编码方案

由图1 中的编码信息可知该工件的各加工特征顺序为F1-F5-F3-F4-F2-F6；工件具体的加工工序顺序为O1-O8-O6-O7-O4-O5-O9；结合设备的选择和加工工序的信息解码后可以得到该工件的工艺路线为：O1（M4）-O8（M5）-O6（M4）-O7（M1）-O4（M3）-O5（M2）-O9（M2）。

2.2 种群初始化

果蝇种群代表了柔性工艺规划问题的解空间，而在种群中的每个果蝇代表着一条工艺路线。种群中有NS 个果蝇，每一只果蝇都由三个向量表示。由于种群的每个个体都由三段编码序列组成且代表着一条可行的工艺路线，因此需要分别对这三个部分进行初始化。假设某零件包含m个加工特征，特征串是采用随机的方法生成一个1 到m的编码序列。由于零件的加工特征之间存在着次序关系，随机初始化的方法可能会产生不符合次序约束的特征编码序列。因此，本文通过文献[7]的约束调整方法对产生的不合理特征序列进行重新排序。对于候选工序串，如果该零件的第n 个加工特征的可选工艺数量为m，那么在1 到m 的整数中随机选取一个整数，填入该序列的第n 个位置；同理，对于候选机器编码串，采用与生成候选工艺串相同的方法对候选机器序列进行生成。

2.3 嗅觉搜索与视觉搜索

在规范的果蝇算法中，嗅觉搜索是果蝇算法的核心搜索过程，果蝇种群采用邻域搜索的方法进行寻优。为了解决本文所研究的柔性工艺规划问题，本文使用了三种十分有效的邻域搜索方式：交换、插入、变异，其中变异操作又包含工序变异以及设备变异，交换和插入均作用于特征序列，因此在产生邻域时随机选择其中一种对特征序列进行改变，这三种操作可以让每一个果蝇个体生成多个邻域解。并且果蝇会围绕中心位置采用随机的搜索方向以及搜索距离进行寻优，这种随机的方式可以大大提升算法的全局寻优能力，增加解的多样性，相关具体操作如下所示：

①交换操作：随机从特征串编码中选择两个不同的位置，并将这两个位置上的数值进行交换，对出现的不合理的编码使用约束调整方法进行调整。

②插入操作：随机从特征串编码中随机选择一个位置，并将其插入特征串中的另一个位置，对于出现的不符合特征先后次序约束的编码，使用约束调整方法进行调整。

③工序变异操作：随机从候选工序编码串中选择一个位置，在其可选加工资源中，选择另外一种加工资源。

④机器变异操作：随机从候选机器编码串中选择一个位置，在其可选的设备集合中选择另一台加工设备。

在嗅觉搜索阶段，种群中的每个个体都会生成S 个邻域个体。在基于局部的视觉搜索中，这个阶段需要在S+1个方案种挑选出最佳的一个解决方案。对于嗅觉搜索中新生成的果蝇进行评价，然后采用贪婪的选择策略对每只父代果蝇进行更新。

2.4 全面协作机制

本文参考果蝇种群在觅食时的相互协作行为，在基本的果蝇优化算法中加入了全局协作机制对算法的寻优能力进行提高。根据柔性工艺规划问题的特点，本文采用两点交叉的方法对果蝇种群进行协作具体操作如下所示。

2.4.1 特征序列交叉操作

随机取两个交叉点将加工特征序列1 和加工特征序列2 分割成三部分，直接将加工特征序列1 中两个交叉点之间的特征数复制到新的加工特征序列的相应位置。在加工特征2 中，将已经从加工特征序列1 中复制到新的加工序列中的特征进行删除，然后将加工特征2 中其余的编码数按先后的顺序依次复制到新加工特征序列中的空白处，由此一条新的加工特征序列就被成功生成，具体操作如图2 所示。

图2 特征序列交叉操作

2.4.2 工艺序列交叉操作

随机选取两个交叉点将工艺序列1 与工艺序列2 分割成三部分，直接将工艺序列1 的两个交叉点之间的加工工艺序列复制到子代新加工序列的相应位置；然后，将工艺序列2 的两个交叉点两头的工艺序列复制到新加工工艺序列对应的位置上，通过以上的交叉操作可以得到一个全新的子代加工工艺序列，具体操作如图3 所示。

图3 工艺序列交叉操作

2.4.3 机器序列交叉操作

此部分操作与候选工艺串的交叉操作类似，此处就不多赘述，如图4 所示。

图4 机器序列交叉操作

2.5 FOA 求解柔性工艺规划问题总流程

基于以上分析，求解柔性工艺规划问题的改进果蝇优化算法的使用流程如图5 所示。

图5 改进果蝇优化算法总流程

3 数值实例测试

本文将通过Matlab 平台对该过程进行实现，本文的测试实例中的零件1 包含14 个加工特征20 道可选加工工序，具体加工工艺信息以及工件在不同机器之间的运输时间见文献[3]，优化目标为加工时间最小。果蝇优化算法参数设置如下：NP（初始化果蝇总数）=50；S（邻域解个数）=4；Maxgen（最大迭代次数）=200。由于需要与前人的研究结果进行对比，因此，参照文献[3]将果蝇优化算法程序运行20 次，并将程序运行20 次的实验结果进行统计，分别记录仿真结果中得到的最优值、平均值以及最优值平均收敛代数。最后，通过将FOA 算法求得的目标优化值与文献[3]中的三种算法所求得的优化结果进行比较，实例的优化结果对比统计后如表2 所示。

表2 零件1 的工艺路线优化结果对比

由表2 的对比结果可见，FOA 算法在20 次的运行中，每一次都可以搜寻到最优解。对四种方法的最优值进行统计分析，FOA 所求的平均值要小于其他三种算法所求的平均值，与最优值相同，也就是说FOA 每一次都可以搜索到最优解。因此，FOA 在解决柔性工艺规划问题上体现出了更好的稳定性。而且在20 次的FOA 算法运行中，FOA算法每次找到最优值所需要的收敛代数的平均值也较SA、GA 及MPSO 要少很多，具有更好的求解效率。

4 结论

本文针对工艺规划问题中的多种柔性，使用了三段式的编码结构。并且根据该问题的特点，对FOA 算法的嗅觉搜索阶段进行了改进，同时采用交叉操作进行种群间的协作，增强了FOA 算法的寻优能力。最后，通过数值实例对所提出的算法进行测试，实验结果表明，FOA 算法具有更好的求解效率以及稳定性。