论文部分内容阅读
【摘 要】在缓冲区总容量确定的约束条件下，以生产线效率最大化为目标进行研究，针对线性混合管道的缓冲容量分配问题，提出了一种遗传模拟退火算法。该算法主要以遗传算法为核心，引入模拟退火算法，具有较好的局部搜索能力和全域搜索能力。最后，证明了算法的收敛性。仿真实验结果表明，遗传模拟退火算法在分配线性混合制造系统缓冲能力时比传统算法更为有效。
【Abstract】Under the constraint of the total capacity of the buffer， the goal of maximizing the efficiency of the production line is studied. Aiming at the problem of buffer capacity allocation in linear mixed pipelines， a genetic simulated annealing algorithm is proposed. The algorithm mainly adopts genetic algorithm as the core and introduces simulated annealing algorithm， which has better local search ability and global search ability. Finally， the convergence of the algorithm is proved. The simulation results show that the genetic simulated annealing algorithm is more effective than the traditional algorithm in allocating the buffer capacity of the linear hybrid manufacturing system.
【关键词】直线型； 遗传模拟退火算法； 早熟
【Keywords】linear pattern； genetic simulated annealing algorithm； precocious
【中图分类号】TB497 【文献标志码】A 【文章编号】1673-1069（2018）08-0154-03
1 引言
缓冲区被临时设计用来存储半成品和成品，以减少随机事件或影响和破坏其他设备乃至整个系统的性能。缓冲区容量分配问题一直是制造系统设计者们面临的一个重要的优化问题。
缓冲区最优分配问题是一个np-hard问题。对缓冲区分配问题的研究已经有几十年的历史，已有的方法可以归结为传统的数学规划法和启发式算法两种。许多学者对此做出了巨大贡献，例如：Koenigsberg（1959）[1]，Buzacott and Hanifin （1978）[2]，Dallery and Gershwin（1992）[3]， Gershwin（1994）[4]， Aksoy and Gupta[5]。
传统的数学规划法依赖于精确的数学模型，但精确的数学模型较复杂，难以适应实时控制的要求，而较简单的数学模型误差又大。为了更好地解决缓冲区最优分配问题，研究人员逐渐把启发式算法应用于解决缓冲区最优分配问题。
Can和Heavey[6]提出了用遗传算法来解决连续生产线的缓冲区分配问题以使得生产线的效率最大化。研究提出了一种通过实验设计经验的分析方法，这个方法使用遗传算法解决基于模拟的直线型生产线的缓冲区问题，但该方法容易陷入局部最优解且比较耗时。Spinellis 和Papadopoulos[7]提出了用模拟退火算法来实现生产线效率的最大化。
本文通过利用模拟退火算法对遗传算法进行改进，先通过一定的策略生成种群，然后用遗传算法进行求解，在遗传算法结束后再利用模拟退火算法进行一次局部搜索，尝试在当前求得的最优解的前提下获取更优解。
2 模型描述
图1所示为一由K台设备，K-1个缓冲（B1，B2，…，BK-1 ）组成的相似型生产线模型。原材料从外部到设备M1，再进入缓冲B1，进而到设备M2，直到设备MK，最终退出生产线系统。Ci为生产线中各个缓冲区最大缓冲区容量，pi与ri分别为设备故障率和维修率，且服从指数分布，则其平均故障时间为1/pi，Ti为设备加工时间。
3 缓冲区分配问题的研究
缓冲区容量分配技術主要由评价方法和生成方法两部分组成。评价方法是对生产线成产效率进行预测，生成方法是来寻找最优的缓冲区容量分配方案。
3.1 评价方法
评价方法主要分为精确法和近似法两类。由于精确法只是用于较为简单的生产线模型，故本文采用近似法中的分解方法来评价成产线的生产效率。
3.2 遗传模拟退火算法
遗传模拟退火算法可视为在遗传算法中引入了模拟退火算法的思想，有效地缓解了遗传算法的选择压力，避免了早熟，增强了遗传算法的全局收敛能力。遗传模拟退火算法以遗传算法控制寻优方向，用模拟退火算法解决局部收敛性的问题，具有较高的效率和广泛的适用性。
3.3 遗传模拟退火算法参数流程
3.3.1 遗传算法部分[7]
第1步 初始化种群。
第2步 选择。
采用轮盘赌选择法。轮盘赌选择法是从染色体群体中选择一些个体的方法，被选中的机率和它们的适应度成比例，染色体的适应度数愈高，被选中的概率也愈大。
第3步 个体评价。
第4步 基因操作。
变异操作需要每个个体的基因位置，并根据突变概率计算其值以产生新个体。 3.3.2 模拟退火算法部分
用模拟退火算法模拟热力学系统[9]中的退火过程。在退火过程中，目标函数被用作能量函数。主要参数设置包括：
①初始温度；
②领域函数；
③接受概率。
具体操作步骤为：
步骤1初始化。选择初始解x=parent，最优值为极小值。初始温度为T。
步骤2通过随机扰动产生新的解决方案如下：
①在当前解向量中，随机选择两个位置POS来计算剩余空间的总MM。
②对于第一选择位置POS（1），在剩余松弛区域的空间范围内随机地产生占据的松弛空间的大小，并且更新所占用的松弛区域的大小。
③对于所选择的第二位置POS（2），由给定空间占用的空间不大于松弛区域的总和的上界。
④计算更新解XTEMP的函数值ATEMP，计算值与当前最优函数值DF=AtEMP-MIAES之间的差值。
步骤3更新当前解决方案：
①如果DF<0，则以1的概率更新当前最优解。
②如果DF大于0，则用概率EXP（-）更新当前最优解。
窗体顶端
步骤4若T>0，更新温度T=T-0.1，返回步骤2。否则停止计算，输出当前最优解。
4 数值仿真
仿真环境：双核心英特尔第二代核心处理器（OpTIPLEX 3010型号戴尔计算机）、Win 7最终32位系统和Matlab 2010A软件的主频率为3.30GHZI3 2120。
它分别对五条装备生产线和十条装备生产线进行了试验模拟。在实验中，给出了平均工作时间（MTTF）和平均修复时间（MTTR），假设每个器件失效后的连续工作时间和修复时间满足指数分布。
在五设备小型生产线中，缓冲区总量B=31，其余参数见表1。将混合算法与 Diomidis 提出的模拟退火算法、传统遗传算法进行比较，通过比较生产率的大小来说明算法的优劣性。
可以看出，对于直线型生产线缓冲区优化问题，遗传模拟算法下的生产效率最高，其次是遗传算法，模拟退火算法较差。两种算法较好的原因在于它们均为采用了遗传算法的种群生成，每个种群中基因数较多，因此可以在产生新种群的同时产生大量信息。
模拟退火算法的本质是串行算法。当生成新的解决方案时，只能使用一个解决方案信息。仿真结果表明，遗传算法被困在局部最优解中，通过引入模拟退火算法来跳出局部最优解，找到最优解。遗传模拟退火算法采用模拟退火代替遗传算法中的变异操作，从而增加了算法的搜索空间，提高了遗传算法中变异操作的能力差，产生新的解，从而使遗传算法更具鲁棒性。E性能大大提高。
5 结论
在建立线性生产线模型的基础上，将模拟退火算法引入遗传算法，设计了遗传模拟退火算法。在保留遗传算法的全域搜索能力的基础上，提高了局部搜索能力，得到了近似最优值。原因是交叉操作是产生新的解决方案的主要步骤，并且突变操作由于突变率的大小常常被忽略，导致搜索范围小。为了解决这一问题，引入了模拟退火算法的摄动运算，因为该过程所产生的解较大，将以一定的概率接受，从而提高了遗传算法的搜索能力。采用遗传模拟退火算法对线性生产线的缓冲容量进行分配。与传统的遗传算法和模拟退火算法相比，其产率有了很大的提高。
【参考文献】
【1】Koenigsberg， E. （1959）. Production lines and internal storage—A review[J]. Management Science， 5，410-433.
【2】Buzacott， J. A.， & Shanthikumar， J. G. Stochastic models of manufacturing systems. New Jersey： Prentice-Hall[M].Production & Operations Management ， 2007.
【3】Dallery Y， Gershwin S B. Manufacturing flow line systems： a review of models and analytical results[J]. Queueing systems， 1992，12（1-2）：3-94.
【4】Gershwin， S. B.， & Schor， J. E.（2000）. Efficient algorithms for bufferspace allocation[J]. Annals of Operations Research，93，117-144.
【5】Aksoy， K. H.， & Gupta， S. M. （2010）. Near optimal buffer allocation in remanufacturing systems with N-policy[J]. Computers，Industrial Engineering， 59，496-508.
【6】Can， B.， & Heavey， C. （2011）. Comparison of experimental designs for simulation-based symbolic regression of manufacturing systems[J].Computers ， Industrial Engineering， 61（3）：447-462.
【7】Z.米凱利维茨.演化程序——遗传算法和数据编码的结合[M].北京：科学出版社，2007.
【8】刘红，韦穗.遗传算子的分析[J].计算机技术与发展，2006（10） ：10-16.
【9】葛洪伟，王银年.求解VRPSDP问题的改进模拟退火遗传算法[J].计算机工程与应用，2010（30）：136-137.
【Abstract】Under the constraint of the total capacity of the buffer， the goal of maximizing the efficiency of the production line is studied. Aiming at the problem of buffer capacity allocation in linear mixed pipelines， a genetic simulated annealing algorithm is proposed. The algorithm mainly adopts genetic algorithm as the core and introduces simulated annealing algorithm， which has better local search ability and global search ability. Finally， the convergence of the algorithm is proved. The simulation results show that the genetic simulated annealing algorithm is more effective than the traditional algorithm in allocating the buffer capacity of the linear hybrid manufacturing system.
【关键词】直线型； 遗传模拟退火算法； 早熟
【Keywords】linear pattern； genetic simulated annealing algorithm； precocious
【中图分类号】TB497 【文献标志码】A 【文章编号】1673-1069（2018）08-0154-03
1 引言
缓冲区被临时设计用来存储半成品和成品，以减少随机事件或影响和破坏其他设备乃至整个系统的性能。缓冲区容量分配问题一直是制造系统设计者们面临的一个重要的优化问题。
缓冲区最优分配问题是一个np-hard问题。对缓冲区分配问题的研究已经有几十年的历史，已有的方法可以归结为传统的数学规划法和启发式算法两种。许多学者对此做出了巨大贡献，例如：Koenigsberg（1959）[1]，Buzacott and Hanifin （1978）[2]，Dallery and Gershwin（1992）[3]， Gershwin（1994）[4]， Aksoy and Gupta[5]。
传统的数学规划法依赖于精确的数学模型，但精确的数学模型较复杂，难以适应实时控制的要求，而较简单的数学模型误差又大。为了更好地解决缓冲区最优分配问题，研究人员逐渐把启发式算法应用于解决缓冲区最优分配问题。
Can和Heavey[6]提出了用遗传算法来解决连续生产线的缓冲区分配问题以使得生产线的效率最大化。研究提出了一种通过实验设计经验的分析方法，这个方法使用遗传算法解决基于模拟的直线型生产线的缓冲区问题，但该方法容易陷入局部最优解且比较耗时。Spinellis 和Papadopoulos[7]提出了用模拟退火算法来实现生产线效率的最大化。
本文通过利用模拟退火算法对遗传算法进行改进，先通过一定的策略生成种群，然后用遗传算法进行求解，在遗传算法结束后再利用模拟退火算法进行一次局部搜索，尝试在当前求得的最优解的前提下获取更优解。
2 模型描述
图1所示为一由K台设备，K-1个缓冲（B1，B2，…，BK-1 ）组成的相似型生产线模型。原材料从外部到设备M1，再进入缓冲B1，进而到设备M2，直到设备MK，最终退出生产线系统。Ci为生产线中各个缓冲区最大缓冲区容量，pi与ri分别为设备故障率和维修率，且服从指数分布，则其平均故障时间为1/pi，Ti为设备加工时间。
3 缓冲区分配问题的研究
缓冲区容量分配技術主要由评价方法和生成方法两部分组成。评价方法是对生产线成产效率进行预测，生成方法是来寻找最优的缓冲区容量分配方案。
3.1 评价方法
评价方法主要分为精确法和近似法两类。由于精确法只是用于较为简单的生产线模型，故本文采用近似法中的分解方法来评价成产线的生产效率。
3.2 遗传模拟退火算法
遗传模拟退火算法可视为在遗传算法中引入了模拟退火算法的思想，有效地缓解了遗传算法的选择压力，避免了早熟，增强了遗传算法的全局收敛能力。遗传模拟退火算法以遗传算法控制寻优方向，用模拟退火算法解决局部收敛性的问题，具有较高的效率和广泛的适用性。
3.3 遗传模拟退火算法参数流程
3.3.1 遗传算法部分[7]
第1步 初始化种群。
第2步 选择。
采用轮盘赌选择法。轮盘赌选择法是从染色体群体中选择一些个体的方法，被选中的机率和它们的适应度成比例，染色体的适应度数愈高，被选中的概率也愈大。
第3步 个体评价。
第4步 基因操作。
变异操作需要每个个体的基因位置，并根据突变概率计算其值以产生新个体。 3.3.2 模拟退火算法部分
用模拟退火算法模拟热力学系统[9]中的退火过程。在退火过程中，目标函数被用作能量函数。主要参数设置包括：
①初始温度；
②领域函数；
③接受概率。
具体操作步骤为：
步骤1初始化。选择初始解x=parent，最优值为极小值。初始温度为T。
步骤2通过随机扰动产生新的解决方案如下：
①在当前解向量中，随机选择两个位置POS来计算剩余空间的总MM。
②对于第一选择位置POS（1），在剩余松弛区域的空间范围内随机地产生占据的松弛空间的大小，并且更新所占用的松弛区域的大小。
③对于所选择的第二位置POS（2），由给定空间占用的空间不大于松弛区域的总和的上界。
④计算更新解XTEMP的函数值ATEMP，计算值与当前最优函数值DF=AtEMP-MIAES之间的差值。
步骤3更新当前解决方案：
①如果DF<0，则以1的概率更新当前最优解。
②如果DF大于0，则用概率EXP（-）更新当前最优解。
窗体顶端
步骤4若T>0，更新温度T=T-0.1，返回步骤2。否则停止计算，输出当前最优解。
4 数值仿真
仿真环境：双核心英特尔第二代核心处理器（OpTIPLEX 3010型号戴尔计算机）、Win 7最终32位系统和Matlab 2010A软件的主频率为3.30GHZI3 2120。
它分别对五条装备生产线和十条装备生产线进行了试验模拟。在实验中，给出了平均工作时间（MTTF）和平均修复时间（MTTR），假设每个器件失效后的连续工作时间和修复时间满足指数分布。
在五设备小型生产线中，缓冲区总量B=31，其余参数见表1。将混合算法与 Diomidis 提出的模拟退火算法、传统遗传算法进行比较，通过比较生产率的大小来说明算法的优劣性。
可以看出，对于直线型生产线缓冲区优化问题，遗传模拟算法下的生产效率最高，其次是遗传算法，模拟退火算法较差。两种算法较好的原因在于它们均为采用了遗传算法的种群生成，每个种群中基因数较多，因此可以在产生新种群的同时产生大量信息。
模拟退火算法的本质是串行算法。当生成新的解决方案时，只能使用一个解决方案信息。仿真结果表明，遗传算法被困在局部最优解中，通过引入模拟退火算法来跳出局部最优解，找到最优解。遗传模拟退火算法采用模拟退火代替遗传算法中的变异操作，从而增加了算法的搜索空间，提高了遗传算法中变异操作的能力差，产生新的解，从而使遗传算法更具鲁棒性。E性能大大提高。
5 结论
在建立线性生产线模型的基础上，将模拟退火算法引入遗传算法，设计了遗传模拟退火算法。在保留遗传算法的全域搜索能力的基础上，提高了局部搜索能力，得到了近似最优值。原因是交叉操作是产生新的解决方案的主要步骤，并且突变操作由于突变率的大小常常被忽略，导致搜索范围小。为了解决这一问题，引入了模拟退火算法的摄动运算，因为该过程所产生的解较大，将以一定的概率接受，从而提高了遗传算法的搜索能力。采用遗传模拟退火算法对线性生产线的缓冲容量进行分配。与传统的遗传算法和模拟退火算法相比，其产率有了很大的提高。
【参考文献】
【1】Koenigsberg， E. （1959）. Production lines and internal storage—A review[J]. Management Science， 5，410-433.
【2】Buzacott， J. A.， & Shanthikumar， J. G. Stochastic models of manufacturing systems. New Jersey： Prentice-Hall[M].Production & Operations Management ， 2007.
【3】Dallery Y， Gershwin S B. Manufacturing flow line systems： a review of models and analytical results[J]. Queueing systems， 1992，12（1-2）：3-94.
【4】Gershwin， S. B.， & Schor， J. E.（2000）. Efficient algorithms for bufferspace allocation[J]. Annals of Operations Research，93，117-144.
【5】Aksoy， K. H.， & Gupta， S. M. （2010）. Near optimal buffer allocation in remanufacturing systems with N-policy[J]. Computers，Industrial Engineering， 59，496-508.
【6】Can， B.， & Heavey， C. （2011）. Comparison of experimental designs for simulation-based symbolic regression of manufacturing systems[J].Computers ， Industrial Engineering， 61（3）：447-462.
【7】Z.米凱利维茨.演化程序——遗传算法和数据编码的结合[M].北京：科学出版社，2007.
【8】刘红，韦穗.遗传算子的分析[J].计算机技术与发展，2006（10） ：10-16.
【9】葛洪伟，王银年.求解VRPSDP问题的改进模拟退火遗传算法[J].计算机工程与应用，2010（30）：136-137.