臺灣博碩士論文加值系統

粒子群演算法是近年來群體智能中相當熱門的議題，也因此有許多的學者針對粒子群演算法進行研究與改良。然而即使經過長久的開發，粒子群演算法仍然存在一些可能性陷入局部最佳解。本論文導入詢問式學習改善粒子群演算法，不僅是提高粒子群的全區域最佳解探索能力，同時也提高小區域的最佳解搜索能力。論文當中介紹兩種詢問式學習機制啟動的方式，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.

1 Chapter 1. Introduction 1
1.1 Motivation & Research Background 2
1.2 Contributions 3
1.3 Organization 4
2 Chapter 2. Related Works 5
2.1 Query-based Learning Algorithm 5
2.2 Particle Swarm Optimization Algorithm 6
2.2.1 Background and Concept of Particle Swarm Optimization 6
2.2.2 Particle Swarm Optimization Algorithm 7
2.3 Green Computing 10
2.3.1 Review and Applications of the Green Computing 11
2.3.2 Load Prediction and Contract Capacity Optimization 13
2.3.3 PSO Optimization Strategy and Power System Applications. 14
2.3.4 Green Cloud：Virtual Machine Placement 14
3 Chapter 3. Proposed Methods 17
3.1 Query-based Learning Improved Particle Swarm Optimization Algorithm 17
3.1.1 Particle Swarm Optimization with Crowd Redistribution 18
3.1.2 QBL-PSO by Smoothly-convergent Redistribution 24
3.2 Particle Swarm Optimizer with Query-based Learning for Multi-objective Power Contract Problem 27
3.2.1 Load Forecast Model - Peak Capacity Prediction 28
3.2.2 Stochastic Simulation Mechanism 30
3.2.3 Contract Capacity Optimization 33
3.3 Particle Swarm Optimizer with Query-based Learning for Virtual Machine Placement 39
3.3.1 Optimal VM Placement Optimization Framework 40
3.3.2 QBL-PSO Algorithm for VM Placement Optimization 43
4 Chapter 4. Experimental Results and Analyses 45
4.1 Evaluation of Particle Swarm Optimization with Query-based Learning 45
4.1.1 Illustrations of Test Functions 46
4.1.2 Evaluation Results of QP-CR 52
4.1.3 Evaluation Results of QP-SR 69
4.2 Evaluation of QBL-PSO for Multi-objective Power Contract Problem 79
4.2.1 Evaluation and Data Explanation of Real Cases. 79
4.2.2 Evaluation of Load Forecasting and Peak Capacity Prediction. 81
4.2.3 Evaluation of Contract Capacity Optimization. 83
4.3 Evaluation of QBL-PSO for Virtual Machine Placement in Cloud Computing 86
5 Chapter 5. Conclusion and Future Works 88
5.1 Conclusions 88
5.2 Future Works 90
5.2.1 Dynamic Optimization with Query-based Learning 90
Reference 92

[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.
[3]D. Niyato, S. Chaisiri, L.B. Sung, "Optimal power management for server farm to support green computing", Proceedings of the 2009 9th IEEE/ACM International Symposium on Cluster Computing and the Grid, CCGRID’09, IEEE Computer Society, pp. 84–91, 2009.
[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.
[5]A. Tiwari, M. Laurenzano, J. Peraza, L. Carrington, and A. Snavely, "Green queue: Customized large-scale clock frequency scaling", in 2012 Second International Conference on Cloud and Green Computing (CGC) IEEE, pp. 260–267, 2012.
[6]Z. Wu and J. Wang, "Power Control by Distribution Tree with Classified Power Capping in Cloud Computing", reen Computing and Communications (GreenCom), 2010 IEEE/ACM Int''l Conference on and International Conference on Cyber, Physical and Social Computing (CPSCom), pp. 319-324, 2010.
[7]M. Clerc, "Discrete Particle Swarm Optimization Illustrated by the Traveling Sa- lesman Problem", http://www.maurieeclerc.net, 2000.
[8]A. Beloglazov, R. Buyya, "Adaptive threshold-based approach for energy-efficient consolidation of virtual machines in cloud data centers", Proceedings of the 8th International Workshop on Middleware for Grids, Clouds and e-Science, pp.1-6, 2010.
[9]L. Liu, H. Wang, X. Liu, X. Jin, W.B. He, Q.B. Wang, and Y. Chen, "GreenCloud: a new architecture for green data center", Proceedings of the 6th international conference industry session on Autonomic computing and communications industry session, Barcelona, Spain: ACM, pp. 29-38, 2009.
[10]A. J. Younge, G. Laszewski, L. Wang L, "Efficient resource management for cloud computing environments", International conference on green computing, pp 357–364, 2010.
[11]J. Werner, G. Geronimo, C. Westphall, et al., "Simulator improvements to validate the green cloud computing approach", The IEEE/IFIP Network Operations and Management Symposium, pp.1-8, 2011.
[12]F Van den Bergh, and Engelbrech, A. P., "Cooperative Learning in Neural Net- works using Particle Swarm Optimizers", South African Computer Journal, 2002.
[13]C Hankendi and A. K. Coskun, "Adaptive Power and Resource Management Techniques for Multi-threaded Workloads", Proceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing Workshops and PhD Forum, pp.2302-2305, 2013
[14]F. Heppner and U. Grenander, "A stochastic nonlinear model for coordinated bird flocks, The Ubiquity of Chaos", AAAS Publications, 1990.
[15]I. Takouna , W. Dawoud and C. Meinel, "Energy Efficient Scheduling of HPC-Jobs on Virtualized Clusters Using Host and VM Dynamic Configuration", Proc. ACM SIGOPS Oper. Syst. Rev., vol. 46, no. 2, pp. 19-27, 2012.
[16]O. Sarood and L.V. Kalé, "A ''Cool''Load Balancer for Parallel Applications", Proc. ACM/IEEE Conf. Supercomputing, 2011.
[17]M. Iyengar, M. David, P. Parida, V. Kamath, B. Kochuparambil, D. Graybill, M. Schultz, M. Gaynes, R. Simons, R. Schmidt and T. Chainer, "Server Liquid Cooling with Chiller-less Data Center Design to Enable Significant Energy Savings", IEEE SEMITherm Conference, 2012.
[18]J. Baliga, R. W. A. Ayre, K. Hinton and R. S. Tucker, "Green cloud computing: Balancing energy in processing, storage, and transport", Proc. IEEE, vol. 99, no. 1, pp. 149-167, 2011.
[19]M. Xu, Y. Shang, D. Li, and X. Wang, "Greening data center networks with throughput-guaranteed power-aware routing," Computer Networks, vol. 57, no. 15, pp. 2880-2899, 2013.
[20]J. Kennedy and R. Eberhart, "Particle swarm optimization", IEEE International Conference on Neural Networks, pp. 1942-1948, 1995.
[21]J. Kennedy and R. C. Eberhart, "A discrete binary version of the particle swarm algorithm", IEEE International Conference on Computational Cybernetics and Simulation., , pp. 4104-4108, 1997.
[22]N. Cordeschi, M. Shojafar and E. Baccarelli. "Energy-saving self-configuring networked data centers", Comput. Networks, vol. 57, no. 17, pp. 3479-3491, 2013.
[23]D. Kliazovich, P. Bouvry, and S. Khan, "Greencloud: a packet-level simulator of energy-aware cloud computing data centers," The Journal of Supercomputing, 2010.
[24]C. Pang, C. W. Hui, L. Wenkai, S. Haruo, H. Kentaro and L. Pu, "Long-term electricity contract optimization with demand uncertainties", Energy, vol. 31, no. 13, pp. 2469-2485, 2006.
[25]K. Visakha, K. Thukaram and J. Lawrence, "An approach for evaluation of transmission costs of real power contracts in deregulated systems", Systems Research, vol. 70, no. 2, pp. 141-151, 2004.
[26]B. Adam and H. Greg, "Better power contracts: Using flexibility to increase value", The Electricity Journal, vol. 18, no. 10, pp. 62-69, 2005.
[27]L. Messerschmidt and A. P. Engelbrech, "Learning to play games using a PSO-based competitive learning approach", IEEE Evolutionary Computation, vol. 8, no. 3, pp. 280-288, 2004.
[28]Z. L. Gaing, C. N. Lu, B. S. C. Storation and C. L. Cheng, "An object-orientation approach for implementing power system restoration package", IEEE Transactions on Power Systems, vol. 11, no. 1, pp. 483-498, 1996.
[29]L. Yang, "Automatic calibration of a rainfall–runoff model using a fast and elitist multi-objective particle swarm algorithm", Expert Systems with Applications, vol. 36, no. 5, pp. 9533-9538, 2009.
[30]C. Reynolds, "Flocks,birds,and schools-a distributed behavioral model", Computer Graphics, vol. 21, no. 4, pp. 25-34, 1987.
[31]W. Yujia and Y. Yupu, "Particle swarm optimization with preference order ranking for multi-objective optimization", Information Sciences, vol. 179, no. 12, pp.1944-1959, 2009.
[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.
[33]A.-J. Su, D. R. Choffnes, A. Kuzmanovic, and F. E. Bustamante, "Drafting behind Akamai (travelocity-based detouring)", ACM SIGCOMM Computer Communication Review, vol. 36, pp. 435-446, 2006.
[34]L. Bertini, J. C. Leite, and D. Mosse, "Statistical qos guarantee and energy-efficiency in web server clusters", 19th Euromicro Conference on RECRTS''07, pp. 83-92, 2007.
[35]R. Bianchini and R. Rajamony, "Power and energy management for server systems", Computer, vol. 37, pp. 68-76, 2004.
[36]D. Kusic and N. Kandasamy, "Risk-aware limited lookahead control for dynamic resource provisioning in enterprise computing systems", Cluster Computing, vol. 10, pp. 395-408, 2007.
[37]N. Bobroff, A. Kochut, and K. Beaty, "Dynamic placement of virtual machines for managing sla violations", IEEE International Symposium on Integrated Network Management, pp. 119-128, 2007.
[38]E. O. Wilson, "Sociobiology: The new synthesis", Belknap Press of Harvard Uni- versity Press, 1975.
[39]A. Molla, S. Pittayachawan, B. Corbitt, "Green IT Diffusion: An International Comparison", RMIT University, Melbourne, Australia, 2009.
[40]H. Xiaohui and R. Eberhart, "Multiobjective optimization using dynamic neigh- borhood particle swarm optimization", IEEE Evolutionary Computation, vol. 2, pp. 1677-1681, 2002.
[41]S. Murugesan, "Harnessing green IT: Principles and practices", IEEE IT Professional, vol. 10, no. 1, pp. 24-33, 2008.
[42]R. Bose, X. Luo., "Integrative framework for assessing firms’ potential to undertake Green IT initiatives via virtualization – A theoretical perspective", Journal of Strategic Information Systems, vol. 20, pp. 38-54, 2011.
[43]A. Molla., V. A. Cooper., S. Pittayachawan, "IT and Eco-sustainability: Developing and Validating a Green IT Readiness Model", International Conference on Information Systems, pp. 141-158, 2009
[44]S. Farag, A. Baiyat, and T. Cheng, "Economic load dispatch multi-objective optimization procedures using linear programming techniques", IEEE Transaction on Power System, vol. 10, no. 2, pp. 731-738, 1995.
[45]R. Jabr, A. Coonick, and B. Cory, "A homogeneous linear programming algorithm for the security constrained economic dispatch problem", IEEE Transaction on Power System, vol. 15, no. 3, pp. 930-36, 2000.
[46]I. Habiballah and M. Irving, "Observability analysis for state estimation using linear programming", IEEE Proceedings Generation, Transmission and Distribution, vol. 148, no. 2, pp. 142-145, 2001.
[47]S. L. Wen, Y. T. Chen, T.H. Wu, "Optimization for ice-storage air-conditioning system using particle swarm algorithm", Applied Energy, vol. 86, pp. 1589-1595, 2010.
[48]D. Chattopadhyay, "A practical maintenance scheduling program mathematical model and case study", IEEE Transaction on Power System, vol.13, no. 4, pp. 1475-1480, 1998.
[49]X. Lin, A. David, and C. Yu, "Reactive power optimization with voltage stability consideration in power market systems", IEEE Proceedings Generation, Transmission and Distribution, vol. 150, no. 3, pp. 305-310, 2003.
[50]C. Lehmkoster, "Security constrained optimal power flow for an economical operation of FACTS-devices in liberalized energy markets", IEEE Transaction on Power System, vol. 17, no. 2, pp. 603-608, 2002.
[51]W. Si1, H. Ogai1, T. Li1, M. Ogawa1,K. Hirai, and H. Takahashi , "Energy Saving System for Office Lighting by Using PSO and ZigBee Network", Simulated Evolution and Learning, pp. 667-676, 2010
[52]G. Shrestha, B. Pokharel, T. Tek, and S. Fleten, "Medium term power planning with bilateral contracts", IEEE Transactions on Power Systems, vol. 20, no.2, pp. 627–633, 2005.
[53]A. Escobar, R. Gallego, and R. Romero, "Multistage and coordinated planning of the expansion of transmission systems", IEEE Transactions on Power Systems, vol. 19, no. 2, pp. 735-744, 2004.
[54]E. Aponte and J. Nelson, "Time optimal load shedding for distributed power systems", IEEE Transactions on Power Systems, vol. 21, no. 1, pp. 269-277, 2006.
[55]A. Conejo, N. Alguacil, and G. Fernandez, "Allocation of the cost of transmission losses using a radial equivalent network", IEEE Transactions on Power Systems, vol. 18, no. 4, pp. 1353-1358, 2003.
[56]D. Pudjianto, S. Ahmed, and G. Strbac, "Allocation of VAr support using LP and NLP based optimal power flows", IEEE Proceedings Generation, Transmission and Distribution, vol. 149, no. 4, pp. 377-383, 2002.
[57]D. Abramson, J. Giddy, and L. Kotler, "High performance parametric modeling with Nimrod/G: Killer application for the global grid?", Parallel and Distributed Processing Symposium, pp. 520-528, 2000.
[58]R. Buyya, D. Abramson, and J. Giddy, "A Case for Economy Grid Architecture for Service-Oriented Grid Computing", IPDPS, 2001.
[59]R. Buyya, K. Branson, J. Giddy, and D. Abramson, "The Virtual Laboratory: a toolset to enable distributed molecular modelling for drug design on the World‐Wide Grid", Concurrency and Computation: Practice and Experience, vol. 15, pp. 1-25, 2003.
[60]R. Buyya, D. Abramson, and S. Venugopal, "The grid economy", Proceedings of the IEEE, vol. 93, pp. 698-714, 2005.
[61]G. Stuer, K. Vanmechelen, and J. Broeckhove, "A commodity market algorithm for pricing substitutable Grid resources", Future Generation Computer Systems, vol. 23, pp. 688-701, 2007.
[62]R. Buyya, H. Stockinger, J. Giddy, and D. Abramson, "Economic models for management of resources in peer-to-peer and grid computing", International Symposium on the Convergence of IT and Communications, pp. 13-25, 2001.
[63]F. Heppner and U. Grenander, "A stochastic nonlinear model for coordinated bird flocks", The ubiquity of chaos, AAAS Publications, 1990.
[64]C. Reynolds, "Flocks, birds, and schools–A distributed behavioral model", Computer Graphics, vol. 21, no. 4, pp. 25-34, 1987.
[65]M. Jiang, Y. P. Luo and S. Y. Yang,"Stochastic convergence analysis and parameter selection of the standard particle swarm optimization algorithm", Information Processing Letters, vol. 102, pp. 8-16, 2007.
[66]R. I. Chang and P. Y. Hsiao, "Unsupervised query-based learning of neural networks using selective-attention and self-regulation", IEEE Trans. Neural Networks, vol. 18, no. 2, pp.205-217, 1997.
[67]R. I. Chang, C. C. Chu, Y. Y. Wu, Y. L. Chen, "Gene clustering by using query-based self-organizing maps", Expert Systems with Applications, vol. 37, no. 9, pp. 6689-6694, 2010.
[68]F. Hermenier, X. Lorca, J.-M. Menaud, G. Muller, and J. Lawall, "Entropy: a consolidation manager for clusters", ACM SIGPLAN/SIGOPS international conference on Virtual execution environments, pp. 41-50, 2009
[69]S. Chaisiri, B.-S. Lee, and D. Niyato, "Optimal virtual machine placement across multiple cloud providers", Services Computing Conference, APSCC 2009. IEEE Asia-Pacific, pp. 103-110, 2009
[70]A. Filali, A. S. Hafid, and M. Gendreau, "Adaptive Resources Provisioning for Grid applications and services", IEEE International Conference on Communications, pp. 186-191, 2008.
[71]K. Keahey, I. Foster, T. Freeman, and X. Zhang, "Virtual workspaces: Achieving quality of service and quality of life in the grid", Scientific Programming, vol. 13, pp. 265-275, 2005.
[72]C. S. Carver and M. Scheier, "Attention and self-regulation: a control-theory approach to human behavior", Springer-Verlag, 1981.
[73]W. T. Powers, "Behavior: The control of perception", New York, NY: Hawthorne, 1973.
[74]R.-I. Chang, L.-B. Lai, W.-D. Su, J.-C. Wang, and J.-S. Kouh, "Intrusion detection by backpropagation neural networks with sample-query and attribute-query", International Journal of Computational Intelligence Research, vol. 3, pp. 6-10, 2007.
[75]P. Angeline, V. W. Porto, N. Saravanan, D. Waagen, and A. E. Eiben, "Evolutionary optimization versus particle swarm optimization: Philosophy and performance differences", Evolutionary Programming VII, pp. 601- 610, 1998.
[76]M. Clerc, "The swarm and the queen: Towards a deterministic and adaptive particle swarm optimization”, Proceedings of the Congress of Evolutionary Computation, pp. 195l-1957, 1999.
[77]M. Clerc, J. Kennedy, "The particle swarm-explosion, stability, and convergence in a multidimensional complex space", IEEE Transactions on Evolutionary Computation, vol. 6, no. 1, pp. 58-73, 2002.
[78]C. T. Iristian, "The particle swarm optimization algorithm: Convergence analysis and parameter selection. Information Processing Letters", vol. 85, no. 6, pp. 317-325, 2003.
[79]M. Jean-Daniel, H. N. Saphores, A. O. Oladele and A. S. Andrew, "Household willingness to recycle electronic waste: An application to California", Environment and Behavior, vol. 38, no. 2, pp. 183-208, 2006.
[80]Y. H. Shi and R. C. Eberhart, "Parameter selection in particle swarm optimization", Lecture notes on computer science, vol. 1447, pp. 591-600, 1998.
[81]Y. H. Shi and R. C. Eberhart, "Comparing inertia weights and constriction factors in particle swarm optimization", IEEE Evolutionary Computation, vol. 1, pp. 84-88, 2000.
[82]J. Kennedy, "Small worlds and mega-minds: Effects of neighborhood topology on particle swarm performance", IEEE Evolutionary Computation, vol. 3, pp. 1931-1938, 1999.