進階搜尋


下載電子全文  
系統識別號 U0026-2408201616051800
論文名稱(中文) 多目標最佳化技術於不規則接鄰區域查詢
論文名稱(英文) Toward Optimal Search of Multi-Objective Region with Irregular Contour
校院名稱 成功大學
系所名稱(中) 資訊工程學系
系所名稱(英) Institute of Computer Science and Information Engineering
學年度 104
學期 2
出版年 105
研究生(中文) 許誠貿
研究生(英文) Cheng-Mao Hsu
學號 P76034282
學位類別 碩士
語文別 英文
論文頁數 34頁
口試委員 指導教授-莊坤達
口試委員-舒宇宸
口試委員-高宏宇
口試委員-李政德
口試委員-謝孫源
中文關鍵字 接鄰區域查詢  不規則區域查詢  多目標最佳化  變形蟲概念 
英文關鍵字 Geographic scope of the region  Irregular Region Search  Ameba-like Manipulation  Multi-Objective Optimization 
學科別分類
中文摘要 我們將探討如何在多限制與多目標下,查詢最佳之不規則的連續接鄰區域。在現今這類的地理範圍查詢已經成為一個重要的議題,很多實際應用例如城市規劃中之區域查詢,又或是生態保護區的設計、流行病爆發之區域防治決策等。以往的區域查詢之文獻很少探討到符合地理環境之不規則的區域查詢,在本篇論文中,我們新建構了一個不規則區域查詢的問題,也使這問題能夠解決在多目標的考慮下,查詢最佳的接鄰區域。之後,我們提出一個創新的概念叫變形蟲概念,它將非常適合用來設計這類問題的演算法,因此我們也根據此概念提出四種方法來解決不規則接鄰區域問題。最後,我們以流行病爆發之區域防治決策的應用作為實驗結果的呈現,我們所提出的四個方法將會在不同的參數設定下拿來互相比較,且在地理環境上的結果對去年的真實決策作評估。
英文摘要 The geographical scope of the search has been recognized as an important issue when governments need to arrange and construct their cities or environments. This searching skill can widely apply to facility location planning, wildlife preservation design, intervention strategies on outbreak diseases, etc. In the thesis, we design a geographic area search algorithm which is able to search part of irregular shapes with multi-objective optimizations. Afterwards, we propose an innovative manipulation called Ameba-like manipulation, which is relatively advisable for designing heuristic algorithms to traverse on large domain space. In addition, we proposed four algorithms based on the ameba-like manipulation for solving the geographical scope of the search problem. Finally, we demonstrate our experimental results with application of intervention strategies on outbreak diseases. The four proposed algorithms will eventually be compared together with different settings of parameters, and we will illustrate the geographic results compared to real decisions in the outbreak of Tainan dengue fever in 2015.
論文目次 中文摘要............................................ i
Abstract............................................. ii
Acknowledgment ........................................ iii
Contents............................................. iv
List of Figures ......................................... vi
1 Introduction......................................... 1
2 Preliminaries ........................................ 4
2.1 Related Works..................................... 4
2.2 SSB Partition..................................... 5
3 ORCS Problem Formulation ................................ 8
3.1 Problem Definition .................................. 8
3.2 Ameba-like Manipulation............................... 10
4 Evolutionary Optimization................................. 12
4.1 EMO.......................................... 12
4.2 AEMO Algorithm................................... 13
4.3 Time Complexity Analysis.............................. 17
5 Experimental Results.................................... 18
5.1 Two Objectives Optimization ............................ 19
5.2 Three Objectives Optimization ........................... 27
5.3 Executive Time.................................... 28
6 Conclusions ......................................... 31
Bibliography .......................................... 32
參考文獻 [1] A ́lvarez-Miranda, E., Ljubic ́, I., and Mutzel, P. The maximum weight connected subgraph problem. In Facets of Combinatorial Optimization. Springer, 2013, pp. 245–270.
[2] Branke, J., Deb, K., Miettinen, K., and Slowin ́ski, R. Multiobjective optimiza- tion: interactive and evolutionary approaches, vol. 5252. Springer, 2008.
[3] Brisaboa, N. R., De Bernardo, G., Konow, R., Navarro, G., and Seco, D. Aggregated 2d range queries on clustered points. Information Systems 60 (2016), 34–49.
[4] Burke, E. K., Kendall, G., et al. Search methodologies. Springer, 2005.
[5] Cheriyan, J., Vempala, S., and Vetta, A. Approximation algorithms for minimum- cost k-vertex connected subgraphs. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montr ́eal, Qu ́ebec, Canada (2002), pp. 306–312.
[6] Choi, D., Chung, C., and Tao, Y. A scalable algorithm for maximizing range sum in spatial databases. PVLDB 5, 11 (2012), 1088–1099.
[7] Deb, K., and Goel, T. Evolutionary multi-criterion optimization. Evolutionary algo- rithms in engineering and computer science (1999), 135–162.
[8] Dorigo, M., Birattari, M., Blum, C., Clerc, M., Stu ̈tzle, T., and Winfield, A. Ant Colony Optimization and Swarm Intelligence: 6th International Conference, ANTS 2008, Brussels, Belgium, September 22-24, 2008, Proceedings, vol. 5217. Springer, 2008.
[9] Dorigo, M., Birattari, M., and Stutzle, T. Ant colony optimization. IEEE computational intelligence magazine 1, 4 (2006), 28–39.
[10] Dorigo, M., and Stu ̈tzle, T. Ant colony optimization: overview and recent advances. Techreport, IRIDIA, Universite Libre de Bruxelles (2009).
[11] El-Kebir, M., and Klau, G. W. Solving the maximum-weight connected subgraph problem to optimality. CoRR abs/1409.5308 (2014).
[12] Frank, A. U. Spatial concepts, geometric data models, and geometric data structures. Computers & Geosciences 18, 4 (1992), 409–417.
[13] Goldschmidt, O., and Hochbaum, D. S. k-edge subgraph problems. Discrete Applied Mathematics 74, 2 (1997), 159–169.
[14] Guttman, A. R-trees: a dynamic index structure for spatial searching, vol. 14. ACM, 1984.
[15] Heendaliya, L., Wisely, M., Lin, D., Sarvestani, S. S., and Hurson, A. Influence-aware predictive density queries under road-network constraints. In Advances in Spatial and Temporal Databases. Springer, 2015, pp. 80–97.
[16] Hochbaum, D. S., and Pathria, A. Node-optimal connected k-subgraphs. manuscript, UC Berkeley (1994).
[17] Kortsarz, G., and Nutov, Z. Approximation algorithm for k-node connected sub- graphs via critical graphs. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (2004), ACM, pp. 138–145.
[18] Mamoulis, N. Spatial Data Management. Spatial Data Management. Morgan & Claypool Publishers, 2011.
[19] Manolopoulos, Y., Nanopoulos, A., Papadopoulos, A. N., and Theodoridis, Y. R-Trees: Theory and Applications. Advanced Information and Knowledge Processing. Springer, 2006.
[20] Minella, G., Ruiz, R., and Ciavotta, M. A review and evaluation of multiobjective algorithms for the flowshop scheduling problem. INFORMS Journal on Computing 20, 3 (2008), 451–471.
[21] Nandy, S. C., and Bhattacharya, B. B. A unified algorithm for finding maximum and minimum object enclosing rectangles and cuboids. Computers & Mathematics with Applications 29, 8 (1995), 45–61.
[22] Nievergelt, J., and Widmayer, P. Spatial data structures: Concepts and design choices. In Algorithmic foundations of geographic information systems. Springer, 1997, pp. 153–197.
[23] Osman, I. H., and Kelly, J. P. Meta-heuristics: an overview. In Meta-Heuristics. Springer, 1996, pp. 1–21.
[24] Phan, T.-K., Jung, H., and Kim, U.-M. An ecient algorithm for maximizing range sum queries in a road network. The Scientific World Journal 2014 (2014).
[25] Samet, H. The design and analysis of spatial data structures, vol. 199. Addison-Wesley Reading, MA, 1990.
[26] Sheng, C., and Tao, Y. New results on two-dimensional orthogonal range aggregation in external memory. In Proceedings of the thirtieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (2011), ACM, pp. 129–139.
[27] Tao, Y., Hu, X., Choi, D.-W., and Chung, C.-W. Approximate maxrs in spatial databases. Proceedings of the VLDB Endowment 6, 13 (2013), 1546–1557.
[28] Zheng, Y., Capra, L., Wolfson, O., and Yang, H. Urban computing: concepts, methodologies, and applications. ACM Transactions on Intelligent Systems and Technology (TIST) 5, 3 (2014), 38.
[29] Zheng, Y., Liu, Y., Yuan, J., and Xie, X. Urban computing with taxicabs. In Proceedings of the 13th international conference on Ubiquitous computing (2011), ACM, pp. 89–98.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2016-12-31起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2016-12-31起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw