(3.236.222.124) 您好!臺灣時間:2021/05/08 07:25
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:許誠貿
研究生(外文):Cheng-MaoHsu
論文名稱:多目標最佳化技術於不規則接鄰區域查詢
論文名稱(外文):Toward Optimal Search of Multi-Objective Region with Irregular Contour
指導教授:莊坤達莊坤達引用關係
指導教授(外文):Kun-Ta Chuang
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2016
畢業學年度:104
語文別:英文
論文頁數:34
中文關鍵詞:接鄰區域查詢不規則區域查詢多目標最佳化變形蟲概念
外文關鍵詞:Geographic scope of the regionIrregular Region SearchAmeba-like ManipulationMulti-Objective Optimization
相關次數:
  • 被引用被引用:0
  • 點閱點閱:55
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
我們將探討如何在多限制與多目標下,查詢最佳之不規則的連續接鄰區域。在現今這類的地理範圍查詢已經成為一個重要的議題,很多實際應用例如城市規劃中之區域查詢,又或是生態保護區的設計、流行病爆發之區域防治決策等。以往的區域查詢之文獻很少探討到符合地理環境之不規則的區域查詢,在本篇論文中,我們新建構了一個不規則區域查詢的問題,也使這問題能夠解決在多目標的考慮下,查詢最佳的接鄰區域。之後,我們提出一個創新的概念叫變形蟲概念,它將非常適合用來設計這類問題的演算法,因此我們也根據此概念提出四種方法來解決不規則接鄰區域問題。最後,我們以流行病爆發之區域防治決策的應用作為實驗結果的呈現,我們所提出的四個方法將會在不同的參數設定下拿來互相比較,且在地理環境上的結果對去年的真實決策作評估。
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.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
無相關期刊
 
無相關點閱論文
 
系統版面圖檔 系統版面圖檔