基于GA的矿井通风网络图节点排序的优化

Optimized version for node scheduling of mining ventilation network graph based on GA

遗传算法(GA)作为一种全新的随机搜索与优化算法迅速地发展起来,并且在很多领域被广泛地应用。以遗传算法进行矿井通风网络图分支交叉数的优化,采用堆积木的组合思想进行交叉操作,来提高层次图的质量(分支交叉数少),并采用混合遗传算法增加了一个局部搜索过程,用于增强遗传算法的局部搜索能力。最后,根据研究的理论算法,优化网络图的节点排序,从而达到通风网络图的优化绘制。

This paper is aimed to apply the so-called hierarchical algorithm to the node scheduling of mining ventilation network in hoping to optimize the said node scheduling. As is known, the Genetic Algorithm （GA） has been developing rapidly and widely adopted as a brand new random search and optimal algorithm. On the basis of hierarchical network diagram, this paper has brought about the encoding of ventilation network graph based on the node ordering in hoping to introduce it into the area of mining ventilation to optimize the node ordering. In doing so, we have first of all made a description of the mathematical expression of the feasibility of the method for the sug- gested purpose. And, then, more detailed study on how to use the genetic algorithm to optimize a number of ventilation network branches including the mining field by combining the operation of the stacked wooden cross to improve the quality of the hierarchical graph （fewer crossing number of branches）. In doing so, we have adapted the hy- brid genetic algorithm, initiated by the three French scholars known as Pascale Kuntz, Bruno Pinand, and Rrmi Lehn, by using the center of gravity location of heuristic algorithm, hybrid genetic algorithm to enhance the local search ability of the genetic algorithm by reducing the number of crossing branches while adding a local search pro- cess. Thus, we have achieved a math representation through node layering and sorting in addition to introducing some kind of drawing algorithm of the math representation into the concrete graphic form, so as to determine the coordinates of nodes and drawing branches （straight line or curves）. And, as a result, the paper ends up with its study of the effect that the least number of crossing branches and nice drawing embodiment through a certain algorithm. And, consequently, we have gained two functions, the automatic drawing of ven- tilation network crossing number in the mine and optimization of the number of branches through C ＋ ＋ programming. The testing results show that the scheme proposed by us is ideal for drawing the ventila- tion network with small scales. But it remains reluctant for the larger scale ventilation network with more branches for it involves longer transferring complexity and continuous adjustment of the original graphics.