詢問式學習改良粒子群演算法於綠能計算之研究

Query-based Learning Particle Swarm Optimization Algorithm for Green Computing

林書宇(Lin Shu-Yu)

指導教授 ： 張瑞益

國立臺灣大學/工學院/工程科學及海洋工程學研究所/博士(2015年)

https://doi.org/10.6342/NTU.2015.00916

摘要

粒子群演算法是近年來群體智能中相當熱門的議題，也因此有許多的學者針對粒子群演算法進行研究與改良。然而即使經過長久的開發，粒子群演算法仍然存在一些可能性陷入局部最佳解。本論文導入詢問式學習改善粒子群演算法，不僅是提高粒子群的全區域最佳解探索能力，同時也提高小區域的最佳解搜索能力。論文當中介紹兩種詢問式學習機制啟動的方式，QP-CR和QP-SR。其應用的方法是基於過去我們對於詢問式學習應用在類神經網路、自我組織圖、粒子群演算法等概念。進而提出一種新的詢問式學習改良的粒子群演算法。同時該演算法透過在最佳化演算法研究採用的測試方程式進行效能驗證，我們更進一步採用綠能計算應用來進行驗證。兩個綠能計算應用分別是：契約用電最佳化研究以及雲端計算虛擬機器布置研究。實驗結果顯示，相較於傳統的粒子群演算法，詢問式學習粒子群演算法不僅增加搜索多樣性，同時也提高最佳解搜索的精確度。本論文同時也提出兩個基於粒子群演算法的綠能應用模組，更進一步驗證其較其他統計方法來的更接近真實問題模擬狀況，也成功的降低能源相關成本。

關鍵字

詢問式學習 ； 粒子群演算法 ； 綠能計算 ； 雲端計算 ； 人工智慧

並列摘要

Particle swarm optimization (PSO) is one of the most important research topics on swarm intelligence. Existing PSO techniques, however, still contain some significant disadvantages. We present a novel QBL-PSO algorithm that uses QBL (query-based learning) to improve both the exploratory and exploitable capabilities of PSO. Two ways for invoking the QBL are introduced, QP-CR and QP-SR. Here, we apply a QBL method proposed in our previous research to PSO, the new algorithm is first verified through several optimization testing functions. And later on, two green computing applications are introduced and verify the QBL-PSO. The two applications are real cases about power conservation and consumption. The first is power contract problem and the other is virtual machine placement problem in cloud computing. This research not only contributes on improving the PSO through combining QBL, but also advice the PSO-based modules for solving the two green computing applications. Furthermore, QBL not only broadens the diversity of PSO, but also improves its precision. Conventional PSO falls into local solutions when performing queries, instead of finding better global solutions. To overcome the drawbacks, when particles converge in nature, we direct some of them into an ambiguous solution space defined by our algorithm.
Our experiment results confirm that the proposed method attains better convergence to the global best solution. We also verify the PSO-based method through solving green computing applications. Both of them successfully reduces energy cost, and to our knowledge, this research presents the first attempt within the literature to apply the QBL concept to PSO.

並列關鍵字

Query-based learning ； Particle Swarm optimization ； Green Computing ； Cloud Computing ； Artificial Intelligence

參考文獻

[32] A. Fox, R. Griffith, A. Joseph, R. Katz, A. Konwinski, G. Lee, et al., "Above the clouds: A Berkeley view of cloud computing," Dept. Electrical Eng. and Comput. Sciences, University of California, Berkeley, Rep. UCB/EECS, vol. 28, 2009.

[1] A. Beloglazov, R. Buyya, Y. C. Lee, and A. Zomaya, "A taxonomy and survey of energy-efficient data centers and cloud computing systems," Adv. Comput., vol. 82, pp. 47-111, 2011.

[2] M. Y. Liao,C. W. Tsai,C. S. Yang,M. C. Chiang,C. F. Lai,"Energy efficiency based on high performance particle swarm optimization: a case study", Telecommunication Systems, pp. 1-12, 2011.

[4] R. Jeyarani, N. Nagaveni, R. Vasanth Ram, "Design and implementation of adaptive power-aware virtual machine provisioner (APA-VMP) using swarm intelligence", Future Generation Comput Syst, vol. 28, no. 5, pp. 811–821, 2012.

[7] M. Clerc, "Discrete Particle Swarm Optimization Illustrated by the Traveling Sa- lesman Problem", http://www.maurieeclerc.net, 2000.