(35.175.120.174) 您好!臺灣時間:2019/11/19 19:20
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
本論文永久網址: 
line
研究生:謝垂燊
研究生(外文):Chui-Shen Hsieh
論文名稱:在直角多邊形上使用基因演算法畫樹之研究
指導教授:何錦文高明達高明達引用關係
學位類別:碩士
校院名稱:國立中央大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文出版年:2005
畢業學年度:93
語文別:中文
論文頁數:66
相關次數:
  • 被引用被引用:1
  • 點閱點閱:123
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:8
  • 收藏至我的研究室書目清單書目收藏:0
論文提要及內容:
一個圖形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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔