A curve-fitting genetic algorithm for a styling application

Fitting curves in computer-aided geometric design is generally regarded as an optimisation problem. Depending on the application, the conditions to be satisfied can make the problem difficult to solve using classic methods, and for this reason, stochastic methods, such as genetic algorithms appear to be appropriate. This article considers a curve fitting problem, with the objective of generating shapes with specific curvature variations for use in the design of car bodies. To this end, a particular curve model was developed and implemented within a genetic algorithm. The main characteristics of this algorithm are described and its promising results are presented. The conclusion will show that this technique can be used as an alternative method in the design of car bodies.     

The use of search experimentation in discrete-event simulation practice

The practice of DES experimentation has not been rigorously assessed in over a decade. Past studies of DES practice report little transfer of experimentation theory into real-world application. We conducted an international survey of over 300 modellers to investigate the extent to which simulation optimisation, meta-modelling and design of experiments are used in practice. Over the last decade there has been substantial growth in the use of optimisation and to a lesser extent design of experiments to tackle practical problems. However, users rarely make use of optimisers bundled with commercial software, opting instead for custom or third-party solutions. Outside of academia, the use of methods is hampered by a lack of application knowledge and a persisting view that such techniques are not necessary. It is clear that academics must not become complacent regarding the dissemination of theory into common practice and continue to reach out to industry users.     

Heuristic optimisation in financial modelling

There is a large number of optimisation problems in theoretical and applied finance that are difficult to solve as they exhibit multiple local optima or are not ‘well-behaved’ in other ways (e.g., discontinuities in the objective function). One way to deal with such problems is to adjust and to simplify them, for instance by dropping constraints, until they can be solved with standard numerical methods. We argue that an alternative approach is the application of optimisation heuristics like Simulated Annealing or Genetic Algorithms. These methods have been shown to be capable of handling non-convex optimisation problems with all kinds of constraints. To motivate the use of such techniques in finance, we present several actual problems where classical methods fail. Next, several well-known heuristic techniques that may be deployed in such cases are described. Since such presentations are quite general, we then describe in some detail how a particular problem, portfolio selection, can be tackled by a particular heuristic method, Threshold Accepting. Finally, the stochastics of the solutions obtained from heuristics are discussed. We show, again for the example from portfolio selection, how this random character of the solutions can be exploited to inform the distribution of computations.     

On Optimal Control Using Particle Methods

Mesh-based methods like finite elements and finite volumes enjoy limited use in deforming domain and free surface applications due to exorbitant computational demands. Instead, particle methods are very suitable for simulating such problems. However, they have not been used for optimisation yet. We therefore derive optimisation strategies using this kind of methods. (© 2009 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

BIANCA: a genetic algorithm to solve hard combinatorial optimisation problems in engineering

The genetic algorithm BIANCA, developed for design and optimisation of composite laminates, is a multi-population genetic algorithm, capable to deal with unconstrained and constrained hard combinatorial optimisation problems in engineering. The effectiveness and robustness of BIANCA rely on the great generality and richness in the representation of the information, i.e. the structure of populations and individuals in BIANCA, and on the way the information is extensively exploited during genetic operations. Moreover, we developed proper and original strategies to treat constrained optimisation problems through the generalisation of penalisation methods. BIANCA can also treat constrained multi-objective problems based on the construction of the Pareto frontier. Therefore, BIANCA allows us to approach very general design problems for composite laminates, but also to make a step forward to the treatment of more general problems of optimisation of materials and structures. In this paper, we describe specifically the case of optimal design of composite laminates, concerning both the theoretical formulation and the numeric resolution.     

An evolutionary approach for finding optimal trees in undirected networks

In many utilities, such as water and gas, materials are distributed through networks of pipes. For efficiency, many such distribution networks are constructed as trees. The cost of construction and operation of these is generally a complex function of the edges which are used, so that it is impossible to use conventional algorithms for the optimisation of trees. This paper presents a method for identifying a tree which is close to optimal. This evolutionary method is based on ideas from genetic algorithms.     

Multilevel Refinement for Combinatorial Optimisation Problems

We consider the multilevel paradigm and its potential to aid the solution of combinatorial optimisation problems. The multilevel paradigm is a simple one, which involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found (sometimes for the original problem, sometimes the coarsest) and then iteratively refined at each level. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas (most notably in the form of multigrid techniques). However, with the exception of the graph partitioning problem, multilevel techniques have not been widely applied to combinatorial optimisation problems. In this paper we address the issue of multilevel refinement for such problems and, with the aid of examples and results in graph partitioning, graph colouring and the travelling salesman problem, make a case for its use as a metaheuristic. The results provide compelling evidence that, although the multilevel framework cannot be considered as a panacea for combinatorial problems, it can provide an extremely useful addition to the combinatorial optimisation toolkit. We also give a possible explanation for the underlying process and extract some generic guidelines for its future use on other combinatorial problems.     

A Geometric Integration Approach to Nonsmooth,Nonconvex Optimisation

The optimisation of nonsmooth, nonconvex functions without access to gradients is a particularly challenging problem that is frequently encountered, for example in model parameter optimisation problems. Bilevel optimisation of parameters is a standard setting in areas such as variational regularisation problems and supervised machine learning. We present efficient and robust derivative-free methods called randomised Itoh–Abe methods. These are generalisations of the Itoh–Abe discrete gradient method, a well-known scheme from geometric integration, which has previously only been considered in the smooth setting. We demonstrate that the method and its favourable energy dissipation properties are well defined in the nonsmooth setting. Furthermore, we prove that whenever the objective function is locally Lipschitz continuous, the iterates almost surely converge to a connected set of Clarke stationary points. We present an implementation of the methods, and apply it to various test problems. The numerical results indicate that the randomised Itoh–Abe methods can be superior to state-of-the-art derivative-free optimisation methods in solving nonsmooth problems while still remaining competitive in terms of efficiency.

     

Mathematical programming time-based decomposition algorithm for discrete event simulation

Mathematical programming has been proposed in the literature as an alternative technique to simulating a special class of Discrete Event Systems. There are several benefits to using mathematical programs for simulation, such as the possibility of performing sensitivity analysis and the ease of better integrating the simulation and optimisation. However, applications are limited by the usually long computational times. This paper proposes a time-based decomposition algorithm that splits the mathematical programming model into a number of submodels that can be solved sequentially to make the mathematical programming approach viable for long running simulations. The number of required submodels is the solution of an optimisation problem that minimises the expected time for solving all of the submodels. In this way, the solution time becomes a linear function of the number of simulated entities.     

Beamforming and Interference Cancellation for Capacity Gain in Mobile Networks

The growth of wireless communication continues. There is a demand for more user capacity from new subscribers and new services such as wireless internet. In order to meet these expectations new and improved technology must be developed. A way to increase the capacity of an existing mobile radio network is to exploit the spatial domain in an efficient way. An antenna array adds spatial domain selectivity in order to improve the Carrier-to-Interference ratio (C/I) as well as Signal-to-Noise Ratio (SNR). An adaptive antenna array can further improve the Carrier-to-Interference ratio (C/I) by suppressing interfering signals and steer a beam towards the user. The suggested scheme is a combination of a beamformer and an interference canceller.The proposed structure is a circular array consisting of K omni-directional elements and combines fixed beamforming with interference cancelling. The fixed beamformers use a weight matrix to form multiple beams. The interference cancelling stage suppresses undesired signals, leaking into the desired beam.The desired signal is filtered out by the fixed beamforming structure. Due to the side-lobes, interfering signals will also be present in this beam. Two alternative strategies were chosen to cancel these interferers; use the other beamformer outputs as inputs to an adaptive interference canceller; or regenerate the outputs from the other beamformer outputs and generate clean signals which are used as inputs to adaptive interference cancellers.Resulting beamformer patterns as well as interference cancellation simulation results are presented. Two different methods have been used to design the beamformer weights, Least Square (LS) and minimax optimisation. In the minimax optimisation a semi-infinite linear programming approach was used. Although the optimisation plays an essential role in the performance of the beamformer, this paper is focused on the application rather then the optimisation methods.     

An objective space cut and bound algorithm for convex multiplicative programmes

Multiplicative programming problems are global optimisation problems known to be NP-hard. In this paper we propose an objective space cut and bound algorithm for approximately solving convex multiplicative programming problems. This method is based on an objective space approximation algorithm for convex multi-objective programming problems. We show that this multi-objective optimisation algorithm can be changed into a cut and bound algorithm to solve convex multiplicative programming problems. We use an illustrative example to demonstrate the working of the algorithm. Computational experiments illustrate the superior performance of our algorithm compared to other methods from the literature.     

Robust supply chain network design with service level against disruptions and demand uncertainties: A real-life case

We have developed a stochastic mathematical formulation for designing a network of multi-product supply chains comprising several capacitated production facilities, distribution centres and retailers in markets under uncertainty. This model considers demand-side and supply-side uncertainties simultaneously, which makes it more realistic in comparison to models in the existing literature. In this model, we consider a discrete set as potential locations of distribution centres and retailing outlets and investigate the impact of strategic facility location decisions on the operational inventory and shipment decisions of the supply chain. We use a path-based formulation that helps us to consider supply-side uncertainties that are possible disruptions in manufacturers, distribution centres and their connecting links. The resultant model, which incorporates the cut-set concept in reliability theory and also the robust optimisation concept, is a mixed integer nonlinear problem. To solve the model to attain global optimality, we have created a transformation based on the piecewise linearisation method. Finally, we illustrate the model outputs and discuss the results through several numerical examples, including a real-life case study from the agri-food industry.     

Gradient-based approximation methods applied to the optimal design of vehicle suspension systems using computational models with severe inherent noise

The principal aim of this paper is to evaluate the feasibility of using gradient-based approximation methods for the optimisation of the spring and damper characteristics of an off-road vehicle, for both ride comfort and handling. The Sequential Quadratic Programming algorithm and the relatively new Dynamic-Q method are the two successive approximation methods used for the optimisation. The determination of the objective function value is performed using computationally expensive numerical simulations that exhibit severe inherent numerical noise. The use of forward finite differences and central finite differences for the determination of the gradients of the objective function within Dynamic-Q is also investigated. This is done in investigating methods for overcoming the difficulties associated with the optimisation of noisy objective functions.A recreational off-road vehicle is modelled in ADAMS, and coupled to MATLAB for the execution of the optimisation process. The full vehicle ADAMS model includes suspension kinematics, a load-dependent tyre model, as well as non-linear springs and dampers. Up to four design variables are considered in modelling the suspension characteristics.It is found that both algorithms perform well in optimising handling. However, difficulties are encountered in obtaining improvements in the design process when ride comfort is considered. Nevertheless, meaningful design configurations are still achievable through the proposed optimisation process, at a relatively low cost in terms of the number of simulations that have to be performed.     

A simulation-based study of a NHS Walk-in Centre

This paper describes a simulation-based project to help North Mersey Community National Health Service Trust to design and plan the operation of a NHS Walk-in Centre. The simulation model developed of this multi-service facility was used to facilitate managers and health professionals to recognize existing problems and potential future problems, and to investigate ideas for their ‘solution’. In the fast-moving NHS where initiatives to improve access, such as walk-in centres, are a recent development and where no two centres are the same, ideas for best practice borrowed from elsewhere can be quickly tested for suitability in the local situation.     

Robots,CAM and O.R.

Microelectronics have greatly influenced the nature of manufacturing technology and systems. New factories make growing use of microcomputers and microprocessors in robots, C.N.C. machine tools and flexible manufacturing systems. The result is an increasing trend towards fully integrated computer-based manufacturing systems. As a consequence, O.R. software has a newer, more direct role in the modern factory than ever before. Fully integrated CAM systems are implemented by multi-disciplinary teams of engineers and management scientists. The O.R. practitioner can make a major contribution, for example in layout optimisation and plant simulations.     

An architecture for solving sequencing and resource allocation problems using approximation methods

In the search for better optimisation techniques, new methods that mix artificial intelligence and operations research have emerged. Search heuristics are integrated with optimisation algorithms. Approximation methods, like Hill Climbing, Simulated Annealing, and Tabu Search, that have been used with success in combinatorial optimisation problems, are one of such research lines. This paper presents the key elements of approximation methods and combines them in a tool appropriate for solving sequencing and resource allocation problems. The system permits a clear division between problem specification and problem solving, allowing a declarative representation and therefore minimising developing costs. The key issues discussed in this work are a model for representing this class of problems in a standard form, a set of strategies for applying the approximation methodology, and an expert system that dynamically manipulates the strategies' parameters.     

Multi-objective optimisation of positively homogeneous functions and an application in radiation therapy

Unconstrained multi-objective optimisation problems with p$p$ positively homogeneous objective functions are considered. We prove that such problems reduce to multi-objective optimisation problems with p−1$p-1$ objectives and a single equality constraint. Thus, problems with two objectives can be solved with standard single objective optimisation methods and, for problems with p>2$p>2$ objectives, we can compute infinitely many efficient solutions by solving a finite number of single objective problems. The proposed procedure is applied on radiotherapy for cancer treatment.     

A multiobjective programming model for locating treatment sites and routing hazardous wastes

In this paper, a multiobjective model for locating disposal or treatment facilities and transporting hazardous waste along the links of a transportation network are presented. Some of the nodes of this network may be population centres generating hazardous waste which must be transported to the treatment facilities. Four objectives are considered: (1) minimisation of total operating cost, (2) minimisation of total perceived risk, (3) equitable distribution of risk among population centres and (4) equitable distribution of the disutility caused by the operation of the treatment facilities. A goal programming model to solve the problem is developed and a small hypothetical example is presented to illustrate how penalty functions can be used to obtain more satisfactory solutions in real life applications.     

Modular global optimisation in chemical engineering

Chemical Engineering design and analysis is dominated by the use of modular computational systems restricting the use of rigorous global optimisation techniques. Other engineering domains also exploit modularity in order to break down complex tasks to allow the use of legacy codes, to protect intellectual property, and to allow large teams to work on problems. By casting modules in a generic form such systems could be recast to incorporate interval based methods. In this paper we explore the use of five interval contraction methods to improve the performance of interval based optimization of modular process design systems: consistency methods, constraint propagation, Interval Gaussian elimination, Interval Newton and Linear Programming. It is shown that the Linear Programming contractor provides the greatest value in contracting the intervals and that constraint propagation and Interval Gaussian elimination (as implemented here) provides less of an impact. Other contractors do provide value and the LP contractor will be of less value as the problem size increases so it is necessary to include a number of contractors which can be done at small computational cost. A number of challenges are outlined which need to be addressed before there can be routine use of interval global optimization in modular systems.