This BEACON Researchers at Work blog post is by Dr. Shuwei Zhu, Prof. Lihong Xu, Prof. Erik D Goodman and Dr. Zhichao Lu.
Prof. Lihong Zu and Prof. Erik D. Goodman
BEACON’s Greenhouse research team, led by Prof. Lihong Xu (from Tongji University, China) and Prof. Erik D Goodman, has been doing work on BEACON’s international collaboration projects to model, optimize and control for the microclimate inside greenhouse with the aid of evolutionary techniques. We explore the capabilities of evolutionary algorithms for solving problems with multiple conflicting objectives and started from adapting some Multi-Objective Evolutionary Algorithms (MOEAs), including NSGA-II developed by a senior BEACONite—Prof. Kalyanmoy Deb, to explicitly tradeoff the greenhouse production and the associated energy cost. This strategy worked pretty well until we tried to take more objectives (such as the control precision) into our consideration, as the effectiveness of Pareto-dominance-based MOEAs deteriorates progressively as the number of objectives in the problem, given by M, grows.
It has been widely-believed that, the above issue is mainly due to the poor discriminability of Pareto optimality in many-objective spaces (typically M≥4). To be specific, solutions become incomparable which induced by the loss of Pareto-based selection pressure toward the true Pareto front (PF). As a consequence, research efforts have been driven in the general direction of developing solution ranking methods that do not rely on Pareto dominance (especially decomposition-based techniques), which can provide sufficient selection pressure. However, it is still a nontrivial issue for many existing non-Pareto-dominance-based evolutionary algorithms to deal with unknown irregular Pareto front shapes. For example, it is known that the performance of decomposition-based algorithms strongly depends on the Pareto front (PF) shapes, since the predefined set of weight directions plays a primary role in the performance of decomposition-based algorithms. Compared to decomposition-based methods, the performance of Pareto-dominance-based MOEAs is less related to the PF shapes.
To tackle the scalability problem of Pareto-based MOEAs, in our previous work [1] the generalization of Pareto optimality (GPO) was proposed to better discriminate among solutions. It can guarantee the identity of expanding the dominance area to improve selection pressure, but only at the cost of introducing some difficulty in diversity maintenance. Usually, excessive selection pressure tends to cause diversity maintenance to deteriorate, for example, it may lead the population to converge into a subregion (or several small subregions) of the PF; while excessive diversity pressure may result in degraded convergence performance. So the GPO still has difficulty to maintain the delicate balance between convergence and diversity.
Hence, a new many-objective evolutionary algorithm based on the generalization of Pareto optimality (GPO) is proposed, which is simple, yet effective, in addressing many-objective optimization problems. The proposed algorithm [2] used an “(M-1)+1” framework of GPO dominance, (M-1)-GPD for short, to rank solutions in the environmental selection step, in order to promote convergence and diversity simultaneously. To be specific, we apply M symmetrical cases of (M-1)-GPD, where each enhances the selection pressure of M-1 objectives by expanding the dominance area of solutions, while remaining unchanged for the one objective left out of that process. For clearer understanding, Fig. 1 shows a graphical explanation of (M-1)-GPD in the original f1-f2 space and the indirect objective spaces f1-Ω2 (blue) and Ω1-f2 (green).
Fig. 1. Pictorial illustration of a two-dimensional objective space and the shrunken space after performing two (M-1)-GPD cases. (a) The original f1-f2 objective space; (b) The two indirect f1- Ω2 (blue) and Ω1-f2 (green) objective spaces (also the two contracted spaces inside) after generalization.
Given an expanding angle φ, for solution P the f1 objective remains unchanged while f2 expands by φ degrees, i.e., “M-1″ is related to f2 and “1” is for f1, such that ⋀P φ(1) depicts the coverage of its dominance envelope. Correspondingly, the case of f1-“M-1” and f2-“1” is presented for solution Q, and ⋀Q φ(2) shows its dominating envelope. In the case of ⋀P φ(1), the contracted blue space f1– f2 (inside axes f1 and Ω2) is obtained; while for dominating envelope ⋀Q φ(2), we have the contracted green space f1– f2 (inside axes Ω1 and f2), as shown in Fig. 1b. Moreover, the difference is clearly visible, marked in light gray–—i.e., the coverage of the true PF (bold PQ curve in Fig. 1a) in the original f1– f2 space and of the two partial generalized Pareto fronts (shown by the green arc of P‘ and the blue arc of Q‘, respectively, in Fig. 1b). In fact, a larger φ is likely to lower the coverage of the true PF. When φ reaches its maximum, the two transformed objective spaces will be close to the hyper-lines, such that only two extreme solutions left in each of the extreme case, respectively.
The proposed (M-1)-GPD scheme is nearly parameterless and is used in a novel many-objective evolutionary algorithms (MaOEA), that is, multiple (M-1)-GPD-based optimization, called MultiGPO for short, which shows competitive performance compared with several state-of-the-art MaOEAs. Moreover, Fig. 2 shows the comparison of conventional Pareto dominance, GPO and MultiGPO. In conventional Pareto dominance, the Percentage of the better region is 1/2M, which is based on the value of M, such that the convergence deteriorates with insufficient selection pressure. It is obvious that GPO losses diversity by enhancing dominance area. However, the diversity of population is poor (in this case) and the parameter φ should be dynamically tuned generation by generation, leading to the impractical usage of GPO in applications. For our MultiGPO algorithm, the convergence and diversity can be balanced well, and the parameter φ is set based on the value of M that is fixed during optimization. Moreover, since no reference vectors are employed, the performance of MultiGPO is less dependent on the PF shapes than methods using reference vectors, and is robust, especially in solving problems having irregular PFs. The scheme validation was performed on some benchmark functions with different types of known PFs (e.g., concave, convex, and disconnected), and real-world problems with irregular PFs. For most problems, a relatively complete set of solutions could always be acquired by MultiGPO, and it can obtain overall better performance than some other state-of-the-art methods.
Fig. 2. Comparison of the conventional Pareto dominance, GPO and MultiGPO
To enhance understanding, we illustrate the (M-1)-GPD ranking method on a set of candidate solutions of a bi-objective minimization problem, as shown in Fig. 3, where (a) depicts the case of GPOf1, while (b) is for GPOf2. The ten circles (labeled from A to J) denote the non-dominated solutions of this problem, as analogous to those obtained on an MaOP, which are usually incomparable. In Fig. 3a, solutions B, C, D, I, J highlighted in blue are ranked in the first order by GPOf1; while Fig. 3b shows that solutions A, B, F, G, H, I (also highlighted in blue) are ranked order 1 according to GPOf2. It is obvious that these two cases are mostly complementary to each other. That is to say, employing GPOf1 or GPOf2 can enhance selection pressure in terms of discriminability, and diversity can be preserved by adopting them simultaneously. Apart from the complementarity of the distinct symmetrical (M-1)-GPD schemes, the max-min distance-based selection also plays a role in maintaining diversity. For example, solution E is accorded a higher rank (>1) by either GPOf1 or GPOf2; however, its density in terms of the max-min distance is better than others. Hence, a priority will be provided to solution E for survival during environmental selection. Moreover, solutions C and D (or F and G) are closer to each other in terms of angular distance. With the max-min distance-based selection, so if C or F is selected, the nearest neighbor D or G can hardly be considered for survival to the next generation.
Fig. 3. An illustration of the (M-1)-GPD ranking method. (a) GPOf1: Objective f1 remains unchanged and f2 expands dominance region; (b) GPOf2: Objective f2 remains unchanged and f1 expands dominance region.
Notes: The main result above has been published in the Journal— IEEE Transactions on Cybernetics, 2021, doi: 10.1109/TCYB.2021.3051078
References:
[1] S. Zhu, L. Xu, , E. D Goodman, and Zhichao Lu. A New Many-Objective Evolutionary Algorithm Based on Generalized Pareto Dominance. IEEE Transactions on Cybernetics, 2021, doi: 10.1109/TCYB.2021.3051078
For more information about this work, you can contact Prof. Lihong Xu at email: xulihong@msu.edu
