跳到主要內容

臺灣博碩士論文加值系統

(3.237.38.244) 您好!臺灣時間:2021/07/26 09:18
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:古季詮
研究生(外文):Chi-Chuan Ku
論文名稱:直交類梯度搜尋演算法之研究
論文名稱(外文):A Study of Orthogonal Quasi-Gradient Search Algorithm
指導教授:張炳騰張炳騰引用關係曾宗瑤曾宗瑤引用關係
指導教授(外文):Ping-Teng ChangTsueng-Yao Tseng
學位類別:碩士
校院名稱:東海大學
系所名稱:工業工程與經營資訊學系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:中文
論文頁數:101
中文關鍵詞:演化策略最佳化搜尋直交表實驗設計全域搜尋
外文關鍵詞:Evolution strategiesOptimizationOrthogonal experimental designGradientGlobal search
相關次數:
  • 被引用被引用:0
  • 點閱點閱:346
  • 評分評分:
  • 下載下載:19
  • 收藏至我的研究室書目清單書目收藏:0
本研究提出的直交類梯度搜尋演算法(Orthogonal Quasi Gradient Search Algorithm; OQGS)中,取代傳統求解最佳化問題以隨機方式產生初始解,應用直交表實驗設計(Orthogonal Experimental Design; OED)及直交交配之技術做全域搜尋(exploration),建立出更靠近最佳解的初始解以節省求解時間。演化搜尋重點在於利用類梯度搜尋方法,在母體搜尋最佳解時會先比較周圍的資訊,再根據母體梯度向量與母體歷史移動向量判斷子代該移動的方向與距離,加速演化策略整體的搜尋速度,進一步提升演化策略的搜尋效率。最後結合直交微調做區域搜尋(exploitation),向附近的區域解作快速的逼近以達到快速收斂的目的,藉由這樣的機制使整體族群在搜尋時能快速且有效的得到最佳點所在位置。
本研究於相關直交表改良演算法的文獻中,選出八個測試函數做實驗,包含單一區域解與多重區域解等最佳化函數問題。實驗類型包括:固定參數組合之實驗、變動參數組合之實驗、隨機變數邊界之實驗、不同變數個數之實驗等。實驗結果與直交基因演算法(Orthogonal Genetic Algorithm; OGA)、直交模擬退火演算法(Orthogonal Simulated Annealing Algorithm; OSA)作比較,整體結果中直交類梯度搜尋演算法對各種測試函數能迅速且穩定向最佳解逼近,且OQGS在各實驗之績效總表均呈現出優秀的表現,證實OQGS的整體績效較OGA、OSA佳。
This paper brings up the Orthogonal Quasi Gradient Search Evolution Strategy Method (OQGS). Instead of generating initial solution randomly in traditional method to solving the optimization problem, OQGS apply method of orthogonal experimental design (OED) and orthogonal clossover for global search to build a better mechanism for the initial solution. The main focal point of evolution is that parents should consider about the environment information around itself before searching the optimization solution. According to gradient vector and historical moving vector of parents judge the best direction and distance of offspring to approach the region of optimization solution. In this way, the whole population can get the information around the optimization solution efficiency and surround the nearby region of the optimization solution quickly by this system.In order to achieve the goal of quickly convergence, this paper uses orthogonal pitch adjustment for local search, to approximate the local optimal solution nearby. With the method of OQGS, we want to precipitate the whole evolutionary speed and improve the searching efficiency of evolution strategies.
We execute the proposed algorithm to solve eight test functions include of unimodal and multi-modal. The experimental type including of the experiment of fixing parameters, the experiment of changing parameters, the experiment of changing the bound of the variables randomly, the experiment of changing the number of variables Comparing with Orthogonal Genetic Algorithm (OGA) and Orthogonal Simulated Annealing Algorithm (OSA), we can find that OQGS can quicker slove problems than them and more stable find optimal or close-to-optimal solutions to eight test functions. In all of the performance tables show that OQGS can be presentable outstanding performance and it prove that OQGS has best Overall performance than others.
摘要 I
ABSTRACT II
誌謝 III
目錄 IV
表目錄 VI
圖目錄 VII
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究流程與步驟 3
1.4 研究工具 4
第二章 文獻探討 6
2.1 啟發式演算法相關文獻 6
2.1.1 基因演算法(Genetic Algorithms; GAs) 6
2.1.2 基因規劃(Genetic Programming; GP) 7
2.1.3 演化規劃(Evolutionary Programming; EP) 7
2.1.4 蟻拓尋優法(Ant Colony Optimization; ACO) 7
2.1.5 禁忌搜尋法(Tabu Search; TS) 8
2.1.6 模擬退火演算法(Simulated Annealing; SA) 8
2.2 演化策略(EVOLUTION STRATEGIES; ESS) 9
2.2.1 演化策略簡介 9
2.2.2 天擇(selection) 9
2.2.3 自我適應能力 (Self–Adaptation) 10
2.2.4 重構(recombination) 12
2.3 直交表實驗設計方法簡介 12
2.3.1 直交表結合搜尋演算法之相關文獻 13
2.3.2 直交表 14
2.3.3 建立直交表 17
2.3.4 主效果分析 19
2.4 梯度搜尋法 20
2.4.1 最速下降法 (Steepest Descent Method) 20
2.4.2 共軛梯度法(Conjugate Gradient Method) 21
2.5 利用啟發式解法搜尋參數相關文獻 22
2.6 小結 24
第三章 研究方法 25
3.1 直交類梯度搜尋演算法原理 26
3.2 直交類梯度搜尋演算法系統架構 27
3.2.1 初始解 30
3.2.2 直交交配 32
3.2.3 類梯度搜尋 34
3.2.4 直交微調 38
3.3 參數實驗說明 40
3.4 OQGS與相關直交表改良演算法的結構比較 42
3.5 小結 44
第四章 數值實驗與分析 46
4.1 實驗測試函數 46
4.1.1 測試函數簡介 47
4.1.2 實驗假設與定義 50
4.2 參數實驗設計及說明 51
4.2.1 參數說明 51
4.3 OQGS與其他演算法實驗結果之比較:變數個數為10或30 56
4.3.1 利用最佳參數進行實驗比較 56
4.3.2 利用固定參數比較八組測試函數 60
4.3.3 OQGS與OGA特定函數變數範圍偏移之實驗比較 64
4.4 OQGS與其他演算法實驗結果之比較:變數個數為100 68
4.4.1 利用最佳參數進行實驗比較 68
4.4.2 利用固定參數進行實驗比較 72
4.5 OQGS與其他演算法實驗結果之比較:變動變數個數討論 75
4.5.1 不同變數下之各函數各方法排名 75
4.5.2 距離函數分析 80
4.6 實驗結果比較、小結 82
第五章 結論及未來建議 85
5.1 研究總結 85
5.2 後續研究建議 86
參考文獻 88
附錄 92
[1]吳子逢,何信瑩。使用直交實驗設計的高效率演化策略及其應用,逢甲大學碩士論文,2003。
[2]林宏穗,何信瑩。設計一種新型的直交粒子群最佳化演算法,逢甲大學碩士論文,2004。
[3]郭文偉,張炳騰。類梯度搜尋演算策略方法,東海大學碩士論文,2005。
[4]A. Balakrishnan, “A steepest descent method for a class of final value control systems”, IRE Transactions on Automatic Control, Vol: 7, 3 Apr. 1962, pp.75-75.
[5]Arabas, J., Mulawka, J. and Pokrasniewicz, J., “A new class of the crossover operators for the numerical optimization,” Proceedings of the 6th International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, pp. 42-48, 1995.
[6]Bäck, T., Evolutionary Algorithms in Theory and Practice. New York: Oxford Univ. Press, 1996.
[7]Beyer, H.-G., “Toward a theory of evolution strategies: On the benefit of sex—the ( )-Theory,” Evol. Comput., vol. 3, no. 1, pp. 81–111, 1995.
[8]Beyer, H.-G. “Toward a theory of evolution strategies: Self-adaptation,” Evolutionary Computation Journal 3(1), 81-111, 1995b.
[9]Beyer, H.-G., “Toward a theory of evolution strategies: Self-adaptation,” Evolutionary Computation, vol. 3, no. 3, pp. 311–348, 1995.
[10]C. Darwin, On the origin of species. London: John Murray, 1859.
[11]Carlos Andrés Peña-Reyes, Moshe Sipper, “Evolutionary Computation in Medicine: an overview,” Artificial Intelligence in Medicine, 19, pp. 1-23, 2000.
[12]Colorni, A., Dorigo, M. and Maniezzo, V., “An investigation of some properties of an ant algorithm,” Proceedings of the Parallel Problem Solving from Nature Conference, R. Manner and B. Manderick Eds. Brussels, Belgium: Elsevier, pp.509-520, 1992.
[13]Colorni, A., Dorigo, M. and Maniezzo, V., “Distributed optimization by ant colnies,” Proceedings of the First European Conference Artificial Life, F. Varela and P. Bourgine, Eds. Paris, France: Elsevier, pp.134-142, 1991.
[14]Deb, K. and Agrawal, R. B., “Simulated binary crossover for continuous search space.” Complex Systems, 9(2):115–148, 1995.
[15]Deb, K., Anand, A. and Joshi, D., “A Computationally Efficient Evolutionary Algorithm for Real-Parameter Optimization,” Evolutionary Computation 10(4), 371-395, 2002.
[16]Dorigo, M., Bonabeau, E. and Theraulaz, G., “Ant algorithm and stigmergy,” Future Generation Computer Systems, 16, pp. 851-871, 2000.
[17]Dorigo, M., Caro, G.D. and Gambarsella, L.M., “Ant algorithms for discrete optimization,” Artificial Life, 5, pp. 137-172, 1999.
[18]Dorigo, M., Maniezzo, V. and Colorni, A., “Positive feedback as a research strategy,” Technology Report 91-016, Politecnico di Milano, 1991.
[19]Eberhart, R.C. and Kennedy, J. “A new optimizer using particle swarm theory,” Proc. 6th Int. Symp. Micro Machine and Human Science, Nagoya, Japan, pp.39-43.1995.
[20]Eshelman, L. J. and Schaffer, J. D., Real-coded genetic algorithms and intervalschemata. In Foundations of Genetic Algorithms 2 (FOGA-2), pp.187-202, 1993.
[21]Fogel, L. J., Owens, A. J., & Walsh, M. J., Artificial intelligence through simulated evolution. New York: Wiley, 1966.
[22]Glover F., “Heuristic for integer programming using surrogate constraints,” Decision Sci. 8(1), pp. 156-166, 1977.
[23]Goldberg, D. E., Genetic Algorithms in Search, Optimazation and Machine Learning, Addison-Wesley, Reading, MA, 1989.
[24]Goldberg, D. E., Real-coded genetic algorithms, virtual alphabets, and blocking. Complex Systems 5(2), 139-168, 1991.
[25]Goldberg, D. E. and Deb, K., A comparison of selection schemes used in genetic algorithms. In Foundations of Genetic Algorithms 1 (FOGA-1), pp. 69-93, 1991.
[26]H. Szu and R. Hartley, “Fast simulated annealing,” Phys. Lett., vol. 122, pp. 157–162, 1987.
[27]Hansen, N. and Ostermeier, “Completely Derandomized Self-Adaptation in Evolution Strategies,” Evolutionary Computation 9(2), 159-195, 2001.
[28]Higuchi, T., Tsutsui, S., and Yamamura, M., “Theoretical analysis of simplex crossover for real-coded genetic algorithms.” In Schoenauer, M. et al., editors, Parallel Problem Solving from Nature (PPSN-VI), pages 365–374, Springer, Berlin, Germany, 2000.
[29]Ho S.-Y. and Chen J.-H., “A GA-based systematic reasoning approach for solving traveling salesman problems using an orthogonal array crossover,” High Performance Computing in the Asia-Pacific Region, 2000. Proceedings. The Fourth International Conference/Exhibition on, vol.2, no.pp.659-663 vol.2, 2000.
[30]Ho S.-J., Ho S.-Y, and Shu L.-S., “A Novel Orthogonal Simulated Annealing Algorithm for Optimization of Electromagnetic Problems,” IEEE TRANSACTIONS ON MAGNETICS 40(4), 2004.
[31]Ho S.-Y., Ho S.-J., and Lin Y.-K., “An orthogonal simulated annealing for floorplanning problems,” IEEE Trans. VLSI Syst. 12, 2004.
[32]Holland, J. H., “Outline for a logical theory of adaptive systems,” J. Assoc. Comput. Mach., vol. 3, pp. 297–314, 1962.
[33]Holland, J. H., Adaptation in Natural and Artificial Systems. Ann Arbor, MI: Univ. of Michigan Press, 1975.
[34]Holland, J. H. and Reitman, J. S., “Cognitive systems based on adaptive algorithms,” in Pattern-Directed Inference Systems, D. A. Waterman and F. Hayes-Roth, Eds. New York: Academic, 1978.
[35]J. Yen, J. C. Liao, B. Lee and D. Randolph, A hybrid approach to modeling metabolic systems using a genetic algorithm and simplex method, IEEE Transactions on System, Man, and Cybernetics-Part B: Cybernetics, 28(2), pp. 173-191, 1998.
[36]K. Chellapilla, “Combining mutation operators in evolutionary programming,” IEEE Trans. Evol. Comput., vol. 2, pp. 91–96, Sept 1998.
[37]Kirkpatrick S., Gelatt C. and Vecchi M., “Optimization by simulated annealing,” Science 220(4598), pp. 671-680, 1983.
[38]Koza, JR., Genetic programming: a paradigm for genetically breeding populations of computer programs to solve problems. Technical Report STANCS-90-1314, Department of Computer Science, Stanford University, June 1990.
[39]Koza, JR., Genetic Programming. Cambridge, MA: MIT Press, 1992.
[40]Koza, John R., Bennett, Forrest H. III and Andre, David, Classifying proteins as extracellular using programmatic motifs and genetic programming, Proceedings of the IEEE Conference on Evolutionary Computation, ICEC, pp. 212-217, 1998.
[41]Leung Y.-W. and Wang Y., “An orthogonal genetic algorithm with quantization for global numerical optimization,” IEEE Trans. Evol. Comput. 5, pp. 41–53, 2001.
[42]M. S. Phadke, Quality Engineering Using Robust Design. Englewood Cliffs. NJ: Prentice-Hall, 1989.
[43]Montgomery, D.C., 1984. Design and Analysis of Experiments, John Wiley, New York.
[44]Mitsuo Gen, Runwei Cheng, Genetic Algorithms and Engineering Design, Wiley, New York, 1997.
[45]Ono, I. and Kobayashi, S., “A real-coded genetic algorithm for function optimization using unimodal normal distribution crossover.” In Bäck, T., editor, Proceedings of the Seventh International Conference on Genetic Algorithms (ICGA-7), pages 246–253, Morgan Kaufmann, San Francisco, California, 1997.
[46]P. J. Angeline, “Evolutionary optimization versus particle swarm optimization: Philosophy and performance differences,” in Proc. Evol. Prog. VII, V. W. Porto, N. Saravanan, D. Waagen, and A. E. Eiben, Eds. Berlin, Germany: Springer-Verlag, 1998, pp. 601–610.
[47]P. Siarry, G. Berthiau, F. Durbin, and J. Haussy, “Enhanced simulated annealing for globally minimizing functions of many-continuous variables,” ACM Trans. Math. Software, vol. 23, pp. 209–228, June 1997.
[48]Pai, Ping-Feng, “System reliability forecasting by support vector machines with genetic algorithms”, Mathematical and Computer Modeling, (Ref No. MCM 4969), 2005.
[49]Pierreval, H., Caux, C., Paris J.L. and Viguier, F., “Evolutionary Approaches to the Design and Organization of Manufacturing Systems,” Computers & Industrial Engineering, 44, pp. 339-364, 2003.
[50]Rechenberg, I., Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Stuttgart, Germany: Frommann-Holzboog, 1973.
[51]Rechenberg, I., Evolutionstrategie ’94. Frommann-Holzboog, Stuttgart, 1994.
[52]S. H. Park, Robust Design and Analysis for Quality Engineering. Chapman & Hall, 1996.
[53]S. Forrest and M. Mitchell. “Relative buildingblock fitness and the building-block hypothesis,” FOGA-92. Proc. of Workshop on Foundations of Genetic Algorithms and Classifier Systems, 1992, pp.109-126.
[54]Schwefel, H.-P., “Kybemetische evolution als strategie der experimentellen forschung in der strmungstechnik,” Diploma thesis, Technical Univ. of Berlin, 1965.
[55]Schwefel, H.-P., Numerical Optimization of Computer Models. Chichester: Wiley, 1981.
[56]Schwefel, H.-P., Evolution and Optimum Seeking, Wiley , New York, 1995.
[57]Schwefel, H.-P.,and Rudolph, G., “Contemporary evolution strategies,” in Advances in Artificial Life. 3rd Int. Conf. on Artificial Life (Lecture Notes in Artificial Intelligence, vol. 929), F. Mor´an, A. Moreno, J. J. Merelo, and P. Chac´on, Eds. Berlin, Germany: Springer, pp. 893–907, 1995.
[58]Schwefel, H.-P. “Collective intelligence in evolving systems,” in W. Wolff, C. J. Soeder and F. Drepper (Eds), Ecodynamics – Contributions to Theoretical Ecology, pp. 95-100. Berlin: Springer, 1987a.
[59]Schwefel, H.-P., Evolution and Optimum Seeking. New York: Wiley, 1995 (Sixth-Generation Computer Technology Series).
[60]Schwefel, H.-P. and Bäck, T. Artifical evolution: How and why? In D. Quagliarella, J. Périaux, C. Poloni and G. Winter (Eds), Genetic Algorithms an Evolution Strategies in Engineering an Computer Science: Recent Advances and Industrial Applications, pp. 1-19. Chichester, UK: Wiley, 1998.
[61]Schwefel, H.-P.,and Rudolph, G., “Contemporary evolution strategies,” in Advances in Artificial Life. 3rd Int. Conf. on Artificial Life (Lecture Notes in Artificial Intelligence, vol. 929), F. Mor´an, A. Moreno, J. J. Merelo, and P. Chac´on, Eds. Berlin, Germany: Springer, 1995, pp. 893–907.
[62]Shu L.-S., Ho S.-Y., and Ho S.-J., “OSA: Orthogonal Simulated Annealing Algorithm and Its Application to Designing Mixed H2/H Optimal Controllers,” IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS 34(5), 2004.
[63]X. Yao and Y. Liu, “Fast evolution strategies,” in Evolutionary Programming VI, P. J. Angeline, R. Reynolds, J. McDonnell, and R. Eberhart, Eds. Berlin, Germany: Springer-Verlag, 1997, pp. 151–161.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top