Abstract
Evolutionary Algorithm provides a framework that is largely applicable to particular problems including multiobjective optimization problems, basically for the ease of their implementation and their capability to perform efficient parallel search. Indeed, in some cases, expensive multiobjective optimization evaluations might be a challenge to restrict the number of explicit fitness evaluations in multiobjective evolutionary algorithms. Accordingly, this article presents a novel approach that tackles this problem so as to not only decrease the number of fitness evaluations but also to improve the performance. During evolution, our proposed approach selects fit individuals based on the knowledge acquired throughout the search, and performs explicit fitness evaluations on these individuals. A comprehensive comparative analysis of a wide range of well-established test problems, selected from both traditional and state-of-the-art benchmarks, has been presented. Afterward, the effectiveness of the obtained results is compared with some of the state-of-the-art methods using two well-known metrics- i.e. Hypervolume and Inverted Generational Distance (IGD). The experiments of our implemented approach is performed to illustrate that our proposal seems to be promising and would prove more efficient than other approaches in terms of both the performance and the computational cost.
Keywords
Introduction
Evolutionary Algorithms (EAs) are probabilistic optimizers inspired by the principles of natural evolution with some unique features among proposed optimization methods [1] including their flexibility and ease of implementation [2], and hence, they are applicable to a wide range of problems. Moreover, unlike classical optimizers, EAs are stochastic and population- based methods where a few individuals evolve into a new generation as the impact of stochastic variations in order to guide the search towards the best areas of the search space [1, 2].
Many optimization problems have multiple conflicting objectives known as Multiobjective Optimization Problems (MOPs). In such cases, a set of optimal solutions, called Pareto optimal set, is considered to form the best trade-offs between the entire objectives that confront. However, some problems focus only a single objective to be optimized as Single Objective Optimization Problems (SOPs) and one solution should be presented as the best solution [3]. Even though EAs are applied to a great variety of problems- as mentioned before- due to their population-based property, it will be illogical to use them to solve SOPs rather than MOPs [1]. Therefore, application of EAs to MOPs demonstrates a growing large-scale trend known as Multi-objective Evolutionary Algorithms (MOEAs).
The set of optimal solutions of MOEAs in the decision space is called non-dominated solutions that project a Pareto front in the objective space. Furthermore, MOEAs have been evaluated on a large number of objective functions to finally provide a fast and effective approximation of the real Pareto front. In some cases though, due to the high computational cost of the objective function evaluations, or, limited budget allocated to man-made systems [4], fitness approximation techniques can be integrated into MOEAs in order to decrease the number of exact fitness function evaluations. Using fitness approximation in MOEAs incorporates little knowledge to the system. Thus, it is essential to establish a balance between fitness approximation and fitness evaluation [5].
With a view to reduce computational cost, in this paper, following the fact that the ‘Survival of the Fittest’ in the actual world does not take place based on only one factor, we introduce an efficient factor through application of fuzzy conception beside various factors to a system, to exploit this natural tolerance. In order to enable this system to calculate the fitness evaluation of the chromosomes of value more accurately, we have employed a discriminative approach like Hypervolume concept. Thus, in addition to considerable reduction of computational cost, we have succeeded to direct the research towards Optima Pareto Set and hence improve the performance. The rest of this paper is organized as follows. Section 2 reviews the research literature. Section 3 presents proposed approaches. This is respectively followed by experimental setup and experimental results in Sections 4 and 5. Our proposed approach and its relevant results are discussed in Section 6. Finally, Section 7 concludes the paper.
Related work
Many real-world applications involve two or even more conflicting objectives. Due to their ability to achieve multiple optimal solutions in a single run as parallelism paradigms, Evolutionary Algorithms have attracted much attention particularly in relation to MOPs [6] in recent years. Despite the capability of MOEAs as optimization methods, their need to a significant number of objective function evaluations is considered a constraint. In order to deal with this, fitness approximation techniques are integrated into MOEAs. Three groups of these techniques have been so far categorized, namely problem approximation, functional approximation and evolutionary approximation [6].
Problem approximation is used to solve a complex problem in a more computationally efficient manner by replacing a simpler solvable problem with the original one. For example, while designing turbine blades, the performance should be evaluated on the basis of wind tunnel experiments. These experiments appear in the Euler equations and can be substituted for Computational Fluid Dynamics (CFD) and leads to Navier-Stokes equations [2–7].
In optimization methods and EAs in particular, functional approximation can estimate a model in terms of objective functions known as meta-model or surrogate model. Application of surrogate models in evolutionary computation has proved to be successful in reducing the computational cost of expensive objective evaluations [2, 7]. A recent research on surrogate-assisted evolutionary computation in MOPs proposed a Pareto rank learning scheme [8] where a model is learned through an embedded database and an ordinal SVM. In this method, fitness of each generated individual for evolutionary algorithm is evaluated explicitly and stored in an embedded database as a single training datum. This process continues until there is sufficient number of training data to learning the model. After that, the non-dominance sorting routine is used to assign ranks to training data [9]. Then, an ordinal SVM-based approach is used to learn a model. Finally, the rank for each generated individual is predicted based on the learned model. The assigned rank one describes a dominant individual and that the fitness evaluation of that individual has been performed explicitly. Also, the model is periodically upgraded according to the updated information for each generation.
Several related researches [10–12] propose an Aggregate Surrogate Model (ASM), i.e. the collaboration of One-Class Support Vector Machine (SVMs) and Support Vector Regression (SVR). SVMs are applied to map the training data of unsupervised learning onto that of the supervised learning, while SVR is applied to estimate the fitness of unseen data. ASM is also used for extrapolation. Therefore, instead of applying ordinary variations, informed operators usually generate many pre-children in order to provide enough search diversity. Since a learned model involves a high rate of errors in predictions, filtering generated pre-children only through ASM is not acceptable. The ASM in the nearest neighborhood of a non-inferior solution has been considered [10, 11, 10, 11]. ASM greedily detects to find an offspring, among pre-children, with maximal distance from the nearest neighbor [12]. However, because greedy search leads to premature convergence, a probabilistic selection is proposed besides using a normal distribution [2]. Although proposed models can deal with objective evaluations cost, there are still more problems with these models. First of all, the accuracy of the model depends largely on the training data. Likewise, the more the number of problem parameters, the larger will the complexity of the model tends to be. Moreover, the computational burden will be increasingly enhanced once the model is updated [13].
Evolutionary approximation is used specifically in EAs. In Fast Evolutionary Algorithm (FEA) [14], offspring inherit their fitness from their parents. However, fitness inheritance during evolution exponentially decreases precision of the evaluations. Thus, reliability of evaluated fitness for parents of each new offspring is incorporated. If the reliability value assigned to each new parent is lower than that of the threshold, fitness is explicitly evaluated; otherwise, the new offspring will inherit the fitness value of its parents. Despite the seemingly simplicity of this approach, since the similarity between each offspring and its parents is evaluated in the decision space, the performance is still unsatisfactory [13].
In order to address these concerns, a novel approach has been proposed as Adaptive Fuzzy Granulation NSGAII [15]. This method is based on information granulation that maintains a pool of fuzzy granules. Each fuzzy granule is a Gaussian Membership Function (GMF). The center width constant (CWC) of each GMF is an individual and a control parameter for fitness computation, respectively. Using approximate fitness evaluation of the control parameter during evolution leads to large approximation errors. Therefore, the control parameter [16] is instead evaluated based on the weighted rank of each fuzzy granule. The life index is yet another property of each fuzzy granule which is used not only to do the fitness approximation but also to control the computational complexity. In order to decide whether the fitness of an individual must be evaluated or approximated, a similarity metric known as Gaussian similarity function is used. Moreover, the computed width of each fuzzy granule is added to this criterion to control the degree of similarity between a new individual and the pool; if the maximum similarity value is higher than that of an adaptive threshold, its fitness is approximated and the life index of the most similar granule is increased by M-step. To simplify the evaluations [16], a predefined threshold (0.9) is considered instead of an adaptive one. The life index is used to determine which granule to be removed from the pool whenever the population size exceeds a certain threshold to prevent memory explosion.
In recent years, researchers have tried to improve the above-mentioned fitness approximation techniques; accordingly, the center width constant (CWC) of each fuzzy granule as a control parameter [17], the number of completed generations, the number of decision variables and maximum generations for fitness approximation have been investigated using Spread Spectrum Watermarking (SSW) [5].
On the whole, in many simulation and mechanical design problems, evaluation of multiple objective functions is quite expensive; thus, it is critical to decrease its computational cost even if its computational complexity increases. FFG_NSGAII has recently been a promising and competitive fitness approximation method to deal with this constraint. Although the decrease of the exact number of fitness function evaluations naturally yields lower bounds on the performance, in order for maximum reduction of computational cost without sacrificing the performance, the main concern is the exact identification of the qualified solutions to be evaluated. To this end, we propose a series of methods to directly or indirectly assess the qualification of each solution generated by such evolutionary process through which we have obtained superior results.
The proposed approach
Through the evolutionary algorithm, that exploits a random search to find solutions, a series of individuals, i.e. chromosomes, are randomly generated as an initial population for each member of which an exact fitness evaluation is thus performed, as they are all newly-made. While accompanied by a specific fitness value, every chromosome forms the center for each Gaussian Membership Function (GMF), i.e. fuzzy granule, which creates the pool.
As evolutionary algorithm automatically places the created population inside the evolutionary loop, the population of the next generation will be produced. Fitness values are also required to be attributed to the new individuals, and here arises the problem: an exact fitness evaluation or an approximation? The exact evaluation would be so costly in the real world and not all chromosomes are of such a high value to undergo an exact evaluation. Naturally the exact evaluation should be performed for a limited number, while the value of the rest should be approximated. Among the entire approaches used for approximation, FFG_NSGAII [16] has been the best to filter out non-promising individuals by means of a pool of solutions, a Gaussian similarity function and a fixed threshold.
Through a Gaussian similarity function, maximum similarity is detected between each new chromosome and the granules in the pool. If the similarity degree is found lower than the predefined threshold, its fitness is explicitly evaluated and it then is added to the pool;otherwise, the winner granule’ fitness is allocated to the new individual and the granule’s life index is increased (fitness is approximated). Since the exact evaluation of the ones of value is costly, the ones decided to undergo exact evaluation, will join the pool. Hence, the entire consequent decision will be made based on the granules of value, and hence, superior approximations are achieved. If the approximations were supposed to be computed based on previously approximated, it would dramatically deteriorate performance; conversely, if it is based on exact evaluations, it will not affect the performance, and thus, it will be maintained at the same level.
As evolutionary algorithm mimics natural selection, we discovered, apparently not just a single factor, like the offspring’s maximal distance from the nearest neighbor [12] and the assigned rank of each new offspring [8], contributes to the ‘Survival of the Fittest’, but more requirements must be involved, including both resources and suitable habitats. Accordingly, the Gaussian similarity function should necessarily be applied simultaneously with some other aspects of competing peers during evolution. Maintaining this natural tolerance, we have successfully designed the first fuzzy controller through a combination of effective factors, to precisely and trustworthily decide whether an explicit or approximate fitness evaluation is required, and consequently, which individual would have more chances to survive through evolution.
Our proposed fuzzy controller drastically decreases the number of expensive exact fitness evaluations. Despite the consequent entrance of less knowledge into the system and a failure of convergence near the global optima, due to our decision accuracy and superior filtering, the performance is at least maintained or even improved, as a fortunate offshoot of our experiment. Besides our fuzzy controller, we employed a co-evolutionary process as a powerful tool to determine whether the value of an individual is high enough for an accurate evaluation. Hypervolume content [18] was also finally combined with fuzzy concept for maximum reduction of computational cost, in addition to the significant improvement of the performance, in comparison with previous approaches.
Fuzzy fitness granulation with a fuzzy inference system
In order to be more accurate in recognizing and filtering the individuals of high value in the evolutionary process, we have proposed our efficiency factor besides the already applied factor. Since the final solutions are to be selected as the final Pareto set from the granules inside the pool, the filtering should be as strong as possible so that the best individuals can be selected. With this objective, our proposed factor should screen out the better chromosomes generated during the evolutionary process, do the exact fitness evaluation and add them to the pool. This process has dramatically decreased the exact fitness evaluation cost as the best chromosomes on which the exact evaluation is run will be entirely added to the pool.
Based on the natural patterns, as one factor proves to be quite insufficient to be considered in ‘Survival of the Fittest’ problem, thus, our proposed efficiency factor is integrated with the already applied one as the final filtering of which has been proved to be more accurate. At the end of each generation in the evolutionary process, through a non-dominant sorting mechanism employed as a preprocessing stage, the entire granules inside the pool are organized and receive ranks. A series of first rank solution will then form the current Pareto set (fuzzy granules of the first rank) for each generation.
Suppose that the size of the current Pareto set in ith generation is r, where the centre of jth fuzzy granule inside the pool may be written as
Additionally, the phenotype of kth generated individual is given below
By the end of the entire process, a set of first rank solutions is presented as the final Pareto set that contains the best possible chromosomes so far generated.
Knowing that solutions closest to the current Pareto set are fit enough for exact fitness evaluations, we have introduced our efficiency factor to guide the search toward the optimal Pareto set. Thus, the cost of objective function evaluations is reduced without performance being sacrificed. Our proposed factor demands the minimum distance between each new offspring and current Pareto set is first calculated followed by the calculation of the minimum distance between the parent of the same offspring and the current Pareto set. These two figures are then compared and as a result, the individual closer to the Pareto set, either the new offspring or the parent, is decided to be a better solution.
Applying Euclidean distance, the minimum distance of kth individual to r elements of the Current Pareto Set is evaluated based on Equation (1) [2].
In general, to determine whether the fitness value of an individual should be exactly evaluated or approximated, first their maximum similarity should be calculated and if their similarity is less than the predefined threshold, the minimum distance of the offspring and the parent from the current Pareto set should be subtracted.
If the result is negative, the new offspring will be a better solution than its parent due to its proximity to the Pareto set.
This proposed approach of ours is called Modified_FFG (M_FFG). Applying this efficiency factor, as it appears, makes algorithm computationally complicated, but precise selection of each solution for exact fitness function evaluation leads to remarkable reduction of the computational cost due to the more exact selection of chromosomes that is of great importance in MOEAs, particularly in expensive-to-evaluate objective functions. In other words, decreasing the computational cost is more significant whenever MOEAs are applied to solve problems with expensive-to-evaluate objective functions.
To this section of our experiment, we only applied Crisp Logic to the problem, which follows the bivalent classical logic and takes to be based on the two-element algebra and no intermediate element. However, during the experiment, we noticed three recurrent considerable shortfalls in Crisp Logic, as follows: It is not fair if a solution is considered to satisfy maximum similarity only if the similarity to a first rank granule is equal or more than 0.9, but if it is 0.89999 or less, it is not considered similar at all. Two individuals with different positive (negative) closeness (remoteness) rates to the current Pareto set, do not substantially share the same value; besides, this proximity can occur either on the right or the left side of the Pareto fronts, as the point of origin, that affects the value. As in all researches, the actual Pareto set is what is looked for, and since it is a minimization problem, the chromosome below the Pareto set, to which a negative number is attributed, is particularly considered a solution of more value. Therefore, a remoteness of +0.1 and –0.1 does actually make a difference to the favor of the latter. This is a significant notion to be taken into account in order to be able to make a more precise decision on which offspring is fit enough for exact fitness evaluation; the conventional employed logic though has been proved to be incapable of approaching it inany way. If the maximum similarity is close to 0.2 and thus the first condition is satisfied, but the minimum distance of the new offspring, compared to that of its parent, is farther and thus the second condition is not satisfied, the fitness value, according to what had been supposed and estimated, should be approximated. As in the real world, when there is a 20% similarity between two objects, it does not necessarily mean either is as good, and hence, no one single fitness value can be decided to be ascribed to both. The fitness value of this new offspring thereof should be exactly calculated.
A deeper understanding of the proposed approach is achieved when the workflow of MOEAs is embedded with our proposed MFIS, to reduce the computational cost of the evolutionary process on expensive multiobjective problems, demonstrated in Fig. 1. Accordingly, a pool of solutions is generated from the first generation where exact fitness evaluation is performed. As an expert, our proposed fuzzy controller precisely controls which individual, among the second generation to the end of the process, is fit enough to be explicitly evaluated by combining two efficiency factors. Since applying MOEAs to some real world problems is still computationally prohibitive [4], our method plays a key role in reducing the computational cost, and adds to the recent findings like FFG_NSGAII, which has been applied to two mechanical design problems, i.e. 2-D Truss frame design for maximum rigidity and voltage or design optimization of piezoelectric actuator patterns [13].
In fitness approximation mechanism, the main shortcoming, i.e. lack of precision, which is caused by the insertion of less knowledge to the system, naturally leads to the failure of convergence, even near the global optima. Hence, performance is expected to decline. The methods presented for fitness approximation should be designed both to reduce the computational cost while the performance is maintained or even improved [6]. To this point, two factors have been persistent in the approaches we have so far proposed: remarkable reduction of the computational cost and relatively maintained performance level.
In our search for an appropriate mechanism to perform as above, i.e. decrease the computational cost and improve the performance, in this section, we decided to employ the co-evolutionary process. Why? As there exists a Rank parameter in FFG_NSGAII similarity metric (Gaussian similarity function) as a part of it and an impressive factor in decision-making, ranking can be concluded to have a significant impact on this metric. Since our use of the non-dominant sorting mechanism for ranking in the evolutionary process, proved to produce more outputs of the same rank, and therefore, because a large number of fuzzy granules tend to be ranked the same, the ranking figure in this similarity metric has gradually lost its effectiveness. Thus, a replacement is required to be made for non-dominant sorting process. And that is co-evolutionary process, i.e. the domination process to be replaced by Hypervolume Approximation with Co-evolution process which is called Fuzzy Fitness Granulation with Co-evolution (FFG_C).
Inspired by [19], a set of goals of the maximum size of the pool, i.e. G, is generated. Each goal is the vector of random numbers within a range of objectives. The Hypervolume of both granules of the pool and the goals are evaluated based on Hypervolume approximation [19]. Both the individuals of the pool and the goals are separately sorted in ascending order. Pool is ranked for the similarity evaluation of each new offspring to the pool. Finally, M-top goals are selected for the next generation. In this way, there are fewer numbers of individuals with equal ranks. Thus, the higher the ranks with granules, the more similarity they share. As a result, the scale of similarity measurement changes from [0, 1] to [0.8, 1]. Also, the predefined threshold of similarity evaluations should be changed from 0.9 to 0.98. To be more illustrative, Hypervolume formula (Equation 2) will be explained in the next section.
Then, we applied this to FFG_NSGAII and waited for the result to integrate it with the fuzzy controller once the performance is improved. This method could also reduce the computational cost, but it could only maintain the performance, even not as favorable as FFG_FIS and M_FFG. Since our aim was to reduce the computational cost and improve the performance simultaneously, this method did not fulfill our target and thus could only help to solve expensive problems, yet not as well as the previously suggested frameworks.
In order to have a fast Hypervolume evaluation with greater accuracy, the rankings of the granules of the pool are induced by the Hypervolume Contribution as suggested in the recent research in Hypervolume indicator domain, introduced by Bader and Zitzler [18]. We call this work Fuzzy Fitness Granulation with Hypervolume Contribution (FFG_HC). Using Hypervolume Contribution, the results indicate a considerable reduction in the computational cost. Also, its performance is not as good as M_FFG but it is more acceptable than either FFG_FIS or FFG_C.
Fuzzy fitness granulation with hypervolume contribution
In comparison with the two previous methods, this improvement directed us to integrate the fuzzy controller with FFG_HC and obtain our much favored result: reduction of computational cost andimprovement in performance. Despite the inevitable increase of the computational complexity during this operation, as computational cost reduction is of greater significance than its complexity, what we have come to proves to be feasible in the actual world.
This novel approach to fitness approximation aims at a higher level of performance compared to its competitor methods, where the minimal number of the exact fitness evaluations is carried out while improving the performance. To this end, our fuzzy logic-inspired expert system acts as a decision maker, determining whether a fitness evaluation should be calculated for of an individual explicitly or via approximation and is combined with Hypervolume Contribution mechanism, as a discriminative factor to the pool, and constitutes the combinatorial system called FFG_FIS_HC.
In order to test how well our proposed approaches have succeeded, we have selected 13 test problems with different characteristics from two well-known benchmarks. Moreover, among the practical performance measures in the literature, i.e., HV and IGD are employed to validate our proposed approaches. In addition, we introduce a performance measure under AUC evaluation in the discussion section to explore the reason for the favourable performance of our five proposed approaches. Also, the statistical analysis is performed based on Friedman and Bonferroni-Dunn tests [20].
Employing evolutionary algorithm in a part of the problems in the actual world will be impossible at times if fitness approximation mechanism is not applied. Thus, we have tried to present a method to considerably lower the computational cost and improve the performance. As in the actual world, there is a gain for what you lose, in this regard, the computational complexity has been what we have lost for the aim we had set.”
The experimental setup
To illustrate the efficacy of our proposed approaches, we employ two popular performance measures and two sets of optimization test problems from different domains with various characteristics. The results are compared with respect to those obtained with a state of the art algorithm for fitness approximation as FFG_NSGAII [16].
Performance measures
In this section, we illustrate two popular indicators used especially in MOEAs to assess the quality of our proposed approaches.
Hypervolume
In minimization problem, the maximum quantity of objectives forms a vector called reference set. The volume enclosed by non-inferior solutions (N) and the reference set are computed by means of a number of hyper cubes (V
s
) in the grid. The union of evaluated hyper cubes is considered as Hypervolume indicator as follows [21]:
If we are given a true Pareto front (PF) and a set of candidate solutions (CS), where E
j
is the minimum Euclidean distance from each member of true Pareto front to candidate solutions, the Inverted Generational Distance indicator is evaluated as follows[22].
Benchmarks
To have a comprehensive assessment, we employ 1 traditional and 1 state-of-the-art optimization benchmarks which are explained below.
Congress on Evolutionary Computation 2009 (CEC09)
In CEC 2009 competition, two sets of optimization test problems were presented, which are bound constrained MOP test problem as UF family, and constrained test problems as CF family [23]. We chose 5 test problems from CF family, and 4 test problems from UF family with different characteristics (CF1 to CF5, UF1 to UF5 except UF4).
Zitzler-Deb-Thiele (ZDT)
As expressed in [24], ZDT family is a traditional benchmark adopted in MOPs. We employ 4 test problems- ZDT1 to ZDT4- in our experiments.
The experimental results
A part of the parameter settings of our conducted experiments in this paper are given as follows: Offspring are generated by Simulate Binary Crossover (SBX) with the probability of 0.9 and the applied mutation operator is Polynomial Mutation (PM) with the probability of 1/L, where L is the number of decision variables considering distributions η c = 20 and η m = 20 respectively. Also, in order to have a fair comparison between our approaches and our rival approach, all settings are taken from [16]. Furthermore, both the current population and the generated offspring participate in binary tournament selection which selects a new population for the next generation. Also, population size of 50 is used. Design parameters, such as reference points and the number of decision variables for test problem, are initialized which are depicted in Table 1. Also, all numerical results are the average of 30 independent runs so that a perfect assessment can be achieved.
One of the state-of-the-art approaches in the literature, which practically overcomes the computational cost of expensive objective functions in MOEAs is FFG_NSGAII (this method was applied in some mechanical design problems like 2-D Truss frame design for maximum rigidity and voltage or design optimization of piezoelectric actuator patterns [13]). Therefore, our proposed approaches are first conducted on several benchmarks such as ZDT, CF, and UF family. Then, they are compared with rival modern approaches. To this end, Figs. 4–6 demonstrate the diagrammatical representation of the reduced computational cost of our proposed approaches conducted on a set of representatives of the whole adopted test problems. The horizontal axis of each diagram is the number of generations for evolution and the vertical axis is the average number of exact fitness function evaluations.
To be more illustrative, for example in Fig. 4, the values of the exact fitness evaluations in 1000th generation (shown with filled squares) are 13296.29, 10188.58, 8882.23, 8179.65, 7116.71, and 4017.68 for FFG_NSGAII, FFG_C, M_FFG, FFG_FIS, FFG_HC, and FFG_FIS_HC respectively. Accordingly, the lowestnumber of exact fitness evaluations is related to FFG_FIS_HC, i.e. the ability of this method formaximum reduction of the computational cost is much greater than other suggested frameworks. Also, all suggested frameworks are capable of reducing the computational cost rather than FFG_NSGAII, remarkably. In other words, the lowest to the highest reduction rates of exact fitness evaluations are related to FFG_C, M_FFG, FFG_FIS, FFG_HC, and FFG_FIS_HC.
To compare the reduction rates of the computational cost with numerical results, we use Area Under the Curve (AUC) for each method through adopted test problems. The AUC is the integral of the curve and represents a total number of exact fitness function evaluations in generations during evolution. For test problems, this metric is separately computed for each method. Then, the percentage differences of computed AUC, FFG_NSGAII and that of other methods are calculated in sequence as the computational cost reduction in each suggested framework. In Table 2, the reader’s attention is drawn to the percentage difference of AUC which is incorporated to compare different suggested frameworks in terms of their ability to tackle the computational cost of some expensive problems compared to FFG_NSGAII. The results are shown in bold indicate, FFG_FIS_HC is most often more capable of decreasing the computational cost compared to the other methods.
Comprehensive statistical analysis is performed in the next section. Two well-known metrics in the literature (HV and IGD) are used to compare the performance of different methods. Tables 3 and 4 respectively present the performance of each method for test problem, based on the two introduced metrics. As it can be seen, there are some improvements in terms of performance of some adopted test problems through different methods presented in bold. At last, the results indicate the ability of our proposed approaches to reduce the computational cost without any tangible effect in the efficiency or efficacy. Even FFG_NSGAII is able to improve the performance with respect to both Hypervolume and Inverted Generational Distance measures. Furthermore, respect to derivative figures, it is clear that FFG_FIS_HC obtains the highest reduction rate of the computational cost than other proposed methods and FFG_NSGAII. Moreover, in the next section, we extensively try to show the stability of FFG_FIS_HC as well as itsperformance.
Discussion
Although there is an explicit fitness function available in most cases, in order to apply MOEAs to some real-world optimization problems, a large number of expensive objective functions should be evaluated. Therefore, fitness approximation can be integrated to each MOEA and used together with the explicit fitness function. However, applying fitness approximation leads to insertion of less knowledge into the system, and thus, natural decrease of the performance. Indeed, some comprehensive techniques should be presented, in which a set of high-value individuals would be selected throughout generations and directed to the explicit fitness function. In this paper, we contribute to this line of research by introducing a series of frameworks.
First of all, an efficiency factor was introduced besides the applied factor in FFG_NSGAII to filter out non-promising individuals more precisely. After that, we designed a fuzzy logic inference system as an expert system to prioritize the solutions in terms of their values. In our two suggested frameworks, the qualification of each candidate solution throughout generations has been directly evaluated. In order to improve the performance, we substitute non-dominant sorting with a co-evolutionary process. The results indicate no improvement in the performance but a decrease of the computational cost, though not as adequately as the other proposed approaches. Afterwards, Hypervolume Contribution, as a recent study of Hypervolume indicator domain, was substituted with the previous one.
In this way, we have so far achieved the highest computational cost reduction rate through four proposed approaches. According to the earlier discussion in subsection 3.2, the two above approaches indirectly affect our selections of individuals during evolution. We finally combine the expert system and the Hypervolume Contribution, through which, we could not only significantly reduce the computational cost compared to the previously suggested approaches as well as the competitive approach, but the performance could be also considerably improved.
In order to show that our proposed approach, FFG_FIS_HC, and the competitive approach, FFG_NSGAII, can generate a well-distributed Pareto set, we deployed Pareto fronts of those methods through 30 independent runs of 13 different test problems and considering a limited number of exact fitness evaluations with differing test problems, based on their convergence time. Since both methods are state-of-the-art, it is quite predictable that their Pareto fronts completely overlap each other. Figures 7–12 show the Pareto fronts of some representative test problems from different families (All other test problems share the same characteristics). Accordingly, since the comparison of these perfect methods in terms of their Pareto front shapes does not make any sense, we refer to two well-known metrics, Hypervolume and Inverted Generational Distance, to compare our results with the competitive approach [21, 22].
In some applications, possible number of exact fitness evaluations is considered a constraint. Hence, we limit the number of such evaluations to 100 to 1,000 (step size is set to 100) and compare the most recent approach to fitness approximation, FFG_NSGAII, which is studied in this paper, along with our proposed approaches, i.e. M_FFG, FFG_FIS, FFG_C, FFG_HC, and FFG_FIS_HC. The results are reported by using HV and IGD as two existing well-known performance metrics. Figures 13–18 show a comparison between the performance of different methods applied to the representatives of the families selected from the adopted test problems among a limited number of explicit fitness evaluations in terms of HV-metric and IGD-metric, respectively, over 30 independent runs. Derivative figures demonstrate that all suggested frameworks, except FFG_C, can improve the performance of FFG_NSGAII. Moreover, FFG_FIS_HC outperforms others.
Since the stability of the proposed algorithm is a matter of concern (Jin 2005), we computed the means and standard deviations of our proposed approaches through 30 independent runs of different test problems with a limited number of exact fitness evaluations, presented in Tables 5 and 6 for each of the performance metrics. Also, note that the number of standard deviations is less than 1% in almost all problems.
To be more illustrative, the means and standard deviations of FFG_FIS_HC are designed despite the limited number of exact fitness evaluations. Figures 19–26 depict some representatives of adopted test problems of the plotted figures. The results indicate that the variation of the performance (of both metrics) in all cases, gradually decreases as the algorithm evolves, which makes the algorithm stable enough to be considered as a candidate solution for the fitness approximation challenge.
In this regard, a comprehensive statistical analysis is performed as depicted in Table 7. Null-hypothesis has been rejected in Friedman test [20] for either performance metrics due to inequality among different methods. Therefore, a post-hoc statistical test like Bonferroni-Dun [20] is employed to check out whether the inequality obtained by Friedman test is statistically significant. According to Table 8, the results indicate our proposed approach (FFG_FUZ_HC) outperforms FFG_NSGAII in terms of performance measures. In the following parts, we show our proposed method also decreases the computational cost significantly.
Up until now, we have assessed the performance of each method through some fixed points. However, all possible numbers of explicit fitness evaluationscharacterized in terms of convergence time per test problem should be evaluated. Therefore, for each test problem, the entire methods should be run through a fixed number of generations and their performance should be compared. Figures 27–32 show the performance obtained for different suggested and studied methods, over three representatives of applied test problems and based on HV and IGD respectively [20, 21].
In the previous section, the ability of each suggested method to deal with expensive-to-evaluate objective functions has been assessed in terms of AUC. The results obtained in the previous section show the ability of our proposed approaches, FFG_FIS_HC in particular, to reduce the computational cost more considerably than the competitive approach (FFG_NSGAII). Now, we also aim to investigate the decreasing or even increasing rate of the Hypervolume of each method through a fixed number of generations of test problem based on AUC. In order for this, based on Figs. 27–32, the AUC of each method conducted on each test problem is evaluated. Then, the percentage differences of evaluated AUC among FFG_NSGAII and other methods are consecutively calculated. Experimental results in Table 5 demonstrate the percentage of performance decrease or even increase. Particularly, in FFG_HC, there are some enhancements in the performance presented in bold for some test problems such as CF3, CF4, and CF5. On the other hand, according to Table 2 in the previous section and Table 5 here, particularly in FFG_FIS_HC, the computational cost for some test problems such as CF4 has improved to more than 88% while the convergence speed has reduced to less than 1% . Related statistical analysis is performed in the following sections. For more clarity, column charts are used to indicate multiple measures of both computational cost reduction and Hypervolume fluctuation for different methods presented in Tables 2 and 9 in order, throughout the entire adopted test problems. The charts are respectively demonstrated in Figs. 33 and 34.
As explained before, applying fitness approximation techniques in MOEAs leads to insertion of lessknowledge into the system. Hence, decreasing thenumber of explicit fitness evaluations naturally accompanies performance decline. Thus, it is critical to develop methods which handle the computational cost without any effect on the performance. To gain a better understanding of the efficacy of our proposedmethods, we try to separately perform a thorough analysis of each proposed approach by using column charts. We assess each method under both decreasing computational cost and declining performance. The results are depicted in Figs. 35–39 related to M_FFG, FFG_FIS, FFG_C, FFG_HC, and FFG_FIS_HC, respectively. As it appears, derivative figures show that all our suggested approaches could tackle expensive-to-evaluate objective functions while the performance is almost maintained.
In search for the reason our proposed approaches achieve such results, we found out the ability to discover individuals qualified for explicit fitness evaluations during evolution, should be considered as a strong method employed to perform fitness approximation techniques.
In our experiments, all proposed approaches have been evaluated in terms of two different metrics- the computational cost reduction rate and the performance fluctuation rate by applying 13 different test problems through 1 classical and 1 state-of-the-art families of benchmarks in the literature. The complete results are depicted in Tables 2 and 5. According to each applied metric, to find the best method among the proposed ones, a multiple comparison is performed using Friedman test. In this case, the average rank of each method is calculated. As the results show in Table 6, each of FFG_FIS_HC and FFG_HC is ranked first in terms of the computational cost reduction and the Hypervolume in order.
As depicted in Table 11, in Friedman test, Null-hypothesis has been rejected in both metrics. Rejection of Null-hypothesis indicates that the various methods proposed are not equal. Hence, according to the rankings presented in Table 10, FFG_FIS_HC and FFG_HC are considered as control algorithms in the first and the second metrics respectively. Then, a post-hoc test, like Bonferroni-Dunn test, should be used to discover whether each control algorithm is statistically significant compared with other methods in terms of rank ordering obtained in Friedman test. As presented in Table 11, applying the first metric FFG_FIS_HC has statistical differences compared with the rest of methods which is discernible from absolute mean differences. Also, using the second metric FFG_HC is statistically significant when compared to three methods of FFG_FIS, FFG_C, and FFG_FIS_HC.
Conclusion
For some applications in MOEAs, a significant number of expensive objective functions must be evaluated. Although fitness approximation is an important notion to tackle such expensive evaluations, the challenge remains with how to select an individual for the exact fitness evaluation, capable of having great impact on the complexity and performance of the target MOEA.
In this study we focus on the deployment of fitness approximation techniques and propose a series of frameworks. We first introduce a factor inspired by information granulation that effectively weeds out non-promising individuals. Then, an expert system based on fuzzy logic is developed to prioritize individuals according to their weight values. After that, non-dominance sorting among achieved solutions is substituted by co-evolutionary Hypervolume approximation to screen out non-promising individuals during evolution. Afterwards Hypervolume Contribution [18] is applied instead of co-evolutionary process to not only improve the performance but also to decrease the computational cost. Finally, the expert system and Hypervolume Contribution are combined to reduce the computational cost as much as possible.
Basically, we employ two popular metrics available in the literature, i.e., HV, IGD as well as a proposed metric based on AUC evaluation, to inspect the capability of our proposed approaches in dealing with the computationally expensive problems with respect to a well-known representative fitness approximation techniques developed recently. Our comprehensive experiments to test problems in different domains with various features illustrate that our proposed methods offer a promising alternative and would provide more significant improvements over rival methods because of their remarkable role in computational cost reduction and performance improvement. Indeed, we can tackle multiple expensive objective evaluations in MOEAs by exploiting a set of fit individuals for their exact evaluations during evolution.