Evolving timetabling heuristics using a grammar-based genetic programming hyper-heuristic framework

This paper introduces a Grammar-based Genetic Programming Hyper-Heuristic framework (GPHH) for evolving constructive heuristics for timetabling. In this application GP is used as an online learning method which evolves heuristics while solving the problem. In other words, the system keeps on evolving heuristics for a problem instance until a good solution is found. The framework is tested on some of the most widely used benchmarks in the field of exam timetabling and compared with the best state-of-the-art approaches. Results show that the framework is very competitive with other constructive techniques, and did outperform other hyper-heuristic frameworks on many occasions.     

Hybridizations within a graph-based hyper-heuristic framework for university timetabling problems

A significant body of recent literature has explored various research directions in hyper-heuristics (which can be thought as heuristics to choose heuristics). In this paper, we extend our previous work to construct a unified graph-based hyper-heuristic (GHH) framework, under which a number of local search-based algorithms (as the high level heuristics) are studied to search upon sequences of low-level graph colouring heuristics. To gain an in-depth understanding on this new framework, we address some fundamental issues concerning neighbourhood structures and characteristics of the two search spaces (namely, the search spaces of the heuristics and the actual solutions). Furthermore, we investigate efficient hybridizations in GHH with local search methods and address issues concerning the exploration of the high-level search and the exploitation ability of the local search. These, to our knowledge, represent entirely novel directions in hyper-heuristics. The efficient hybrid GHH obtained competitive results compared with the best published results for both benchmark course and exam timetabling problems, demonstrating its efficiency and generality across different problem domains. Possible extensions upon this simple, yet general, GHH framework are also discussed.     

A heterogeneous cooperative parallel search of branch-and-bound method and tabu search algorithm

In this study, we present a heterogeneous cooperative parallel search that integrates branch-and-bound method and tabu search algorithm. These two algorithms perform searches in parallel and cooperate by asynchronously exchanging information about the best solutions found and new initial solutions for tabu search. The rapid production of a good solution from the tabu search process provides the branch-and-bound process with a better feasible solution to accelerate the elimination of subproblems that do not contain an optimal solution. The new initial solution produced from the subproblem with a least-cost lower bound of the branch-and-bound method suggests the best potential area for tabu search to explore. We use a master-slave model to reduce the complexity of communication and enhance the performance of data exchange. A branch-and-bound process is used as the master process to control the exchange of information and the termination of computation. Several tabu search processes are executed simultaneously as the slave processes and cooperate by asynchronously exchanging information on the best solutions found and the new initial solutions by the master process of branch-and-bound. Based on the computation experiments of solving traveling salesman problems (TSP), the proposed heterogeneous parallel search algorithm outperforms a conventional parallel branch-and-bound method and a conventional parallel tabu search. We also present the computational results showing the efficiency of heterogeneous cooperative parallel search when we use more processors to accelerate search time. Thus, the proposed heterogeneous parallel search algorithm achieves linear accelerations.     

A mixture experiments multi-objective hyper-heuristic

This paper proposes a hyper-heuristic that combines genetic algorithm with mixture experiments to solve multi-objective optimisation problems. At every iteration, the proposed algorithm combines the selection criterion (rank indicator) of a number of well-established evolutionary algorithms including NSGA-II, SPEA2 and two versions of IBEA. Each indicator is called according to an associated probability calculated and updated during the search by means of mixture experiments. Mixture experiments are a particular type of experimental design suitable for the calibration of parameters that represent probabilities. Their main output is an explanatory model of algorithm performance as a function of its parameters. By finding the maximum (probability distribution) of the surface represented by this model, we also find a good algorithm parameterisation. The design of mixture experiments approach allowed the authors to identify and exploit synergies between the different rank indicators at the different stages of the search. This is demonstrated by our experimental results in which the proposed algorithm compared favourably against other well-established algorithms.     

A graph-based hyper-heuristic for educational timetabling problems

This paper presents an investigation of a simple generic hyper-heuristic approach upon a set of widely used constructive heuristics (graph coloring heuristics) in timetabling. Within the hyper-heuristic framework, a tabu search approach is employed to search for permutations of graph heuristics which are used for constructing timetables in exam and course timetabling problems. This underpins a multi-stage hyper-heuristic where the tabu search employs permutations upon a different number of graph heuristics in two stages. We study this graph-based hyper-heuristic approach within the context of exploring fundamental issues concerning the search space of the hyper-heuristic (the heuristic space) and the solution space. Such issues have not been addressed in other hyper-heuristic research. These approaches are tested on both exam and course benchmark timetabling problems and are compared with the fine-tuned bespoke state-of-the-art approaches. The results are within the range of the best results reported in the literature. The approach described here represents a significantly more generally applicable approach than the current state of the art in the literature. Future work will extend this hyper-heuristic framework by employing methodologies which are applicable on a wider range of timetabling and scheduling problems.     

A parallel multi-neighborhood cooperative tabu search for capacitated vehicle routing problems

This paper presents a parallel tabu search algorithm that utilizes several different neighborhood structures for solving the capacitated vehicle routing problem. Single neighborhood or neighborhood combinations are encapsulated in tabu search threads and they cooperate through a solution pool for the purpose of exploiting their joint power. The computational experiments on 32 large scale benchmark instances show that the proposed method is highly effective and competitive, providing new best solutions to four instances while the average deviation of all best solutions found from the collective best results reported in the literature is about 0.22%. We are also able to associate the beneficial use of special neighborhoods with some test instance characteristics and uncover some sources of the collective power of multi-neighborhood cooperation.     

A cooperative parallel tabu search algorithm for the quadratic assignment problem

In this study, we introduce a cooperative parallel tabu search algorithm (CPTS) for the quadratic assignment problem (QAP). The QAP is an NP-hard combinatorial optimization problem that is widely acknowledged to be computationally demanding. These characteristics make the QAP an ideal candidate for parallel solution techniques. CPTS is a cooperative parallel algorithm in which the processors exchange information throughout the run of the algorithm as opposed to independent concurrent search strategies that aggregate data only at the end of execution. CPTS accomplishes this cooperation by maintaining a global reference set which uses the information exchange to promote both intensification and strategic diversification in a parallel environment. This study demonstrates the benefits that may be obtained from parallel computing in terms of solution quality, computational time and algorithmic flexibility. A set of 41 test problems obtained from QAPLIB were used to analyze the quality of the CPTS algorithm. Additionally, we report results for 60 difficult new test instances. The CPTS algorithm is shown to provide good solution quality for all problems in acceptable computational times. Out of the 41 test instances obtained from QAPLIB, CPTS is shown to meet or exceed the average solution quality of many of the best sequential and parallel approaches from the literature on all but six problems, whereas no other leading method exhibits a performance that is superior to this.     

Competitive travelling salesmen problem: A hyper-heuristic approach

We introduce a novel variant of the travelling salesmen problem and propose a hyper-heuristic methodology in order to solve it. In a competitive travelling salesmen problem (CTSP), m travelling salesmen are to visit n cities and the relationship between the travelling salesmen is non-cooperative. The salesmen will receive a payoff if they are the first one to visit a city and they pay a cost for any distance travelled. The objective of each salesman is to visit as many unvisited cities as possible, with a minimum travelling distance. Due to the competitive element, each salesman needs to consider the tours of other salesman when planning their own tour. Since equilibrium analysis is difficult in the CTSP, a hyper-heuristic methodology is developed. The model assumes that each agent adopts a heuristic (or set of heuristics) to choose their moves (or tour) and each agent knows that the moves/tours of all agents are not necessarily optimal. The hyper-heuristic consists of a number of low-level heuristics, each of which can be used to create a move/tour given the heuristics of the other agents, together with a high-level heuristic that is used to select from the low-level heuristics at each decision point. Several computational examples are given to illustrate the effectiveness of the proposed approach.     

A simulated annealing hyper-heuristic methodology for flexible decision support

Most of the current search techniques represent approaches that are largely adapted for specific search problems. There are many real-world scenarios where the development of such bespoke systems is entirely appropriate. However, there are other situations where it would be beneficial to have methodologies which are generally applicable to more problems. One of our motivating goals for investigating hyper-heuristic methodologies is to provide a more general search framework that can be easily and automatically employed on a broader range of problems than is currently possible. In this paper, we investigate a simulated annealing hyper-heuristic methodology which operates on a search space of heuristics and which employs a stochastic heuristic selection strategy and a short-term memory. The generality and performance of the proposed algorithm is demonstrated over a large number of benchmark datasets drawn from two very different and difficult problems, namely; course timetabling and bin packing. The contribution of this paper is to present a method which can be readily (and automatically) applied to different problems whilst still being able to produce results on benchmark problems which are competitive with bespoke human designed tailor made algorithms for those problems.     

A hyper-heuristic approach to sequencing by hybridization of DNA sequences

In this paper we investigate the use of hyper-heuristic methodologies for predicting DNA sequences. In particular, we utilize Sequencing by Hybridization. We believe that this is the first time that hyper-heuristics have been investigated in this domain. A hyper-heuristic is provided with a set of low-level heuristics and the aim is to decide which heuristic to call at each decision point. We investigate three types of hyper-heuristics. Two of these (simulated annealing and tabu search) draw their inspiration from meta-heuristics. The choice function hyper-heuristic draws its inspiration from reinforcement learning. We utilize two independent sets of low-level heuristics. The first set is based on a previous tabu search method, with the second set being a significant extension to this basic set, including utilizing a different representation and introducing the definition of clusters. The datasets we use comprises two randomly generated datasets and also a publicly available biological dataset. In total, we carried out experiments using 70 different combinations of heuristics, using the three datasets mentioned above and investigating six different hyper-heuristic algorithms. Our results demonstrate the effectiveness of a hyper-heuristic approach to this problem domain. It is necessary to provide a good set of low-level heuristics, which are able to both intensify and diversify the search but this approach has demonstrated very encouraging results on this extremely difficult and important problem domain.     

A dual local search framework for combinatorial optimization problems with TSP application

In practice, solving realistically sized combinatorial optimization problems to optimality is often too time-consuming to be affordable; therefore, heuristics are typically implemented within most applications software. A specific category of heuristics has attracted considerable attention, namely local search methods. Most local search methods are primal in nature; that is, they start the search with a feasible solution and explore the feasible space for better feasible solutions. In this research, we propose a dual local search method and customize it to solve the traveling salesman problem (TSP); that is, a search method that starts with an infeasible solution, explores the dual space—each time reducing infeasibility, and lands in the primal space to deliver a feasible solution. The proposed design aims to replicate the designs of optimal solution methodologies in a heuristic way. To be more specific, we solve a combinatorial relaxation of a TSP formulation, design a neighborhood structure to repair such an infeasible starting solution, and improve components of intermediate dual solutions locally. Sample-based evidence along with statistically significant t-tests support the superiority of this dual design compared to its primal design counterpart.     

Diversified local search strategy under scatter search framework for the probabilistic traveling salesman problem

This paper focuses on introducing a concept of diversified local search strategy under the scatter search framework for the probabilistic traveling salesman problem (PTSP). Different combinations of three commonly used local search methods in the PTSP, i.e., 1-shift, 2-opt, and 3-opt, were used to investigate its effects. A set of numerical experiments were conducted to test the validity of the proposed strategy based on randomly generated test instances. The numerical results and the permutation test showed that the diversified local search strategy, especially by combining 1-shift and 2-opt algorithms, can most effectively solve the homogeneous and heterogeneous PTSP in most of the tested instances in comparison with the single local search strategy under scatter search framework.     

A new model and a hyper-heuristic approach for two-dimensional shelf space allocation

In this paper, we propose a two-dimensional shelf space allocation model. The second dimension stems from the height of the shelf. This results in an integer nonlinear programming model with a complex form of objective function. We propose a multiple neighborhood approach which is a hybridization of a simulated annealing algorithm with a hyper-heuristic learning mechanism. Experiments based on empirical data from both real-world and artificial instances show that the shelf space utilization and the resulting sales can be greatly improved when compared with a gradient method. Sensitivity analysis on the input parameters and the shelf space show the benefits of the proposed algorithm both in sales and in robustness.     

Evaluating selection methods on hyper-heuristic multi-objective particle swarm optimization

Multi-objective particle swarm optimization (MOPSO) is a promising meta-heuristic to solve multi-objective problems (MOPs). Previous works have shown that selecting a proper combination of leader and archiving methods, which is a challenging task, improves the search ability of the algorithm. A previous study has employed a simple hyper-heuristic to select these components, obtaining good results. In this research, an analysis is made to verify if using more advanced heuristic selection methods improves the search ability of the algorithm. Empirical studies are conducted to investigate this hypothesis. In these studies, first, four heuristic selection methods are compared: a choice function, a multi-armed bandit, a random one, and the previously proposed roulette wheel. A second study is made to identify if it is best to adapt only the leader method, the archiving method, or both simultaneously. Moreover, the influence of the interval used to replace the low-level heuristic is analyzed. At last, a final study compares the best variant to a hyper-heuristic framework that combines a Multi-Armed Bandit algorithm into the multi-objective optimization based on decomposition with dynamical resource allocation (MOEA/D-DRA) and a state-of-the-art MOPSO. Our results indicate that the resulting algorithm outperforms the hyper-heuristic framework in most of the problems investigated. Moreover, it achieves competitive results compared to a state-of-the-art MOPSO.     

A study of heuristic combinations for hyper-heuristic systems for the uncapacitated examination timetabling problem

Research in the domain of examination timetabling is moving towards developing methods that generalise well over a range of problems. This is achieved by implementing hyper-heuristic systems to find the best heuristic or heuristic combination to allocate examinations when constructing a timetable for a problem. Heuristic combinations usually take the form of a list of low-level heuristics that are applied sequentially. This study proposes an alternative representation for heuristic combinations, namely, a hierarchical combination of heuristics. Furthermore, the heuristics in each combination are applied simultaneously rather than sequentially. The study also introduces a new low-level heuristic, namely, highest cost. A set of heuristic combinations of this format have been tested on the 13 Carter benchmarks. The quality of the examination timetables induced using these combinations are comparable to, and in some cases better than, those produced by hyper-heuristic systems combining and applying heuristic combinations sequentially.     

A benchmark for cooperative coevolution

Cooperative co-evolution algorithms (CCEA) are a thriving sub-field of evolutionary computation. This class of algorithms makes it possible to exploit more efficiently the artificial Darwinist scheme, as soon as an optimisation problem can be turned into a co-evolution of interdependent sub-parts of the searched solution. Testing the efficiency of new CCEA concepts, however, it is not straightforward: while there is a rich literature of benchmarks for more traditional evolutionary techniques, the same does not hold true for this relatively new paradigm. We present a benchmark problem designed to study the behavior and performance of CCEAs, modeling a search for the optimal placement of a set of lamps inside a room. The relative complexity of the problem can be adjusted by operating on a single parameter. The fitness function is a trade-off between conflicting objectives, so the performance of an algorithm can be examined by making use of different metrics. We show how three different cooperative strategies, Parisian Evolution, Group Evolution and Allopatric Group Evolution, can be applied to the problem. Using a Classical Evolution approach as comparison, we analyse the behavior of each algorithm in detail, with respect to the size of the problem.     

Swarm intelligence-based hyper-heuristic for the vehicle routing problem with prioritized customers

The vehicle routing problem (VRP) is a combinatorial optimization management problem that seeks the optimal set of routes traversed by a vehicle to deliver products to customers. A recognized problem in this domain is to serve ‘prioritized’ customers in the shortest possible time where customers with known demands are supplied by one or several depots. This problem is known as the Vehicle Routing with Prioritized Customers (VRPC). The purpose of this work is to present and compare two artificial intelligence-based novel methods that minimize the traveling distance of vehicles when moving cargo to prioritized customers. Various studies have been conducted regarding this topic; nevertheless, up to now, few studies used the Cuckoo Search-based hyper-heuristic. This paper modifies a classical mathematical model that represents the VRPC, implements and tests an evolutionary Cuckoo Search-based hyper-heuristic, and then compares the results with those of our proposed modified version of the Clarke Wright (CW) algorithm. In this modified version, the CW algorithm serves all customers per their preassigned priorities while covering the needed working hours. The results indicate that the solution selected by the Cuckoo Search-based hyper-heuristic outperformed the modified Clarke Wright algorithm while taking into consideration the customers’ priority and demands and the vehicle capacity.

     

A modeling framework and local search solution methodology for a production-distribution problem with supplier selection and time-aggregated quantity discounts

Supplier selection with quantity discounts has been an active research problem in the literature. In this paper, we focus on a new real-world quantity discounts scheme, where suppliers are selected in the beginning of a strategic planning period (e.g., 5 years). Monthly orders are placed from the selected suppliers, but the quantity discounts are based on the aggregated annual order quantities. We incorporate this type of cost structure in a multi-period, multi-product, multi-echelon supply chain planning problem, and develop a mixed integer linear programming (MIP) model for it. Our model is highly intractable; leading commercial solvers cannot construct high quality feasible solutions for realistic instances even after multiple hours of solution time. We develop an algorithm that constructs an initial feasible solution and a large neighborhood search method that combines two customized iterative algorithms based on MIP-based local search and improves such solution. We report numerical results for a food supply chain application and show the efficiency of using our methodology in getting very high quality primal solutions quickly.