Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems

In this paper, we present a random iterative graph based hyper-heuristic to produce a collection of heuristic sequences to construct solutions of different quality. These heuristic sequences can be seen as dynamic hybridisations of different graph colouring heuristics that construct solutions step by step. Based on these sequences, we statistically analyse the way in which graph colouring heuristics are automatically hybridised. This, to our knowledge, represents a new direction in hyper-heuristic research. It is observed that spending the search effort on hybridising Largest Weighted Degree with Saturation Degree at the early stage of solution construction tends to generate high quality solutions. Based on these observations, an iterative hybrid approach is developed to adaptively hybridise these two graph colouring heuristics at different stages of solution construction. The overall aim here is to automate the heuristic design process, which draws upon an emerging research theme on developing computer methods to design and adapt heuristics automatically. Experimental results on benchmark exam timetabling and graph colouring problems demonstrate the effectiveness and generality of this adaptive hybrid approach compared with previous methods on automatically generating and adapting heuristics. Indeed, we also show that the approach is competitive with the state of the art human produced methods.

The Combination of Multiple Classifiers Using an Evidential Reasoning Approach

In many domains when we have several competing classifiers available we want to synthesize them or some of them to get a more accurate classifier by a combination function. In this paper we propose a ‘class-indifferent’ method for combining classifier decisions represented by evidential structures called triplet and quartet, using Dempster's rule of combination. This method is unique in that it distinguishes important elements from the trivial ones in representing classifier decisions, makes use of more information than others in calculating the support for class labels and provides a practical way to apply the theoretically appealing Dempster–Shafer theory of evidence to the problem of ensemble learning. We present a formalism for modelling classifier decisions as triplet mass functions and we establish a range of formulae for combining these mass functions in order to arrive at a consensus decision. In addition we carry out a comparative study with the alternatives of simplet and dichotomous structure and also compare two combination methods, Dempster's rule and majority voting, over the UCI benchmark data, to demonstrate the advantage our approach offers. (A continuation of the work in this area that was published in IEEE Trans on KDE, and conferences)

An extended framework for evidential reasoning systems.

Use of the Dempster-Shafer (D-S) theory of evidence to deal with uncertainty in knowledge-based systems has been widely addressed. Several AI implementations have been undertaken based on the D-S theory of evidence or the extended theory. But the representation of uncertain relationships between evidence and hypothesis groups (heuristic knowledge) is still a major problem. This paper presents an approach to representing such knowledge, in which Yen’s probabilistic multi-set mappings have been extended to evidential mappings, and Shafer’s partition technique is used to get the mass function in a complex evidence space. Then, a new graphic method for describing the knowledge is introduced which is an extension of the graphic model by Lowrance et al. Finally, an extended framework for evidential reasoning systems is specified.

Automated detection and tracking of solar magnetic bright points

Magnetic bright points (MBPs) in the internetwork are among the smallest objects in the solar photosphere and appear bright against the ambient environment. An algorithm is presented that can be used for the automated detection of the MBPs in the spatial and temporal domains. The algorithm works by mapping the lanes through intensity thresholding. A compass search, combined with a study of the intensity gradient across the detected objects, allows the disentanglement of MBPs from bright pixels within the granules. Object growing is implemented to account for any pixels that might have been removed when mapping the lanes. The images are stabilized by locating long-lived objects that may have been missed due to variable light levels and seeing quality. Tests of the algorithm, employing data taken with the Swedish Solar Telescope, reveal that approximate to 90 per cent of MBPs within a 75 x 75 arcsec(2) field of view are detected.

Inductive reasoning and semantic cognition: More than just different names for the same thing?

We describe evidence that certain inductive phenomena are associated with IQ, that different inductive phenomena emerge at different ages, and that the effects of causal knowledge on induction are decreased under conditions of memory load. On the basis of this evidence we argue that there is more to inductive reasoning than semantic cognition.

Deciding between theories of how reasoning develops is hard

Although Sloutsky agrees with our interpretation of our data, he argues that the totality of the evidence supports his claim that children make inductive generalisations on the basis of similarity. Here we take issue with his characterisation of the alternative hypotheses in his informal analysis of the data, and suggest that a thorough Bayesian analysis, although practically very difficult, is likely to result in a more finely balanced outcome than he suggests. (c) 2008 Elsevier B.V. All rights reserved.

Rarity, pseudodiagnosticity and Bayesian reasoning

Three experiments investigated the effect of rarity on people's selection and interpretation of data in a variant of the pseudodiagnosticity task. For familiar (Experiment 1) but not for arbitrary (Experiment 3) materials, participants were more likely to select evidence so as to complete a likelihood ratio when the initial evidence they received was a single likelihood concerning a rare feature. This rarity effect with familiar materials was replicated in Experiment 2 where it was shown that participants were relatively insensitive to explicit manipulations of the likely diagnosticity of rare evidence. In contrast to the effects for data selection, there was an effect of rarity on confidence ratings after receipt of a single likelihood for arbitrary but not for familiar materials. It is suggested that selecting diagnostic evidence necessitates explicit consideration of the alternative hypothesis and that consideration of the possible consequences of the evidence for the alternative weakens the rarity effect in confidence ratings. Paradoxically, although rarity effects in evidence selection and confidence ratings are in the spirit of Bayesian reasoning, the effect on confidence ratings appears to rely on participants thinking less about the alternative hypothesis.

Searching and planning: Young children's reasoning about past and future event sequences

Six experiments examined children's ability to make inferences using temporal order information. Children completed versions of a task involving a toy zoo; one version required reasoning about past events (search task) and the other required reasoning about future events (planning task). Children younger than 5 years failed both the search and the planning tasks, whereas 5-year-olds passed both (Experiments 1 and 2). However, when the number of events in the sequence was reduced (Experiment 3), 4-year-olds were successful on the search task but not the planning task. Planning difficulties persisted even when relevant cues were provided (Experiments 4 and 5). Experiment 6 showed that improved performance on the search task found in Experiment 3 was not due to the removal of response ambiguity.