基于GA与最长路径并联通路法优化通风网络图绘制

针对矿井通风网络图分支交叉的问题，基于最长路径对网络图节点分层，以遗传算法优化节点排序，主要采用堆积木的组合思想来进行层间交叉与层内交叉操作，提高层次图的质量（减少分支交叉数），并以重心定位启发式算法来增强遗传算法的局部搜索能力，提高遗传算法的搜索质量。最后，以改进的最长路径并联通路法绘制出较优的通风网络图。

Optimization on drawing of ventilation network graph based on GA and longest parallel path method

According to the problem of branch crossing in ventilation network graph of mine, on the basis of layering network graph nodes based on the longest path, genetic algorithm (GA) was applied to optimize node ordering. Also, the inter-layer crossover and intra-layer crossover operation were conducted by using the combination idea of stacked wooden cross, so as to improve the quality of hierarchical graph (fewer crossing number of branches). Meanwhile, the heuristic algorithm of center of gravity location was applied to enhance the local search ability and quality of genetic algorithm. Finally, the optimal ventilation network graph of mine was drawn by the improved longest parallel path method.