18 May 2024 in Complex & Intelligent Systems
As potent approaches for addressing computationally expensive optimization problems, surrogate-assisted evolutionary algorithms (SAEAs) have garnered increasing attention. Prevailing endeavors in evolutionary computation predominantly concentrate on expensive continuous optimization problems, with a notable scarcity of investigations directed toward expensive combinatorial optimization problems (ECOPs). Nevertheless, numerous ECOPs persist in practical applications. The widespread prevalence of such problems starkly contrasts the limited development of relevant research. Motivated by this disparity, this paper conducts a comprehensive survey on SAEAs tailored to address ECOPs. This survey comprises two primary segments. The first segment synthesizes prevalent global, local, hybrid, and learning search strategies, elucidating their respective strengths and weaknesses. Subsequently, the second segment furnishes an overview of surrogate-based evaluation technologies, delving into three pivotal facets: model selection, construction, and management. The paper also discusses several potential future directions for SAEAs with a focus towards expensive combinatorial optimization.
9 February 2023 in IEEE Transactions on Evolutionary Computation
Hypervolume-based evolutionary algorithms have been widely used to handle many-objective optimization problems. In such algorithms, hypervolume-based environmental selection (HVES), which aims at selecting a subpopulation with the maximal hypervolume (HV) from the current population, plays a crucial role in guiding evolution. However, the computation time of HV increases exponentially with the number of objectives, making the HVES task an expensive optimization problem. In this paper, we propose an efficient surrogate-assisted greedy inclusion algorithm to deal with computationally expensive HVES tasks. It uses a lightweight surrogate model, radial basis function network, to replace the most time-consuming calculations. In addition, an L1-norm distance-based filter is performed as a preselection operator to reduce the search space and avoid some unnecessary calculations. Considering the inevitable approximation errors of surrogate models, we also design an online sampling strategy to enhance the reliability of selected solutions. The proposed algorithm is tested on two types of datasets and compared with six state-of-the-art greedy algorithms. Experimental results show that the proposed algorithm performs excellently on most datasets.
22 July 2025 in Nature Machine Intelligence
1 February 2021 in Mathematics of Operations Research
We introduce a unified algorithmic framework, called the proximal-like incremental aggregated gradient (PLIAG) method, for minimizing the sum of a convex function that consists of additive relatively smooth convex components and a proper lower semicontinuous convex regularization function over an abstract feasible set whose geometry can be captured by using the domain of a Legendre function. The PLIAG method includes many existing algorithms in the literature as special cases, such as the proximal gradient method, the Bregman proximal gradient method (also called the NoLips algorithm), the incremental aggregated gradient method, the incremental aggregated proximal method, and the proximal incremental aggregated gradient method. It also includes some novel interesting iteration schemes. First, we show that the PLIAG method is globally sublinearly convergent without requiring a growth condition, which extends the sublinear convergence result for the proximal gradient algorithm to incremental aggregated-type first-order methods. Then, by embedding a so-called Bregman distance growth condition into a descent-type lemma to construct a special Lyapunov function, we show that the PLIAG method is globally linearly convergent in terms of both function values and Bregman distances to the optimal solution set, provided that the step size is not greater than some positive constant. The convergence results derived in this paper are all established beyond the standard assumptions in the literature (i.e., without requiring the strong convexity and the Lipschitz gradient continuity of the smooth part of the objective). When specialized to many existing algorithms, our results recover or supplement their convergence results under strictly weaker conditions.
16 January 2025 in Neural Networks