(44.192.66.171) 您好!臺灣時間:2021/05/18 00:41
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:芮雍能
研究生(外文):Yung-Neng Jui
論文名稱:整合平行計算與生物演算法的技術應用於整體最佳化問題之研究
論文名稱(外文):The Study of Global Optimization by Integrating Parallel Computations and Evolution Algorithms
指導教授:游子宜游子宜引用關係
指導教授(外文):Yzu-Yi Yu
學位類別:碩士
校院名稱:國立暨南國際大學
系所名稱:資訊管理學系
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2005
畢業學年度:93
語文別:中文
論文頁數:100
中文關鍵詞:平行計算MPIOpenMP基因演算法演化策略模擬退火演算法
外文關鍵詞:Parallel computationMPIOpenMPgenetic algorithmevolution strategysimulated annealing algorithm
相關次數:
  • 被引用被引用:6
  • 點閱點閱:204
  • 評分評分:
  • 下載下載:33
  • 收藏至我的研究室書目清單書目收藏:0
最佳化問題一直是被研究的重要領域,因為它跟我們生活息息相關。一般的演算法在面對最佳解問題時,無不希望變數數量與運算時間能在合理的範圍內。但是對於一些多個變數數量或需要大量計算的問題,雖然電腦的運算速度一直在進步,卻仍然無法在有限的時間內滿足這些問題龐大的計算量,如果減少其演算法搜尋的次數或時間,又可能會造成無法找到理想的最佳近似解的情形。故本研究針對多個變數數量與縮短運算時間以演化策略、基因演算法與模擬退火演算法於MPI平行程式計算的環境下,求取最大化與最小化實例問題的最佳近似解。在平行程式方面,我們介紹共用式記憶體架構下的OpenMP與分散式記憶體架構下的MP I平行程式。在三種演算法的效率與效能方面,我們以兩個有門檻的函數作為標竿來驗證以循序程式、MPI與OpenMP平行程式寫成的三種演算法的效率與效能。最後,我們以MPI平行程式計算針對多個變數數量與縮短運算時間之下,求取政治大學風險管理與保險學系提供的兩個最大化與最小化實例問題的最佳近似解。並由結果顯示平行計算的結果都遠遠優於原來模擬的方法,證明平行計算能有效解決演算法在面對變數數量被限制或運算時間太長的困境。
Global optimization is important since it is highly related to human’s life and has been studied for decades. Generally speaking, when applying solution algorithms to global optimization problem, one would expect the number of variables to be solved and computational time needed could both fall in the acceptable range. Even though today’s computer has much improved both in memory capacity and computational power, when solving hard optimization problems with lots of unknown generally requires heavy computational resources. One might reduce the iterations in the algorithm to save computational time, yet this might lead to local optimization or not even converge. In this study, the focus has been placed on developing algorithms to solve the global optimization problems with large unknown variables within a reasonable computation time. Three algorithms – the evolution strategy (ES), genetic algorithm (GA) and simulated annealing algorithm (SA) have been implemented. And these three algorithms have been integrated with the parallel computational environment – the Message Passing Interface (MPI), for solving the optimization (both maximum and minimum) problems. These algorithms have been tested with two benchmarks in sequential, MPI and OpenMP forms to study the performance and efficiency. Finally, the algorithms integrated with MPI are applied to two real cases provided by the Department of Risk Management and Insurance of National Chengchi University. The results show that the parallel computation can significantly the computation time when solving the optimization problem with a large number of variables.
目 錄
論文摘要 I
ABSTRACT II
目 錄 IV
圖 目 錄 VI
表 目 錄 VII
第一章 緒論 1
1.1 研究動機 1
1.2 研究目的 3
1.3 全文結構 4
第二章 平行計算介紹 5
2.1 前言 5
2.2 格雷電腦 7
2.3 共用式記憶體多處理器系統(Shared Memory Multiprocessor System) 8
2.4 分散式記憶體多處理器系統(Distributed Memory Multiprocessor System) 10
2.5 創新的平行電腦架構 13
2.6 MPI(Message Passing Interface) 14
2.6.1 MPI簡介 14
2.6.2 MPI程式架構 14
2.6.3 MPI程式範例 16
2.7 OpenMP 19
2.7.1 OpenMP簡介 19
2.7.2 OpenMP平行模式 21
2.7.3 OpenMP程式範例 21
第三章 演算法介紹 26
3.1 基因演算法(Genetic Algorithm) 26
3.1.1 文獻回顧 26
3.1.2 基因演算法簡介 28
3.1.3 基因演算法流程圖 33
3.1.4 基因演算法架構與流程 34
3.2 演化策略(Evolution Strategy) 39
3.2.1 文獻回顧 39
3.2.2 演化策略簡介 40
3.2.3 演化策略流程圖 42
3.2.4 演化策略架構與流程 43
3.3 模擬退火演算法(Simulated Annealing Algorithm) 46
3.3.1 文獻回顧 46
3.3.2 模擬退火演算法簡介 48
3.3.3 模擬退火演算法流程圖 51
3.3.4 模擬退火演算法架構與流程 52
第四章 實例分析 55
4.1 演算法驗證 55
4.1.1 最大化問題驗證 55
4.1.2 最小化問題驗證 57
4.2 平行計算與演算法 60
4.3 實例說明 62
4.3.1 案例-模擬產險公司最佳化資產配置 62
4.3.2 案例-計算退休金誤差 63
4.4 平行計算結果 66
4.4.1 最大化問題 66
4.4.2 最小化問題 69
第五章 結論與建議 72
參考文獻 74
中文文獻 74
英文文獻 74
附 錄 一 79
附 錄 二 80
附 錄 三 86
中文文獻
[1].鄭守成,2004,MPI平行計算程式設計,新竹:國家高速網路與計算中心。
[2].金重勳,1996,熱處理,台南市:復文書局。
[3].蘇承懋,2004,「模擬產險公司最佳化資產配置」,碩士論文,國立政治大學風險管理與保險學系,台北。
英文文獻
[4].Aarts, E. and Korst, J., 1989, Simulated Annealing and Boltzmann Machine, New York, Wiley & Sons.
[5].Bagley, J. D., 1967, “The behavior of adaptive systems which employ genetic and correlation algorithms”, Dissertation Abstracts International, Vol. 28, No. 12, 5106B.
[6].Battiti, R. and Tecchiolli, G.., 1994, “Simulated annealing and tabu search in the long run: a comparison on QAP tasks,” Computers and Mathematics with Applications 28 (6), pp. 1-8.
[7].Colville, A. R., 1968, A Comparative Study on Nonlinear Programming Codes, IBM Scientific Center Report 320-2949, New York.
[8].Cox, J. C., Ingersoll, J. E., and Ross, S. A., 1985, A theory of the term structure of interest rates, Econometrica, 53: 385-408.
[9].Chu, P.H and Dudley, S.A., 1993, “The effect of population structure on the rate of convergence of genetic algorithms,” in Proceedings of the 1993 ACM/SIGAPP symposium on Applied computing: states of the art and practice, Indianapolis, Indiana, United States, pp. 147-151.
[10].Dougherty, D. E. and Marryott, R. A., 1991, Optimal Ground Water Management: 1. Simulated Annealing. Water Resource Research 27(10):2493-2508.
[11].De Jong, K. A., 1975, “An Analysis of the Behavior of a Class of Genetic Adaptive Systems,” Ph.D. Dissertation, University of Michigan, Ann Arbor.
[12].Dozier, G., Homaifar, A., Tunstel, E. and Battle, D., “An introduction to evolutionary computation” (Chapter 17), Intelligent Control Systems Using Soft Computing Methodologies, A. Zilouchian and M. Jamshidi (Eds.), pp. 365-380, CRC press. (can be found at: www.eng.auburn.edu/~gvdozier/chapter17.doc)
[13].Frederick S. Hillier, Gerald J. Lieberman, 2004, Introduction to Operation Research, Mc Graw-Hill, New York.
[14].Goldberg, D. E., 1989, Genetic Algorithms in Search, Optimization and Machine Learning, Addison – Wesley Publishing Company.
[15].Holland, J. H., 1975, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor.
[16].James Fung, Steve Mann, 2004, "Using Multiple Graphics Cards as a General Purpose Parallel Computer : Applications to Computer Vision", in Proceedings of the 17th International Conference on Pattern Recognition (ICPR2004) , Cambridge, United Kingdom, August 23-26, volume 1, pp. 805-808.
[17].Jeffcoat, D. and Bulfin, R., 1993, Simulated annealing for resource-constrained scheduling. European Journal of Operational Research, 70: 43-51.
[18].Kirkpatrick, S., Gelatt Jr., C. and Vecchi, M. 1983, Optimization by simulated annealing, Science 220, pp. 671-680.
[19].Kliewer, G. and Tschoke, S., 2000, “A general parallel simulated annealing library and its application in airline industry,” in Proceedings of the 14th International Parallel and Distributed Processing Symposium (IPDPS 2000), pp. 55-61.
[20].Lin, F.T., Kao, C.Y., and Hsu, C. C., 1993, Applying the genetic approach to simulated annealing in solving some NP-hard problems, IEEE Transactions on Systems, Man, and Cybernetics 23 (6), pp. 1752-1767.
[21].Metropolis, N. A., A. 1953, Rosenbluth, M. Rosenbluth, “Equation of state calculations by fast computing machines,” Journal of Chemical Physics 21, pp. 1087-1092.
[22].Michalewicz, Z., 1996, Genetic Algorithms + Data Structures = Evolution Programs, Springer, New York.
[23].Muhlenbein, H., 1989, Parallel genetic algorithms, population genetics and combinatorial optimization, In Proceedings of the Third International Conference on Genetic Algorithms, Morgan Kaufmann Publishers, San Mateo, CA, pp.416-421.
[24].Pai, G.A.V. and Sreeram, S., 2002, “Military target identification using Simulated Annealing,” in Proceedings of the 9th International Conference on Neural Information Processing (ICONIP '02), Vol. 4, pp. 2064-2068.
[25].Peter Pacheco, 1997, Parallel Programming with MPI , Morgan Kaufmann Publishers, San Francisco, California.
[26].Rechenberg, I., 1965, Cybernetic solution path of an experimental problem. Royal Air-craft Establishment, Library Translation NO. 1122, Farnborough, Hants., UK.
[27].Rechenberg, I., 1973, Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Frommann-Holzboog Verlag, Stuttgart.
[28].Rosenberg, R. S., 1967, “Simulation of genetic populations with biochemical properties”, Dissertation Abstracts International, 28(7), 2732B.
[29].Schwefel, H.-P., 1981, Numerical Optimization for Computer Models, John Wiley, Chichester, UK.
[30].Shu, Li-Sun, Ho, Shinn-Ying, Ho, S.-J., 2004, “A novel orthogonal simulated annealing algorithm for optimization of electromagnetic problems, ” Magnetics, IEEE Transactions on Volume 40, Issue 4, pp. 1791-1795.
[31].Srinivas, M. and Patnaik, L. M., 1994, “Adaptive probabilities of crossover and mutation in genetic algorithms,” IEEE Transactions on System, Man. and Cybernetics, Vol. 24, pp. 656 - 667.
[32].Toda, M., Kubo, R., and Saito, N., 1983, Statistical Physics I: Equilibrium Statistical Mechanics, Springer-Verlag.
[33].URL: http://www.ancad.com.tw/iThinker64/Agenda/.
[34].URL: http://www.cray.com/about_cray/history.html.
[35].URL: http://www.eng.auburn.edu/~gvdozier/Intro2EC.ppt.
[36].URL: http://www.flotrend.com.tw/ls-dyna/enews/enews2004-7.htm.
[37].URL: http://www.llnl.gov/computing/tutorials/workshops/workshop/mpi/MAIN.html.
[38].URL: http://www.llnl.gov/computing/tutorials/workshops/workshop/openMP/MAIN.html.
[39].URL: http://www.microsoft.com/taiwan/windows2000/hpc/devtools.htm.
[40].URL: http://www.mpi-forum.org/docs/mpi-20-html/node2.htm#Node2.
[41].Vakharia, A. and Chang, Y., 1990, A simulated annealing approach to scheduling a manufacturing cell. Naval Research Logistics, 37: 559-577.
[42].Van den Bout, D. E. and Miller, T. K., 1989, Improving the Performance of the Hopfield-Tank Neural Network Through Normalization and Annealing. Biological Cybernetics, 62,129-139.
[43].Wakunda, J., Zell, A., 1997, “EvA: a tool for optimization with evolutionary algorithms,” in Proceedings of the 23rd EUROMICRO Conference on New Frontiers of Information Technology, pp.644-651.
[44].Whitley, D., 1990, GENITOR II: A Distributed Genetic Algorithm, Journal of Experimental and Theoretical Artificial Intelligence, Vol.2, pp.189-214.
[45].Yanrong, Hu, Yang, S.X., 2004, “A knowledge based genetic algorithm for path planning of a mobile robot,” IEEE International Conference on Robotics and Automation, Vol. 5, pp. 4350 - 4355.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top