An Analysis of Control Parameters of MOEA/D Under Two Different Optimization Scenarios

Figure 2 shows the overall performance of MOEA/D with various $\mu$ settings on the 13 problems with $M\in\{2,3,4,5\}$ under (a) the final population scenario and (b) the reduced UEA scenario. It should be noted that results for (a) the final population scenario and (b) the reduced UEA scenario shown in this paper are obtained from the identical MOEA/D runs.

First, we describe results of MOEA/D for the final population scenario shown in Figure 2(a). For $M=2$, while MOEA/D with small $\mu$ values ($\mu\in\{25,50\}$) perform better than that with larger $\mu$ values ($\mu\in\{100,200,300,400\}$) just after the beginning of the search, their APS values gradually deteriorate as the search progresses. When $M$ is increasing, such a tendency is more noticeable. For $M\geq 3$, after several function evaluations, the larger $\mu$ value is used for MOEA/D, the better APS value is achieved. The best performance of MOEA/D is obtained with the largest $\mu$ value ($\mu=406,455,$ and $495$ for $M=3,4,$ and $5$) for $M\geq 3$, and MOEA/D with the smallest $\mu$ value ($\mu=25,28,35,$ and $126$ for $M=2,3,4,$ and $5$) performs worst among all the configurations for all $M$.

Next, the results of MOEA/D for the reduced UEA scenario in Figure 2(b) are described below. In contrast to the results for the final population scenario, MOEA/D with the largest $\mu$ value always shows the worst APS value. For $M\in\{2,3\}$, small $\mu$ values ($\mu\in\{50,100\}$ and $\mu\in\{55,105\}$, respectively) are suitable for MOEA/D at any time. For $M\in\{4,5\}$, MOEA/D with a small $\mu$ value also shows a good performance within a short period. After several function evaluations, MOEA/D with $\mu=120$ and $\mu\in\{210,330\}$ outperform other configurations on the four- and five-objective MOPs, respectively.

Figure 3 shows the anytime performance of MOEA/D with various $\mu$ settings on the WFG4 problem with $M\in\{2,3,4,5\}$ under two scenarios. Although we do not show results on all the 13 problems here due to the space constraints, they can be found in Figures S.1 – S.13 in the supplementary file⁶⁶6The supplementary file is also available online (https://sites.google.com/site/moeadanalysis/home/ti-moead-asoc17-supp.pdf) of this paper.

As shown in Figure 3(a), under the final population scenario, while MOEA/D with $\mu\in\{100,200\}$ show good performance for $M=2$, MOEA/D with the largest $\mu$ value outperforms other configurations after several function evaluations for $M\geq 3$. A larger $\mu$ value is beneficial to MOEA/D for the final population scenario. Similar results can be found on other problems shown in Figures S.1(a) – S.13(a). Of course, there are some exceptions. For example, results on the WFG1 problem (Figure S.5) show that MOEA/D with a small $\mu$ value exhibits a good performance under the final population scenario.

While good HV values are obtained with a large $\mu$ value in most cases for the final population scenario, MOEA/D with a small $\mu$ value performs the best under the reduced UEA scenario as seen from Figure 3(b). It is interesting to notice that the performance rank of MOEA/D with the smallest and largest $\mu$ values is totally different between the two scenarios on the three- and four-objective WFG4 problems. For example, for $M=3$, while MOEA/D with $\mu=406$ performs significantly better than MOEA/D with $\mu=28$ under the final population scenario, their performance rank is inverted even on the same problem instance in the case of the reduced UEA scenario. Similar conclusions can be found on most of other problems shown in Figures S.1(b) – S.13(b), except for the results on the DTLZ4, WFG2, WFG3, and WFG8 problems. A large $\mu$ value is suitable for MOEA/D on the DTLZ4, WFG2, WFG3, and WFG8 test problems even when we use the reduced UEA scenario.

According to the percentiles in Figure 3(a) and (b), there is no large variation in the HV values obtained by using all the $\mu$ values for $M=2$. However, the variation of the HV values becomes large with increasing $M$. In particular, a larger variation is observed in results of MOEA/D with small $\mu$ values for $M=5$. Thus, it is likely that the performance of MOEA/D with small $\mu$ values on MOPs with a large $M$ is significantly different for each run.

We here discuss why the best population size $\mu$ is dependent on the choice of an optimization scenario, the number of objectives $M$, and the characteristics of a given problem. As described in Subsections 4.1.1 and 4.1.2, while MOEA/D with the largest $\mu$ value outperforms other configurations in most cases under the final population scenario, a small $\mu$ value is suitable for MOEA/D on some problems for the reduced UEA scenario. In particular, the performance rank of MOEA/D with various $\mu$ values on the WFG4 problem with $M\in\{3,4\}$ is totally different depending on the considered optimization scenario.

This seems to be simply because MOEA/D with a large $\mu$ value is capable of keeping a large number of nondominated solutions in the population. As discussed in [67], such a large number of nondominated solutions are always beneficial for the HV calculation. For this reason, the results in Subsections 4.1.1 and 4.1.2 show that MOEA/D with a large $\mu$ value performs well on most problems. However, nondominated solutions in the population do not directly influence the performance of MOEA/D under the reduced UEA scenario, because solutions selected from the UEA are used for the HV calculation. Also, MOEA/D can store nondominated solutions whose size is over $\mu$ in the UEA. Due to this reason, MOEA/D with a small $\mu$ value works well under the reduced UEA scenario.

Figure 4 shows the distribution of nondominated solutions in the objective function space for each scenario found by MOEA/D with $\mu=28$ and $\mu=406$ on the three-objective WFG4 problem. For the final population scenario, while MOEA/D with $\mu=406$ achieves a set of diverse nondominated solutions, MOEA/D with $\mu=28$ can provide only a small number of nondominated solutions. Unlike the results for the final population scenario, MOEA/D with both $\mu$ settings successfully maintain the densely distributed solutions covering the entire PF in the UEA for the reduced UEA scenario. It is likely that MOEA/D with a small $\mu$ value cannot keep good nondominated solutions in the population but has an ability to generate well-distributed solutions.

We do not intend to argue that a small $\mu$ value is always beneficial for MOEA/D under the reduced UEA scenario. Our results in Subsection 4.1.2 show that a (relatively) large $\mu$ value is necessary for MOEA/D to find good nondominated solutions on some problems, especially MOPs with a large $M$ or an irregular shape of the PF. As seen from the results on the five-objective WFG4 problem (Figure 3), while MOEA/D with the smallest $\mu$ value ($\mu=126$) achieves the highest HV value until $14\,000$ function evaluations, it clearly performs worst after that. Since the objective function space is exponentially increasing with $M$, a large population size is necessary for the search if $M$ is large.

Results on the DTLZ4, WFG2, WFG3, and WFG8 problems (Figure S.4, S.6, S.7, and S.12, respectively) show that a large $\mu$ value is beneficial for MOEA/D for all $M$ independently of the choice of an optimization scenario. The shape of the PF of the WFG2 and WFG3 problems are discontinuous and partially degenerate [64], respectively. Since the Pareto optimal solutions do not exist in most of the decomposed subproblems of MOPs having discontinuous and degenerate PFs [68], a large $\mu$ value, which makes a large number of subproblems, is necessary for MOEA/D to find well-approximated solutions. For this reason, MOEA/D with a small $\mu$ value performs poorly on the WFG2 and WFG3 problems. Also, the mapping from the solution space to the objective function space $\mbox{\boldmath$f$}:\mathbb{S}\rightarrow\mathbb{R}^{M}$ is biased in the DTLZ4 and WFG8 problems. The existence of the bias makes the problem more difficult, and thus MOEA/D with a small $\mu$ value cannot find good solutions on the DTLZ4 and WFG8 problems.

Figure 5 shows the overall performance of MOEA/D with the three scalarizing functions ($g^{\rm chm}$, $g^{\rm chd}$, and $g^{\rm pbi}$ with $\theta=5$) over all the 13 test problems. For details of the three functions, see Section 2. The influence of $\theta$ on the performance of MOEA/D using $g^{\rm pbi}$ is investigated in Subsection 4.3.

The results on the two- and three-objective 13 problems for the final population scenario show that the performance of MOEA/D with the two Chebyshev functions ($g^{\rm chm}$ and $g^{\rm chd}$) is better than that with $g^{\rm pbi}$ at anytime (Figure 5(a)). For $M=4$, MOEA/D with $g^{\rm pbi}$ outperforms the other configurations after $38\,000$ function evaluations. For $M=5$, MOEA/D with $g^{\rm pbi}$ always exhibits the best performance.

The results for the reduced UEA scenario (Figure 5(b)) are significantly different from the results for the final population scenario described above. As seen from Figure 5(b), MOEA/D with the two Chebyshev functions are competitive with each other. The $g^{\rm chm}$ and $g^{\rm chd}$ are the best scalarizing functions for $M\in\{2,4,5\}$ and $M=3$, respectively. Interestingly, while MOEA/D with $g^{\rm pbi}$ exhibits a good performance on MOPs with more than four objectives after several function evaluations under the final population (Figure 5(a)), its performance is worst among the three configurations for all $M$ under the reduced UEA scenario (Figure 5(b)).

Figure 6 shows the anytime performance of MOEA/D with the three scalarizing functions on the WFG4 problem with $M\in\{2,3,4,5\}$. Results on all the 13 problems can be found in Figures S.14 – S.26 in the supplementary file.

As shown in Figure 6, the results on the WFG4 problem are similar to the aggregated results on all of the 13 problems shown in Figure 5. For both scenarios, MOEA/D with the two Chebyshev functions perform significantly better than that with $g^{\rm pbi}$ on the two- and three-objective WFG4 problems. For the final population scenario, with increasing $M$, MOEA/D with $g^{\rm pbi}$ achieves the highest HV values among the three configurations in the later search stage. However, for the reduced UEA scenario, the worst HV values are obtained by using $g^{\rm pbi}$, and MOEA/D with the two Chebyshev functions show better performance at any time. As seen from the percentiles in Figure 6(a) and (b), the variation of the HV values achieved by using the two Chebyshev functions is large for $M=5$. In contrast, the performance of MOEA/D with $g^{\rm pbi}$ is not much different for each run. The quality of nondominated solutions found by using $g^{\rm pbi}$ is likely to be stable even on MOPs with a large $M$.

Results on the DTLZ2, WFG5, WFG6, WFG7, WFG8, and WFG9 problems are similar to results on the WFG4 problem. On the DTLZ1 problem, MOEA/D with $g^{\rm chd}$ and $g^{\rm pbi}$ show good performance (Figure S.14). On the DTLZ3 problem, $g^{\rm chd}$ is the best scalarizing function for all $M$ (Figure S.16). On the DTLZ4 problem with $M\geq 3$, MOEA/D with $g^{\rm pbi}$ performs the best (Figure S.17). On the WFG2 and WFG3 problems with all $M$, the performance of MOEA/D with the two Chebyshev functions is better than that with $g^{\rm pbi}$ even for the final population scenario (Figure S.19 and S.20).

A number of previous work report that MOEA/D with $g^{\rm chm}$ is not capable of obtaining well-distributed nondominated solutions in the objective function space (e.g., [18, 30, 54, 69]). Recent studies also report the promising performance of MOEA/D with $g^{\rm pbi}$ on MOPs with more than four objectives [24, 30]. Our results for the final population described in Subsections 4.2.1 and 4.2.2 are consistent with these previous studies. However, the performance of MOEA/D with the two Chebyshev functions ($g^{\rm chm}$ and $g^{\rm chd}$) is significantly better than that with $g^{\rm pbi}$ on most problem instances under the reduced UEA scenario. In summary, the best scalarizing function for MOEA/D is significantly dependent on the choice of an optimization scenario. Below, we discuss this result (mainly with respect to the comparison between the PBI function and the two Chebyshev functions).

Figure 7 shows the parallel coordinates of the objective function values of nondominated solutions found by MOEA/D with the three scalarizing functions on the five-objective WFG4 problem under (a) the final population scenario and (b) the reduced UEA scenario. It should be recalled that $g^{\rm pbi}$ and $g^{\rm chm}$ are the best scalarizing functions on the five-objective WFG4 problem for the final population and reduced UEA scenarios, respectively (see Figure 6).

The number of nondominated solutions in Figure 7(a) is $146$ for $g^{\rm chm}$, $150$ for $g^{\rm chd}$, and $210$ for $g^{\rm pbi}$. That is, MOEA/D with $g^{\rm pbi}$ obtains the largest number of nondominated solutions among the three configurations for the final population scenario. The nondominated solutions found by MOEA/D with $g^{\rm pbi}$ are also uniformly distributed in the objective function space. For these two reasons, it seems that MOEA/D with $g^{\rm pbi}$ achieves the highest HV value at the end of the search. In contrast to the results for the final population scenario, as shown in Figure 7(b), MOEA/D with $g^{\rm chm}$ obtains well-distributed nondominated solutions in the objective function space under the reduced UEA scenario. The uniformity of the distribution of nondominated solutions found by MOEA/D with $g^{\rm chm}$ is slightly better than those obtained by the other methods.

For further discussion, we show the distribution of nondominated solutions in the objective function space for both the final and reduced UEA scenarios on the three-objective WFG4 problem in Figure 8. The distribution on the three-objective WFG4 problem in Figure 8 is similar to the distribution on the five-objective WFG4 problem in Figure 7. In the final population scenario (Figure 8(a)), while the uniformly distributed nondominated solutions are obtained by using $g^{\rm pbi}$ and $g^{\rm chd}$, the distribution of solutions found by MOEA/D with $g^{\rm chm}$ is biased. However, it seems that MOEA/D with all the three scalarizing functions find evenly distributed nondominated solution under the reduced UEA scenario (Figure 8(b)).

As pointed out in [37, 54], it seems that MOEA/D with $g^{\rm chm}$ is capable of generating well-approximated solutions but cannot maintain them in its population. Such a problem of $g^{\rm chm}$ is addressed by incorporating the UEA, which automatically stores good nondominated solutions independently from the population, into MOEA/D. Due to this reason, MOEA/D with $g^{\rm chm}$ performs the best on the five-objective WFG4 problem under the reduced UEA scenario, regarding the HV metric. This observation can be found in some of the other test problems.

Figure 9 shows the overall performance of MOEA/D using the PBI function $g^{\rm pbi}$ with $\theta\in\{0.1,0.5,1,2,3,5,8,10\}$ on the 13 problems with $M\in\{2,3,4,5\}$ under (a) the final population scenario and (b) the reduced UEA scenario. Unlike the results of $\mu$ and $g$ presented in Subsections 4.1 and 4.2, the performance rank of each configuration is not drastically changed during the search process for both scenarios. That is, a configuration that performs well at the beginning of the search exhibits good performance also at the end of the search.

As shown in Figure 9(a), good APS values are obtained by $\theta\in\{2,3\}$ for $M\in\{2,3\}$ for the final population scenario. The best penalty value is $\theta\in\{3,5\}$ and $\theta\in\{5,8\}$ for $M=4$ and $M=5$, respectively. It seems that MOEA/D using $g^{\rm pbi}$ with $\theta=5$ works well for all $M$. In contrast, $\theta\in\{0.1,0.5,1\}$ are clearly inappropriate penalty values for all $M$.

Figure 9(b) shows results for the reduced UEA scenario. It seems that the performance rank under the reduced UEA scenario is not significantly different from that under the final population scenario. Although the smallest APS value is obtained by $\theta=0.1$ until $6\,000$ function evaluations for $M\geq 3$, MOEA/D using $g^{\rm pbi}$ with $\theta\in\{3,5\}$ perform well among all the configurations for all $M$. While the performance rank of $\theta=0.1$ is improved $M\geq 3$, MOEA/D using $g^{\rm pbi}$ with $\theta\in\{0.5,1\}$ performs poorly even for the reduced UEA scenario.

Figure 10 shows the anytime performance of MOEA/D using $g^{\rm pbi}$ with various $\theta$ values on the WFG4 problem with $M\in\{2,3,4,5\}$. Figures S.27 – S.39 in the supplementary file show results on all the 13 problems.

As seen from Figure 10(a), for the final population scenario, $\theta=1,2,2$, and $3$ are suitable values on the WFG4 problem with $M=2,3,4,$ and $5$, respectively. That is, the best penalty value $\theta$ increases with respect to the number objectives $M$ on the WFG4 problem. Interestingly, as shown in Figure 10(b), in contrast to the results for the final population scenario, MOEA/D using $g^{\rm pbi}$ with $\theta=0.1$ achieves the good HV value under the reduced UEA scenario for $M\in\{2,3\}$. According to the percentiles in Figure 10(a) and (b), for $M=3$, the variation of the HV values obtained by using $\theta\in\{0.1,0.5\}$ is larger than that by using other $\theta$ values. Interestingly, in Figure 10, the 25th and 75th percentile values are not evenly distributed. For example, on the results for $M=3$ in Figure 10(a), while the median and the 25th percentile values are almost the same, the difference between the median and 75th percentile values is large. Only for $M=5$, a large variation is observed in results of MOEA/D with $\theta=3$. While MOEA/D with $\theta=3$ obtains the best HV value under both scenarios regarding the median HV value, it performs similarly to MOEA/D with $\theta\in\{0.1,0.5,1,2\}$ for a particular run as seen from its 75th percentile values.

Due to space constraints, results on other test problems are not described here. Similar to the results on the WFG4 problem, the best $\theta$ value significantly depends on the considered scenario on most test problems.

Our results described in Subsections 4.3.1 and 4.3.2 show that the best setting of $\theta$ is significantly dependent on the characteristics of a given problem. For example, while MOEA/D using $g^{\rm pbi}$ with $\theta=2$ performs well on the WFG4 problem with $M=3$ (Figure 10(a)), $\theta=10$ is the best setting for solving the three-objective DTLZ1 problem (Figure S.27). Such conclusions are consistent with previous studies [33, 35, 36, 70]. For example, experimental results in [33] show that MOEA/D using $g^{\rm pbi}$ with $\theta=0.1$ performs better than that with other $\theta$ values on multi- and many-objective knapsack problems with the convex PFs. However, a small penalty value like $\theta=0.1$ is not appropriate for MOEA/D to solve MOPs with nonconvex PFs [36].

In addition to the characteristics of a given problem, our results in Subsections 4.3.1 and 4.3.2 newly reveal that a suitable $\theta$ value also depends on a target optimization scenario. For example, as shown in Figure 10, the best $\theta$ value is totally different on the WFG4 problem (nonconvex) for each scenario. Below, we discuss the reason why the $\theta=0.1$ is the best penalty value on the three-objective WFG4 problem for the reduced UEA scenario.

Figure 11 shows the distribution of nondominated solutions found by MOEA/D using $g^{\rm pbi}$ with $\theta=0.1$ and $\theta=2$ on the three-objective WFG4 problem for the final and reduced UEA scenarios. It should be noted that $\theta=2$ is the best parameter setting on the WFG4 problem with $M=3$ for the final population scenario (see Figure 10). As seen from Figure 11(a), while MOEA/D with $\theta=0.1$ can find only the three extreme solutions under the final population scenario, well-distributed nondominated solutions are obtained by $\theta=2$. However, Figure 11(b) shows that in addition to the extreme solutions, MOEA/D with $\theta=0.1$ achieves some nondominated solutions distributed on the rim and inside regions of the PF. Note that the HV value of nondominated solutions obtained by using $\theta=0.1$ is higher than that by $\theta=2$ in Figure 11(b).

It is pointed out that the HV indicator does not always assess the uniformity and diversity of the distribution of nondominated solutions [71]. For further investigation, we used the inverted generational distance (IGD) [65], which evaluates both convergence and diversity performance of MOEAs. The generational distance (GD) and maximum spread (MS) [65] indicator values of nondominated solutions are also reported to discuss convergence and diversity performance of MOEA/D, individually.

The MS value of $A$ is the average of the maximum and minimum objective function values of solutions in $A$ for each objective as follows:

Figure 12 shows the MS, GD, and IGD indicator values of nondominated solutions found by MOEA/D using $g^{\rm pbi}$ with various $\theta$ values on the three-objective WFG4 problem under (a) the final population scenario and (b) the reduced UEA scenario. Before calculating each indicator value, all objective function values were normalized as described in Subsection 3.1. One may wonder that GD values for the final population scenario are significantly better than those for the reduced UEA scenario. This is because the number of nondominated solutions in the population is usually smaller than that in the UEA (e.g., see Figure 11), and a small number of solutions is possibly beneficial for GD as discussed in [67].

As seen from Figure 12, MOEA/D with $\theta\in\{0.1,2,3,5,8,10\}$ achieve high MS values for both scenarios. The best GD values are also obtained by using $\theta=0.1$ for the reduced UEA scenario. Thus, nondominated solutions in the UEA obtained by using $\theta=0.1$ are close to the PF. This is because the contour lines of $g^{\rm pbi}$ with $\theta=0.1$ and the weighted sum function are similar [33]. Therefore, MOEA/D using $g^{\rm pbi}$ with $\theta=0.1$ shows good HV values on the WFG4 problem with $M=3$.

It is interesting to notice that the performance rank based on the IGD metric is slightly different from that based on the HV indicator. Although the best HV values are obtained by using $\theta=0.1$ under the reduced UEA scenario (Figure 10), MOEA/D with $\theta=2$ achieves the lowest IGD values (Figure 12). Since the IGD metric assesses the uniformity of the distribution, the IGD value of nondominated solutions found by MOEA/D with $\theta=0.1$, whose distribution is biased to specific regions as shown in Figure 11, is worse than that by MOEA/D with $\theta=2$.

Figure 13 shows the influence of $\mu$ on the performance of MOEA/D with the three scalarizing functions ($g^{\rm chm}$, $g^{\rm chd}$, and $g^{\rm pbi}$) on the WFG4 problem with $M\in\{2,3,5\}$. Results on other test problems can be found in Figures S.40 – S.52 in the supplementary file.

As seen from Figure 13, the best $\mu$ value is different depending on scalarizing functions. For example, as shown in Figure 13(a), for the final population scenario, MOEA/D with the two Chebyshev functions need a relatively large $\mu$ value for all $M$. In contrast, small $\mu$ values are suitable for $g^{\rm pbi}$. In addition, as discussed in Subsection 4.1, suitable $\mu$ values also depend on the choice of an optimization scenario. Figure 13(b) indicates that small $\mu$ values are appropriate for all the three scalarizing functions on the WFG4 problem under the reduced UEA scenario. For $M\in\{2,3\}$, in most cases, the increase of $\mu$ deteriorates the performance of MOEA/D under the reduced UEA scenario. In summary, $\mu$ and $g$ are correlated with each other, and the relation between them is dependent on the choice of a scenario.

Figure 14 shows the impact of $\mu$ on the performance of MOEA/D using $g^{\rm pbi}$ with various $\theta$ values on the WFG4 problem with $M\in\{2,3,5\}$. Results on other test problems are shown in Figures S.53 – S.65 in the supplementary file. Unlike the analysis results of $\mu$ and $g$, the effect of $\mu$ values on the performance of MOEA/D with various $\theta$ values is relatively moderate, except for some results (e.g., results for $\theta=1$ on the three-objective WFG4 problem). Thus, the performance rank of MOEA/D with different $\theta$ values is not significantly influenced by $\mu$.

Figure 15 provides a comparison of the two Chebyshev functions ($g^{\rm chm}$ and $g^{\rm chd}$) and $g^{\rm pbi}$ with $\theta\in\{0.1,...,10\}$ on the WFG4 problem with $M\in\{2,3,5\}$. For $g^{\rm chm}$ and $g^{\rm chd}$, the same HV values are shown for each $\theta$ value in Figure 15. Results on other test problems can be found Figures S.79 – S.91 in the supplementary file.

As seen from Figure 15, the performance of MOEA/D with $g^{\rm pbi}$ significantly depends on the $\theta$ value for both optimization scenarios. Although such results under the final population scenario have already been reported in previous work (e.g., [35, 70]), similar results are observed under the reduced UEA scenario. MOEA/D with a particular $\theta$ value performs better than that with the two Chebyshev functions. Whereas the poor results are obtained by the $g^{\rm pbi}$ with $\theta=5$ under the reduced UEA scenario in Subsection 4.2, it is likely that MOEA/D using $g^{\rm pbi}$ with a suitable $\theta$ value performs well. Interestingly, the performance of MOEA/D regarding the HV metric is drastically improved or degraded at around $\theta\in\{1,2,3\}$. The reason is unclear, and thus its further analysis is our future research topic.