Taking both convergence and diversity into consideration, this paper suggests a vector angle-based evolutionary algorithm for unconstrained (with box constraints only) many-objective optimization problems. In the proposed algorithm, the maximum-vector-angle-first principle is used in the environmental selection to guarantee the wideness and uniformity of the solution set. With the help of the worse-elimination principle, worse solutions in terms of the convergence (measured by the sum of normalized objectives) are allowed to be conditionally replaced by other individuals. Therefore, the selection pressure toward the Pareto-optimal front is strengthened. The proposed method is compared with other four state-of-the-art many-objective evolutionary algorithms on a number of unconstrained test problems with up to 15 objectives. The experimental results have shown the competitiveness and effectiveness of our proposed algorithm in keeping a good balance between convergence and diversity. Furthermore, it was shown by the results on two problems from practice (with irregular Pareto fronts) that our method significantly outperforms its competitors in terms of both the convergence and diversity of the obtained solution sets. Notably, the new algorithm has the following good properties: 1) it is free from a set of supplied reference points or weight vectors; 2) it has less algorithmic parameters; and 3) the time complexity of the algorithm is low. Given both good performance and nice properties, the suggested algorithm could be an alternative tool when handling optimization problems with more than three objectives.

We propose a new many-objective evolutionary algorithm with Pareto-adaptive reference points. In this algorithm, the shape of the Pareto-optimal front is estimated based on a ratio of Euclidean distances. If the estimated shape is likely to be convex, the nadir point is used as the reference point to calculate convergence and diversity indicators for individuals. Otherwise, the reference point is set to the ideal point. In addition, the estimation of the nadir point is different from what was widely used in the literature. The nadir point, together with the ideal point, provides a feasible way to deal with dominance resistant solutions, which are difficult to be detected and eliminated in Pareto-based algorithms. The proposed algorithm is compared with state-of-the-art many-objective optimization algorithms on a number of unconstrained and constrained test problems with up to 15 objectives. The experimental results show that it performs better than other algorithms in most of the test instances. Moreover, the new algorithm shows good performance on problems whose Pareto-optimal fronts are irregular (being discontinuous, degenerated, bent or mixed). The observed high performance and inherent good properties (such as being free of weight vectors and control parameters) make the new proposal a promising tool for other similar problems.

Constrained multi-objective optimization abounds in practical applications and is gaining growing attention in the evolutionary computation community. Artificial test problems are critical to the progress in this research area. Nevertheless, many of them lack important characteristics such as scalability and variable dependencies, which may be essential in benchmarking modern evolutionary algorithms. This paper firstly proposes a new framework for constrained test problem construction. This framework splits a decision vector into position and distance variables, and forces their optimal values to lie on a non-linear hypersurface such that the inter-dependencies can be introduced among the position ones and among the distance ones individually. In this framework, two kinds of constraints are designed to introduce convergence-hardness and diversity-hardness respectively. The first kind introduces infeasible barriers in approaching the optima, and at the same time, makes the position and distance variables inter-relate with each other. The second kind restricts the feasible optimal regions such that different shapes of Pareto fronts can be obtained. Based on this framework, we construct 16 scalable and constrained test problems covering a variety of difficulties. Then, in the second part of this paper, we evaluate the performance of some state of the art on the proposed test problems, showing that they are quite challenging and there is room for further enhancement of existing algorithms. Finally, we discuss in detail the source of difficulties presented in these new problems.

A feature model (FM) is a compact representation of the information of all possible products from software product lines. The optimal feature selection involves the simultaneous optimization of multiple (usually more than three) objectives in a large and highly constrained search space. By combining our previous work on many-objective evolutionary algorithm (i.e., VaEA) with two different satisfiability (SAT) solvers, this article proposes a new approach named SATVaEA for handling the optimal feature selection problem. In SATVaEA, an FM is simplified with the number of both features and constraints being reduced greatly. We enhance the search of VaEA by using two SAT solvers: one is a stochastic local search--based SAT solver that can quickly repair infeasible configurations, whereas the other is a conflict-driven clause-learning SAT solver that is introduced to generate diversified products. We evaluate SATVaEA on 21 FMs with up to 62,482 features, including two models with realistic values for feature attributes. The experimental results are promising, with SATVaEA returning 100% valid products on almost all FMs. For models with more than 10,000 features, the search in SATVaEA takes only a few minutes. Concerning both effectiveness and efficiency, SATVaEA significantly outperforms other state-of-the-art algorithms.

In decomposition-based multiobjective evolutionary algorithms, the setting of search directions (or weight vectors), and the choice of reference points (i.e., the ideal point or the nadir point) in scalarizing functions, are of great importance to the performance of the algorithms. This paper proposes a new decomposition-based many-objective optimizer by simultaneously using adaptive search directions and two reference points. For each parent, binary search directions are constructed by using its objective vector and the two reference points. Each individual is simultaneously evaluated on two fitness functions-which are motivated by scalar projections-that are deduced to be the differences between two penalty-based boundary intersection (PBI) functions, and two inverted PBI functions, respectively. Solutions with the best value on each fitness function are emphasized. Moreover, an angle-based elimination procedure is adopted to select diversified solutions for the next generation. The use of adaptive search directions aims at effectively handling problems with irregular Pareto-optimal fronts, and the philosophy of using the ideal and nadir points simultaneously is to take advantages of the complementary effects of the two points when handling problems with either concave or convex fronts. The performance of the proposed algorithm is compared with seven state-of-the-art multi-/many-objective evolutionary algorithms on 32 test problems with up to 15 objectives. It is shown by the experimental results that the proposed algorithm is flexible when handling problems with different types of Pareto-optimal fronts, obtaining promising results regarding both the quality of the returned solution set and the efficiency of the new algorithm.