Skip to main page content - your browser does not fully support our CSS, or is text-only.

Computing Science Seminars, Spring 2015

The Division of Computing Science and Mathematics presents the following seminars. Unless otherwise stated, seminars will take place in Room 4B108 of the Cottrell Building, University of Stirling from 15.00 to 16.00 on Friday afternoons during semester time. For instructions on how to get to the University, please look at the following routes.

If you would like to give a seminar to the department in future or if you need more information,  
please contact the seminar organiser,  .

Spring 2015

Date Presenter Title/Abstract
Tuesday
13 Jan
Prof Darrell Whitley
Department Chair
Computer Science Department
Colorado State University, US
SICSA
Distinguished Visiting Fellow
Blind No More: Constant Time Non-Random Improving Moves and Exponentially Powerful Recombination. For decades, most local search algorithms have relied on enumerating a neighborhood of solutions in order to locate improving moves.   Similarly, evolutionary algorithms have also long relied on random mutation and random recombination operators to generate new candidate solutions.

For optimization problems over binary strings where variable interactions are bounded by a constant k (i.e k-bounded  pseudo-Boolean optimization problems) such as MAX-kSAT and NK-Landscapes, we have proved that it is possible to exactly identify improving bit flip moves in constant  time under reasonable assumptions.  This result can be generalized:  we can also identify all improving moves within a Hamming radius r in constant  time.   We currently have results for string-length N = 12,000 and r = 7 for NK-landscapes, where the Hamming Ball neighborhood has 1 billion neighbors.  This means that we no longer need to enumerate neighborhoods for local search, or to use random mutations to locate improving moves.

We can also prove that there exists deterministic forms of recombination that are also guaranteed to return the best possible offspring under reasonable assumptions.   Given two parent solutions, the method identifies p subgraphs that partition the variable interactions of the parents.    Given p subgraphs, recombination can be done in O(n) time such that crossover returns the best solutions out of 2^p offspring.     This form of   “Partition Crossover” has been developed for both  k-bounded pseudo-Boolean optimization problems as well as for the Traveling Salesman Problem.   Empirical results suggest that Partition Crossover is highly effective at accelerating search.
Friday
6 Feb
Dr Simon Martin
Research Assistant
Computing Science and  
Mathematics
University of Stirling
A Multi-Agent Based Cooperative Approach to Scheduling and Routing. In this talk, we propose a general agent-based distributed framework where each agent implementing a different meta-heuristic/local search combination. Moreover, an agent continuously adapts itself during the search process using a direct cooperation protocol based on reinforcement learning and pattern matching. Good patterns that make up improving solutions are identified and shared by the agents. This agent-based system aims to provide a modular flexible framework to deal with a variety of different problem domains. We have evaluated the performance of the system on two sets of well known benchmarks for Permutation Flow-shop Scheduling and Capacitated Vehicle Routing respectively. The results show the success of the approach yielding  three new best known results of the Capacitated Vehicle Routing benchmarks while, the results for Permutation Flow-shop Scheduling are commensurate with the best known values for all the benchmarks tested.  The system has also been applied to the problem of Fairness in Nurse Rostering.
Friday
13 Feb
Dr Leandro L. Minku
Research Fellow II - CERCIA, School of Computer Science, The University of Birmingham
Understanding and Improving Search-Based Software Project Scheduling. The Software Project Scheduling Problem (SPSP) is concerned with finding optimal allocations of employees to tasks in a software project so as to minimise its cost and completion time. When the software project is large, the space of possible allocations is enormous, making this a very challenging problem for software engineers to solve manually. Therefore, existing work has applied Evolutionary Algorithms (EAs) to find such allocations automatically. However, it is not yet well understood how different EA design choices could affect their performance for this problem, and what problem features make the SPSP hard for EAs. This talk aims at (1) providing a better understanding of what makes SPSP easy/hard for EAs and (2) presenting an improved design to overcome specific problems of existing EAs for the SPSP. The new design includes a mechanism to avoid certain types of infeasible solutions, a fitness function that requires fewer pre-defined parameters and provides a clear gradient towards feasible solutions, and an improved representation and mutation operator. A thorough experimental analysis shows that the new design can considerably improve not only the quality of the solutions, but also their robustness to different problem features. I will finish this talk by presenting some very recent results on improving EAs further to address previously neglected SPSP challenges.
Friday 
20 Feb
Mid Semester Break
Mid Semester Break
Friday
27 Feb
Mid Semester Break Mid Semester Break
Friday
6 March
Dr Phil Bartie
Lecturer Geospatial Technology
Biological and
Environmental Sciences
University of Stirling
Spacebook: Talking Maps. SpaceBook (EU FP7) is a speech-driven, hands-free, eyes-free device for pedestrian navigation and exploration.  The user interacts with the smartphone application using only speech as they walk around Edinburgh learning about the city and its history. The system relies on using spatial datasets to better model the user’s context and thereby enable more natural human-computer interactions. For example SpaceBook can model the visibility of city objects in real time, using a digital surface model sourced from LiDAR, so that the user may ask questions about things they can see. The presentation will include some of the challenges and solutions developed in this project, with a focus on the supporting spatial methods and services.
Friday
13 March
Dr Paul Patras
Chancellor's Fellow and Lecturer
School of Informatics
University of Edinburgh
Wi-Fi Virtualisation with Fairness Guarantees. As mobile devices are increasingly the preferred choice for Internet access, mobile operators are deploying Wi-Fi access points to increase coverage and offload capacity. In popular locations, such as airports, stadiums and cafés, infrastructure is however frequently managed by local businesses and operators are required to share the limited resources of access points. This talk will expose a wireless LAN virtualisation mechanism that guarantees the fair distribution of resources among service providers, while maximising the network throughput. By dynamically adjusting the contention parameters in the virtual networks, the solution will prove effective, independent of the number of associated clients and their level of activity. The talk will close by exploring practical implementation aspects.
Friday
27 March
Dr André Grüning
Lecturer
Department of Computing
University of Surrey
Learning to Map Spike Train Patterns in Multilayer Spiking Neural Networks. There is increasing evidence that the precise timing of spikes generated by neurons, and not just their firing rate, conveys meaningful information regarding input and output and internal processing of the nervous system. It is also widely considered that synaptic plasticity forms the basis of learning temporal spike-train-based codes in the brain. In particular, spike-timing dependent plasticity is believed to play a key role in learning, where changes in the synaptic strength between paired neurons have a dependence on relative pre- and postsynaptic spike times.

However, relating such localized plasticity changes to learning on the network level remains a significant challenge. To address this, we formulate a new supervised learning rule that can train spiking networks containing a hidden layer of neurons to associate spatio-temporal input and output spike patterns.

We demonstrate the high performance of the learning rule in terms of the number of pattern associations that it can learn.  Our approach contributes both an understanding of how spike pattern information processing might take place in the brain, and a learning rule that has technical potential for artificial neural networks build from spiking.
Friday
10 April
Dr Nadarajen Veerapen
Research Assistant
Computing Science and 
Mathematics
University of Stirling
Solving the Software Next Release Problem. The Next Release Problem involves determining the set of requirements to implement in the next release of a software project.

We first show that, although Integer Linear Programming (ILP) was found to be inefficient on this problem in the early 2000s, a modern ILP solver is now a viable solving method. Large single objective instances and small bi-objective instances can be solved exactly very quickly. On large bi-objective instances, execution times can be significant when calculating the complete Pareto front.

We therefore investigate two approximate solving methods, a genetic algorithm and a method based on ILP. Both of these produce good approximations in a timely manner, while also exhibiting good any-time behaviour.

This talk is based on a recent article.
Friday
05 June
Dr Matthew Craven
Lecturer in Applied Mathematics
School of Computing, Electronics and Mathematics (Faculty of Science and Engineering)
Plymouth University
Information Security and Evolutionary Techniques: Security of information is an increasingly important issue in the modern world, and indeed, is one of the main thrusts in the UK economic strategy. One way towards information security is via encryption of sensitive information, with new and supposedly better methods of encryption being proposed all the time. This talk will look at evolutionary algorithm attacks on two classical cryptosystems, illustrating that, in some cases, common techniques thought to make encryption harder to break in fact do the opposite. Finally we introduce a novel visualisation of EA properties and their use in control parameter optimisation, using the above EA as a case study."
Friday
26 June
Dr Rafael  Lahoz-Beltra
Associate Professor
Department of Applied Mathematics (Biomathematics)
Faculty of Biological Sciences
Complutense University of Madrid, Spain
Quantum Genetic Algorithms for Computer Scientists. Genetic algorithms (GAs) are a class of evolutionary algorithms inspired by Darwinian natural selection.  They are popular heuristic optimisation methods  based on simulated genetic mechanisms, i.e. mutation, crossover, etc. and population dynamical processes such as reproduction, selection, etc. Over the last decade, the possibility to emulate a quantum computer (a computer using quantum-mechanical phenomena to perform operations on data) has led to a new class of GAs known under the name of ‘Quantum Genetic Algorithms’ (QGAs). In this seminar we present a discussion, future potential, pros and cons of this new class of GAs. The seminar will be oriented to Computer Scientists interested in QGAs ‘avoiding’ the possible difficulties of quantum-mechanical phenomena.
Previous Seminar Series
2014:   Spring   Autumn
2013:   Spring   Autumn
2012:   Spring   Autumn
2011:   Spring   Autumn
2010:   Spring   Autumn
2009:   Spring   Autumn
2008:   Spring   Autumn

Top image: Local optima Networks for Partition Crossover (PX) on two selected instances of NK-Landscapes (N = 20, K = 2). Nodes are local optima and edges connect parents to off spring after partition crossover (black edges indicate PX followed by hill-climbing). Vertex area is proportional to their fittness and the global optimum is highlighted in red. Left: Adjacent model, the network has 60 nodes and features a single connected component. Right: Random model, the network has 50 nodes (local optima) and features 7 connected components, 4 of which are isolated nodes.  From the research article to appear (GECCO 2015): "Tunneling Crossover Networks", by G. Ochoa, F. Chicano, R. Tinos, D. Whitley.
Courtesy of Gabriela Ochoa



Last Updated: 22 June 2015.