Finding preferred subsets of Pareto optimal solutions

Multi-objective optimization algorithms can generate large sets of Pareto optimal (non-dominated) solutions. Identifying the best solutions across a very large number of Pareto optimal solutions can be a challenge. Therefore it is useful for the decision-maker to be able to obtain a small set of preferred Pareto optimal solutions. This paper analyzes a discrete optimization problem introduced to obtain optimal subsets of solutions from large sets of Pareto optimal solutions. This discrete optimization problem is proven to be NP-hard. Two exact algorithms and five heuristics are presented to address this problem. Five test problems are used to compare the performances of these algorithms and heuristics. The results suggest that preferred subset of Pareto optimal solutions can be efficiently obtained using the heuristics, while for smaller problems, exact algorithms can be applied.     

Two-phase Pareto local search for the biobjective traveling salesman problem

In this work, we present a method, called Two-Phase Pareto Local Search, to find a good approximation of the efficient set of the biobjective traveling salesman problem. In the first phase of the method, an initial population composed of a good approximation of the extreme supported efficient solutions is generated. We use as second phase a Pareto Local Search method applied to each solution of the initial population. We show that using the combination of these two techniques: good initial population generation plus Pareto Local Search gives better results than state-of-the-art algorithms. Two other points are introduced: the notion of ideal set and a simple way to produce near-efficient solutions of multiobjective problems, by using an efficient single-objective solver with a data perturbation technique.     

Hybrid adaptive methods for approximating a nonconvex multidimensional Pareto frontier

New hybrid methods for approximating the Pareto frontier of the feasible set of criteria vectors in nonlinear multicriteria optimization problems with nonconvex Pareto frontiers are considered. Since the approximation of the Pareto frontier is an ill-posed problem, the methods are based on approximating the Edgeworth-Pareto hull (EPH), i.e., the maximum set having the same Pareto frontier as the original feasible set of criteria vectors. The EPH approximation also makes it possible to visualize the Pareto frontier and to estimate the quality of the approximation. In the methods proposed, the statistical estimation of the quality of the current EPH approximation is combined with its improvement based on a combination of random search, local optimization, adaptive compression of the search region, and genetic algorithms.     

Convergence of stochastic search algorithms to finite size pareto set approximations

In this work we investigate the convergence of stochastic search algorithms toward the Pareto set of continuous multi-objective optimization problems. The focus is on obtaining a finite approximation that should capture the entire solution set in a suitable sense, which will be defined using the concept of ε-dominance. Under mild assumptions about the process to generate new candidate solutions, the limit approximation set will be determined entirely by the archiving strategy. We propose and analyse two different archiving strategies which lead to a different limit behavior of the algorithms, yielding bounds on the obtained approximation quality as well as on the cardinality of the resulting Pareto set approximation.      

A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems

This paper presents a new hybrid evolutionary algorithm to solve multi-objective multicast routing problems in telecommunication networks. The algorithm combines simulated annealing based strategies and a genetic local search, aiming at a more flexible and effective exploration and exploitation in the search space of the complex problem to find more non-dominated solutions in the Pareto Front. Due to the complex structure of the multicast tree, crossover and mutation operators have been specifically devised concerning the features and constraints in the problem. A new adaptive mutation probability based on simulated annealing is proposed in the hybrid algorithm to adaptively adjust the mutation rate according to the fitness of the new solution against the average quality of the current population during the evolution procedure. Two simulated annealing based search direction tuning strategies are applied to improve the efficiency and effectiveness of the hybrid evolutionary algorithm. Simulations have been carried out on some benchmark multi-objective multicast routing instances and a large amount of random networks with five real world objectives including cost, delay, link utilisations, average delay and delay variation in telecommunication networks. Experimental results demonstrate that both the simulated annealing based strategies and the genetic local search within the proposed multi-objective algorithm, compared with other multi-objective evolutionary algorithms, can efficiently identify high quality non-dominated solution set for multi-objective multicast routing problems and outperform other conventional multi-objective evolutionary algorithms in the literature.     

On the structure of multiobjective combinatorial search space: MNK-landscapes with correlated objectives

The structure of the search space explains the behavior of multiobjective search algorithms, and helps to design well-performing approaches. In this work, we analyze the properties of multiobjective combinatorial search spaces, and we pay a particular attention to the correlation between the objective functions. To do so, we extend the multiobjective NK-landscapes in order to take the objective correlation into account. We study the co-influence of the problem dimension, the degree of non-linearity, the number of objectives, and the objective correlation on the structure of the Pareto optimal set, in terms of cardinality and number of supported solutions, as well as on the number of Pareto local optima. This work concludes with guidelines for the design of multiobjective local search algorithms, based on the main fitness landscape features.     

Stochastic Optimization over a Pareto Set Associated with a Stochastic Multi-Objective Optimization Problem

We deal with the problem of minimizing the expectation of a real valued random function over the weakly Pareto or Pareto set associated with a Stochastic Multi-objective Optimization Problem, whose objectives are expectations of random functions. Assuming that the closed form of these expectations is difficult to obtain, we apply the Sample Average Approximation method in order to approach this problem. We prove that the Hausdorff–Pompeiu distance between the weakly Pareto sets associated with the Sample Average Approximation problem and the true weakly Pareto set converges to zero almost surely as the sample size goes to infinity, assuming that our Stochastic Multi-objective Optimization Problem is strictly convex. Then we show that every cluster point of any sequence of optimal solutions of the Sample Average Approximation problems is almost surely a true optimal solution. To handle also the non-convex case, we assume that the real objective to be minimized over the Pareto set depends on the expectations of the objectives of the Stochastic Optimization Problem, i.e. we optimize over the image space of the Stochastic Optimization Problem. Then, without any convexity hypothesis, we obtain the same type of results for the Pareto sets in the image spaces. Thus we show that the sequence of optimal values of the Sample Average Approximation problems converges almost surely to the true optimal value as the sample size goes to infinity.     

On parallel local search for permutations

We investigate some ways in which massively parallel computing devices can be exploited in local search algorithms. We show that the substantial speedups that can be gained from parallel neighbourhood evaluation enables an efficient best improvement local search, and that this in turn enables further speedups through selection and parallel application of a set of independent, improving moves. Our experiments demonstrate a total speedup of up to several hundred times compared to a classical, sequential best improvement search. We also demonstrate how an exchange of good partial solutions between the incumbent and best found solutions improves the efficiency of the Iterated Local Search algorithm.     

Distributed computation of Pareto solutions inn-player games

The problem of computing Pareto optimal solutions with distributed algorithms is considered inn-player games. We shall first formulate a new geometric problem for finding Pareto solutions. It involves solving joint tangents for the players' objective functions. This problem can then be solved with distributed iterative methods, and two such methods are presented. The principal results are related to the analysis of the geometric problem. We give conditions under which its solutions are Pareto optimal, characterize the solutions, and prove an existence theorem. There are two important reasons for the interest in distributed algorithms. First, they can carry computational advantages over centralized schemes. Second, they can be used in situations where the players do not know each others' objective functions.     

Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers

This paper extends the recently introduced Phased Local Search (PLS) maximum clique algorithm to unweighted/weighted maximum independent set and minimum vertex cover problems. PLS is a stochastic reactive dynamic local search algorithm that interleaves sub-algorithms which alternate between sequences of iterative improvement, during which suitable vertices are added to the current sub-graph, and plateau search, during which vertices of the current sub-graph are swapped with vertices not contained in the current sub-graph. These sub-algorithms differ in their vertex selection techniques and also in the perturbation mechanism used to overcome search stagnation. PLS has no problem instance dependent parameters and achieves state-of-the-art performance over a large range of the commonly used DIMACS and other benchmark instances.     

Pareto memetic algorithm with path relinking for bi-objective traveling salesperson problem

The paper presents an effective version of the Pareto memetic algorithm with path relinking and efficient local search for multiple objective traveling salesperson problem. In multiple objective Traveling salesperson problem (TSP), multiple costs are associated with each arc (link). The multiple costs may for example correspond to the financial cost of travel along a link, time of travel, or risk in the case of hazardous materials. The algorithm searches for new good solutions along paths in the decision space linking two other good solutions selected for recombination. Instead of a simple local search it uses short runs of tabu search based on the steepest version of the Lin–Kernighan algorithm. The efficiency of local search is further improved by the techniques of candidate moves and locked arcs. In the final step of the algorithm the neighborhood of each potentially Pareto-optimal solution is searched for new solutions that could be added to this set. The algorithm is compared experimentally to the state-of-the-art algorithms for multiple objective TSP.     

Pareto memetic algorithm for multiple objective optimization with an industrial application

Multiple objective combinatorial optimization problems are difficult to solve and often, exact algorithms are unable to produce optimal solutions. The development of multiple objective heuristics was inspired by the need to quickly produce acceptable solutions. In this paper, we present a new multiple objective Pareto memetic algorithm called PMS^MO. The PMS^MO algorithm incorporates an enhanced fine-grained fitness assignment, a double level archiving process and a local search procedure to improve performance. The performance of PMS^MO is benchmarked against state-of-the-art algorithms using 0–1 multi-dimensional multiple objective knapsack problem from the literature and an industrial scheduling problem from the aluminum industry.     

Two-Sided Pareto Front Approximations

A new approach to derive Pareto front approximations with evolutionary computations is proposed here. At present, evolutionary multiobjective optimization algorithms derive a discrete approximation of the Pareto front (the set of objective maps of efficient solutions) by selecting feasible solutions such that their objective maps are close to the Pareto front. However, accuracy of such approximations is known only if the Pareto front is known, which makes their usefulness questionable. Here we propose to exploit also elements outside feasible sets to derive pairs of such Pareto front approximations that for each approximation pair the corresponding Pareto front lies, in a certain sense, in-between. Accuracies of Pareto front approximations by such pairs can be measured and controlled with respect to distance between elements of a pair. A rudimentary algorithm to derive pairs of Pareto front approximations is presented and the viability of the idea is verified on a limited number of test problems.     

鲁棒优化中的Pareto有效性

对于一般的不确定优化问题, 研究了鲁棒解的~Pareto 有效性. 首先, 证明了Pareto 鲁棒解集即是鲁棒解集的Pareto 有效集, 因此求Pareto 鲁棒解等价于求鲁棒解集的Pareto 有效元. 其次, 基于推广的epsilon-约束方法, 得到了Pareto 鲁棒解的生成方法.     

Algorithms for Pareto optimal exchange with bounded exchange cycles

We consider exchange markets with single-unit endowments and demands where there is a bound on the size of the exchange cycles. The computational problem we study is that of computing a Pareto optimal and individually rational allocation. We present polynomial-time algorithms to compute a Pareto optimal and individually rational allocation when preferences are strict, the exchange bound is two, or when Pareto optimality is replaced with weak 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.     

Variable and large neighborhood search to solve the multiobjective set covering problem

In this paper, we study the multiobjective version of the set covering problem. To our knowledge, this problem has only been addressed in two papers before, and with two objectives and heuristic methods. We propose a new heuristic, based on the two-phase Pareto local search, with the aim of generating a good approximation of the Pareto efficient solutions. In the first phase of this method, the supported efficient solutions or a good approximation of these solutions is generated. Then, a neighborhood embedded in the Pareto local search is applied to generate non-supported efficient solutions. In order to get high quality results, two elaborate local search techniques are considered: a large neighborhood search and a variable neighborhood search. We intensively study the parameters of these two techniques. We compare our results with state-of-the-art results and we show that with our method, better results are obtained for different indicators.     

On dominance-based multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problems

This paper discusses simple local search approaches for approximating the efficient set of multiobjective combinatorial optimization problems. We focus on algorithms defined by a neighborhood structure and a dominance relation that iteratively improve an archive of nondominated solutions. Such methods are referred to as dominance-based multiobjective local search. We first provide a concise overview of existing algorithms, and we propose a model trying to unify them through a fine-grained decomposition. The main problem-independent search components of dominance relation, solution selection, neighborhood exploration and archiving are largely discussed. Then, a number of state-of-the-art and original strategies are experimented on solving a permutation flowshop scheduling problem and a traveling salesman problem, both on a two- and a three-objective formulation. Experimental results and a statistical comparison are reported in the paper, and some directions for future research are highlighted.     

A method for generating a well-distributed Pareto set in nonlinear multiobjective optimization

A method is presented for generating a well-distributed Pareto set in nonlinear multiobjective optimization. The approach shares conceptual similarity with the Physical Programming-based method, the Normal-Boundary Intersection and the Normal Constraint methods, in its systematic approach investigating the objective space in order to obtain a well-distributed Pareto set. The proposed approach is based on the generalization of the class functions which allows the orientation of the search domain to be conducted in the objective space. It is shown that the proposed modification allows the method to generate an even representation of the entire Pareto surface. The generation is performed for both convex and nonconvex Pareto frontiers. A simple algorithm has been proposed to remove local Pareto solutions. The suggested approach has been verified by several test cases, including the generation of both convex and concave Pareto frontiers.