Monte Carlo hyper-heuristics for examination timetabling

Automating the neighbourhood selection process in an iterative approach that uses multiple heuristics is not a trivial task. Hyper-heuristics are search methodologies that not only aim to provide a general framework for solving problem instances at different difficulty levels in a given domain, but a key goal is also to extend the level of generality so that different problems from different domains can also be solved. Indeed, a major challenge is to explore how the heuristic design process might be automated. Almost all existing iterative selection hyper-heuristics performing single point search contain two successive stages; heuristic selection and move acceptance. Different operators can be used in either of the stages. Recent studies explore ways of introducing learning mechanisms into the search process for improving the performance of hyper-heuristics. In this study, a broad empirical analysis is performed comparing Monte Carlo based hyper-heuristics for solving capacitated examination timetabling problems. One of these hyper-heuristics is an approach that overlaps two stages and presents them in a single algorithmic body. A learning heuristic selection method (L) operates in harmony with a simulated annealing move acceptance method using reheating (SA) based on some shared variables. Yet, the heuristic selection and move acceptance methods can be separated as the proposed approach respects the common selection hyper-heuristic framework. The experimental results show that simulated annealing with reheating as a hyper-heuristic move acceptance method has significant potential. On the other hand, the learning hyper-heuristic using simulated annealing with reheating move acceptance (L?CSA) performs poorly due to certain weaknesses, such as the choice of rewarding mechanism and the evaluation of utility values for heuristic selection as compared to some other hyper-heuristics in examination timetabling. Trials with other heuristic selection methods confirm that the best alternative for the simulated annealing with reheating move acceptance for examination timetabling is a previously proposed strategy known as the choice function.     

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 competitive and cooperative co-evolutionary approach to multi-objective particle swarm optimization algorithm design

Multi-objective particle swarm optimization (MOPSO) is an optimization technique inspired by bird flocking, which has been steadily gaining attention from the research community because of its high convergence speed. On the other hand, in the face of increasing complexity and dimensionality of today’s application coupled with its tendency of premature convergence due to the high convergence speeds, there is a need to improve the efficiency and effectiveness of MOPSO. In this paper a competitive and cooperative co-evolutionary approach is adapted for multi-objective particle swarm optimization algorithm design, which appears to have considerable potential for solving complex optimization problems by explicitly modeling the co-evolution of competing and cooperating species. The competitive and cooperative co-evolution model helps to produce the reasonable problem decompositions by exploiting any correlation, interdependency between components of the problem. The proposed competitive and cooperative co-evolutionary multi-objective particle swarm optimization algorithm (CCPSO) is validated through comparisons with existing state-of-the-art multi-objective algorithms using established benchmarks and metrics. Simulation results demonstrated that CCPSO shows competitive, if not better, performance as compared to the other algorithms.     

A memetic algorithm for job shop scheduling using a critical-path-based local search heuristic

In this article, a new memetic algorithm has been proposed to solve job shop scheduling problems (JSSPs). The proposed method is a genetic-algorithm-based approach combined with a local search heuristic. The proposed local search heuristic is based on critical operations. It removes the critical operations and reassigns them to a new position to improve the fitness value of the schedule. Moreover, in this article, a new fitness function is introduced for JSSPs. The new fitness function called priority-based fitness function is defined in three priority levels to improve the selection procedure. To show the generality of our proposed method, we apply it to three different types of job scheduling problems including classical, flexible and multi-objective flexible JSSPs. The experiment results show the efficiency of the proposed fitness function. In addition, the results show that incorporating local search not only offers better solutions but also improves the convergence rate. Compared to the state-of-the-art algorithms, the proposed method outperforms the existing methods in classical JSSPs and offers competitive solutions in other types of scheduling problems.     

A cooperative hyper-heuristic search framework

In this paper, we aim to investigate the role of cooperation between low level heuristics within a hyper-heuristic framework. Since different low level heuristics have different strengths and weaknesses, we believe that cooperation can allow the strengths of one low level heuristic to compensate for the weaknesses of another. We propose an agent-based cooperative hyper-heuristic framework composed of a population of heuristic agents and a cooperative hyper-heuristic agent. The heuristic agents perform a local search through the same solution space starting from the same or different initial solution, and using different low level heuristics. The heuristic agents cooperate synchronously or asynchronously through the cooperative hyper-heuristic agent by exchanging the solutions of the low level heuristics. The cooperative hyper-heuristic agent makes use of a pool of the solutions of the low level heuristics for the overall selection of the low level heuristics and the exchange of solutions. Computational experiments carried out on a set of permutation flow shop benchmark instances illustrated the superior performance of the cooperative hyper-heuristic framework over sequential hyper-heuristics. Also, the comparative study of synchronous and asynchronous cooperative hyper-heuristics showed that asynchronous cooperative hyper-heuristics outperformed the synchronous ones.     

Particle swarm with equilibrium strategy of selection for multi-objective optimization

A new ranking scheme based on equilibrium strategy of selection is proposed for multi-objective particle swarm optimization (MOPSO), and the preference ordering is used to identify the “best compromise” in the ranking stage. This scheme increases the selective pressure, especially when the number of objectives is very large. The proposed algorithm has been compared with other multi-objective evolutionary algorithms (MOEAs). The experimental results indicate that our algorithm produces better convergence performance.     

A hybrid multi-objective artificial bee colony algorithm for burdening optimization of copper strip production

To achieve burdening process optimization of copper strips effectively, a nonlinear constrained multi-objective model is established on the principle of the actual burdening. The problem is formulated with two objectives of minimizing the total cost of raw materials and maximizing the amount of waste material thrown into melting furnace. In this paper, a novel approach called “hybrid multi-objective artificial bee colony” (HMOABC) to solve this model is proposed. The HMOABC algorithm is new swarm intelligence based multi-objective optimization technique inspired by the intelligent foraging behavior of honey bees, summation of normalized objective values and diversified selection (SNOV-DS) and nondominated sorting approach. Two test examples were studied and the performance of HMOABC is evaluated in comparison with other nature inspired techniques which includes nondominated sorting genetic algorithm II (NSGAII) and multi-objective particle swarm optimization (MOPSO). The numerical results demonstrate HMOABC approach is a powerful search and optimization technique for burdening optimization of copper strips.     

A multi-objective memetic algorithm based on decomposition for big optimization problems

When solving multi-objective optimization problems (MOPs) with big data, traditional multi-objective evolutionary algorithms (MOEAs) meet challenges because they demand high computational costs that cannot satisfy the demands of online data processing involving optimization. The gradient heuristic optimization methods show great potential in solving large scale numerical optimization problems with acceptable computational costs. However, some intrinsic limitations make them unsuitable for searching for the Pareto fronts. It is believed that the combination of these two types of methods can deal with big MOPs with less computational cost. The main contribution of this paper is that a multi-objective memetic algorithm based on decomposition for big optimization problems (MOMA/D-BigOpt) is proposed and a gradient-based local search operator is embedded in MOMA/D-BigOpt. In the experiments, MOMA/D-BigOpt is tested on the multi-objective big optimization problems with thousands of variables. We also combine the local search operator with other widely used MOEAs to verify its effectiveness. The experimental results show that the proposed algorithm outperforms MOEAs without the gradient heuristic local search operator.     

Coalition-based metaheuristic: a self-adaptive metaheuristic using reinforcement learning and mimetism

We present a self-adaptive and distributed metaheuristic called Coalition-Based Metaheuristic (CBM). This method is based on the Agent Metaheuristic Framework (AMF) and hyper-heuristic approach. In CBM, several agents, grouped in a coalition, concurrently explore the search space of a given problem instance. Each agent modifies a solution with a set of operators. The selection of these operators is determined by heuristic rules dynamically adapted by individual and collective learning mechanisms. The intention of this study is to exploit AMF and hyper-heuristic approaches to conceive an efficient, flexible and modular metaheuristic. AMF provides a generic model of metaheuristic that encourages modularity, and hyper-heuristic approach gives some guidelines to design flexible search methods. The performance of CBM is assessed by computational experiments on the vehicle routing problem.     

A stochastic local search algorithm with adaptive acceptance for high-school timetabling

Automating high school timetabling is a challenging task. This problem is a well known hard computational problem which has been of interest to practitioners as well as researchers. High schools need to timetable their regular activities once per year, or even more frequently. The exact solvers might fail to find a solution for a given instance of the problem. A selection hyper-heuristic can be defined as an easy-to-implement, easy-to-maintain and effective ‘heuristic to choose heuristics’ to solve such computationally hard problems. This paper describes the approach of the team hyper-heuristic search strategies and timetabling (HySST) to high school timetabling which competed in all three rounds of the third international timetabling competition. HySST generated the best new solutions for three given instances in Round 1 and gained the second place in Rounds 2 and 3. It achieved this by using a fairly standard stochastic search method but significantly enhanced by a selection hyper-heuristic with an adaptive acceptance mechanism.     

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.     

FEMOEA: a fast and efficient multi-objective evolutionary algorithm

A multi-objective evolutionary algorithm which can be applied to many nonlinear multi-objective optimization problems is proposed. Its aim is to quickly obtain a fixed size Pareto-front approximation. It adapts ideas from different multi-objective evolutionary algorithms, but also incorporates new devices. In particular, the search in the feasible region is carried out on promising areas (hyperspheres) determined by a radius value, which decreases as the optimization procedure evolves. This mechanism helps to maintain a balance between exploration and exploitation of the search space. Additionally, a new local search method which accelerates the convergence of the population towards the Pareto-front, has been incorporated. It is an extension of the local optimizer SASS and improves a given solution along a search direction (no gradient information is used). Finally, a termination criterion has also been proposed, which stops the algorithm if the distances between the Pareto-front approximations provided by the algorithm in three consecutive iterations are smaller than a given tolerance. To know how far two of those sets are from each other, a modification of the well-known Hausdorff distance is proposed. In order to analyze the algorithm performance, it has been compared to the reference algorithms NSGA-II and SPEA2 and the state-of-the-art algorithms MOEA/D and SMS-EMOA. Several quality indicators have been considered, namely, hypervolume, average distance, additive epsilon indicator, spread and spacing. According to the computational tests performed, the new algorithm, named FEMOEA, outperforms the other algorithms.     

An efficient multi-objective PSO algorithm assisted by Kriging metamodel for expensive black-box problems

The huge computational overhead is the main challenge in the application of community based optimization methods, such as multi-objective particle swarm optimization and multi-objective genetic algorithm, to deal with the multi-objective optimization involving costly simulations. This paper proposes a Kriging metamodel assisted multi-objective particle swarm optimization method to solve this kind of expensively black-box multi-objective optimization problems. On the basis of crowding distance based multi-objective particle swarm optimization algorithm, the new proposed method constructs Kriging metamodel for each expensive objective function adaptively, and then the non-dominated solutions of the metamodels are utilized to guide the update of particle population. To reduce the computational cost, the generalized expected improvements of each particle predicted by metamodels are presented to determine which particles need to perform actual function evaluations. The suggested method is tested on 12 benchmark functions and compared with the original crowding distance based multi-objective particle swarm optimization algorithm and non-dominated sorting genetic algorithm-II algorithm. The test results show that the application of Kriging metamodel improves the search ability and reduces the number of evaluations. Additionally, the new proposed method is applied to the optimal design of a cycloid gear pump and achieves desirable results.     

A new orthogonal evolutionary algorithm based on decomposition for multi-objective optimization

The diversity of solutions is very important for multi-objective evolutionary algorithms to deal with multi-objective optimization problems (MOPs). In order to achieve the goal, a new orthogonal evolutionary algorithm based on objective space decomposition (OEA/D) is proposed in this paper. To be specific, the objective space of an MOP is firstly decomposed into a set of sub-regions via a set of direction vectors, and OEA/D maintains the diversity of solutions by making each sub-region have a solution to the maximum extent. Also, the quantization orthogonal crossover (QOX) is used to enhance the search ability of OEA/D. Experimental studies have been conducted to compare this proposed algorithm with classic MOEA/D, NSGAII, NICA and D2MOPSO. Simulation results on six multi-objective benchmark functions show that the proposed algorithm is able to obtain better diversity and more evenly distributed Pareto fronts than other four algorithms.     

A Constraint-Based Method for Project Scheduling with Time Windows

This paper presents a heuristic algorithm for solving RCPSP/max, the resource constrained project scheduling problem with generalized precedence relations. The algorithm relies, at its core, on a constraint satisfaction problem solving (CSP) search procedure, which generates a consistent set of activity start times by incrementally removing resource conflicts from an otherwise temporally feasible solution. Key to the effectiveness of the CSP search procedure is its heuristic strategy for conflict selection. A conflict sampling method biased toward selection of minimal conflict sets that involve activities with higher-capacity requests is introduced, and coupled with a non-deterministic choice heuristic to guide the base conflict resolution process. This CSP search is then embedded within a larger iterative-sampling search framework to broaden search space coverage and promote solution optimization. The efficacy of the overall heuristic algorithm is demonstrated empirically on a large set of previously studied RCPSP/max benchmark problems.     

PSOHS: an efficient two-stage approach for data clustering

Cluster analysis is an important task in data mining and refers to group a set of objects such that the similarities among objects within the same group are maximal while similarities among objects from different groups are minimal. The particle swarm optimization algorithm (PSO) is one of the famous metaheuristic optimization algorithms, which has been successfully applied to solve the clustering problem. However, it has two major shortcomings. The PSO algorithm converges rapidly during the initial stages of the search process, but near global optimum, the convergence speed will become very slow. Moreover, it may get trapped in local optimum if the global best and local best values are equal to the particle’s position over a certain number of iterations. In this paper we hybridized the PSO with a heuristic search algorithm to overcome the shortcomings of the PSO algorithm. In the proposed algorithm, called PSOHS, the particle swarm optimization is used to produce an initial solution to the clustering problem and then a heuristic search algorithm is applied to improve the quality of this solution by searching around it. The superiority of the proposed PSOHS clustering method, as compared to other popular methods for clustering problem is established for seven benchmark and real datasets including Iris, Wine, Crude Oil, Cancer, CMC, Glass and Vowel.     

Heuristic approaches to determine base-stock levels in a serial supply chain with a single objective and with multiple objectives

This paper deals with the problem of determination of installation base-stock levels in a serial supply chain. The problem is treated first as a single-objective inventory-cost optimization problem, and subsequently as a multi-objective optimization problem by considering two cost components, namely, holding costs and shortage costs. Variants of genetic algorithms are proposed to determine the best base-stock levels in the single-objective case. All variants, especially random-key gene-wise genetic algorithm (RKGGA), show an excellent performance, in terms of convergence to the best base-stock levels across a variety of supply chain settings, with minimum computational effort. Heuristics to obtain base-stock levels are proposed, and heuristic solutions are introduced in the initial population of the RKGGA to expedite the convergence of the genetic search process. To deal with the multi-objective supply-chain inventory optimization problem, a simple multi-objective genetic algorithm is proposed to obtain a set of non-dominated solutions.     

Evolving hyper-heuristics for the uncapacitated examination timetabling problem

This paper reports on the use of an evolutionary algorithm (EA) to search a space of heuristic combinations for the uncapacitated examination timetabling problem. The representation used by an EA has an effect on the difficulty of the search and hence the overall success of the system. The paper examines three different representations of heuristic combinations for this problem and compares their performance on a set of benchmark problems for the uncapacitated examination timetabling problem. The study has revealed that certain representations do result in a better performance and generalization of the hyper-heuristic. An EA-based hyper-heuristic combining the use of all three representations (CEA) was implemented and found to generalize better than the EA using each of the representations separately.     

A hybrid iterated local search heuristic for the maximum weight independent set problem

This paper presents a hybrid iterated local search (ILS) algorithm for the maximum weight independent set (MWIS) problem, a generalization of the classical maximum independent set problem. Two efficient neighborhood structures are proposed and they are explored using the variable neighborhood descent procedure. Moreover, we devise a perturbation mechanism that dynamically adjusts the balance between intensification and diversification during the search. The proposed algorithm was tested on two well-known benchmarks (DIMACS-W and BHOSLIB-W) and the results obtained were compared with those found by state-of-the-art heuristics and exact methods. Our heuristic outperforms the best-known heuristic for the MWIS as well as the best heuristics for the maximum weight clique problem. The results also show that the hybrid ILS was capable of finding all known optimal solutions in milliseconds.     

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.