臺灣博碩士論文加值系統

本論文的第一個主題是以Nelder-Mead (NM)搜尋法與粒子群集最佳化 (PSO)為基礎的一個整合性搜尋法，稱為NM-PSO，用來處理無限制式最佳化的問題。由20個測試方程式的比較結果可知，NM-PSO搜尋法對Nelder- Mead搜尋法和粒子群集最佳化所做的修正，可以快且正確地收斂到最佳解。因此NM-PSO演算法可應用在解影像分割的兩個方法：(1) Otsu方法與 (2) Gaussian 曲線配適法。我們測試了六個影像例子且比較三個不同的方法：Otsu方法；NM-PSO-Otsu法和NM-PSO-Curve方法。實驗結果可知NM-PSO-Otsu比Otsu方法更有效率地決定多階層分隔界定值，NM-PSO-Curve比Otsu方法可以提供比較好的視覺效果及物體大小的辨識。
本論文的第二個主題是修正Nelder-Mead 搜尋法使它更適用於處理隨機最佳化的問題，簡稱NM+SPC。NM+SPC主要精神是整合原來的Nelder-Mead 搜尋法與統計品質管制裡的變異數統計量，藉以估計與控制反應值的干擾項。由一系列的模擬結果，可知NM+SPC比近期發展的其他修正Nelder-Mead 搜尋法，更有效處理隨機最佳化問題；同樣地，此新方法可以視為一個有用的工具，可為存在許多不確定性的半導體製造環境，決定最佳的程序配適。最後由化學機械平坦化(CMP)實驗結果可證實，NM+SPC方法可有效控制每個批次的晶圓產出在一定的目標要求上。

The first topic of this dissertation is concerned with a hybrid, unconstrained optimization algorithm based on Nelder-Mead simplex method (NM) and particle swarm optimization (PSO). The hybrid NM-PSO incorporates concepts from the NM and PSO, and is very easy to implement in practice and does not require gradient computation. A modification made to both Nelder-Mead simplex method and particle swarm optimization succeeds in producing faster and more accurate convergence, as born out by empirical evaluations of a suit of 20 test functions. The new algorithm proves to be extremely effective and efficient at locating best-practice optimal solutions. Therefore, the hybrid optimization scheme is applied to problems involving multiple thresholding by the criteria of (1) Otsu’s minimum within-group variance and (2) Gaussian function fitting. Six example images are used to test and illustrate the three different methods: the Otsu’s method; the NM-PSO-Otsu method and the NM-PSO-Curve method. The experimental results show that the NM-PSO-Otsu could expedite the Otsu’s method efficiently to a great extent in the case of multilevel thresholding, and that the NM-PSO-Curve method could provide better effectiveness than the Otsu’s method in the context of visualization, object size and image contrast.
The second topic, an enhanced NM, is proposed in this dissertation to explore the terrains of empirical (or experimental) optimization adaptively where the known response surface function is contaminated by white-noise errors. Modifications to basic operations of NM are made primarily according to some statistical process control (SPC) statistics used in estimating response variation and confidence bands for mean responses. A series of graphical illustrations are presented to give insight into the way the new simplex-search-type approach accurately anchors the true optimum point in noisy environments. As evidenced by a wide variety of simulation studies on the published response functions, the new method proves to perform much better than two recent modifications of NM in solution quality when applied to the stochastic response surface optimization problems. As such, the new method could serve as a useful tool for process recipe optimization in noisy semiconductor manufacturing environments. Finally, the chemical mechanical planarization (CMP) process, a turnkey process during semiconductor fabrication, is simulated from batch to batch based on the real-data equipment model and the presented algorithm is employed to seek the optimal recipe profile while processing each batch of wafers sequentially through the CMP tool.

摘要……………………………………………………………… i
Abstract………………………………………………………….. ii
Acknowledgements……………………………………………… iv
List of Tables…………………………………………………… vii
List of Figures………………………………………………… ix
Chapter 1. Introduction……………………………………… 1
1.1 Motivation……………………………………………… 1
1.2 Research Goals……………………………………… 3
1.3 Organization of the Dissertation………………… 4
Chapter 2. Nelder-Mead Simplex Search Method and Particle
Swarm Optimization……………………………… 6
2.1 Optimization………………………………………………6
2.2 The Nelder-Mead Simplex Method (NM)……………… 9
2.3 Particle Swarm Optimization (PSO)………………… 14
2.3.1 The Guaranteed Convergence Particle Swam Optimizer
(GCPSO)…………………………………….. 19
2.4 Nelder-Mead Simplex Method vs. Particle Swarm
Optimization……………………………………………. 22
Chapter 3. A Hybrid Simplex Search and Particle Swarm
Optimization for Unconstrained Optimization……… 23
3.1 Overview……………………………………………… 23
3.2 Hybrid NM-PSO Method………………………………… 25
3.2.1 The Structure of Our NM-PSO Hybrid………. 25
3.2.2 The Modified Simplex Search Method……….. 28
3.2.3 The Modified PSO Method……………………… 28
3.3 Computational results………………………………. 33
3.3.1 Design of Experiments………………………… 33
3.3.2 Sensitivity Analysis of NM-PSO Parameters 35
3.3.3 Empirical Results……………………………… 40
3.4 Application of NM-PSO to Optimal Multi-Thresholding in
image segmentation……………………………………… 48
3.4.1 Parametric and Nonparametric Approaches… 49
3.4.2 Simplified Version of the Hybrid NM-PSO…. 52
3.4.3 Experimental Results…………………………. 53
3.5 Conclusions……………………………………………. 64
Chapter 4. Stochastic Response Surface Optimization via an
Enhanced Nelder-Mead Simplex Search Procedure… 67
4.1 Overview………………………………………………… 67
4.2 Modified Nelder-Mead Simplex Search (NM+SPC)…. 69
4.3 Computational Comparisons of Simulation Optimization
Procedures……………………………………….. 76
4.3.1 Investigation of Stopping Criterion……… 76
4.3.2 Performance Measures on Stochastic Response Surface
Optimization……………………………………… 79
4.3.3 Computational Experience……………………… 80
4.4 Stochastic Response Surface Optimization……… 86
4.4.1 Numerical Example 1…………………………… 87
4.4.2 Numerical Example 2…………………………… 91
4.4.3 Numerical Examples 3-4………………………… 91
4.4.4 Study of Factorial Experiment by Analysis of
Variance (ANOVA)………………………………… 94
4.4.5 Main ANOVA Results and Interpretations…… 98
4.4.6 Multiple-Comparisons Procedures…………… 99
4.5 Application of NM+SPC for Recipe Qualification of
Semiconductor Manufacturing under Noisy Environments…101
4.5.1 Real-Coded Genetic Algorithm………………. 102
4.5.2 Application to Chemical Mechanical Planarization
Process……………………………………………. 106
4.6 Conclusions……………………………………………… 111
Chapter 5. Conclusion…………………………………………. 114
Bibliography……………………………………………………. 117
Appendix………………………………………………………… 125
作者簡介…………………………………………………………… 129

Balakrishnan, J., Gunasekaran, M. K. and Gopal, E. S. R. (1984). “Critical Dialectric-Constant Measurements in the Binary Liquid System — Methanol + Normal Heptane,” International Journal of PA Physics 22, pp. 286-298.
Battiti, R. and Tecchiolli, G. (1996). “The Continuous Reactive Tabu Search: Blending Combinatorial Optimization and Stochastic Search for Global Optimization,” Annals of Operations Research 63, pp. 53-188.
Barton, R. R. and Ivey J. S., Jr. (1996). “Nelder-Mead Simplex Modifications for Simulation Optimization,” Management Science 42, pp. 954-973.
Bilbro, G.. L. and Snyder, W. E. (1991). “Optimization of Functions with Many Minima,” IEEE Transaction on System, Man and Cybernetics 21, pp. 840-849.
Box, G. E. P. and Hunter, J. S. (1957). “Multi-Factor Experimental Designs for Exploring Response Surfaces,” Annals of Mathematical Statistics 28, pp. 195-241.
Box, M. J. (1966). “A Comparison of Several Current Optimization Methods, and the Use of Transformation in Constrained Problems,” The Computer Journal 9, pp. 67-77.
Brandstatter, B. and Baumgartner, U. (2002). “Particle Swarm Optimization―Mass-Spring System Analogon,” IEEE Transactions on Magnetics 38, pp. 997-1000.
Brooks, S. H. (1959). “A Comparison of Maximum-Seeking Methods,” Operations Research 7, pp. 430-457.
Busing, W. R. and Matsui, M. (1984). “The Application of External Forces to Computational Model of Crystals,” Act Cryst A 40, pp. 532-540.
Castillo, E. Del and Yeh, J. (1998). “An Adaptive Run-To-Run Optimization Controller for Linear and Nonlinear Semiconductor Processes,” IEEE Transactions on Semiconductor Manufacturing 11, pp.285-295.
Chelouah, R. and Siarry, P. (2000). “Tabu Search Applied to Global Optimization,” European Journal of Operational Research 123, pp. 30-44. Special issue on combinatorial optimization.
Chelouah, R. and Siarry, P. (2000). “A Continuous Genetic Algorithm Designed for the Global Optimization of Multimodal Functions,” Journal of Heuristics 6, pp. 191-213.
Chelouah, R. and Siarry, P. (2003). “Genetic and Nelder-Mead Algorithms Hybridized for a More Accurate Global Optimization of Continuous Multiminima Functions,” European Journal of Operational Research 148, pp. 335-348.
Chen, D. H., Saleem, Z. and Grace, D. W. (1986). “ A New Simplex Procedure for Function Minimization,” International Journal of Modeling and Simulation 6, pp. 81-85.
Christie, D. P. and Watson, H. J. (1983). “The Application of Simulation: A Survey of Industry Practice,” Interfaces 13, pp. 47-52.
Clerc, M. and Kennedy, J. (2002). “The Particle Swarm-Explosion, Stability and Convergence in a Multidimensional Complex Space,” IEEE Transactions on Evolutionary Computation 6, pp. 58-73.
Copeland, K. A. F. and Nelson, P. R. (1996). “Dual Response Optimization via Direct Function Minimization,” Journal of Quality Technology 28, pp. 331-336.
Cvijovic, D. and Klinowski, J. (1995). “Taboo Search. An Approach to the Multiple Minima Problem,” Science 667, pp. 664-666.
Dennis, J. E. Jr. and Woods, D. J. (1987). “Optimization on Microcomputers: The Nelder-Mead Simplex Algorithm,” New Computing Environments: Microcomputers in Large Scale Computing, A. Wouk (ED.), SIAM, Philadelphia, PA, pp. 116-122.
Eberhart, R. C. and Kennedy, J. (1995). “A New Optimizer Using Particle Swarm Theory,” Proc. of the Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan, pp. 39-43.
Eberhart, R. C.and Shi, Y. (2001). “Tracking and Optimizing Dynamic Systems with Particle Swarms,” Proc. Congress on Evolutionary Computation, Seoul, Korea, pp. 94-97.
Fan, S. K. (2000). “Quality Improvement of Chemical-Mechanical Wafer Planarization Process in Semiconductor Manufacturing Using a Combined Generalized Linear Modeling-Non-Linear Programming Approach,” International Journal of Production Research 38, pp. 3011-3029.
Fan, S. K. and Zahara, E. (2002). “A Hybrid Simplex Search and Particle Swarm Optimization for Unconstrained Optimization,” Submitted to Europen Journal of Operational Research.
Fan, S. K., Liang, Y. C. and Zahara, E. (2003). “A Hybrid Simplex Search and Particle Swarm Optimization for the Global Optimization of Multimodal Functions.” submitted to Engineering Optimization.
Fletcher, R. (1987). Practical Methods of Optimization, John Wiley & Sons, Chichester.
Glad, T. and Goldstein, A. (1977). “Optimization of Function Whose Values are Subjecy to Small Errors,” BIT 17, pp. 160-175.
Glasbey, C. A. (1993). “An Analysis of Histogram-Based Thresholding Algorithms,” CVGIP: Graphical Models and Image Processing 55, pp. 532-537.
Goldberg, D. E. (1998). Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, New York, NY.
Gonzalez, R. C. and Woods, R. E. (2002). Digital Image Processing. Prentice Hall, Upper Saddle River, NJ.
Grabitech Solutions AB (2001). MultiSimplex Release 2.1 for Windows, Grabitech Solutions AB, Sundsvall, Sweden.
Heppner, F. and Grenander, U. (1990). “A Stochastic Nonlinear Model for Coordinate Bird Flocks,” In: Krasner S (ed) The Ubiquity of Chaos. AAAS Publications, Washington, D.C.
Higashi, N. and Iba, H. (2003). “Particle Swarm Optimization with Gaussian Mutation,” IEEE Proc. on Swarm Intelligence Symposium, Indianapolis, IN, USA, pp. 72-79.
Holland, J. (1975). Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor, MI.
Hooke, R. and Jeeves, T. A. (1961). “Direct Search Solution of Numerical and Statistical Problems,” Journal of Association for Computing Machinery 8, pp. 212-221.
Humphrey, D. G. and Wilson, J. R. (2000). “A Revised Simplex Search Procedure for Stochastic Simulation Response Surface Optimization,” INFORMS Journal on Computing 12, pp. 272-283.
Hu, X. and Eberhart, R. C. (2001). “Tracking Dynamic Systems With PSO: Where’s the Cheese?” Proc. of The Workshop on Particle Swarm Optimization, Indianapolis, IN, USA.
Hu, X. and Eberhart, R. C. (2002). “Adaptive Particle Swarm Optimization: Detection and Response to Dynamic Systems,” Proc. IEEE International Conference on Evolutionary Computation, Honolulu, Hawaii, USA, pp. 1666-1670.
Kapur, J., Sahoo, P. and A. Wong. (1985). “A New Method for Gray-Level Picture Thresholding Using the Entropy of the Histogram,” Computer Vision, Graphics, and Image Processing 29, pp. 273-285.
Kennedy, J. and Eberhart, R. C. (1995). “Particle Swarm Optimization,” Proc. IEEE International Conference on Neural Networks, Piscataway, NJ, USA, pp. 1942-1948.
Khuri, A. I. and Cornell, J. A. (1987). Response Surfaces: Designs and Analyses, Marcel Dekker, New York, NY.
Li, C. H. and Lee, C. K. (1993). “Minimum Cross Entropy Thresholding,” Pattern Recognition 26, pp. 617-625.
Millonas, M. M. (1994). “Swarms, Phase Transitions, and Collective Intelligence,” In: Palaniswami, M.; Attikiouzel, Y.; Marks, R.; Fogel, D.; Fukuda, T.; (eds) Computational Intelligence: A Synamic System Perspective, IEEE Press, Piscataway, N.J, pp. 137-151.
Montgomery, D. C. (2001). Introduction to Statistical Quality Control, 4th ed. Wiley, New York, NY.
Montgomery, D. C. (2001). Design and Analysis of Experiments, 5th ed. Wiley, New York, NY.
Moré, J. J., Garbow, B. S. and Hillstrom, K. E. (1981). “Testing Unconstrained Optimization Software,” ACM Transactions on Mathematical Software 7, pp. 17-41.
Myers, R. H. and Montgomery, D. C. (2002). Response Surface Methodology: Process and Product Optimization Using Designed Experiments, 2nd ed. Wiley, New York, NY, pp. 10-12.
Nash, S. G. and Sofer, A. (1996). Linear and Nonlinear Programming, McGraw-Hill, New York.
Nazareth, L. and Tzeng, P. (2002). “Gilding The Lily: A Variant of the Nelder-Mead Algorithm Based on Golden-Section Search,” Computational Optimization and Applications 22, pp. 133-134.
Nelder, J. A. and Mead, R. (1965). “A Simplex Method for Function Minimization,” The Computer Journal 7, pp. 308-313.
Olsson, D. M. (1974). “A Sequential Simplex Program for Solving Minimization Problems,” Journal of Quality Technology 6, pp. 53-57.
Olsson, D. M. and Nelson, L. S. (1975). “The Nelder-Mead Simplex Procedure for Function Minimization,” Technometrics 17, pp. 45-51.
Otsu, N. (1979). “A Threshold Selection Method for Gray-Level Histogram,” IEEE Transaction on Systems, Man, and Cybernetics. 9, pp. 62-66.
Parkinson, J. M. and Hutchinson, D. (1972). “An Investigation into the Efficiency of Variants on the Simplex Method,” Numerical Methods for Nonlinear Optimization, F. A. Lootsma (Ed.), pp. 115-136.
Rees, L. P., Clayton, E. R. and Taylor, B. W, III (1985). “Solving Multiple Response Simulation Models Using Modified Response Surface Methodology Within a Lexicographic Goal Programming Framework,” IIE Transactions 17, pp. 47-57.
Renders, J. M. and Flasse, S. P. (1996). “Hybrid Methods Using Genetic Algorithms for Global Optimization,” IEEE Transaction on Systems, Man, and Cybernetics-Part B: Cybernetics 26, pp. 243-258.
Reynolds, C. W. (1987). “Flocks, Herds, and Schools: A Distributed Behavioral Model,” Computer Graphics 21, pp. 25-34.
Rosenbrock, H. H. (1960). “An Automatic Method for Finding the Greatest or Least Value of a Function,” Computer Journal 3, pp. 175-184.
Sahoo, P., Soltani, S. and A. Wong. (1988). “A Survey of Thresholding Techniques,” Computer Vision, Graphics, and Image Processing 41, pp. 233-260.
SAS Institute (1998). SAS/IML Software Release 6.12 for Windows, SAS Institute Inc., Cary, NC.
Schulze, W. and Rehder, U. (1984). “Organization and Morphogenesis of the Human Seminiferous Epithelium,” Cellular Tissue Review 237, pp. 395-417.
Shapiro, S. S. and Wilk, M. B. (1965). “An Analysis of Variance Test for Normality,” Biometrika 52, pp. 591-611.
Siarry, P., Berthiau, G.., Durbin, F. and Haussy, J. (1997). “Enhanced Simulated Annealing for Globally Minimizing Functions of Many Continuous Variables,” ACM Transactions on Mathematical Software 23, pp. 209-228.
Silver, G. L. (1981). “Space Modification: An Alternative Approach to Chemistry Problem Involving Geometry,” Journal of Computational Chemistry 2, pp. 478-490.
Smith, S. (1998). “The Simplex Method and Evolutionary Algorithms,” Proc. IEEE International Conference on Evolutionary Computation, pp. 799-804.
Spendley, W., Hext, G. R. and Himsworth, F. R. (1962). “Sequential Application of Simplex Designs in Optimization and Evolutionary Operation,” Technometrics 4, pp. 441-461.
Sthapit, P. R., Ottoway, J. M., and Fell, G. S. (1984). “Determination of Lead in Matural and Tap Waters by Flame Atomic-Fluorescence Spectrometry,” Analyst 109, pp.1061-1075.
Synder, W., Bilbro, G.., Logenthiran, A. and Rajala, S. (1990). “Optimal Thresholding-A New Approach,” Pattern Recognition Letters 11, pp. 803-810.
Tandon, V. (2000). Closing the Gap Between CAD/CAM and Optimized CNC and Milling, Master’s thesis, Purdue School of Engineering and Technology, Indianapolis, IN, USA.
van den Bergh, F. (2001). An analysis of Particle Swarm Optimizers. PhD thesis, Department of Computer Science, University of Pretoria, Pretoria, South Africa.
van den Bergh, F. and Engelbrecht, A. P. (2002). “A New Locally Convergent Particle Swarm Optimizer,” IEEE International Conference on Systems, Man and Cybernetics, pp.96-101.
Walters, F. H., Parker, L. R., Jr., Morgan, S. L. and Deming, S. N. (1991). Sequential Simplex Optimization: A Technique for Improving Quality and Productivity in Research, Development, and Manufacturing, CRC Press, Boca Raton, FL.
Weszka, J. and Rosenfeld, A. (1979). “Histogram Modifications for Threshold Selection,” IEEE Transaction on Systems, Man, and Cybernetics 9, pp. 38-52.
Wilson, E. O. (1975). Sociobiology: The New Synthesis, Belkmap Press, Cambridge, MA.
Wolfram Research (2002). Mathematica/Optimization and Statistics Release 4.2, Wolfram Research Inc., Champaign, IL.
Yin, P. Y. (1999). “A Fast Scheme for Optimal Thresholding Using Genetic Algorithms,” Signal Processing 72, pp. 85-95.
Yen, J., Liao, J. C., Lee, B. and Randolph, D. (1998). “A Hybrid Approach to Modeling Metabolic Systems Using a Genetic Algorithm and Simplex Method,” IEEE Transaction on Systems, Man, and Cybernetics-Part B: Cybernetics 28, pp. 173-191.
Yoshida, H., Kawata, K., Fukuyama, Y. and Nakanishi, Y. (1999). “A Particle Swarm Optimization for Reactive Power and Voltage Control Considering Voltage Stability,” Proc. International Conference on Intelligent System Application to Power Systems, Rio de Janeiro, Brazil, pp. 117-121.
Young, P. (1976). “Optimization in the Presence of Noise-A Guided Tour,” Optimization in Action, (L. C. W. Dixon, ed.), Academic Press, London, pp. 517-573.
Zahara, E. and Fan, S. K. (2003). “Real-Coded Genetic Algorithm for Stochastic Optimization: A Tool for Recipe Qualification of Semiconductor Manufacturing under Noisy Environments,” accepted by International Journal of Advanced Manufacturing Technology.