一个求解层次图边交叉数最小化问题的遗传算法  

A genetic algorithm for hierarchical graph edge crossing minimization problem

作　　者：吕启斌[1] 黄竞伟[1] 

机构地区：[1]武汉大学计算机学院,湖北武汉430072

出　　处：《计算机工程与设计》2003年第5期91-93,96,共4页Computer Engineering and Design

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

摘　　要：最小化边交叉数是层次图绘制过程中的一个关键步骤,直接影响着层次图的可读性。提出了一个基于 遗传算法的层次图边交叉数最小化算法,详细地给出了编码表示方法以及遗传算子的设计。与常用的启发算法 相比,该算法得到了更好的计算结果,此外算法简单且易于实现。Minimizing edge crossing is a key problem in drawing layered digraphs, and it's directly involved with the readability of the graph. An edge crossing minimization algorithm for layered digraphs based on genetic algorithms is present in this article, the code method and the genetic operator are given detailedly. The algorithm is more efficient while comparing it with some heuristic algorithms, and it's simple and easy to implement.

关 键 词：层次图 边交叉数最小化问题 遗传算法 遗传算子 NP问题 启发式算法 

分 类 号：O224[理学—运筹学与控制论] O242.23[理学—数学]