2.1. Multi-objective evolutionary algorithms (MOEAs)

Most real-world decision problems require multi-objective optimization, which should be optimized simultaneously. Additionally, not any of the objectives have the same importance at any time¹⁸. Thus, the multi-objective optimization tries to find a set of solutions with an acceptable trade-off^11,10, and there is not a clear criterion to compare all these solutions due to the relative importance among objectives is unknown or variable. Without loss of generality, a multi-objective optimization problem (MOP) can be stated as the maximization of the vector function:

Then, a concept of Pareto domination where a solution u→ dominates another v→ (denoted as u→≽v→ ) if the following two conditions are satisfied:

1. 1.

   the solution u→ is not worse than v→ in all the objectives;

2. 2.

   the solution u→ is strictly better than v→ in at least one objective.

The initial representative Pareto-based approaches of MOEAs (NPGA and NSGA) lack of elitism so they cannot guarantee that the non-dominated solutions obtained during the search process are always preserved. Later some elitist multi-objective algorithms were published, some of the most important are: SPEA2, PAES, and NSGA-II.

With the grow of objectives number, the classic Pareto dominance used in NSGA-II and SPEA becomes ineffective to sort the quality of solutions, in this case, the population of non-dominated can be completely saturated. Then, the genetic operators are unable to compensate that effect. To solve this problem many approaches make modifications of the classic Pareto dominance including some relaxed forms of Pareto such as ɛ-dominance and α-domination. The ɛ-dominance acts as an archiving strategy and was proposed as a way for regulating convergence. The α-domination permits a solution x→ to dominate a solution y→ if x→ is slightly inferior to y→ in an objective but largely superior to y→ in some other objectives. Others approaches assigned different rankings levels to non-dominated solutions like in the paper of Sato et al.²⁵, where it was controlled the dominance area in order to induce appropriate ranking of solutions. This work showed that either convergence and diversity can be emphasized by contracting or expanding the dominance area. The R2-IBEA²⁶ algorithm eliminated dominance ranking in the selection process, and it performed an indicator-based selection with the R2 indicator. The R2 indicator had a stronger bias to the center of the Pareto front than to its edges.

2.2. Preference-based MOEA approaches

Another interesting way to address the multi-objective problem is to include preference information of an external decision maker. To the best of our knowledge, one of the first attempts to incorporate preferences in MOEAs was the work of Fonseca and Fleming²⁷. Their proposal was an extension of MOGA to accommodate goal information as an additional criterion to non-dominance to assign ranks to the population. However, Thiele et al.¹⁹ proposed a preference-based evolutionary approach where at each iteration the decision maker is asked to give preference information in terms of a reference point. Cetkovic and Parmee²⁸ converted fuzzy preferences into weights and a minimum threshold for dominance. Jin and Sendhoff ²⁹ proposed a way to convert the fuzzy preferences in intervals of weights and using the method of dynamic weighted aggregation introduced in a previous work. This approach converts the multi-objective problem in a single-objective by aggregating the weights. In¹⁸ a new relationship of dominance called “superior strength” to replace classic Pareto dominance was proposed. It is based on information from the preference between objectives and it is constructed with a fuzzy inference system to find solutions in the preferable regions. González et al.⁹ work modified the crowding distance (CD) by Objective Scale Crowding Distance (OSCD). The parents selection technique was modified by a Crowding-Based Mating heuristic and the population size was dynamically adjusted. The Preference-based Interactive Evolutionary (PIE) algorithm²⁰ used achievement scalarizing functions to help the decision maker to lead the search towards the desired Pareto optimal solution. Starting with approximation of the Nadir point. Guo and Wang³⁰ proposed a new fuzzy multi-objective lattice order decision method for preference ranking in conflict analysis. In RP²-NSGA-II³¹ addressed the problem of multi-criteria ranking with a medium-sized set of alternatives as a multi-objective combinatorial optimization problem.

To develop this work we are inspired in Deb et al.^22,23 and Yang et al.³² approaches. The R-NSGA-II and NSGA-III algorithms included preferences through reference points as well as a fast sorting scheme of non-dominated solutions and a modified crowding distance. The GrEA³² algorithm used the property of a grid to reflect the convergence and diversity information simultaneously. The performance of a solution regarding convergence can be estimated by the location of its grid compared to other solutions. The performance of a solution in connection to diversity can be estimated by the number of solutions with the same or similar grid location. In this work, Pareto-dominance was replaced by the Grid-dominance. This approach (x grid-domination) also balanced the diversity and convergence adaptively, varying the grid size.

2.3. MOEAs for classification

In a really interesting survey¹⁰, MOEAs for classification are categorized in three manners: evolving a good set of classification rules; defining the class boundaries (hyperplanes) in the training data; and modeling the construction of well known classifiers such as neural networks and decision trees. Our proposal is based on the first category by using a Michigan approach. Some major representative MOEAs for classification are described below.

In CEMOGA¹¹, binary chromosomes of variable length are used to encode the parameters of a varied set of hyperplanes. It simultaneously minimizes the number of misclassified training points and the number of hyperplanes whereas the accuracy is maximized. In this work, authors proposed two quantitative scores: purity and minimal space for evaluating multi-objective techniques. A comparison was done with other classifiers in six UCI data sets: Vowel, Iris, Cancer, Landsat, Mango and Crude Oil.

EMOGA¹³ is a nonfuzzy categorical classification rule mining algorithm, proposed using an elitist multi-objective genetic algorithm and a weighted sum of three objectives. In this work the experimental section included Zoo, Nursery and Adult data sets obtained from UCI repository.

In the work propsoed by Satchidananda et al.¹², an interesting multi-objective classification with gene expression programming was proposed. Here, two objectives were considered and the experimental section included two and three classes UCI data sets: Australian, Cloud, Cleveland, German data, Haberman, Heart, HouseVotes84, Iris, Pima and Wine. No comparison with other rule-based classifiers were done.

PAES-RCS¹⁴ generated a fuzzy rule-based classifier exploiting a multi-objective evolutionary algorithm. To learn the rule base they employed a rule and a condition selection approach. Two trade-offs objectives were used: accuracy and rule base complexity. The MOEA was tested by considering fifteen UCI data sets.

Cárdenas et al.¹⁵ proposed a multi-objective genetic process to generate fuzzy sets of rules. The algorithm was divided into three stages. The first one comprises the definition of an initial database with the same number of fuzzy sets for all attributes. The second and third stages were used for the rule generation and fuzzy sets optimization by means of multi-objective genetic algorithms to handle the accuracy-interpretability trade-off. The experimental section included seven UCI data sets: Iris, Wine, Thyroid, Heart, Sonar, Bupa and Breast.

3.1. Initial population

The generation of an initial population in GEP is a simple process. Here, it is only necessary to ensure that the head is generated with terminal and non-terminal elements and the tail only with terminal elements randomly taken from the element set (union of terminal and function set). The population size is defined in the pop_size algorithm parameter.

3.2. Genetic operators

In GEP, there are several genetic operators available to guide the evolutionary process, which can be categorized into: mutation, crossover and transposition operators. Sometimes particular GEP transposition operators are included within the mutation category, and other specific GEP operators listed below are included within crossover category. In this work we used the following genetic operators: simple mutator (GEPSimpleMutt), transposition of insertion sequence (GEPISTranspositionMutator), root transposition of insertion sequence (GEPRISTranspositionMutator), one-point recombination (GEPOnePointRecombinator) and two-point recombination (GEPTwoPointsRecombinator). All of them were implemented as recommended by Ferreira²⁴. A more detailed explanation of each one can be consulted in²⁴ or in the previous MCGEP²¹ work.

3.3. Function set and terminal set

In this paper, we used the basic arithmetic operations to build the discriminant functions that form the final classifier as a decision list; the function set was formed by the following operations: * (multiplication), / (division), + (addition) and − (subtraction). In all the cases, these functions were established with arity = 2. By now, we implement an algorithm only for numerical data sets. Terminals are attributes or elements from constant list defined in the configuration file.

3.4. Fitness function

Each individual encodes a rule in Michigan-style, representing a discriminant function and having a class as the consequent. It represents, in each run of the algorithm, the current class, so the algorithm runs as many times as classes exist in an one-vs-all approach. In this multi-objective algorithm, we have several objectives included in the fitness function, the equations 5, 6, 7 and 8 were used for each one.

The first two objectives have also been widely used as performance metrics for rules. The third is a good metric for finding rules with which a decision list can be built. The last objective guarantees a good interpretability in the final model. The tp, tn, fn and fp represent: true positives, true negatives, false negatives and false positives respectively from the confusion matrix obtained from evaluating an individual in the training set, see the figure 1.

Fig. 1.

Confusion matrix.

The term phenotSize in equation 8, is the length (number of terminal and non-terminal elements) of the expression tree coded in the phenotype of an individual, this factor reaches its maximum unitary value when a phenotype is as simplest as possible (length equal to one). This factor was designed as a negative slope line decreasing to a minimum of 0.1 when the length reaches the maximum pheno-type represented by the value maxSize.

3.5. Classification with discriminant functions

Discriminant functions are one of the schemes used in data mining for rules classification. In a discriminant function, the output is computed as a value that is the result of evaluating the function on input attributes. Then, this value must be compared with a threshold (normally 0) to associate it with the corresponding initial pattern classification. A classifier will consist in a list of discriminant functions where each function associates an output class. For the two classes case, the classifier would be as in equation 9, where X is the input feature vector. In this case the function f (X) split the characteristic space only into two regions.

The multi-class problem can be solved by using one-vs-all approach (OVA) where the n-class problem is transformed into n two-class problems. In this approach the instances of each class is taken as positive instances and the rest as negative ones. On the other hand, a way to build the classifier would be: finding a single discriminant function for each class. However, it has the disadvantage that in real world problems the space of feature is usually much more complex. Thus we need to find more than one function for each class so the proposed algorithm searches for discriminant functions to achieve a certain predefined level of coverage over all the instances for each class. Thus, a decision list is generated where the best functions are placed first. When a new instance is presented to this classifier, the first function of the list is evaluated. If it returns a positive value, then the class associated with this discriminant function is returned. On the contrary, if it returns a non-positive value, then the next discriminant function is evaluated, and so on. If no one returns a positive value, the most numerous class in the training set is returned as default.

4.1. R-NSGEP algorithm

R-NSGEP is a first step that allows to reach the adaptive version named AR-NSGEP. As previously said, the R-NSGEP implementation is based on the MOEA (R-NSGA-II) approach of Deb et al.²² as starting point. Initially, parent and offspring populations are joined. Then a non-dominated sorting is performed to classify the combined populations into different levels of non-domination. Solutions from the best non-domination levels are chosen and a modified crowding distance operator is used to choose a subset of solutions from the last front until the population size is reached. The following steps are then performed:

• •

  The normalized Euclidean distance is calculated from the ideal reference point to each front solution. With this, solutions are sorted in ascending order. The closest reference solution would be the first in crowding distance ranking. Solutions with a small crowding distance are preferred.

• •

  To control the quantity of solutions obtained, all the solutions having a normalized euclidean distance between them and ɛ or less are grouped. A randomly picked solution from each group is retained and the rest of the members of the group are assigned with a large crowding distance in order to discourage them (see Figure 2). This ɛ strategy is similar to that suggested in³⁴.

As shown in the pseudo-code (see Algorithm 1, line 4), the evolutionary process begins with the generation of the initial population bset with pop_size. Then, an iterative process in the population starts for several generations until any of the following stop conditions are reached: the maximum number of generations g_max is perfromed, or an individual with fitness ≈ 1 is obtained. In each generation, individuals are evaluated according to the objective functions defined in the subsection 3.4 (see equations 5, 6, 7, 8). The selection procedure is detailed in the pseudo-code (see Algorithm 1, line 8).

Fig. 2.

Epsilon reduction strategy.

Algorithm 1:

R-NSGEP, pseudo-code.

For each generation, we used the selection operator of the R-NSGA-II algorithm. This operator is based on a binary tournament, considering the fronts of non-dominance and the crowding distance. The crowding distance is also affected by the ɛ reduction strategy.

The GEP operators detailed in Section 3.2 are applied to the previously selected set of parents (pset), see lines 12 to 16; then, the obtained offspring (represented as rset) are evaluated as shown in line 16. Subsequently, on line 19, it is checked whether the adaptive strategy (AS) is performed. This AS is explained in the next section “AR-NSGEP. Adaptation with ROC analysis”. Parents and offspring are joined to be sorted in non-dominations fronts as R-NSGA-II does (see line 21). Then, a TCompet() (token competition) is performed on the union of the sets bset and eset. It returns a new non-redundant vector of individuals, eset as denoted line 21. The pseudo-code of this function is illustrated in Algorithm 2.

Algorithm 2:

Function TCompet(bset).

After finishing a complete generation, the whole process (starting at line 7) is repeated until the maximum number of generations is reached or until an individual achieves a fitness very close to 1.0. Once any of the previous stop conditions is reached, all the elements within eset are added to the classifier and the algorithm is initialized with the next class, repeating the whole process (starting now from line 3 in the pseudocode). In each complete iteration of the algorithm the class used to calculate the fitness is assigned as consequent of the rule, assuming as positive instances those belonging to that class and as negative those belonging to the other classes. The algorithm is repeated as many times as number of classes exist in the training set, and each cycle adds to the classifier all the rules coded in eset individuals, which is reset to an empty list each time (see line 26). At the end of the process, all the rules in the classifier are sorted according to its value of precision on the training subset not covered by the previous precision-best rule (used initially the best precision-rule over full training set). Precision is computed as illustrated in equation 7.

6.1. Training sets

To evaluate the behavior of our classifier, twenty-seven real-world data sets were chosen from KEEL^*38 and UCI^†39 repositories. To execute the experiments, data sets listed in Table 1 were used.

In our experimental assessment, all the examples with missing values were removed from the datasets. In Australian, Lymphography and Zoo datasets nominal attributes were binarized. In total, we have 14 binary problems, 5 three-class problems and 8 problems including between 5 and 10 classes. The evaluation of the quality of a classification algorithm may be seen as a multi-objective problem⁴⁰ so we used three metrics for the assessment. We evaluated the performance of models evolved by each learning system with the test accuracy metric (proportion of correct classifications over previously unseen examples), AUC (area under ROC curve) and number of rules of the models obtained in each case. We used a ten-fold cross validation procedure with 5 different random seeds over each data set.

6.2. Experimental tools

We used the JCLEC^‡ framework described in⁴¹, a software system for Evolutionary Computation (EC) research, developed in Java programming language. The parameters used in the algorithm are summarized in Table 2.

In our experiments, we used the chromosome size and constants list problem-dependent. The list of constants was fixed for all data sets except for the case of bands, pima and wine. In these cases, the constant values were different due to those data sets have attributes in a wide range of values. Note that no additional parameter optimization was done for R-NSGEP and AR-NSGEP. Thus, the configuration used for this algorithm should not be taken as the optimal set of parameters for each data set. Considering a particular dataset, a fine tuning may achieve even better results. The configuration files for AR-NSGEP and complementary material of the experimental study are publicly available at the link.^§

The way in which the size of the head in GEP is defined is still an open issue²⁴, so we have adjusted this parameter through trial and error with values equal to ten times the number of attributes for each dataset. The source codes and optimum configurations for CORE, GASSIST, HIDER, SLAVE, UCS and LOGIT-BOOST were based on KEEL³⁸ and their original authors as well as in the useful review³⁷.

6.3. Statistical analysis

We followed the recommendations pointed out by Derrac et al.⁴² to perform the statistical analysis of the results. As the authors suggested, non-parametric statistical tests are used to compare the accuracy and sizes of the models built by the different learning systems. Specifically, we used Friedman’s test. Derrac et al.⁴² found in their work that Finner and Li tests denoted the most powerful behavior, reaching the lowest p-values in the comparisons. Then, we applied these tests to arrive at solid conclusions. To statistical computations we used the “scmamp” library⁴³ implemented with the R programming language.

6.4. Experiment #1

In this experiment we analyze the behavior of the proposed algorithm for two, three and four objectives. The previous mono-objective version, MCGEP, is also included in this comparison. The average results for each collection are shown in Table 3. The last row shows the average rank for each algorithm.

The multi-comparison Friedman’s test rejected the following null hypotheses: all the systems performed the same on accuracy (Acc) with Friedman’s p – value = 1.1826 × 10⁻¹⁰; all the systems performed the same on AUC with Friedman’s p – value = 9.2003 × 10⁻⁹ and the number of rules in the models was equivalent on average with Friedman’s p – value = 7.3714 × 10⁻¹¹. To check the results, we apply Finner’s and Li’s methods to test the hypotheses ordered by their significance. As can be seen in Table 4, all tests with α = 0.05 detect a significant difference in Acc performance of AR-NSGEP against the rest.

As it is illustrated in Table 5, when analysing the AUC metric, Finner and Li test detected significant differences of AR-NSGEP against MCGEP, AR-NSGEP-3, R-NSGEP-3, AR-NSGEP-2 and R-NSGEP-2. In Figure 4, it is shown the Bonferroni-Dunn test comparing all systems in terms of number of rules.

Fig. 4.

Critical difference comparison of AUC and accuracy.

As it is illustrated, the three-objective versions and MCGEP obtained the simplest classifiers, however this is achieved at the expense of decreasing the values of the Acc and AUC metrics as shown in the previous test. On the other hand, it is clearly illustrated in Figure 4 that simpleness-objective versions significantly improved the ones that do not optimize the size of rules. Then, it was empirically manifested that finding simplest rules it is also possible to build more comprehensible classifiers. It was hoped that AR-NSGEP approach will fail to find good solutions in all metrics at the same time, but it finds good trade-off solutions. This version was built with three accuracy-objectives against only one comprehensibility-objective, then it generates much more selective pressure in the accuracy direction than the comprehensibility direction. As it is demonstrated, the proposed AR-NSGEP algorithm significantly improved the AUC and Acc metrics regarding to versions of three and two objectives, as well as versus the single-objective version (MCGEP). With this experiment, we verify the scalability in the number of objectives of the proposed approach.

6.5. Experiment #2

In this second experiment and similarly to the previous experiment, we assessed the performance of models evolved by each MOEA (NSGA-II, SPEA2 and R-NSGA-II implemented as R-NSGEP). The average results for each collection are shown in Table 6. According to the obtained results, we statistically analyze them to detect significant differences between models evolved by the different search methods. The multi-comparison Friedman’s test rejected the following two null hypotheses: performed the same on accuracy with Friedman’s p – value = 5.7925 × 10⁻³; performed the same on AUC with Friedman’s p – value = 4.1844 × 10⁻². The number of rules in the models was equivalent on average with Friedman’s p – value = 1.4474 × 10⁻¹. These last hypotheses were not rejected.

Then, we applied Finner’s and Li’s methods to test the hypotheses ordered by their significance. As can be seen in Tables 7 and 8, all the tests with α = 0.05 detected a significant difference in Acc and AUC performance for AR-NSGEP. As for the number of rules (NR) in the learned models, our proposal is not the first-ranking algorithm, then we decided to test all the pairwise comparisons with Bergmann and Hommel’s correction. For this we used the scmamp R-library implementation, in particular the function drawAlgorithmGraph() was used to generate a graph where all the significant differences among the combinations of algorithm-pairs are shown.

The graph illustrated in Figure 5 shows that the NSGA-II algorithm is the first in ranking. However, no significant difference was found according to the Bergmann’s test between the four algorithms evaluated in this experiment.

Fig. 5.

All pairwise comparisons obtained by Bergmann and Hommel’s method for NR metric.

6.6. Experiment #3

In this last experiment, we assessed the performance of AR-NSGEP algorithm against other six Genetic Rule Based Systems (GRBS) referenced by the specialized literature. The average results for each collection are shown in Table 11, where the last row indicates the average rank for each algorithm. The multi-comparison Friedman’s test rejected the following null hypotheses: all the systems performed the same on Acc with Friedman’s p – value = 6.7901 × 10⁻¹⁰; all the systems performed the same on AUC with Friedman’s p – value = 2.4236 × 10⁻¹³ and the number of rules in the models was equivalent on average with Friedman’s p – value < 2.2204 × 10⁻¹⁶.

Then we applied Finner’s and Li’s methods to test the hypotheses ordered by their significance. As illustrated in Table 9 for the Acc metric, both Finner’s and Li’s methods detected a significant improvement of our algorithm against CORE and SLAVE. In addition, the Finner’s test detected significant differences between our proposal and both Hider and LogitBoost. On the contrary, UCS and Gassist were not significantly improved by AR-NSGEP for the Acc metric.

As for the AUC metric, we applied the same tests as before. Table 10 illustrates that the proposed AR-NSGEP algorithm is the first in ranking and it significantly improves UCS, LogitBoost, Hider, SLAVE and CORE algorithms. All the test were applied with α = 0.05. On the contrary, Gassist was not significantly improved by AR-NSGEP.

Regarding to the metric number of rules (NR) in the learned models, we decided to test all pairwise comparisons with Bergmann and Hommel’s correction. Results shown in Figure 6 denote that CORE algorithm is significantly better than the rest, except for Gassist. CORE discovers nearly one-rule per class, this fact has a very high cost and it is also the worst in Acc and AUC metrics. Figure 6 shows that Gassist, Hider, SLAVE, R-NSGEP and AR-NSGEP are not significantly different between them.

Fig. 6.

All pairwise comparisons obtained by Bergmann and Hommel’s method for NR metric.

Next, Figure 7 represents the algorithms’ behavior in the metrics assessed (Acc, AUC and NR) at the same time. With this, we visualize in a better way the compromise solutions found by all the algorithms in this experiment. Therefore, we have represented the cut-off points defined by the Finner’s test for AUC and Acc metrics by horizontal and vertical lines respectively. Finally, we combined the Bergmann and Hommel’s test by linking the equivalent algorithms. Our proposal, AR-NSGEP, is marked as the most well balanced of all methods analyzed in this work when only Acc and AUC metrics are taken into account. Additionally, Gassist appears as one of the most balanced algorithm too.

Fig. 7.

Combining Finner’s for Acc and AUC metrics with Bergmann and Hommel’s tests for NR metric.

In favour of the proposed AR-NSGEP approach, we can assert that, rule-set complexity for discriminant functions is not exactly the same of rule-based complexity. Gassist were stated in the review⁴⁴ as one of “the two most outstanding learners in the GBML history”.