摘要
本文提出了一个新的画一般无向图的遗传算法。以前的无向图画图算法将顶点数较多且无弦的圈画成了凹多边形,为了克服这一缺点,本文的遗传算法设计了全新的变异算子——单点邻域变异,并在适应度函数中增加用于产生对称画法的分量,可将这种图画成凸多边形。新算法的优点是方法简单,易于实现,画出的图形美观,其灵活之处在于准则的权重可以改变。实验结果表明,在相同条件下,本文算法画出的图形要比标准遗传算法画出的图形美观。
This paper proposes a new genetic algorithm for drawing general undirected graphs nicely. Previous undirected graph drawing algorithms draw large cycles with no chords as concave polygons. In order to overcome such disadvantages, the genetic algorithm in this paper designs a new mutation operator called singlenodeneighborhood mutation, and adds a component aiming at symmetric drawings to the fitness function, and it can draw such type of graphs as convex polygons. The new algorithm has the following advantages： It is simple and easy to be implemented, and the figures drawn by the algorithm are beautiful, and also it is flexible in that the relative weights of the criteria can be changed. The experiment results show that the figures drawn by our algorithm are more beautiful than that of simple genetic algorithms under the same conditions.
出处
《计算机工程与科学》
CSCD
2006年第6期58-61,共4页
Computer Engineering & Science
关键词
遗传算法
无向图
画图
美学标准
genetic algorithm
undirected graph
graph drawing
aesthetic criteria
