族群基因繪圖演算法的改良

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：18

、訪客IP：3.144.109.5

姓名

鄭健台(Jian-Tai Zheng) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

族群基因繪圖演算法的改良
(Improvements of tribe geneatic drawing algorithm)

相關論文

★ 一種減輕LEO衛星網路干擾的方案	★ 萃取駕駛人在不同環境之駕駛行為方法
★ 非地面網路中基於位置的隨機接入分配方法	★ TrustFADE: 針對可程式化邏輯區塊之安全認證方法
★ 捷徑問題在特殊圖形上之演算研究	★ 行動電腦教室與其管理系統的設計與建置
★ 蛋白質體視覺化系統之實作	★ 最小切割樹群聚演算法極端情形之研究
★ 教室內應用無線科技之一對一數位學習模式	★ 蛋白質交互作用網路之視覺化系統
★ 以賓果式遊戲輔助技巧熟練之數位學習環境設計與實作	★ 蛋白質註解的三維視覺化工具
★ Joyce 2：一個在一對一數位教室環境下之小組競爭遊戲	★ 同儕計算網路上內文散佈演算法之實作與效能評估
★ 在直角多邊形上使用基因演算法畫樹之研究	★ 經由潛在語義的線索從蛋白質交互作用網路進行蛋白質功能的預測

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

在計算機科學中最常見到的資料結構便是圖形，圖形基本上是由節點和邊所組合而成。圖型結構往往隨著龐大的資料量而變的相當複雜，要如何透過電腦的輔助，才可以將複雜的圖形結構繪製成概念清楚的圖形。
在[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.

關鍵字(中)

★ 基因演算法
★ 繪圖演算法

關鍵字(英)

★ genetic algorithm
★ drawing algorithm

論文目次

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.

指導教授

何錦文(Chin-Wen Ho)

審核日期

2006-11-30

推文