基于遗传算法与有向图拓扑排序的工艺路线优化  

Process planning optimization based on genetic algorithm and topological sort algorithm for digraph

作　　者：黄伟军[1] 蔡力钢[1] 胡于进[1] 王学林[1] 凌玲[1] 

机构地区：[1]华中科技大学机械科学与工程学院

出　　处：《计算机集成制造系统》2009年第9期1770-1778,共9页Computer Integrated Manufacturing Systems

基　　金：国家863计划资助项目(2006AA04Z136);国家自然科学基金资助项目(50675078)~~

摘　　要：针对工艺设计中的工艺路线优化问题,归纳了工步间的基本优先级约束关系。基于约束关系,将整个工艺活动过程转化为工步有向图,工步节点间的拓扑关系以约束矩阵的形式存储。提出了约束矩阵判错的检测方法;建立了工步图的拓扑排序模型。设计了一种随机的深度优先搜索算法对工步图进行拓扑排序,得到全部可行的一定数目初始工艺计划作为遗传算法的初始种群。算法中,提出了基于车间动态资源的加工序列编码策略;定量分析了工艺计划评价准则,采用罚函数的方法将目标函数和约束条件建立成一个无约束的优化目标函数,由此确定了染色体的适应度函数;设计了遗传操作算子(选择、交叉、变异),并通过基于模拟退火机制的精英策略加速算法收敛。最后,通过实例证明了该算法的有效性。Aming at process planning optimization in process design, the basic priority of constraints between operations were summed up, the entire process was transformed into an operation digraph based on the constraint relationship. The topological relationships among operation nodes were transformed into a constraint matrix, a detection approach for matrix-bound judgement was proposed. The operation graph＇s topological sort model was established. A random depth-first search algorithm to topologically sort out an operation digraph was designed and a certain number of feasible initial proeess planning qua the initial population of genetic algorithm was obtained. In the algorithm, processing sequence coding strategy based on the dynamic Job Shop resources was proposed. The evaluation criteria of the process planning was analyzed quantitatively, the objective function and constraints was established as a nonconstraint optimization objective function by using penalty function, thus the chromosome＇s fitness function was determined. Genetic operations （selection, crossover and mutation） were developed. Algorithm astringency was speed up by elite tactic based on simulated annealing algorithm. Finally, an illustrative example was given to testify the effectiveness of this algorithm.

关 键 词：工艺设计 工艺路线优化 遗传算法 工步有向图 拓扑排序 约束矩阵 

分 类 号：TH162[机械工程—机械制造及自动化] TP391[自动化与计算机技术—计算机应用技术]