Constraint Handling in Genetic Algorithms: The Set Partitioning Problem

In this paper we present a genetic algorithm-based heuristic for solving the set partitioning problem (SPP). The SPP is an important combinatorial optimisation problem used by many airlines as a mathematical model for flight crew scheduling.A key feature of the SPP is that it is a highly constrained problem, all constraints being equalities. New genetic algorithm (GA) components: separate fitness and unfitness scores, adaptive mutation, matching selection and ranking replacement, are introduced to enable a GA to effectively handle such constraints. These components are generalisable to any GA for constrained problems.We present a steady-state GA in conjunction with a specialised heuristic improvement operator for solving the SPP. The performance of our algorithm is evaluated on a large set of real-world problems. Computational results show that the genetic algorithm-based heuristic is capable of producing high-quality solutions.     

Lamination Design Optimization for Continuous Fiber Reinforced Composites of Variable Thicknesses北大核心CSCD

由于具备高的比强度、比刚度,利用连续纤维增强复合材料代替传统金属材料以实现结构轻量化正受到设计者们的广泛关注。然而,结构的复杂性给复合材料的铺层设计与优化带来了很大的挑战。针对航空用复合材料铺层设计约束多的问题,通过逐步构建设计变量准确表达结构的铺层信息。基于经典遗传算法框架,结合各设计变量特点,定义了铺层优化算法中的遗传算子,通过引入“修复”策略保证了每一代解都能满足设计约束,分布在可行域区间内。最后利用精英保留策略提高了算法的局部寻优能力,可以降低复杂复合材料结构铺层设计的计算成本。通过解决经典benchmark问题并与已有优化结果的比较,验证了前述铺层优化算法的全局、局部寻优能力,为工程实际中的复合材料铺层设计优化提供了理论支撑。     

A simplicial homology algorithm for Lipschitz optimisation

The simplicial homology global optimisation (SHGO) algorithm is a general purpose global optimisation algorithm based on applications of simplicial integral homology and combinatorial topology. SHGO approximates the homology groups of a complex built on a hypersurface homeomorphic to a complex on the objective function. This provides both approximations of locally convex subdomains in the search space through Sperner’s lemma and a useful visual tool for characterising and efficiently solving higher dimensional black and grey box optimisation problems. This complex is built up using sampling points within the feasible search space as vertices. The algorithm is specialised in finding all the local minima of an objective function with expensive function evaluations efficiently which is especially suitable to applications such as energy landscape exploration. SHGO was initially developed as an improvement on the topographical global optimisation (TGO) method. It is proven that the SHGO algorithm will always outperform TGO on function evaluations if the objective function is Lipschitz smooth. In this paper SHGO is applied to non-convex problems with linear and box constraints with bounds placed on the variables. Numerical experiments on linearly constrained test problems show that SHGO gives competitive results compared to TGO and the recently developed Lc-DISIMPL algorithm as well as the PSwarm, LGO and DIRECT-L1 algorithms. Furthermore SHGO is compared with the TGO, basinhopping (BH) and differential evolution (DE) global optimisation algorithms over a large selection of black-box problems with bounds placed on the variables from the SciPy benchmarking test suite. A Python implementation of the SHGO and TGO algorithms published under a MIT license can be found from https://bitbucket.org/upiamcompthermo/shgo/.     

Optimisation of road vehicle passive suspension systems. Part 1. Optimisation algorithm and vehicle model

Numerous problems have in the past been experienced during the development of military vehicle suspension systems. In order to solve some of these problems a two-dimensional multi-body vehicle dynamics simulation model has been developed for computer implementation. This model is linked to a mathematical optimisation algorithm in order to enable the optimisation of vehicle design parameters through the minimisation of a well defined objective function. In part 1 of this paper the concept of multi-disciplinary design optimisation is discussed. This is followed by the presentation of the up to six degrees of freedom vehicle model developed for this study, and a discussion of the specific gradient-based optimisation algorithm selected for the optimisation. In particular the derivation of the set of second-order differential equations, describing the acceleration of the different solid bodies of the vehicle model, is presented. In order to perform the optimisation of the non-linear suspension component characteristics, a six piece-wise continuous and linear approximation is used which is also described in this paper. Part 2 of this study will outline the simulation programme and the qualification of the programme. It will also present a typical case study where the proposed optimisation methodology is applied to improve the damper characteristics of a specific vehicle.     

Maintenance scheduling of rolling stock using a genetic algorithm

We have developed a Genetic algorithm (GA) for the optimisation of maintenance overhaul scheduling of rolling stock (trains) at the Hong Kong Mass Transit Railway Corporation (MTRC). The problem is one of combinatorial optimisation. Genetic algorithms (GAs) belong to the class of heuristic optimisation techniques that utilise randomisation as well as directed smart search to seek the global optima. The workshop at MTRC does have difficulties in establishing good schedules for the overhaul maintenance of the rolling stock. Currently, an experienced scheduler at MTRC performs this task manually. In this paper, we study the problem in a scientific manner and propose ways in which the task can be automated with the help of an algorithm embedded in a computer program. The algorithm enables the scheduler to establish the annual maintenance schedule of the trains in an efficient manner; the objective being to satisfy the maintenance requirements of various units of the trains as closely as possible to their due dates since there is a cost associated with undertaking the maintenance tasks either `too early’ or ‘too late’. The genetic algorithm developed is found to be very effective for solving this intractable problem. Computational results indicate that the genetic algorithm consistently provides significantly better schedules than those established manually at MTRC. More over, we provide evidence that the algorithm delivers close to optimal solutions for randomly generated problems with known optimal solutions. We also propose a local search method to reconfigure the trains in order to improve the schedule and to balance the work load of the overhaul maintenance section of the workshop throughout the planning horizon. We demonstrate that the reconfiguration of trains improves the schedule and reduces cost significantly.     

Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree

The Degree Constrained Minimum Spanning Tree (DCMST) on a graph is the problem of generating a minimum spanning tree with constraints on the number of arcs that can be incident to vertices of the graph. In this paper we develop three heuristics for the DCMST, including simulated annealing, a genetic algorithm and a method based on problem space search. We propose alternative tree representations to facilitate the neighbourhood searches for the genetic algorithm. The tree representation that we use for the genetic algorithm can be generalised to other tree optimisation problems as well. We compare the computational performance of all of these approaches against the performance of an exact solution approach in the literature. In addition, we also develop a new exact solution approach based on the combinatorial structure of the problem. We test all of these approaches using standard problems taken from the literature and some new test problems that we generate.     

DSLC-FOA : Improved fruit fly optimization algorithm for application to structural engineering design optimization problems

In this study, we propose an improved fruit fly optimization algorithm (FOA) based on linear diminishing step and logistic chaos mapping (named DSLC-FOA) for solving benchmark function unconstrained optimization problems and constrained structural engineering design optimization problems. Based on comparisons with genetic algorithm, particle swarm optimization, FOA, LGMS -FOA, and chaotic FOA methods, we demonstrated that DSLC-FOA performed better at searching for the optimal solutions of four typical benchmark functions. The approximate optimal results were obtained using DSLC-FOA for three structural engineering design optimization problems as examples of applications. The numerical results demonstrated that the proposed DSLC-FOA algorithm is superior to the basic FOA and other metaheuristic or deterministic methods.     

Using tree search bounds to enhance a genetic algorithm approach to two rectangle packing problems

A popular approach when using a genetic algorithm in the solution of constrained problems is to exploit problem specific information by representing individuals as ordered lists. A construction heuristic is then often used as a decoder to produce a solution from each ordering. In such a situation further information is often available in the form of bounds on the partial solutions. This paper uses two two-dimensional packing problems to illustrate how this information can be incorporated into the genetic operators to improve the overall performance of the search. Our objective is to use the packing problems as a vehicle for investigating a series of modifications of the genetic algorithm approach based on information from bounds on partial solutions.     

Optimal design of a hoist structure frame

In an attempt to find the most cost effective design of a multipurpose hoisting device that can be easily mounted on and removed from a regular farm vehicle, cost optimisation including both material and manufacturing expenditure, is performed on the main frame supporting the device. The optimisation is constrained by local and global buckling and fatigue conditions. Implementation of Snyman’s gradient-based LFOPC optimisation algorithm to the continuous optimisation problem, results in the economic determination of an unambiguous continuous solution, which is then utilised as the starting point for a neighbourhood search within the discrete set of profiles available, to attain the discrete optimum.

This optimum is further investigated for a different steel grade and for the manufacturing and material cost pertaining to different countries. The effect of variations in the formulation of the objective function for optimisation is also investigated. The results indicate that considerable cost benefits can be obtained by optimisation, that costing in different countries do not necessarily result in the same most cost effective design, and that accurate formulation of the objective function, i.e. realistic mathematical modelling, is of utmost importance in obtaining the intended design optimum.     

Optimisation of road vehicle passive suspension systems. Part 2. Qualification and case study

As an aid during the concept design phase, the two-dimensional vehicle simulation programme Vehsim2d has been developed (see part 1 of this paper for the vehicle model). The leap-frog optimisation algorithm for constrained problems (LFOPC) has been linked to the multi-body dynamics simulation code (Vehsim2d) to enable the computationally economic optimisation of certain vehicle and suspension design variables. This paper describes the simulation programme, the qualification of the programme, and gives an example of the application of the Vehsim2d/LFOPC system. In particular it is used to optimise the damper characteristics of an existing 22 ton three axle vehicle, over a typical terrain and at a representative speed. By using this system the optimised damper characteristics with respect to ride comfort for the vehicle are computed. The optimum damper characteristics give a 28.5% improvement in the ride comfort of the vehicle over the specified terrain and prescribed speed. Further optimisation runs were performed considering other terrain and different speed values. From these results final damper characteristics for the vehicle are proposed. Using the proposed characteristics, simulations were performed with the more advanced and proven DADS programme. The results show that the damper suggested by the optimisation study is indeed likely to improve the suspension of the vehicle. This study proves that the Vehsim2d/LFOPC vehicle modelling and optimisation system is indeed a valuable tool for a vehicle design team.     

An improved penalty function method for solving constrained parameter optimization problems

An effective algorithm is described for solving the general constrained parameter optimization problem. The method is quasi-second-order and requires only function and gradient information. An exterior point penalty function method is used to transform the constrained problem into a sequence of unconstrained problems. The penalty weightr is chosen as a function of the pointx such that the sequence of optimization problems is computationally easy. A rank-one optimization algorithm is developed that takes advantage of the special properties of the augmented performance index. The optimization algorithm accounts for the usual difficulties associated with discontinuous second derivatives of the augmented index. Finite convergence is exhibited for a quadratic performance index with linear constraints; accelerated convergence is demonstrated for nonquadratic indices and nonlinear constraints. A computer program has been written to implement the algorithm and its performance is illustrated in fourteen test problems.     

Gradient projection and local region search for multiobjective optimisation

This paper presents a new method for multiobjective optimisation based on gradient projection and local region search. The gradient projection is conducted through the identification of normal vectors of an efficient frontier. The projection of the gradient of a nonlinear utility function onto the tangent plane of the efficient frontier at a given efficient solution leads to the definition of a feasible local region in a neighbourhood of the solution. Within this local region, a better efficient solution may be sought. To implement such a gradient-based local region search scheme, a new auxiliary problem is developed. If the utility function is given explicitly, this search scheme results in an iterative optimisation algorithm capable of general nonseparable multiobjective optimisation. Otherwise, an interactive decision making algorithm is developed where the decision maker (DM) is expected to provide local preference information in order to determine trade-off directions and step sizes. Optimality conditions for the algorithms are established and the convergence of the algorithms is proven. A multiobjective linear programming (MOLP) problem is taken for example to demonstrate this method both graphically and analytically. A nonlinear multiobjective water quality management problem is finally examined to show the potential application of the method to real world decision problems.     

Uncertainty quantification of multi-dimensional parameters for composite laminates based on grey mathematical theory

In order to perform uncertainty quantification of elastic mechanical properties for composite laminates with multi-dimensional parameters, this paper is to develop a novel quantification approach based on grey mathematical theory. Here, uncertain parameters are modeled as correlated interval variables by virtue of some limited experimental points. The developed method not only can eliminate big errors in experimental points, but also can estimate uncertain information including nominal values, uncertain intervals, auto and mutual uncertainties of elastic properties. Besides, it can give out feasible domains of mechanical properties when considering mutual uncertainties for uncertainty propagation analysis. The numerical examples are implemented to demonstrate the feasibility and availability of the developed method. The results show that the developed method can become an important and powerful tool for uncertainty quantification of composite laminates with mutual uncertainties.     

A mixture experiments multi-objective hyper-heuristic

This paper proposes a hyper-heuristic that combines genetic algorithm with mixture experiments to solve multi-objective optimisation problems. At every iteration, the proposed algorithm combines the selection criterion (rank indicator) of a number of well-established evolutionary algorithms including NSGA-II, SPEA2 and two versions of IBEA. Each indicator is called according to an associated probability calculated and updated during the search by means of mixture experiments. Mixture experiments are a particular type of experimental design suitable for the calibration of parameters that represent probabilities. Their main output is an explanatory model of algorithm performance as a function of its parameters. By finding the maximum (probability distribution) of the surface represented by this model, we also find a good algorithm parameterisation. The design of mixture experiments approach allowed the authors to identify and exploit synergies between the different rank indicators at the different stages of the search. This is demonstrated by our experimental results in which the proposed algorithm compared favourably against other well-established algorithms.     

General iterative methods for equilibrium and constrained convex minimization problem

The gradient-projection algorithm (GPA) plays an important role in solving constrained convex minimization problems. Based on Marino and Xu's method [G. Marino and H.-K. Xu, A general method for nonexpansive mappings in Hilbert space, J. Math. Anal. Appl. 318 (2006), pp. 43–52], we combine GPA and averaged mapping approach to propose implicit and explicit composite iterative algorithms for finding a common solution of an equilibrium and a constrained convex minimization problem for the first time in this article. Under suitable conditions, strong convergence theorems are obtained.     

A reduced Hessian method for constrained optimization

Reduced Hessian methods have been shown to be successful for equality constrained problems. However there are few results on reduced Hessian methods for general constrained problems. In this paper we propose a method for general constrained problems, based on Byrd and Schnabel's basis-independent algorithm. It can be regarded as a smooth extension of the standard reduced Hessian Method.Research supported in part by NSF, AFORS and ONR through NSF grant DMS-8920550.     

The development of a multi-objective Tabu Search algorithm for continuous optimisation problems

While there have been many adaptations of some of the more popular meta-heuristics for continuous multi-objective optimisation problems, Tabu Search has received relatively little attention, despite its suitability and effectiveness on a number of real-world design optimisation problems. In this paper we present an adaptation of a single-objective Tabu Search algorithm for multiple objectives. Further, inspired by path relinking strategies common in discrete optimisation problems, we enhance our algorithm to allow it to handle problems with large numbers of design variables. This is achieved by a novel parameter selection strategy that, unlike a full parametric analysis, avoids the use of objective function evaluations, thus keeping the overall computational cost of the procedure to a minimum. We assess the performance of our two Tabu Search variants on a range of standard test functions and compare it to a leading multi-objective Genetic Algorithm, NSGA-II. The path relinking-inspired parameter selection scheme gives a clear performance improvement over the basic multi-objective Tabu Search adaptation and both variants perform comparably with the NSGA-II.     

An interval entropy method for equality constrained multiobjective optimization problems

Based on the maximum entropy principle and the idea of a penalty function, an evaluation function is derived to solve multiobjective optimization problems with equality constraints. Combining with interval analysis method, we define a generalized Krawczyk operator, design interval iteration with constrained functions and new region deletion test rules, present an interval algorithm for equality constrained multiobjective optimization problems, and also prove relevant properties. A theoretical analysis and numerical results indicate that the algorithm constructed is effective and reliable.     

A meta-heuristic approach for solving the Urban Network Design Problem

This paper proposes an optimisation model and a meta-heuristic algorithm for solving the urban network design problem. The problem consists in optimising the layout of an urban road network by designing directions of existing roads and signal settings at intersections. A non-linear constrained optimisation model for solving this problem is formulated, adopting a bi-level approach in order to reduce the complexity of solution methods and the computation times. A Scatter Search algorithm based on a random descent method is proposed and tested on a real dimension network. Initial results show that the proposed approach allows local optimal solutions to be obtained in reasonable computation times.     

Vector maximisation and lagrange multipliers

The Lagrangean function for scalar constrained optimisation problems is extended in a directly analogous manner to constrained vector optimisation problems. Some simple saddle point results are presented for vector maxima sets. Conditions are given for the characterisation of the vector maximum set of the original vector problem in terms of the vector maximum sets with respect to the vector Lagrangeans. Finally some attention is given to Lagrangean relaxation for vector optimisation problems as an extension of a result of Everett.