簡易檢索 / 詳目顯示

回結果列表
研究生： 王東泰
Wang, Dung-Tai
論文名稱： 利用反應曲面輔助DIRECT演算法處理耗時工程計計問題
Surrogate-Assisted DIRECT Algorithm for Optimization Problems with Expensive Engineering Simulations
指導教授： 詹魁元
Chan, Kuei-Yuan
學位類別： 碩士
Master
系所名稱： 工學院 - 機械工程學系
Department of Mechanical Engineering
論文出版年： 2013
畢業學年度： 101
語文別： 英文
論文頁數： 53
中文關鍵詞： 全域最佳解 、德瑞特演算法 、萊布尼常數 、輔助模型 、懲罰函數 、包絡線
外文關鍵詞： global optimization, DIviding RECTangles(DIRECT), Lipschitz constant, surrogate model, penalty function, convex hall
相關次數： 點閱：98  下載：1 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 在處理工程上的設計的問題時，高精確度的電腦模型模擬是一個重要的步驟，然而隨著要求的設計細節越多，電腦要花更長的時間完成運算，如果要將這些高運算成本的電腦模型整合於最佳化程序中，在現實的時間限制下，往往是一個非常大的挑戰。本論文修改一個全域最佳化演算法 DIviding RECTangles (DIRECT)，以期能更廣泛應用在實際的工程設計問題，更能在極少量的演算次數上便可達到理想的最佳化結果。 DIRECT 演算法的概念來自於 Shubert 演算法，Shubert 演算法是利用 Lipschitz 常數來進行最佳化的搜尋，但如何決定 Lipschitz 常數是一個複雜的問題，一旦Lipschitz常數計算有瑕疵，該演算法變化無法收斂。DIRECT 使用不同的方式決定 Lipschitz 常數，取而代之的是在每一個最佳化搜尋迴圈中利用比較局部 (local)與全域 (global) 的特徵，自然的產生一系列 Lipschitz 常數，然而現行的DIRECT有許多使用上的問題，為求空間等份切割而只取終點代表，無法鄰近邊界，對於工程上多數位居邊界的最佳化結果使用上有所限制。再者，現行DIRECT無法針對拘束條件的違反加以量化並斟酌接受其結果，使演算法效率無法提昇。本論文利用反應曲面輔助提出一修正DIRECT演算法，故名為 Surrogate-Assisted DIRECT。我們利用現有樣本建立空間曲面，依序完成子空間最佳化及空間切割的程序，取代本原本 DIRECT 演算法只取中點的特性，確保在子空間最佳化時能得到最近似理論值之結果，提昇整體演算效率。針對非線性拘束條件，我們利用一個來自懲罰 (penalty) 的概念，在每一個最佳化搜尋迴圈時，計算目標函數值及違背限制式的最大違背量來進行篩選以選定之母空間，以確定下一迴圈欲運行的子空間。我們利用現行文獻上15個數學範例進行比較，比較結果呈現出在少量的演算次數下，S.A. DIRECT有比較好的目標函數值，針對有非線性拘束條件的問題，S.A. DIRECT結果更是遠優於原本的 DIRECT 演算法。我們也利用一個皮帶輪系統的工程設計問題來呈現S.A. DIRECT的優勢，此問題的電腦工程模擬單次需耗時12小時以上，這是一般最佳化問題無法完成的任務，使用S.A. DIRECT可成功達成最佳設計，更進一步驗證本篇論文所提出的方法可以進行實際的應用。

    The use of high-fidelity models in the early stages of engineering design ensures accuracy but at the cost of computation. These expensive models present challenges in optimization routines, especially for practical engineering problems with a tight time constraint. This study modifies the global algorithm DIviding RECTangles (DIRECT) to improve engineering designs within a very small number of function evaluations. As an update to the standard Shubert algorithm, DIRECT does not require the calculation of the Lipschitz constant; instead, a set of Lipschitz constants are obtained sequentially by compromising the local versus global characteristics as the algorithm iterates. We use subspace optimum instead of the center as the local characteristic with the aid of surrogate modeling to ensure boundary optimum is obtained. We also use a penalty-inspired filter concept is used to make a trade-off between objective function values and constraint violations during design iteration. Numerical comparisons show that the proposed method gives performance improvements with few function evaluations. With an increase of function counts, the proposed method yields the same outcomes as those of the original DIRECT. A belt-tensioner-pulley design problem is used to demonstrated the applicability of the proposed method to engineering problems.

    中文摘要 . . . . . . . . . . . . . . ii Abstract . . . . . . . . . . . . . iii Œ誌謝 . . . . .. . . . . . . . . . . iv Table of Contents . . . . . . . . v List of Tables . . .. . . . . . . . viii List of Figures . .. . . . . . . . ix List of Symbols . . . . . . . . . xi 1 Introduction and Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Motivation and Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.3 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 DIRECT algorithm and its modifications . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1 DIRECT Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Candidate Identification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.1 Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.2 Modifications to candidate identification . . . . . . . . . . . . . . . . . . 9 2.3 Space Division and Sampling the Center of Subspace . . . . . . . . . . . . . . . 10 2.3.1 Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3.2 Modifications to space division and sampling . . . . . . . . . . . . . . . . 11 2.4 Termination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4.1 Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4.2 Modifications to termination . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.5 Demonstration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.6 DIRECT in constrained optimization . . . . . . . . . . . . . . . . . . . . . . . . 14 2.6.1 Methods to Handle Inequality Constraints . . . . . . . . . . . . . . . . . 14 2.6.2 Methods to Handle Equality constraint . . . . . . . . . . . . . . . . . . . 18 2.7 Other modifications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3 Surrogate-Assisted DIRECT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.1 Algorithm overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2 Candidate identi cation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3 f - g filter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.4 Subspace optimization and division . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.4.1 Subspace optimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.4.2 Subspace division . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.4.3 Extension to Multi-dimensional problems . . . . . . . . . . . . . . . . . . 27 3.5 Special cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4 Numerical Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4.1 Bounds constrained problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 Inequality constrained problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5 Engineering case study : design of a belt-pulley mechanism . . . . . . . . . . . . . . . 44 6 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 6.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 AppendixList of MATLAB Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Personal Communication. . . . . . . . . . . . . . . . . . . . . . . 53

    [1] L.T. Watson and C.A. Baker. A fully distributed parallel global search algorithm. Engi-
    neering Computations, 18:155-169, 2001.
    [2] S. E. Cox, R. T. Haftka, C. A. Baker, B. Grossman, W. H. Mason, and L. T. Watson. A
    comparison of global optimization methods for the design of a high-speed civil transport.
    Journal of Global Optimization, 21:415-433, 2001.
    [3] Z. Mehel-Saodo, S. Bourennane, and C. Fossati. Buried object localization using DIRECT
    algorithm. In Proceedings of the 5th IEEE Sensor Array and Multichannel Signal Process-
    ing Workshop, Darmstadt, Germany, 17-20 July 2005.
    [4] J.D. Gri n and T.G. Kolda. Asynchronous parallel hybrid optimization combing DIRECT
    and GSS. Optimization Methods and Software, 25:719-817, 2010.
    [5] W. Lin, N. Kovvali, and L. Carin. DIRECT algorithm for computation of derivatives of the
    daubechies basis function. Applied Mathematics and Computation, 170:1006-1013, 2005.
    [6] J. He, A. Verstak, L. T. Watson, and M. Sosonkina. Performance Modeling and Analy-
    sis of a Massively Parallel DIRECT-Part 1. Technical report TR-07-01, Department of
    Computer Science, Virginia Polytechnic Institute and State University,Blacksburg, 2007.
    [7] J. He, A. Verstak, L. T.Watson, and M. Sosonkina. Performance modeling and analysis of a
    massively parallel DIRECT-part 2. International Journal of High Performance Computing
    Applications, 23:29-41, 2009.
    [8] Y. Zhang, F. Sun, and H. He. Control strategy optimization for hybrid electric vehicle
    based on DIRECT algorithm. IEEE Vehicle Power and Propulsion Conference, 2008.
    [9] Y. Chang, K. Hung, and S. Lee. Human face detection with neural networks and the
    DIRECT algorithm. Arti cial Life and Robotics, 12(1):112-115, 2008.
    [10] M. C. Bartholomew-Biggs, S. C. Parkhurst, and S. P. Wilson. Using DIRECT to solve an
    aircraft routing problem. Computational Optimization and Applications, 21(3):311-323,
    2002.
    [11] D.R. Jones. The DIRECT global optimization algorithm, volume 1. Kluwer Academic
    Publishers, Dordrecht, The Netherlands, the encyclopedia of optimization edition, 2001.
    [12] H. Zhu and D. B. Bogy. Hard disc drive air bearing design:modi ed DIRECT algorithm
    and its application to slider air bearing surface optimization. Tribology International,
    37(2):193-201, 2004.
    [13] J. M. Gablonsky. Modi cations of The DIRECT Algorithm. PhD thesis, Department of
    Mathematics in North Carolina State University, 2001.
    [14] D.R. Jones, C.D. Perttunen, and B.E. Stuckman. Lipschitzian optimization without the
    lipschitz constant. Journal of Global Optimization, 79(1):157-181, 1993.
    [15] D.E. Finkel and C.T. Keley. An adaptive restart implementation of DIRECT. Technical
    Report CRSE-TR04-30, Center for Research in Scienti c Computation, North Carolina
    State University, Raleigh,NC, 2004.
    [16] D.E. Finkel and C.T. Keley. Additive scaling and the DIRECT algorithm. Journal of
    Global Optimization, 36:597-608, 2006.
    [17] O. Liu. Linear scaling and the DIRECT algorithm. Journal of Global Optimization, 2012.
    [18] N. Goldberg, T. G. Kolda, and A. S. Yoshimura. Concurrent optimization with
    duet:DIRECT using external trial points. Technical Report TSAND2008-5844, Sandia
    National Laboratories, Livermore, CA, 2008.
    [19] Y. D. Sergeyev and D. E. Kvasov. Global search based on e cient diagonal partitions and
    a set of lipschitz constant. Society for Industrial and Applied Mathematics, 16(3):910-937,
    2006.
    [20] J.M. Gablonsky and C.T. Kelley. A locally-biased form of the direct algorithm. Journal
    of Global Optimization, 21:27-37, 2001.
    [21] S. E. Cox, R. T. Haftka, C. A. Baker, B. Grossman, W. H. Mason, and L. T. Watson. A
    comparison of global optimization methods for the design of a high-speedy civil transport.
    Journal of Global Optimization, 21:415-433, 2001.
    [22] J. He, L. T. Watson, N. Ramakrishnan, C. A. Sha er, A. Verstak, J. Jiang, K. Bae, and
    W. H. Tranter. Dynamic data structures for a DIRECT search algorithm. Computational
    Optimization and Applications, 23:5-25, 2002.
    [23] J.S. Arora. Sequential Quadratic Programming: SQP, volume 1. Elsevier Academic Press,
    Dordrecht, The Netherlands, introduction to optimization design edition, 2004.
    [24] D. Krige. A statistical approach to some basic mine valuation problems on the witwa-
    tersrand. Journal of the Chemical, Metallurgical and Mining Society of South Africa,
    52:119-139, 1951.
    [25] C. Noel. The origins of kriging. Mathematical Geology, 22(3):239-252, 1990.
    [26] Test function. http://www-optima.amp.i.kyoto-u.as.jp.
    51

    下載圖示 校內：立即公開
    校外：立即公開
    QR CODE