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.
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
1996:
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.