臺灣博碩士論文加值系統

近年來巨量資料已經成為了重要的研究課題，主要原因如以下特性：快速的即時資料變動、複雜的分散式資料來源、異質性資料的整合、以及資料量的快速成長，然而，在此複雜的巨量資料環境中，要達到有效率且準確的預測，是一個新的挑戰。動態資料驅動應用系統(Dynamic Data-Driven Application System, DDDAS)的概念是一種解決的方法，可提供模擬分析和預測的能力，並進一步擴展相關的應用模型。在DDDAS的概念中，找出資料的關聯性是重要的一環，即時的找出資料間資料驅動的相關性，是加強DDDAS框架效率的方法。在過去演化式演算法已被廣泛應用在規則啟發，已證明可以有效的解決在實際應用中最佳化的問題，但隨著資訊的快速發展和巨量資料的出現，這些問題的規模和複雜性持續擴大，傳統的演化式演算法，無法在合理的時間內給予答案。叢集運算是一種合作的平行運算架構，透過網路的整合，結合平行運算、高性能、分散式以及高可用性的能力，此運算框架可以用來解決在動態資料驅動概念下，演化式演算法在動態運算與資源分配上的需求。本研究將提出一個基於演化式演算法與叢集運算的動態資料驅動預測模型，在此模型中，將加入動態資料驅動應用系統的概念，基於叢集運算的架構，以分散式的演化式演算法來建置模型，在一個資料會隨時間變動的動態環境下，即時的找出預測目標與動態資料來源之間的資料關聯，並做出有效率且準確的預測。

In recent years, big data has become an important research topic. Such as the main reason for the following characteristics: high velocity in real-time data, distributed of complex data sources, integration of heterogeneous data and growth of data volumes. Therefore, in this complex information environment. It is a new challenge to achieve an efficient and accurate prediction. The concept of dynamic data-driven applications system (DDDAS) is a solution, to provide simulation and prediction capabilities, and expansion of the relevant application model. In the DDDAS framework, to find out the relationship between data instantly can help to improve the efficiency of DDDAS. In the past, the evolutionary algorithms have been widely used, it has been proven to be effective in solving the practical applications of optimization problems. But, with the advent of the rapid development of information and the big data. The size and complexity of these issues continues to expand. The traditional evolutionary algorithms can’t give a satisfactory answer within a reasonable time. Cluster computing is a parallel computing architecture. It combined with parallel computing, high-performance, distributed, and high availability capabilities through the network integration. In a dynamic data-driven concept. This architecture can be used to solve the operation with evolutionary algorithms on dynamic computing and dynamic resource allocation. In this study. We propose a dynamic data driven prediction model based on evolutionary algorithms and cluster computing. In this model, it will be added to the concept of dynamic data-driven application system. In a dynamic data environment, build a distributed evolutionary algorithms base on cluster computing architecture. To find out the relationship between the dynamic data and prediction target in time and make an efficient and accurate predictions.

摘要 I
Abstract II
目錄 IV
圖目錄 VI
表目錄 VII
第一章、緒論 1
1.1研究背景與動機 1
1.2研究問題 3
1.3研究目的 3
1.4預期研究貢獻 3
第二章、文獻探討 4
2.1動態資料驅動應用系統 4
2.1.1動態資料驅動應用系統架構 5
2.1.2動態資料驅動之資料關聯 6
2.2叢集運算 7
2.2.1Hadoop 8
2.2.2MapReduce 9
2.2.3HDFS 10
2.2.4Spark 11
2.3機器學習方法 12
2.3.1線性迴歸(linear regression) 13
2.4演化式演算法(evolutionary algorithms) 15
2.4.1遺傳演算法(genetic algorithms) 15
2.4.2演化式策略(evolutionary strategy) 15
2.4.3演化式規劃(evolutionary programming) 16
第三章、研究方法 19
3.1研究架構 19
3.2演化式演算法設計 20
3.3適應函數 23
3.4動態驅動預測策略 24
3.5預測方法 25
3.6結果評估 26
第四章、實驗與結果 27
4.1實驗設計 27
4.2評估方式 29
4.3實驗流程 29
4.4實驗結果 36
第五章、結論與建議 44
5.1研究貢獻 44
5.2未來展望與建議 44
參考文獻 45

圖2 - 1動態資料驅動應用系統架構 5
圖2 - 2 Hadoop系統架構圖 9
圖2 - 3 MapReduce運算框架 10
圖2 - 4 HDFS架構示意圖 11
圖2 - 5機器學習分類 13
圖2 - 6簡單線性迴歸示意圖 14
圖2 - 7分散式的演化運算框架示意圖 18
圖3 - 1研究架構 20
圖3 - 2染色體示意圖 21
圖3 - 3染色體交配示意圖1 22
圖3 - 4染色體交配示意圖2 22
圖3 - 5染色體突變示意圖 23
圖3 - 6線性迴歸示意圖 25
圖4 - 1系統架構圖 28
圖4 - 2資料範圍示意圖 31
圖4 - 3三種預測模式比較(500) 37
圖4 - 4動態預測比較(500) 38
圖4 - 5三種模式比較(100) 38
圖4 - 6動態預測比較(100) 39
圖4 - 7三種模式比較(50) 40
圖4 - 8動態預測比較(50) 40
圖4 - 9三種模式比較(10) 41
圖4 - 10動態預測比較(10) 42
圖4 - 11動態演化式演算法比較 42
圖4 - 12動態預測比較 43

表2 - 1 DDDAS各領域應用 6
表2 - 2 Spark相關演算法 12
表2 - 3演化式演算法比較 17
表4 - 1樣本資料 30
表4 - 2資料處理示意圖 30
表4 - 3初始族群示意圖 32
表4 - 4模型預測示意圖1 32
表4 - 5模型預測示意圖2 33
表4 - 6模型預測示意圖3 34
表4 - 7模型預測示意圖4 35
表4 - 8平均MSE 36

Abraham, A. J., Kumar, K. R., Sridharan, R., & Singh, D. (2015). A Genetic Algorithm Approach for Integrated Production and Distribution Problem. Procedia - Social and Behavioral Sciences, 189, 184–192.
Antoniou, C., Koutsopoulos, H. N., & Yannis, G. (2013). Dynamic data-driven local traffic state estimation and prediction. Transportation Research Part C: Emerging Technologies, 34, 89–107.
Aydin, S., & Bay, O. F. (2009). Building a high performance computing clusters to use in computing course applications. Procedia - Social and Behavioral Sciences, 1(1), 2396–2401.
Azimi, M., & Zhang, Y. (2010). Categorizing freeway flow conditions by using clustering methods. Transportation Research Record: Journal of the Transportation Research Board, (2173), 105–114.
Bäck, T. (2002). Adaptive business intelligence based on evolution strategies: some application examples of self-adaptive software. Information Sciences, 148(1–4), 113–121.
Beyer, H.-G., & Schwefel, H.-P. (2002). Evolution strategies–A comprehensive introduction. Natural Computing, 1(1), 3–52.
Darema, F. (2004). Dynamic data driven applications systems: A new paradigm for application simulations and measurements. In Computational Science-ICCS 2004 (pp. 662–669). Springer. Retrieved from
Darema, F. (2005). Dynamic data driven applications systems: New capabilities for application simulations and measurements. In Computational Science–ICCS 2005 (pp. 610–615). Springer.
Darema, F. (2007). Introduction to the ICCS 2007 workshop on dynamic data driven applications systems. In Computational Science–ICCS 2007 (pp. 955–962). Springer.
Dean, J., & Ghemawat, S. (2008). MapReduce: simplified data processing on large clusters. Communications of the ACM, 51(1), 107–113.
Douglas, C. C., & Efendiev, Y. (2006). A dynamic data-driven application simulation framework for contaminant transport problems. Computers & Mathematics with Applications, 51(11), 1633–1646.
Douglas, C. C., Loader, R. A., Beezley, J. D., Mandel, J., Ewing, R. E., Efendiev, Y., … others. (2006). DDDAS approaches to wildland fire modeling and contaminant tracking. In Simulation Conference, 2006. WSC 06. Proceedings of the Winter (pp. 2117–2124). IEEE.
Fujimoto, R., Guin, A., Hunter, M., Park, H., Kanitkar, G., Kannan, R., … Pecher, P. (2014). A Dynamic Data Driven Application System for Vehicle Tracking. Procedia Computer Science, 29, 1203–1215. http://doi.org/10.1016/j.procs.2014.05.108
Fumo, N., & Rafe Biswas, M. A. (2015). Regression analysis for prediction of residential energy consumption. Renewable and Sustainable Energy Reviews, 47, 332–343.
Gagné, C., Beaulieu, J., Parizeau, M., & Thibault, S. (2008). Human-competitive lens system design with evolution strategies. Applied Soft Computing, 8(4), 1439–1452.
Ghazi, M. R., & Gangodkar, D. (2015). Hadoop, MapReduce and HDFS: A Developers Perspective. Procedia Computer Science, 48, 45–50.
Gong, Y.-J., Chen, W.-N., Zhan, Z.-H., Zhang, J., Li, Y., Zhang, Q., & Li, J.-J. (2015). Distributed evolutionary algorithms and their models: A survey of the state-of-the-art. Applied Soft Computing, 34, 286–300.
Gupta, A. K., & Greenwood, G. W. (1996). Static task allocation using (μ, λ) evolutionary strategies. Information Sciences, 94(1–4), 141–150.
Hand, D. J. (2009). Mining the past to determine the future: Problems and possibilities. International Journal of Forecasting, 25(3), 441–451.
HDFS Architecture Guide. (n.d.). Retrieved January 18, 2016, from https://hadoop.apache.org/docs/r1.2.1/hdfs_design.html
Hu, Y., Liu, K., Zhang, X., Su, L., Ngai, E. W. T., & Liu, M. (2015). Application of evolutionary computation for rule discovery in stock algorithmic trading: A literature review. Applied Soft Computing, 36, 534–551.
Jian, F., & Yugeng, X. (1997). Neural network design based on evolutionary programming. Artificial Intelligence in Engineering, 11(2), 155–161.
Jian-Xin, X. U., & Zhong-Sheng, H. (2009). Notes on data-driven system approaches. Acta Automatica Sinica, 35(6), 668–675.
Kacfah Emani, C., Cullot, N., & Nicolle, C. (2015). Understandable Big Data: A survey. Computer Science Review, 17, 70–81.
Keco, D., & Subasi, A. (2012). Parallelization of genetic algorithms using Hadoop Map/Reduce.
Lin, S.-Y. (2014). Reinforcement learning-based prediction approach for distributed Dynamic Data-Driven Application Systems. Information Technology and Management, 1–14.
Lin, S.-Y., Chao, K.-M., Lo, C.-C., & Godwin, N. (2013). Distributed dynamic data driven prediction based on reinforcement learning approach. In Proceedings of the 28th Annual ACM Symposium on Applied Computing (pp. 779–784). ACM.
Loshin, D. (2013). Chapter 7 - Big Data Tools and Techniques. In D. Loshin (Ed.), Big Data Analytics (pp. 61–72). Boston: Morgan Kaufmann.
Ouyang, Y., Zhang, J. E., & Luo, S. M. (2007). Dynamic data driven application system: Recent development and future perspective. Ecological Modelling, 204(1–2), 1–8.
Parashar, M., Klie, H., Catalyurek, U., Kurc, T., Matossian, V., Saltz, J., & Wheeler, M. F. (2004). Application of grid-enabled technologies for solving optimization problems in data-driven reservoir studies. In Computational Science-ICCS 2004 (pp. 805–812). Springer.
Patrikalakis, N. M., McCarthy, J. J., Robinson, A. R., Schmidt, H., Evangelinos, C., Haley, P. J., … others. (2004). Towards a dynamic data driven system for rapid adaptive interdisciplinary ocean forecasting. Dynamic Data-Driven Application Systems. Kluwer Academic Publishers, Amsterdam.
Silva, D. A., Silva, J. P., & Rocha Neto, A. R. (2015). Novel approaches using evolutionary computation for sparse least square support vector machines. Neurocomputing, 168, 908–916.
Sterling, T. (2003). Cluster Computing. In R. A. Meyers (Ed.), Encyclopedia of Physical Science and Technology (Third Edition) (pp. 33–43). New York: Academic Press.
Uysal, A. K., & Gunal, S. (2014). Text classification using genetic algorithm oriented latent semantic features. Expert Systems with Applications, 41(13), 5938–5947.
Verma, A., Llora, X., Goldberg, D. E., & Campbell, R. H. (2009). Scaling genetic algorithms using mapreduce. In Intelligent Systems Design and Applications, 2009. ISDA’09. Ninth International Conference on (pp. 13–18). IEEE.
Zaharia, M., Chowdhury, M., Franklin, M. J., Shenker, S., & Stoica, I. (2010). Spark: cluster computing with working sets. In Proceedings of the 2nd USENIX conference on Hot topics in cloud computing (Vol. 10, p. 10).
Zhao, H., Knight, D., Taskinoglu, E., & Jovanovic, V. (2004). Data driven design optimization methodology development and application. Springer.
張雅芳. (2012). 利用 MapReduce 實作分散式協同推薦系統. 清華大學資訊工程學系學位論文, 1–66.
林豐澤. (2005). 演化式計算上篇: 演化式演算法的三種理論模式. 智慧科技與應用統計學報, 3(1), 1–28.
陳稼興, 謝佳倫, & 許芳誠. (2000). 以遺傳演算法為基礎的中文斷詞研究. 資訊管理研究, 2(2), 27–44.