臺灣博碩士論文加值系統

演化策略利用電腦模擬演化的現象，透過演化計算搜尋複雜問題的最佳解，目前被大量應用在搜尋、最佳化、機器學習、排程、製造系統與醫學應用方面，然而在最佳化問題的求解過程中，如何有效率的搜尋到目標函數的全域最佳解並不是一件容易的事，一般的演化策略由於搜尋目標函數的最佳解的效率取決於突變強度的大小，因此，若演化策略作目標函數最佳解的搜尋時若使用較小的突變強度，在細部搜尋時會較有效率，但若母體落在目標函數平坦區域時其演化效率相對較差，更重要的是，當目標函數為有多重區域解時，若突變強度過小會造成無法跳脫區域解的情況。若使用的突變強度較大，雖然可以跳脫目標函數的區域解，但其整體的搜尋效率會變的相對較差，特別是在靠近最佳解區域作細部搜尋時不易快速的逼近最佳解。
本研究提出的類梯度搜尋演算策略方法(Quasi Gradient Search Evolution Strategy Method; QGSES Method)，主要重點在於母體搜尋最佳解時會應先將周圍的資訊先比較過後，根據母體的梯度向量與母體歷史移動向量判斷子代往最佳解區域逼近的最佳方向與距離，加速演化策略整體的演化速度，進一步提升演化策略的搜尋效率。藉由這樣的機制使整體族群在搜尋時能快速且有效的得到最佳點所在位置的資訊並向附近的區域快速的逼近，以達到快速收斂的目的。
經由實驗驗證的結果顯示，本研究所提出之方法在求解多變數函數有相當好的的收斂效率，特別在有多重區域解的函數中優秀的全域搜尋能力，因此證明本研究所提出的架構擁有優秀的多重區域解函數的全域搜尋能力以及穩定的最佳解收斂效率，是一優良的演算法。

Evolution strategies utilize the computer to simulate the phenomenon of evolution, calculate and search the best solution of complicated problem through evolutionary computation. At present, evolution strategies apply to search, optimization, machine learning, scheduling, manufacturing and medicine application etc. How to search the global optimization solution efficiently in object function is a difficult thing in the process of solving optimization questions. In general, the efficiency of evolution strategies depends on the size of mutation strength. Therefore, when evolution strategies use the small mutation strength to search the optimization solution in object function, it will be relatively efficient in searching the details. But it evolves inefficiency when the parent lands on the smooth area of object function. Moreover, small mutation strength will make the parents to escape the local solution hardly when the object function has multi-local solutions. It can escape the local solution when evolution strategies use the large mutation strength, but it will be relatively efficient in searching as a whole. Especially, it will be difficult to close the optimization solution efficiently when parents approach the region of optimization solution and search the details.
This paper brings up the Quasi Gradient Search Evolution Strategy Method (QGSES Method). The main focal point of QGSES 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. With the method of QGSES, we want to precipitate the whole evolutionary speed and improve the searching efficiency of evolution strategies. In order to achieve the goal of quickly convergence, 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.
The result that proves via the experiment shows that the method of this research institute nice convergence efficiency in multi-variable function and excellent global searching capability in multi-local solutions function. It proves that the architecture of this research have excellent global searching capability in multi-local solutions function and steady convergence efficiency of the optimization solution. It is a nice algorithm of searching.

摘要 I
ABSTRACT II
誌謝 IV
目錄 V
表目錄 VII
圖目錄 VIII
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 1
1.3 研究流程與架構 2
1.4 研究工具 3
第二章 文獻探討 4
2.1 演化理論(EVOLUTIONARY ALGORITHMS)相關文獻 4
2.2.1 演化理論簡介 4
2.2.2 演化理論模型 4
2.2 演化策略(EVOLUTION STRATEGIES; ESS) 6
2.2.1 演化策略簡介 6
2.2.2 天擇(selection) 7
2.2.3 自我適應能力 (Self-Adaptation) 8
2.2.4 重構(recombination) 9
第三章 研究方法 11
3.1 QGSES原理 11
3.2 QGSES系統架構 12
3.3 QGSES演算法 15
3.3.1 QGSES演算法符號說明表 16
3.3.2 QGSES演算法 16
3.4 QGSES與其他演算法的結構比較 21
第四章 數值分析與評估 23
4.1 多變數函數分析 23
4.1.1 函數1：Colville function 23
4.1.2 函數2：Rosenbrock’s function 31
4.1.3 函數3：Shubert function 38
4.1.4 函數4：SinCos function 45
4.1.5 函數5：xsin(1/x) function with 2 variables 52
4.1.6 函數6：xsin(1/x) function with 5 variables 59
4.1.7 函數7：xsin(1/x) function with 10 variables 66
4.2 實驗結論 68
4.2.1 QGSES與其他演算法的搜尋效率比較 68
4.2.2 QGSES與其他演算法的搜尋原理分析 68
第五章 結論與建議 71
5.1 研究總結 71
5.2 後續研究建議 71
參考文獻 73
附錄 與 對QGSES搜尋效率的影響數據 77

[1]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.
[2]Bäck, T., Evolutionary Algorithms in Theory and Practice. New York: Oxford Univ. Press, 1996.
[3]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.
[4]Beyer, H.-G. “Toward a theory of evolution strategies: Self-adaptation,” Evolutionary Computation Journal 3(1), 81-111, 1995b.
[5]Beyer, H.-G., “Toward a theory of evolution strategies: Self-adaptation,” Evolutionary Computation, vol. 3, no. 3, pp. 311–348, 1995.
[6]Cantù-Paz, E ., A summary of research on parallel genetic algorithms. IlliGAL Report No. 95007, University of Illinois at Urbana-Champaign, July, 1995.
[7]Carlos Andrés Peña-Reyes, Moshe Sipper, “Evolutionary Computation in Medicine: an overview,” Artificial Intelligence in Medicine, 19, pp. 1-23, 2000.
[8]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.
[9]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.
[10]Darrell Whitley, L. and Kauth, J., GENITOR: a different genetic algorithm, Proceedings of the 1988 Rocky Mountain Conference on Artifical Intelligence, 1988.
[11]Darrell Whitley, L. and Starkweather, T., “GENITOR II: a distributed genetic algorithm,” Journal of Experimental and Theoretical Artifical Intelligence 2, pp. 189-214, 1990.
[12]Darrell Whitley, L., The GENITOR algorithm and selective pressure: why rank based allocation of reproductive trials is best, in: J. D. Schaffer (Ed.), Proceedings of the Third International Conference on GAs, Morgan Kaufmann, Los Atlos, CA, pp. 116-121., 1989
[13]Deb, K. and Agrawal, R. B., “Simulated binary crossover for continuous search space.” Complex Systems, 9(2):115–148, 1995.
[14]Deb, K., Anand, A. and Joshi, D., “A Computationally Efficient Evolutionary Algorithm for Real-Parameter Optimization,” Evolutionary Computation 10(4), 371-395, 2002.
[15]Dorigo, M., Bonabeau, E. and Theraulaz, G., “Ant algorithm and stigmergy,” Future Generation Computer Systems, 16, pp. 851-871, 2000.
[16]Dorigo, M., Caro, G.D. and Gambarsella, L.M., “Ant algorithms for discrete optimization,” Artificial Life, 5, pp. 137-172, 1999.
[17]Dorigo, M., Maniezzo, V. and Colorni, A., “Positive feedback as a research strategy,” Technology Report 91-016, Politecnico di Milano, 1991.
[18]Dorigo, M. and Maria, L., “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Transactions evolution Computer, 1, pp.53–66, 1997.
[19]Eshelman, L., The CHC adaptive search algorithm. How to have safe search when engaging in nontraditional genetic recombination, in: G. Rawlins (Eds.), FOGA-1, Morgan Kaufmann, Los Atlos, CA, pp. 265-283, 1991.
[20]Eshelman, L. J. and Schaffer, D., Preventing premature convergence in genetic algorithms by preventing incest, in: L. Booker, R. Belew (Eds.), Proceedings of the Fourth International Conference on GAs, Morgan Kaufmann, Los Atlos, CA, 1991.
[21]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.
[22]Fogel, L. J., “Autonomous automata,” Ind. Res., vol. 4, pp. 14–19, 1962.
[23]Fogel, L. J., “On the organization of intellect,” Ph.D. dissertation, University of California, Los Angeles, 1964.
[24]Fogel, L. J., Owens, A. J., & Walsh, M. J., Artificial intelligence through simulated evolution. New York: Wiley, 1966.
[25]Goldberg, D. E., Genetic Algorithms in Search, Optimazation and Machine Learning, Addison-Wesley, Reading, MA, 1989.
[26]Goldberg, D. E., Real-coded genetic algorithms, virtual alphabets, and blocking. Complex Systems 5(2), 139-168, 1991.
[27]Goldberg, D. E., Deb, K. and Korb, B.,Messy genetic algorithms revisited: Nonuniform size and scale. Complex Systems 4(4), pp. 415-444, 1990.
[28]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.
[29]Goldberg, D. E., Korb, B. And Deb, K.,Messy genetic algorithms: Motivation, analysis and first results. Complex Systems 3(5), pp. 493-530, 1989.
[30]Hansen, N. and Ostermeier, A., “Adapting arbitrary normal mutation distributions in evolution strageties: The convariance matrix adaptation.” In Proceedings of the IEEE International Conference on Evolutionary Computation, pp. 312-317, 1996.
[31]Hansen, N. and Ostermeier, “Completely Derandomized Self-Adaptation in Evolution Strategies,” Evolutionary Computation 9(2), 159-195, 2001.
[32]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.
[33]Holland, J. H., “Outline for a logical theory of adaptive systems,” J. Assoc. Comput. Mach., vol. 3, pp. 297–314, 1962.
[34]Holland, J. H., Adaptation in Natural and Artificial Systems. Ann Arbor, MI: Univ. of Michigan Press, 1975.
[35]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.
[36]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.
[37]Koza, JR., Genetic Programming. Cambridge, MA: MIT Press, 1992.
[38]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.
[39]Mitsuo Gen, Runwei Cheng, Genetic Algorithms and Engineering Design, Wiley, New York, 1997.
[40]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.
[41]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.
[42]Rechenberg, I., Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der biologischen Evolution. Stuttgart, Germany: Frommann-Holzboog, 1973.
[43]Rechenberg, I., Evolutionstrategie ’94. Frommann-Holzboog, Stuttgart, 1994.
[44]Schwefel, H.-P., “Kybemetische evolution als strategie der experimentellen forschung in der strmungstechnik,” Diploma thesis, Technical Univ. of Berlin, 1965.
[45]Schwefel, H.-P., Numerical Optimization of Computer Models. Chichester: Wiley, 1981.
[46]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.
[47]Schwefel, H.-P., Evolution and Optimum Seeking. New York: Wiley, 1995 (Sixth-Generation Computer Technology Series).
[48]Schwefel, H.-P., Evolution and Optimum Seeking, Wiley , New York, 1995.
[49]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.
[50]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.
[51]Syswerda, G., “Uniform crossover in genetic algorithms,” Proceedings of the 3rd International Conference on Genetic Algorithms, pp.2-9, 1989.
[52]Yen, J. and B. Lee, ”A simplex genetic algorithm hybrid”, IEEE, pp. 175-180, 1997.
[53]Yen, J., 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 Systems. Man, and Cybernetics, pp. 173-191, 1998.