臺灣博碩士論文加值系統

摘要
比起其他演化式最佳化方法，RNES在適應值的計算上相對的簡單，個體的適應值計算方式是基於個體在各目標下的排名和擁擠程度而定。但RNES在一些參數的設定使用或機制的選用上仍有改善空間，因此本文將嘗試修改、新增演化過程中的參數與機制，希望達到改善演化效率，提供穩定的求解能力。這些修改包括了對重組方式的新增、重組率與突變率的引用、外部菁英族群數量的控制機制改善等，同時也進行題目的測試與效能評估。經過不同類型、目標數的題目測試後，新增或修改後的RNES都有不錯的效率改善與求解能力。
實際上的最佳化問題設計變數大多是受到數量與範圍拘限的離散變數，因此本文還針對RNES設計了三種處理離散變數的方法，另外也引用在其他演化式方法中使用的離散變數處理方法卜瓦松分佈亂數方法共四種方法，使得RNES除了可以處理實數變數之外，還可以同時處理離散變數或是混合離散、整數、連續變數等問題。本文以數個不同複雜程度的題目進行測試，測試的結果顯示，RNES配合本文所提出的三種處理離散變數方法在處理具離散變數或混合變數的最佳化問題上都有不錯的求解能力與效率。

Abstract
Compared with other evolutionary algorithms the fitness computation in multiobjective solver RNES is relatively simple. The fitness is computed based on the ranks and the crowding status of the individual. But the parameter settings and the evolutionary operators still have rooms to improve. This thesis tries to eliminate the drawbacks of RNES to increase the efficiency and capability of finding better solutions. These efforts include adding new recombination operators, introducing mutation probability and recombination probability and simplifying clustering operation. Some problems are used to test modified RNES and the results are satisfactory.
Many real-life optimization problems contain discrete variables and constraints. In addition to previous improvements this thesis also introduces three methods to treat discrete variable problems. Besides those three methods developed in this thesis one method from other paper using random number of Poisson distribution to treat discrete variables is also tested. The RNES with these discrete variables treating methods can solve not only continuous variable problems but also mixed-variable problems. Several test problem with different characteristics are used to test the methods proposed in this thesis. In general the outcomes show the methods proposed indeed can solve those problems efficiently.

目 錄
致謝
中文摘要…………………………..………………………………….i
英文摘要……………………………………………………………...ii
目錄…………………………………………………………………...iii
圖目錄……………………………………………………………....vi
表目錄……………………………………………………………... xv
符號說明………………………………………………………....xvii
第一章 緒論
1.1 前言………………………….………………………………1
1.2 文獻回顧……………………………………………………2
1.3 研究動機與目的……………………………………………5
1.4 研究方法與內容……………………………………………5
第二章 多目標演算法與RNES方法
2.1 多目標最佳化問題概論……………...……………………7
2.2 演化式計算發展概論………….…………………………...13
2.3 演化策略法簡介…………...……………………………..22
2.4 RNES………………………..…………………………….27
第三章 RNES機制和策略之改善與題目測試
3.1 RNES重組機制的新增…………………………….…….33
3.2 無限制條件單目標最佳化測試問題…………...………..35
3.3 無限制條件多目標最佳化測試問題…………………….49
3.4 重組率與突變率的使用測試……………………………100
3.5 外部菁英族群數量控制方法的改善…..…………………111
第四章 RNES處理離散變數的方法與驗證
4.1 離散變數、離散隨機變數與離散最佳化問題……………125
4.2 RNES處理離散的方式…………………………………...127
4.3 離散變數與混雜變數最佳化的測試題目………………..132
4.4 多目標混雜變數最佳化測試題目……….………………167
4.5 結論………………...……………………………………...178
第五章 結論與未來展望
5.1結論……………………………………………………….180
5.2 未來發展與建議……………………………………….….183
參考文獻…………………………………… ……….………………….184
附錄A 常態分佈(Normal distribution)…………………………..…….190
附錄B 卜瓦松分佈(Poisson distribution)…………………………......194
附錄C Box plot說明…………………………………………………..196

參考文獻
1.俆永勝，“使用演化策略的多目標最佳化演算法”，國立中興大學機械研究所碩士論文，民國92年11月。
2.陳孟成，“求解有限制條件的多目標最佳化問題的演化策略法”，國立中興大學機械研究所碩士論文，民國93年12月。
3.許博傑，“實數編碼與二元編碼遺傳演算法之性能比較研究”，國立台灣科技大學機械研究所碩士論文，民國89年。
4.D. E. Goldberg,“Genetic algorithms in search, optimization, and machine learning, ” Addison-Wesley, Reading, MA, 1989.
5.K. Deb, “Multi-Objective Optimization using Evolutionary Algorithms, ” John Wiley & Sons, Chichester, U.K, 2001.
6.T. Bäck, U. Hammel, and H.-P. Schwefel, “Evolutionary computation: Comments on the history and current state,” IEEE Transactions on Evolutionary Computation, Vol. 1, NO. 1, pp. 3-17, 1997.
7.R. Toakley, “Optimum design using available sections,” J Struct Div ASME, 94, pp. 1219-1241, 1968.
8.J. Bauer, W. Gutkowski, Z. Iwanow, “A discrete method for lattice structures optimization,” Engng Optim, Vol. 5, NO. 2, pp. 121-127, 1981.
9.A. B. Templeman, D. F. Yates, “A segmental method for the discrete optimum design of structures,” Engng Optim,Vol. 6, NO. 3, pp. 145-155, 1983.
10.M. Z. Duan, “An improved Templeman's algorithm for the optimum design of trusses with discrete member sizes,” Engng Optim,Vol. 9, pp. 303-312, 1986.
11.S. Chai, H. C. Sun, “Difference quotient algorithm for finding the feasible set of (0,1) programming of optimum design of structures with discrete design variables ,” J Dalian Univ Tech, 35, pp. 612-617, 1995.
12.D. F. Yates, A. B. Templeman, T. B. Boffey, “The complexity of procedures for determining minimum weight trusses with discrete member sizes ,” International Journal of Solids and Structures, Vol. 18, NO. 6, pp. 487-495, 1982.
13.U. T. Ringertz, “On methods for discrete structural optimization,” Engng Optim Vol. 13, pp. 47-64, 1988.
14.C. P. Pantelides, S. R. Tzan, “Optimal design of dynamically constrained structures,” Computers and Structures, Vol. 62, NO. 1, pp. 141-149, 1997.
15.C. J. Shih, “Fuzzy and improved penalty approaches for multiobjective mixed-discrete optimization in structural systems,” Computers and Structures, Vol. 63, NO. 3, pp. 559-565,1997.
16.J. B. Cai, G. Thiereut, “Discrete optimization of structures using an improved penalty function method,” Engineering Optimization, Vo. 21, NO. 4, pp. 293-306, 1993.
17.E. Salajegheh, G. N. Vanderplaats, “Optimum design of trusses with sizing and shape variables, ” Struct. Optim, Vol. 6, pp. 79–85, 1993.
18.R. K. Kincaid, S. L. Padula, “Minimizing distortion and internal forces in truss structures by simulated annealing, ” AIAA-90-1095-CP, pp. 327–333, 1990.
19.M. Bremicker, PY. Papalambros , HT. Loh, “Solution of mixed-discrete structural optimization problems with a new sequential linearization algorithm,” Comput Struct, Vol. 37, pp. 451-461, 1990.
20.D. S. Juang, Y. T. Wu and Chang, “Optimum Design of Truss Structures, ” Journal of the Chinese Institute of Engineers, Vol. 25, NO. 6, pp. 755-766, 2003.
21.M. Galante,“Genetic algorithms as an approach to optimize real-world trusses, ” Int J Numer Meth Eng, Vol. 39, pp. 361–82, 1996.
22.MR. Ghasemi, E. Hinton, RD. Wood,“Optimization of trusses using genetic algorithms for discrete and continuous variable, ” EngComputat, Vol. 16, NO. 3, pp. 272–301, 1999.
23.J. Cai,“Discrete optimization of structures under dynamic loading using sequential and parallel evolution strategies, ” doct oral dissertation, Department of Civil Engineering, University of Essen, Germany.
24.F. Y. Edgeworth, “Mathematical Psychics: An Essay on the Application of Mathematics to the Moral Sciences,” 1881.
25.V. Pareto, “ Cours d’Economie Politique,” F. Rouge, Lausanne,1896
26.K. C. Tan, T. H. Lee, E. F. Khor, “ Evolutionary algorithms for multi-objective optimization: Performance assessments and comparisons,” Artificial Intelligence Review, Vol. 17, NO. 4, pp. 253-290, June 2002.
27.C. M. Fonseca and P. J. Fleming, “An Overview of Evolutionary Algorithm in Miltiobjective Optimization,” Evolutionary Computing , Vol 3, NO. 1, pp. 1-16, 1995.
28.J. David Schaffer,“Multiple Objective Optimization with Vector Evaluated Genetic Algorithms, ” Genetic Algorithms and Their Applications: Proceedings of the First International Conference on Genetic Algorithms, London: Lawrence Erlbaum, pp. 93-100, 1985.
29.N. Srinivas and K. Deb, “Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms,” Evolutionary Computation , Vol. 2, NO. 3, pp. 221-248, Fall 1994.
30.J. Horn, N. Nafpliotis, and D. E. Goldberg,“A Niched Pareto Genetic Algorithm for Multiobjective Optimization, ” Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence, 1994.
31.E. Zitzler and L. Thiele,“Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach, ” IEEE Transactions on Evolutionary Computation, Vol. 3, NO. 4, pp. 257-271, November 1999.
32.I. Rechenberg, “Evolutionsstrategie: Optimierung technisher Systeme nach Prinzipien der biologischen Evolution, ” Frommann-Holzboog Verlag, Stuttgart, 1973.
33.T. Bäck, “Evolutionary Algorithms in Theory and Practice, ” Oxford University Press, September 1995.
34.X. Yao and Y. Liu, “Fast Evolution Strategies ,” Control and Cybernetics, Vol. 26, NO. 3, pp. 467-496, 1997.
35.K. Ohkura, Y. Matsumura and K. Ueda, “Robust Evolution Strategies ,” Applied Intelligence, Vol. 15, Issue 3, pp. 153-169, 2001
36.J. D. Knowles, and D. W. Corne, . “The Pareto Archived Evolution Strategy: A New Baseline Algorithm for Pareto Multiobjective Optimization, ” In CEC’99: Proceedings of the 1999 Congress on Evolutionary Computation, pp. 98–105, IEEE Service Center, Piscataway, New Jersey
37.H.-P. Schwefel, “Numerische Optimierung von Computer-Modellen mittels der Evolutionsstrategie, ” Interdisciplinary systems research, Birkhauser, Vol. 26, 1977.
38.H.-P. Schwefel, “Numerical Optimization of Computer Models, ” John Wiley&Sons Ltd, Chichester, U.K, 1977.
39.F. Kursawe, “Toward Self-adaping Evolution Strategies,” Proc. Of 2nd IEEE Conference Evolutionary Computation, pp. 283-288, 1995.
40.T. Bäck, “An Overview of Evolutionary Algorithms for Parameter Optimization, ” Evolutionary Computation, Vol. 1, NO. 1, pp. 1-24, 1993.
41.A. E. Eiben and T. Bäck, “Empirical Investigation of Multiparent Recombination Operator in Evolution Strategies,” Evolutionary Computation, Vol. 5, NO. 3, pp. 347-365, 1998.
42.T. Bäck and A. E. Eiben, “Generalizations of intermediate recombination in Evolution Strategies,” Pro. Of Congress on Evolutionary Computation(CEC'99), pp. 1566-1573, 1999.
43.H.-P. Schwefel, “Collective phenomena in evolutionary systems,” In P. Checkland and l. Kiss. Editors, Problems of constancy and Change the Complementarity of Systems Approaches to Complexity ,Papers parented at the 31st Annual Meeting of the lnt’l Soc. For General System Research, Vol. 2, pp. 1025-1033, 1987.
44.K.–H. Liang, X. Yao, Y. Liu, C. Newton and D. Hoffman, “An Experimental Investigation of Self-adaptation in Evolutionary Programming,” Proc. Of the Seventh Annual Conference on Evolutionary Programming, Lecture Note in Computer Science, Vol. 1447, Springer-Verlag, Berlin, pp. 291-300.
45.K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A Fast and Elitist Multiobjective Genetic Algorithm: NSGA--II,” IEEE Transactions on Evolutionary Computation, Vol. 6, NO. 2, pp. 182-197, April 2002.
46.C. M. Fonseca and P. J. Fleming, “Multiobjective optimization and multiple constraint handling with evolutionary algorithms—Part II: Application example,” IEEE Trans. Syst., Man, Cybern. A, Vol. 28, pp. 38–47, Jan. 1998.
47.C. Poloni, “Hybrid GA for multiobjective aerodynamic shape optimization,” in Genetic Algorithms in Engineering and Computer Science, G. Winter, J. Periaux, M. Galan, and P. Cuesta, Eds. New York: Wiley, pp. 397–414, 1997.
48.F. Kursawe, “A variant of evolution strategies for vector optimization,” in Parallel Problem Solving from Nature, H.-P. Schwefel and R. Männer, Eds. Berlin, Germany: Springer-Verlag, pp. 193–197, 1990.
49.S. Rajeev and C. S. Krishnamoorthy, “Discrete Optimization of Structures Using Genetic Algorithms,” Journal of Structural Engineering, ASCE. , Vol. 118, pp. 1233-1250, 1992.
50.B. Wha, Y. Shang and Z. Wu, “Discrete Lagrangian Method for Optimizing the Design of Multipilerless QMF Filter Banks,” Proc. Int’l Conf. on Application Specific Array Process, IEEE, pp. 529-538, 1997.
51.D. K. Shin, Z. Guardal and O. H. Griffin, “A Penalty Approach for Nonlinear Optimization with Discrete Design Variables,” Engineering Optimization, Vol. 16, pp. 29-42.
52.J. Obalek, “Rekombinationsoperatoren fuer Evolutionsstrategien,” Diploma Thesis, Department of Computer Science, University of Dortmund, 1994.
53.J. Cai and G. Thierauf, “Discrete structural optimization using evolution strategies,” in Topping, B.H.V. and Khan, A.I. (Eds), Neural Networks and Combinatorial in Civil and Structural Engineering, Civil-Comp Limited, pp. 95-100, 1993
54.C. J. Shih, Y. C. Yang, “Generalized Hopfield network based structural optimization using sequential unconstrained minimization technique with additional penalty strategy,” Advance in Engineering Software，Vol. 33, NO. 7-10, pp. 721-729, 2002.
55.W. H. Tong, G. R. Liu, “An optimization procedure for truss structures with discrete design variables and dynamic constraints,” Computers and Structures, Vol. 79, NO. 2, pp. 155-162, 2001.
56.X. Yao, “Global Optimization by Evolutionary Algorithms,” Proceedings of the second IEEE Aizu International Symposium on Parallel Algorithms and Architecture Synthesis, pp. 282-291, 1997.
57.J.-H. Zhang, X.-H. Xu, “An Efficient Evolutionary programming Algorithm,” Computers and Operations Research, Vol. 26, pp. 645-663, 1999.
58.J. Cai and G. Thierauf, “Evolution Strategies for Solving Discrete Optimization Problems,” Advances in Engineering Software, Vol. 25, pp. 177-183, 1996.
59.J. Cai and G. Thierauf, “Discrete Optimization of Structures Using an Improved Penalty Function Method,” Engineering Optimization, Vol. 21, pp. 293-306, 1993.
60.M. Galante, “Genetic Algorithms as an Approach to Optimize Real-World Truess,” International Journal for Numerical Methods in Engineering, Vol. 39, pp. 361-382, 1996.
61.A. Osyczka, “Multicriteria optimization for engineering design,” Design Optimization, Academic Press, pp. 193-227, 1985.
62.J. E. Fieldsend, R. M. Everson, and S. Singh, “Using Unconstrainted Elite Archives for Multiobjective Optimization,” IEEE Transaction on Evolutionary Computation, 7(3), pp. 305-323, June 2003.
63.J. Knowles and D. Corne, “ Properties of an Adaptive Archiving Algorithm for Storing Nondominated Vectors,” IEEE Transaction on Evolutionary Computation, 7(2), pp. 100-116, April 2003.
64.G. E. P. Box and M. E. Muller, “A note on the generation of random normal deviates,” Annals Math. Stat, 29, pp. 610-611, 1958.
65.J. M. Chambers, “Graphical Methods for Data Analysis,” CRC Press, Wadsworth, 1983.