臺灣博碩士論文加值系統

在計算機科學中最常見到的資料結構便是圖形，圖形基本上是由節點和邊所組合而成。圖型結構往往隨著龐大的資料量而變的相當複雜，要如何透過電腦的輔助，才可以將複雜的圖形結構繪製成概念清楚的圖形。
在[Hsieh05]中，對於二維空間上直角多邊形內繪製樹狀圖的問題，提出一個以基因演算法為基礎的樹狀圖繪製演算法，透過階層式的繪製方式，將樹狀圖收縮後再逐層展開來做繪製。
然而[Hsieh05]所設計的繪圖演算法存在不少的缺點，當遇到結構龐大的樹狀圖執行時間過長，突變和交配運算的設計不夠恰當，且美學規則設計並不能明確地挑出較佳的樹狀圖。此篇論文，主要是針對[Hsieh05]所提出的繪圖演算法作改良，我們藉由物種初始狀態的改良來幫助改善過長的執行時間，且提出新的交配和突變方式，並在美學規則加入新的概念。

The data structure seen most frequently in the computer science is graph, and the graph is composed of nodes and edges. The graph often becomes complicated with a large number of data, so we must change the complicated graph into the graph that is clear and easy to understand by using computer.
In the [Hsieh05], it provides a drawing algorithm which is based on the genetic algorithm to draw a tree in the rectilinear polygon on the two-dimentional space. By using Hierarchical layout, the drawing algorithm contracts a tree and expands it hierarchically.
However, the drawing algorithm has many disadvantages. It spends a lot of time drawing a complicated tree; designs for crossover and mutation are not good enough, and aesthetic criteria can’t pick out a proper tree. This paper focuses on improving the drawing algorithm. We improve the initial state of species to prevent lasting execution time, provide new designs for crossover and mutation, and join a new concept in aesthetic criteria.

I
目錄
目錄........................................................... I
圖目錄....................................................... III
表目錄........................................................ VI
第一章緒論.................................................... 1
第二章圖形繪製相關研究........................................ 7
2.1 力導向模型................................................7
2.1.1 彈簧嵌入演算法........................................8
2.1.2 Fruchterman 及Reingold 的演算法.....................10
2.2 最佳化問題模型...........................................13
第三章族群基因繪圖演算法..................................... 15
3.1 基因演算法之簡介.........................................15
3.2 族群基因繪圖演算法.......................................18
3.2.1 階層式的繪製方式.....................................18
3.2.2 族群的概念...........................................19
3.2.3 基因演算法的設計.....................................20
第四章族群基因繪圖演算法的改良............................... 27
4.1 美學規則的改良...........................................27
4.1.1 實驗結果比較.........................................33
4.2 物種初始狀態的改良.......................................39
4.2.1 實驗結果比較.........................................41
4.3 基因運算的改良...........................................43
4.3.1 交配運算的改良.......................................43
4.3.2 突變運算的改良.......................................46
4.3.3 實驗結果比較.........................................48
第五章實驗結果與討論......................................... 54
5.1 演算法執行效能比較.......................................54
5.2 圖形繪製結果.............................................58
第六章結論與未來工作......................................... 73
參考文獻...................................................... 75

[BaRa02] A. Bagheri and M. Razzazi. “Drawing Free Trees Inside
Rectilinear polygons Using Straight Skeleton,” 18th European Workshop on Computational Geometry, pp. 17-32, 2002.
[BaBa00] A. M.S. Barreto and H. J.C. Barbosa. “Graph Layout Using a Genetic Algorithm,” Neural Network 2000 Proceedings, pp.179-184.
[BrBS97] J. Branke, F. Bucher, and H. Schmeck. “Using Genetic
Algorithms for Drawing Undirected Graphs,” Proceedings of the Third Nordic Workshop on Genetic Algorithm and their
Applications, pp. 193-205, 1997.
[CaHK04] L. Carmel, D. Harel, and Y. Koren. “Combining Hierarchy and Energy for Drawing Directed Graphs,” IEEE Transactions on Visualization and Computer Graphics, Vol. 10, No.1, pp. 46-57,2004.
[DaHa96] R. Davidson and D. Harel. “Drawing Graphs Nicely Using
Simulated Annealing,” ACM Transactions on Graphs, Vol. 15,No. 4, pp. 301-331, 1996.
[Eade84] P. Eades. “A Heuristic for Graph Drawing”. Congressus
Numerantium, Vol. 42, pp. 149-160, 1984
[Elor01] T. Eloranta. “TimGA: A Genetic Algorithm for Drawing
Undirected Graphs,” Divulagciones Matematicas, Vol. 9 , No. 2,pp. 155-171, 2001.
[FrRe91] T. Fruchterman and E. Reingold. “Graph drawing by
force-directed placement,” Software-Practice and Experience,Vol. 21, Issue 11, pp. 1129-1164, 1991.
[HaHa99] R. Hadany and D. Harel. “A Multi-Scale Algorithm for
Drawing Graphs Nicely,” Proceedings of the 25th International Workshop on Graph-Theoretic Concepts in Computer Science,pp. 262-277, 1999.
[HaKo02] D. Harel and Y. Koren. “A Fast Multi-Scale Method for
Drawing Large Graphs,” Journal of Graph Algorithms and
Applications, Vol. 6, No. 3, pp. 179-202, 2002.
[Holl75] J.H. Holland. “Adaption in Natural and Artificial Systems,” The University Michigan Press, pp. 37-40, 1975.
[Hsieh05] 謝垂燊, “在直角多邊形上使用基因演算法畫樹之研究” 國立中央大學資訊工程研究所碩士論文, 2005.
[JrBr79] N. R. Quinn Jr. and M. A. Breuer. “A forced directed
component placement procedure for printed circuit boards,”IEEE Transactions on Circuits and Systems, Vol. 26, pp.377-388, 1979.
[KaKa89] T. Kamada and S. Kawai. “An Algorithm for Drawing General
Undirected Graph,” Information Letters, Vol. 31, No. 1, pp.7-15, 1989.
[Lin04] 林俊吉, “蛋白質交互作用網路之視覺化工具,” 國立中央大
學資訊工程研究所碩士論文, 2004
[WaCY02] J. Wan-Rong, K. Cheng-Yen, and H. Yung-Jen. “Using Family
Competition Genetic Algorithm in Pickup and Delivery
Problem with Time Window Constraints,” Proceedings of the 2002 IEEE International Symposium on Intelligent Control
Vancouver, pp.27-30, 2002.
[WaPN05] Wanchun Li, Peter Eades, Nikola Nikolov. “Using spring algorithms to remove node overlapping,” proceedings of the 2005 Asia-Pacific symposium on Information visualization, Volume 45 CRPIT ''05, 2005.
[XiWe03] Xiaodi Huang, Wei Lai. “Force-transfer: a new approach to removing overlapping nodes in graph layout,” Proceedings of the twenty-sixth Australasian computer science conference on Conference in research and practice in information technology, Volume 16 CRIPTS ''03, 2003.