A hybrid metaheuristic approach to the university course timetabling problem

This paper describes the development of a novel metaheuristic that combines an electromagnetic-like mechanism (EM) and the great deluge algorithm (GD) for the University course timetabling problem. This well-known timetabling problem assigns lectures to specific numbers of timeslots and rooms maximizing the overall quality of the timetable while taking various constraints into account. EM is a population-based stochastic global optimization algorithm that is based on the theory of physics, simulating attraction and repulsion of sample points in moving toward optimality. GD is a local search procedure that allows worse solutions to be accepted based on some given upper boundary or ‘level’. In this paper, the dynamic force calculated from the attraction-repulsion mechanism is used as a decreasing rate to update the ‘level’ within the search process. The proposed method has been applied to a range of benchmark university course timetabling test problems from the literature. Moreover, the viability of the method has been tested by comparing its results with other reported results from the literature, demonstrating that the method is able to produce improved solutions to those currently published. We believe this is due to the combination of both approaches and the ability of the resultant algorithm to converge all solutions at every search process.

Dynamic evolution of the genetic search region through fuzzy coding

A technique for automatic exploration of the genetic search region through fuzzy coding (Sharma and Irwin, 2003) has been proposed. Fuzzy coding (FC) provides the value of a variable on the basis of the optimum number of selected fuzzy sets and their effectiveness in terms of degree-of-membership. It is an indirect encoding method and has been shown to perform better than other conventional binary, Gray and floating-point encoding methods. However, the static range of the membership functions is a major problem in fuzzy coding, resulting in longer times to arrive at an optimum solution in large or complicated search spaces. This paper proposes a new algorithm, called fuzzy coding with a dynamic range (FCDR), which dynamically allocates the range of the variables to evolve an effective search region, thereby achieving faster convergence. Results are presented for two benchmark optimisation problems, and also for a case study involving neural identification of a highly non-linear pH neutralisation process from experimental data. It is shown that dynamic exploration of the genetic search region is effective for parameter optimisation in problems where the search space is complicated.

A New Gradient Descent Approach for Local Learning of Fuzzy Neural Models

The majority of reported learning methods for Takagi-Sugeno-Kang fuzzy neural models to date mainly focus on the improvement of their accuracy. However, one of the key design requirements in building an interpretable fuzzy model is that each obtained rule consequent must match well with the system local behaviour when all the rules are aggregated to produce the overall system output. This is one of the distinctive characteristics from black-box models such as neural networks. Therefore, how to find a desirable set of fuzzy partitions and, hence, to identify the corresponding consequent models which can be directly explained in terms of system behaviour presents a critical step in fuzzy neural modelling. In this paper, a new learning approach considering both nonlinear parameters in the rule premises and linear parameters in the rule consequents is proposed. Unlike the conventional two-stage optimization procedure widely practised in the field where the two sets of parameters are optimized separately, the consequent parameters are transformed into a dependent set on the premise parameters, thereby enabling the introduction of a new integrated gradient descent learning approach. A new Jacobian matrix is thus proposed and efficiently computed to achieve a more accurate approximation of the cost function by using the second-order Levenberg-Marquardt optimization method. Several other interpretability issues about the fuzzy neural model are also discussed and integrated into this new learning approach. Numerical examples are presented to illustrate the resultant structure of the fuzzy neural models and the effectiveness of the proposed new algorithm, and compared with the results from some well-known methods.

Possibilistic Information Fusion Using Maximal Coherent Subsets

When multiple sources provide information about the same unknown quantity, their fusion into a synthetic interpretable message is often a tedious problem, especially when sources are conicting. In this paper, we propose to use possibility theory and the notion of maximal coherent subsets, often used in logic-based representations, to build a fuzzy belief structure that will be instrumental both for extracting useful information about various features of the information conveyed by the sources and for compressing this information into a unique possibility distribution. Extensions and properties of the basic fusion rule are also studied.

A graded BDI agent model to represent and reason about preferences

In this research note, we introduce a graded BDI agent development framework, g-BDI for short, that allows to build agents as multi-context systems that reason about three fundamental and graded mental attitudes (i.e. beliefs, desires and intentions). We propose a sound and complete logical framework for them and some logical extensions to accommodate slightly different views on desires. © 2011 Elsevier B.V. All rights reserved.

A sequential algorithm for sparse support vector classifiers

Support vector machines (SVMs), though accurate, are not preferred in applications requiring high classification speed or when deployed in systems of limited computational resources, due to the large number of support vectors involved in the model. To overcome this problem we have devised a primal SVM method with the following properties: (1) it solves for the SVM representation without the need to invoke the representer theorem, (2) forward and backward selections are combined to approach the final globally optimal solution, and (3) a criterion is introduced for identification of support vectors leading to a much reduced support vector set. In addition to introducing this method the paper analyzes the complexity of the algorithm and presents test results on three public benchmark problems and a human activity recognition application. These applications demonstrate the effectiveness and efficiency of the proposed algorithm.


--------------------------------------------------------------------------------

A defeasible reasoning model of inductive concept learning from examples and communication

This paper introduces a logical model of inductive generalization, and specifically of the machine learning task of inductive concept learning (ICL). We argue that some inductive processes, like ICL, can be seen as a form of defeasible reasoning. We define a consequence relation characterizing which hypotheses can be induced from given sets of examples, and study its properties, showing they correspond to a rather well-behaved non-monotonic logic. We will also show that with the addition of a preference relation on inductive theories we can characterize the inductive bias of ICL algorithms. The second part of the paper shows how this logical characterization of inductive generalization can be integrated with another form of non-monotonic reasoning (argumentation), to define a model of multiagent ICL. This integration allows two or more agents to learn, in a consistent way, both from induction and from arguments used in the communication between them. We show that the inductive theories achieved by multiagent induction plus argumentation are sound, i.e. they are precisely the same as the inductive theories built by a single agent with all data. © 2012 Elsevier B.V.

Constraint rule-based programming of norms for electronic institutions

Norms constitute a powerful coordination mechanism among heterogeneous agents. In this paper, we propose a rule language to specify and explicitly manage the normative positions of agents (permissions, prohibitions and obligations), with which distinct deontic notions and their relationships can be captured. Our rule-based formalism includes constraints for more expressiveness and precision and allows to supplement (and implement) electronic institutions with norms. We also show how some normative aspects are given computational interpretation. © 2008 Springer Science+Business Media, LLC.

Lorentz TEM investigation of the switching behavior in artificial spin ice building blocks

Frustration – the inability to simultaneously satisfy all interactions – occurs in a wide range of systems including neural networks, water ice and magnetic systems. An example of the latter is the so called spin-ice in pyrochlore materials [1] which have attracted a lot of interest not least due to the emergence of magnetic monopole defects when the ‘ice rules’ governing the local ordering breaks down [2]. However it is not possible to directly measure the frustrated property – the direction of the magnetic moments – in such spin ice systems with current experimental techniques. This problem can be solved by instead studying artificial spin-ice systems where the molecular magnetic moments are replaced by nanoscale ferromagnetic islands [3-8]. Two different arrangements of the ferromagnetic islands have been shown to exhibit spin ice behaviour: a square lattice maintaining four moments at each vertex [3,8] and the Kagome lattice which has only three moments per vertex but equivalent interactions between them [4-7]. Magnetic monopole defects have been observed in both types of lattices [7-8]. One of the challenges when studying these artificial spin-ice systems is that it is difficult to arrive at the fully demagnetised ground-state [6-8].
Here we present a study of the switching behaviour of building blocks of the Kagome lattice influenced by the termination of the lattice. Ferromagnetic islands of nominal size 1000 nm by 100 nm were fabricated in five island blocks using electron-beam lithography and lift-off techniques of evaporated 18 nm Permalloy (Ni80Fe20) films. Each block consists of a central island with four arms terminated by a different number and placement of ‘injection pads’, see Figure 1. The islands are single domain and magnetised along their long axis. The structures were grown on a 50 nm thick electron transparent silicon nitride membrane to allow TEM observation, which was back-coated with a 5 nm film of Au to prevent charge build-up during the TEM experiments.
To study the switching behaviour the sample was subjected to a magnetic field strong enough to magnetise all the blocks in one direction, see Figure 1. Each block obeys the Kagome lattice ‘ice-rules’ of “2-in, 1-out” or “1-in, 2-out” in this fully magnetised state. Fresnel mode Lorentz TEM images of the sample were then recorded as a magnetic field of increasing magnitude was applied in the opposite direction. While the Fresnel mode is normally used to image magnetic domain structures [9] for these types of samples it is possible to deduce the direction of the magnetisation from the Lorentz contrast [5]. All images were recorded at the same over-focus judged to give good Lorentz contrast.
The magnetisation was found to switch at different magnitudes of the applied field for nominally identical blocks. However, trends could still be identified: all the blocks with any injection pads, regardless of placement and number, switched the direction of the magnetisation of their central island at significantly smaller magnitudes of the applied magnetic field than the blocks without injection pads. It can therefore be concluded that the addition of an injection pad lowers the energy barrier to switching the connected island, acting as a nucleation site for monopole defects. In these five island blocks the defects immediately propagate through to the other side, but in a larger lattice the monopoles could potentially become trapped at a vertex and observed [10].
References

[1] M J Harris et al, Phys Rev Lett 79 (1997) p.2554.
[2] C Castelnovo, R Moessner and S L Sondhi, Nature 451 (2008) p. 42.
[3] R F Wang et al, Nature 439 (2006) 303.
[4] M Tanaka et al, Phys Rev B 73 (2006) 052411.
[5] Y Qi, T Brintlinger and J Cumings, Phys Rev B 77 (2008) 094418.
[6] E Mengotti et al, Phys Rev B 78 (2008) 144402.
[7] S Ladak et al, Nature Phys 6 (2010) 359.
[8] C Phatak et al, Phys Rev B 83 (2011) 174431.
[9] J N Chapman, J Phys D 17 (1984) 623.
[10] The authors gratefully acknowledge funding from the EPSRC under grant number EP/D063329/1.

Robust Multimodal Person Identification With Limited Training Data

This paper presents a novel method of audio-visual feature-level fusion for person identification where both the speech and facial modalities may be corrupted, and there is a lack of prior knowledge about the corruption. Furthermore, we assume there are limited amount of training data for each modality (e.g., a short training speech segment and a single training facial image for each person). A new multimodal feature representation and a modified cosine similarity are introduced to combine and compare bimodal features with limited training data, as well as vastly differing data rates and feature sizes. Optimal feature selection and multicondition training are used to reduce the mismatch between training and testing, thereby making the system robust to unknown bimodal corruption. Experiments have been carried out on a bimodal dataset created from the SPIDRE speaker recognition database and AR face recognition database with variable noise corruption of speech and occlusion in the face images. The system's speaker identification performance on the SPIDRE database, and facial identification performance on the AR database, is comparable with the literature. Combining both modalities using the new method of multimodal fusion leads to significantly improved accuracy over the unimodal systems, even when both modalities have been corrupted. The new method also shows improved identification accuracy compared with the bimodal systems based on multicondition model training or missing-feature decoding alone.

Dense subgraphs on dynamic networks

In distributed networks, it is often useful for the nodes to be aware of dense subgraphs, e.g., such a dense subgraph could reveal dense substructures in otherwise sparse graphs (e.g. the World Wide Web or social networks); these might reveal community clusters or dense regions for possibly maintaining good communication infrastructure. In this work, we address the problem of self-awareness of nodes in a dynamic network with regards to graph density, i.e., we give distributed algorithms for maintaining dense subgraphs that the member nodes are aware of. The only knowledge that the nodes need is that of the dynamic diameter D, i.e., the maximum number of rounds it takes for a message to traverse the dynamic network. For our work, we consider a model where the number of nodes are fixed, but a powerful adversary can add or remove a limited number of edges from the network at each time step. The communication is by broadcast only and follows the CONGEST model. Our algorithms are continuously executed on the network, and at any time (after some initialization) each node will be aware if it is part (or not) of a particular dense subgraph. We give algorithms that (2 + e)-approximate the densest subgraph and (3 + e)-approximate the at-least-k-densest subgraph (for a given parameter k). Our algorithms work for a wide range of parameter values and run in O(D log n) time. Further, a special case of our results also gives the first fully decentralized approximation algorithms for densest and at-least-k-densest subgraph problems for static distributed graphs. © 2012 Springer-Verlag.

A network architectural style for real-time systems: NaSr

Inter-component communication has always been of great importance in the design of software architectures and connectors have been considered as first-class entities in many approaches [1][2][3]. We present a novel architectural style that is derived from the well-established domain of computer networks. The style adopts the inter-component communication protocol in a novel way that allows large scale software reuse. It mainly targets real-time, distributed, concurrent, and heterogeneous systems.