A Hidden Markov Model Approach to the Problem of Heuristic Selection in Hyper-Heuristics with a Case Study in High School Timetabling Problems.

Operations research is a well-established field that uses computational systems to support decisions in business and public life. Good solutions to operations research problems can make a large difference to the efficient running of businesses and organisations and so the field often searches for new methods to improve these solutions. The high school timetabling problem is an example of an operations research problem and is a challenging task which requires assigning events and resources to time slots subject to a set of constraints. In this article, a new sequence-based selection hyper-heuristic is presented that produces excellent results on a suite of high school timetabling problems. In this study, we present an easy-to-implement, easy-to-maintain, and effective sequence-based selection hyper-heuristic to solve high school timetabling problems using a benchmark of unified real-world instances collected from different countries. We show that with sequence-based methods, it is possible to discover new best known solutions for a number of the problems in the timetabling domain. Through this investigation, the usefulness of sequence-based selection hyper-heuristics has been demonstrated and the capability of these methods has been shown to exceed the state of the art.

Ant colony optimisation of decision tree and contingency table models for the discovery of gene-gene interactions.

In this study, ant colony optimisation (ACO) algorithm is used to derive near-optimal interactions between a number of single nucleotide polymorphisms (SNPs). This approach is used to discover small numbers of SNPs that are combined into a decision tree or contingency table model. The ACO algorithm is shown to be very robust as it is proven to be able to find results that are discriminatory from a statistical perspective with logical interactions, decision tree and contingency table models for various numbers of SNPs considered in the interaction. A large number of the SNPs discovered here have been already identified in large genome-wide association studies to be related to type II diabetes in the literature, lending additional confidence to the results.

Gene expression rule discovery and multi-objective ROC analysis using a neural-genetic hybrid.

Microarray data allows an unprecedented view of the biochemical mechanisms contained within a cell although deriving useful information from the data is still proving to be a difficult task. In this paper, a novel method based on a multi-objective genetic algorithm is investigated that evolves a near-optimal trade-off between Artificial Neural Network (ANN) classifier accuracy (sensitivity and specificity) and size (number of genes). This hybrid method is shown to work on four well-established gene expression data sets taken from the literature. The results provide evidence for the rule discovery ability of the hybrid method and indicate that the approach can return biologically intelligible as well as plausible results and requires no pre-filtering or pre-selection of genes.

Deductive sort and climbing sort: new methods for non-dominated sorting.

In recent years an increasing number of real-world many-dimensional optimisation problems have been identified across the spectrum of research fields. Many popular evolutionary algorithms use non-dominance as a measure for selecting solutions for future generations. The process of sorting populations into non-dominated fronts is usually the controlling order of computational complexity and can be expensive for large populations or for a high number of objectives. This paper presents two novel methods for non-dominated sorting: deductive sort and climbing sort. The two new methods are compared to the fast non-dominated sort of NSGA-II and the non-dominated rank sort of the omni-optimizer. The results demonstrate the improved efficiencies of the deductive sort and the reductions in comparisons that can be made when applying inferred dominance relationships defined in this paper.