Multi-objective Bayesian optimization (MOBO) aims to optimize multiple competing objective functions in the expensive-to-evaluate scenario. The Expected Hypervolume Improvement (EHVI) is a commonly used acquisition function for MOBO and shows a good performance. However, the computation of EHVI becomes challenging as the number of objective functions grows. In this paper, we revisit the formulation of EHVI, as well as its multi-point counterpart qEHVI, and derive much simpler analytic expressions for them. The main contributions of this paper include: (1) first formulating EHVI as a particular hypervolume improvement, and thus immediately obtaining a formal proof of its NP-hardness, faster algorithms in both theory and practice, and more results on its derivatives; (2) first obtaining the analytic expressions of qEHVI for any q > 1 and m ≥ 2 where m is the number of objectives; and (3) demonstrating the advantages of our formulation over existing exact and approximation methods for computing EHVI and qEHVI through a large number of numerical experiments.

In the realm of evolutionary multiobjective optimization, the hypervolume indicator serves as a crucial metric for assessing the quality of solution sets. Due to the high costs in hypervolume computation, hypervolume-based optimization algorithms always meet the challenge of finding a certain number of points in a given point set to maximize the hypervolume indicator, especially when there are many objectives. In response, the greedy decremental algorithm for hypervolume subset selection problem (gHSSD) has emerged as a noteworthy alternative. This paper introduces a general algorithm for gHSSD, applicable in any dimensionality above two. The proposed algorithm leverages a space partition tree and incorporates a once-build-multiple-use strategy, effectively reducing time complexity. We prove that the proposed algorithm has a time complexity of O((n-k+n)nd-12logn) where n is the number of points, k is the number of points to be reserved, and d the dimensionality. Theoretically, this complexity is competitive with the current best algorithms for d=3,4 and better than them for all 5≤d≤7. To validate our algorithm, we have conducted extensive tests on various random point sets and multiobjective optimization benchmarks. Experimental results suggest that our implementation is more efficient than or competitive with state-of-the-art algorithms on many instances as n increases for d=3,4.

The hypervolume contribution is widely used in indicator-based multiobjective algorithms. We propose an algorithm to compute exact 4-D hypervolume contributions for a set of n points in O(n32logn) time. Our algorithm improves the currently best time complexity O(n2) by O(nlogn), and it is the first algorithm of subquadratic time for this problem. Our algorithm is built upon a space partition method in computational geometry and a geometric structure called the anchored gradient. We also propose a new space partition strategy to reduce the practical running time and the space overhead of this algorithm. Experimental results on a variety of test instances show that our proposed algorithm performs better than the existing state-of-the-art algorithm especially on point sets with cliff or other irregular properties.

This work is geared toward a real-world manufacturing planning (MP) task, whose two objectives are to maximize the order fulfillment rate and minimize the total cost. More important, the requirements and constraints in real manufacturing make the MP task very challenging in several aspects. For example, the MP needs to cover many production components of multiple plants over a 30-day horizon, which means that it involves a large number of decision variables. Furthermore, the MP task's two objectives have extremely different magnitudes, and some constraints are difficult to handle. Facing these uncompromising practical requirements, we introduce an interactive multiobjective optimization-based MP system in this article. It can help the decision maker reach a satisfactory tradeoff between the two objectives without consuming massive calculations. In the MP system, the submitted MP task is modeled as a multiobjective integer programming (MOIP) problem. Then, the MOIP problem is addressed via a two-stage multiobjective optimization algorithm (TSMOA). To alleviate the heavy calculation burden, TSMOA transforms the optimization of the MOIP problem into the optimization of a series of single-objective problems (SOPs). Meanwhile, a new SOP solving strategy is used in the MP system to further reduce the computational cost. It utilizes two sequential easier SOPs as the approximator of the original complex SOP for optimization. As part of the MP system, TSMOA and the SOP solving strategy are demonstrated to be efficient in real-world MP applications. In addition, the effectiveness of TSMOA is also validated on benchmark problems. The results indicate that TSMOA as well as the MP system are promising.

The computation of hypervolume is a key issue in multiobjective optimization, particularly, multiobjective evolutionary optimization. However, it is NP-hard to compute the exact hypervolume value. Monte Carlo methods have been widely used for approximating the hypervolume. Observing that the basic Monte Carlo method and the fully polynomial-time randomized approximation scheme (FPRAS) suit different solution sets, we propose a combination of these two methods and show that it performs very well on a number of solution sets.

In this paper, we propose a computationally efficient variant of elitist covariance matrix evolution strategy for continuous local search in high dimensional space. It focuses on searching in a low-dimensional subspace expanded by a small number of promising search directions. This leads to the linear internal computational complexity of each iteration, which enables the algorithm to scale to high dimensional problems. We conduct comprehensive experiments to evaluate the parameter sensitivity and the algorithm’s performance. The experimental results validate that the proposed algorithm reduces the running time by a factor of ten, and it can be easily scaled up to n>1000 on a set of commonly used test functions.

The hypervolume and hypervolume contributions are widely used in multiobjective evolutionary optimization. However, their exact calculation is NP-hard. By definition, hypervolume is an m-D integral (where m is the number of objectives). Using polar coordinate, this paper transforms the hypervolume into an (m - 1)-D integral, and then proposes two approximation methods for computing the hypervolume and hypervolume contributions. Numerical experiments have been conducted to investigate the performance of our proposed methods.

Iterative thresholding is a dominating strategy for sparse optimization problems. The main goal of iterative thresholding methods is to find a so-called -sparse solution. However, the setting of regularization parameters or the estimation of the true sparsity are nontrivial in iterative thresholding methods. To overcome this shortcoming, we propose a preference-based multiobjective evolutionary approach to solve sparse optimization problems in compressive sensing. Our basic strategy is to search the knee part of weakly Pareto front with preference on the true -sparse solution. In the noiseless case, it is easy to locate the exact position of the -sparse solution from the distribution of the solutions found by our proposed method. Therefore, our method has the ability to detect the true sparsity. Moreover, any iterative thresholding methods can be used as a local optimizer in our proposed method, and no prior estimation of sparsity is required. The proposed method can also be extended to solve sparse optimization problems with noise. Extensive experiments have been conducted to study its performance on artificial signals and magnetic resonance imaging signals. Our experimental results have shown that our proposed method is very effective for detecting sparsity and can improve the reconstruction ability of existing iterative thresholding methods.

The bias feature is a major factor that makes a multiobjective optimization problem (MOP) difficult for multiobjective evolutionary algorithms (MOEAs). To deal with this problem feature, an algorithm should carefully balance between exploration and exploitation. The decomposition-based MOEA decomposes an MOP into a number of single objective subproblems and solves them in a collaborative manner. Single objective optimizers can be easily used in this algorithm framework. Covariance matrix adaptation evolution strategy (CMA-ES) has proven to be able to strike good balance between the exploration and the exploitation of search space. This paper proposes a scheme to use both differential evolution (DE) and covariance matrix adaptation in the MOEA based on decomposition. In this scheme, single objective optimization problems are clustered into several groups. To reduce the computational overhead, only one subproblem from each group is selected to optimize by CMA-ES while other subproblems are optimized by DE. When an evolution strategy procedure meets some stopping criteria, it will be reinitialized and used for solving another subproblem in the same group. A set of new multiobjective test problems with bias features are constructed in this paper. Extensive experimental studies show that our proposed algorithm is suitable for dealing with problems with biases.

Solving sparse optimization problems via regularization frameworks is the dominant methodology for reconstructing sparse signals in the area of compressive sensing. In recent a few years, the use of multiobjective evolutionary algorithms (MOEAs) for sparse optimization has also attracted some research interests. Under the multiobjective framework, the loss term (error) and the regularization term (sparsity) are treated as two separate objective functions. So far, two popular multiobjective frameworks, NSGA-II and MOEA/D, have been used for sparse optimization. In this paper, we further develop a new MOEA/D variant for sparse reconstruction and sparsity detection, which involves three phases - approximating Pareto front (PF) in a chain order (phase 1) and in a random order (phase 2), and exploiting a knee region (phase 3 - optional). Our experimental results show that our proposed method is more effective than the earlier version of MOEA/D and the HALF solver in sparse signal reconstruction and sparsity detection.

MOEA/D is a decomposition-based multiobjective evolutionary algorithm that has attracted much attention in recent years. Its performance depends on the setting of weight vectors which are used for defining subproblems. In the case of irregular Pareto fronts (e.g, disconnected or degenerated), fixed setting of weight vectors in MOEA/D may not work well. In this paper, we propose an improved MOEA/D with both random and fixed weight vectors. Moreover, an external archive based on a modified ε-dominance strategy is used for storing nondominated solutions found by the proposed algorithm and assisting the generation of random weight vectors. Some experiments have been conducted to verify the efficiency and effectiveness of the improved MOEA/D on benchmark multiobjective test problems with irregular Pareto fronts. The experimental results show that the overall performance of the proposed algorithm is better than baseline MOEA/D and NSGA-II.

It is well-established that the shapes of Pareto-optimal fronts (POFs) can affect the performance of some multiobjective optimization methods. The most well-known characteristics on the shape of POFs are convexity and discontinuity. In this paper, we investigate the construction of multiobjective test problems with complicated POFs, of which its local parts could have mixed dimensionalities. For example, in the case of 3 objectives, some parts of POFs can be 1-D curves while others could be 2-D surfaces. We formulate eight test problems, called CPFT1-8, with such a feature. To study the difficulties of these test problems, we conducted some experiments with two state-of-the-art algorithms MOEA/D and NSGA-II, and analyzed their performances.