A Hybrid Meta-Heuristic for Multi-Objective Optimization: MOSATS

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 solutions, called the 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, the majority of problems of this kind cannot be solved exactly because they have very large and highly complex search spaces. In recent years, meta-heuristics have become important tools for solving multi-objective problems encountered in industry as well as in the theoretical field. This paper presents a novel approach based on hybridizing Simulated Annealing and Tabu Search. Experiments on the Graph Partitioning Problem show that this new method is a better tool for approximating the efficient set than other strategies also based on these meta-heuristics.     

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.     

Solving multi-objective multicast routing problems by evolutionary multi-objective simulated annealing algorithms with variable neighbourhoods

This paper presents the investigation of an evolutionary multi-objective simulated annealing (EMOSA) algorithm with variable neighbourhoods to solve the multi-objective multicast routing problems in telecommunications. The hybrid algorithm aims to carry out a more flexible and adaptive exploration in the complex search space by using features of the variable neighbourhood search to find more non-dominated solutions in the Pareto front. Different neighbourhood strictures have been designed with regard to the set of objectives, aiming to drive the search towards optimising all objectives simultaneously. A large number of simulations have been carried out on benchmark instances and random networks with real world features including cost, delay and link utilisations. Experimental results demonstrate that the proposed EMOSA algorithm with variable neighbourhoods is able to find high-quality non-dominated solutions for the problems tested. In particular, the neighbourhood structures that are specifically designed for each objective significantly improved the performance of the proposed algorithm compared with variants of the algorithm with a single neighbourhood.     

Pruned Pareto-optimal sets for the system redundancy allocation problem based on multiple prioritized objectives

In this paper, a new methodology is presented to solve different versions of multi-objective system redundancy allocation problems with prioritized objectives. Multi-objective problems are often solved by modifying them into equivalent single objective problems using pre-defined weights or utility functions. Then, a multi-objective problem is solved similar to a single objective problem returning a single solution. These methods can be problematic because assigning appropriate numerical values (i.e., weights) to an objective function can be challenging for many practitioners. On the other hand, methods such as genetic algorithms and tabu search often yield numerous non-dominated Pareto optimal solutions, which makes the selection of one single best solution very difficult. In this research, a tabu search meta-heuristic approach is used to initially find the entire Pareto-optimal front, and then, Monte-Carlo simulation provides a decision maker with a pruned and prioritized set of Pareto-optimal solutions based on user-defined objective function preferences. The purpose of this study is to create a bridge between Pareto optimality and single solution approaches.     

Stochastic Pareto local search: Pareto neighbourhood exploration and perturbation strategies

Pareto local search (PLS) methods are local search algorithms for multi-objective combinatorial optimization problems based on the Pareto dominance criterion. PLS explores the Pareto neighbourhood of a set of non-dominated solutions until it reaches a local optimal Pareto front. In this paper, we discuss and analyse three different Pareto neighbourhood exploration strategies: best, first, and neutral improvement. Furthermore, we introduce a deactivation mechanism that restarts PLS from an archive of solutions rather than from a single solution in order to avoid the exploration of already explored regions. To escape from a local optimal solution set we apply stochastic perturbation strategies, leading to stochastic Pareto local search algorithms (SPLS). We consider two perturbation strategies: mutation and path-guided mutation. While the former is unbiased, the latter is biased towards preserving common substructures between 2 solutions. We apply SPLS on a set of large, correlated bi-objective quadratic assignment problems (bQAPs) and observe that SPLS significantly outperforms multi-start PLS. We investigate the reason of this performance gain by studying the fitness landscape structure of the bQAPs using random walks. The best performing method uses the stochastic perturbation algorithms, the first improvement Pareto neigborhood exploration and the deactivation technique.     

Non-dominated sorting procedure for Pareto dominance ranking on multicore CPU and/or GPU

Evolutionary multi-objective optimization algorithms aim at finding an approximation of the Pareto set. For hard to solve problems with many conflicting objectives, the number of functions evaluations to represent the Pareto front can be large and time consuming. Parallel computing can reduce the wall-clock time of such algorithms. Previous studies tackled the parallelization of a particular evolutionary algorithm. In this research, we focus on improving one of the most time consuming procedures—the non-dominated sorting—, which is used in the state-of-the-art multi-objective genetic algorithms. Here, three parallel versions of the non-dominated sorting procedure are developed: (1) a multicore (based on Pthreads); (2) a Graphic Processing Unit (GPU) (based on CUDA interface); and (3) a hybrid (based on Pthreads and CUDA). The user can select the most suitable option to efficiently compute the non-dominated sorting procedure depending on the available hardware. Results show that the use of GPU computing provides a substantial improvement in terms of performance. The hybrid approach has the best performance when a good load balance is established among cores and GPU.     

Transfer weight functions for injecting problem information in the multi-objective CMA-ES

The covariance matrix adaptation evolution strategy (CMA-ES) is one of the state-of-the-art evolutionary algorithms for optimization problems with continuous representation. It has been extensively applied to single-objective optimization problems, and different variants of CMA-ES have also been proposed for multi-objective optimization problems (MOPs). When applied to MOPs, the traditional steps of CMA-ES have to be modified to accommodate for multiple objectives. This fact is particularly evident when the number of objectives is higher than 3 and, with a high probability, all the solutions produced become non-dominated. An open question is to what extent information about the objective values of the non-dominated solutions can be injected in the CMA-ES model for a more effective search. In this paper, we investigate this general question using several metrics that describe the quality of the solutions already evaluated, different transfer weight functions, and a set of difficult benchmark instances including many-objective problems. We introduce a number of new strategies that modify how the probabilistic model is learned in CMA-ES. By conducting an exhaustive empirical analysis on two difficult benchmarks of many-objective functions we show that the proposed strategies to infuse information about the quality indicators into the learned models can achieve consistent improvements in the quality of the Pareto fronts obtained and enhance the convergence rate of the algorithm. Moreover, we conducted a comparison with a state-of-the-art algorithm from the literature, and achieved competitive results in problems with irregular Pareto fronts.     

Multi-Objective Biclustering: When Non-dominated Solutions are not Enough

The biclustering technique was developed to avoid some of the drawbacks presented by standard clustering techniques, such as their impossibility of finding correlating data under a subset of features, and, consequently, to allow the extraction of more accurate information from datasets. Given that biclustering requires the optimization of at least two conflicting objectives (residue and volume) and that multiple independent solutions are desirable as the outcome, a few multi-objective evolutionary algorithms for biclustering were proposed in the literature. However, these algorithms only focus their search in the generation of a global set of non-dominated biclusters, which may be insufficient for most of the problems as the coverage of the dataset can be compromised. In order to overcome such problem, a multi-objective artificial immune system capable of performing a multipopulation search, named MOM-aiNet, was proposed. In this work, the MOM-aiNet algorithm will be described in detail, and an extensive set of experimental comparisons will be performed, with the obtained results of MOM-aiNet being confronted with those produced by the popular CC algorithm, by another immune-inspired approach for biclustering (BIC-aiNet), and by the multi-objective approach for biclustering proposed by Mitra & Banka.     

Hybrid multi-objective Bayesian estimation of distribution algorithm: a comparative analysis for the multi-objective knapsack problem

Nowadays, a number of metaheuristics have been developed for efficiently solving multi-objective optimization problems. Estimation of distribution algorithms are a special class of metaheuristic that intensively apply probabilistic modeling and, as well as local search methods, are widely used to make the search more efficient. In this paper, we apply a Hybrid Multi-objective Bayesian Estimation of Distribution Algorithm (HMOBEDA) in multi and many objective scenarios by modeling the joint probability of decision variables, objectives, and the configuration parameters of an embedded local search (LS). We analyze the benefits of the online configuration of LS parameters by comparing the proposed approach with LS off-line versions using instances of the multi-objective knapsack problem with two to five and eight objectives. HMOBEDA is also compared with five advanced evolutionary methods using the same instances. Results show that HMOBEDA outperforms the other approaches including those with off-line configuration. HMOBEDA not only provides the best value for hypervolume indicator and IGD metric in most of the cases, but it also computes a very diverse solutions set close to the estimated Pareto front.     

Evolutionary Pareto optimizers for continuous review stochastic inventory systems

Multi-objective inventory control has been studied for a long time. The trade-off analysis of cycle stock investment and workload, so called the exchange curve concept, possibly dates back to several decades ago. A classical way to such trade-off analysis is to utilize the Lagrangian relaxation technique or interactive method to search for the optimum in a sequence of single objective optimization problems. However, the field of optimization has been changed over the last few decades since the concept of evolutionary computation was introduced. In this paper, a continuous review stochastic inventory system with three objectives about cost and shortage is resolved by evolutionary computation in order to plan for the control policies under backordering and lost sales. Two evolutionary optimizers, multi-objective electromagnetism-like optimization (MOEMO) and multi-objective particle swarm optimization (MOPSO), are employed to well and fast approximate the non-dominated policies in term of lot size and safety stock. Trade-offs are observed in a non-dominated set that no one excels the others in all objectives. Computational results show that the evolutionary Pareto optimizers could generate trade-off solutions potentially ignored by the well-known simultaneous method. Comparisons between the results of backordering and lost sales indicate that decision makers will make more deliberate choices about lot sizing and safety stocking when unsatisfied demand is completely lost.     

New simulation-based frameworks for multi-objective reliability-based design optimization of structures

In the present study, two new simulation-based frameworks are proposed for multi-objective reliability-based design optimization (MORBDO). The first is based on hybrid non-dominated sorting weighted simulation method (NSWSM) in conjunction with iterative local searches that is efficient for continuous MORBDO problems. According to NSWSM, uniform samples are generated within the design space and, then, the set of feasible samples are separated. Thereafter, the non-dominated sorting operator is employed to extract the approximated Pareto front. The iterative local sample generation is then performed in order to enhance the accuracy, diversity, and increase the extent of non-dominated solutions. In the second framework, a pseudo-double loop algorithm is presented based on hybrid weighted simulation method (WSM) and the Non-dominated Sorting Genetic Algorithm II (NSGA-II) that is efficient for problems including both discrete and continuous variables. According to hybrid WSM-NSGA-II, proper non-dominated solutions are produced in each generation of NSGA-II and, subsequently, WSM evaluates the reliability level of each candidate solution until the algorithm converges to the true Pareto solutions. The valuable characteristic of presented approaches is that only one simulation run is required for WSM during entire optimization process, even if solutions for different levels of reliability be desired. Illustrative examples indicate that NSWSM with the proposed local search strategy is more efficient for small dimension continuous problems. However, WSM-NSGA-II outperforms NSWSM in terms of solutions quality and computational efficiency, specifically for discrete MORBDOs. Employing global optimizer in WSM-NSGA-II provided more accurate results with lower samples than NSWSM.     

Focused ultrasonic therapy planning: Metamodeling,optimization, visualization

We present a generic approach for focused ultrasonic therapy planning on the basis of numerical simulation, multi-objective optimization, stochastic analysis and visualization in virtual environments. A realistic test case is used to demonstrate the approach. RBF metamodeling of simulation results is performed for continuous representation of two optimization objectives. The non-convex Pareto front of the objectives is determined by means of non-dominated set and local improvement algorithms. Uncertainties of metamodeling are estimated by means of a cross-validation procedure. The 3D visualization in virtual environment framework Avango allows detailed inspection of MRT images, the corresponding material model and spatial distribution of the resulting thermal dose.     

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.     

ParEGO extensions for multi-objective optimization of expensive evaluation functions

This paper deals with multi-objective optimization in the case of expensive objective functions. Such a problem arises frequently in engineering applications where the main purpose is to find a set of optimal solutions in a limited global processing time. Several algorithms use linearly combined criteria to use directly mono-objective algorithms. Nevertheless, other algorithms, such as multi-objective evolutionary algorithm (MOEA) and model-based algorithms, propose a strategy based on Pareto dominance to optimize efficiently all criteria. A widely used model-based algorithm for multi-objective optimization is Pareto efficient global optimization (ParEGO). It combines linearly the objective functions with several random weights and maximizes the expected improvement (EI) criterion. However, this algorithm tends to favor parameter values suitable for the reduction of the surrogate model error, rather than finding non-dominated solutions. The contribution of this article is to propose an extension of the ParEGO algorithm for finding the Pareto Front by introducing a double Kriging strategy. Such an innovation allows to calculate a modified EI criterion that jointly accounts for the objective function approximation error and the probability to find Pareto Set solutions. The main feature of the resulting algorithm is to enhance the convergence speed and thus to reduce the total number of function evaluations. This new algorithm is compared against ParEGO and several MOEA algorithms on a standard benchmark problems. Finally, an automotive engineering problem allowing to illustrate the applicability of the proposed approach is given as an example of a real application: the parameter setting of an indirect tire pressure monitoring system.     

Tabu search for a multi-objective routing problem

Multi-objective optimization problems deal with the presence of different conflicting objectives. Given that it is not possible to obtain a single solution by optimizing all the objectives simultaneously, a common way to face these problems is to obtain a set of efficient solutions called the non-dominated frontier. In this paper, we address the problem of routing school buses with two objectives: minimize the number of buses, and minimize the longest time a student would have to stay in the bus. The trade-off in this problem is between service level, which is represented by the maximum route length, and operational cost, which is represented by the number of buses in the solution. We present different constructive solution methods and a tabu search procedure to obtain non-dominated solutions. The procedure is coupled with an intensification phase based on the path relinking methodology: a strategy proposed several years ago, which has been rarely used in actual implementations. Computational experiments with real data, in the context of routing school buses in a rural area, establish the effectiveness of our procedure in relation to the approach previously identified to be the best.     

A New Hybrid Evolutionary Multiobjective Algorithm Guided by Descent Directions

Hybridization of local search based algorithms with evolutionary algorithms is still an under-explored research area in multiobjective optimization. In this paper, we propose a new multiobjective algorithm based on a local search method. The main idea is to generate new non-dominated solutions by adding a linear combination of descent directions of the objective functions to a parent solution. Additionally, a strategy based on subpopulations is implemented to avoid the direct computation of descent directions for the entire population. The evaluation of the proposed algorithm is performed on a set of benchmark test problems allowing a comparison with the most representative state-of-the-art multiobjective algorithms. The results show that the proposed approach is highly competitive in terms of the quality of non-dominated solutions and robustness.     

Primal and dual algorithms for optimization over the efficient set

ABSTRACT

Optimization over the efficient set of a multi-objective optimization problem is a mathematical model for the problem of selecting a most preferred solution that arises in multiple criteria decision-making to account for trade-offs between objectives within the set of efficient solutions. In this paper, we consider a particular case of this problem, namely that of optimizing a linear function over the image of the efficient set in objective space of a convex multi-objective optimization problem. We present both primal and dual algorithms for this task. The algorithms are based on recent algorithms for solving convex multi-objective optimization problems in objective space with suitable modifications to exploit specific properties of the problem of optimization over the efficient set. We first present the algorithms for the case that the underlying problem is a multi-objective linear programme. We then extend them to be able to solve problems with an underlying convex multi-objective optimization problem. We compare the new algorithms with several state of the art algorithms from the literature on a set of randomly generated instances to demonstrate that they are considerably faster than the competitors.     

An efficient multi-objective PSO algorithm assisted by Kriging metamodel for expensive black-box problems

The huge computational overhead is the main challenge in the application of community based optimization methods, such as multi-objective particle swarm optimization and multi-objective genetic algorithm, to deal with the multi-objective optimization involving costly simulations. This paper proposes a Kriging metamodel assisted multi-objective particle swarm optimization method to solve this kind of expensively black-box multi-objective optimization problems. On the basis of crowding distance based multi-objective particle swarm optimization algorithm, the new proposed method constructs Kriging metamodel for each expensive objective function adaptively, and then the non-dominated solutions of the metamodels are utilized to guide the update of particle population. To reduce the computational cost, the generalized expected improvements of each particle predicted by metamodels are presented to determine which particles need to perform actual function evaluations. The suggested method is tested on 12 benchmark functions and compared with the original crowding distance based multi-objective particle swarm optimization algorithm and non-dominated sorting genetic algorithm-II algorithm. The test results show that the application of Kriging metamodel improves the search ability and reduces the number of evaluations. Additionally, the new proposed method is applied to the optimal design of a cycloid gear pump and achieves desirable results.     

K-PPM: A new exact method to solve multi-objective combinatorial optimization problems

In this paper we propose an exact method able to solve multi-objective combinatorial optimization problems. This method is an extension, for any number of objectives, of the 2-Parallel Partitioning Method (2-PPM) we previously proposed. Like 2-PPM, this method is based on splitting of the search space into several areas, leading to elementary searches. The efficiency of the proposed method is evaluated using a multi-objective flow-shop problem.     

An interactive evolutionary multi-objective optimization algorithm with a limited number of decision maker calls

This paper presents a preference-based method to handle optimization problems with multiple objectives. With an increase in the number of objectives the computational cost in solving a multi-objective optimization problem rises exponentially, and it becomes increasingly difficult for evolutionary multi-objective techniques to produce the entire Pareto-optimal front. In this paper, an evolutionary multi-objective procedure is combined with preference information from the decision maker during the intermediate stages of the algorithm leading to the most preferred point. The proposed approach is different from the existing approaches, as it tries to find the most preferred point with a limited budget of decision maker calls. In this paper, we incorporate the idea into a progressively interactive technique based on polyhedral cones. The idea is also tested on another progressively interactive approach based on value functions. Results are provided on two to five-objective unconstrained as well as constrained test problems.