Population diversity control based differential evolution algorithm using fuzzy system for noisy multi-objective optimization problems

To evaluate the performance of the proposed NDE algorithm, DTLZ34and WFG35 test problems are taken. The above test problem set are multi-objective unconstrained optimization problems and varying noise levels (0.1, 0.2, 0.5) is used for experimentation, and is detailed in section “Test problems”. The performance metrics used for experimentation are modified inverted generational distance (IGD+)36 and hypervolume (HV)37 , which helps to assess both convergence and diversity properties of the attained solution set and the metrics are detailed in section “Performance metrics”.The performance of proposed NDE algorithm is compared with five multi-objective evolutionary algorithms namely, two stage evolutionary algorithm (TSEA)9, two archive algorithm (Two_Arch2)38, regularity model in NSGA-II (RM-NSGA-II)25, Noise-tolerant Strength Pareto Evolutionary Algorithm (NTSPEA)2, rolling tide evolutionary algorithm (RTEA)39 and Filters based NSGA-II (FNSGA-II)27. Except Two_Arch2 all other algorithms are developed to solve noisy optimization problems. The initialization of values for the various parameters used in proposed NDE algorithm are listed in Table 3.Table 3 Parameters and initial values.Test problemsSixteen test problems are used to evaluate the performance of the proposed algorithm. All the problems are multi-objective unconstrained optimization problems. From DTLZ test suite34 seven problems (DTLZ1 to DTLZ7) are taken and from WFG test suite35 nine problems (WFG1 to WFG9) are taken. The number of decision variables and objectives can be scaled up to required numbers. These sixteen problems exhibits different properties (concave, multimodal, biased, etc.) make it suitable to be used to test the performance of the proposed optimization algorithm. Three objective problems are considered for investigation.The properties of these problems are listed in Table 4. The significance of using above problems in evaluating optimization algorithms is the availability of true pareto optimal front. Further, in DTLZ problems the number of objectives is scalable, test problems DTLZ5 and DTLZ6 have degenerated pareto fronts and distance functions are added in all the DTLZ test problems. WFG Problems include complex characteristics like many problems are non-separable, we may also observe few problems are deceptive, problems where pareto fronts are mixed shape. The availability of problems with such complex characteristics and availability true optimal fronts for the benchmark problems like above, significantly contributes in conducting the experimentation in the optimization field.Table 4 Test problems and its properties.Performance metricsThe performance of the proposed algorithm is investigated using two performance metrics, modified Inverted Generational Distance (IGD+)36 and HyperVolume (HV)37.IGD+ performance metric is a modified inverted generational distance metric that quantifies both convergence and diversity characteristic of an optimization algorithm. It helps to estimate the distance between the attained and true pareto fronts, lesser the IGD+ value indicates better the attained solutions and is calculated as given in Eq. 7.$${IGD}^{+}\left(A,B\right)=\frac{{\sum }_{x\in A}d(x,B)}{\left|A\right|}$$
(7)
where, \(A\) represents the reference points in true front, \(B\) represents the solutions in the attained pareto front. \(d(x,B)\) represents the nearest distance from \(x\) to attained front solutions, and this distance calculation from \(x\) to a solution \(y\) in \(B\) is estimated as, \(d\left(x,y\right)=\sqrt{\sum_{j=1}^{n}\text{max}{({y}_{j}-{x}_{j},0)}^{2}}\) and \(n\) represents the number of objectives.HV performance metric helps to evaluate the convergence and diversity properties of the obtained solutions. HV calculates the hypervolume between the attained front and a given reference point. Formula to calculate HV is given in Eq. 8. A higher HV value indicates that better solutions are attained.$$HV=Le\left({\cup }_{X\in S}\left[{f}_{1}\left(X\right),{re}_{1}\right]*\dots \left[{f}_{n}\left(X\right),{re}_{n}\right]\right)$$
(8)
where variable \(S\) represents attained solution set and \(Le\) indicates the Lebesgue measure. Variable \(n\) denotes the number of objective functions. \(Re=({re}_{1}, {re}_{2},..,{re}_{m})\) is a vector of maximum reference point value on every objective function set at (1,1). Before calculating HV metric value, the objective functions are normalized using Min–max normalization.Results and discussion on DTLZ problemsThe mean IGD+ value results of DTLZ problems are given in Table 5 and the pareto fronts are given in Fig. 2. The results of HV Metric is listed in Table 6. The overall performance of NDE algorithm results is better when compared to all algorithms. DTLZ1 test problem is a linear and multi-modal test problem and chances of getting stuck at local optimal solutions are higher for problems of such characteristics, the obtained pareto front is shown in Fig. 2a. NDE algorithms performance is best followed by TSEA algorithm and the other algorithms. This is because of the fuzzy system based control parameter adaptation to regulate the population diversity and the applied denoising method. DTLZ2 is a concave, unimodal problem and the possibility of noise affecting its performance is high. NDE outperforms and the results are better compared to the other algorithms, and the respective attained front is shown in Fig. 2b. The effectiveness of averaging based denoising method is evident through the results. The characteristic of DTLZ3 test problem is multimodal as well and the performance of the proposed NDE algorithm is better, and the attained front is given in Fig. 2c.Table 5 Mean IGD+ values for DTLZ Problems (best results are highlighted).Figure 2Obtained pareto fronts for DTLZ problems. (a) Obtained pareto fronts for DTLZ1 problem. (b) Obtained pareto fronts for DTLZ2 problem. (c) Obtained pareto fronts for DTLZ3 problem. (d) Obtained pareto fronts for DTLZ4 problem. (e) Obtained pareto fronts for DTLZ5 problem. (f) Obtained pareto fronts for DTLZ6 problem. (g) Obtained pareto fronts for DTLZ7 problem.Table 6 Mean HV values for DTLZ Problems (best results are highlighted).DTLZ4 test problem is a modified one from DTLZ2 and the solutions are usually densely populated near to the planes. The performance of NTSPEA algorithm is better followed by NDE and the other methods. It can be observed that the NTSPEA algorithm works by associating survival time factor for all the solutions in the population and DTLZ4 problem is sensitive towards the initial population, and the respective attained front is given in Fig. 2d. The characteristics of test problems DTLZ5, DTLZ6 and DTLZ7 are irregular and the pareto front for DTLZ7 is discontinuous, the obtained pareto fronts for these problems are illustrated in Fig. 2e, f and g respectively. The proposed NDE algorithm attains better results for all the above problems. The IGD+ and HV values evolution across the function evaluations for DTLZ2 and DTLZ7 test problems are given in Fig. 3a and b respectively.Figure 3(a) IGD + values across the function evaluations for DTLZ2 test problem. (b) HV values across the function evaluations for DTLZ7 test problem.Results and discussion on WFG problemsWFG test problems are relatively complex when compared to the DTLZ problems. The mean values of the IGD+ and HV performance metrics are given in Tables 7, 8 respectively. The attained pareto fronts for the WFG problems are given in Fig. 4. WFG1 test problem is a complex test problem with mixed and biased characteristics. The performance of the proposed NDE algorithm is better than other algorithms taken for comparison, and is at par with performance of NTSPEA algorithm, the obtained pareto front for the same is illustrated in Fig. 4a. WFG2 is a multimodal test problem, and the performance of NDE is the best, and the respective front is given in Fig. 4b. WFG3 is a linear, non-separable test problem and the attained solutions and the mean IGD+ and HV values are better than other methods, and the pareto front is given in Fig. 4c.Table 7 Mean IGD+ values for WFG problems (best results are highlighted).Table 8 Mean HV values for WFG problems (best results are highlighted).Figure 4Obtained pareto fronts for WFG problems. (a) Obtained pareto fronts for WFG1 problem. (b) Obtained pareto fronts for WFG2 problem. (c) Obtained pareto fronts for WFG3 problem. (d) Obtained pareto fronts for WFG4 problem. (e) Obtained pareto fronts for WFG5 problem. (f) Obtained pareto fronts for WFG6 problem. (g) Obtained pareto fronts for WFG7 problem. (h) Obtained pareto fronts for WFG8 problem. (i) Obtained pareto fronts for WFG9 problem.The characteristic of WFG4 problem is that it is multi-modal, with multiple local optimal solutions. The population diversity control and the appropriate denoising method aid in escaping from such locally optimal solutions and it is evident through the obtained results, and front as given in Fig. 4d. WFG5 problem is of deceptive characteristic and is a separable problem and the attained concave pareto front and the mean IGD+ and HV values are better, and the front for the problem is illustrated in Fig. 4e. WFG6, WFG8 and WFG9 test problems are non-separable test problems and WFG9 is multi-modal as well. For the test problem WFG6, the performance of NDE and RTEA are at par, followed by the other algorithms, and the attained pareto front is illustrated in Fig. 4f. For WFG8 and WFG9 test problems, the results of NDE algorithm are promising, and the obtained pareto fronts for these problems are given in Fig. 4h and i respectively. The characteristic of WFG7 is it is unimodal and a separable one and the results of the proposed NDE algorithm is best, and the pareto front is given in Fig. 4g. The IGD+ and HV values evolution across the function evaluations for WFG9 and WFG2 test problems are given in Fig. 5a and b respectively.Figure 5(a) IGD + values across the function evaluations for WFG9 test problem. (b) HV values across the function evaluations for WFG2 test problem.Population effect and population diversity analysisPopulation plays a vital role in search and optimization algorithms. The initial population is randomly generated within the variable bounds. Along the evolution, fitter solutions are selected and used that helps to attain an optimal or pareto-optimal solutions. In the proposed research, the population diversity plays a key role. The population diversity is controlled adaptively in order to improve the search performance. The solutions in the population must be diverse enough during the initial stages of evolution to have a better exploration over the search space and over the evolution and at later stages the population diversity is to be low to have better exploitation. Population that aids in balancing the explore-exploit cycle is required to attain optimal or pareto optimal solutions. The effect of population diversity in the present research is presented below and the explore-exploit cycle analysis is presented in the section “Exploration–Exploitation analysis”.To perform population diversity analysis, diversity of the population is calculated as given in Eq. 9, “distance to average point” measure32. This measure includes population size, dimension and search region of variables, thus this measure used for population diversity estimation.$${diversity}_{generation}\left(PP\right)= \frac{1}{|LenDia|*NP}*{\sum }_{i=1}^{NP}\sqrt{{\sum }_{j=1}^{{d}_{i}}({y}_{ij}-{\overline{y}}_{j}}{)}^{2}$$
(9)
where, \(PP\) represents population with size \(NP\). \(\left|LenDia\right|\) is the diagonal length of the search space, \({d}_{i}\) is the problem dimension. \({y}_{ij}\) is \({j}^{th}\) value of \({i}^{th}\) solution, \({\overline{y}}_{j}\) is the \({j}^{th}\) value of average point \(\overline{y }\).Figure 6a and b shows the diversity graph of the population along the iterations for two problems, from which it is evident that, during the initial stages of evolution higher diversity is observed to improve the exploration and in later stage diversity value is lesser to improve exploitation.Figure 6(a) Population diversity adaptation along the iterations for DTLZ1 test problem. (b) Population diversity adaptation along the iterations for WFG7 test problem.Exploration–Exploitation analysisTo analyse the balancing property of exploration–exploitation cycle, the exploration and exploitation rate along the evolution is calculated using Eqs. 10 and 1140.$$exploration\;\left(iteration\right)=\left(\frac{popdiversity(iteration)}{\text{max}(popdiversity(iteration)}\right)\times 100$$
(10)
$$exploitation\;\left(iteration\right)=\left(\frac{|popdiversity\left(iteration\right)-\text{max}(popdiversity(iteration)|}{\text{max}(popdiversity\left(iteration\right))}\right)\times 100$$
(11)
where, \(popdiversity\) indicates the population diversity and is calculated using Eq. 9.Exploration–exploitation graph for two problems is given in Fig. 7a and b. It can be observed that, exploration starts with a higher value and during later stages it decreases and the exploitation begins with a smaller value and upon evolution its value is increased in final stages, which ensures the balance between the cycles of exploration and exploitation.Figure 7(a) Exploration–exploitation graph for DTLZ5 test problem. (b) Exploration–exploitation graph for WFG2 test problem.Statistical test resultsStatistical analysis through Wilcoxon signed rank test and Friedman test41 are performed to further validate the performance of NDE.Wilcoxon signed rank test is a pairwise comparison test, used to find whether there is significant difference between two algorithms. The test is performed using IBM SPSS package and the significance level \(\alpha\) is set to 0.05. \(\rho\)-value is computed through the above test and if the obtained \(\rho\)-value is less than \(\alpha\), the null hypothesis can be rejected and it implies there is significance difference among the algorithms taken for evaluation. The test results using the mean HV value results with \(\sigma\) value 0.5 obtained through various algorithms for DTLZ problems is presented in Table 9. The \(\rho\)-value is less than 0.05 (significance level) and the null hypothesis can be rejected. It is evident that the proposed NDE algorithm is significantly better when compared to other algorithms taken for comparison.Table 9 Wilcoxon signed rank test results for mean HV values against DTLZ problems.Table 10 gives the Wilcoxon signed rank test results using the mean IGD+ value results with.Table 10 Wilcoxon signed rank test results for mean IGD+ values against WFG problems.\(\sigma\) value 0.5 obtained through various algorithms for WFG test problems. It is evident that the NDE algorithm is significantly better than the other algorithms taken for comparison as the \(\rho\)-value is less than 0.05.The competence of the proposed NDE algorithm is also statistically analysed using Friedman rank test, which is a multiple comparison test. Joint analysis of algorithms taken for comparison is performed through the above test. The test is performed using IBM SPSS package and the significance level \(\alpha\) is set to 0.05. \(\rho\)-value is computed through the above test and if the obtained \(\rho\)-value is less than \(\alpha\), it implies there is significance difference among the algorithms taken for evaluation.Table 11 gives the Friedman rank test results using the mean IGD+ value results with.Table 11 Friedman rank test results for mean IGD+ values against DTLZ problems.\(\sigma\) value 0.5 obtained through various algorithms for DTLZ problems.The proposed NDE algorithm is ranked first in the above test and the \(\rho\)-value obtained is 0.0001 which is less than the significance level \(\alpha =0.05\), which proves the significance of the proposed optimization algorithm.Table 12 gives the Friedman rank test results using the mean HV value results with \(\sigma\) value 0.5 obtained through various algorithms for WFG problems.Table 12 Friedman rank test results for mean HV values against WFG problems.The proposed NDE algorithm is again ranked first in the above statistical test and the \(\rho\)-value obtained is 0.00008 which is less than the significance level \(\alpha =0.05\), shows the significance of the proposed optimization algorithm.Experimentation on CEC 2017 test problemsTo further investigate the effectiveness of the proposed Differential Evolution based Noise handling Optimization algorithm (NDE), experimentation is conducted on CEC 2017 test problems42 which are single objective optimization problems. To perform this study, the selection process in the proposed NDE algorithm is changed suitable to handle single objective optimization problems. The trial vector generated after the crossover operation is subject to fitness function evaluation. The fitness function values of the solutions in target and trial vectors are compared and the better solution is chosen as candidate for the next generation.CEC 2017 test suite comprises 29 test problems (Test problem F2 has been removed from the CEC 2017 suite). The parameter settings are followed as given in the technical report and are given in Table 13.Table 13 Parameter settings for CEC 2017 test problem evaluation.The result analysis is performed by calculating error value, which is the difference between the best objective function value that is attained in a run and the true optimal value. This error value is calculated for all the 51 runs and the mean and standard deviation values are recorded. The results are compared with two other algorithms Effective Butterfly Optimizer using Covariance Matrix Adapted Retreat phase (EBOwithCMAR)43 and jSO44 which has secured first and second rank in the CEC 2017 competition and are presented in Table 14. The best results are highlighted in boldface, and it can be observed that the proposed NDE algorithm performs better in 19 functions, similar performance in 3 functions and inferior performance in 7 functions. This shows the significance of the NDE algorithm, with its capability of population diversity control through strategy adaptations, the restricted local search and noise handling techniques exhibits a robust performance.Table 14 Mean and standard deviation results of the error values.LimitationsThe main limitations of the research include, experimenting on a number of benchmark problems with varied and complex characteristics and not conducting experimentation on a real-world optimization problem45,46,47. The widely considered limitation in applying an optimization algorithm to a real-world problem will be parameter fine tuning according to the problem. But in the proposed NDE algorithm the major parameters like crossover rate and trial vector generation strategies are self-adapted according to the population domain of the problem. Thus, finetuning the other associated parameters may be a challenge. Through the above test results the robustness of the proposed NDE algorithm in solving a wider range of problems is evident. Further improvements will be studied in future work, by integrating multiple denoising models, fine tuning algorithm to handle constrained optimization problems and conducting experiments on real-world optimization problem.