Surrogate-based optimization with clustering-based space exploration for expensive multimodal problems

This paper presents a surrogate-based global optimization algorithm to solve multimodal expensive black-box optimization problems (EBOPs) with or without expensive nonlinear constraints. Two approximation methods (kriging and quadratic response surfaces, QRS) are used to construct surrogate models, among which kriging can predict multiple promising local optima and QRS can reflect the overall trend of a true model. According to their characteristics, two different optimizers are employed to capture the promising samples on kriging and QRS, respectively. One is the nature-inspired algorithm "Grey wolf optimization (GWO)", which can efficiently find the global optimum of a QRS model. The other one is a multi-start optimization algorithm that can find several different local optimal locations from a kriging model. In addition, the complete optimization flow is presented and its detailed pseudo code is given. In the presented optimization flow, if a proposed local convergence criterion is satisfied, sparsely sampled regions will be explored. Such a space exploration strategy is developed based on the k-means clustering algorithm, which can make search jump out of a local optimal location and focus on unexplored regions. Furthermore, two penalty functions are proposed to make this algorithm applicable for constrained optimization. With tests on 15 bound constrained and 7 nonlinear constrained benchmark examples, the presented algorithm shows remarkable capacity in dealing with multimodal EBOPs and constrained EBOPs.