Evolutionary Multi-Criterion Optimization

The maximin fitness function can be used in multi-objective genetic algorithms to obtain a diverse set of non-dominated designs. The maximin fitness function is derived from the definition of dominance, and its properties are explored. The modified maximin fitness function is proposed. Both fitness functions are briefly compared to a state-of-the-art fitness function from the literature. Results from a real-world multi-objective problem are presented. This problem addresses land-use and transportation planning for high-growth cities and metropolitan regions.

This paper contributes a platform for the treatment of large numbers of criteria in evolutionary multi-criterion optimisation theory through consideration of the relationships between pairs of criteria. In a conflicting relationship, as performance in one criterion is improved, performance in the other is seen to deteriorate. If the relationship is harmonious, improvement in one criterion is rewarded with simultaneous improvement in the other. The criteria may be independent of each other, where adjustment to one never affects adjustment to the other. Increasing numbers of conflicting criteria pose a great challenge to obtaining a good representation of the global trade-off hypersurface, which can be countered using decision-maker preferences. Increasing numbers of harmonious criteria have no effect on convergence to the surface but difficulties may arise in achieving a good distribution. The identification of independence presents the opportunity for a divide-and-conquer strategy that can improve the quality of trade-off surface representations.

Fitness evaluation in real-world applications often causes a lot of computational overhead. Fitness inheritance has been proposed for tackling this problem. Instead of evaluating each individual, a certain percentage of the individuals is evaluated indirectly by interpolating the fitness of their parents. However, the problems on which fitness inheritance has been tested are very simple and the question arises whether fitness inheritance is really useful for real-world applications. The objective of this paper is to test the performance of average and weighted average fitness inheritance on a well-known test suite of multiple objective optimization problems. These problems have been generated as to constitute a collection of test cases for genetic algorithms. Results show that fitness inheritance can only be applied to convex and continuous problems.

The paper concerns a multiobjective heuristic to compute approximate efficient solutions for the assignment problem with two objectives. The aim here is to show that the genetic information extracted from supported solutions constitutes a useful genetic heritage to be used by crossover operators to approximate non-supported solutions. Bound sets describe one acceptable limit for applying a local search over an offspring. Results of extensive numerical experiments are reported. All exact efficient solutions are obtained using Cplex in a basic enumerative procedure. A comparison with published results shows the efficiency of this approach.

Pareto optimality is someway ineffective for optimization problems with several (more than three) objectives. In fact the Pareto optimal set tends to become a wide portion of the whole design domain search space with the increasing of the numbers of objectives. Consequently, little or no help is given to the human decision maker. Here we use fuzzy logic to give two new definitions of optimality that extend the notion of Pareto optimality. Our aim is to identify, inside the set of Pareto optimal solutions, different “degrees of optimality” such that only a few solutions have the highest degree of optimality; even in problems with a big number of objectives. Then we demonstrate (on simple analytical test cases) the coherence of these definitions and their reduction to Pareto optimality in some special subcases. At last we introduce a first extension of (1+1)ES mutation operator able to approximate the set of solutions with a given degree of optimality, and test it on analytical test cases.

This paper introduces a new constraint-handling method called Inverted-Shrinkable PAES (IS-PAES), which focuses the search effort of an evolutionary algorithm on specific areas of the feasible region by shrinking the constrained space of single-objective optimization problems. IS-PAES uses an adaptive grid as the original PAES (Pareto Archived Evolution Strategy). However, the adaptive grid of IS-PAES does not have the serious scalability problems of the original PAES. The proposed constraint-handling approach is validated with several examples taken from the standard literature on evolutionary optimization.

We present PICPA, a new algorithm for tackling constrained continuous multi-objective problems. The algorithm combines constraint propagation techniques and evolutionary concepts. Unlike other evolutionary algorithm which gives only heuristic solutions, PICPA is able to bound effectively the Pareto optimal front as well as to produce accurate approximate solutions.

In complex engineering problems, often the objective functions can be very slow to evaluate. This paper introduces a new algorithm that aims to provide controllable exploration and exploitation of the decision space with a very limited number of function evaluations. The paper compares the performance of the algorithm to a typical evolutionary approach.

We present new hierarchical set oriented methods for the numerical solution of multi-objective optimization problems. These methods are based on a generation of collections of subdomains (boxes) in parameter space which cover the entire set of Pareto points. In the course of the subdivision procedure these coverings get tighter until a desired granularity of the covering is reached. For the evaluation of these boxes we make use of evolutionary algorithms. We propose two particular strategies and discuss combinations of those which lead to a better algorithmic performance. Finally we illustrate the efficiency of our methods by several examples.

Improved sample-based trade-off surface representations for large numbers of performance criteria can be achieved by dividing the global problem into groups of independent, parallel sub-problems, where possible. This paper describes a progressive criterion-space decomposition methodology for evolutionary optimisers, which uses concepts from parallel evolutionary algorithms and nonparametric statistics. The method is evaluated both quantitatively and qualitatively using a rigorous experimental framework. Proof-of-principle results confirm the potential of the adaptive divide-and-conquer strategy.

We present a new method for solving a multi-level multi-objective optimization problem that is hierarchically decomposed into several sub-problems. The method preserves diversity of Pareto solutions by maximizing an entropy metric, a quantitative measure of distribution quality of a set of solutions. The main idea behind the method is to optimize the sub-problems independently using a Multi-Objective Genetic Algorithm (MOGA) while systematically using the entropy values of intermediate solutions to guide the optimization of sub-problems to the overall Pareto solutions. As a demonstration, we applied the multi-level MOGA to a mechanical design example: the design of a speed reducer. We also solved the example in its equivalent single-level form by a MOGA. The results show that our proposed multi-level multi-objective optimization method obtains more Pareto solutions with a better diversity compared to those obtained by the single-level MOGA.

In this paper, we propose an approach for solving hierarchical multi-objective optimization problems (MOPs). In realistic MOPs, two main challenges have to be considered: (i) the complexity of the search space and (ii) the non-monotonicity of the objective-space. Here, we introduce a hierarchical problem description (chromosomes) to deal with the complexity of the search space. Since Evolutionary Algorithms have been proven to provide good solutions in non-monotonic objective-spaces, we apply genetic operators also on the structure of hierarchical chromosomes. This novel approach decreases exploration time substantially. The example of system synthesis is used as a case study to illustrate the necessity and the benefits of hierarchical optimization.

For any optimization algorithm tuning the parameters is necessary for effective and effcient optimization. We use a meta-level evolutionary algorithm for optimizing the effectiveness and effciency of a load-balancing evolutionary algorithm. We show that the generated parameters perform statistically better than a standard set of parameters and analyze the importance of selecting a good region on the Pareto Front for this type of optimization.

This paper investigates the exploitation of non-dominated sets’ schemata in guiding multi-objective optimization. Schemata capture the similarities between solutions in the non-dominated set. They also reflect the knowledge acquired by multi-objective evolutionary algorithms. A schemata-driven genetic algorithm as well as a schemata-driven local search algorithm are described. An experimental study to evaluate the suggested approach is then conducted.

This paper proposes a real-coded predator-prey GA for multiobjective optimization (RCPPGA). The model takes its inspiration from the spatial predator-prey dynamics observed in nature. RCPPGA differs itself from previous similar work by placing a specific emphasis on introducing a dynamic spatial structure to the predator-prey population. RCPPGA allows dynamic changes of the prey population size depending on available space and employs a BLX-α crossover operator that encourages a more self-adaptive search. Experiments using two different fitness assignment methods have been carried out, and the results are compared with previous related work. Although RCPPGA does not employ elitism explicitly (such as using an external archive), it has been demonstrated that given a sufficiently large lattice size, RCPPGA can consistently produce and maintain a diverse distribution of nondominated optimal solutions along the Pareto-optimal front even after many generations.

The trade-off between obtaining a good distribution of Pareto-optimal solutions and obtaining them in a small computational time is an important issue in evolutionary multi-objective optimization (EMO). It has been well established in the EMO literature that although SPEA produces a better distribution compared to NSGA-II, the computational time needed to run SPEA is much larger. In this paper, we suggest a clustered NSGA-II which uses an identical clustering technique to that used in SPEA for obtaining a better distribution. Moreover, we propose a steady-state MOEA based on ε-dominance concept and effcient parent and archive update strategies. Based on a comparative study on a number of two and three objective test problems, it is observed that the steady-state MOEA achieves a comparable distribution to the clustered NSGA-II with a much less computational time.

In real-world applications, it is often desired that a solution is not only of high performance, but also of high robustness. In this context, a solution is usually called robust, if its performance only gradually decreases when design variables or environmental parameters are varied within a certain range. In evolutionary optimization, robust optimal solutions are usually obtained by averaging the fitness over such variations. Frequently, maximization of the performance and increase of the robustness are two conflicting objectives, which means that a trade-off exists between robustness and performance. Using the existing methods to search for robust solutions, this trade-off is hidden and predefined in the averaging rules. Thus, only one solution can be obtained. In this paper, we treat the problem explicitly as a multiobjective optimization task, thereby clearly identifying the trade-off between performance and robustness in the form of the obtained Pareto front. We suggest two methods for estimating the robustness of a solution by exploiting the information available in the current population of the evolutionary algorithm, without any additional fitness evaluations. The estimated robustness is then used as an additional objective in optimization. Finally, the possibility of using this method for detecting multiple optima of multimodal functions is briefly discussed.

In this paper, we deal with an important issue generally omitted in the current literature on evolutionary multiobjective optimization: on-line adaptation. We propose a revised version of our micro-GA for multiobjective optimization which does not require any parameter fine-tuning. Furthermore, we introduce in this paper a dynamic selection scheme through which our algorithm decides which is the “best’ crossover operator to be used at any given time. Such a scheme has helped to improve the performance of the new version of the algorithm which is called the micro-GA2 (μGA2). The new approach is validated using several test function and metrics taken from the specialized literature and it is compared to the NSGA-II and PAES.

Evolutionary Algorithms are a standard tool for multi-objective optimization that are able to approximate the Pareto front in a single optimization run. However, for some selection operators, the algorithm stagnates at a certain distance from the Pareto front without convergence for further iterations.We analyze this observation for different multi-objective selection operators. We derive a simple analytical estimate of the stagnation distance for several selection operators, that use the dominance criterion for the fitness assignment. Two of the examined operators are shown to converge with arbitrary precision to the Pareto front. We exploit this property and propose a novel algorithm to increase their convergence speed by introducing suitable self-adaptive mutation. This adaptive mutation takes into account the distance to the Pareto front. All algorithms are analyzed on a 2- and 3-objective test function.

An evolutionary multi-objective optimization tool based on an estimation of distribution algorithm is proposed. The algorithm uses the ranking method of non-dominated sorting genetic algorithm-II and the Parzen estimator to approximate the probability density of solutions lying on the Pareto front. The proposed algorithm has been applied to different types of test case problems and results show good performance of the overall optimization procedure in terms of the number of function evaluations. An alternative spreading technique that uses the Parzen estimator in the objective function space is proposed as well. When this technique is used, achieved results appear to be qualitatively equivalent to those previously obtained by adopting the crowding distance described in non-dominated sorting genetic algorithm-II.

We describe, and make publicly available, two problem instance generators for a multiobjective version of the well-known quadratic assignment problem (QAP). The generators allow a number of instance parameters to be set, including those controlling epistasis and inter-objective correlations. Based on these generators, several initial test suites are provided and described. For each test instance we measure some global properties and, for the smallest ones, make some initial observations of the Pareto optimal sets/fronts. Our purpose in providing these tools is to facilitate the ongoing study of problem structure in multiobjective (combinatorial) optimization, and its effects on search landscape and algorithm performance.

Parametric and dynamic multiobjective optimization problems for adaptive optimal control are carefully defined; some test problems are introduced for both continuous and discrete design spaces. A simple example of a dynamic multiobjective optimization problems arising from a dynamic control loop is given and an extension for dynamic situation of a previously proposed search direction based method is proposed and tested on the proposed test problems.

The classic NFL theorems are invariably cast in terms of single objective optimization problems. We confirm that the classic NFL theorem holds for general multiobjective fitness spaces, and show how this follows from a ‘single-objective’ NFL theorem. We also show that, given any particular Pareto Front, an NFL theorem holds for the set of all multiobjective problems which have that Pareto Front. It follows that, given any ‘shape’ or class of Pareto fronts, an NFL theorem holds for the set of all multiobjective problems in that class. These findings have salience in test function design. Such NFL results are cast in the typical context of absolute performance, assuming a performance metric which returns a value based on the result produced by a single algorithm. But, in multiobjective search we commonly use comparative metrics, which return performance measures based non-trivially on the results from two (or more) algorithms. Closely related to but extending the observations in the seminal NFL work concerning minimax distinctions between algorithms, we provide a ‘Free Leftovers’ theorem for comparative performance of algorithms over permutation functions; in words: over the space of permutation problems, every algorithm has some companion algorithm(s) which it outperforms, according to a certain well-behaved metric, when comparative performance is summed over all problems in the space.

Evolutionary Multi-objective Optimization(EMO) is becoming a hot research area and quite a few aspects of Multi-objective Evolutionary algorithms(MOEAs) have been studied and discussed. However there are still few literatures discussing the roles of search and selection operators in MOEAs. This paper studied their roles by a representative combinatorial Multi-objective Problem(MOP): Multi-objective TSP. In the new MOEA, We adopt an efficient search operator, which has the properties of both crossover and mutation, to generate the new individuals and chose two kinds of selection operators: Family Competition and Population Competition with probabilities to realize selection. The simulation experiments showed that this new MOEA could get good uniform solutions representing the Pareto Front and outperformed SPEA in almost every simulation run on this problem. Furthermore, we analyzed its convergence property using Finite Markov Chain and proved that it could converge to Pareto Front with probability 1. We also find that the convergence property of MOEAs has much relationship with search and selection operators.

We propose a multi-objective generalisation for the well known Counting Ones problem, called the Multi-objective Counting Ones (MOCO) function. It is shown that the problem has four qualitative different regions. We have constructed a convergence time model for the Simple Evolutionary Multi-objective Optimiser (SEMO) algorithm. The analysis gives insight in the convergence behaviour in each region of the MOCO problem. The model predicts a ℓ2 ln ℓ running time, which is confirmed by the experimental runs.

This paper examines the use of fitness sharing in evolutionary multiobjective optimization (EMO) algorithms to form a uniform distribution of niches along the non-dominated frontier. A long-standing, implicit assumption is that fitness sharing within an equivalence class, such as the Pareto optimal set, can form dynamically stable (under selection) subpopulations evenly spaced along the front. We show that this behavior can occur, but that it is highly unlikely. Rather, it is much more likely that a steady-state will be reached in which stable niches are maintained, but at inter-niche distances much less than the specified niche radius, with several times more niches than previously predicted, and with non-uniform sub-population sizes. These results might have implications for EMO population sizing, and perhaps even for EMO algorithm design itself.

MOEAs are getting immense popularity in the recent past, mainly because of their ability to find a wide spread of Pareto-optimal solutions in a single simulation run. Various evolutionary approaches to multi-objective optimization have been proposed since 1985. Some of fairly recent ones are NSGA-II, SPEA2, PESA (which are included in this study) and others. They all have been mainly applied to two to three objectives. In order to establish their superiority over classical methods and demonstrate their abilities for convergence and maintenance of diversity, they need to be tested on higher number of objectives. In this study, these state-of-the-art MOEAs have been investigated for their scalability with respect to the number of objectives (2 to 8). They have also been compared on the basis of -(1) Their ability to converge to Pareto front, (2) Diversity of obtained non-dominated solutions and (3) Their running time. Four scalable test problems (DTLZ1, 2, 3 and 6) are used for the comparative study.

A number of authors made the claim that a multiobjective approach preserves genetic diversity better than a single objective approach. Sofar, none of these claims presented a thorough analysis to the effect of multiobjective approaches. In this paper, we provide such analysis and show that a multiobjective approach does preserve reproductive diversity. We make our case by comparing a pareto multiobjective approach against a single objective approach for solving single objective global optimization problems in the absence of mutation. We show that the fitness landscape is different in both cases and the multiobjective approach scales faster and produces better solutions than the single objective approach.

Numerous quality assessment metrics have been developed by researchers to compare the performance of different multi-objective evolutionary algorithms. These metrics show different properties and address various aspects of solution set quality. In this paper, we propose a conceptual framework for selection of a handful of these metrics such that all desired aspects of quality are addressed with minimum or no redundancy. Indeed, we prove that such sets of metrics, referred to as ‘minimal sets’, must be constructed based on a one-to-one correspondence with those aspects of quality that are desirable to a decision-maker.

The design of Pressurized Water Reactor (PWR) reload cores is a difficult combinatorial optimization problem with multiple competing objectives. This paper describes the use of a Genetic Algorithm (GA) to perform true multiobjective optimization on the PWR reload core design problem and improvements made to its performance in identifying nondominated solutions to represent the trade-off surface between competing objectives. The use of different pairing strategies for combining parents is investigated and found to produce promising results in some cases.

This paper examines the effect of mating restriction on the search ability of EMO algorithms. First we propose a simple but flexible mating restriction scheme where a pair of similar (or dissimilar) individuals is selected as parents. In the proposed scheme, one parent is selected from the current population by the standard binary tournament selection. Candidates for a mate of the selected parent are winners of multiple standard binary tournaments. The selection of the mate among multiple candidates is based on the similarity (or dissimilarity) to the first parent. The strength of mating restriction is controlled by the number of candidates (i.e., the number of tournaments used for choosing candidates from the current population). Next we examine the effect of mating restriction on the search ability of EMO algorithms to find all Pareto-optimal solutions through computational experiments on small test problems using the SPEA and the NSGA-II. It is shown that the choice of dissimilar parents improves the search ability of the NSGA-II on small test problems. Then we further examine the effect of mating restriction using large test problems. It is shown that the choice of similar parents improves the search ability of the SPEA and the NSGA-II to efficiently find near Pareto-optimal solutions of large test problems. Empirical results reported in this paper suggest that the proposed mating restriction scheme can improve the performance of EMO algorithms for many test problems while its effect is problem-dependent and algorithm-dependent.

Many resource allocation issues, such as land use- or irrigation planning, require input from extensive spatial databases and involve complex decision-making problems. Recent developments in this field focus on the design of allocation plans that utilize mathematical optimization techniques. These techniques, often referred to as multi criteria decision-making (MCDM) techniques, run into numerical problems when faced with the high dimensionality encountered in spatial applications. In this paper, it is demonstrated how both Simulated annealing, a heuristic algorithm, and Goal Programming techniques can be used to solve high-dimensional optimization problems for multi-site land use allocation (MLUA) problems. The optimization models both minimize development costs and maximize spatial compactness of the allocated land use. The method is applied to a case study in The Netherlands.

In this paper a Population-based Ant Colony Optimization approach is proposed to solve multi-criteria optimization problems where the population of solutions is chosen from the set of all non-dominated solutions found so far. We investigate different maximum sizes for this population. The algorithm employs one pheromone matrix for each type of optimization criterion. The matrices are derived from the chosen population of solutions, and can cope with an arbitrary number of criteria. As a test problem, Single Machine Total Tardiness with changeover costs is used.

This article proposes the Two-Phase Local Search for finding a good approximate set of non-dominated solutions. The two phases of this procedure are to (i) generate an initial solution by optimizing only one single objective, and then (ii) to start from this solution a search for non-dominated solutions exploiting a sequence of different formulations of the problem based on aggregations of the objectives. This second phase is a single chain, using the local optimum obtained in the previous formulation as a starting solution to solve the next formulation. Based on this basic idea, we propose some further improvements and report computational results on several instances of the biobjective TSP that show competitive results with state-of-the-art algorithms for this problem.

This paper introduces an interface specification (PISA) that allows to separate the problem-specific part of an optimizer from the problem-independent part. We propose a view of the general optimization scenario, where the problem representation together with the variation operators is seen as an integral part of the optimization problem and can hence be easily separated from the selection operators. Both parts are implemented as independent programs, that can be provided as ready-to-use packages and arbitrarily combined. This makes it possible to specify and implement representation-independent selection modules, which form the essence of modern multiobjective optimization algorithms. The variation operators, on the other hand, have to be defined in one module together with the optimization problem, facilitating a customized problem description. Besides the specification, the paper contains a correctness proof for the protocol and measured efficiency results.

We propose a new data structure for the efficient computation of the nondominance problem which occurs in most multi-objective optimization algorithms. The strength of our data structure is illustrated by a comparison both to the linear list approach and the quad tree approach on a category of problems. The computational results indicate that our method is particularly advantageous in the case where the proportion of the nondominated vectors versus the total set of criterion vectors is not too large.

This article describes a set function that maps a set of Pareto optimal points to a scalar. A theorem is presented that shows that the maximization of this scalar value constitutes the necessary and sufficient condition for the function’s arguments to be maximally diverse Pareto optimal solutions of a discrete, multi-objective, optimization problem. This scalar quantity, a hypervolume based on a Lebesgue measure, is therefore the best metric to assess the quality of multiobjective optimization algorithms. Moreover, it can be used as the objective function in simulated annealing (SA) to induce convergence in probability to the Pareto optima. An efficient, polynomial-time algorithm for calculating this scalar and an analysis of its complexity is also presented.

In this paper, we suggest a distributed computing approach for finding multiple Pareto-optimal solutions. When the number of objective functions is large, the resulting Pareto-optimal front is of large dimension, thereby requiring a single processor multi-objective EA (MOEA) to use a large population size and run for a large number of generations. However, the task of finding a well-distributed set of solutions on the Pareto-optimal front can be distributed among a number of processors, each pre-destined to find a particular portion of the Pareto-optimal set. Based on the guided domination approach [1], here we propose a modified domination criterion for handling problems with a convex Pareto-optimal front. The proof-of-principle results obtained with a parallel version of NSGA-II shows the efficacy of the proposed approach.

The Capacitated Arc Routing Problem (CARP) is a very hard vehicle routing problem raised for instance by urban waste collection. In addition to the total route length (the only criterion minimized in the academic problem), waste management companies seek to minimize also the length of the longest trip. In this paper, a bi-objective genetic algorithm is presented for this more realistic CARP, never studied before in literature. Based on the NSGA-II template, it includes two-key features: use of good constructive heuristics to seed the initial population and hybridization with a powerful local search procedure. This genetic algorithm is appraised on 23 classical CARP instances, with excellent results. For instance, for a majority of instances, its efficient solutions include an optimal solution to the academic CARP (minimization of the total route length).

In this paper, Neighborhood Cultivation GA (NCGA) is applied to the rectangular packing problem. NCGA is one of the multi-objective Genetic Algorithms that includes not only the mechanisms of effective algorithms such as NSGA-II and SPEA2, but also the mechanism of the neighborhood crossover. This model can derive good nondominated solutions in typical multi-objective optimization test problems. The rectangular packing problem (RP) is a well-known discrete combinatorial optimization problem in many applications such as LSI layout problems, setting of plant facility problems, and so on. The RP is a difficult and time-consuming problem since the number of possible placements of rectangles increase exponentially as the number of rectangles increases. In this paper, the sequent-pair is used for representing the solution of the rectangular packing and PPEX is used as the crossover. The results were compared to the other methods: SPEA2, NSGA-II and non-NCGA (NCGA without neighborhood crossover). Through numerical examples, the effectiveness of NCGA for the RP is demonstrated and it is found that the neighborhood crossover is very effective both when the number of modules is small and large.

The aim of this paper is to show the influence of genetic operators such as crossover and mutation on the performance of a genetic algorithm (GA). The GA is applied to the multi-objective permutation flowshop problem. To achieve our goal an experimental study of a set of crossover and mutation operators is presented. A measure related to the dominance relations of different non-dominated sets, generated by different algorithms, is proposed so as to decide which algorithm is the best. The main conclusion is that there is a crossover operator having the best average performance on a very specific set of instances, and under a very specific criterion. Explaining the reason why a given operator is better than others remains an open problem.

Hybridization of evolutionary algorithms with local search (LS) has already been investigated in many studies. Such a hybrid algorithm is often referred to as a memetic algorithm. Hart investigated the following four questions for designing efficient memetic algorithms for single-objective optimization: (1) How often should LS be applied? (2) On which solutions should LS be used? (3) How long should LS be run? (4) How efficient does LS need to be? When we apply LS to an evolutionary multiobjective optimization (EMO) algorithm, another question arises: (5) To which direction should LS drive? This paper mainly addresses the final issue together with the others. We apply LS to the set of non-dominated solutions that is stored separately from the population governed by genetic operations in a cellular multiobjective genetic algorithm (C-MOGA). The appropriate direction for the non-dominated solutions is attained in experiments on multiobjective classification problems.

One advantage of evolutionary multiobjective optimization (EMO) algorithms over classical approaches is that many non-dominated solutions can be simultaneously obtained by their single run. This paper shows how this advantage can be utilized in genetic rule selection for the design of fuzzy rulebased classification systems. Our genetic rule selection is a two-stage approach. In the first stage, a pre-specified number of candidate rules are extracted from numerical data using a data mining technique. In the second stage, an EMO algorithm is used for finding non-dominated rule sets with respect to three objectives: to maximize the number of correctly classified training patterns, to minimize the number of rules, and to minimize the total rule length. Since the first objective is measured on training patterns, the evolution of rule sets tends to overfit to training patterns. The question is whether the other two objectives work as a safeguard against the overfitting. In this paper, we examine the effect of the three-objective formulation on the generalization ability (i.e., classification rates on test patterns) of obtained rule sets through computer simulations where many non-dominated rule sets are generated using an EMO algorithm for a number of high-dimensional pattern classification problems.

In the area of bioinformatics, the identification of gene subsets responsible for classifying available samples to two or more classes (for example, classes being ‘malignant’ or ‘benign’) is an important task. The main difficulties in solving the resulting optimization problem are the availability of only a few samples compared to the number of genes in the samples and the exorbitantly large search space of solutions. Although there exist a few applications of evolutionary algorithms (EAs) for this task, we treat the problem as a multi-objective optimization problem of minimizing the gene subset size and simultaneous minimizing the number of misclassified samples. Contrary to the past studies, we have discovered that a small gene subset size (such as four or five) is enough to correctly classify 100% or near 100% samples for three cancer samples (Leukemia, Lymphoma, and Colon). Besides a few variants of NSGA-II, in one implementation NSGA-II is modified to find multi-modal non-dominated solutions discovering as many as 630 different three-gene combinations providing a 100% correct classification to the Leukemia data. In order to perform the identification task with more confidence, we have also introduced a threshold in the prediction strength. All simulation results show consistent gene subset identifications on three disease samples and exhibit the flexibilities and efficacies in using a multi-objective EA for the gene identification task.

This paper deals with the application of multi-objective optimization to the diagnosis of Paroxysmal Atrial Fibrillation (PAF). The automatic diagnosis of patients that suffer PAF is done by analysing Electrocardiogram (ECG) traces with no explicit fibrillation episode. This task presents difficult problems to solve, and, although it has been addressed by several authors, none of them has obtained definitive results. A recent international initiative to study the viability of such an automatic diagnosis application has concluded that it can be achieved, with a reasonable efficiency. Furthermore, such an application is clinically important because it is based on a non-invasive examination and can be used to decide whether more specific and complex diagnosis testing is required. In this paper we have formulated the problem in order to be approached by a multi-objective optimisation algorithm, providing good results through this alternative.

We apply the NSGA-II algorithm and its controlled elitist version NSGA-IIc for the intensity modulated beam radiotherapy dose optimization problem. We compare the performance of the algorithms with objectives for which deterministic optimization methods provide global optimal solutions. The number of parameters to be optimized can be up to a few thousands and the number of objectives varies from 3 to 6. We compare the results with and without supporting solutions. Optimization with constraints for the target dose variance value provides clinical acceptable solutions.

Recognising the multiobjective nature of the decision process for rehabilitation of water supply distribution systems, this paper presents a comparative study of two multiobjective evolutionary methods, namely, multiobjective genetic algorithm (MOGA) and strength Pareto evolutionary algorithm (SPEA). The analyses were conducted on a simple hypothetical network for cost minimisation and minimum pressure requirement, treated as a two-objective problem. For the application example studied, SPEA outperforms MOGA in terms of the Pareto fronts produced and processing time required.

Determination of pipe diameters is the most important problem in design of water supply networks. Several authors have focused on the methods capable of sizing the network considering uncertainty and other important aspects. This study presents an application of multiobjective decision making techniques using evolutionary algorithms to generate a series of nondominated solutions. The three objective functions considered here include investment costs, entropy system and system demand supply ratio. The determination of Pareto frontier employed the public domain library MOMHLib++ and a hybrid hydraulic simulator based on the method of Nielsen. This technique is found to be quite promising, the nondominated region being identified in a reasonably small number of iterations.

The watershed water quality management problem considered in this study involves the identification of pollution control choices that help meet water quality targets while sustaining necessary growth. The primary challenge is to identify nondominated management choices that represent the noninferior tradeoff between the two competing management objectives, namely allowable urban growth and water quality. Given the complex simulation models and the decision space associated with this problem, a genetic algorithm-based multiobjective optimization (MO) approach is needed to solve and analyze it. This paper describes the application of the Nondominated Sorting Algorithm II (NSGA-II) to this realistic problem. The effects of different population sizes and sensitivity to random seed are explored. As the water quality simulation run times can become prohibitive, appropriate stopping criteria to minimize the number of fitness evaluations are being investigated. To compare with the NSGA-II results, the MO watershed management problem was also analyzed via an iterative application of a hybrid GA/local-search method that solved a series of single objective ε-constraint formilations of the multiobjective problem. In this approach, the GA solutions were used as the starting points for the Nelder-Mead local search algorithm. The results indicate that NSGA-II offers a promising approach to solving this complex, real-world MO watershed management problem.

Attacks against computer networks are becoming more sophisticated, with adversaries using new attacks or modifying existing attacks. This research uses three different types of multiobjective approaches, one lexicographic and two Pareto-based, in a multiobjective evolutionary programming algorithm to develop a new method for detecting such attacks. The approach evolves finite state transducers to detect attacks; this approach may allow the system to detect attacks with features similar to known attacks. Also, the approach examines the solution quality of each detector. Initial testing shows the algorithm performs satisfactorily in generating finite state transducers capable of detecting attacks.

In this work new safety systems multiobjective optimum design methodologies are introduced and compared. Various multicriteria evolutionary algorithms are analysed (SPEA2, NSGAII and controlled elitist-NSGAII) and applied to a Containment Spray Injection System of a nuclear power plant. Influence of various mutation rates is considered. A double minimization is handled: unavailability and cost of the system. The comparative statistical results of the test case show a convergence study during evolution by means of certain metrics that measure front coverage and distance to the optimal front. Results succeed in solving the problem.

This paper presents the usage of a multi-objective genetic algorithm to a set of engineering design problems. The studied problems span from detailed design of a hydraulic pump to more comprehensive system design. Furthermore, the problems are modeled using dynamic simulation models, response surfaces based on FE-models as well as static equations. The proposed method is simple and straight forward and it does not require any problem specific parameter tuning. The studied problems have all been successfully solved with the same algorithm without any problem specific parameter tuning. The resulting Pareto frontiers have proven very illustrative and supportive for the decision-maker.

In this paper, a real-world test problem is presented and made available for use by the EMO community. The problem deals with the optimization of polymer extrusion, in terms of setting the operating conditions and/or the screw geometry. The binary code of a computer program that predicts the thermomechanical experience of a polymer inside the machine, as a function of geometry, polymer properties and operating conditions, is developed. The program can be used through input and output data files, so that the parameters to optimize and the criteria evaluated data is communicated in both directions. Two distinct EMO algorithms are used to illustrate and test the optimization of this problem.

The method is developed for multi-objective optimization problems. Its purpose is to evolve an evenly distributed group of solutions to determine the optimum Pareto set for a given problem. The algorithm determines a set of solutions (a population), this population being sorted by its domination properties and a filter is defined in order to retain the Pareto solutions.In most topology design problem volume is in general a constraint of the problem. Due to this constraint, all chromosomes used in the genetic algorithm must generate individuals with the same volume value; in the coding adopted this means that they must preserve the same number of ones and, implicitly, the same number of zeros, along the evolutionary process. It is thus necessary to define these chromosomes and to create corresponding operators of crossover and mutation which preserve volume.To reduce computational effort, optimal solutions of each of the single-objective problems are introduced in the initial population.Results obtained by the evolutionary and classical methods are compared.

In this paper we will describe the optimisation of a two-criteria wing-design problem where calculation of the objective function requires the solution of the two-dimensional Navier-Stokes equations. It will be shown that basic concepts of the Strength Pareto Evolutionary Algorithm 2 (SPEA2) and the Non dominated Sorting Genetic Algorithm II (NSGA-II) work well with Evolution Strategies. Results for the wing design problem are presented for the selection operators of SPEA2 and NSGA-II in combination with three different mutation operators. These results are compared with results found by a multi-objective Genetic Algorithm.

Self-Organizing Maps (SOMs) have been used to visualize tradeoffs of Pareto solutions in the objective function space for engineering design obtained by Evolutionary Computation. Furthermore, based on the codebook vectors of cluster-averaged values of respective design variables obtained from the SOM, the design variable space is mapped onto another SOM. The resulting SOM generates clusters of design variables, which indicate roles of the design variables for design improvements and tradeoffs. These processes can be considered as data mining of the engineering design. Data mining examples are given for supersonic wing design and supersonic wing-fuselage design.