首页 | 本学科首页   官方微博 | 高级检索  
     

用遗传算法画无向图
引用本文:张清国,叶俊民,张维,张连发. 用遗传算法画无向图[J]. 计算机工程与科学, 2006, 28(6): 58-61
作者姓名:张清国  叶俊民  张维  张连发
作者单位:华中师范大学计算机系,湖北,武汉,430079
摘    要:本文提出了一个新的画一般无向图的遗传算法.以前的无向图画图算法将顶点数较多且无弦的圈画成了凹多边形,为了克服这一缺点,本文的遗传算法设计了全新的变异算子--单点邻域变异,并在适应度函数中增加用于产生对称画法的分量,可将这种图画成凸多边形.新算法的优点是方法简单,易于实现,画出的图形美观,其灵活之处在于准则的权重可以改变.实验结果表明,在相同条件下,本文算法画出的图形要比标准遗传算法画出的图形美观.

关 键 词:遗传算法 无向图 画图 美学标准
文章编号:1007-130X(2006)06-0058-04
修稿时间:2004-12-03

Drawing Undirected Graphs with Genetic Algorithms
ZHANG Qing-guo,YE Jun-min,ZHANG Wei,ZHANG Lian-fa. Drawing Undirected Graphs with Genetic Algorithms[J]. Computer Engineering & Science, 2006, 28(6): 58-61
Authors:ZHANG Qing-guo  YE Jun-min  ZHANG Wei  ZHANG Lian-fa
Abstract: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 single-node-neighborhood 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.
Keywords:genetic algorithm  undirected graph  graph drawing  aesthetic criteria
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《计算机工程与科学》浏览原始摘要信息
点击此处可从《计算机工程与科学》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号