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

针对工艺设计中的工艺路线优化问题,归纳了工步间的基本优先级约束关系。基于约束关系,将整个工艺活动过程转化为工步有向图,工步节点间的拓扑关系以约束矩阵的形式存储。提出了约束矩阵判错的检测方法;建立了工步图的拓扑排序模型。设计了一种随机的深度优先搜索算法对工步图进行拓扑排序,得到全部可行的一定数目初始工艺计划作为遗传算法的初始种群。算法中,提出了基于车间动态资源的加工序列编码策略;定量分析了工艺计划评价准则,采用罚函数的方法将目标函数和约束条件建立成一个无约束的优化目标函数,由此确定了染色体的适应度函数;设计了遗传操作算子(选择、交叉、变异),并通过基于模拟退火机制的精英策略加速算法收敛。最后,通过实例证明了该算法的有效性。

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

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 operat...