Research On Edge Crossing Minimization Of Hierarchical Graph Based On Improved DE

Hierarchical graph is a graph that assigns vertices to different levels for representation.It is widely used in software engineering,bioinformatics,VLSI design,and other fields.Multi-layer crossing minimization is one of the core problems in the automatic drawing of hierarchical graph,which directly affects the readability of graph.However,this problem is a combinatorial optimization problem in essence,and has been proved to be NP-hard.At present,the mainstream optimization algorithm for this problem still needs to be improved in terms of solving accuracy and solving speed.To solve these problems,an improved discrete differential evolution algorithm is proposed to solve the hierarchical graph edge crossing minimization problem.Firstly,the standard differential evolution algorithm(DE)is discretized by combining the characteristics of the hierarchical graph automatic drawing algorithm and the multi-layer crossing minimization problem.Secondly,the initial population is improved based on local search operator and opposite-based learning strategy,which improves the uniformity of population distribution and individual quality,and speeds up the convergence speed of the algorithm.Finally,before the next round of optimization,the parameter adaptive strategy is used to update the relevant parameters involved in the algorithm search process,and dynamic local search is carried out according to the feedback information,which helps to achieve a better balance between the algorithm exploration and exploitation.In the simulation data,the propesed is compared with other mainstream optimization algorithms.Experimental results show that compared with the traditional heuristic algorithm,the average number of crossings the proposed are reduced by 13.37,37.00,and 105.74 respectively in bipartite graph experiments.In the multi-layer graph experiment,compared with the meta-heuristic algorithm,the average number of crossings are reduced by 18.4,12.2 and 3.0 respectively.In conclusion,the proposed has better optimization performance improvement when solving the multi-layer crossing minimization problem.In this thesis,the proposed is also embedded into the mine ventilation management information system,and the automatic drawing of the mine ventilation network graph is successfully realized,and good practical application effect is achieved.This thesis has 29 pictures,13 tables and 59 references.