Metaheuristics: review and application

The area of metaheuristics has grown immensely in the past two decades as a solution to real-world optimisation problems. They are able to perform well in situations where exact optimisation techniques fail to deliver satisfactory results. For complex optimisation problems (Nondeterministic polynomial time-hard problems), metaheuristic techniques are able to generate good quality solution in relatively much less time than traditional optimisation techniques. Metaheuristics find applications in a wide range of areas including finance, planning, scheduling and engineering design. This paper presents a review of various metaheuristic algorithms, their methodology, recent trends and applications.     

Shape optimisation of continuum structures via evolution strategies and fixed grid finite element analysis

Evolution strategies (ES) are very robust and general techniques for finding global optima in optimisation problems. As with all evolutionary algorithms, ES apply evolutionary operators and select the most fit from a set of possible solutions. Unlike genetic algorithms, ES do not use binary coding of individuals, working instead with real variables. Many recent studies have applied evolutionary algorithms to structural problems, particularly the optimisation of trusses. This paper focuses on shape optimisation of continuum structures via ES. Stress analysis is accomplished by using the fixed grid finite element method, which reduces the computing time while keeping track of the boundary representation of the structure. This boundary is represented by b-spline functions, circles, and polylines, whose control points constitute the parameters that govern the shape of the structure. Evolutionary operations are applied to each set of variables until a global optimum is reached. Several numerical examples are presented to illustrate the performance of the method. Finally, structures with multiple load cases are considered along with examples illustrating the results obtained.     

Differential evolution and differential ant-stigmergy on dynamic optimisation problems

Many real-world optimisation problems are of dynamic nature, requiring an optimisation algorithm which is able to continuously track a changing optimum over time. To achieve this, we propose two population-based algorithms for solving dynamic optimisation problems (DOPs) with continuous variables: the self-adaptive differential evolution algorithm (jDE) and the differential ant-stigmergy algorithm (DASA). The performances of the jDE and the DASA are evaluated on the set of well-known benchmark problems provided for the special session on Evolutionary Computation in Dynamic and Uncertain Environments. We analyse the results for five algorithms presented by using the non-parametric statistical test procedure. The two proposed algorithms show a consistently superior performance over other recently proposed methods. The results show that both algorithms are appropriate candidates for DOPs.     

An overview of population-based algorithms for multi-objective optimisation

In this work we present an overview of the most prominent population-based algorithms and the methodologies used to extend them to multiple objective problems. Although not exact in the mathematical sense, it has long been recognised that population-based multi-objective optimisation techniques for real-world applications are immensely valuable and versatile. These techniques are usually employed when exact optimisation methods are not easily applicable or simply when, due to sheer complexity, such techniques could potentially be very costly. Another advantage is that since a population of decision vectors is considered in each generation these algorithms are implicitly parallelisable and can generate an approximation of the entire Pareto front at each iteration. A critique of their capabilities is also provided.     

Cauchy Grey Wolf Optimiser for continuous optimisation problems

ABSTRACT

Grey Wolf Optimiser (GWO) is a recently developed optimisation approach to solve complex non-linear optimisation problems. It is relatively simple and leadership-hierarchy based approach in the class of Swarm Intelligence based algorithms. For solving complex real-world non-linear optimisation problems, the search equation provided in GWO is not of sufficient explorative behaviour. Therefore, in the present paper, an attempt has been made to increase the exploration capability along with the exploitation of a search space by proposing an improved version of classical GWO. The proposed algorithm is named as Cauchy-GWO. In Cauchy-GWO Cauchy operator has been integrated in which first two new wolves are generated with the help of Cauchy distributed random numbers and then another new wolf is generated by taking the convex combination of these new wolves. The performance of Cauchy-GWO is exhibited on standard IEEE CEC 2014 benchmark problem set. Statistical analysis of the results on CEC 2014 benchmark set and popular evaluation criteria, Performance Index (PI) proves that Cauchy-GWO outperforms GWO in terms of error values defined in IEEE CEC 2014 benchmarks collection. Later on in the paper, GWO and Cauchy-GWO algorithms have been used to solve three well-known engineering application problems and two problems of reliability. From the analysis conducted in the present paper, it can be concluded that the proposed algorithm, Cauchy-GWO is reliable and efficient algorithm to solve continuous benchmark test problems, as well as real-life applications problems.     

On the application of graph colouring techniques in round-robin sports scheduling

The purpose of this paper is twofold. First, it explores the issue of producing valid, compact round-robin sports schedules by considering the problem as one of graph colouring. Using this model, which can also be extended to incorporate additional constraints, the difficulty of such problems is then gauged by considering the performance of a number of different graph colouring algorithms. Second, neighbourhood operators are then proposed that can be derived from the underlying graph colouring model and, in an example application, we show how these operators can be used in conjunction with multi-objective optimisation techniques to produce high-quality solutions to a real-world sports league scheduling problem encountered at the Welsh Rugby Union in Cardiff, Wales.     

Multi-objective evolutionary simulation-optimisation of a real-world manufacturing problem

Many real-world manufacturing problems are too complex to be modelled analytically. For these problems, simulation can be a powerful tool for system analysis and optimisation. While traditional optimisation methods have been unable to cope with the complexities of many problems approached by simulation, evolutionary algorithms have proven to be highly useful. This paper describes how simulation and evolutionary algorithms have been combined to improve a manufacturing cell at Volvo Aero in Sweden. This cell produces high-technology engine components for civilian and military airplanes, and also for space rockets. Results from the study show that by using simulation and evolutionary algorithms, it is possible to increase the overall utilisation of the cell and at the same time decrease the number of overdue components.     

Swarm intelligence algorithms for macroscopic traffic flow model validation with automatic assignment of fundamental diagrams

This paper is concerned with the problem of macroscopic road traffic flow model calibration and verification. Thoroughly validated models are necessary for both control system design and scenario evaluation purposes. Here, the second order traffic flow model METANET was calibrated and verified using real data.A powerful optimisation problem formulation is proposed for identifying a set of model parameters that makes the model fit to measurements. For the macroscopic traffic flow model validation problem, this set of parameters characterise the aggregate traffic flow features over a road network. In traffic engineering, one of the most important relationships whose parameters need to be determined is the fundamental diagram of traffic, which models the non-linear relationship between vehicular flow and density. Typically, a real network does not exhibit the same traffic flow aggregate behaviour everywhere and different fundamental diagrams are used for covering different network areas. As a result, one of the initial steps of the validation process rests on expert engineering opinion assigning the spatial extension of fundamental diagrams. The proposed optimisation problem formulation allows for automatically determining the number of different fundamental diagrams to be used and their corresponding spatial extension over the road network, simplifying this initial step. Although the optimisation problem suffers from local minima, good solutions which generalise well were obtained.The design of the system used is highly generic and allows for a number of evolutionary and swarm intelligence algorithms to be used. Two UK sites have been used for testing it. Calibration and verification results are discussed in detail. The resulting models are able to capture the dynamics of traffic flow and replicate shockwave propagation.A total of ten different algorithms were considered and compared with respect to their ability to converge to a solution, which remains valid for different sets of data. Particle swarm optimisation (PSO) algorithms have proven to be particularly effective and provide the best results both in terms of speed of convergence and solution generalisation. An interesting result reported is that more recently proposed PSO algorithms were outperformed by older variants, both in terms of speed of convergence and model error minimisation.     

Estimating meme fitness in adaptive memetic algorithms for combinatorial problems

Among the most promising and active research areas in heuristic optimisation is the field of adaptive memetic algorithms (AMAs). These gain much of their reported robustness by adapting the probability with which each of a set of local improvement operators is applied, according to an estimate of their current value to the search process. This paper addresses the issue of how the current value should be estimated. Assuming the estimate occurs over several applications of a meme, we consider whether the extreme or mean improvements should be used, and whether this aggregation should be global, or local to some part of the solution space. To investigate these issues, we use the well-established COMA framework that coevolves the specification of a population of memes (representing different local search algorithms) alongside a population of candidate solutions to the problem at hand. Two very different memetic algorithms are considered: the first using adaptive operator pursuit to adjust the probabilities of applying a fixed set of memes, and a second which applies genetic operators to dynamically adapt and create memes and their functional definitions. For the latter, especially on combinatorial problems, credit assignment mechanisms based on historical records, or on notions of landscape locality, will have limited application, and it is necessary to estimate the value of a meme via some form of sampling. The results on a set of binary encoded combinatorial problems show that both methods are very effective, and that for some problems it is necessary to use thousands of variables in order to tease apart the differences between different reward schemes. However, for both memetic algorithms, a significant pattern emerges that reward based on mean improvement is better than that based on extreme improvement. This contradicts recent findings from adapting the parameters of operators involved in global evolutionary search. The results also show that local reward schemes outperform global reward schemes in combinatorial spaces, unlike in continuous spaces. An analysis of evolving meme behaviour is used to explain these findings.     

An iterative approach to robust and integrated aircraft routing and crew scheduling

In airline scheduling a variety of planning and operational decision problems have to be solved. We consider the problems aircraft routing and crew pairing: aircraft and crew must be allocated to flights in a schedule in a minimal cost way. Although these problems are not independent, they are usually formulated as independent mathematical optimisation models and solved sequentially. This approach might lead to a suboptimal allocation of aircraft and crew, since a solution of one of the problems may restrict the set of feasible solutions of the problem solved later. Also, when minimal cost solutions are used in operations, a short delay of one flight can cause very severe disruptions of the schedule later in the day. We generate solutions that incur small costs and are also robust to typical stochastic variability in airline operations. We solve the two original problems iteratively. Starting from a minimal cost solution, we produce a series of solutions which are increasingly robust. Using data from domestic airline schedules we evaluate the benefits of the approach as well as the trade-off between cost and robustness. We extend our approach considering the aircraft routing problem together with two crew pairing problems, one for technical crew and one for flight attendants.     

Operations research in the high-level synthesis of integrated circuits

The acceptance of high-level synthesis tools and methodologies by the design engineers depends on their efficiency in producing circuits with small silicon areas and high operating speeds. This paper shows how this efficiency can be achieved through the use of several operations research techniques applied to the many optimization problems that must be solved. These include: shortest path algorithms, integer programming techniques applied to silicon area minimization, force directed scheduling to optimize the number of operators and cost/speed trade-offs of logical gates. This paper presents several examples providing an operations research solution to each of them.     

Including stakeholder input in formulating and solving real-world optimisation problems: Generic framework and case study

Multi-objective evolutionary algorithms (MOEAs) are becoming increasingly popular for solving formal environmental and water resources optimisation problems. In the past, the focus of these studies has generally been on methodological issues related to the optimisation algorithm. However, in recent years, there has been increased recognition of the need to apply these approaches to real-world problems to facilitate the realisation of their full potential. In order to assist with this, a framework for including stakeholder input in real-world optimisation problems is introduced in this paper, including a conceptual framework and a procedure for implementing it. The framework is applied to an urban water supply security study for Adelaide, South Australia. This study highlights the role of stakeholder input at the various stages of the optimisation process, as well as the resulting changes in the formulation, analysis and results. A discussion of the lessons learnt from the case study is also provided.     

Scheduling in a dynamic heterogeneous distributed system using estimation error

In real-world dynamic heterogeneous distributed systems, allocating tasks to processors can be an inefficient process, due to the dynamic nature of the resources, and the tasks to be processed. The information about these tasks and resources is not known a priori, and thus must be estimated online. We utilize the accuracy of these estimates, and when combined with different objectives, such as minimizing makespan and evenly distributing load, naturally gives rise to a family of four different scheduling algorithms. The algorithms have been implemented on a real-world heterogeneous distributed system with up to 90 processors. A set of real-world problems from the areas of cryptography, bioinformatics, and biomedical engineering were used as a test-set to measure the effectiveness of the scheduling algorithms. We have found that considering estimation error when allocating tasks to processors can provide more efficient solutions, than when estimation error is not considered. We have found that using a simple heuristic, combined with estimation error, can in some cases provide solutions approaching the efficiency of complicated well-known evolutionary algorithms.     

Memetic algorithms based on local search chains for large scale continuous optimisation problems: MA-SSW-Chains

Nowadays, large scale optimisation problems arise as a very interesting field of research, because they appear in many real-world problems (bio-computing, data mining, etc.). Thus, scalability becomes an essential requirement for modern optimisation algorithms. In a previous work, we presented memetic algorithms based on local search chains. Local search chain concerns the idea that, at one stage, the local search operator may continue the operation of a previous invocation, starting from the final configuration reached by this one. Using this technique, it was presented a memetic algorithm, MA-CMA-Chains, using the CMA-ES algorithm as its local search component. This proposal obtained very good results for continuous optimisation problems, in particular with medium-size (with up to dimension 50). Unfortunately, CMA-ES scalability is restricted by several costly operations, thus MA-CMA-Chains could not be successfully applied to large scale problems. In this article we study the scalability of memetic algorithms based on local search chains, creating memetic algorithms with different local search methods and comparing them, considering both the error values and the processing cost. We also propose a variation of Solis Wets method, that we call Subgrouping Solis Wets algorithm. This local search method explores, at each step of the algorithm, only a random subset of the variables. This subset changes after a certain number of evaluations. Finally, we propose a new memetic algorithm based on local search chains for high dimensionality, MA-SSW-Chains, using the Subgrouping Solis Wets’ algorithm as its local search method. This algorithm is compared with MA-CMA-Chains and different reference algorithms, and it is shown that the proposal is fairly scalable and it is statistically very competitive for high-dimensional problems.     

Algebraic query optimisation for database programming languages

A major challenge still facing the designers and implementors of database programming languages (DBPLs) is that of query optimisation. We investigate algebraic query optimisation techniques for DBPLs in the context of a purely declarative functional language that supports sets as first-class objects. Since the language is computationally complete issues such as non-termination of expressions and construction of infinite data structures can be investigated, whilst its declarative nature allows the issue of side effects to be avoided and a richer set of equivalences to be developed. The language has a well-defined semantics which permits us to reason formally about the properties of expressions, such as their equivalence with other expressions and their termination. The support of a set bulk data type enables much prior work on the optimisation of relational languages to be utilised. In the paper we first give the syntax of our archetypal DBPL and briefly discuss its semantics. We then define a small but powerful algebra of operators over the set data type, provide some key equivalences for expressions in these operators, and list transformation principles for optimising expressions. Along the way, we identify some caveats to well-known equivalences for non-deductive database languages. We next extend our language with two higher level constructs commonly found in functional DBPLs: set comprehensions and functions with known inverses. Some key equivalences for these constructs are provided, as are transformation principles for expressions in them. Finally, we investigate extending our equivalences for the set operators to the analogous operators over bags. Although developed and formally proved in the context of a functional language, our findings are directly applicable to other DBPLs of similar expressiveness. Edited by Matthias Jarke, Jorge Bocca, Carlo Zaniolo. Received September 15, 1994 / Accepted September 1, 1995     

Benchmarking and comparison of nature-inspired population-based continuous optimisation algorithms

This paper describes an experimental investigation into four nature-inspired population-based continuous optimisation methods: the Bees Algorithm, Evolutionary Algorithms, Particle Swarm Optimisation, and the Artificial Bee Colony algorithm. The aim of the proposed study is to understand and compare the specific capabilities of each optimisation algorithm. For each algorithm, thirty-two configurations covering different combinations of operators and learning parameters were examined. In order to evaluate the optimisation procedures, twenty-five function minimisation benchmarks were designed by the authors. The proposed set of benchmarks includes many diverse fitness landscapes, and constitutes a contribution to the systematic study of optimisation techniques and operators. The experimental results highlight the strengths and weaknesses of the algorithms and configurations tested. The existence and extent of origin and alignment search biases related to the use of different recombination operators are highlighted. The analysis of the results reveals interesting regularities that help to identify some of the crucial issues in the choice and configuration of the search algorithms.     

Memetic cooperative coevolution of Elman recurrent neural networks

Cooperative coevolution decomposes an optimisation problem into subcomponents and collectively solves them using evolutionary algorithms. Memetic algorithms provides enhancement to evolutionary algorithms with local search. Recently, the incorporation of local search into a memetic cooperative coevolution method has shown to be efficient for training feedforward networks on pattern classification problems. This paper applies the memetic cooperative coevolution method for training recurrent neural networks on grammatical inference problems. The results show that the proposed method achieves better performance in terms of optimisation time and robustness.     

Optimisation With Real-Coded Genetic Algorithms Based On Mathematical Morphology

The goal of this work is to propose a novel approach to function optimisation by evolutionary techniques, in particular, real-coded genetic algorithms. A new genetic crossover operator, suitable for real codification, has been designed. This operator is called morphological crossover as it is based on mathematical morphology theory. The morphological crossover includes a new genetic diversity measure that has low computational cost. This operator is presented along with the resolution of a set of optimisation problems, including neural network training. The results are compared to other optimisation approaches as gradient descent methods or binary and real-coded genetic algorithms using different crossover operators. These tests show that the properties exhibited by the proposed operator when using real-coded genetic algorithms give higher convergence speed and less probability of being trapped in a local optimum.     

Arbitrary function optimisation with metaheuristics

No free lunch theorems for optimisation suggest that empirical studies on benchmarking problems are pointless, or even cast negative doubts, when algorithms are being applied to other problems not clearly related to the previous ones. Roughly speaking, reported empirical results are not just the result of algorithms’ performances, but the benchmark used therein as well; and consequently, recommending one algorithm over another for solving a new problem might be always disputable. In this work, we propose an empirical framework, arbitrary function optimisation framework, that allows researchers to formulate conclusions independent of the benchmark problems that were actually addressed, as long as the context of the problem class is mentioned. Experiments on sufficiently general scenarios are reported with the aim of assessing this independence. Additionally, this article presents, to the best of our knowledge, the first thorough empirical study on the no free lunch theorems, which is possible thanks to the application of the proposed methodology, and whose main result is that no free lunch theorems unlikely hold on the set of binary real-world problems. In particular, it is shown that exploiting reasonable heuristics becomes more beneficial than random search when dealing with binary real-world applications.     

String similarity search and join: a survey

String similarity search and join are two important operations in data cleaning and integration, which extend traditional exact search and exact join operations in databases by tolerating the errors and inconsistencies in the data. They have many real-world applications, such as spell checking, duplicate detection, entity resolution, and webpage clustering. Although these two problems have been extensively studied in the recent decade, there is no thorough survey. In this paper, we present a comprehensive survey on string similarity search and join. We first give the problem definitions and introduce widely-used similarity functions to quantify the similarity. We then present an extensive set of algorithms for string similarity search and join. We also discuss their variants, including approximate entity extraction, type-ahead search, and approximate substring matching. Finally, we provide some open datasets and summarize some research challenges and open problems.