Search

Many-objective optimization is a hot issue in the EMO (evolutionary multiobjective optimization) community. Since almost all solutions in the current population are non-dominated with each other in many-objective EMO algorithms, we may need a different fitness evaluation scheme from the case of two and three objectives. One difficulty in the design of many-objective EMO algorithms is that we cannot visually observe the behavior of multiobjective evolution in the objective space with four or more objectives. In this paper, we propose the use of many-objective test problems in a two- or three-dimensional decision space to visually examine the behavior of multiobjective evolution. Such a visual examination helps us to understand the characteristic features of EMO algorithms for many-objective optimization. Good understanding of existing EMO algorithms may facilitates their modification and the development of new EMO algorithms for many-objective optimization. [ABSTRACT FROM AUTHOR]

This paper demonstrates that the performance of multiobjective memetic algorithms (MOMAs) for combinatorial optimization strongly depends on the choice of solutions to which local search is applied. We first examine the effect of the tournament size to choose good solutions for local search on the performance of MOMAs. Next we examine the effectiveness of an idea of applying local search only to non-dominated solutions in the offspring population. We show that this idea has almost the same effect as the use of a large tournament size because both of them lead to high selection pressures. Then we examine different configurations of genetic operators and local search in MOMAs. For example, we examine the use of genetic operators after local search. In this case, improved solutions by local search are used as parents for recombination while local search is applied to the current population after generation update. [ABSTRACT FROM AUTHOR]

Evolutionary algorithms have been successfully applied to design fuzzy rule-based classifiers. They are used for attribute selection, fuzzy set selection, rule selection, membership function tuning, and so on. Genetics-based machine learning (GBML) is one of the promising evolutionary algorithms for classifier design. It can find an appropriate combination of antecedent sets for each rule in a classifier. Although GBML has high search ability, it needs long computation time especially for large data sets. In this paper, we apply a parallel distributed implementation to our fuzzy genetics-based machine learning. In our method, we divide not only a population but also a training data set into subgroups. These subgroups are assigned to CPU cores. Through computational experiments on large data sets, we show the effectiveness of the proposed parallel distributed implementation. [ABSTRACT FROM AUTHOR]

It is well-known that multiobjective problems with many objectives are difficult for Pareto dominance-based algorithms such as NSGA-II and SPEA. This is because almost all individuals in a population are non-dominated with each other in the presence of many objectives. In such a population, the Pareto dominance relation can generate no strong selection pressure toward the Pareto front. This leads to poor search ability of Pareto dominance-based algorithms for many-objective problems. Recently it has been reported that better results can be obtained for many-objective problems by the use of scalarizing functions. The weighted sum usually works well in scalarizing function-based algorithms when the Pareto front is convex. However, we need other functions such as the weighted Tchebycheff when the Pareto front is non-convex. In this paper, we propose an idea of automatically choosing between the weighted sum and the weighted Tchebycheff for each individual in each generation. The characteristic feature of the proposed idea is to use the weighted Tchebycheff only when it is needed for individuals along non-convex regions of the Pareto front. The weighted sum is used for the other individuals in each generation. The proposed idea is combined with a high-performance scalarizing function-based algorithm called MOEA/D (multiobjective evolutionary algorithm based on decomposition) of Zhang and Li (2007). Effectiveness of the proposed idea is demonstrated through computational experiments on modified multiobjective knapsack problems with non-convex Pareto fronts. [ABSTRACT FROM AUTHOR]

In this chapter, we discuss various issues related to the implementation of multiobjective memetic algorithms (MOMAs) for combinatorial optimization problems. First we explain an outline of our MOMA, which is a hybrid algorithm of NSGA-II and local search. Our MOMA is a general framework where we can implement a number of variants. For example, we can use Pareto dominance as well as scalarizing functions such as a weighted sum in local search. Through computational experiments on multiobjective knapsack problems, we examine various issues in the implementation of our MOMA. More specifically, we examine the following issues: the frequency of local search, the choice of initial solutions for local search, the specification of an acceptance rule of local moves, the specification of a termination condition of local search, and the handling of infeasible solutions. We also examine the dynamic control of the balance between genetic operations (i.e., global search) and local search during the execution of our MOMA. Experimental results show that the hybridization with local search does not necessarily improve the performance of NSGA-II whereas local search with problem-specific knowledge leads to drastic performance improvement. Experimental results also show the importance of the balance between global search and local search. Finally we suggest some future research issues in the implementation of MOMAs. [ABSTRACT FROM AUTHOR]

This paper proposes an idea of using heuristic local search procedures specific for single-objective optimization in multiobjective genetic local search (MOGLS). A large number of local search techniques have been studied for various combinatorial optimization problems. Thus we may have a situation where a powerful local search procedure specific for a particular objective is available in multiobjective optimization. Such a local search procedure, however, can improve only a single objective. Moreover, it may have severe side-effects on the other objectives. For example, in a scheduling problem, an insertion move of a job with the maximum delay to an earlier position in a current schedule is likely to improve only the maximum tardiness. In this paper, we assume a situation where each objective has its own heuristic local search procedure. First we explain our MOGLS algorithm, which is the hybridization of NSGA-II and weighted sum-based local search. Next we propose an idea of using heuristic local search procedures specific for single-objective optimization in MOGLS. Then we implement the proposed idea as a number of variants of MOGLS. These variants are different from each other in the choice of a heuristic local search procedure. We examine three schemes: random, probabilistic and deterministic. Finally we examine the performance of each variant through computational experiments on multiobjective 0/1 knapsack problems with two, three and four objectives. It is shown that the use of heuristic local search procedures and their appropriate choice improve the performance of MOGLS. [ABSTRACT FROM AUTHOR]

Elitism has a large effect on the search ability of evolutionary algorithms. Many studies, however, did not discuss its different implementations in cellular algorithms. Usually a replacement policy called ˵replace-if-better″ is applied to each cell in cellular algorithms as a kind of elitism. In this paper, we examine three implementations of elitism. One is global elitism where a prespecified number of the best individuals in the entire population are viewed as being the elite. The replace-if-better policy is applied only to the globally best individuals. Another scheme is local elitism where an individual is viewed as being the elite if it is the best among its neighbors. The replace-if-better policy is applied only to the locally best individuals. The other scheme is cell-wise elitism where the replace-if-better policy is applied to all individuals. Effects of elitism are examined through computational experiments using a cellular genetic algorithm with two neighborhood structures. One is for local competition among neighbors. This competition neighborhood is used in the local elitism to determine the locally best individuals. The other is for local selection of parents. This selection neighborhood is also called the mating neighborhood. Since we have the two neighborhood structures, we can specify the size of the competition neighborhood for the implementation of the local elitism independent of the selection neighborhood for mating. Experimental results show that the use of the replace-if-better policy at all cells is not always the best choice. [ABSTRACT FROM AUTHOR]

We have already proposed multiobjective genetic fuzzy rule selection with a multi-classifier coding scheme for the design of ensemble classifiers. An entropy-based diversity measure was used as an objective to be maximized for increasing the diversity of base classifiers in an ensemble. In this paper, we examine the use of other diversity measures in the design of ensemble classifiers. Experimental results show that the choice of a diversity measure has a large effect on the performance of designed ensemble classifiers. [ABSTRACT FROM AUTHOR]

In our former study (Ishibuchi et al. 2006), we proposed the use of two neighborhood structures in a cellular genetic algorithm. One is for local selection where a pair of parents is selected from neighboring cells for mating. This neighborhood structure has been usually used in standard cellular algorithms. The other is for local competition, which is used to define local elitism and local ranking. We have already examined the effect of local elitism on the performance of our cellular genetic algorithm (Ishibuchi et al. 2008). In this paper, we examine the effect of using local ranking as the fitness of each individual. First we explain our cellular genetic algorithm with the two neighborhood structures. Then we examine its two variants with/without local ranking. In one variant, the local ranking of an individual among its neighbors is used as its fitness. Such a fitness redefinition scheme can be viewed as a kind of noise in parent selection. The other variant uses the original fitness value (instead of its local ranking). Through computational experiments, we demonstrate that the use of the local ranking improves the ability to escape from local optima. [ABSTRACT FROM AUTHOR]

The main goal in classifier design has been accuracy maximization on unseen patterns [23]. A number of learning algorithms have been proposed to minimize the classification errors on training patterns in various fields such as neural networks [84], fuzzy systems [76] and machine learning [81]. It is well-known that neural networks are universal approximators of nonlinear functions [34, 35]. Since fuzzy systems are also universal approximators [70, 73, 92], we can design fuzzy rule-based classifiers that can correctly classify all training patterns. Such a fuzzy rule-based classifier, however, does not usually have high accuracy on test patterns, as shown in Fig. 1, where a typical accuracy-complexity tradeoff relation is depicted. We can decrease the error rate of classifiers on training patterns by increasing their complexity (for example, by increasing the number of fuzzy rules in fuzzy rule-based classifiers), as shown by the dotted curve in Fig. 1. The classification accuracy on test patterns is, however, degraded by increasing the complexity too much, as shown by the solid curve in Fig. 1. Such an undesirable deterioration in the classification accuracy on test patterns is known as `overfitting to training patterns΄ [23]. Finding the optimal complexity with the maximum accuracy on test patterns (that is, S* in Fig. 1) is one of the main research issues in machine learning, especially in the field of statistical learning theory [10]. [ABSTRACT FROM AUTHOR]

This chapter discusses the application of evolutionary multi-objective optimization (EMO) to classification rule mining. In the field of classification rule mining, classifiers are designed through the following two phases: rule discovery and rule selection. In the rule discovery phase, a large number of classification rules are extracted from training data. This phase is based on two rule evaluation criteria: support and confidence. An association rule mining technique such as Apriori is usually used to extract classification rules satisfying pre-specified threshold values of the minimum support and confidence. In some studies, EMO algorithms were used to search for Pareto-optimal rules with respect to support and confidence. On the other hand, a small number of rules are selected from the extracted rules to design an accurate and compact classifier in the rule selection phase. A heuristic rule sorting criterion is usually used for rule selection. In some studies, EMO algorithms were used for multi-objective rule selection to maximize the accuracy of rule sets and minimize their complexity. In this chapter, first we explain the above-mentioned two phases in classification rule mining. Next we explain the search for Pareto-optimal rules and the search for Pareto-optimal rule sets. Then we explain evolutionary multi-objective rule selection as a post processing procedure in the second phase of classification rule mining. A number of Pareto-optimal rule sets are found from a large number of candidate rules, which are extracted from training data in the first phase. Finally we show experimental results on some data sets from the UCI machine learning repository. Through computational experiments, we demonstrate that evolutionary rule selection can drastically decrease the number of extracted rules without severely degrading their classification accuracy.We also examine the relation between Paretooptimal rules and Pareto-optimal rule sets. [ABSTRACT FROM AUTHOR]

Linguistic rules are fuzzy rules described by linguistic terms such as small and large. Here we discuss pattern classification with linguistic rules. The main advantage of using linguistic rules is their high interpretability. We can construct linguistically interpretable fuzzy rule-based classification systems using linguistic rules. First we briefly explain fuzzy rules for function approximation. Next we explain fuzzy rules and fuzzy reasoning for pattern classification. Then we explain linguistic rule extraction from numerical data. Finally we show some future research topics on pattern classification with linguistic rules. [ABSTRACT FROM AUTHOR]

Genetic fuzzy rule selection is an effective approach to the design of accurate and interpretable fuzzy rule-based classifiers. It tries to minimize the complexity of fuzzy rule-based classifiers while maximizing their accuracy by selecting only a small number of fuzzy rules from a large number of candidate rules. One important issue in genetic fuzzy rule selection is the prescreening of candidate rules. If we use too many candidate rules, a large computation load is required to search for good rule sets. On the other hand, good rule sets will not be found when promising fuzzy rules are not included in the candidate rule set. It is essential for the success of genetic fuzzy rule selection to use a tractable number of promising fuzzy rules as candidate rules. In this paper, we propose an idea of using Pareto-optimal and near Pareto-optimal fuzzy rules as candidate rules in genetic fuzzy rule selection. Pareto-optimality is defined by two well-known data mining criteria: support and confidence. To extract not only Pareto-optimal but also near Pareto-optimal fuzzy rules, we modify Pareto dominance using a dominance margin ε. Through computational experiments, we examine the effect of the proposed idea on multiobjective genetic fuzzy rule selection. [ABSTRACT FROM AUTHOR]

Genetic rule selection is an approach to the design of classifiers with high accuracy and high interpretability. It searches for a small number of simple classification rules from a large number of candidate rules. The effectiveness of genetic rule selection strongly depends on the choice of candidate rules. If we have hundreds of thousands of candidate rules, it is very difficult to efficiently search for their good subsets. On the other hand, if we have only a few candidate rules, rule selection does not make sense. In this paper, we examine the use of Pareto-optimal and near Pareto-optimal rules with respect to support and confidence as candidate rules in genetic rule selection. [ABSTRACT FROM AUTHOR]

We implement a cellular genetic algorithm with two neighborhood structures following the concept of structured demes: One is for interaction among individuals and the other is for mating. The effect of using these two neighborhood structures on the search ability of cellular genetic algorithms is examined through computational experiments on function optimization problems. Experimental results show that good results are obtained from the combination of a small interaction neighborhood and a large mating neighborhood. This relation in the size of the two neighborhood structures coincides with many cases of biological evolution in nature such as plants and territorial animals. It is also shown that the search ability of cellular genetic algorithms is deteriorated by the opposite combination of the two neighborhood structures. [ABSTRACT FROM AUTHOR]

This paper proposes an idea of probabilistically using a scalarizing fitness function in evolutionary multiobjective optimization (EMO) algorithms. We introduce two probabilities to specify how often the scalarizing fitness function is used for parent selection and generation update in EMO algorithms. Through computational experiments on multiobjective 0/1 knapsack problems with two, three and four objectives, we show that the probabilistic use of the scalarizing fitness function improves the performance of EMO algorithms. In a special case, our idea can be viewed as the probabilistic use of an EMO scheme in single-objective evolutionary algorithms (SOEAs). From this point of view, we examine the effectiveness of our idea. Experimental results show that our idea improves not only the performance of EMO algorithms for multiobjective problems but also that of SOEAs for single-objective problems. [ABSTRACT FROM AUTHOR]

In this paper, we demonstrate that simple fuzzy rule-based classification systems with high interpretability are obtained through multiobjective genetic rule selection. In our approach, first a prespecified number of candidate fuzzy rules are extracted from numerical data in a heuristic manner using rule evaluation criteria. Then multiobjective genetic rule selection is applied to the extracted candidate fuzzy rules to find a number of non-dominated rule sets with respect to the classification accuracy and the complexity. The obtained non-dominated rule sets form an accuracy-complexity tradeoff surface. The performance of each non-dominated rule set is evaluated in terms of its classification accuracy and its complexity. Computational experiments show that our approach finds simple fuzzy rules with high interpretability for some benchmark data sets in the UC Irvine machine learning repository. [ABSTRACT FROM AUTHOR]

The focus of this paper is the handling of overlapping solutions in evolutionary multiobjective optimization (EMO) algorithms. In the application of EMO algorithms to some multiobjective combinatorial optimization problems, there exit a large number of overlapping solutions in each generation. We examine the effect of removing overlapping solutions on the performance of EMO algorithms. In this paper, overlapping solutions are removed from the current population except for a single solution. We implement two removal strategies of overlapping solutions. One is the removal of overlapping solutions in the objective space. In this strategy, one solution is randomly chosen among the overlapping solutions with the same objective vector and left in the current population. The other overlapping solutions with the same objective vector are removed from the current population. As a result, each solution in the current population has a different location in the objective space. It should be noted that the overlapping solutions in the objective space are not necessary the same solution in the decision space. Thus we also examine the other strategy where the overlapping solutions in the decision space are removed from the current population except for a single solution. As a result, each solution in the current population has a different location in the decision space. The effect of removing overlapping solutions is examined through computational experiments where each removal strategy is combined into the NSGA-II algorithm. [ABSTRACT FROM AUTHOR]