一个新的基于GA的有向无环图画图算法  

A new GA based drawing algorithm for directed acyclic graphs

作　　者：纪凌光[1] 高世臣[1] 王娟[1,2] 

机构地区：[1]中国地质大学,北京100083 [2]中国石油长庆油田分公司,710018

出　　处：《微计算机信息》2009年第30期149-150,176,共3页Control & Automation

摘　　要：本文提出一种新的有向无环图画图算法,这种算法是建立在图的分层理论和遗传算法的基础上。分层是通过加一些约束,降低了搜索难度,提高了遗传算法的执行效率。并在遗传算法中给出一个目标函数,此函数表征了图的均匀性,对称性和交叉点的数目。最后通过仿真说明了此算法的有效性。A new drawing algorithm for directed acyclic graphs which based on graph layered theory, and genetic algorithm is proposed in this paper. The new algorithm has two steps： first graph layered method and then Genetic algorithm （GA） is utilized. The graph layered method aims at reducing the calculation complexity of GA. In GA a special objective function is given. The function signifies the uniformity, symmetry and the number of cross-point of the graph. Finally, some simulation result proves the effectiveness of the new algorithm.

关 键 词：遗传算法 有向无环图 图的分层 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]