2020年(决策管理）基于改进最大-最小蚂蚁系统的多工艺路线决策方法研究

基于改进最大-最小蚂蚁系统的多工艺路线决策方法研究基金项目：国防科工委基础科研项目(D0420060521)。Foundation item: Commission of Science Technology and Industry for National Defense Research Project, China (No. D0420060521).作者简介：刘新华（1981-），男，江苏徐州人，哈尔滨工业大学机电工程学院博士研究生，主要从事工艺准备集成技术、本体技术、粗糙集理论、人工智能等方面的研究。E-mail：l_xinhuayahoo.com.cn。刘新华，张旭堂，刘文剑(哈尔滨工业大学 机电工程学院， 黑龙江 哈尔滨 150001)摘要：为了实现工艺规划与生产调度的集成，提出了基于最大-最小蚂蚁系统的多工艺路线决策方法。给出了零件可行性工艺路线图的概念，建立了多工艺路线决策问题的数学模型，从而将零件的工艺路线规划问题转化成对零件可行性工艺路线图中具备最优值的路径搜索和寻优问题。提出了基于精英蚂蚁排序策略的改进最大-最小蚂蚁系统，并设计了算法流程。最后，通过仿真实例验证了改进的算法具有很好的鲁棒性，并且在性能上优于其他算法。关键词：多工艺路线决策；最大-最小蚂蚁系统；可行性工艺路线图Research on Multi-Process Routes Decision-Making Methodology Based on Improved Max-Min Ant SystemLIU Xin-hua, ZHANG Xu-tang, LIU Wen-jian(School of Mechatronics Engineering, Harbin Institute of Technology, Harbin 150001, China)Abstract：In order to realize integration of process planning and production scheduling, an MMAS-based methodology for multi-process routes decision-making was proposed. The feasibility process graph for a part was defined and the mathematic model of multi-process routes decision-making problem was set up. Thus, the problem of multi-process routes decision-making was transformed into the problem of searching optimum path in this directed graph. Moreover, an improved max-min ant system based on the strategy of sorting elite ants was presented and the flowchart was designed. Finally, by simulations, the robustness and outperforming others of the improved algorithm were verified.Key words：multi-process routes decision-making; max-min ant system; feasibility process graph0 引言工艺路线是连接产品设计和产品制造的重要纽带，没有合理正确的工艺路线，就不可能经济而有效地将设计蓝图转变成合格产品1。因此，工艺路线的合理制定对于保证产品质量、提高生产率以及降低生产成本都具有十分重要的意义。目前，工艺路线的决策方法主要有基于事例推理的方法2、基于知识推理的方法3和基于特征的决策方法4-5等。但是这些决策方法主要采用线性规划的方式，容易导致一些本来可选的工艺路线方案在工艺规划的早期阶段就被过早地丢弃，还可能由于太多的约束使得最终的工艺路线方案并不是最优；同时，在工艺规划过程中，现有的CAPP系统对后续生产调度考虑不充分，因此，制定的工艺路线在后续的生产调度过程中常常遭遇诸如资源瓶颈等问题。对此，很多学者试图将人工智能技术用于工艺路线决策，如遗传算法6-7、神经网络8-9、进化算法10、蚁群算法11以及它们的混合算法12-13，并取得了较好的成果。由于受到产品种类多样性、制造过程离散性、生产环境复杂性以及系统状态模糊性的综合影响，每种算法都有各自的特色和不足。蚁群优化算法（Ant Colony Optimization，ACO）是模拟真实蚁群觅食过程寻求最短路径的原理而发展起来的一种启发式仿生搜索算法，最早由意大利学者M.Dorigo等人提出，用于求解复杂的组合优化问题14-16。实验结果表明蚁群优化算法具有较强的鲁棒性和发现较好解的能力，但同时也存在一些缺陷，如收敛速度慢、容易出现停滞现象、算法的运行时间长等，从而影响了蚁群优化算法在组合优化问题中的应用。本文针对上述问题，提出了基于最大-最小蚂蚁系统的工艺路线规划方案。文章首先阐述了零件可行性工艺路线图的概念，从而将工艺路线规划问题转化成对该加权有向图中具备最优值的路径搜索和寻优问题，并建立了多工艺路线决策问题的数学模型。对最大-最小蚂蚁系统进行改进，引入了局部信息素更新机制和全局信息素更新中的精英蚂蚁排序策略，减小了蚂蚁算法陷入局部陷阱的可能性，加快了其收敛速度。最后将改进的算法应用到多工艺路线决策问题中，详细讨论了该算法的具体实现流程，并通过仿真实例验证了该算法的可行性和有效性。1 零件可行性工艺路线图定义一个非负值的加权简单有向图：。其中：G表示零件可行性工艺路线图；为顶点集，表示工艺路线中的n道工序，图中有且仅有一个开始节点和一个结束节点，节点的权值称为计算开销；为有向边集，表示工序之间的关联关系，有向边的权值称为通信开销；表示从节点到节点的有向边，其中：称为有向边的前驱节点，称为有向边的后续节点，显然。定义集合为顶点的后续节点集合，即工序的下一道可选工序集合；定义一个工序序列L，表示一条完整、可行的工艺路线。零件可行性工艺路线图中的顶点和有向边除了表示零件工艺路线之间的关联关系和约束关系外，还包括其他一些工艺信息。例如，顶点还包含该道工序的加工成本、使用设备、加工时间、工艺质量等信息；有向边还包含两道工序之间的搬运距离、搬运工具、搬运成本等信息，这些信息在计算工序执行成本时起到非常重要的作用。2 多工艺路线决策方案在传统CAPP系统中往往只考虑单条、线性工艺路线，且工艺路线多在不考虑生产资源是否可用的情况下制定。但由于生产环境的复杂性，在实际生产中经常会出现刀具准备不到位或设备出现突发故障的情况，中断了工艺路线的执行，进而影响了生产进度。为了解决这个弊端，本文提出了基于最大-最小蚂蚁系统的工艺路线规划方案，如图1所示，该方案将工艺路线规划过程分解为两个步骤：步骤1：零件可行性工艺路线图构建。工艺规划阶段，根据零件几何信息和技术要求，设计多条可行的工艺路线，以零件可行性工艺路线图的形式表示并存储；步骤2：多工艺路线决策。生产调度阶段，考虑制造周期、加工成本、工艺质量、企业制造资源配置等情况，对零件所有可行性工艺路线进行评估，从中寻找出最优工艺路线。该方案的思路就是将工艺路线规划问题转化成对零件可行性工艺路线图中具备最优值的路径搜索和寻优问题。图1 多工艺路线决策方案零件可行性工艺路线图构建途径主要有三个：事例检索。利用相似性原理，从事例库中检索出符合条件的事例，直接使用或修正后使用，这里的事例是指零件可行性工艺路线图；知识推理。如果检索不到符合条件的事例，则利用专家知识进行推理，构建零件可行性工艺路线图；手工绘制。当事例库、知识库规模较小时，可以通过工作流建模工具手工绘制零件可行性工艺路线图。由于零件可行性工艺路线图构建不是本文研究的重点，在此不作详细描述。对于零件可行性工艺路线图中具备最优值的路径搜索和寻优问题，其数学模型可以描述如下：s.t. 式中：表示工序的执行成本，是对所执行工序的加工成本、使用设备、加工时间以及其他因素的综合考虑，包括计算开销和通讯开销两部分；K表示执行成本影响因素集，包括静态影响因素和动态影响因素；W表示各影响因素的权重系数，用来区别每个影响因素对工序执行成本的相对重要程度；如果有向边被选中，则的后续节点同时被选中。考虑到各项影响因素在数量级上可能不一致，需要进行无量纲修正，修正公式如下：3 基于MMAS的多工艺路线决策算法最大-最小蚂蚁系统（MMAS）直接来源于ACO算法，主要作了如下改进：每次迭代结束后，只有最优解所属路径上的信息素被更新，从而更好地利用了历史信息；为了避免算法过早收敛于并非全局最优的解，将各条路径可能的信息素浓度限制于，超出这个范围的值被强制设为或者是，可以有效避免某条路径上的信息素远大于其余路径，使得所有蚂蚁都集中到同一条路径上，从而使算法不再扩散。本文对基于MMAS的多工艺路线决策算法作一些规定：每次迭代前设置蚂蚁的初始位置为开始节点，蚂蚁到达的最后位置对应结束节点；蚂蚁根据概率选择下一道工序，每次在选择之前都要判断一个可行性工序搜索空间，而且只在中选择，并把选中的工序放入工序序列L中。3.1 路径构造根据MMAS算法原理可知，蚂蚁每一步都是沿着概率最大的方向转移到下一道工序，直到找到结束节点为止。而每只蚂蚁选择下一道工序时，在满足约束条件的前提下，蚂蚁转移的概率和当前工序节点与下一道工序节点之间的信息素浓度成正比，和下一道工序节点的执行成本成反比，因此，第k条路径上的蚂蚁在工序选择工序的概率由下式决定：式中：表示t时刻从工序转移到工序的信息素浓度；表示t时刻从工序转移到工序的启发式信息，即可见度；表示信息素在路径选择中的相对重要程度；表示启发式信息在路径选择中的相对重要程度；定义，其中T为常量，为调解参数。蚂蚁已经选择的工序节点和不符合加工顺序约束的工序节点被放入禁忌（tabu）表中，tabu表中的工序节点不能作为蚂蚁下一步选择的工序节点。3.2 信息素更新随着时间的推移，蚂蚁在走过的路径上留下信息素，该信息素可以进一步影响后来的蚂蚁，使得群体蚂蚁走向最优解，同时该路径上先前留下的信息素将逐渐消失。因此，必须定期对路径上的信息素进行更新，以引导后来的蚂蚁走向最优。本文采用两次信息素更新，即局部信息素更新和全局信息素更新。蚂蚁每走完一步，就应该对走过路径上的信息素进行挥发，避免其他蚂蚁走相同的路径以致陷入局部最优解，因此需要更新局部信息素。局部信息素更新方式如下：式中：为局部信息素挥发因子，；表示初始信息素，。所有蚂蚁都到达结束节点以后，需要进行全局信息素更新，目的是为了使蚂蚁在走过的路径上留下相应的信息素，同时更好的利用已知最优解。全局信息素更新方式如下：，式中：为全局信息素挥发因子，；表示信息素增量；Q为常量，表示蚂蚁释放的信息素量；表示当前全局最优解的长度。这种全局信息素更新方式收敛速度较慢，而且其全局优化能力也不明显。为了加快其收敛速度，同时又不影响全局优化能力，在较短的时间内找到最优解，笔者提出一种基于精英蚂蚁排序策略的全局信息素更新方法。该方法保留全局的最优解，在每次迭代完成后，只将最好的蚂蚁用于信息素更新，即将求解结果中排名前几位的所谓精英蚂蚁用于信息素更新，同时将精英蚂蚁所经路径按从小到大的顺序排列，即，并根据