asap
University of Nottingham >
School of CS >
a s a p
Group Research Seminars 2010 |
(TBD= To be determined; TBC= To Be Confirmed; TBA = To Be Announced)
Seminars are in room C60 at 10:30am unless announced otherwise.
|
Time: Internal seminars are generally 30mins and held on Thursdays at 11:00 and 11:30. * : Seminars organised by School (for venue and time please follow the link on date). Previous seminars 2007-2008 2006-2007 2005-2006 2004-2005 2003-2004 2002-2003 2001-2002 1999-2000 ABSTRACTS 9 Mar, 2010, Ozgur ULKER ASAP : "A 0/1 Integer Programming Model for the Office Space Allocation Problem" Abstract: We propose a 0/1 integer programming model to tackle the office space allocation (OSA) problem which refers to assigning room space to a set of entities (people, machines, roles, etc.), with the goal of optimising the space utilisation while satisfying a set of additional requirements. In the proposed approach, these requirements can be modelled as constraints (hard constraints) or as objectives (soft constraints). Then, we conduct some experiments on benchmark instances and observe that setting certain constraints as hard (actual constraints) or soft (objectives) has a significant impact on the computational difficulty on this combinatorial optimisation problem. 2 Mar, 2010, Rupa Jagannathan ASAP : "A Case-based Reasoning System for Radiotherapy Treatment Planning in Brain Cancer" Abstract: Radiotherapy is a commonly used method to treat tumours of the brain by subjecting them to ionizing radiation. The aim of radiotherapy treatment planning is to attain a uniform tumouricidal dose for the tumour while minimizing the damage caused by the radiation to healthy tissue and organs in the vicinity of the tumour. Treatment planning for brain cancer patients is a complex decision-making process that relies heavily on the subjective experience and expert domain knowledge of clinicians. In this talk, a decision support system is presented that captures this experience using case-based reasoning. Our case-based reasoning system uses a fuzzy similarity measure to evaluate the similarity between patient cases based on clnical information and geometric patient descriptors. 2 Mar, 2010, Joe Obit, ASAP : "Non-Linear Great Deluge with Learning Mechanism for Solving the Course Timetabling Problem" Abstract: This paper presents a non-linear great deluge hyper-heuristic framework which deals with complete solutions. The non-linear great deluge hyper-heuristic uses a learning mechanism for the selection of low level heuristics and a non-linear great deluge acceptance criterion. The learning mechanism allows the hyper-heuristic to select low level heuristics based on their previous performance. The learning mechanism provides a measure of performance for each low level heuristic and ranks them from the highest to the lowest, therefore, the highest ranked low level heuristic is selected next. The low level heuristics are local search operators which operate in the solution space. We propose two learning mechanisms: learning with static memory length and learning with dynamic memory length. In static memory length, the reward and punishment are constant and the reward of the low level heuristics is normalized at every predefined learning period. Whereas in dynamic memory length, a low level heuristic is rewarded and penalized when it is selected to change the current solution and the learning rate is changed automatically at random at every predefined learning period. The performance of the proposed hyper-heuristics were compared with the results of standard course timetabling benchmark instances of Socha et al in [CE22]and the ones in the literature. The experimental results showed that non-linear great deluge hyper-heuristic with static memory length outperformed the non-linear great deluge hyper-heuristic with dynamic memory length. Furthermore, non-linear great deluge hyper-heuristic with static memory length produced five new best results out of 11 and shared optimal solution for all small instances. No-linear great deluge hyper-heuristic with dynamic memory produced four best results compared to the best results reported in the literature and shared optimal solution for all small instances. 23 Feb, 2010, Yuri Bykov ASAP : "Active Data Specification Format for multi-problem benchmark instances" Abstract:The generalization of optimization techniques is always considered as an important research direction. However, the traditional way is to develop the specially-tailored optimization software for each particular type of problem. Usually it is caused by certain objective reasons, as well as artificial ones: different terminology, modeling issues, etc. In this scope, can we overcome the problem-specific obstacles and develop an algorithm, which solves, for example, Travelling Salesman Problem (TSP), Bin Packing Problem (BPP) and Exam Timetabling Problem (ETP) using exactly the same software code? For this purpose the Active Data Specification Format (ADSF) was proposed. It is an alternative way of the specification of input data for optimization problems. Using this format, all problem-specific information (including an objective function) can be obtained from a Dynamic Linked Libraries (DLL). By loading different DLLs we instruct our software to solve a new problem. This format allows a higher level of abstraction. Using ADSF we can specify an ordinary optimization problem as well as a Meta Problem, which can envelop several problems of different types. A Rectangular Assignment Meta Problem (RAMP) is an example of such specification. Nowadays ten different types of problems (including TSP, BPP, ETP and others) are mapped onto RAMP. Correspondingly, ten multi-problem benchmark instances (in the form of DLLs) are collected and publicly available. Now all these problems can be solved by the same software code. It does not require any preliminary adjustment, moreover, we even do not know which type of problem we are currently solving. Further information, benchmark instances and sample software can be found at: http://www.cs.nott.ac.uk/~yxb/actispec/ (Google: actispec) 16 Feb, 2010, Sven Groenemeyer ASAP : "A Graph Based Algorithm for the Cyclic Job-Shop Problem with Transportation" Abstract: Many jobs in industrial production and elsewhere consist of sets of tasks or operations which have to be processed on different machines. However, for this processing to happen there are several conditions or constraints which have to be satis?ed. Over recent decades fully automated manufacturing systems, where the material handling is usually carried out by transport robots, have signi?cantly increased the ?exibility and productivity of the process. Therefore, efficient schedules for different problems need to consider the interaction between machines and robots. In this talk we present a fast algorithm for the the cyclic job-shop problem with one transport robot, setup times and a given robotic cycle. The problem is polynomial solvable and the best known algorithm in the literature (as we far as we know) solves the problem (with additional time window constraints) in O(n4). The algorithm we present in this talk solves the problem in O(nm) time, where n is the number of operations and m is the number of machines. 9 Feb, 2010, Sebastienh Verel : "Fitness Landscapes and Graphs in combinatorial optimisation" Abstract:One of the most commonly-used metaphors to describe the process of heuristic search methods in solving combinatorial optimisation problems is that of a fitness landscape. The landscape metaphor appears most commonly in work related to evolutionary algorithms, however, it can be used for search in general; the search space can be regarded as a spatial structure where each point (solution) has a height (objective function value) forming a landscape surface. In this scenario, the search process would be an adaptive-walk over a landscape that can range from having many peaks of high fitness flanked by cliffs falling to profound valleys of low fitness, to being smooth, with low hills and gentle valleys. Combinatorial landscapes can be seen as a graph whose vertices are the possible configurations. If two configurations can be transformed into each other by a suitable operator move, then we can trace an edge between them. The resulting graph, with an indication of the fitness at each vertex, is a representation of the given problem fitness landscape. The study of the fitness landscape consists in analysing this graph or a relevant partition of it, with respect to the search dynamics or problem difficulty. 2 Feb, 2010, Ender Ozcan, ASAP : "Bidirectional Best-fit Heuristic for Orthogonal Rectangular Strip Packing" Abstract: Solving a rectangular strip packing problem requires a search for the best placement of a set of rectangles with given widths and heights in a suitable orientation on a strip of rectangular stock sheet with a fixed width and an infinite height. The ultimate objective is to minimise the height of the strip on which all rectangles will be oriented orthogonally without any overlaps. In this talk, a bidirectional best-fit heuristic will be introduced which considers the gaps in both horizontal and vertical directions during the placement process as a new key feature. The experiments over benchmark instances show that the bidirectional best-fit heuristic achieves better results than the existing heuristics (including the state-of-the-art) and delivers a better or matching performance as compared to the most of the previously proposed meta-heuristics. 26th January, 2010, Amr Soghier ASAP : "A graph based hyperheuristic" In this talk, we discuss a graph-based hyper-heuristic that applies tiebreakers and chooses the best low-level heuristic for hybridisation in a constructive method for solving exam-timetabling problems. After applying different tiebreakers to the Saturation Degree heuristic, Largest Weighted Degree proved to be the best heuristic to break ties during solution construction. We propose an approach to construct solutions after defining two parameters: 1) The low-level heuristic to hybridise with the tie breaked Saturation Degree is determined according to the ability of a pure Saturation Degree sequence to find a feasible solution, and 2) According to the conflict density of the problem, the percentage range of the tie breaked SD to be used is defined. Random heuristic sequences are then generated to find the best solution. The approach was tested on the Toronto benchmark problems and was able to obtain better results in comparison with the graph-based hyper-heuristics presented in the literature. In addition, to test the generality of our approach we introduce an exam timetabling instance generator and a new benchmark data set which has a similar format to the Toronto benchmark problems. The instances in the data set generated vary in size and conflict density. The publication of this problem data to the research community is aimed to give researchers the opportunity to investigate their approaches on more problems with different characteristics. We present the first results for the benchmarks and the results obtained prove that the approach is adaptive to all problems. We also encourage the use of the data set and generator to produce tailored instances and investigate certain criteria on them. 26th January, 2010, Pedro Rocha, ASAP : "Automated Radiotherapy Scheduling" Radiotherapy represents an important phase of treatment for a large number of cancer patients. It is essential that resources used to deliver this treatment are employed efficiently. In this talk, I will present three different algorithms for scheduling radiotherapy patients: a constructive approach, a mixed integer programming model and a GA, and how these algorithms can be combined with three robustness techniques: rolling horizon, pre-scheduling and re-scheduling. The experiments are conducted using real-world data from the Nottingham University Hospitals NHS Trust, UK. 17th December, 2009, James Smaldon , ASAP : "CUDA" A recent development in parallel computing is the ability to harness the massive parallel processing power of commodity graphics processing units (GPUs) for general purpose computation. Modern GPUs are highly optimised for single instruction, multiple data (SIMD) processing and have a peak theoretical performance approach 1 teraflop per second, whilst typically costing less than a single desktop PC. Nvidia's compute unified device architecture (CUDA) provides a convenient and well supported platform for developing GPU accelerated applications in the C programming language which can then be executed on Nvidia GPUs. In this talk I will introduce the CUDA hardware and the programming environment, and then describe the techniques which can be applied to get good performance when programming for CUDA. 16th December, 2009, Professor Jean-Francois Cordeau , Canada Research Chair in Logistics and Transportation, HEC Montreal : "A Large Neighbourhood Search Heuristic for an Airline Recovery Problem" The operations of a commercial passenger airline are normally planned long in advance by following a sequential planning process. Despite careful planning, however, normal operations are often disrupted by unforeseen events. Several times a week, flights are for example delayed or cancelled because of mechanical failures, airport congestion, security problems, or bad weather. When perturbations occur, airlines must react quickly to recover and minimize their impact. This talk will introduce a large neighbourhood search heuristic for an airline recovery problem combining fleet assignment, aircraft routing and passenger routing. Given an initial schedule, a list of disruptions, and a recovery period, the problem consists in constructing aircraft routes and passenger itineraries for the recovery period that allow the resumption of normal operations as quickly as possible while minimizing operating costs and impacts on passengers. The heuristic alternates between construction, repair and improvement phases, which iteratively destroy and repair parts of the solution. This work was initiated in the context of the 2009 ROADEF Challenge, a competition organized jointly by the French Operational Research and Decision Analysis Society and the Spanish firm Amadeus S.A.S., in which our team won the first prize. Co-authors: Serge Bisaillon, Gilbert Laporte and Federico Pasin. 8th December, 2009, Ying Xu, ASAP : "A new Variable Neighborhood Evolutionary Multi-objective Simulated Annealing Algorithm for Multi-objective multicast routing problems" In this talk I will present a new hybrid Variable Neighborhood Evolutionary Multi-objective Simulated Annealing Algorithm to solve the multi-objective multicast routing problems. The algorithm combines the features of variable neighborhood search and evolutionary multi-objective simulated annealing algorithm, aiming at a more flexible and adaptive exploration when searching over the search space to find more non-dominated solutions in the Pareto Front. The motivation is to enable a search concerning multiple objectives simultaneously by employing different neighborhood structures which are specifically designed for each objective in the problem. Simulations have been carried out on benchmark instances and a set of random networks for the multi-objective multicast routing problems with real world objectives including cost, delay and link utilizations. Our experimental results demonstrate that the proposed Variable Neighborhood Evolutionary Multi-objective Simulated Annealing algorithm is able to find high quality non-dominated solutions for the multi-objective multicast routing problems. In particular, the variable neighborhood structures make a significant improvement to the performance of the proposed algorithm compared with the single neighborhood based evolutionary multi-objective simulated annealing algorithm. 8th December, 2009, Sam Allen, ASAP : "An Abstract Data Type for Packing Representations" In this talk I will discuss a method for representing packing solutions and partial packings in n dimensions. I will give some complexity results on "best fit" style packing algorithms in n dimensions and show how different concrete implementations of the ADT can effect runtime both theoretically and empirically. 1st December, 2009, Antonio David Masegosa Arredondo, ASAP : "Multi-threaded cooperative strategies for optimisation " Multi-threaded cooperative strategies are a very promising field in optimisation. This type of method consists of a set of heuristics or solvers run in parallel that exchange and share information collected along the search to increase their robustness and efficiency. This type of strategies can be centralised if the information exchange is done through a central processor that controls the solvers, or decentralised if the search threads exchange information directly between them. In this talk I will focus on centralised multi-threaded cooperative strategies. Concretely, I will present a centralised model where the solvers are controlled by a rule based coordinator. Apart from this, I will discuss some aspects like the benefits of cooperation, the importance of the composition of the cooperative strategy as well as the behaviour of the method when the coordinator uses different control rules. 1st December, 2009, Danny Kershaw, Principle R&D Engineer at ARM : "ARM and the challenges of implementing ubiquitous computing" By volume shipment, ARM is by far the worlds most successful 32 micro-processor architecture, with well over 10Bn total, and a current run rate of about 4Bn units being shipped per year. ARM processors bring intelligence and functionality to the consumer products which surround you, your mobile phone, car, navigation equipment, TV, set-top box, USB sticks, disk drives, WiFi NIC, to name but a few. In this seminar I introduce ARM, its products and innovative partnership business model, and go on to list some of the challenges we face in a selection of the markets we are active in, and end with a plea for the research community to help with the some of the challenges we face as we follow the trend of parallel computing becoming both more openly end user programmable, and ubiquitous. 24th November, 2009, Carlos Garcia Martinez, ASAP : "Evolutionary Algorithms Specialising on Intensification/Diversification & Evolutionary Components" Hybrid metaheuristics attempt to obtain the best from a set of algorithms that perform together and complement each other to produce a profitable synergy from their combination. Nowadays, a promising way to obtain hybrid metaheuristics concerns the combination of several search algorithms with strong specialization in intensification and/or diversification. The flexible architecture of evolutionary algorithms allows specialized models to be obtained with the aim of providing intensification and/or diversification. The outstanding role that is played by evolutionary algorithms at present justifies the choice of their specialist approaches as suitable ingredients to build hybrid metaheuristics. Skipping the details, I will briefly present in this talk four proposals we developed with this idea in mind: 1) Global and local real-coded genetic algorithms for continuous optimisation; 2) Binary local genetic algorithm for binary combinatorial problems; 3) Evolutionary iterated-local-search perturbation technique for binary combinatorial problems as well; and 4) Variable neighbourhood search with evolutionary components for continuous optimisation. 24th November, 2009, Gabriela Ochoa, ASAP : "Local Optima Networks: A Model for Landscape Analysis" We propose a characterisation of combinatorial fitness landscapes as complex networks. This network model is a reduction of the landscape in which the nodes correspond to the local optima, and the edges account for the notion of adjacency between their basins of attraction. The model was inspired by the notion of 'inherent network' of potential energy surfaces proposed in physical-chemistry. Once the network of a combinatorial landscape has been extracted, the tools of complex network analysis can bee used to characterise its topology. We proposed a definition of the edges that account for transition probabilities between basins, and conducted a large empirical study where the networks of a set of abstract landscapes (the NK model) with different degrees of ruggedness, were extracted. We found that the network topologies of the studied landscapes reflect the previously known increase in search difficulty on landscapes with increasing ruggedness. We also found interesting and unknown properties of the basins of attraction. A visualisation of the landscapes as local optima networks, illustrates the potential of this network view. We argue that this model can be useful for understanding problem difficulty in combinatorial optimization, and eventually for guiding the design of effective search heuristics. 17th November, 2009, Juergen Branke, : "Analysing and Improving Job Shop Dispatching Rules by Automatically Generating Difficult Problem Instances" Dispatching rules are heuristic decision rules that, whenever a machine becomes available, determine which operation is processed next. Because dispatching rules make local decisions at the latest possible time, they have the ability to flexibly react to shop floor disruptions or dynamics which are prevalent in real world manufacturing environments. This and other advantages makes them widely used in industry. However, there is no simple way of generating a local dispatching rule that will result in a good global performance of a complex shop floor. In most cases, it is a matter of expertise and tedious trial-and-error to come up with a suitable dispatching rule. In this talk, we propose an evolutionary algorithm that assists in the development of dispatching rules by automatically constructing problem instances where a proposed rule performs poorly. This allows the designer to better understand and remove the weaknesses of a given rule. We apply the approach to a scenario from the literature and show that the gained insights can indeed lead to the design of a more effective dispatching rule. 10th November, 2009, Daniel Hulme, : "Constraint Satisfaction and Silicon Valley" In this talk I intend to introduce the basic concepts of Constraint Satisfaction and Boolean Satisfiability (SAT). Using a simple example I demonstrate how natural constraint problems can be formulated as SAT instances. I show how encoding a problem differently can have a dramatic effect on it solubility. Over the past decade dramatic improvements in algorithms have given rise to SAT algorithms that can solve industrial instances with thousands and even millions of variables. Though these solvers have been adopted by the Semiconductor industry, they are largely untapped by the rest of the scientific and business communities. Finally, I will introduce the NPComplete Project underway in UCLs Computer Science Department. NPComplete leverages a combination of encodings, pre-processing, algorithms, machine learning and high-power grid computing; providing a conduit to facilitate algorithmic research developments to reach industry. 3th November, 2009, Prof Stein Wallace, : "Planning under uncertainty - the use of what-if analysis" Most decisions are made under some uncertainty about the future. Most models do not take that explicitly into account. Is that a minor issue or a major problem? The purpose of this lecture is to illustrate how deterministic models, even combined with sensitivity analysis, what-if-sessions, or other similar tools, can lead to rather bad decisions. This is true whether we use quantitative tools or simple verbal arguments. Using one example from network design and one from scheduling, I demonstrate how solutions from deterministic models differ from those of stochastic models in systematic and recognizable ways. I also discuss how important it might be to capture the time structure of the uncertainty correctly. 20th October, 2009, Nishikant Mishra, ASAP : "A knowledge-light nonlinear case-based reasoning approach to radiotherapy planning" Radiation is often used in prostate cancer treatments. Radiotherapy treatment planning is a complex decision making process. In order to make a patient well, the oncologist has to make a trade-off between the benefit of radiation i.e. delivering a high enough dose to fight the cancer cells, and risk that refers to the side effects of the treatment. In this research, a case based reasoning system is developed for dose planning in prostate cancer treatment. A case similar to the new patient is retrieved. An adaptation of the suggested plan is performed taking into account trade-offs made in the past to determine the extent to which the maximum dose limits of the new patient (case) can be violated. The performance of the proposed method is validated on the real data sets obtained from the City Hospital Nottingham, University Hospital, NHS Trust, UK. 20th October, 2009, Tim Curtois, ASAP : "An improved model for staff rostering" This presentation will introduce a new, more general and flexible model for the staff rostering problem. The new model has a number of significant practical and algorithmic advantages over previous models which will all be discussed. 15th October, 2009, Andrew Koh, Institute for Transport Studies,University of Leeds : "Game Theoretic Formulations of Decision Making in Transportation Systems Management and their Solutions by Evolutionary Algorithms" In Transportation Systems Management, decisions by both regulators and private sector participants can be modelled using paradigms founded in game theory. With a single regulator, the problem becomes one of a mathematical programming with Equilibrium Constraints (MPECs) and in a market with private sector participants, the resultant formulation is an Equilibrium Problem with Equilibrium Constraints (EPECs). Compared with other optimization problems, these models possess the distinguishing feature that the leaders actions are governed by an equilibrium condition describing equilibrium in a given system. This topic is currently a popular research field in Mathematics with applications in engineering and economics. Employing evolutionary algorithms, we describe how such problems may be formulated and solved. Numerical examples drawn from the literature are then given. 6th October, 2009, Elkin Castro, ASAP : "A multi-objective approach to the radiotherapy pre-treatment scheduling problem based on mathematical programming" Demand for radiotherapy treatment services has increased due to higher cancer incidence, aging population, and a larger number of prescribed radiotherapy fractions. This higher demand can, in turn, produce longer waiting times. It is also known that long waiting times negatively impact the health of patients. Government regulations have been put in place to have a common baseline to measure and mitigate this issue. We introduce a real-world radiotherapy pre-treatment scheduling problem at a hospital in the UK. We introduce a multi-objective solution approach based on mathematical programming, discuss the obtained results, and give insights into future research work. 6th October, 2009, Enrico Glaab, ASAP : "Pathway-based analysis of cancer gene sets" New high-throughput experimental technologies in the bio-sciences enable researchers to analyze massive numbers of genes, proteins and metabolites in a fast and parallel fashion. Correspondingly, public annotation data bases on the web have been growing exponentially in recent years. Scientists are confident that ultimately, interpreting this data will not only expand our knowledge but help us to improve medical diagnosis and identify new drug targets for many diseases. However, new computational methods are needed to combine the vast amount of experimental data with the equally complex and voluminous medical data from the literature. In this talk I will present the results of a bioinformatics data integration project conducted during a 3-months internship at the Spanish National Centre of Oncological Research (CNIO). Based on simple network analysis methods and statistics, I will provide some examples of how metabolic pathway data can be combined with protein interaction data and cancer gene sets from the literature. The presented methods can be used to identify and rank associations between metabolic pathways and cancer gene sets in order to obtain new biological insights. 27th August, 2009, Natalio Krasnogor, ASAP : "Memetic Algorithms \\MetaComand: replace(memetic algorithms, hyperheuristics)" Memetic Algorithms have become one of the key methodologies behind solvers that are capable of tackling very large, real-world, optimisation problems. They are being actively investigated in research institutions as well as broadly applied in industry. In this talk we provide a pragmatic guide on the key design issues underpinning Memetic Algorithms (MA) engineering. We begin with a brief contextual introduction to Memetic Algorithms and then move on to define a Pattern Language for MAs. For each pattern, an associated design issue is tackled and illustrated with examples from the literature. We then fast forward to the future and mention what, in our mind, are the key challenges that scientistis and practitioner will need to face if Memetic Algorithms are to remain a relevant technology in the next 20 years. 25th August, 2009, Eunice S. G. Oliveira, : "Adaptive operators and hybridization of meta-heuristics for multi-objective problems" This presentation is about two multi-objective optimization problems: a flow-shop problem and a reactive power compensation in electrical distribution networks problem. Some of the well-known Genetic Algorithms and the Simulated Annealing were used to obtain a Pareto Optimal front. We present and compare some results achieved with the both. 25th June, 2009, Michael Li, ASAP : "The collective strategy for evolutionary iterated prisoners dilemma" In recent iterated prisoners dilemma tournaments, the most successful strategies were those that had identification mechanisms. By playing a predetermined sequence of moves and learning from their opponents responses, these strategies managed to identify their opponents. We believe that these identification mechanisms may be very useful in evolutionary games. In this talk, a strategy, which we call collective strategy, is introduced. Collective strategies apply a simple but efficient identification mechanism that just distinguishes themselves from other strategies, and only cooperate with their group members and defect against any others. In this way, collective strategies are able to maintain a stable population. Simulations show that a group of collective strategies is especially strong in competing with other strategies. This collective behavior assists in maintaining a stable population in evolutionary dynamics. 18th June, 2009, Syariza Abdul Rahman, ASAP : "Construction of examination timetables based on ordering heuristics" We combined graph coloring heuristics, namely largest degree and saturation degree with the concept of a heuristic modifier under the framework of squeaky wheel optimization for solving a set of examination timetabling problems. Both heuristics interact and adaptively determine the ordering of examinations to be processed during each of iteration. A variety of approaches based on different heuristics and their combinations are investigated. Experimental results on a set of benchmark problems show that the proposed approaches can produce high quality solutions comparable to the other constructive methods. For one problem instance, the best results based on onstructive heuristics provided in the literature are improved by one of the proposed methods. We conclude that our approach is simple, yet effective. 11th June, 2009, Rong Qu, ASAP : "A generic graph based hyper-heuristic framework" This is a brief overview of research issues in a simple generic graph based hyper-heuristic (GHH) framework. These include some fundamental issues on the characteristics of two search spaces (namely the search spaces of the heuristics and the actual solutions) and the effect of a number of high level search algorithms upon the problems concerned. Hybridisations in the GHH framework with local search methods have also been concerned with respect to the exploration of the high level search and the exploitation of the local search. Possible extensions upon this simple, yet general, GHH framework are also discussed. 4th June, 2009, Ha Duong (Maverick), ASAP : "New heuristics to solve three dimensional strip packing problem" Packing is one of combinatorial optimization problem and has many applications in real world. Different heuristic has been proposed to solve the problem. In the presentation, we present some constructive heuristics to solve the problem. 28th May, 2009, James Smaldon, ASAP : "Liposome Logic - encapsulating digital logic within vesicles" Synthetic biology is the engineering of biological systems to introduce new functionality that does not exist in nature. More and more concepts derived from computer science and engineering such as the use of clocks, switches and pulse generators are applied to design decision making and other such complex behaviours in cells. Recent work by Weiss et al has shown that simple boolean logic gates can be constructed from gene regulation networks within bacteria, which may be interconnected to produce robust computation and communications in the stochastic environment of the cell volume. In this presentation, an investigation into the possibility of creating modular components built from these logic gates and encapsulated within liposomes, small vesicles formed from phospholipid membranes, is described. In essence, this approach is the application of the bio-logic paradigm to bottom-up synthetic biology where the aim is the creation of the simplest living protocells from first principles. Logic gates were encapsulated and simulated within self-assembled liposomes using an implementation of Dissipative Particle Dynamics (DPD) created with the NVIDIA CUDA framework and were shown to behave as intended. The benefit of our system over other stochastic modelling techniques is that the dynamics of the compartment encapsulating the computation are emergent, due to the repeated application of simple rules rather than being specified in the model explicitly. 28th May, 2009, Belal Ismail Khalil Al-Khateeb, ASAP : "Introducing a Round Robin Tournament into Blondie24" Evolving self learning players has attracted a lot of research attentions in recent years. Fogels Blondie24 represents one of the successes in this field and one of the main reasons for motivating other scientists. In this paper evolutionary neural networks, evolved via an evolution strategy, are utilised to evolve game playing strategies for the game of checkers by introducing a league structure into the learning phase of a system based on Blondie24. We believe that this helps eliminate the randomness in the evolution strategies phase. Thirty feed forward neural network players are played against each other, using a round robin tournament structure, for 150 generations and the best player obtained is tested against a reimplementation of Blondie24 (Blondie24-R). We also test the best player against an online program, as well as two other strong programs. The results obtained are promising. 21st May, 2009, Mohd Nizam Mohmad Kahar, ASAP : "The examination timetabling problem at Universiti Malaysia Pahang-Comparison of a constructive heuristic with an existing software solution" This talk presents a real world, capacitated examination timetabling problem from Universiti Malaysia Pahang (UMP), Malaysia. The problem has additional constraints which have not been modelled before, these being the distance between examination rooms and splitting exams across several rooms. These constraints provide additional challenges in defining a suitable model and in developing a constructive heuristic. We presented the constructive heuristic that is able to produce good quality solutions for the problem, which are superior to the solutions that are produced using the universitys current software. Moreover, our method adheres to all hard constraints which the current systems fails to do. 21st May, 2009, Azhar Ali Shah Syed, ASAP : "Distributed Framework for Multi-Criteria Protein Structure Comparison" Protein Structure Comparison (PSC) is an essential component of biomedical research as it impacts on, e.g., drug design, molecular docking, protein folding and structure prediction algorithms as well as being essential to the assessment of these predictions. Each of these applications, as well as many others where molecular comparison plays an important role, requires a different notion of similarity that naturally lead to the Multi-Criteria Protein Structure Comparison (MC-PSC) problem. ProCKSI (www.procksi.org), provides algorithmic solutions for the MC-PSC problem by means of an enhanced structural comparison that relies on the principled application of information fusion to similarity assessments derived from multiple comparison methods. Current MC-PSC works well for moderately sized data sets and it is time consuming as it provides public service to multiple users. Many of the structural bioinformatics applications mentioned above would benet from the ability to perform, for a dedicated user, thousands or tens of thousands of comparisons through multiple methods in real-time, a capacity beyond our current technology. This talk presents our work on high-throughput distributed re-implementation of ProCKSI for very large data sets. The core of this work lies in the design of an innovative distributed algorithm that runs on each compute node in a cluster/grid environment to perform structure comparison of a given subset of input structures using some of the most popular PSC methods (e.g. USM, MaxCMO, Fast, DaliLite, CE and TMalign). This is followed by the procedure of distributed consensus building. Thus the new algorithms proposed here achieve ProCKSIs similarity assessment quality but with a fraction of the time required by it. 14th May, 2009, Dario Landa-Silva, ASAP : "Tackling shelf space allocation with hybrid heuristics" Shelf space allocation is the problem of arranging retail products on shelves. An arrangement can be created based on various criteria, such as product profitability, product size and shelf profitability. The objective of shelf space allocation is usually to maximize profits. Sometimes other objectives may exist, such as improving stock control and improving customer satisfaction. This talks describe some heuristic approaches to automate the shelf space allocation process for a retail shop in order to produce an efficient arrangement represented as a planogram, which is the graphical representation of an arrangement. Most work on shelf space allocation reported in the literature has focused on the case of large retailers such as supermarkets. We tackle the case of a small retail shop using hybrid heuristics. This method helps to almost double the expected profit by producing an improved arrangement of products in the available shelf space. 7th May, 2009, Hui Li, ASAP : "An Adaptive Population-based Multi-objective Simulated Annealing Algorithm for Combinatorial Optimization" In the recent two decades, the research on the combinatorial optimization problems with multiple objectives has attracted growing interest. Many metaheuristic algorithms originally designed for single objective optimization, such as evolutionary algorithms, simulated annealing, tabu search, ant colony optimization, have also been extended to find the Pareto-optimal solutions of these problems. In this paper, we propose a hybrid metaheuristic algorithm for dealing with multi-objective combinatorial optimization problems. It combines a recent multi-objective evolutionary algorithm, i.e., MOEA/D, with simulated annealing. The new features of the proposed algorithm include adaptive weight vectors, epsilon-dominance archiving strategy, and adaptive temperature scheme. Our experimental results show that the proposed algorithm performs better than several other state-of-the-art multi-objective algorithms on both the multi-objective knapsack problem and the multi-objective traveling salesman problem. 7th May, 2009, Francisco Romero Campero, ASAP : "Modular Assembly of Cell Systems Biology Models Using P Systems" In this talk we present a computational framework for the modelling of complex systems in systems and synthetic biology based on P systems. Our framework takes explicitly modularity into account. Modularisation in cellular systems can be produced by chemical specificity, spatial localisation and/or temporal modulation within cellular compartments. The first two of these modularisation features, the focus of this talk, can be easily specified and analysed in P systems using sets of rewriting rules to describe chemical specificity and membranes distributed over a geometrical lattice to represent spatial localisation. Our methodology enables the assembly of cell systems biology models by combining modules which represent functional subsystems. We illustrate this framework by presenting two on going studies. Namely, the quorum sensing system in the bacterium Pseudomonas aeruginosa and synthetic gene regulatory networks producing propagating waves of gene expression in bacterial colonies. 30th April 2009, Geert De Maere, ASAP : "Multi-objective strategic robust airline scheduling" This talk presents an overview of the recent work in robust airline scheduling that was carried out in the ASAP research group at the University of Nottingham. We introduce the multi-objective approaches based on re-timing and integrated re-timing and re-routeing that enabled us to investigate the mutual interaction between robustness influencing characteristics, and their simultaneous influence on a schedule's operational performance. Exact and approximate solution methods are introduced. Results for real world data from a major European airline are presented and discussed. The key observations are summarised and a brief overview of promising directions for future research is provided. 23rd April 2009, Hongqing Cao, ASAP : "Analysis of Alternative Fitness Methods for the Evolutionary Synthesis of Cell Systems Biology Models" This study proposes a new methodology for the automatic design of cell systems biology models. Our modelling framework is based on P systems, a discrete, stochastic and modular computational modelling paradigm that abstracts from the structure and functioning of the living cell. We use a modular modelling approach which means that all the models are created and later evolved based on a module library in which simple modules representing general gene regulatory mechanisms and specific regulations in particular well-known gene promoters are defined. The design of our models, comprising both the optimization of the model structure and stochastic kinetic constants contained in the modules, is performed using a nested evolutionary algorithm. The first layer of our algorithm evolves model structures by combining different modules taken from a predefined module library, whereas the inner layer finely tunes the stochastic kinetic constants of the modules. Both layers are implemented as genetic algorithms. In order to properly deal with different test cases with specific data properties, we provide four alternative fitness methods for the fitness calculation in our nested evolutionary algorithm, namely, equally weighted sum method, normalization method, randomly weighted sum method, and equally weighted product method. The effectiveness of the methodology is tested on four case studies predesigned with increasing complexity, namely, negative and positive autoregulation, and two gene networks implementing a pulse generator and a band width detector. The four different fitness methods are applied to each test case and their results are compared and analyzed. 23rd April 2009, Dr Jaume Bacardit, ASAP : "A Mixed Discrete-Continuous Attribute List Representation for Large Scale Classification Domains" Datasets with a large number of attributes are a difficult challenge for evolutionary learning techniques. The recently proposed attribute list rule representation has shown to be able to significantly improve the overall performance (e.g. run-time, accuracy, rule set size) of the BioHEL Iterative Evolutionary Rule Learning system. In this talk I am going to show, first, how the attribute list rule representation has been extended so it can handle not only continuous domains, but also datasets with a very large number of mixed discrete-continuous attributes. Afterwards, the new representation is benchmarked with a diverse set of large-scale datasets and its performance is compared against several well-known machine learning methods. The results of the experiments show that the new representation is equal or better than the state-of-the-art in evolutionary rule representations both in terms of the accuracy obtained with the benchmark datasets used, as well as in terms of the computational time requirements needed to achieve these improved accuracies. The new attribute list representation puts BioHEL on an equal footing with other well-established machine learning techniques in terms of accuracy. 9th April 2009, Andrew Parkes, ASAP : "From OPL to ice-cream cones?" Not really a seminar as such, but an introduction to the mathematical programming tools that we have available and with some experiences of their usages. This should be brief but lead into a discussion surrounding the email sent out a few months back as to whether people wanted to form some internal group to teach ourselves their usage. (I might also mention stochastic and/or nonlinear programming). 9th April 2009, Jason Atkin, ASAP : "Departure sequencing near the runway at Heathrow " The take-off sequencing problem at Heathrow has differences to the normal problems which are studied in the academic literature. After a brief description and illustration of the departure system, I will discuss the characteristics of the problem and the differences between the real world problem and the usual academic formulations in both the constraints and objectives. Obviously I'll have to end with some results showing why the research was worth doing. 31st March 2009, Hugo Terashima-Marin, Tecnolgico de Monterrey, Campus Monterrey : "Generalized Hyper-heuristics for Solving 2D Regular and Irregular Packing Problems" The idea behind hyper-heuristics is to discover some combination of straightforward heuristics to solve a wide range of problems. To be worthwhile, such a combination should outperform the single heuristics. This article presents a GA-based method that produces general hyper-heuristics that solve two-dimensional regular (rectangular) and irregular (convex polygonal) bin-packing problems. A hyper-heuristic is used to define a high-level heuristic that controls low-level heuristics. The hyper-heuristic should decide when and where to apply each single low-level heuristic, depending on the given problem state. In this investigation two kinds of heuristics were considered: for selecting the figures (pieces) and objects (bins), and for placing the figures into the objects. Some of the heuristics were taken from the literature, others were adapted, and some other variations developed by us. We chose the most representative heuristics of their type, considering their individual performance in various studies and also in an initial experimentation on a collection of benchmark problems. The GA included in the proposed model uses a variable-length representation, which evolves combinations of condition-action rules producing hyper-heuristics after going through a learning process which includes training and testing phases. Such hyper-heuristics, when tested with a large set of benchmark problems, produce outstanding results for most of the cases. The testbed is composed of problems used in other similar studies in the literature. Some additional instances for the testbed were randomly generated. 19th March 2009, Ender Ozcan, ASAP : "A Case Study of Memetic Algorithms for Constraint Optimization" There are many types of knapsack problems in the literature. In a multidimensional 0-1 knapsack problem, there are multiple knapsacks and each item has a different weight in different knapsacks. The objective is to maximize the total profit obtained by selecting a subset of items while respecting the capacity constraints defined for each knapsack. As the 0-1 suggests, the items are indivisible. Multidimensional 0-1 knapsack problem is an NP-hard combinatorial optimization problem having many application areas, such as stock cutting, cargo loading, capital budgeting, and allocating processors in a distributed computing environment. This talk describes a set of memetic algorithms for solving this problem and provides a comparison to the previous results. 12th March 2009, Nam Pham, ASAP : "Linear combinations of heuristics for examination timetabling." Using graph colouring to model timetabling problems is popular. In this talk, we will present several new vertex-selection heuristics based on the well know heuristics - largest degree, largest weighted degree and saturation degree. Then, we propose an approach of using linear combinations of such heuristics to identify the most troublesome vertices as early as possible; a troublesome vertex is one that is most likely to lead to a poor or infeasible timetable if its colouring is deferred until later in the process. We give justification on our decisions of designing linear combinations of heuristics and report our results on the Toronto timetabling benchmark. 12th March 2009, Matthew Hyde, ASAP : "Automatic Design of Reusable 3D Packing Heuristics" This presentation compares the quality of reusable heuristics designed by our genetic programming (GP) system, to those designed by human programmers. The heuristics are designed for the three dimensional knapsack packing problem. Evolutionary computation has been employed many times to search the space of solutions to such problems. However, actually designing heuristics for this problem domain is a skill in which GP currently has no experience. In contrast, the literature shows that it has taken years of experience by human analysts to design the very effective heuristic methods that currently exist.Hyper-heuristics search a space of heuristics, rather than directly searching a solution space. GP operates as a hyper-heuristic in this work, because it searches the space of heuristics that can be constructed from a given set of components. We show that GP can design simple, yet effective, stand-alone constructive heuristics. While these heuristics do not represent the best in the literature, the fact that they are designed by evolutionary computation, and are human competitive, provides evidence that further improvements in this GP methodology could yield heuristics superior to those designed by humans. 5th March 2009. Qiang Guo (John), ASAP "Applying Grouping Method for Cutting and Packing Problems" The Grouping Genetic Algorithm has been previously applied to one-dimensional bin packing problems and obtained some good results. We are extending the method to multi-dimensional problems. The idea is to reuse of good building blocks and avoid bad ones. During the developing of this technique, we have observed some factors which may have significant influence on results. The project is still on-going and we will appreciate any comments /discussion on this technique. 26th February 2009. Gabriela Ochoa, ASAP "HyFlex: A Flexible Framework for the Design and Analysis of Hyper-heuristics" This seminar is more like a tutorial than a research talk. The first part of the talk will present an overview and a classification of hyper-heuristic approaches. The second part will introduce Hyflex, a novel OO framework for supporting research into modern search methodologies (especially but not only hyper-heuristics). This is a team effort (Tim, Antonio, Matt and me). The emphasis of the HyFlex framework lies in providing the algorithm components that are problem specific, thus liberating algorithm designers from needing to know the problem domains specific details. The design efforts of HyFlex's users will instead be focused on designing high-level strategies to intelligently combine the provided tools. 19th February 2009. Jingpeng Li, ASAP "A New Data Mining Based Multi-objective Optimisation Framework" Multi-objective optimization is the process of simultaneously optimizing two or more conflicting objectives subject to certain constraints. In this presentation, I will briefly introduce a new data mining based multi-objective optimisation framework. Firstly, we generate an initial solution by whatever method, such as a heuristic or mathematical approach. We then use any local search method to search the neighbouring area of the initial solution and identify a new solution. Next, we evaluate the quality of the newly-obtained solution under multiple objectives, by the method of compromise programming. Later, we set a criterion to decide if the solution can be accepted, by any of the methods such as hill-climbing, simulated annealing, tabu search, and our newly-proposed falling tide optimisation. After accepting a new solution, we update the maintained Pareto set which contains a number of solutions, with each solution being no worse than any other solutions for all objectives and being better in at least one objective. The following four steps are executed in a loop, until a stopping condition met. In the meaning time, we use a data mining processor to aid or speed up the search. Data mining is the search for relationships and global patterns that exist in large databases but which are hidden among them. By data mining, we can predict the quality of resulting solutions, without calculating their actual objective values. 19th February 2009. Jonathan Blakes, ASAP "The case for another systems biology modelling environment" Systems biology is a growing interdisciplinary field that aims understand the normal and abnormal functioning of organisms by modelling the relationships between molecular species in living cells. There is a large body of software, often developed in academia, to assist with the building and simulation of such models. This talk will give an overview of recent computational modelling approaches in systems biology and the associated software landscape. It presents the case for the development of a new modelling environment aims to improve the user experience of biologists by making models easier to build and to refine, while increasing the complexity of and scales over which models can be built. 12th February 2009. Xiang Song, Research associate in School of Mathematics, University of Cardiff "Variant Beam Search Implementation for the Irregular Shape Bin Packing Problem" The talk presents progress on the design of an evolutionary algorithm which uses the concept of volume dominance instead of conventional Pareto dominance to assign fitness to solutions in multi-objective optimization (MOO). We have previously proposed volume dominance to promote a good balance between convergence and diversity in MOO. Volume dominance has improved the performance of other algorithms and now we combine it with other features such as ranking and crowding techniques. Preliminary experiments on multiple knapsack problems shows that the presented algorithm significantly improves the diversity of the non-dominated solutions set when compared to SEAMO2, SPEA2, NSGA2. 12th February 2009. Khoi Le, ASAP "Volume Dominance Within a Multi-objective Evolutionary Algorithm" The talk presents progress on the design of an evolutionary algorithm which uses the concept of volume dominance instead of conventional Pareto dominance to assign fitness to solutions in multi-objective optimization (MOO). We have previously proposed volume dominance to promote a good balance between convergence and diversity in MOO. Volume dominance has improved the performance of other algorithms and now we combine it with other features such as ranking and crowding techniques. Preliminary experiments on multiple knapsack problems shows that the presented algorithm significantly improves the diversity of the non-dominated solutions set when compared to SEAMO2, SPEA2, NSGA2. 5th February 2009. Yuri Bykov, ASAP "Late Acceptance Strategy - the new general-purpose optimisation metaheuristic" The Late Acceptance Strategy is a recently invented optimisation methodology, which has been publicly presented on PATAT 2008 conference. It was adapted to Hill-Climbing algorithm (LAHC - Late Acceptance Hill-Climbing) and applied to Exam Timetabling Problems. This search technique has only one parameter, very simple for implementation and tuning and, at the same time, its performance is not worse (or even better) than the most powerful metaheuristics, such as Simulated Annealing. Its high quality was confirmed by ASAP group members who already implemented it and I suppose that more other researches will be interesting to apply it to their problems. 29th January 2009. Zalilah Abd Aziz, ASAP "An Ant-based hyperheuristic for Vehicle Routing Problem" One of the aims for hyperheuristics is to raise the generality of an optimisation system. The objective is to produce a more general system that is able to solve a wider range of problem domains. In this presentation, I will explain briefly the concept of Ant-based hyperheuristics and the Vehicle Routing Problem. 29th January 2009. Antonio Vazquez, ASAP "Discovering interesting algorithm variants using genetic programming" An exciting new application of genetic programming is the automatic discovery of procedures to solve difficult combinatorial problems. Researchers so far have built new algorithms from scratch by combining primitive operators or components of known algorithms into fully working procedures. In this work, we (1) start with a well known heuristic, (2) identify one of its components which is easy to modify and has an important contribution to performance, (3) use genetic programming to find an improved compatible new component, and (4) replace the old component with the new one. We have used this methodology to find variants of the well known NEH heuristic to solve the permutation flow shop problem with different objective functions, and constraints. We demonstrate that, according to certain metrics, the new heuristic variants are as successful on their target problems as is NEH on the problem for which it was originally designed. 22nd January 2009. Rupa Jagannathan, ASAP "Dealing with missing values in a clinical case-based reasoning system" In clinical case-based reasoning systems, missing values in the case-base pose a common but serious problem that impairs the performance of the system. Imputing or estimating missing values by making an informed guess is popular in many knowledge-based systems but once the imputation has been performed, the system needs to be adjusted to acknowledge the fact that imputed values are only estimates of original values. In this talk, I will introduce an imputation method that exploits the correlation between clinical data by filtering the case-base according to attributes correlated to the missing attribute. I will also present a framework that shows how any imputation method can be used in a case-based reasoning system to reflect the quality of the imputation method in the similarity calculation and account for the inherent uncertainty associated with imputation. 22nd January 2009. Sven Groenemeyer, ASAP "Cyclic Job-Shop Scheduling with one Transport Robot" Many jobs in industrial production and elsewhere consist of sets of tasks or operations which have to be processed on different machines. However, for this processing there are several conditions or constraints which have to be satisfied. In large-scale productions identical jobs are performed many times. To deal with such situations, cyclic scheduling problems are introduced which will be presented in this talk. Furthermore, we assume that the jobs are transported between the machines by one robot. Thus, we have additional constraints concerning the robot moves. In this talk, we will show the advantages and disadvantages of cyclic scheduling in general. Most authors considering the problem including a transport robot assume that the route of the robot is given in advance. Thus, we will show how the route the robot takes to transport the different jobs between the machines can influence the quality of possible solutions. Additionally we present some ideas for local search heuristics to solve the general problem. 15th January 2009. Patrick Moratori, ASAP "Match-Up Strategies for Job Shop Rescheduling" We investigate the problem of integrating new rush orders into the current schedule of a real world job shop floor. Satisfactory rescheduling methods must keep stability of the shop, by introducing the fewest number of changes in the ordering of operations, while maintaining the same levels of the schedule performance criteria. This paper introduces a number of match-up strategies that modify only part of the schedule in order to accommodate new arriving jobs. These strategies are compared with the right-shift and the total-rescheduling methods, which are optimal regarding stability and performance, but ineffective for performance and stability, respectively. Statistical analysis indicates that the match-up strategies are comparable to right-shift for stability, and as good as total-rescheduling for performance. 15th January 2009. Juan Pedro Castro Gutierrez, ASAP "From Infeasible to Feasible Solutions for the VRPTW Using a MOPSO Approach" This presentation is intended to show the ability of a discrete particle swarm optimization algorithm (DPSO) to evolve solutions from infeasibility to feasibility for the Vehicle Routing Problem with Time Windows (VPRTW). The proposed algorithm incorporates some principles from multi-objective optimization to allow particles to conduct a dynamic trade-off between objectives in order to reach feasibility. The main contribution of this paper is to demonstrate that without incorporating tailored heuristics or operators to tackle infeasibility, it is possible to evolve very poor infeasible route-plans to very good feasible ones using swarm intelligence. 11th December 2008. Ying Xu, ASAP "A Variable Descent Search Algorithm for Multicast Routing Problem" The rapid evolution of real-time multimedia applications requires Quality of Service based multicast routing in underlying computer networks. The constrained Steiner Tree, as the underpinning mathematical structure, is a well-known NP-complete problem. In this paper we investigate variants of variable neighborhood search for the delay-constrained least-cost multicast routing problems. The neighborhood structures designed in the variable neighborhood search approaches are based on the idea of path replacement in trees. They are simple, yet effective, enabling a flexible search over the solution space of this complex problem with multi-constraints. A large number of simulations demonstrate that our algorithm is highly efficient in solving the delay-constrained least-cost multicast routing problem in terms of both the total tree cost and execution time. To our knowledge, this is the first study of variable neighborhood search on delay-constrained least-cost multicast routing problem. It outperforms other algorithms and heuristics over a range of problem instances. 11th December 2008. Nor Hayati Abdul Hamid, ASAP "Maximising Stadium Attendance : A Case Study of Malaysian Football" Malaysian football is seeing a decrease in the number of supporters at stadiums. We propose that a level of importance is defined for each fixture, which we then maximise. This is in the expectation that the more important a match, the more attractive it will be for supporters. 4th December 2008. Fang He, ASAP "A Hybrid Constraint Programming Approach for Nurse Rostering Problems" Due to the complexity of nurse rostering problems (NRPs), pure Constraint Programming (CP) approaches have shown to be ineffective in solving these highly constrained problems. We investigate a two-stage hybrid CP approach on real world benchmark NRPs. In the first stage, a CP model is used to generate weekly rosters consist of high quality shift sequences satisfying a subset of constraints. An iterative forward search is then adapted to extend them to build complete feasible solutions. Variable and value selection heuristics are employed to improve the quality of the solution built. In the second stage, a simple Variable Neighborhood Search is used to quickly improve the solution obtained. The basic idea of the approach is based on the observations that high quality nurse rosters are consist of high quality shift sequences. By decomposing the problems into solvable sub-problems for CP, the search space of the original problems are significantly reduced. The results on benchmark problems showed the efficiency of this hybrid CP approach when compared to the state-of-the-art approaches in the literature. 4th December 2008. Sam Allen, ASAP "A Novel Heuristic/Metaheuristic Approach to the Three-Dimensional Strip-Packing Problem" Although cutting and packing research has received significant attention in recent years it has generally concentrated on one or two-dimensional packing. Though this has many real-life practical applications - paper, metal, glass or other sheet material cutting, basic pallet loading etc., and several more theoretical ideas such as multi-processor scheduling it is not directly applicable or translatable to other industrial problems, such as three-dimensional block cutting (e.g. foam, wood, marble etc.), load planning (trucks, air cargo etc.) or multi-dimensional limited resource scheduling. The proposed packing strategy developed for the 3-dimensional strip-packing problem draws inspiration from the ideas proposed for the equivalent two-dimensional problem algorithm presented by Burke et al in 2004, whilst adding a number of substantial changes and improvements in order to make it applicable to the three-dimensional problem. The results so far are extremely competitive and show a lot of potential for future applications. The heuristics created scale well to large problems and also create high quality solutions for two-dimensional problems, which are being explored in conjunction with a University spin out company, Aptia Solutions Ltd who specialise in creating automated nesting and machine control cutting software. 27th November 2008. Djamila Ouelhadj, ASAP "A Cooperative Hyper-heuristic Framework for Scheduling" The aim of this research work is to investigate the role of cooperative decision making in the selection process of low level heuristics within a distributed hyper-heuristic framework to enhance performance and robustness. The cooperative hyper-heuristic framework is an agent-based system composed of a Coordinator Hyper-Heuristic Agent (CHHA) and a population of Low Level Heuristic Agents (LLHA). The HHA manages the cooperative selection of the low level heuristics to apply at each decision point of the search space. The LLHAs perform different search strategies using different low level heuristics, and coopearte synchronously or asynchronously through the CHHA. Cooperation is based on the solution pool strategy, in which the LLHAs cooperate through the synchronous/asynchronous exchange of elite solutions of the low level heuristics. Experimental results for a set of permutation flow shop benchmark instances illustrate the performance of the asynchronous/asynchronous cooperative hyper-heuristics. 27th November 2008. Amr Soghier, ASAP "An Adaptive Graph Based Hyper-heuristic using GRASP for Exam Timetabling Problems" We propose an approach where two low-level graph heuristics, Saturation Degree (SD) and Largest Weighted Degree (LWD) are dynamically hybridised in the construction phase of a Greedy Random Adaptive Search Procedure (GRASP) to construct solutions for exam timetabling problems. The problem is initially solved using an intelligent adaptive LWD and SD graph hyper-heuristic, which constructs the restricted candidate list (RCL) in the first phase of GRASP. It is observed that the SD heuristic is essential to construct a feasible solution but that it does not perform well at the early stages of the construction. Therefore, LWD is used until a certain switching point is reached. The hyper-heuristic determines the best switching point adaptively after evaluating the quality of the solutions produced. Steepest descent is used in the improvement phase of GRASP to improve the quality of the solutions constructed. The comparison of this approach with state-of-the-art approaches indicates that it is a simple yet efficient technique. The results also indicate that the technique could adapt itself to construct good quality solutions for any timetabling problem with similar constraints. 20th November 2008. Manual Kutschka, University of Warwick "Improving state-of-the-art ILP-solvers by separating {0,1/2}-cuts for general integer linear programs" Many real-world optimisation problems can be modelled as integer linear programs, for example in production, logistics or telecommunication. A branch-and-bound approach in conjunction with the separation of cutting planes (branch-and-cut) is used for solving these problems. Within this process violated inequalities (cuts) are added to the linear relaxation in order to tighten it and therefore to provide better dual bounds on the optimal objective value. Chvatal-Gomory cuts are among the most well-known classes of cutting planes for general integer linear programs (ILPs). In case the constraint multipliers are either 0 or 1/2, such cuts are known as {0,1/2}-cuts. It has been proven by Caprara and Fischetti that separation of {0,1/2}-cuts is NP-hard. In this talk, we describe our efforts to separate {0,1/2}-cuts effectively in practice. We propose a range of preprocessing rules to reduce the size of the separation problem. The core of the preprocessing builds a Gaussian elimination-like procedure. To separate the most violated {0,1/2}-cut, we formulate the (reduced) problem as integer linear program. Some simple heuristic separation routines complete the algorithmic framework. Computational experiments on benchmark instances show that the combination of preprocessing with exact and/or heuristic separation is a very vital idea to generate strong generic cutting planes for integer linear programs and to reduce the overall computation times of state-of-the-art ILP-solvers. 13th November 2008. Pawel Widera "Evolutionary design of the energy function for protein structure prediction" Automatic protein structure predictors use the notion of energy to guide the search towards good candidate structures. The energy function is commonly defined as a linear combination of energy terms designed by human experts. Although a vast amount of scientific effort has been put into development of these energy components, not much is known about how they should be combined into the energy function. To test the hypothesis that less restricted combination of the energy terms may lead to more accurate prediction, we have designed a genetic programming algorithm to evolve the energy function for protein structure prediction. The talk will introduce a number of different GP designs that we came up with and present the results of evaluation of their accuracy on a set of protein structures generated by the real predictor. 6th November 2008. Jakub Marecek "Decomposition, Reformulation, and Diving" In many real-life optimisation problems, there are multiple interacting components in a solution. For example, different components might specify assignments to different kinds of resource. Often, each component is associated with different sets of soft constraints, and so with different counts of their violations. The goal is then to minimise a linear combination of such counts of violations related to particular components of a solution. On the example of Udine Course Timetabling, this paper studies an approach to such problems, which can be denoted as multiphase exploitation of multiple objective-/value-restricted submodels. In this approach, only one computationally difficult component of a problem and a subset of objectives is considered at first. This produces partial solutions, which define interesting neighbourhoods in the search space of the complete problem. Using integer programming, it is easy to implement heuristics producing solutions with bounds on their quality. 30th October 2008. Graham Kendall "Balancing Conflicting Objectives for English Football" Previous work minimised the distance travelled by English football clubs over the Christmas/New Year period. In doing so various constraints have to be respected. One of these relates to /clashes/ which measures how many /paired/ teams play at home on the same day. The schedules that are actually used allow a certain number of clashes and our previous work used these values for our investigations. In this work we explore if travel distances are significantly increased if we reduce the number of clashes below those that were used in practise. The results from seven seasons will be presented. 23rd October 2008. Alberto Castellini "Metabolic P systems for modelling biological processes" Metabolic P systems, shortly MP systems, are a class of P systems proved to be effective and successful for modeling biological phenomena related to metabolism. Equivalences between this formalism and, respectively, autonomous ODE and Hybrid Functional Petri nets have been recently proved, and several biological processes have been modelled, such as the lac operon gene regulatory mechanism in glycolytic pathway and the mitotic cycles in early amphibian embryos. A Java virtual laboratory, called MetaPlab, have been also developed which supports the synthesis and the simulation of MP models by means of an extensible plugin-based architecture. In this talk I introduce a new technique, based on neural networks, for the synthesis of MP regulation functions, namely the functions that regulate the dynamics of an MP system, and I show some results achieved by this methodology. 23rd October 2008. Joe Obit "Great Deluge with Non-linear Decay Rate for Solving Course Timetabling Problems" Course timetabling is the process of allocating, subject to constraints, limited rooms and timeslots for a set of courses to take place. Usually, in addition to constructing a feasible timetable (all constraints satisfied), there are desirable goals like minimising the number of undesirable allocations (e.g. courses timetabled in the last timeslot of the day). The construction of course timetables is regarded as a complex problem common to a wide range of educational institutions. The great deluge algorithm explores neighbouring solutions which are accepted if they are better than the best solution so far or if the detriment in quality is no larger than the current water level. In the original great deluge, the water level decreases steadily in a linear fashion. In this paper, we propose a modified version of the great deluge algorithm in which the decay rate of the water level is non-linear. The proposed method produces new best results in 4 of the 11 course timetabling problem instances used in our experiments. 16th October 2008. Pedro Rocha "Constructive Approaches to Radiotherapy Scheduling" With the increase in the number of cancer cases and new government regulations for cancer treatment, radiotherapy scheduling has gained a lot of importance recently. In this paper, four constructive approaches to radiotherapy scheduling are introduced, as well as a GRASP based algorithm for improving the solution obtained by the constructive approaches. These algorithms are investigated on real-world data obtained from the Nottingham University Hospitals NHS Trust, UK. 9th October 2008. Robert `Bob' Oates: "Immunology, Signal Processing and RatSLAM" A large proportion of bio-inspired computing is based on abstracted models of the brain and nervous system. However, from an engineering perspective, there is a largely-overlooked mechanism within the body that performs information processing, contains aspects of memory and decision making and lends itself perfectly to parallel computation: the immune system. This talk will provide a simple introduction to the basics of immunology and go on to demonstrate how these mechanisms have inspired a variety of novel algorithms. The talk will go on to focus on a relatively new algorithm within the field of artificial immune systems based on the operation of dendritic cells developed by Dr Julie Greensmith at the University of Nottingham and explain how we intend to fuse this algorithm with The University of Queenslands RatSLAM algorithm to provide an immune-inspired robotic security system. 2nd October 2008. Minaya Villasana: "An approach to cancer chemotherapy scheduling" We start with a mathematical model that can capture qualitative features of tumour growth and it's interaction with the immune system. The purpose is to use the drug as a controller of the system, taking the tumour level to desired states. In mathematical terms, we are guiding the tumour into the basin of attraction of a tumour-free stable equilibrium of the dynamical system. We will focus on the modelling aspect of the problem formulations, give a brief summary of the most important results up to date, work in progress, and future directions. 4th September 2008. Nikola Todorovic: "Bee Colony Optimisation for Nurse Rostering" We propose a novel bee colony optimisation approach to the nurse rostering problem. The bee colony optimisation algorithm belongs to the class of stochastic swarm optimisation methods. It is motivated by the foraging habits of honey bees. In iterations, artificial bees collectively improve their solutions. The algorithm for nurse rostering was designed to be a combination of constructive and improving phases. In the constructive phase, unscheduled shifts are being assigned to available nurses, while the improving phase aims to improve the current solution within the defined neighbourhood. An intelligent discarding of the portion of a large neighbourhood is performed for which it is predicted that it will not lead to the improvement of the objective function. The algorithm was tested on real world data from hospitals in Belgium. The results show that the bee colony optimisation is able to efficiently find solutions that are competitive compared to the solutions produced by other algorithms. 23rd July 2008. Michel Toulouse: "A cooperation/diffusion search algorithm and applications to hyper-heuristics" Search steps in population based methods make use of information gathered from several points. In cooperative neighborhood based methods, information is obtained from points (solutions) generated by several independent search programs running concurrently. This information is then integrated in the decision process of neighborhood based search methods allowing for cooperation among search methods. However, centralized cooperation schemes involving many programs are difficult to define and cumbersome to implement. In this talk, I describe a decentralized cooperation/diffusion scheme in which information is gathered and used cooperatively in several small scale cooperative algorithms. This information then diffuses across many cooperative algorithms, forming a single large scale cooperative problem solving system. Cooperative search could be seen as a mean to address the heuristic selection problem. I will describe new algorithms which are initial avenues to hybrid cooperation/diffusion schemes with hyper-heuristics. 9th July 2008. Jacomine Grobler: "Metaheuristics for multiple machine multi-objective production scheduling" Production scheduling has been fascinating researchers since the early 1950s. Customers increasingly expect to receive the right product, at the right price, at the right time. To meet these requirements, manufacturing companies need to improve their production scheduling performance. This talk investigates the application of particle swarm optimization and differential evolution in a multiple machine multi-objective scheduling environment. Production down time and sequence-dependent set-up times were also considered in this work. Various solution representations, and multi-objective optimization strategies were investigated and benchmarking against currently used algorithms on real customer data demonstrated significant performance improvement. 12th June. 2008. Jiawei Li (Michael): "An approach to accelerate heuristics for exam timetabling" The successful application of metaheuristic methods in exam timetabling problems shows that those good solutions for a specific timetabling have some common features. If the problems could be simplified according to these common features, good solutions would be kept in the reduced search space and then heuristic methods could be much efficiently not only in improving the speed of converging to a feasible solution but also that the quality of resulted timetable could be improved. In this talk, I am about to introduce a new approach that combines compatible examinations in order to accelerate both the initial timetable construction, as well as a later search. The conditions for combining exams are described, and we show that we are able to offer some guarantees as to the quality of solutions that remain in the reduced search space. The approach is applied to one of the standard benchmarks in this area; the St. Andrews83 instance. The results verify the effectiveness of this approach in simplifying examination timetabling problems, speeding up initial timetable construction and assisting any subsequent search. 5th June 2008. Mujgan Sagir: "Analytic Network Process, Multiobjective Educational Timetabling Problems and Approaches" This talk briefly summarizes the ongoing educational timetabling researches of the speaker. Besides, an introduction of the Analytic Network Process (ANP), the generalization of the Analytic Hierarchy Process (AHP), is given. The reason to introduce ANP here is the need to prioritize different criteria or multiple objectives of the optimization problems and ANP can be used for this purpose. Because the solution of any decision model strongly depends on its parameters, if the model does not represent the real problem, the outcome of the model may not be a valid one. Educational timetabling problems (ETP) are usually difficult to solve due to the complex and varied nature of them. Each system has its own constraints and therefore hard to get a general approach that will handle all type of problems. Besides 0-1 discreteness increases the complexity. We are interested in different types of educational timetabling problems as faculty-course, faculty-course-room, faculty-course-room-time slot, or invigilator assignments and also exam scheduling. They mostly have multiple and both qualitative and quantitative objectives. Two-phased solution methods (dividing the problem into two different sub problems which are then solved consecutively), a methodology for finding non-dominated solutions, considering participant preferences and using analytic network process are some topics characterize the solution approaches of our works. There are also on going researches with a research group of the speaker related to three dimensional pallet loading, open vehicle routing, and assortment problems. The total time (40-50 minutes) of the talk is going to be used by introducing the ANP, and the ETP researches of the speaker as about 20-25 minutes for each. |
| Comments to jaa at cs.nott.ac.uk |