# 臺灣博碩士論文加值系統

(44.192.49.72) 您好！臺灣時間：2024/09/19 22:23

:::

### 詳目顯示

:

• 被引用:1
• 點閱:198
• 評分:
• 下載:9
• 書目收藏:1
 在計算機科學中最常見到的資料結構便是圖形，圖形基本上是由節點和邊所組合而成。圖型結構往往隨著龐大的資料量而變的相當複雜，要如何透過電腦的輔助，才可以將複雜的圖形結構繪製成概念清楚的圖形。在[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第二章圖形繪製相關研究........................................ 72.1 力導向模型................................................72.1.1 彈簧嵌入演算法........................................82.1.2 Fruchterman 及Reingold 的演算法.....................102.2 最佳化問題模型...........................................13第三章族群基因繪圖演算法..................................... 153.1 基因演算法之簡介.........................................153.2 族群基因繪圖演算法.......................................183.2.1 階層式的繪製方式.....................................183.2.2 族群的概念...........................................193.2.3 基因演算法的設計.....................................20第四章族群基因繪圖演算法的改良............................... 274.1 美學規則的改良...........................................274.1.1 實驗結果比較.........................................334.2 物種初始狀態的改良.......................................394.2.1 實驗結果比較.........................................414.3 基因運算的改良...........................................434.3.1 交配運算的改良.......................................434.3.2 突變運算的改良.......................................464.3.3 實驗結果比較.........................................48第五章實驗結果與討論......................................... 545.1 演算法執行效能比較.......................................545.2 圖形繪製結果.............................................58第六章結論與未來工作......................................... 73參考文獻...................................................... 75
 [BaRa02] A. Bagheri and M. Razzazi. “Drawing Free Trees InsideRectilinear 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 GeneticAlgorithms for Drawing Undirected Graphs,” Proceedings of the Third Nordic Workshop on Genetic Algorithm and theirApplications, 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 UsingSimulated Annealing,” ACM Transactions on Graphs, Vol. 15,No. 4, pp. 301-331, 1996.[Eade84] P. Eades. “A Heuristic for Graph Drawing”. CongressusNumerantium, Vol. 42, pp. 149-160, 1984[Elor01] T. Eloranta. “TimGA: A Genetic Algorithm for DrawingUndirected Graphs,” Divulagciones Matematicas, Vol. 9 , No. 2,pp. 155-171, 2001.[FrRe91] T. Fruchterman and E. Reingold. “Graph drawing byforce-directed placement,” Software-Practice and Experience,Vol. 21, Issue 11, pp. 1129-1164, 1991.[HaHa99] R. Hadany and D. Harel. “A Multi-Scale Algorithm forDrawing 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 forDrawing Large Graphs,” Journal of Graph Algorithms andApplications, 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 directedcomponent 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 GeneralUndirected 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 FamilyCompetition Genetic Algorithm in Pickup and DeliveryProblem with Time Window Constraints,” Proceedings of the 2002 IEEE International Symposium on Intelligent ControlVancouver, 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.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 在直角多邊形上使用基因演算法畫樹之研究 2 應用防火牆日誌資料視覺化分析網路行為

 無相關期刊

 1 A Study on the Minimum Area of Rectilinear Polygons Realized by Turn Sequences 2 在多核心電腦上實作偵測k-clique community之平行演算法 3 改良中介性相關計算之研究 4 行動科技對經驗學習之支援性 5 設計與實做一對一數位教室環境與元件交換社群 6 快速5G下行傳輸方法 7 CLW-LTE:在未授權的頻譜中LTE與WiFi之間的公平共存 8 基於等價路徑與靜態路由產生的負載平衡系統 9 距離繼承圖上的最長路徑問題 10 從蛋白質交互作用網絡中偵測必要性蛋白質與蛋白質功能模組 11 利用蛋白質交互作用網路偵測必要性蛋白質 12 經由潛在語義的線索從蛋白質交互作用網路進行蛋白質功能的預測 13 從生物文件中萃取出蛋白質或基因之名稱 14 在直角多邊形上使用基因演算法畫樹之研究 15 同儕計算網路上內文散佈演算法之實作與效能評估

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室