基于遗传算法的有向无环图画图算法  

Graph drawing algorithm for directed acyclic graphs based on genetic algorithm

作　　者：高榕[1] 李跃新[1] 

机构地区：[1]湖北大学数学与计算机科学学院,武汉430062

出　　处：《计算机应用研究》2007年第12期63-65,共3页Application Research of Computers

基　　金：国家自然科学基金资助项目(70271033)

摘　　要：在研究了现有画有向无环图的主要方法的基础上提出一种基于遗传算法的有向无环图画图算法,将一般有向无环图的画图问题转换为函数优化问题,用遗传算法求目标函数最优解的近似值。实验表明此算法具有算法统一、方法简单、容易实现、易于修改,并且具有自适应、自学习和易于并行化的特点。Via studying the predominant rmethods for drawing directed acyclic graphs, this paper proposed a new graph drawing algorithm for directed graphs which based on the genetic algorithm. The algorithm transformed the problem of directed acyclic graph drawing into the problem of function optimization, then used genetic algorithm to find the approximate optimal solutions of the objective function. The experiment results show that the frames of the algorithms are unified, the method is simple, realizable, and it can be easily revised. It also has the following characters： self-adaptive, self-study and easily parallelized.

关 键 词：画图 边交叉的缩减 遗传算法 有向无环图 

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