HYBRID AND CONSTRUCTIVE METAHEURISTICS: METHODS AND APPLICATIONS

BASIC INFORMATION

Ph.D. Student: Francisco Javier Rodríguez
Advisors: Carlos García, Manuel Lozano
Defended on: November 2012
Keywords: hybrid metaheuristics, constructive metaheuristics, parallel machines scheduling, combinatorial optimisation
Digital version

DESCRIPTION

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.

Conclusions

1) Study of HMs-EA/SA for black-box problems in binary combinatorial optimisation.
In this thesis, we provided an overview of the ways EAs and SA may be combined with each other to obtain HMs-EA/SA. We have organised the approaches found in the literature by proposing a taxonomy based on those introduced by Talbi and Raidl for hybrid metaheuristics and we have proposed new HM-EA/SA models that follow unexplored paths so far in the literature. Moreover, we have developed, to our knowledge, the first experimental study analysing a large spectrum of HM-EA/SA models from three points of view:

• We have compared the performance of the HM-EA/SA models, individually and by categories, extracting relevant conclusions regarding the categories of the presented taxonomy.
• We have performed a synergy test that has identified two HM-EA/SA models that really provide synergistic properties.
• We have compared HM-EA/SA models with the state-of-the-art evolutionary algorithms for binary combinatorial optimisation, obtaining promising results on the considered testbed.
• Our study allowed us to draw an outstanding conclusion: the hybridisation of EAs and SA becomes a prospective research area for finding more effective search algorithms.

2) Hybrid and constructive metaheuristics for scheduling on non-identical parallel machines with minimising total weighted completion times.
For the non-identical parallel machines scheduling problem with minimising total weighted completion times, we have proposed two different approaches in this thesis:
In the first place, we have proposed a hybrid algorithm for the scheduling on uniform and unrelated parallel machines problem, which combines the basic GRASP scheme with other elements such as path-relinking and evolutionary path-relinking. Moreover, we have performed a comparative study between the proposed algorithm and the previously existing metaheuristics for this problem. This study has shown that the GRASP + path-relinking algorithm provides the best performance from among the studied algorithms. In addition, elements such as the greedy randomised initial solutions and path-relinking, which distinguish the proposed method from compared metaheuristics, have proven to be quite useful increasing the quality of the solutions and achieving high-quality solutions in a reasonable time. Finally, the better performance of the hybrid GRASP + path-relinking over the pure GRASP shows that their combination really provide a profitable synergy.
Secondly, we have proposed an IG algorithm to deal with the scheduling on unrelated parallel machines problem, expanding the study to instances larger than the previous work and considering different conditions for generating instances. The computational experiments performed show that: 1) the proposed IG is very competitive with other state-of-the-art algorithms for this problem; specifically, significant improvements were obtained for large size problem instances (involving a large number of jobs or machines) and 2) Our IG has been tested on a great number of different kinds of instances, proving to be very robust. Moreover, from the methodological point of view, the proposed IG presents two novel elements that can help to improve the performance of IG on other optimisation problems. In the first place, the acceptance criterion including randomness has proved to be quite useful to improve its performance. Secondly, the heuristic strategy for the destruction step has allowed improving the results of the proposed IG on certain types of difficult instances. This way, we think that using more elaborated strategies in the destructive step than the classical random one should be considered when dealing with complex optimisation problems thorough IG algorithms.

3) Hybrid and constructive metaheuristics for the quadratic minimum spanning tree problem.
Finally, in this thesis, we have faced the quadratic minimum spanning tree problem and compared the behaviour on this problem of two different metaheuristics that follow a constructive strategy as SO and IG. Our research study demonstrates the effectiveness of a strategy for solving this problem that alternates between constructive and destructive phases, as originally proposed in strategic oscillation and more recently in IG method.
Our tests disclose that the memory-based strategic oscillation method is able to solve complex instances better than other previous algorithms. On the other hand, our implementation of the IG algorithm succeeds in performing most effectively for large problems that are not highly complex, while the iterated tabu search (ITS) algorithm performs best in application to easier instances. Based on these findings we developed a hybrid method, HSII, that combines these three algorithms, which proved very effective across the board with the exception of one class of problem instances, where ITS remained the winner.
Overall, the ability of the alternating constructive/destructive strategies to give superior outcomes for larger problems, with memory proving valuable for complex problems and a disregard for memory proving valuable for easier problems, invites further consideration of other forms of strategic oscillation, particularly by crossing feasibility boundaries and by going beyond the reliance on randomisation in carrying out destructive moves by introducing more advanced strategies for selecting these moves.

FUNDS

The development of this thesis was supported by:

• Regional Government of Andalusia, project P08-TIC-4173.
• Spanish Ministry of Education and Science, project TIN2008-05854.
• Spanish Ministry of Science and Innovation, project TIN2011-24124.

PUBLICATIONS ASSOCIATED WITH THIS THESIS

INTERNATIONAL JOURNALS

1. F. J. Rodríguez, C. García-Martínez, M. Lozano. Hybrid Metaheuristics Based on Evolutionary Algorithms and Simulated Annealing: Taxonomy, Comparison, and Synergy Test IEEE Transactions on Evolutionary Computation, vol. 16(6), pp. 787-800. 2012.
2. F. J. Rodríguez, C. Blum, C. García-Martínez, M. Lozano. GRASP with path-relinking for the non-identical parallel machine scheduling problem with minimising total weighted completion times. Annals of Operations Research, vol. 201(1), pp. 383-401. 2012.
3. C. C. García-Martínez, M. Lozano, F. J. Rodríguez. A simulated annealing method based on a specialised evolutionary algorithm. Applied Soft Computing, vol. 12(2), pp. 573-588. 2012.
4. F. J. Rodríguez, M. Lozano, C. Blum, C. García-Martínez. An Iterated Greedy Algorithm for the Large-Scale Unrelated Parallel Machines Scheduling Problem. Computers & Operations Research, vol. 40(7), pp. 1829-1841. 2013.
5. M. Lozano, F. Glover, C. García-Martínez, F. J. Rodríguez, R. Martí. Tabu Search with Strategic Oscillation for the Quadratic Minimum Spanning Tree. IIE Transactions, vol. 46(4). pp. 414-428. 2014.

INTERNATIONAL CONFERENCES

1. F.J. Rodríguez, C. García-Martínez, C. Blum and M. Lozano. An Artificial Bee Colony Algorithm for the Unrelated Parallel Machines Scheduling Problem. Proceedings of Parallel Problem Solving from Nature (PPSN’12), pp. 143-152. 2010.
2. F.J. Rodríguez, C. García-Martínez and M. Lozano. A GA-based Multiple Simulated Annealing. Proceedings of IEEE Congress on Evolutionary Computation, pp. 195-201. 2010.
3. F.J. Rodríguez, C. Blum, M. Lozano and C. García-Martínez. Iterated Greedy Algorithms for the Maximal Covering Location Problem. Proceedings of European Conference on Evolutionary Computation in Combinatorial Optimization, pp. 172-181. 2012.