Robustness in multi-objective optimization using evolutionary algorithms

This work discusses robustness assessment during multi-objective optimization with a Multi-Objective Evolutionary Algorithm (MOEA) using a combination of two types of robustness measures. Expectation quantifies simultaneously fitness and robustness, while variance assesses the deviation of the original fitness in the neighborhood of the solution. Possible equations for each type are assessed via application to several benchmark problems and the selection of the most adequate is carried out. Diverse combinations of expectation and variance measures are then linked to a specific MOEA proposed by the authors, their selection being done on the basis of the results produced for various multi-objective benchmark problems. Finally, the combination preferred plus the same MOEA are used successfully to obtain the fittest and most robust Pareto optimal frontiers for a few more complex multi-criteria optimization problems.     

Portfolio optimization with an envelope-based multi-objective evolutionary algorithm

The problem of portfolio selection is a standard problem in financial engineering and has received a lot of attention in recent decades. Classical mean–variance portfolio selection aims at simultaneously maximizing the expected return of the portfolio and minimizing portfolio variance. In the case of linear constraints, the problem can be solved efficiently by parametric quadratic programming (i.e., variants of Markowitz’ critical line algorithm). However, there are many real-world constraints that lead to a non-convex search space, e.g., cardinality constraints which limit the number of different assets in a portfolio, or minimum buy-in thresholds. As a consequence, the efficient approaches for the convex problem can no longer be applied, and new solutions are needed.In this paper, we propose to integrate an active set algorithm optimized for portfolio selection into a multi-objective evolutionary algorithm (MOEA). The idea is to let the MOEA come up with some convex subsets of the set of all feasible portfolios, solve a critical line algorithm for each subset, and then merge the partial solutions to form the solution of the original non-convex problem. We show that the resulting envelope-based MOEA significantly outperforms existing MOEAs.     

Interactive evolutionary multi-objective optimization for quasi-concave preference functions

We present a new hybrid approach to interactive evolutionary multi-objective optimization that uses a partial preference order to act as the fitness function in a customized genetic algorithm. We periodically send solutions to the decision maker (DM) for her evaluation and use the resulting preference information to form preference cones consisting of inferior solutions. The cones allow us to implicitly rank solutions that the DM has not considered. This technique avoids assuming an exact form for the preference function, but does assume that the preference function is quasi-concave. This paper describes the genetic algorithm and demonstrates its performance on the multi-objective knapsack problem.     

Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem

Evolutionary algorithms are applied to problems that are not well understood as well as to problems in combinatorial optimization. The analysis of these search heuristics has been started for some well-known polynomial solvable problems. Such analyses are starting points for the analysis of evolutionary algorithms on difficult problems. We present the first runtime analysis of a multi-objective evolutionary algorithm on a NP-hard problem. The subject of our analysis is the multi-objective minimum spanning tree problem for which we give upper bounds on the expected time until a simple evolutionary algorithm has produced a population including for each extremal point of the Pareto front a corresponding spanning tree. These points are of particular interest as they give a 2-approximation of the Pareto front. We show that in expected pseudopolynomial time a population is produced that includes for each extremal point a corresponding spanning tree.     

An evolutionary artificial immune system for multi-objective optimization

In this paper, an evolutionary artificial immune system for multi-objective optimization which combines the global search ability of evolutionary algorithms and immune learning of artificial immune systems is proposed. A new selection strategy is developed based upon the concept of clonal selection principle to maintain the balance between exploration and exploitation. In order to maintain a diverse repertoire of antibodies, an information-theoretic based density preservation mechanism is also presented. In addition, the performances of various multi-objective evolutionary algorithms as well as the effectiveness of the proposed features are examined based upon seven benchmark problems characterized by different difficulties in local optimality, non-uniformity, discontinuity, non-convexity, high-dimensionality and constraints. The comparative study shows the effectiveness of the proposed algorithm, which produces solution sets that are highly competitive in terms of convergence, diversity and distribution. Investigations also demonstrate the contribution and robustness of the proposed features.     

A multi-objective optimal allocation model for irrigation water resources under multiple uncertainties

This paper proposed a multi-objective optimal water resources allocation model under multiple uncertainties. The proposed model integrated the chance-constrained programming, semi-infinite programming and integer programming into an interval linear programming. Then, the developed model is applied to irrigation water resources optimal allocation system in Minqin’s irrigation areas, Gansu Province, China. In this study, the irrigation areas’ economic benefits, social benefits and ecological benefits are regarded as the optimal objective functions. As a result, the optimal irrigation water resources allocation plans of different water types (surface water and groundwater) under different hydrological years (wet year, normal year and dry year) and probabilities are obtained. The proposed multi-objective model is unique by considering water-saving measures, irrigation water quality impact factors and the dynamic changes of groundwater exploitable quantity in the irrigation water resources optimal allocation system under uncertain environment. The obtained results are valuable for supporting the adjustment of the existing irrigation patterns and identify a desired water-allocation plan for irrigation under multiple uncertainties.     

Omni-optimizer: A generic evolutionary algorithm for single and multi-objective optimization

Due to the vagaries of optimization problems encountered in practice, users resort to different algorithms for solving different optimization problems. In this paper, we suggest and evaluate an optimization procedure which specializes in solving a wide variety of optimization problems. The proposed algorithm is designed as a generic multi-objective, multi-optima optimizer. Care has been taken while designing the algorithm such that it automatically degenerates to efficient algorithms for solving other simpler optimization problems, such as single-objective uni-optimal problems, single-objective multi-optima problems and multi-objective uni-optimal problems. The efficacy of the proposed algorithm in solving various problems is demonstrated on a number of test problems chosen from the literature. Because of its efficiency in handling different types of problems with equal ease, this algorithm should find increasing use in real-world optimization problems.     

Multi-objective simulation-based evolutionary algorithm for an aircraft spare parts allocation problem

Simulation optimization has received considerable attention from both simulation researchers and practitioners. In this study, we develop a solution framework which integrates multi-objective evolutionary algorithm (MOEA) with multi-objective computing budget allocation (MOCBA) method for the multi-objective simulation optimization problem. We apply it on a multi-objective aircraft spare parts allocation problem to find a set of non-dominated solutions. The problem has three features: huge search space, multi-objective, and high variability. To address these difficulties, the solution framework employs simulation to estimate the performance, MOEA to search for the more promising designs, and MOCBA algorithm to identify the non-dominated designs and efficiently allocate the simulation budget. Some computational experiments are carried out to test the effectiveness and performance of the proposed solution framework.     

A parallel multiple reference point approach for multi-objective optimization

This paper presents a multiple reference point approach for multi-objective optimization problems of discrete and combinatorial nature. When approximating the Pareto Frontier, multiple reference points can be used instead of traditional techniques. These multiple reference points can easily be implemented in a parallel algorithmic framework. The reference points can be uniformly distributed within a region that covers the Pareto Frontier. An evolutionary algorithm is based on an achievement scalarizing function that does not impose any restrictions with respect to the location of the reference points in the objective space. Computational experiments are performed on a bi-objective flow-shop scheduling problem. Results, quality measures as well as a statistical analysis are reported in the paper.     

Availability allocation and multi-objective optimization for parallel–series systems

Availability allocation is required when the manufacturer is obliged to allocate proper availability to various components in order to design an end product to meet specified requirements. This paper proposes a new multi-objective genetic algorithm, namely simulated annealing based multi-objective genetic algorithm (saMOGA), to resolve the availability allocation and optimization problems of a repairable system, specifically a parallel–series system. Compared with a general multi-objective genetic algorithm, the major feature of the saMOGA is that it can accept a poor solution with a small probability in order to enlarge the searching space and avoid the local optimum. The saMOGA aims to determine the optimal decision variables, i.e. failure rates, repair rates, and the number of components in each subsystem, according to multiple objectives, such as system availability, system cost and system net profit. The proposed saMOGA is compared with three other multi-objective genetic algorithms. Computational results showed that the proposed approach could provide higher solution quality and greater computing efficiency.     

An effective ant colony optimization algorithm (ACO) for multi-objective resource allocation problem (MORAP)

The multi-objective resource allocation problem (MORAP) addresses the important issue which seeks to find the expected objectives by allocating the limited amount of resource to various activates. Resources may be manpower, assets, raw material or anything else in limited supply which can be used to accomplish the goals. The goals may be objectives (i.e., minimizing costs, or maximizing efficiency) usually driven by specific future needs. In this paper, in order to obtain a set of Pareto solution efficiently, we proposed a modified version of ant colony optimization (ACO), in this algorithm we try to increase the efficiency of algorithm by increasing the learning of ants. Effectiveness and efficiency of proposed algorithm was validated by comparing the result of ACO with hybrid genetic algorithm (hGA) which was applied to MORAP later.     

A new multi-objective self-organizing optimization algorithm (MOSOA) for spatial optimization problems

Spatial planning is an important and complex activity. It includes land use planning and resource allocation as basic components. An abundance of papers can be found in the literature related to each one of these two aspects separately. On the contrary, a much smaller number of research reports deal with both aspects simultaneously. This paper presents an innovative evolutionary algorithm for treating combined land use planning and resource allocation problems. The new algorithm performs optimization on a cellular automaton domain, applying suitable transition rules on the individual neighbourhoods. The optimization process is multi-objective, based on non-domination criteria and self-organizing. It produces a Pareto front thus offering an advantage to the decision maker, in comparison to methods based on weighted-sum objective functions. Moreover, the present multi-objective self-organizing algorithm (MOSOA) can handle both local and global spatial constraints. A combined land use and water allocation problem is treated, in order to illustrate the cellular automaton optimization approach. Water is allocated after pumping from an aquifer, thus contributing a nonlinearity to the objective function. The problem is bi-objective aiming at (a) the minimization of soil and groundwater pollution and (b) the maximization of economic profit. An ecological and a socioeconomic constraint are imposed: (a) Groundwater levels at selected places are kept above prescribed thresholds. (b) Land use quota is predefined. MOSOA is compared to a standard multi-objective genetic algorithm and is shown to yield better results both with respect to the Pareto front and to the degree of compactness. The latter is a highly desirable feature of a land use pattern. In the land use literature, compactness is part of the objective function or of the constraints. In contrast, the present approach renders compactness as an emergent result.     

A hybrid method for solving multi-objective global optimization problems

Real optimization problems often involve not one, but multiple objectives, usually in conflict. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined but rather a set of optimums, which constitute the so called Pareto-optimal front. Thus, the goal of multi-objective strategies is to generate a set of non-dominated solutions as an approximation to this front. However, most problems of this kind cannot be solved exactly because they have very large and highly complex search spaces. The objective of this work is to compare the performance of a new hybrid method here proposed, with several well-known multi-objective evolutionary algorithms (MOEA). The main attraction of these methods is the integration of selection and diversity maintenance. Since it is very difficult to describe exactly what a good approximation is in terms of a number of criteria, the performance is quantified with adequate metrics that evaluate the proximity to the global Pareto-front. In addition, this work is also one of the few empirical studies that solves three-objective optimization problems using the concept of global Pareto-optimality.     

Hyper-spherical inversion transformations in multi-objective evolutionary optimization

Multi-objective evolutionary algorithms (MOEAs) are widely considered to have two goals: convergence towards the true Pareto front and maintaining a diverse set of solutions. The primary concern here is with the first goal of convergence, in particular when one or more variables must converge to a constant value. Using a number of well known test problems, the difficulties that are currently impeding convergence are discussed and then a new method is proposed that transforms the decision space using the geometric properties of hyper-spherical inversions to converge towards/onto the true Pareto front. Future extensions of this work and its application to multi-objective optimisation is discussed.     

Searching for multiobjective preventive maintenance schedules: Combining preferences with evolutionary algorithms

Heavy industry maintenance facilities at aircraft service centers or railroad yards must contend with scheduling preventive maintenance tasks to ensure critical equipment remains available. The workforce that performs these tasks are often high-paid, which means the task scheduling should minimize worker idle time. Idle time can always be minimized by reducing the workforce. However, all preventive maintenance tasks should be completed as quickly as possible to make equipment available. This means the completion time should be also minimized. Unfortunately, a small workforce cannot complete many maintenance tasks per hour. Hence, there is a tradeoff: should the workforce be small to reduce idle time or should it be large so more maintenance can be performed each hour? A cost effective schedule should strike some balance between a minimum schedule and a minimum size workforce.     

Balancing exploration and exploitation with adaptive variation for evolutionary multi-objective optimization

Although recent studies have shown that evolutionary algorithms are effective tools for solving multi-objective optimization problems, their performances are often bottlenecked by the suitability of the evolutionary operators with respect to the optimization problem at hand and their corresponding parametric settings. To adapt the search dynamic of evolutionary operation in multi-objective optimization, this paper proposes an adaptive variation operator that exploits the chromosomal structure of binary representation and synergizes the function of crossover and mutation. The overall search ability is deterministically tuned online to maintain a balance between extensive exploration and local fine-tuning at different stages of the evolutionary search. Also, the coordination between the two variation operators is achieved by means of an adaptive control that ensures an efficient exchange of information between the different chromosomal sub-structures throughout the evolutionary search. Extensive comparative studies with several representative variation operators are performed on different benchmark problems and significant algorithmic performance improvements in terms of proximity, uniformity and diversity are obtained with the incorporation of the proposed adaptive variation operator into the evolutionary multi-objective optimization process.     

Resource allocation in rooted trees for VLSI applications

ABSTRACT

Several optimization problems of modifying the weight of vertices in rooted trees, some of which are special cases of the inverse 1-median problem, are solved. Such problems arise in Very Large Scale Integration (VLSI) design of hardware security circuits, circuit synchronization, and analog-to-digital converters. These problems require assigning costly hardware (demands) to the leaves of rooted trees. One common property of these problems is that a resource allocated to an internal node can be shared by the entire sub-tree emanated at the node. Two types of problems are studied here. (1) A tree node employs an addition operation and the demands at the leaves are obtained by summing the resources allocated to nodes along the root-to-leaf paths. A linear-time bottom-up algorithm is shown to minimize the total resources allocated to tree nodes. (2) A tree’s node employs a multiplication operation and the demands at the leaves are obtained by multiplying the resources allocated to nodes along the root-to-leaf paths. A bottom-up dynamic programming algorithm is shown to minimize the total resources allocated to the tree’s nodes. While the above problems are usually solved by design engineers heuristically, this paper offers optimal solutions that can be easily programmed in CAD tools.     

On operators and search space topology in multi-objective flow shop scheduling

Multi-objective optimization using evolutionary algorithms identifies Pareto-optimal alternatives or their close approximation by means of a sequence of successive local improvement moves. While several successful applications to combinatorial optimization problems are known, studies of underlying problem structures are still scarce.     

Scope of stationary multi-objective evolutionary optimization: a case study on a hydro-thermal power dispatch problem

Many engineering design and developmental activities finally resort to an optimization task which must be solved to get an efficient and often an intelligent solution. Due to various complexities involved with objective functions, constraints, and decision variables, optimization problems are often not adequately suitable to be solved using classical point-by-point methodologies. Evolutionary optimization procedures use a population of solutions and stochastic update operators in an iteration in a manner so as to constitute a flexible search procedure thereby demonstrating promise to such difficult and practical problem-solving tasks. In this paper, we illustrate the power of evolutionary optimization algorithms in handling different kinds of optimization tasks on a hydro-thermal power dispatch optimization problem: (i) dealing with non-linear, non-differentiable objectives and constraints, (ii) dealing with more than one objectives and constraints, (iii) dealing with uncertainties in decision variables and other problem parameters, and (iv) dealing with a large number (more than 1,000) variables. The results on the static power dispatch optimization problem are compared with that reported in an existing simulated annealing based optimization procedure on a 24-variable version of the problem and new solutions are found to dominate the solutions of the existing study. Importantly, solutions found by our approach are found to satisfy theoretical Kuhn–Tucker optimality conditions by using the subdifferentials to handle non-differentiable objectives. This systematic and detail study demonstrates that evolutionary optimization procedures are not only flexible and scalable to large-scale optimization problems, but are also potentially efficient in finding theoretical optimal solutions for difficult real-world optimization problems. Kalyanmoy Deb, Deva Raj Chair Professor. Currently a Finland Distinguished Professor, Department of Business Technology, Helsinki School of Economics, 00101 Helsinki, Finland.     

A generalized DEA model for centralized resource allocation

In this paper, we introduced a new generalized centralized resource allocation model which extends Lozano and Villa’s and Asmild et al.’s models to a more general case. In order to uncover the sources of such total input contraction in the generalized centralized resource allocation model, we applied the structural efficiency to further decompose it into three components: the aggregate technical efficiency, the aggregate allocative efficiency and re-transferable efficiency components. The proposed models are not only flexible enough for the central decision-maker to adjust the inputs and outputs to achieve the total input contraction but also identify the sources of such total input contraction, thereby giving rise to an important interpretation and understanding of the generalized centralized resource allocation model. Finally, an empirical example is used to illustrate the approach.