- author = "Ayad Mashaan Turky",
- title = "Bi-level hyper-heuristic approaches for combinatorial optimisation problems",
- school = "College of Science, Engineering, and Health, RMIT University",
- year = "2019",
- address = "Melbourne, Victoria, Australia",
- month = jul,
- keywords = "genetic algorithms, genetic programming, hyper-heuristic, combinatorial optimisation problems, multi-capacity bin packing problem, google machine reassignment problem, bi-level, bin packing problem",
- language = "eng",
-
URL = "
https://research-repository.rmit.edu.au/articles/thesis/Bi-level_hyper-heuristic_approaches_for_combinatorial_optimisation_problems/27580371.pdf",
-
URL = "
https://research-repository.rmit.edu.au/articles/thesis/Bi-level_hyper-heuristic_approaches_for_combinatorial_optimisation_problems/27580371?file=50749800",
-
URL = "https://academics.rmit.edu.au/andy-song/teaching#29-Feb-2016",
- size = "159 pages",
- abstract = "Many real-world combinatorial optimisation problems (COPs) are too complex to be handled in polynomial time using exact methods. One way to solve such problems is using approximation or heuristic algorithms which produce good quality solutions within a reasonable amount of time. Local searches are a class of approximation algorithms for dealing with COPs and have been shown to be very effective in solving large-scale COPs. Several local search algorithms have been proposed in literature where different ones use different rules or mechanisms to approach the search space of a given COP. However, due to the complexity and variability of characteristics in different COPs, it is very different to decide which local search algorithm should be used. Indeed, it is very different to design a single local search algorithm that can perform well across a diverse set of COP instances. Furthermore, even for a given local search algorithm, its performance critically hinges on the setting of its internal components, such as the operators/parameters that should be included or adjusted, and this may vary from one instance to another. To deal with these issues, this thesis proposes bi-level hyper-heuristic approaches that use various local and diverse sets of operators for solving COPs. The proposed frameworks control the selection of the local search algorithm and operators that should be used at each decision point. The appropriate mix of the local search algorithm with the operators are determined adaptively during the search process. In this thesis, the search spaces of the local search algorithm and operators are formulated as bi-level heuristic search spaces that interact with each other during the selection process. This thesis introduces two new hyper-heuristic approaches. One approach comprises a two-stage hyper-heuristic local search to adaptively select local search algorithm and its components. The local search algorithms are selected in the first stage and the operators for the selected local search are chosen in the second stage. The two stages interact with each other by exchanging information in order to arrive at a better decision. The second approach is based on two interleaved ant colonies that integrates the strengths of several local search algorithms and their components. This new framework is an improvement on its predecessor in several respects, but the key contributions are related to the designing of dual ant colonies and the use of multiple evaluation criteria. We formulate the search spaces of local search algorithms and their components as a graph to be searched by the proposed framework. The dual ant colonies work an interleaved manner as an adaptive selection mechanism where the first one controls the selection of which local search algorithm should be applied, while the second one chooses the local search algorithm components for the selected local search algorithm. These design colonies exploit and exchange information in a co-operative manner to effectively guide the search and the selection process. To test the generality, consistency and performance of the proposed frameworks, two COPs are considered: a multi-capacity bin packing problem (MCBPP) and a google machine reassignment problem (GMRP). Results demonstrate that the proposed frameworks obtain competitive results (if not best results for some instances), on all problem domains when compared to the best-known methods in the literature.",
-
notes = "RMIT University = Royal Melbourne Institute of
Technology
supervisors: Andy Song and Nasser R. Sabar and Simon Dunstall",
