Advances in Metaheuristics for Hard Optimization

The continuous Constrained Optimization Problem (COP) often occurs in industrial applications. In this study, we compare three novel algorithms developed for solving the COP.The first approach consists of an Interval Partitioning Algorithm (IPA) that is exhaustive in covering the whole feasible space. IPA has the capability of discarding sub-spaces that are sub-optimal and/or infeasible, similar to available Branch and Bound techniques. The difference of IPA lies in its use of Interval Arithmetic rather than conventional bounding techniques described in the literature. The second approach tested here is the novel dual-sequence Simulated Annealing (SA) algorithm that eliminates the use of penalties for constraint handling. Here, we also introduce a hybrid algorithm that integrates SA in IPA (IPA-SA) and compare its performance with stand-alone SA and IPA algorithms. All three methods have a local COP solver, Feasible Sequential Quadratic Programming (FSQP) incorporated so as to identify feasible stationary points. The performances of these three methods are tested on a suite of COP benchmarks and the results are discussed.

This chapter presents an alternative method of linkage synthesis (finding link lengths and its initial position) using a computational intelligence technique: Simulated Annealing. The technique allows one to define n desired path points to be followed by a four-bar linkage (path generation problem). The synthesis problem is transformed into an optimization problem in order to use the Simulated Annealing algorithm. With this approach, a path can be better specified since the user will be able to provide more “samples” than the usual limited number of five allowed by the classical methods. Several examples are shown to demonstrate the advantages of this alternative synthesis technique.

This chapter introduces a new version of our multiobjective scatter search to deal with nonlinear continuous vector optimization problems, applying a multi-star tabu search (TS) and convex combinationmethods as a diversification generationmethod. A new mechanism of forbidden solutions to create different families of subsets of solutions to be combined, is applied in this version. Aconstrain-handlingmechanism is incorporated to deal with constrained problems. Theperformance of our approach is compared with ourMOSS implementation for some bi-objective unconstrained test problems, 3-objective test problems were compared with points of the Paretooptimal front, and our constraint-handling mechanism is illustrated.

The nearest-neighbour (NN) classifier has long been used in pattern recognition, exploratory data analysis, and data mining problems. A vital consideration in obtaining good results with this technique is the choice of distance function, and correspondingly which features to consider when computing distances between samples. In this chapter, a new ensemble technique is proposed to improve the performance of NNclassifiers.The proposed approach combinesmultiple NNclassifiers, where each classifier uses a different distance function and potentially a different set of features (feature vector). These feature vectors are determined for each distance metric using a Simple Voting Scheme incorporated in Tabu Search (TS). The proposed ensemble classifier with different distance metrics and different feature vectors (TS–DF/NN) is evaluated using various benchmark data sets from the UCI Machine Learning Repository. Results have indicated a significant increase in the performance when compared with various well-known classifiers. The proposed ensemble method is also compared with an ensemble classifier using different distance metrics but with the same feature vector (with or without Feature Selection (FS)).

In this work, we introduce a new parallel ant colony optimization algorithm based on an ant metaphor and the crossover operator from genetic algorithms.The performance of the proposed model is evaluated usingwell-known numerical test problems and then it is applied to train recurrent neural networks to identify linear and nonlinear dynamic plants. The simulation results are compared with results using other algorithms.

In this chapter we present the integration of an ant-based algorithm with a greedy algorithm for optimizing the scheduling of a multistage plant in the consumer packaged goods industry. The multistage manufacturing plant is comprised of different stages: mixing, storage, packing and finished goods storage, and is an extension of the classic Flowshop Scheduling Problem (FSP).We propose a new algorithm for the Multistage Flowshop Scheduling Problem (MSFSP) for finding optimized solutions. Theschedulingmust provide both optimal and flexible solutions to respond to fluctuations in the demand and operations of the plants while minimizing costs and times of operation. Optimization of each stage in the plant is an increasingly complex task when considering limited capacity and connectivity of the stages, and the constraints they mutually impose on each other.

This chapter uses an ant colony meta-heuristic to optimally load balance code divisionmultiple access micro-cellular mobile communication systems. Load balancing is achieved by assigning each micro-cell to a sector.The cost function considers handoff cost and blocked calls cost, while the sectorization must meet a minimum level of compactness. The problem is formulated as a routing problem where the route of a single ant creates a sector of micro-cells. There is an ant for each sector in the system, multiple ants comprise a colony and multiple colonies operate to find the sectorization with the lowest cost. It is shown that the method is effective and highly reliable, and is computationally practical even for large problems.

The issue of setting the values of various parameters of an evolutionary algorithm (EA) is crucial for good performance. One way to do it is by controlling EA parameters on-the-fly, which can be done in various ways and for various parameters. We briefly review these options in general and present the findings of a literature search and some statistics about themost popular options. Thereafter, we provide three case studies indicating a high potential for uncommon variants. In particular, we recommend focusing on parameters regulating selection and population size, rather than those concerning crossover and mutation. On the technical side, the case study on adjusting tournament size shows by example that global parameters can also be selfadapted, and that heuristic adaptation and pure self-adaptation can be successfully combined into a hybrid of the two.

Memetic algorithms are hybridizations of evolutionary algorithms (EAs) with problem- specific heuristics or other meta-heuristics, that are generally used within the EA to locally improve the evolutionary solutions. However, this approach fails when the local method stops working on the complete problem. Divide-and-Evolve is an original approach that evolutionarily builds a sequential slicing of the problem at hand into several, hopefully easier, sub-problems: the embedded (meta-)heuristic is only asked to solve the ‘small’ problems, and Divide-and-Evolve is thus able to globally solve problems that are intractable when directly fed into the heuristic.The Divide and- Evolve approach is described here in the context of temporal planning problems (TPPs), and the results on the standard Zeno transportation benchmarks demonstrate its ability to indeed break the complexity barrier. But an even more prominent advantage of the Divide-and-Evolve approach is that it immediately opens up an avenue for multi-objective optimization, even when using single-objective embedded algorithm

Genetic Algorithms have been seen as search procedures that can quickly locate high performance regions of vast and complex search spaces, but they are not well suited for fine-tuning solutions, which are very close to optimal ones. However, genetic algorithms may be specifically designed to provide an effective local search as well. In fact, several genetic algorithm models have recently been presented with this aim. In this chapter, we call these algorithms Local Genetic Algorithms.

Cluster geometry optimization is an important problem from the Chemistry area. Hybrid approaches combining evolutionary algorithms and gradient-driven local search methods are one of the most efficient techniques to perform a meaningful exploration of the solution space to ensure the discovery of low energy geometries. Here we performa comprehensive study on the locality properties of this approach to gain insight to the algorithm’s strengths andweaknesses.Theanalysis is accomplished through the application of several static measures to randomly generated solutions in order to establish the main properties of an extended set of mutation and crossover operators. Locality analysis is complemented with additional results obtained from optimization runs. The combination of the outcomes allows us to propose a robust hybrid algorithm that is able to quickly discover the arrangement of the cluster’s particles that correspond to optimal or near-optimal solutions.

It is well known that Dynamic Time Warping (DTW) is superior to Euclidean distance as a similarity measure in time series analyses. Use of DTW with the recently introduced warping window constraints and lower bounding measures has significantly increased the accuracy of time series classification while reducing the computational expense required. The warping window technique learns arbitrary constraints on the warping path while performing time series alignment. This work utilizes genetic algorithms to find the optimal warping window constraints which provide a better classification accuracy. Performance of the proposed methodology has been investigated on two problems from diverse domains with favorable results.

Ubiquitous robot systems represent the state-of-the-art in robotic technology. This paradigm seamlessly blendsmobile robot technology (Mobot) with distributed sensor systems (Embot) and overseeing software intelligence (Sobot), for various integrated services. The wide scope for research in each component area notwithstanding, the design of the Sobot is critical since it performs the dual purpose of overseeing intelligence as well as user interface. The Sobot is hencemodeled as an Artificial Creature with autonomously driven behavior. This chapter discusses the evolutionary generation of an artificial creature’s personality. The artificial creature has its own genome in which each chromosome consists of many genes that contribute to defining its personality. The large number of genes also allows for a highly complex system. However, it becomes increasingly difficult and time-consuming to ensure reliability, variability and consistency for the artificial creature’s personality while manually assigning gene values for the individual genome. One effective approach to counter these problems is the Evolutionary Generative Process for an Artificial Creature’s Personality (EGPP) which forms the focus of this chapter. EGPP evolves a genome population such that it customizes the genome, meeting a simplified set of personality traits desired by the user. An evaluation procedure for each genome of the population is carried out in a virtual environment using tailored perception scenarios. Effectiveness of this scheme is demonstrated by using an artificial creature Sobot, ‘Rity’ in the virtual 3D world created in a PC, designed to be a believable interactive software agent for human–robot interaction.

In recent decades, a novel class of optimization techniques, namely metaheuristics, has been developed and devoted to the solution of highly combinatorial discrete problems.The improvements provided by these methods were extended to the continuous or mixed-integer optimization area. This chapter addresses the problem of adapting a Genetic Algorithm (GA) to a Mixed Integer Non-linear Programming (MINLP) problem.The basis of the work is optimal batch plant design, which is of great interest in the framework of Process Engineering. This study deals with the two main issues for GAs, i.e. the treatment of continuous variables by specific encoding and efficient constraints handling in GA. Various techniques are tested for both topics and numerical results show that the use of a mixed real-discrete encoding and a specific domination-based tournament method is the most appropriate approach.

Two approaches based on genetic algorithms (GA) to solve economic dispatch (ED) problems are presented. The first approach is based on the hybrid genetic algorithm (HGA). Undesirable premature convergence to local minima can be avoided by means of the mutation operator, which is used to create diversity in the population by penalization or perturbation. Nevertheless, HGA needs to tune parameters before starting a run. A coevolutionary hybrid genetic algorithm (COEHGA) is proposed to improve the performance of the HGA.The COEHGA effectively eliminates the parameter tuning process because the parameters are adjusted while running the algorithm. A case from the literature is studied to demonstrate these approaches.

In this chapter, we present an evolutionary approach to solve a novelmechatronic design problemof a pinion-rack continuously variable transmission (CVT).This problem is stated as a multiobjective optimization problem, because we concurrently optimize the mechanical structure and the controller performance, in order to produce mechanical, electronic and control flexibility for the designed system. The problem is solved first with a mathematical programming technique called the goal attainment method. Based on some shortcomings found, we propose a differential evolution (DE)-based approach to solve the aforementioned problem. The performance of both approaches (goal attainment and the modified DE) are compared and discussed, based on quality, robustness, computational time and implementation complexity. We also highlight the interpretation of the solutions obtained in the context of the application.

Air defense systems based onMANPortable Air Defense Systems (MANPADS) have demonstrated exceptional effectiveness against aircraft. To counter these systems, an artefact named flare was developed.

This chapter serves as an introduction to estimation of distribution algorithms (EDAs). Estimation of distribution algorithms are a new paradigm in evolutionary computation. They combine statistical learning with population-based search in order to automatically identify and exploit certain structural properties of optimization problems. State-of-the-art EDAs consistently outperformclassical genetic algorithms on a broad range of hard optimization problems.We review fundamental terms, concepts, and algorithms which facilitate the understanding of EDA research. The focus is on EDAs for combinatorial and continuous non-linear optimization and the major differences between the two fields are discussed.

Differential evolution (DE) and evolutionary programming (EP) are two major algorithms in evolutionary computation. They have been applied with success to many real-world numerical optimization problems. Neighborhood search (NS) is a main strategy underpinning EP.There have been analyses of different NS operators’ characteristics. Although DE might be similar to the evolutionary process in EP, it lacks the relevant concept of neighborhood search. In this chapter, DE with neighborhood search (NSDE) is proposed based on the generalization of NS strategy. The advantages of NS strategy in DE are analyzed theoretically. These analyses mainly focus on the change of search step size and population diversity after using neighborhood search. Experimental results have shown that DE with neighborhood search has significant advantages over other existing algorithms on a broad range of different benchmark functions. NSDE’s scalability is also evaluated on a number of benchmark problems, whose dimension ranges from 50 to 200.

In this chapter, we consider the issue of Hidden Markov Model (HMM) training. First, HMMs are introduced and then we focus on the particular HMM training problem. We emphasize the difficulty of this problem and present various criteria that can be considered.Many different adaptations of metaheuristics have been used but, until now, few extensive comparisons have been performed for this problem. We propose to compare three population-based metaheuristics (genetic algorithm, ant algorithm and particle swarm optimization) with and without the help of a local optimizer. These algorithms make use of solutions that can be explored in three different kinds of search space (a constrained space, a discrete space and a vector space). We study these algorithms from both a theoretical and an experimental perspective: parameter settings are fully studied on a reduced set of data and the performances of algorithms are compared on different sets of real data.

Recent adaptive memory and evolutionary metaheuristics for mixed integer programming have included proposals for introducing inequalities and target objectives to guide the search. These guidance approaches are useful in intensification and diversification strategies related to fixing subsets of variables at particular values, and in strategies that use linear programming to generate trial solutions whose variables are induced to receive integer values. We show how to improve such approaches by new inequalities that dominate those previously proposed and by associated target objectives that underlie the creation of both inequalities and trial solutions.