The Pareto fitness genetic algorithm: Test function study

Evolutionary algorithms have shown some success in solving multiobjective optimization problems. The methods of fitness assignment are mainly based on the information about the dominance relation between individuals. We propose a Pareto fitness genetic algorithm (PFGA) in which we introduce a modified ranking procedure and a promising way of sharing; a new fitness function based on the rank of the individual and its density value is designed. This is considered as our main contribution. The performance of our algorithm is evaluated on six multiobjective benchmarks with different Pareto front features. Computational results (quality of the approximation of the Pareto optimal set and the number of fitness function evaluations) proving its efficiency are reported.     

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.     

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.     

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.     

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.     

A novel elitist multiobjective optimization algorithm: Multiobjective extremal optimization

Recently, a general-purpose local-search heuristic method called extremal optimization (EO) has been successfully applied to some NP-hard combinatorial optimization problems. This paper presents an investigation on EO with its application in numerical multiobjective optimization and proposes a new novel elitist (1 + λ) multiobjective algorithm, called multiobjective extremal optimization (MOEO). In order to extend EO to solve the multiobjective optimization problems, the Pareto dominance strategy is introduced to the fitness assignment of the proposed approach. We also present a new hybrid mutation operator that enhances the exploratory capabilities of our algorithm. The proposed approach is validated using five popular benchmark functions. The simulation results indicate that the proposed approach is highly competitive with the state-of-the-art multiobjective evolutionary algorithms. Thus MOEO can be considered a good alternative to solve numerical multiobjective optimization problems.     

Bicriteria train scheduling for high-speed passenger railroad planning applications

This paper is concerned with a double-track train scheduling problem for planning applications with multiple objectives. Focusing on a high-speed passenger rail line in an existing network, the problem is to minimize both (1) the expected waiting times for high-speed trains and (2) the total travel times of high-speed and medium-speed trains. By applying two practical priority rules, the problem with the second criterion is decomposed and formulated as a series of multi-mode resource constrained project scheduling problems in order to explicitly model acceleration and deceleration times. A branch-and-bound algorithm with effective dominance rules is developed to generate Pareto solutions for the bicriteria scheduling problem, and a beam search algorithm with utility evaluation rules is used to construct a representative set of non-dominated solutions. A case study based on Beijing–Shanghai high-speed railroad in China illustrates the methodology and compares the performance of the proposed algorithms.     

Duality and a Characterization of Pseudoinvexity for Pareto and Weak Pareto Solutions in Nondifferentiable Multiobjective Programming

In this paper, we unify recent optimality results under directional derivatives by the introduction of new pseudoinvex classes of functions, in relation to the study of Pareto and weak Pareto solutions for nondifferentiable multiobjective programming problems. We prove that in order for feasible solutions satisfying Fritz John conditions to be Pareto or weak Pareto solutions, it is necessary and sufficient that the nondifferentiable multiobjective problem functions belong to these classes of functions, which is illustrated by an example. We also study the dual problem and establish weak, strong, and converse duality results.     

UNIFORM APPROXIMATION OF A MULTIOBJECTIVE OPTIMIZATION SEQUENCE

In this paper the Pareto efficiency of a uniformly convergent multiobjective optimization sequence is studied. We obtain some relation between the Pareto efficient solutions of a given multiobjective optimization problem and those of its uniformly convergent optimization sequence and also some relation between the weak Pareto efficient solutions of the same optimization problem and those of its uniformly convergent optimization sequence. Besides, under a compact convex assumption for constraints set and a certain convex assumption for both objective and constraint functions, we also get some sufficient and necessary conditions that the limit of solutions of a uniformly convergent multiobjective optimization sequence is the solution of a given multiobjective optimization problem.     

Multi-start and path relinking methods to deal with multiobjective knapsack problems

This paper deals with a multiobjective combinatorial optimization problem called Extended Knapsack Problem. By applying multi-start search and path relinking we rapidly guide the search toward the most balanced zone of the Pareto-optimal front. The Pareto relation is applied in order to designate a subset of the best generated solutions to be the current efficient set of solutions. The max-min criterion with the Hamming distance is used as a measure of dissimilarity in order to find diverse solutions to be combined. The performance of our approach is compared with several state-of-the-art MOEAs for a suite test problems taken from the literature.     

Gradient projection and local region search for multiobjective optimisation

This paper presents a new method for multiobjective optimisation based on gradient projection and local region search. The gradient projection is conducted through the identification of normal vectors of an efficient frontier. The projection of the gradient of a nonlinear utility function onto the tangent plane of the efficient frontier at a given efficient solution leads to the definition of a feasible local region in a neighbourhood of the solution. Within this local region, a better efficient solution may be sought. To implement such a gradient-based local region search scheme, a new auxiliary problem is developed. If the utility function is given explicitly, this search scheme results in an iterative optimisation algorithm capable of general nonseparable multiobjective optimisation. Otherwise, an interactive decision making algorithm is developed where the decision maker (DM) is expected to provide local preference information in order to determine trade-off directions and step sizes. Optimality conditions for the algorithms are established and the convergence of the algorithms is proven. A multiobjective linear programming (MOLP) problem is taken for example to demonstrate this method both graphically and analytically. A nonlinear multiobjective water quality management problem is finally examined to show the potential application of the method to real world decision problems.     

Local dominance and local recombination in MOEAs on 0/1 multiobjective knapsack problems

This work studies and compares the effects on performance of local dominance and local recombination applied with different locality in multiobjective evolutionary algorithms on combinatorial 0/1 multiobjective knapsack problems. For this purpose, we introduce a method that creates a neighborhood around each individual and assigns a local dominance rank after alignment of the principle search direction of the neighborhood by using polar coordinates in objective space. For recombination a different neighborhood determined around a random principle search direction is created. The neighborhood sizes for dominance and recombination are separately controlled by two different parameters. Experimental results show that the optimum locality of dominance is different from the optimum locality of recombination. Additionally, it is shown that the performance of the algorithm that applies local dominance and local recombination with different locality is significantly better than the performance of algorithms applying local dominance alone, local recombination alone, or dominance and recombination globally as conventional approaches do.     

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.     

An Application of a Multi-Objective Tabu Search Algorithm to a Bicriteria Flowshop Problem

This paper proposes a new tabu search algorithm for multi-objective combinatorial problems with the goal of obtaining a good approximation of the Pareto-optimal or efficient solutions. The algorithm works with several paths of solutions in parallel, each with its own tabu list, and the Pareto dominance concept is used to select solutions from the neighborhoods. In this way we obtain at each step a set of local nondominated points. The dispersion of points is achieved by a clustering procedure that groups together close points of this set and then selects the centroids of the clusters as search directions. A nice feature of this multi-objective algorithm is that it introduces only one additional parameter, namely, the number of paths. The algorithm is applied to the permutation flowshop scheduling problem in order to minimize the criteria of makespan and maximum tardiness. For instances involving two machines, the performance of the algorithm is tested against a Branch-and-Bound algorithm proposed in the literature, and for more than two machines it is compared with that of a tabu search algorithm and a genetic local search algorithm, both from the literature. Computational results show that the heuristic yields a better approximation than these algorithms.     

A new multiobjective procedure for solving nonconvex environmental/economic power dispatch

In this article, an improved multiobjective chaotic interactive honey bee mating optimization (CIHBMO) is proposed to find the feasible optimal solution of the environmental/economic power dispatch problem with considering operational constraints of the generators. The three conflicting and noncommensurable: fuel cost, pollutant emissions, and system loss, should be minimized simultaneously while satisfying certain system constraints. To achieve a good design with different solutions in a multiobjective optimization problem, Pareto dominance concept is used to generate and sort the dominated and nondominated solutions. Also, fuzzy set theory is used to extract the best compromise solution. The propose method has been individually examined and applied to the standard Institute of Electrical and Electronics Engineers (IEEE) 30‐bus six generator, IEEE 180‐bus 14 generator and 40 generating unit (with valve point effect) test systems. The computational results reveal that the multiobjective CIHBMO algorithm has excellent convergence characteristics and is superior to other multiobjective optimization algorithms. Also, the result shows its great potential in handling the multiobjective problems in power systems. © 2014 Wiley Periodicals, Inc. Complexity 20: 47–62, 2014     

Reduced Jacobian Method

In this paper, we present the Wolfe’s reduced gradient method for multiobjective (multicriteria) optimization. We precisely deal with the problem of minimizing nonlinear objectives under linear constraints and propose a reduced Jacobian method, namely a reduced gradient-like method that does not scalarize those programs. As long as there are nondominated solutions, the principle is to determine a direction that decreases all goals at the same time to achieve one of them. Following the reduction strategy, only a reduced search direction is to be found. We show that this latter can be obtained by solving a simple differentiable and convex program at each iteration. Moreover, this method is conceived to recover both the discontinuous and continuous schemes of Wolfe for the single-objective programs. The resulting algorithm is proved to be (globally) convergent to a Pareto KKT-stationary (Pareto critical) point under classical hypotheses and a multiobjective Armijo line search condition. Finally, experiment results over test problems show a net performance of the proposed algorithm and its superiority against a classical scalarization approach, both in the quality of the approximated Pareto front and in the computational effort.     

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.     

Generalized viscosity approximation methods in multiobjective optimization problems

In this paper, we consider an extend-valued nonsmooth multiobjective optimization problem of finding weak Pareto optimal solutions. We propose a class of vector-valued generalized viscosity approximation method for solving the problem. Under some conditions, we prove that any sequence generated by this method converges to a weak Pareto optimal solution of the multiobjective optimization problem.     

Constraint Handling in Genetic Algorithms: The Set Partitioning Problem

In this paper we present a genetic algorithm-based heuristic for solving the set partitioning problem (SPP). The SPP is an important combinatorial optimisation problem used by many airlines as a mathematical model for flight crew scheduling.A key feature of the SPP is that it is a highly constrained problem, all constraints being equalities. New genetic algorithm (GA) components: separate fitness and unfitness scores, adaptive mutation, matching selection and ranking replacement, are introduced to enable a GA to effectively handle such constraints. These components are generalisable to any GA for constrained problems.We present a steady-state GA in conjunction with a specialised heuristic improvement operator for solving the SPP. The performance of our algorithm is evaluated on a large set of real-world problems. Computational results show that the genetic algorithm-based heuristic is capable of producing high-quality solutions.