Goal programming using multiple objective hybrid metaheuristic algorithm

In this paper, a Goal Programming (GP) model is converted into a multi-objective optimization problem (MOO) of minimizing deviations from fixed goals. To solve the resulting MOO problem, a hybrid metaheuristic with two steps is proposed to find the Pareto set's solutions. First, a Record-to-Record Travel with an adaptive memory is used to find first non-dominated Pareto frontier solutions preemptively. Second, a Variable Neighbour Search technique with three transformation types is used to intensify every non dominated solution found in the first Pareto frontier to produce the final Pareto frontier solutions. The efficiency of the proposed approach is demonstrated by solving two nonlinear GP test problems and three engineering design problems. In all problems, multiple solutions to the GP problem are found in one single simulation run. The results prove that the proposed algorithm is robust, fast and simply structured, and manages to find high-quality solutions in short computational times by efficiently alternating search diversification and intensification using very few user-defined parameters.     

A multiobjective metaheuristic for a mean-risk multistage capacity investment problem

We propose a multiobjective local search metaheuristic for a mean-risk multistage capacity investment problem with irreversibility, lumpiness and economies of scale in capacity costs. Conditional value-at-risk is considered as a risk measure. Results of a computational study are presented and indicate that the approach is capable of producing high-quality approximations to the efficient sets with a modest computational effort. The best results are achieved with a new hybrid approach, combining Tabu Search and Variable Neighbourhood Search.     

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.     

Interactive analysis of multiple-criteria project scheduling problems

The paper considers an interactive search over a non-dominated solution space of a multiple-criteria project scheduling problem. The approach described handles quite a general class of non-preemptive project scheduling problems with renewable, non-renewable and doubly constrained resources, multiple performing modes of activities, precedence constraints in the form of an activity network and multiple project performance criteria of time and cost type. The approach consists of two stages. In the first stage, a large representative sample of approximately non-dominated schedules is generated by the Pareto Simulated Annealing (PSA) metaheuristic method. Then, in the second stage, an interactive search over the sample is organized by the `Light Beam Search' (LBS) procedure in its discrete version.     

Dynamic programming based metaheuristics for the dial-a-ride problem

The organization of a specialized transportation system to perform transports for elderly and handicapped people is usually modeled as dial-a-ride problem. Users place transportation requests with specified pickup and delivery locations and times. The requests have to be completed under user inconvenience considerations by a specified fleet of vehicles. In the dial-a-ride problem, the aim is to minimize the total travel times respecting the given time windows, the maximum user ride times, and the vehicle restrictions. This paper introduces a dynamic programming algorithm for the dial-a-ride problem and demonstrates its effective application in (hybrid) metaheuristic approaches. Compared to most of the works presented in literature, this approach does not make use of any (commercial) solver. We present an exact dynamic programming algorithm and a dynamic programming based metaheuristic, which restricts the considered solution space. Then, we propose a hybrid metaheuristic algorithm which integrates the dynamic programming based algorithms into a large neighborhood framework. The algorithms are tested on a given set of benchmark instances from the literature and compared to a state-of-the-art hybrid large neighborhood search approach.     

NeuroGenetic approach for combinatorial optimization: an exploratory analysis

Given the NP-Hard nature of many optimization problems, it is often impractical to obtain optimal solutions to large-scale problems in reasonable computing time. For this reason, heuristic and metaheuristic search approaches are used to obtain good solutions fast. However, these techniques often struggle to develop a good balance between local and global search. In this paper we propose a hybrid metaheuristic approach which we call the NeuroGenetic approach to search for good solutions for these large scale optimization problems by at least partially overcoming this challenge. The proposed NeuroGenetic approach combines the Augmented Neural Network (AugNN) and the Genetic Algorithm (GA) search approaches by interleaving the two. We chose these two approaches to hybridize, as they offer complementary advantages and disadvantages; GAs are very good at searching globally, while AugNNs are more proficient at searching locally. The proposed hybrid strategy capitalizes on the strong points of each approach while avoiding their shortcomings. In the paper we discuss the issues associated with the feasibility of hybridizing these two approaches and propose an interleaving algorithm. We also provide empirical evidence demonstrating the effectiveness of the proposed approach.     

A multiobjective metaheuristic for a mean-risk static stochastic knapsack problem

In this paper we address two major challenges presented by stochastic discrete optimisation problems: the multiobjective nature of the problems, once risk aversion is incorporated, and the frequent difficulties in computing exactly, or even approximately, the objective function. The latter has often been handled with methods involving sample average approximation, where a random sample is generated so that population parameters may be estimated from sample statistics—usually the expected value is estimated from the sample average. We propose the use of multiobjective metaheuristics to deal with these difficulties, and apply a multiobjective local search metaheuristic to both exact and sample approximation versions of a mean-risk static stochastic knapsack problem. Variance and conditional value-at-risk are considered as risk measures. Results of a computational study are presented, that indicate the approach is capable of producing high-quality approximations to the efficient sets, with a modest computational effort.     

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.     

CHESS—Changing Horizon Efficient Set Search: A Simple Principle for Multiobjective Optimization

This paper presents a new concept for generating approximations to the non-dominated set in multiobjective optimization problems. The approximation set A is constructed by solving several single-objective minimization problems in which a particular function D(A, z) is minimized. A new algorithm to calculate D(A, z) is proposed.No general approach is available to solve the one-dimensional optimization problems, but metaheuristics based on local search procedures are used instead. Tests with multiobjective combinatorial problems whose non-dominated sets are known confirm that CHESS can be used to approximate the non-dominated set. Straightforward parallelization of the CHESS approach is illustrated with examples.The algorithm to calculate D(A, z) can be used in any other applications that need to determine Tchebycheff distances between a point and a dominant-free set.     

Metaheuristic methods based on Tabu search for assigning judges to competitions

Two metaheuristic methods based on Tabu search are introduced to assign judges to individual competitions in a tournament. The complexity of the mathematical formulation accounting for the assignment rules, leads us to use such an approach. The first metaheuristic includes two different Tabu searches that are combined with a diversification strategy. The second metaheuristic is applied to a penalized version of the original model formulated as an assignment problem. This metaheuristic is also based on a Tabu search procedure including a diversification strategy driven by the constraints violated. Numerical results are provided to indicate the efficiency of the methods to generate very good solutions.     

Scatter tabu search for multiobjective clustering problems

We propose a hybrid heuristic procedure based on scatter search and tabu search for the problem of clustering objects to optimize multiple criteria. Our goal is to search for good approximations of the efficient frontier for this class of problems and provide a means for improving decision making in multiple application areas. Our procedure can be viewed as an extension of SSPMO (a scatter search application to nonlinear multiobjective optimization) to which we add new elements and strategies specially suited for combinatorial optimization problems. Clustering problems have been the subject of numerous studies; however, most of the work has focused on single-objective problems. Clustering using multiple criteria and/or multiple data sources has received limited attention in the operational research literature. Our scatter tabu search implementation is general and tackles several problems classes within this area of combinatorial data analysis. We conduct extensive experimentation to show that our method is capable of delivering good approximations of the efficient frontier for improved analysis and decision making.     

The influence of the fitness evaluation method on the performance of multiobjective search algorithms

In this paper we are concerned with finding the Pareto optimal front or a good approximation to it. Since non-dominated solutions represent the goal in multiobjective optimisation, the dominance relation is frequently used to establish preference between solutions during the search. Recently, relaxed forms of the dominance relation have been proposed in the literature for improving the performance of multiobjective search methods. This paper investigates the influence of different fitness evaluation methods on the performance of two multiobjective methodologies when applied to a highly constrained two-objective optimisation problem. The two algorithms are: the Pareto archive evolutionary strategy and a population-based annealing algorithm. We demonstrate here, on a highly constrained problem, that the method used to evaluate the fitness of candidate solutions during the search affects the performance of both algorithms and it appears that the dominance relation is not always the best method to use.     

High-Level Relay Hybrid Metaheuristic Method for Multi-Depot Vehicle Routing Problem with Time Windows

This paper presents an efficient hybrid metaheuristic solution for multi-depot vehicle routing with time windows (MD-VRPTW). MD-VRPTW involves the routing of a set of vehicles with limited capacity from a set of depots to a set of geographically dispersed customers with known demands and predefined time windows. The present work aims at using a hybrid metaheuristic algorithm in the class of High-Level Relay Hybrid (HRH) which works in three levels and uses an efficient genetic algorithm as the main optimization algorithm and tabu search as an improvement method. In the genetic algorithm various heuristics incorporate local exploitation in the evolutionary search. An operator deletion- retrieval strategy is executed which shows the efficiency of the inner working of the proposed method. The proposed algorithm is applied to solve the problems of the standard Cordeau??s Instances. Results show that proposed approach is quite effective, as it provides solutions that are competitive with the best known in the literature.     

Solving the musical orchestration problem using multiobjective constrained optimization with a genetic local search approach

In this paper a computational approach of musical orchestration is presented. We consider orchestration as the search of relevant sound combinations within large instruments sample databases and propose two cooperating metaheuristics to solve this problem. Orchestration is seen here as a particular case of finding optimal constrained multisets on a large ensemble with respect to several objectives. We suggest a generic and easily extendible formalization of orchestration as a constrained multiobjective search towards a target timbre, in which several perceptual dimensions are jointly optimized. We introduce Orchidée, a time-efficient evolutionary orchestration algorithm that allows the discovery of optimal solutions and favors the exploration of non-intuitive sound mixtures. We also define a formal framework for global constraints specification and introduce the innovative CDCSolver repair metaheuristic, thanks to which the search is led towards regions fulfilling a set of musical-related requirements. Evaluation of our approach on a wide set of real orchestration problems is also provided.     

Multi-objective open shop scheduling by considering human error and preventive maintenance

This study presents an open shop scheduling model by considering human error and preventive maintenance. The proposed mathematical model takes into account conflicting objective functions including makespan, human error and machine availability. In order to find the optimum scheduling, human error, maintenance and production factors are considered, simultaneously. Human error is measured by Human Error Assessment and Reduction Technique (HEART). Three metaheuristic methods including non-dominated sorting genetic algorithm-II (NSGA-II), multi-objective particle swarm optimization (MOPSO) and strength Pareto evolutionary algorithm II (SPEA-II) are developed to find near-optimal solution. The Taguchi method is applied by adjusting parameters of metaheuristic algorithms. Several illustrative examples and a real case study (auto spare parts manufacturer) are applied to show the applicability of the multi-objective mixed integer nonlinear programming model. The proposed approach of this study may be used for similar open shop problems with minor modifications.     

Multiobjective big data optimization based on a hybrid salp swarm algorithm and differential evolution

This paper developed a multiobjective Big Data optimization approach based on a hybrid salp swarm algorithm and the differential evolution algorithm. The role of the differential evolution algorithm is to enhance the capability of the feature exploitation of the salp swarm algorithm because the operators of the differential evolution algorithm are used as local search operators. In general, the proposed method contains three stages. In the first stage, the population is generated, and the archive is initialized. The second stage updates the solutions using the hybrid salp swarm algorithm and the differential evolution algorithm, and the final stage determines the nondominated solutions and updates the archive. To assess the performance of the proposed approach, a series of experiments were performed. A set of single-objective and multiobjective problems from the 2015 Big Data optimization competition were tested; the dataset contained data with and without noise. The results of our experiments illustrated that the proposed approach outperformed other approaches, including the baseline nondominated sorting genetic algorithm, on all test problems. Moreover, for single-objective problems, the score value of the proposed method was better than that of the traditional multiobjective salp swarm algorithm. When compared with both algorithms, that is, the adaptive DE algorithm with external archive and the hybrid multiobjective firefly algorithm, its score was the largest. In contrast, for the multiobjective functions, the scores of the proposed algorithm were higher than that of the fireworks algorithm framework.     

Using metaheuristic compromise programming for the solution of multiple-objective scheduling problems

In this paper, we propose a generic approach to find compromise solutions for multiple-objective scheduling problems using metaheuristics. As an illustration, we present a new hybrid tabu search/variable neighbourhood search application of this approach for the solution of a bi-objective scheduling problem. Through numerical experiments we demonstrate its efficiency and effectiveness. We have confirmed that compromise programming with the tabu-VNS metaheuristic generates solutions that approach those of the known reference sets.     

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.     

Heuristic algorithms for the cardinality constrained efficient frontier

This paper examines the application of genetic algorithm, tabu search and simulated annealing metaheuristic approaches to finding the cardinality constrained efficient frontier that arises in financial portfolio optimisation. We consider the mean-variance model of Markowitz as extended to include the discrete restrictions of buy-in thresholds and cardinality constraints. Computational results are reported for publicly available data sets drawn from seven major market indices involving up to 1318 assets. Our results are compared with previous results given in the literature illustrating the effectiveness of the proposed metaheuristics in terms of solution quality and computation time.     

Integrating partial optimization with scatter search for solving bi-criteria {0, 1}-knapsack problems

This paper deals with the problem of inaccuracy of the solutions generated by metaheuristic approaches for combinatorial optimization bi-criteria {0, 1}-knapsack problems. A hybrid approach which combines systematic and heuristic searches is proposed to reduce that inaccuracy in the context of a scatter search method. The components of this method are used to determine regions in the decision space to be systematically searched.