Hybrid and constructive metaheuristics: methods and applications

Abstract

An optimisation problem concerns the selection of the best configuration of a set of variables according to some criteria. Optimisation problems can be basically divided into two categories depending on whether these variables are real-valued or discrete. Among the optimisation problems with discrete variables, we find a type called combinatorial optimisation problems. In combinatorial optimisation problems we are looking for an object such as an integer, permutation or graph from a finite (or possibly countable infinite) set. Due to the importance of combinatorial optimisation problems in science and industry, researchers have devoted great efforts to develop new algorithms to tackle these problems. Algorithms for combinatorial optimisation problems arise in countless real-world applications. Just to name a few, these algorithms are used by airline companies to schedule flights and decide their respective prices, by large companies to decide where and what to stock in their warehouses, by delivery companies to decide the routes for their trucks, by GPS navigators to provide driving directions, by word-processors to decide where to introduce blank spaces to justify a paragraph and by webshops to recommend products to their clients. The existing methods for combinatorial optimisation are classified into two categories: exact and approximate algorithms. Exact methods guarantee to find an optimal solution for every finite size instance in a bounded time. However, many problems arising in practice are NP-hard and so it is unlikely that we can design exact efficient algorithms for these problems. Thus, the use of approximate algorithms, which focus on finding good solutions in a reduced amount of time, has increased greatly in recent years. Among approximate algorithms, metaheuristics have been established as one of the most practical approach to deal with combinatorial optimisation problems. Metaheuristics are a family of approximate methods conformed by iterative processes that guide a subordinate heuristic by combining intelligently different concepts for exploring and exploiting the search space associated to the combinatorial optimisation problem. Metaheuristics have been applied to problems from very different fields, showing its ability to provide acceptably good solutions (not necessarily optimal) in a reasonable amount of time. There is a group of metaheuristics that follow distinct paradigms and are usually cited as classical metaheuristics, as they have a well-established historical background. This group includes methods such as simulated annealing (SA), tabu search, iterated local search, variable neighbourhood search, greedy randomised adaptive search procedure (GRASP), evolutionary algorithms (EAs), and scatter search. Furthermore, over the last few years, a large number of search algorithms have been presented that do not simply follow the concepts of one single classical metaheuristic, but attempt to obtain the best from a set of metaheuristics (and even other kinds of optimisation methods) that perform together and complement each other to produce a profitable synergy from their combination. These approaches are commonly referred to as hybrid metaheuristics (HMs). The increasing number of applications of hybrid metaheuristics and the existence of scientific events focused on this subject such as the series of Workshops on Hybrid Metaheuristics show the success and importance of this specific line of research. The hybridisation of EAs is becoming popular due to its ability to handle several real-world problems involving complexity, noise, imprecision, uncertainty, and vagueness. In particular, it is remarkable the use of SA to design HMs with EAs (HMs-EA/SA) due to its prominent role in the field of hybrid EAs. Besides metaheuristics based on the search for new solutions close to the current one, like SA, or by combining solutions, like EAs, we find another group of metaheuristics that generate new solutions by adding one element at a time to a partial solution. This type of methods are known as constructive metaheuristics and we find several examples in the literature such as iterated greedy (IG), GRASP, and ant colony optimisation. Constructive methods are typically the fastest between approximate ones; however, they often return solutions of inferior quality with regards to local search algorithms. Thereby, to improve the quality of final solutions, most constructive metaheuristics include a local search method after the construction phase. At the same time, constructive metaheuristics are being the subject of many studies on their hybridisations. In the literature, we find, among many other examples, hybridisations between ant colony optimisation and genetic algorithms, ant colony optimisation and fuzzy clustering, GRASP and path relinking, GRASP and particle swarm optimisation, and IG and variable neighbourhood search. For our study, we have considered problems in two distinct scenarios. In the first one, problems in which no useful knowledge that can be used during the solving process is available, except that provided by the problem representation and constraints. These problems are known as black-box problems. In the second one, we tackle problems in environments with specific knowledge, such as information about the structure of the objective function. In particular, we have considered two different problems: parallel machines scheduling problem} and quadratic minimum spanning tree problem. Black-box problems appear in many scientific and engineering optimisation issues where there is not information to be exploited that might reinforce the search process. These problems are common when optimising computationally expensive dynamic models, bioprocess engineering, or where the evaluation of the solutions is carried out by simulations. To address these problems, context independent algorithms are applied due to they only require the type and domain of the decision variables to perform a search on the solution space. The original genetic algorithm proposed by Holland belongs to this class of methods. Parallel machines scheduling problem consists in allocating a set of jobs in any of the available machines, so that the resulting allocation satisfies certain requirements. Within the general formulation, there are many variations in response to the different components of the problem, such as the machines features or the conditions of the scheduling mechanism. Among its practical applications are the optimisation of production processes in manufacturing industry and the optimisation of process allocation in computer systems with multiple processing nodes. The quadratic minimum spanning tree problem is an extension of the well-known minimum spanning tree problem, where in addition to edge costs, we have costs associated with pairs of edges. This problem has been widely studied in the literature due to its applications in a wide variety of settings, including transportation, telecommunication, irrigation, and energy distribution. The problem appears, for example, when transferring oil from one pipe to another in a situation where the cost depends on the type of interface between two pipes. The same pairwise interaction effect arises in the connection of aboveground and underground cables in a road network with turn penalties. In this dissertation, we present the research performed on the issues commented above: 1) optimisation methods for black-box environments based on HMs combining SA and EAs and 2) hybrid and constructive metaheuristics for non-uniform parallel machines scheduling and quadratic minimum spanning tree problems. With regards to the first task, we have performed a study of the state-of-the-art HMs-EA/SA for combinatorial optimisation, classifying them according to a proposed taxonomy for this kind of methods. Moreover, we have presented new HMs-EA/SA that cover categories of the proposed taxonomy for which there are no previous HMs-EA/SA in the literature. Finally, we have compared the experimental performance of the most representative HMs-EA/SA and state-of-the-art methods for combinatorial optimisation. With regards to the second task, we have identified the state-of-the-art metaheuristics for the non-uniform parallel machines scheduling problem and the quadratic minimum spanning tree problem and we have explored constructive metaheuristics combined with local search methods and other metaheuristics such as tabu search and path-relinking, resulting in competitive algorithms with regards to state-of-the-art methods.