Continuous Black-Box Optimization: Samplings and Dynamic Environments

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 blackbox 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 eigenvectors 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 CMAES, 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 (mu, lambda)-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.