基于遗传算法的平面图平面正交直线画图算法  

Planar orthogonal straight-line drawing algorithm of planar graph based on genetic algorithm

作　　者：张清国[1] 金聪[1] 林春 

机构地区：[1]华中师范大学计算机系,湖北武汉430079 [2]广州金鹏集团有限公司,广东广州510665

出　　处：《计算机工程与设计》2005年第2期467-469,共3页Computer Engineering and Design

摘　　要：提出了一种基于遗传算法的新的平面图平面正交直线画图算法,算法将平面图画图问题转化为约束优化问题,根据画图问题选定的美观准则构造约束函数,用遗传算法求解目标函数的最优解的近似值,从而得到平面图的平面正交直线画法。新算法的优点是方法简单,易于实现,画出的图形美观,算法稳定性好。实验结果表明,画图算法的最终结果不依赖于图的初始状态。A new planar graph planar orthogonal straight-line drawing algorithm is proposed which is based on genetic algorithm. The algorithm transforms the problem of planar graph drawing to that of constraint optimization, and constructs a function with constraints according to the aesthetic criteria of graph drawing problem, and then uses genetic algorithms to find approximate optimal solutions to the objective function, and thus obtains a planar orthogonal straight-line drawing of the planar graph. The new algorithm is of following advantages: the method is simple and it is easier to be implemented and also the figure drawn is beautiful, finally, the algorithm is stable. The experiment results show that the final results of the drawing algorithm don't rely on the initial status of graphs.

关 键 词：线画图 遗传算法 图算法 平面图 新算法 算法稳定性 正交 直线 问题转化 近似值 

分 类 号：TP391[自动化与计算机技术—计算机应用技术] G633[自动化与计算机技术—计算机科学与技术]