Solving multiobjective,multiconstraint knapsack problems using mathematical programming and evolutionary algorithms

In this paper, we solve instances of the multiobjective multiconstraint (or multidimensional) knapsack problem (MOMCKP) from the literature, with three objective functions and three constraints. We use exact as well as approximate algorithms. The exact algorithm is a properly modified version of the multicriteria branch and bound (MCBB) algorithm, which is further customized by suitable heuristics. Three branching heuristics and a more general purpose composite branching and construction heuristic are devised. Comparison is made to the published results from another exact algorithm, the adaptive ε-constraint method [Laumanns, M., Thiele, L., Zitzler, E., 2006. An efficient, adaptive parameter variation scheme for Metaheuristics based on the epsilon-constraint method. European Journal of Operational Research 169, 932–942], using the same data sets. Furthermore, the same problems are solved using standard multiobjective evolutionary algorithms (MOEA), namely, the SPEA2 and the NSGAII. The results from the exact case show that the branching heuristics greatly improve the performance of the MCBB algorithm, which becomes faster than the adaptive ε -constraint. Regarding the performance of the MOEA algorithms in the specific problems, SPEA2 outperforms NSGAII in the degree of approximation of the Pareto front, as measured by the coverage metric (especially for the largest instance).     

A new multiobjective evolutionary algorithm

The Pareto-based approaches have shown some success in designing multiobjective evolutionary algorithms (MEAs). Their methods of fitness assignment are mainly from the information of dominated and nondominated individuals. On the top of the hierarchy of MEAs, the strength Pareto evolutionary algorithm (SPEA) has been elaborately designed with this principle in mind. In this paper, we propose a (μ+λ) multiobjective evolutionary algorithm ((μ+λ) MEA), which discards the dominated individuals in each generation. The comparisons of the experimental results demonstrate that the (μ+λ) MEA outperforms SPEA on five benchmark functions with less computational efforts.     

A multiobjective immune algorithm based on a multiple-affinity model

This paper presents a new multiobjective immune algorithm based on a multiple-affinity model inspired by immune system (MAM-MOIA). The multiple-affinity model builds the relationship model among main entities and concepts in multiobjective problems (MOPs) and multiobjective evolutionary algorithms (MOEAs), including feasible solution, variable space, objective space, Pareto-optimal set, ranking and crowding distance. In the model, immune operators including clonal proliferation, hypermutation and immune suppression are designed to proliferate superior antibodies and suppress the inferiors. MAM-MOIA is compared with NSGA-II, SPEA2 and NNIA in solving the ZDT and DTLZ standard test problems. The experimental study based on three performance metrics including coverage of two sets, convergence and spacing proves that MAM-MOIA is effective for solving MOPs.     

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.     

A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems

Most real-life decision-making activities require more than one objective to be considered. Therefore, several studies have been presented in the literature that use multiple objectives in decision models. In a mathematical programming context, the majority of these studies deal with two objective functions known as bicriteria optimization, while few of them consider more than two objective functions. In this study, a new algorithm is proposed to generate all nondominated solutions for multiobjective discrete optimization problems with any number of objective functions. In this algorithm, the search is managed over (p − 1)-dimensional rectangles where p represents the number of objectives in the problem and for each rectangle two-stage optimization problems are solved. The algorithm is motivated by the well-known ε-constraint scalarization and its contribution lies in the way rectangles are defined and tracked. The algorithm is compared with former studies on multiobjective knapsack and multiobjective assignment problem instances. The method is highly competitive in terms of solution time and the number of optimization models solved.     

Evaluation of the multiobjective ant colony algorithm performances on biobjective quadratic assignment problems

The difficulty of resolving the multiobjective combinatorial optimization problems with traditional methods has directed researchers to investigate new approaches which perform better. In recent years some algorithms based on ant colony optimization (ACO) metaheuristic have been suggested to solve these multiobjective problems. In this study these algorithms have been reported and programmed both to solve the biobjective quadratic assignment problem (BiQAP) instances and to evaluate the performances of these algorithms. The robust parameter sets for each 12 multiobjective ant colony optimization (MOACO) algorithms have been calculated and BiQAP instances in the literature have been solved within these parameter sets. The performances of the algorithms have been evaluated by comparing the Pareto fronts obtained from these algorithms. In the evaluation step, a multi significance test is used in a non hierarchical structure, and a performance metric (P metric) essential for this test is introduced. Through this study, decision makers will be able to put in the biobjective algorithms in an order according to the priority values calculated from the algorithms’ Pareto fronts. Moreover, this is the first time that MOACO algorithms have been compared by solving BiQAPs.     

Fast calculation of multiobjective probability of improvement and expected improvement criteria for Pareto optimization

The use of surrogate based optimization (SBO) is widely spread in engineering design to reduce the number of computational expensive simulations. However, “real-world” problems often consist of multiple, conflicting objectives leading to a set of competitive solutions (the Pareto front). The objectives are often aggregated into a single cost function to reduce the computational cost, though a better approach is to use multiobjective optimization methods to directly identify a set of Pareto-optimal solutions, which can be used by the designer to make more efficient design decisions (instead of weighting and aggregating the costs upfront). Most of the work in multiobjective optimization is focused on multiobjective evolutionary algorithms (MOEAs). While MOEAs are well-suited to handle large, intractable design spaces, they typically require thousands of expensive simulations, which is prohibitively expensive for the problems under study. Therefore, the use of surrogate models in multiobjective optimization, denoted as multiobjective surrogate-based optimization, may prove to be even more worthwhile than SBO methods to expedite the optimization of computational expensive systems. In this paper, the authors propose the efficient multiobjective optimization (EMO) algorithm which uses Kriging models and multiobjective versions of the probability of improvement and expected improvement criteria to identify the Pareto front with a minimal number of expensive simulations. The EMO algorithm is applied on multiple standard benchmark problems and compared against the well-known NSGA-II, SPEA2 and SMS-EMOA multiobjective optimization methods.     

Parallel multiobjective evolutionary algorithms for batch scheduling in heterogeneous computing and grid systems

This article presents six parallel multiobjective evolutionary algorithms applied to solve the scheduling problem in distributed heterogeneous computing and grid systems. The studied evolutionary algorithms follow an explicit multiobjective approach to tackle the simultaneous optimization of a system-related (i.e. makespan) and a user-related (i.e. flowtime) objectives. Parallel models of the proposed methods are developed in order to efficiently solve the problem. The experimental analysis demonstrates that the proposed evolutionary algorithms are able to efficiently compute accurate results when solving standard and new large problem instances. The best of the proposed methods outperforms both deterministic scheduling heuristics and single-objective evolutionary methods previously applied to the problem.     

Multicriteria scheduling optimization using an elitist multiobjective population heuristic: the h-NSDE algorithm

In today’s manufacturing industry more than one performance criteria are considered for optimization to various degrees simultaneously. To deal with such hard competitive environments it is essential to develop appropriate multicriteria scheduling approaches. In this paper consideration is given to the problem of scheduling n independent jobs on a single machine with due dates and objective to simultaneously minimize three performance criteria namely, total weighted tardiness (TWT), maximum tardiness and maximum earliness. In the single machine scheduling literature no previous studies have been performed on test problems examining these criteria simultaneously. After positioning the problem within the relevant research field, we present a new heuristic algorithm for its solution. The developed algorithm termed the hybrid non-dominated sorting differential evolution (h-NSDE) is an extension of the author’s previous algorithm for the single-machine mono-criterion TWT problem. h-NSDE is devoted to the search for Pareto-optimal solutions. To enable the decision maker for evaluating a greater number of alternative non-dominated solutions, three multiobjective optimization approaches have been implemented and tested within the context of h-NSDE: including a weighted-sum based approach, a fuzzy-measures based approach which takes into account the interaction among the criteria as well as a Pareto-based approach. Experiments conducted on existing data set benchmarks problems show the effect of these approaches on the performance of the h-NSDE algorithm. Moreover, comparative results between h-NSDE and some of the most popular multiobjective metaheuristics including SPEA2 and NSGA-II show clear superiority for h-NSDE in terms of both solution quality and solution diversity.     

Hybrid Population-Based Algorithms for the Bi-Objective Quadratic Assignment Problem

We present variants of an ant colony optimization (MO-ACO) algorithm and of an evolutionary algorithm (SPEA2) for tackling multi-objective combinatorial optimization problems, hybridized with an iterative improvement algorithm and the robust tabu search algorithm. The performance of the resulting hybrid stochastic local search (SLS) algorithms is experimentally investigated for the bi-objective quadratic assignment problem (bQAP) and compared against repeated applications of the underlying local search algorithms for several scalarizations. The experiments consider structured and unstructured bQAP instances with various degrees of correlation between the flow matrices. We do a systematic experimental analysis of the algorithms using outperformance relations and the attainment functions methodology to asses differences in the performance of the algorithms. The experimental results show the usefulness of the hybrid algorithms if the available computation time is not too limited and identify SPEA2 hybridized with very short tabu search runs as the most promising variant. This research was mainly done while Luís Paquete and Thomas Stützle were with the Intellectics Group at the Computer Science Department of Darmstadt University of Technology, Germany     

An empirical study on similarity-based mating for evolutionary multiobjective combinatorial optimization

We have already proposed a similarity-based mating scheme to recombine extreme and similar parents for evolutionary multiobjective optimization. In this paper, we examine the effect of the similarity-based mating scheme on the performance of evolutionary multiobjective optimization (EMO) algorithms. First we examine which is better between recombining similar or dissimilar parents. Next we examine the effect of biasing selection probabilities toward extreme solutions that are dissimilar from other solutions in each population. Then we examine the effect of dynamically changing the strength of this bias during the execution of EMO algorithms. Computational experiments are performed on a wide variety of test problems for multiobjective combinatorial optimization. Experimental results show that the performance of EMO algorithms can be improved by the similarity-based mating scheme for many test problems.     

On solving multiobjective bin packing problems using evolutionary particle swarm optimization

The bin packing problem is widely found in applications such as loading of tractor trailer trucks, cargo airplanes and ships, where a balanced load provides better fuel efficiency and safer ride. In these applications, there are often conflicting criteria to be satisfied, i.e., to minimize the bins used and to balance the load of each bin, subject to a number of practical constraints. Unlike existing studies that only consider the issue of minimum bins, a multiobjective two-dimensional mathematical model for bin packing problems with multiple constraints (MOBPP-2D) is formulated in this paper. To solve MOBPP-2D problems, a multiobjective evolutionary particle swarm optimization algorithm (MOEPSO) is proposed. Without the need of combining both objectives into a composite scalar weighting function, MOEPSO incorporates the concept of Pareto’s optimality to evolve a family of solutions along the trade-off surface. Extensive numerical investigations are performed on various test instances, and their performances are compared both quantitatively and statistically with other optimization methods to illustrate the effectiveness and efficiency of MOEPSO in solving multiobjective bin packing problems.     

Computing the nadir point for multiobjective discrete optimization problems

We investigate the problem of finding the nadir point for multiobjective discrete optimization problems (MODO). The nadir point is constructed from the worst objective values over the efficient set of a multiobjective optimization problem. We present a new algorithm to compute nadir values for MODO with \(p\) objective functions. The proposed algorithm is based on an exhaustive search of the \((p-2)\)-dimensional space for each component of the nadir point. We compare our algorithm with two earlier studies from the literature. We give numerical results for all algorithms on multiobjective knapsack, assignment and integer linear programming problems. Our algorithm is able to obtain the nadir point for relatively large problem instances with up to five-objectives.     

On the exactness of the ε-constraint method for biobjective nonlinear integer programming

The ε-constraint method is a well-known scalarization technique used for multiobjective optimization. We explore how to properly define the step size parameter of the method in order to guarantee its exactness when dealing with biobjective nonlinear integer problems. Under specific assumptions, we prove that the number of subproblems that the method needs to address to detect the complete Pareto front is finite. We report numerical results on portfolio optimization instances built on real-world data and show a comparison with an existing criterion space algorithm.     

Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation

This paper considers the routing of vehicles with limited capacity from a central depot to a set of geographically dispersed customers where actual demand is revealed only when the vehicle arrives at the customer. The solution to this vehicle routing problem with stochastic demand (VRPSD) involves the optimization of complete routing schedules with minimum travel distance, driver remuneration, and number of vehicles, subject to a number of constraints such as time windows and vehicle capacity. To solve such a multiobjective and multi-modal combinatorial optimization problem, this paper presents a multiobjective evolutionary algorithm that incorporates two VRPSD-specific heuristics for local exploitation and a route simulation method to evaluate the fitness of solutions. A new way of assessing the quality of solutions to the VRPSD on top of comparing their expected costs is also proposed. It is shown that the algorithm is capable of finding useful tradeoff solutions for the VRPSD and the solutions are robust to the stochastic nature of the problem. The developed algorithm is further validated on a few VRPSD instances adapted from Solomon’s vehicle routing problem with time windows (VRPTW) benchmark problems.     

A novel evolution strategy for multiobjective optimization problem

Recent literatures have suggested that multiobjective evolutionary algorithms (MOEAs) can serve as a more exploratory and effective tool in solving multiobjective optimization problems (MOPs) than traditional optimizers. In order to contain a good approximation of Pareto optimal set with wide diversity associated with the inherent characters and variability of MOPs, this paper proposes a new evolutionary approach—(μ, λ) multiobjective evolution strategy ((μ, λ)-MOES). Following the highlight of how to balance proximity and diversity of individuals in exploration and exploitation stages respectively, some cooperative techniques are devised. Firstly, a novel combinatorial exploration operator that develops strong points from Gaussian mutation of proximity exploration and from Cauchy mutation of diversity preservation is elaborately designed. Additionally, we employ a complete nondominance selection so as to ensure maximal pressure for proximity exploitation while a fitness assignment determined by dominance and population diversity information is simultaneous used to ensure maximal diversity preservation. Moreover, a dynamic external archive is introduced to store elitist individuals as well as relatively better individuals and exchange information with the current population when performing archive increase scheme and archive decrease scheme. By graphical presentation and examination of selected performance metrics on three prominent benchmark test functions, (μ, λ)-MOES is found to outperform SPEA-II to some extent in terms of finding a near-optimal, well-extended and uniformly diversified Pareto optimal front.     

Bucket elimination for multiobjective optimization problems

Multiobjective optimization deals with problems involving multiple measures of performance that should be optimized simultaneously. In this paper we extend bucket elimination (BE), a well known dynamic programming generic algorithm, from mono-objective to multiobjective optimization. We show that the resulting algorithm, MO-BE, can be applied to true multi-objective problems as well as mono-objective problems with knapsack (or related) global constraints. We also extend mini-bucket elimination (MBE), the approximation form of BE, to multiobjective optimization. The new algorithm MO-MBE can be used to obtain good quality multi-objective lower bounds or it can be integrated into multi-objective branch and bound in order to increase its pruning efficiency. Its accuracy is empirically evaluated in real scheduling problems, as well as in Max-SAT-ONE and biobjective weighted minimum vertex cover problems.     

Decision making in multiobjective optimization aided by the multicriteria tournament decision method

This paper proposes a new method for multicriteria analysis, named Multicriteria Tournament Decision (MTD). It provides the ranking of alternatives from best to worst, according to the preferences of a human decision-maker (DM). It has some positive aspects such as: it has a simple algorithm with intuitive appeal; it involves few input parameters (just the importance weight of each criterion).The helpfulness of MTD is demonstrated by using it to select the final solution of multiobjective optimization problems in an a posteriori decision making approach. Having at hand a discrete approximation of the Pareto front (provided by a multiobjective evolutionary search algorithm), the choice of the preferred Pareto-optimal solution is performed using MTD.A simple method, named Gain Analysis method (GAM), for verifying the existence of a better solution (a solution associated to higher marginal rates of return) than the one originally chosen by the DM, is also introduced here. The usefulness of MTD and GAM methods is confirmed by the suitable results shown in this paper.     

Multi-criteria TSP: Min and max combined

We present randomized approximation algorithms for multi-criteria traveling salesman problems (TSP), where some objective functions should be minimized while others should be maximized. For the symmetric multi-criteria TSP (STSP), we present an algorithm that computes (2/3,3+ε)-approximate Pareto curves. Here, the first parameter is the approximation ratio for the objectives that should be maximized, and the second parameter is the ratio for the objectives that should be minimized. For the asymmetric multi-criteria TSP (ATSP), we obtain an approximation performance of (1/2,log₂n+ε).