臺灣博碩士論文加值系統

目前求解最佳化問題時常常會使用許多萬用演算法(Meta-Heuristic Algorithm)來做為求解的方法。這些萬用演算法架構雖然相同，但面對不同問題仍需重新撰寫所有程式碼，且在運算的過程中所需的大量運算資源也需要許多人力來加以管理。本研究將提出一萬用演算法之雲端架構(Cloud Architecture of Meta-Heuristic Algorithm，CAMHA)，CAMHA是以雲端運算(Cloud Computing)的方式來做分散式運算，藉此解決萬用演算法執行時所需之大量運算資源。同時在CAMHA中將萬用演算法分為主架構程式(Main Framework Program，MFP)與使用者定義程式碼(User Defined Code，UDC)，其中MFP為系統內定提供之主架構不須使用者一再撰寫，使用者僅須撰寫CAMHA所需之UDC，及設定好演算法所需之所有參數組合，即可將問題導入CAMHA做運算。在此研究中將基因演算法(Genetic Algorithms，GA)、禁忌搜尋法(Tabu Search，TS)、模擬退火法(Simulated Annealing，SA)、與粒子群演算法(Particle Swarm Optimization，PSO)等流程加以調整與改良，以便將演算法導入CAMHA，且提出一雙軌粒子群演算法(Double Track PSO，DTPSO)來改善PSO演算法。最後我們用DTPSO測試了許多範例，以便驗證CAMHA的可用性與DTPSO的效率性。

Up to now, Meta-Heuristic Algorithms are the most popular approaches for solving optimization problems. Although the architectures of Meta-Heuristic Algorithms are fixed, it is still to program the specific individual program for solving different problem; moreover, it is needed numerous manpowers to arrange the computing resources comsumed by those Meta-Heuristic Algorithms. In this study, we propose a Cloud Architecture of Meta-Heuristic Alogrithm (CAMHA) which utilizes the cloud computing to distribute executing the Meta-Heuristic Alogrithm, and it can help us to solve the difficulty of enormous requiring computing resources by Meta-Heuristic. Briefly, there are Main Framework Program (MFP) and User Defined Code (UDC) in CAMHA. MFP is a uniform pre-programming program provided by system, which offers the standard flow of Meta-Heuristic Alogrithm. Users only provide the UDC and configure the parameter sets which required by CAMHA, they can rapidly and easily solve the optimal problems through CAMHA. Genetic Algorithm (GA), Tabu Search (TS), Simulated Annealing (SA), and Particle Swarm Optimization (PSO) are modified and refined in this study for fulfilling the architecture of CAMHA; additional, we propose the Double Track PSO (DTPSO) to improve the efficiency of original PSO. Finally, some numeric experiments demonstrate the usefuleness of CAMHA and the efficieny of DTPSO.

第壹章 緒論 1
第一節 研究背景與動機 1
第二節 研究目的 2
第貳章 文獻探討 5
第一節 雲端運算 5
第二節 分散式運算 9
第三節 Windows Socket 12
第四節 Windows Hyper-V R2 13
第五節 萬用演算法 15
第參章 CAMHA架構 17
第一節 VM建置流程 17
第二節 使用者專案使用流程 19
第三節 專案執行流程 20
第肆章 GA Cloud實作 25
第一節 基本操作介面說明 25
第二節 Cloud主畫面操作 27
第三節 GA Cloud參數設定 30
第四節 GA UDC設定與上傳 34
第五節 UDC規格與說明 38
第六節 結果檢視 49
第伍章 PSO Cloud實作 53
第一節 PSO Cloud參數設定 53
第二節 PSO UDC設定及上傳 60
第三節 Double-Track PSO概念 64
第四節 UDC規格與說明 72
第陸章 Tabu Cloud實作 89
第一節 Tabu Cloud參數設定 89
第二節 Tabu UDC設定及上傳 93
第三節 UDC規格與說明 97
第柒章 SA Cloud實作 113
第一節 SA Cloud參數設定 113
第二節 SA UDC設定及上傳 117
第三節 UDC規格與說明 120
第捌章 實驗結果與分析 137
第一節 PSO 實驗結果 137
第二節 PSO演算法結果分析 142
第三節 CAMHA效能實驗與分析 142
第玖章 結論與未來展望 145
參考文獻 147
附錄 149


 
表次

表8-1 PSO CASE1演算法執行結果 139
表8-2 PSO CASE2演算法執行結果 141
表8-3 CAMHA實驗結果 144

1.李泳泉，Hyper-V伺服器虛擬化簡介，國立台灣大學計算機及資訊網路中心，第0014期，2010/09/20。2014/08/26，擷取自：http://www.cc.ntu.edu.tw/chinese/epaper/0014/20100920_1408.htm。
2.周秉誼，雲端運算平台-Hadoop，國立台灣大學計算機及資訊網路中心，第0011期，2009/12/20。2014/08/26，擷取自：http://www.cc.ntu.edu.tw/chinese/epaper/0011/20091220_1106.htm。
3.Armbrust, M., Armando, F., Rean, G., Anthony, D. J., Randy, K., Andy, K., Gunho, L., David, A. P., Ariel, R., Ion, S. & Matei, Z., Above the Clouds: A Berkeley View of Cloud Computing, Technical Report No. UCB/EECS-2009-28, University of California at Berkeley, 2009.
4.Arora, J. S., Introduction to Optimun Design, McGraw-Hill, New York, 1989.
5.Belegundu, A. D., A study of mathematical programming methods for structural optimization, Technical report, University of Iowa, 1982.
6.Buyya, R., Yeoa, C. S., Venugopala S., Broberga J.& Brandicc I., Cloud computing and emerging IT platforms: Vision, hype, and reality for delivering computing as the 5th utility, Future Generation Computer Systems, 2009.
7.El-Gallad, A. I., El-Hawary, M. E. & Sallam, A. A., Swarming of intelligent particle for solving the nonlinear constrainted optimization problem, International Journal of Engineering Intelligent System for Electrical Engineering and Communications, 9(3), 2001, pp.155-163.
8.Glover, F., Future Paths for Integer Programming and Links to Artificial Intelligence, Computer and Operations Research, Vol. 13. No. 5, 1986, pp.533-549.
9.He, S., Prempain, E. & Wu, Q. H., An Improved Particle Swarm Optimizer for Mechanical Design Optimization Problems, Engineering Optimization, Vol. 36. No. 5, 2004, pp.585-605
10.Himmelblau, D. M., Applied Nonlinear Programming, McGraw-Hill, New York, 1972.
11.Holland, J., Adaptation in Natural and Artificial System, University of Michigan Press, Ann Arbor, 1975.
12.Kennedy, J. & Eberhart, R. C., Particle swarm optimization, IEEE International Conference on Neural Networks, Vol. 4, IEEE Press, 1995, pp.1942-1948.
13.Kirkpatrick, S., Gelatt, C. D. & Vecchi, M. P., Optimization by simulated annealing, Science, vol. 220, 1983, pp.671-680.
14.Mell, P. & Grance, T., The NIST Definition of Cloud Computing, National Institute of Standards and Technology, 2009.
15.Shi, Y. & Eberhart, R. C., Parameter selection in particle swarm optimization. Evolutionary Programming VII, Lecture Notes in Computer Science 1447, Springer, 1998, pp.591-600.