A beginner's guide to tuning methods

Metaheuristic methods have been demonstrated to be efficient tools to solve hard optimization problems. Most metaheuristics define a set of parameters that must be tuned. A good setup of that parameter values can lead to take advantage of the metaheuristic capabilities to solve the problem at hand. Tuning strategies are step by step methods based on multiple runs of the metaheuristic algorithm. In this study we compare four automated tuning methods: F-Race, Revac, ParamILS and SPO. We evaluate the performance of each method using a standard genetic algorithm for continuous function optimization. We discuss about the requirements of each method, the resources used and quality of solutions found in different scenarios. Finally we establish some guidelines that can help to choose the more appropriate tuning procedure.     

A framework for the application of metaheuristics to?tasks-to-processors assignation problems

The optimization of the execution time of a parallel algorithm can be achieved through the use of an analytical cost model function representing the running time. Typically the cost function includes a set of parameters that model the behavior of the system and the algorithm. In order to reach an optimal execution, some of these parameters must be fitted according to the input problem and to the target architecture. An optimization problem can be stated where the modeled execution time for the algorithm is used to estimate the parameters. Due to the large number of variable parameters in the model, analytical minimization techniques are discarded. Exhaustive search techniques can be used to solve the optimization problem, but when the number of parameters or the size of the computational system increases, the method is impracticable due to time restrictions. The use of approximation methods to guide the search is also an alternative. However, the dependence on the algorithm modeled and the bad quality of the solutions as a result of the presence of many local optima values in the objective functions are also drawbacks to these techniques. The problem becomes particularly difficult in complex systems hosting a large number of heterogeneous processors solving non-trivial scientific applications. The use of metaheuristics allows for the development of valid approaches to solve general problems with a large number of parameters. A well-known advantage of metaheuristic methods is the ability to obtain high-quality solutions at low running times while maintaining generality. We propose combining the parameterized analytical cost model function and metaheuristic minimization methods, which contributes to a novel real alternative to minimize the parallel execution time in complex systems. The success of the proposed approach is shown with two different algorithmic schemes on parallel heterogeneous systems. Furthermore, the development of a general framework allows us to easily develop and experiment with different metaheuristics to adjust them to particular problems.     

SO-MI: A surrogate model algorithm for computationally expensive nonlinear mixed-integer black-box global optimization problems

This paper introduces a surrogate model based algorithm for computationally expensive mixed-integer black-box global optimization problems with both binary and non-binary integer variables that may have computationally expensive constraints. The goal is to find accurate solutions with relatively few function evaluations. A radial basis function surrogate model (response surface) is used to select candidates for integer and continuous decision variable points at which the computationally expensive objective and constraint functions are to be evaluated. In every iteration multiple new points are selected based on different methods, and the function evaluations are done in parallel. The algorithm converges to the global optimum almost surely. The performance of this new algorithm, SO-MI, is compared to a branch and bound algorithm for nonlinear problems, a genetic algorithm, and the NOMAD (Nonsmooth Optimization by Mesh Adaptive Direct Search) algorithm for mixed-integer problems on 16 test problems from the literature (constrained, unconstrained, unimodal and multimodal problems), as well as on two application problems arising from structural optimization, and three application problems from optimal reliability design. The numerical experiments show that SO-MI reaches significantly better results than the other algorithms when the number of function evaluations is very restricted (200–300 evaluations).     

Self-adaptive metaheuristics for solving a multi-objective 2-dimensional vector packing problem

In this paper, a multi-objective 2-dimensional vector packing problem is presented. It consists in packing a set of items, each having two sizes in two independent dimensions, say, a weight and a length into a finite number of bins, while concurrently optimizing three cost functions. The first objective is the minimization of the number of used bins. The second one is the minimization of the maximum length of a bin. The third objective consists in balancing the load overall the bins by minimizing the difference between the maximum length and the minimum length of a bin. Two population-based metaheuristics are performed to tackle this problem. These metaheuristics use different indirect encoding approaches in order to find good permutations of items which are then packed by a separate decoder routine whose parameters are embedded in the solution encoding. It leads to a self-adaptive metaheuristic where the parameters are adjusted during the search process. The performance of these strategies is assessed and compared against benchmarks inspired from the literature.     

Multi‐objective optimization using metaheuristics: non‐standard algorithms

In recent years, the application of metaheuristic techniques to solve multi‐objective optimization problems has become an active research area. Solving this kind of problems involves obtaining a set of Pareto‐optimal solutions in such a way that the corresponding Pareto front fulfils the requirements of convergence to the true Pareto front and uniform diversity. Most of the studies on metaheuristics for multi‐objective optimization are focused on Evolutionary Algorithms, and some of the state‐of‐the‐art techniques belong this class of algorithms. Our goal in this paper is to study open research lines related to metaheuristics but focusing on less explored areas to provide new perspectives to those researchers interested in multi‐objective optimization. In particular, we focus on non‐evolutionary metaheuristics, hybrid multi‐objective metaheuristics, parallel multi‐objective optimization and multi‐objective optimization under uncertainty. We analyze these issues and discuss open research lines.     

A hybrid metaheuristic for the prize-collecting single machine scheduling problem with sequence-dependent setup times

This paper investigates a single machine scheduling problem with strong industrial background, named the prize-collecting single machine scheduling problem with sequence-dependent setup times. In this problem, there are n candidate jobs for processing in a single machine, each job has a weight (or profit) and a processing time, and during processing a symmetric sequence-dependent setup time exists between two consecutive jobs. Since there is a maximum available time limitation of the machine, it is generally impossible to complete the processing of all the candidate jobs within this time limitation. The objective is to find a job processing sequence of maximal job weights (or profits) over a subset of all candidate jobs whose makespan does not exceed the given time limitation. This problem can be considered as an application of the orienteering problem (OP) in the field of discrete manufacturing. We formulate this problem as a mixed integer linear programming (MILP) model and propose a hybrid metaheuristic combining the structures of scatter search and variable neighborhood search. Computational results on a large number of randomly generated instances with different structures show that the proposed hybrid metaheuristic outperforms CPLEX and two metaheuristics proposed for the OP.     

Comparative Analysis of Different Evaluation Functions for Protein Structure Prediction Under the HP Model

The HP model for protein structure prediction abstracts the fact that hydrophobicity is a dominant force in the protein folding process.This challenging combinatorial optimization problem has been widely addressed through metaheuristics.The evaluation function is a key component for the success of metaheuristics;the poor discrimination of the conventional evaluation function of the HP model has motivated the proposal of alternative formulations for this component. This comparative analysis inquires into the effectiveness of seven different evaluation functions for the HP model.The degree of discrimination provided by each of the studied functions, their capability to preserve a rank ordering among potential solutions which is consistent with the original objective of the HP model, as well as their effect on the performance of local search methods are analyzed.The obtained results indicate that studying alternative evaluation schemes for the HP model represents a highly valuable direction which merits more attention.     

Cooperative search for fair nurse rosters

The development of decision support systems acceptable for nurse rostering practitioners still presents a daunting challenge. Building on an existing nurse rostering problem, a set of fairness-based objective functions recently introduced in the literature has been extended. To this end, a generic agent-based cooperative search framework utilising new mechanisms is described, aiming to combine the strengths of multiple metaheuristics. These different metaheuristics represent individual planners’ implicit procedures for improving rosters. The framework enables to explore different ways of assessing nurse rosters in terms of fairness objectives. Computational experiments have been conducted across a set of benchmark instances. The overall results indicate that the proposed cooperative search for fair nurse rosters outperforms each metaheuristic run individually.     

Evaluating differential evolution with penalty function to solve constrained engineering problems

Over the years, several metaheuristics have been developed to solve hard constrained and unconstrained optimization problems. In general, a metaheuristic is proposed and following researches are made to improve the original algorithm. In this paper, we evaluate a not so new metaheuristic called differential evolution (DE) to solve constrained engineering design problems and compare the results with some recent metaheuristics. Results show that the classical DE with a very simple penalty function to handle constraints is still very competitive in the tested problems.     

Minimising total tardiness in the m-machine flowshop problem: A review and evaluation of heuristics and metaheuristics

In this work, a review and comprehensive evaluation of heuristics and metaheuristics for the m-machine flowshop scheduling problem with the objective of minimising total tardiness is presented. Published reviews about this objective usually deal with a single machine or parallel machines and no recent methods are compared. Moreover, the existing reviews do not use the same benchmark of instances and the results are difficult to reproduce and generalise. We have implemented a total of 40 different heuristics and metaheuristics and we have analysed their performance under the same benchmark of instances in order to make a global and fair comparison. In this comparison, we study from the classical priority rules to the most recent tabu search, simulated annealing and genetic algorithms. In the evaluations we use the experimental design approach and careful statistical analyses to validate the effectiveness of the different methods tested. The results allow us to clearly identify the state-of-the-art methods.     

HYBRID METAHEURISTICS FOR THE DESIGN OF COUPLED RESONATOR FILTERS

The design of coupled resonator filters used in many telecommunication applications poses an optimization problem that can be tackled with heuristic methods. In many configurations, simple heuristic methods do not give satisfactory results, and the combination in hybrid metaheuristics of local and global search methods is a better approach. This article analyzes the systematic development of hybrid metaheuristic methods for the design of coupled resonator filters. Engineers normally use the MATLAB computing environment to work on the design of these devices, so the available MATLAB optimization toolboxes are used here as a basis to address those optimization problems. The results obtained are in general satisfactory, and the best results are obtained in the experiments with memetic algorithms in which methods based in populations (Genetic Algorithms and Scatter Search) are combined with local search methods to improve individuals in the population at different parts of the metaheuristic.     

A sensitivity analysis method for driving the Artificial Bee Colony algorithm's search process

In this paper, we improve D. Karaboga's Artificial Bee Colony (ABC) optimization algorithm, by using the sensitivity analysis method described by Morris. Many improvements of the ABC algorithm have been made, with effective results. In this paper, we propose a new approach of random selection in neighborhood search. As the algorithm is running, we apply a sensitivity analysis method, Morris’ OAT (One-At-Time) method, to orientate the random choice selection of a dimension to shift. Morris’ method detects which dimensions have a high influence on the objective function result and promotes the search following these dimensions. The result of this analysis drives the ABC algorithm towards significant dimensions of the search space to improve the discovery of the global optimum. We also demonstrate that this method is fruitful for more recent improvements of ABC algorithm, such as GABC, MeABC and qABC.     

Structural optimization using global stress-deviation objective function via the level-set method

The paper deals with minimum stress design using a novel stress-related objective function based on the global stress-deviation measure. The shape derivative, representing the shape sensitivity analysis of the structure domain, is determined for the generalized form of the global stress-related objective function. The optimization procedure is based on the domain boundary evolution via the level-set method. The elasticity equations are, instead of using the usual ersatz material approach, solved by the extended finite element method. The Hamilton-Jacobi equation is solved using the streamline diffusion finite element method. The use of finite element based methods allows a unified numerical approach with only one numerical framework for the mechanical problem as also for the boundary evolution stage. The numerical examples for the L-beam benchmark and the notched beam are given. The results of the structural optimization problem, in terms of maximum von Mises stress corresponding to the obtained optimal shapes, are compared for the commonly used global stress measure and the novel global stress-deviation measure, used as the stress-related objective functions.     

A parameterized shared-memory scheme for parameterized metaheuristics

This paper presents a parameterized shared-memory scheme for parameterized metaheuristics. The use of a parameterized metaheuristic facilitates experimentation with different metaheuristics and hybridation/combinations to adapt them to the particular problem we are working with. Due to the large number of experiments necessary for the metaheuristic selection and tuning, parallelism should be used to reduce the execution time. To obtain parallel versions of the metaheuristics and to adapt them to the characteristics of the parallel system, a unified parameterized shared-memory scheme is developed. Given a particular computational system and fixed parameters for the sequential metaheuristic, the appropriate selection of parameters in the unified parallel scheme eases the development of parallel efficient metaheuristics.     

A nonlinear multi-dimensional variable selection method for high dimensional data: Sparse MAVE

Traditional variable selection methods are model based and may suffer from possible model misspecification. On the other hand, sufficient dimension reduction provides us with a way to find sufficient dimensions without a parametric model. However, the drawback is that each reduced variable is a linear combination of all the original variables, which may be difficult to interpret. In this paper, focusing on the sufficient dimensions in the regression mean function, we combine the ideas of sufficient dimension reduction and variable selection to propose a shrinkage estimation method, sparse MAVE. The sparse MAVE can exhaustively estimate dimensions in the mean function, while selecting informative covariates simultaneously without assuming any particular model or particular distribution on the predictor variables. Furthermore, we propose a modified BIC criterion for effectively estimating the dimension of the mean function. The efficacy of sparse MAVE is verified through simulation studies and via analysis of a real data set.     

Applications of the DM-GRASP heuristic: a survey

Recent research has shown that the hybridization of metaheuristics is a powerful mechanism to develop more robust and efficient methods to solve hard optimization problems. The combination of different techniques and concepts behind metaheuristics, if well designed, has the potential to exploit their advantages while diminishing their drawbacks, which results in methods suited to a more diverse set of real problems. The DM‐GRASP heuristic is one such hybrid method that has achieved promising results. It is a hybrid version of the GRASP metaheuristic that incorporates a data‐mining process. In this work, we review how this hybridization was designed and survey the results of its practical applications evaluated until now.     

A design framework for metaheuristics

This paper is concerned with taking an engineering approach towards the application of metaheuristic problem solving methods, i.e., heuristics that aim to solve a wide variety of problems. How can a practitioner solve a problem using metaheuristic methods? What choices do they have, and how are these choices influenced by the problem at hand? Are there sensible universal choices which can be made, or are these choices always problem-dependent? The aim of this paper is to address questions such as these in the context of a (soft) engineering design framework for the application of metaheuristics. The aim of this framework is to make explicit the choices which a practitioner needs to make in applying these techniques, and to give some guidelines for how metaheuristics might be tuned to problems by considering different problem- and solution-types.     

A comparison of five hybrid metaheuristic algorithms for unrelated parallel-machine scheduling and inbound trucks sequencing in multi-door cross docking systems

The objective of this paper is to develop five hybrid metaheuristic algorithms, including three hybrid ant colony optimization (hACO) variants, and compare their performances in two related applications: unrelated parallel machine scheduling and inbound truck sequencing in a multi-door cross docking system in consideration of sequence dependent setup, and both zero and nonzero release time. The three hACO variants were modified and adapted from the existing literature and they differ mainly in how a solution is coded and decoded, how a pheromone matrix is represented, and the local search methods employed. The other two hybrids are newly constructed hybrid simulated annealing (hSA) algorithms, which are built based on the authors’ knowledge and experience. The evaluation criteria are computational time and the objective function value, i.e., makespan. Based on the results of computational experiments the simulated annealing-tabu search hybrid turns out to be the best if maximal CPU time is used as the stopping criterion and the 2-stage hACO variant is the best if maximal number of evaluations is the stopping criterion. The contributions of this paper are: (i) being the first to carry out a comparative study of hybrid metaheuristics for the two selected applications, (ii) being the first to consider nonzero truck arrival time in multi-door cross docking operations, (iii) identifying which hACO variant is the best among the three, and (iv) investigating the effect of release time on the makespan.     

A comparison of global optimization algorithms applied to a ride comfort optimization problem

This study presents a comparison of global optimization algorithms applied to an industrial engineering optimization problem. Three global stochastic optimization algorithms using continuous variables, i.e. the domain elimination method, the zooming method and controlled random search, have been applied to a previously studied ride comfort optimization problem. Each algorithm is executed three times and the total number of objective function evaluations needed to locate a global optimum is averaged and used as a measure of efficiency. The results show that the zooming method, with a proposed modification, is most efficient in terms of number of objective function evaluations and ability to locate the global optimum. Each design variable is thereafter given a set of discrete values and two optimization algorithms using discrete variables, i.e. a genetic algorithm and simulated annealing, are applied to the discrete ride comfort optimization problem. The results show that the genetic algorithm is more efficient than the simulated annealing algorithm for this particular optimization problem.     

SOMS: SurrOgate MultiStart algorithm for use with nonlinear programming for global optimization

SOMS is a general surrogate‐based multistart algorithm, which is used in combination with any local optimizer to find global optima for computationally expensive functions with multiple local minima. SOMS differs from previous multistart methods in that a surrogate approximation is used by the multistart algorithm to help reduce the number of function evaluations necessary to identify the most promising points from which to start each nonlinear programming local search. SOMS's numerical results are compared with four well‐known methods, namely, Multi‐Level Single Linkage (MLSL), MATLAB's MultiStart, MATLAB's GlobalSearch, and GLOBAL. In addition, we propose a class of wavy test functions that mimic the wavy nature of objective functions arising in many black‐box simulations. Extensive comparisons of algorithms on the wavy test functions and on earlier standard global‐optimization test functions are done for a total of 19 different test problems. The numerical results indicate that SOMS performs favorably in comparison to alternative methods and does especially well on wavy functions when the number of function evaluations allowed is limited.