Nelder-Mead 搜尋法處理無限制式及隨機最佳化問題之研究

A Study of Nelder-Mead Simplex Search Method for Solving Unconstrained and Stochastic Optimization Problems

何怡偉(Erwie Zahara)

指導教授 ： 范書愷

元智大學/工程學院/工業工程與管理學系/博士(2003年)

摘要

本論文的第一個主題是以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方法可有效控制每個批次的晶圓產出在一定的目標要求上。

關鍵字

Nelder-Mead 搜尋法 ； 粒子群集最佳化 ； 無限制式最佳化 ； 隨機最佳化 ； 多階層影像分隔界定值 ； Otsu方法 ； Gaussian 曲線配適法

並列摘要

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.

並列關鍵字

Nelder-Mead simplex method ； particles swarm optimization ； unconstrained optimization ； stochastic optimization ； multilevel thresholding ； the Otsu method ； gaussian curve fitting

參考文獻

Grabitech Solutions AB (2001). MultiSimplex Release 2.1 for Windows, Grabitech Solutions AB, Sundsvall, Sweden.

Khuri, A. I. and Cornell, J. A. (1987). Response Surfaces: Designs and Analyses, Marcel Dekker, New York, NY.

Weszka, J. and Rosenfeld, A. (1979). “Histogram Modifications for Threshold Selection,” IEEE Transaction on Systems, Man, and Cybernetics 9, pp. 38-52.

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.