應用粒子群最佳化演算法設計資料倉儲與效能分析

Research of Applying Particle Swarm Optimization to Design Data Warehouse and Performance Analysis

郭光軒(Kuang-Hsuan Kuo)

指導教授 ： 陳凱瀛

國立臺北科技大學/管理學院/工業工程與管理系所/碩士(2006年)

摘要

由於傳統的資料庫和OLTP平台，是對於工商企業現行業務的自動化而設計的，目的在於協助工作人員執行既有的活動，所產生的資料都為詳細的交易資料，且不適合做為決策分析和各項整合應用。因此，我們必須透過對這些詳細的交易資料進行萃取、轉換和載入，依據使用者的需求，建構成資料倉儲或資料超市，以方便使用者可以透過線上分析處理系統(OLAP)，或是一些現有的分析軟體進行多維度的查詢、分析和決策。
　　在資料倉儲的建置上，為了能夠同時考量使用者查詢的速率，和建置所需的空間成本以及日後的更新維護成本，所以採用部分實體化的方式。因此，如何能夠挑選出適當的資料方體予以實體化，便是本研究主要的目的。
　　過去有學者以改良式的基因演算法(FGS+GA)，應用在設備管理系統的資料方體挑選，有鑒於粒子群演算法(PSO)，在求解的架構上近似於基因演算法，且由於此方法的演算步驟簡單，所需設計的變數和參數單純，往往在求解的效率上有不錯的表現。近年來PSO也開始被應用在TSP、多目標排程、作業指派問題等等的組合最佳化問題上，所以本研究提出改良式的PSO演算法和FGS+GA、BGS＋GA於設備管理系統所產生的相同資料庫環境下進行求解效率和求解品質的比較，最後透過挑選的結果，將較佳的資料方體予以實體化實際建構該系統的資料倉儲，並透過Analyzer 2004這套分析軟體，進行分析和應用。

關鍵字

粒子群最佳化演算法 ； 資料倉儲 ； 線上分析處理 ； 資料方體

並列摘要

Traditional database and Online Transaction Processing (OLTP) environment use database technology to transact and query data, and support the daily operational needs of the business enterprise. But data in traditional database is too detailed to analyze. Therefore, we have to extract、transform and load data into the Online Analytical Processing (OLAP) environment. OLAP environment use database technology to support analysis and mining of the data, and to provide decision makers with a platform for generating decision making information. Manager can also inquire and make decision by data mining tools or some other analytic softwares.
　　In this thesis, we design a data warehouse for Equipment Management System (EMS) to help the manager inquire and make decision by different dimension in a quickly and flexible way. For data cube selection, in order to minimize query time under the storage space limit, we adopt partial materialized way to select data cubes. In this thesis, we use three ways to select data cubes：FGS+PSO which incorporate particle swarm optimization with forward greedy algorithm, FGS+GA, which incorporate genetic algorithm with forward greedy algorithm and BGS+GA, which incorporates genetic algorithm with backward greedy algorithm. According to our experimental result, in case of most of storage constraint, the solution generated by FGS+PSO is as well as the solution generated by FGS+GA. Furthermore, when we compare the efficiency of the three ways, we find that the efficiency of FGS+PSO is superior to the others.
　　For performance anlysis, we compare the query time and space utilization of the selected cubes obtained by FGS+PSO with all materialized way. According to our experimental result, FGS+PSO can reduce 70% of storage space, and the query time of FGS+PSO is as well as all materialized way.

並列關鍵字

Particle Swarm Optimization ； Data Warehouse ； Equipment Management System ； On-Line Analytical Processing (OLAP) ； DataCube

參考文獻

[22] 沈育樹，宮大川，「整合性維護管理系統設計」,工業工程學刊,第20輯,第337－354頁，2003。

[31] 劉文義，應用基因演算法設計資料倉儲與效能分析，碩士論文，國立台北科技大學工業工程與管理研究所，台北，2005。

[2] Clerc, M. “The swarm and the queen: towards a deterministic and adaptive

[3] C.I. Ezeife, “A uniform approach for selecting views and indexes in a data warehouse,” International Database Engineering and Applications Symposium, 1997, pp. 151-160.

[4] Chunkai Zhang; uihe Shao;Yu Li; “Particle swarm optimization for evolving artificial neural network , ”Systems ,Man , and Cybernetics , 2000 IEEE International Conference on Volume 4 , 8-11 Oct. 2000 Page(s):2487-2490 vo1.4.