Meta-heuristics are of significant interest to decision-makers due to the capability of finding good solutions for complex problems within a reasonable amount of computational time. These methods are further known to perform according to how their algorithm-specific parameters are set. As most practitioners aim for an off-the-shelf approach when using meta-heuristics, they require an easy applicable strategy to calibrate its parameters and use it. This chapter addresses the so-called Parameter Setting Problem (PSP) and presents new developments for the Instance-specific Parameter Tuning Strategy (IPTS). The IPTS presented only requires the end user to specify its preference regarding the trade-off between running time and solution quality by setting one parameter p (0 = p =1), and automatically returns a good set of algorithm-specific parameter values for each individual instance based on the calculation of a set of problem instance characteristics. The IPTS does not require any modification of the particular meta-heuristic being used. It aims to combine advantages of the Parameter Tuning Strategy (PTS) and the Parameter Control Strategy (PCS), the two major approaches to the PSP. The chapter outlines the advantages of an IPTS and shows in more detail two ways in which an IPTS can be designed. The first design approach requires expert-based knowledge of the meta-heuristic's performance in relation to the problem at hand. The second, automated approach does not require explicit knowledge of the meta-heuristic used. Both designs use a fuzzy logic system to obtain parameter values. Results are presented for an IPTS designed to solve instances of the Travelling Salesman Problem (TSP) with the meta-heuristic Guided Local Search (GLS).
Top1. Introduction
Exact algorithms for combinatorial optimisation problems (COPs) guarantee that a solution - if one can be found - is optimal. In practice, however, many applications are represented by large problem instances whose optimal solution can only rarely be found in a reasonable time. Heuristic methods with practical running times, although not guaranteeing optimality, are therefore often more attractive for decision makers. Meta-heuristics, including the well-known strategies of simulated annealing, tabu search, genetic algorithms, and guided local search, are often very successful by having mechanisms in place allowing the search to escape the local optimality trap. They are known to perform according to the setting of incorporated parameters. Finding the best values for those parameters is arguably a time-consuming and tedious process. It is henceforth called the Parameter Setting Problem (PSP).
Two major approaches have emerged in the course of a decade to solve the PSP, known as the Parameter Tuning Strategy (PTS) and the Parameter Control Strategy (PCS). A PTS is based on a search for a best fixed set of parameter values for a representative set of instances of a problem. The criterion is often to maximize the average solution quality over all instances of the test set. The outcome is a single set of parameters, which is then re-used whenever new instances in the future have to be solved. A PTS does not require the modification of the meta-heuristic. A PTS is also known as an offline strategy, see Coy et al. (2001), Adenso-Diaz and Laguna (2006), and Kern (2006). A meta-heuristic is considered non-robust if instance characteristics, e.g. instance size or other structural specifics, have an impact on heuristic performance, i.e. solution quality and computational time. Hence, if the set of parameter values is fixed for all instances to be solved, performance – in form of solution quality or computational time – will be average for a set of instances. Therefore, using the same set of parameters is only disadvantageous if the meta-heuristic is non-robust. In practice, however, this is known to be the case for most approaches considering performance values such as computational time and solution quality.
A PCS, also known as an online strategy, see Eiben et al. (1999), Smith (2008), and Jeong et al. (2009), typically starts with initial parameter values, but may update these during the run of the meta-heuristic on a particular instance. A PCS thus requires extending the code of the meta-heuristic, or at least allow for the dynamic extraction of necessary data while the meta-heuristic is running, and the capability of re-setting parameter values on the fly. A PCS works arguably well when the different instances that need solving are not a priori well known but are expected to differ significantly in their characteristics so that instance-specific tailoring of parameter values, during the meta-heuristic search process itself, pays off in solution quality or computational time.
The recently developed Instance-specific Parameter Tuning Strategy (IPTS), see Pavon et al. (2009), and Ries (2009), aims to combine advantages of PTS and PCS. An IPTS provides an initial good set of parameter values to the meta-heuristic, similar to a PTS. In addition, however, this set of parameter values is determined in function of structural information of the particular instance to be solved. The latter feature is somewhat similar to a PCS, however, instead of allowing the modification of parameter values during the runtime of the meta-heuristic, the structural information of an instance is retrieved in a pre-processing step by an IPTS algorithm that runs independently from the meta-heuristic. The meta-heuristic itself thus needs no modification. Further, it is advised to include a decision maker preference p, allowing the IPTS algorithm to return parameter values that either focus on leading to good solution quality, short computational times, or a balance between these extremes.