'On the Application of Hierarchical Coevolutionary Genetic Algorithms: Recombination and Evaluation Partners'

This paper examines the use of a hierarchical coevolutionary genetic algorithm under different partnering strategies. Cascading clusters of sub-populations are built from the bottom up, with higher-level sub-populations optimising larger parts of the problem. Hence higher-level sub-populations potentially search a larger search space with a lower resolution whilst lower-level sub-populations search a smaller search space with a higher resolution. The effects of different partner selection schemes amongst the sub-populations on solution quality are examined for two constrained optimisation problems. We examine a number of recombination partnering strategies in the construction of higher-level individuals and a number of related schemes for evaluating sub-solutions. It is shown that partnering strategies that exploit problem-specific knowledge are superior and can counter inappropriate (sub-) fitness measurements.

Nurse Rostering with Genetic Algorithms

In recent years genetic algorithms have emerged as a useful tool for the heuristic solution of complex discrete optimisation problems. In particular there has been considerable interest in their use in tackling problems arising in the areas of scheduling and timetabling. However, the classical genetic algorithm paradigm is not well equipped to handle constraints and successful implementations usually require some sort of modification to enable the search to exploit problem specific knowledge in order to overcome this shortcoming. This paper is concerned with the development of a family of genetic algorithms for the solution of a nurse rostering problem at a major UK hospital. The hospital is made up of wards of up to 30 nurses. Each ward has its own group of nurses whose shifts have to be scheduled on a weekly basis. In addition to fulfilling the minimum demand for staff over three daily shifts, nurses’ wishes and qualifications have to be taken into account. The schedules must also be seen to be fair, in that unpopular shifts have to be spread evenly amongst all nurses, and other restrictions, such as team nursing and special conditions for senior staff, have to be satisfied. The basis of the family of genetic algorithms is a classical genetic algorithm consisting of n-point crossover, single-bit mutation and a rank-based selection. The solution space consists of all schedules in which each nurse works the required number of shifts, but the remaining constraints, both hard and soft, are relaxed and penalised in the fitness function. The talk will start with a detailed description of the problem and the initial implementation and will go on to highlight the shortcomings of such an approach, in terms of the key element of balancing feasibility, i.e. covering the demand and work regulations, and quality, as measured by the nurses’ preferences. A series of experiments involving parameter adaptation, niching, intelligent weights, delta coding, local hill climbing, migration and special selection rules will then be outlined and it will be shown how a series of these enhancements were able to eradicate these difficulties. Results based on several months’ real data will be used to measure the impact of each modification, and to show that the final algorithm is able to compete with a tabu search approach currently employed at the hospital. The talk will conclude with some observations as to the overall quality of this approach to this and similar problems.

Feasibility study to inform the design of a UK multi-centre randomised controlled trial of prophylactic antibiotics for the prevention of recurrent cellulitis of the leg

Background: This paper describes the results of a feasibility study for a randomised controlled trial (RCT). Methods: Twenty-nine members of the UK Dermatology Clinical Trials Network (UK DCTN) expressed an interest in recruiting for this study. Of these, 17 obtained full ethics and Research & Development (R&D) approval, and 15 successfully recruited patients into the study. A total of 70 participants with a diagnosis of cellulitis of the leg were enrolled over a 5-month period. These participants were largely recruited from medical admissions wards, although some were identified from dermatology, orthopaedic, geriatric and general surgery wards. Data were collected on patient demographics, clinical features and willingness to take part in a future RCT. Results: Despite being a relatively common condition, cellulitis patients were difficult to locate through our network of UK DCTN clinicians. This was largely because patients were rarely seen by dermatologists, and admissions were not co-ordinated centrally. In addition, the impact of the proposed exclusion criteria was high; only 26 (37%) of those enrolled in the study fulfilled all of the inclusion criteria for the subsequent RCT, and were willing to be randomised to treatment. Of the 70 participants identified during the study as having cellulitis of the leg (as confirmed by a dermatologist), only 59 (84%) had all 3 of the defining features of: i) erythema, ii) oedema, and iii) warmth with acute pain/tenderness upon examination. Twenty-two (32%) patients experienced a previous episode of cellulitis within the last 3 years. The median time to recurrence (estimated as the time since the most recent previous attack) was 205 days (95% CI 102 to 308). Service users were generally supportive of the trial, although several expressed concerns about taking antibiotics for lengthy periods, and felt that multiple morbidity/old age would limit entry into a 3-year study. Conclusion: This pilot study has been crucial in highlighting some key issues for the conduct of a future RCT. As a result of these findings, changes have been made to i) the planned recruitment strategy, ii) the proposed inclusion criteria and ii) the definition of cellulitis for use in the future trial.

Simulation Optimization of the Crossdock Door Assignmnet Problem

The purpose of this report is to present the Crossdock Door Assignment Problem, which involves assigning destinations to outbound dock doors of Crossdock centres such that travel distance by material handling equipment is minimized. We propose a two fold solution; simulation and optimization of the simulation model - simulation optimization. The novel aspect of our solution approach is that we intend to use simulation to derive a more realistic objective function and use Memetic algorithms to find an optimal solution. The main advantage of using Memetic algorithms is that it combines a local search with Genetic Algorithms. The Crossdock Door Assignment Problem is a new domain application to Memetic Algorithms and it is yet unknown how it will perform.

Simulation Optimization of the Crossdock Door Assignmnet Problem

The purpose of this report is to present the Crossdock Door Assignment Problem, which involves assigning destinations to outbound dock doors of Crossdock centres such that travel distance by material handling equipment is minimized. We propose a two fold solution; simulation and optimization of the simulation model - simulation optimization. The novel aspect of our solution approach is that we intend to use simulation to derive a more realistic objective function and use Memetic algorithms to find an optimal solution. The main advantage of using Memetic algorithms is that it combines a local search with Genetic Algorithms. The Crossdock Door Assignment Problem is a new domain application to Memetic Algorithms and it is yet unknown how it will perform.