Spelling suggestions: "subject:"0.402.5 .575 2015eb"" "subject:"0.402.5 .775 2015eb""
1 |
Continuous black-box optimization: samplings and dynamic environments / CUHK electronic theses & dissertations collectionJanuary 2015 (has links)
Numerical optimization is one of the most active research areas and is widely used in science, engineering, economics and industry. In numerical black box optimization, the underlying objective functions, which can be non-differentiable, non-convex, multi-modal and noisy, are unknown to optimization algorithms. At any points in the continuous search space, the first and second order information is not available. Only the objective function values are available by means of function evaluations. The optimization algorithms, which consider these optimization problems as a black box, are designed to find the best solutions in the continuous search space. / This thesis focuses on continuous black box optimization and presents a collection of the novel sampling methods improving the state-of-the-art optimization algorithms. The algorithms are Covariance Matrix Adaptation Evolution Strategies (CMA-ES) and Cooperative Coevolutionary Algorithms (CCEAs). We will also study these algorithms in the dynamic environments where the objective functions change during the course of optimization. It is necessary to understand algorithms’ performances because many real world problems are basically dynamic in nature. Examples of real world problems include but not limited to random arrival of new tasks, machine faults and degradation, climate change, market fluctuation and economic factors. / In the first part of this thesis, two novel sampling methods that improves Evolution Strategies (ES) for continuous black-box optimization will be introduced: halfspace sampling and eigenspace sampling. In Halfspace Sampling, the hyperplane which goes through the current solution separates the search space into two halfspaces: a positive halfspace and a negative halfspace. When a candidate solution is sampled, the sample always lies in the positive halfspace that is estimated by successful steps in the recent iterations. We theoretically derive the log-linear convergence rates of a scale-invariant step size ES when ES are used to optimize spherical functions in finite and infinite dimensions. Halfspace sampling is implemented in a (1+1) CMA-ES, and the resulting algorithm is benchmarked on the Black-Box Optimization Benchmarking (BBOB) testbed. In Eigenspace sampling, the optimization algorithms consider the eigenspace of the underlying objective functions. A candidate solution is always sampled in an eigenspace spanned by eigen-vectors with repeated or clustered eigenvalues. This demonstrates experimentally how eigenspace sampling can improve the CMA-ES for the current benchmark problems, In particular, the CMA-ES that uses eigenspace sampling often performs very well in ill-conditioned problems. / In the second part of this thesis, we will study the CMA-ES, ES and CCEA in dynamic environments. Two new types of individuals that address the dynamic environments will be introduced: 1) random immigrants (RIs) that increase the diversity for the changing environments, and 2) elitist individuals that improve the local convergence to the optima. The resulting algorithms are evaluated on a standard suite of benchmark problems. Superior results are observed when the two types of individuals are used. We also investigate the behavior of three CMA-ES variants, which include an elitist (1+1)-CMA-ES, a non-elitist(μ,λ)-CMA-ES and a sep-CMA-ES. Our experimental results show the simple elitist strategies that include the (1+1)-ES and the (1+1)-CMA-ES generally outperform non-elitist CMA-ES variants. The elitist strategies are robust to dynamic changes with different severites, but performance is worsened when the problem dimensions are increased. In higher dimensions, the performance of elitist and non-elitist variants of CMA-ES are marginally identical. / 「連續函數最優化」乃係研究領域中一項重要之議題。其廣泛被應用於科學、工程、經濟及工業等範籌。於黑箱最優化下,「優化算法」往往未能掌握目標函數之基本特性如可微分性,非凸性,多模態性及雜訊,甚至未能完全準確地使用連續函數之基本第一階及第二階導數。它們只能通過目標函數值來評估優化之進度。因此,設計最佳優化算法實為一個既困難且富挑戰性之研究議題。 / 本論文主要探討「連續函數黑箱最優化」,並提出新穎之抽樣方法,分別為「協方差矩陣適應進化策略」 (CMA-ES) 及「協同進化算法」(CCEAs) ,以改善現時研究領域中最佳之優化算法。本文亦深入了解此算法於動態環境中之優化表現。於應用科學中,如氣候變化,市場波動及經濟因素等等問題於本質上是動態,因此了解它們於動態環境中之優化表現是十分重要。 / 本論文第一部分提出兩種新抽樣方法,分別為「半空間抽樣法」及「特徵空間抽樣法」, 作為提高「進化策略」 (ES) 之最優化表現。一、於「半空間抽樣法」下,連續函數之搜崇空間會被一片超平面分割成兩個半空間,分別是「正半空間」及「負半空間」。當優化算法尋找一個元素時,它每一次會從正半空間里面抽樣。本文由此推算出進化策略在球形函數收斂速度,並將之應用於最先進之(1 十1)CMA-ES,從而測試它在最新之BBOB平台之表現。二、於「特徵空間抽樣法」下,優化算法首先在擁有重複或集群特徵值之特徵空間內抽出一個元素,然後將特徵空間抽樣法應用於CMA-ES。實驗結果發現使用特徵抽樣法能提升CMA-ES在俗稱「病態」函數中之優化表現。 / 本論文第二部分探討三個優化算法—「協方差矩陣適應進化策略」、「高進化策略」及「協同進化算法」於動態環境中之表現。本文提出以兩種新元素作處理動態環境—「隨機元素」(Random Immigrants)及「優生元素」(Elitist)。「 隨機元素」用以增加優化過程中元素之多樣性:「優生元素」則作增強局部優化之收斂速度。另外,本文更使用最新之測試平台評估三個CMA-ES優化算法之表現,包括(1+1) CMA-ES、(μ,λ)CMA-ES及sep CMA-ES。實驗結果證明,簡單精英進化策略,如(1+1)ES及(1+1)CMA-ES,普遍比非精英進化策略更能於動態環境作優化表現。精英進化策略較能應付不同程度轉變之動態環境。相反,當該連續函數之維度增加時,進化策略之優化表現則開始下降。於高維度下,精英CMA-ES及非精英CMA-ES之優化表現大致相同。 / Au, Chun Kit. / Thesis (Ph.D.)--Chinese University of Hong Kong, 2015. / Includes bibliographical references (leaves 200-230). / Abstracts also in Chinese. / Title from PDF title page (viewed on 26, October, 2016). / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only.
|
Page generated in 0.0921 seconds