Multilevel refinement for combinatorial optimisation: boosting metaheuristic performance

The multilevel paradigm as applied to combinatorial optimisation problems is a simple one, which at its most basic involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found, usually at the coarsest level, and then iteratively refined at each level, coarsest to finest, typically by using some kind of heuristic optimisation algorithm (either a problem-specific local search scheme or a metaheuristic). Solution extension (or projection) operators can transfer the solution from one level to another. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas (for example multigrid techniques can be viewed as a prime example of the paradigm). Overview papers such as [] attest to its efficacy. However, with the exception of the graph partitioning problem, multilevel techniques have not been widely applied to combinatorial problems and in this chapter we discuss recent developments. In this chapter we survey the use of multilevel combinatorial techniques and consider their ability to boost the performance of (meta)heuristic optimisation algorithms.

Application of particle swarm optimisation to evaluation of polymer cure kinetics models

A particle swarm optimisation approach is used to determine the accuracy and experimental relevance of six disparate cure kinetics models. The cure processes of two commercially available thermosetting polymer materials utilised in microelectronics manufacturing applications have been studied using a differential scanning calorimetry system. Numerical models have been fitted to the experimental data using a particle swarm optimisation algorithm which enables the ultimate accuracy of each of the models to be determined. The particle swarm optimisation approach to model fitting proves to be relatively rapid and effective in determining the optimal coefficient set for the cure kinetics models. Results indicate that the singlestep autocatalytic model is able to represent the curing process more accurately than more complex model, with ultimate accuracy likely to be limited by inaccuracies in the processing of the experimental data.

Numerical optimisation techniques applied to evacuation analysis

A common problem faced by fire safety engineers in the field of evacuation analysis concerns the optimal design of an arbitrarily complex structure in order to minimise evacuation times. How does the engineer determine the best solution? In this study we introduce the concept of numerical optimisation techniques to address this problem. The study makes user of the buildingEXODUS evacuation model coupled with classical optimisation theory including Design of Experiments (DoE) and Response Surface Models (RSM). We demonstrate the technique using a relatively simple problem of determining the optimal location for a single exit in a square room.

Borehole Optimisation System (BOS) - a case study assessing options for abstraction of urban groundwater in Nottingham, UK

The recognition that urban groundwater is a potentially valuable resource for potable and industrial uses due to growing pressures on perceived less polluted rural groundwater has led to a requirement to assess the groundwater contamination risk in urban areas from industrial contaminants such as chlorinated solvents. The development of a probabilistic risk based management tool that predicts groundwater quality at potential new urban boreholes is beneficial in determining the best sites for future resource development. The Borehole Optimisation System (BOS) is a custom Geographic Information System (GIs) application that has been developed with the objective of identifying the optimum locations for new abstraction boreholes. BOS can be applied to any aquifer subject to variable contamination risk. The system is described in more detail by Tait et al. [Tait, N.G., Davison, J.J., Whittaker, J.J., Lehame, S.A. Lerner, D.N., 2004a. Borehole Optimisation System (BOS) - a GIs based risk analysis tool for optimising the use of urban groundwater. Environmental Modelling and Software 19, 1111-1124]. This paper applies the BOS model to an urban Permo-Triassic Sandstone aquifer in the city centre of Nottingham, UK. The risk of pollution in potential new boreholes from the industrial chlorinated solvent tetrachloroethene (PCE) was assessed for this region. The risk model was validated against contaminant concentrations from 6 actual field boreholes within the study area. In these studies the model generally underestimated contaminant concentrations. A sensitivity analysis showed that the most responsive model parameters were recharge, effective porosity and contaminant degradation rate. Multiple simulations were undertaken across the study area in order to create surface maps indicating areas of low PCE concentrations, thus indicating the best locations to place new boreholes. Results indicate that northeastern, eastern and central regions have the lowest potential PCE concentrations in abstraction groundwater and therefore are the best sites for locating new boreholes. These locations coincide with aquifer areas that are confined by low permeability Mercia Mudstone deposits. Conversely southern and northwestern areas are unconfined and have shallower depth to groundwater. These areas have the highest potential PCE concentrations. These studies demonstrate the applicability of BOS as a tool for informing decision makers on the development of urban groundwater resources. (c) 2007 Elsevier Ltd. All rights reserved.

An industrial implementation of a methodology for the optimisation of product design tolerances

Today, the key to commercial success in manufacturing is the timely development of new products that are not only functionally fit for purpose but offer high performance and quality throughout their entire lifecycle. In principle, this demands the introduction of a fully developed and optimised product from the outset. To accomplish this, manufacturing companies must leverage existing knowledge in their current technical, manufacturing and service capabilities. This is especially true in the field of tolerance selection and application, the subject area of this research. Tolerance knowledge must be readily available and deployed as an integral part of the product development process. This paper describes a methodology and framework,currently under development in a UK manufacturer, to achieve this objective.