在直角多邊形上使用基因演算法畫樹之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：49

、訪客IP：3.135.195.91

姓名

謝垂燊(Chui-Shen Hsieh) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

在直角多邊形上使用基因演算法畫樹之研究

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

論文提要及內容：
一個圖形G(V, E)描述一個點集合V上的二元關係E，為一抽象的資料結構。圖形配置即是將圖形繪製在空間中，讓人們實際的觀察到此圖形的樣貌。而一個圖形配置的好壞取決於其可讀性，換句話說即能否把圖形所擁有的結構特性清晰地呈現出來。
一般的繪圖演算法多為在無限制區域的二維或三維空間上產生圖形配置，但在某些情況下，我們會碰到只能在某個限定的不規則區塊上繪圖。例如想在VLSI既有的電路上加入新的電路。此時使用一般的繪圖演算法是無法處理的。
在此論文，我們探討在給定二維空間上直角多邊形內繪製樹狀圖問題，提出一個以基因演算法為基礎的樹狀圖繪製演算法，並且結合階層式繪製的方式，將樹狀圖收縮後再逐層展開來做繪製。此演算法在處理300點以下的樹狀圖時已經有不錯的成效。

論文目次

目錄.........................................................................I
圖目錄.....................................................................III
表目錄.......................................................................V
第一章緒論................................................................1
第二章圖形繪製之相關研究..................................................6
2.1 在無限制配置空間上的演算法..............................................6
2.1.1 力導向演算法..........................................................7
2.1.1.1 彈簧嵌入演算法......................................................7
2.1.1.2 Kamada及Kawai的演算法...............................................8
2.1.2 模擬降溫演算法.........................................................9
2.1.3 基因演算法............................................................11
2.2 在限制配置空間上的演算法...............................................12
第三章基因演算法之簡介...................................................15
第四章繪圖演算法設計.....................................................20
4.1 階層式繪製.............................................................21
4.2 基因演算法之設計.......................................................24
4.2.1 物種的參數解編碼及初始化.............................................26
4.2.2 美學規則與適應值函數.................................................26
4.2.3 基因運算.............................................................32
4.2.4 終止條件.............................................................36
4.2.5 微調.................................................................36
4.3 族群基因演算法.........................................................36
第五章結果與討論.........................................................39
5.1 參數值設定..............................................................39
5.2 結果與比較..............................................................48
第六章結論與未來工作.....................................................60
參考文獻....................................................................64

參考文獻

[AiAu96] O. Aichholzer and F. Aurenhammer. "Straight Skeletons for General Polygonal Figures in the Plane," Proc. 2nd Ann. Int. Conf. Computing and Combinatorics, Lecture Notes in Computer Science 1090, pp. 117-126, 1996.
[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.
[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.

指導教授

何錦文、高明達
(Chin-Wen Ho、Ming-Tat Ko)

審核日期

2005-7-18

推文