Metaheuristic optimization frameworks: a survey and benchmarking
---
paper_title: Meta-heuristics: The state of the art

paper_content:

Meta-heuristics support managers in decision-making with robust tools that provide high-quality solutions to important applications in business, engineering, economics and science in reasonable time horizons. In this paper we give some insight into the state of the art of meta-heuristics. This primarily focuses on the significant progress which general frames within the meta-heuristics field have implied for solving combinatorial optimization problems, mainly those for planning and scheduling.
---
paper_title: EASYLOCAL++: an object-oriented framework for flexible design of local search algorithms

paper_content:

Local search is a paradigm for search and optimization problems, which has recently evidenced to be very effective for a large number of combinatorial problems. Despite the increasing interest of the research community in this subject, there is still a lack of a widely-accepted software tools for local search.We propose EASYLOCAL++, an object-oriented framework for the design and the analysis of local-search algorithms. The abstract classes that compose the framework specify and implement the invariant part of the algorithm and are meant to be specialized by concrete classes that supply the problem-dependent part. The framework provides the full control structures of the algorithms, and the user has only to write the problem-specific code. Furthermore, the framework comes with some tools that simplify the analysis of the algorithms.The architecture of EASYLOCAL++ provides a principled modularization for the solution of combinatorial problems by local search and helps the user by deriving a neat conceptual scheme of the application. It also supports the design of combinations of basic techniques and/or neighborhood structures.The framework has been tested in some applicative domains and has proved to be flexible enough in the implementation of algorithms for the solution of various scheduling problems.
---
paper_title: Heuristics for Integer Programming Using Surrogate Constraints

paper_content:

This paper proposes a class of surrogate constraint heuristics for obtaining approximate, near optimal solutions to integer programming problems. These heuristics are based on a simple framework that illuminates the character of several earlier heuristic proposals and provides a variety of new alternatives. The paper also proposes additional heuristics that can be used either to supplement the surrogate constraint procedures or to provide independent solution strategies. Preliminary computational results are reported for applying one of these alternatives to a class of nonlinear generalized set covering problems involving approximately 100 constraints and 300–500 integer variables. The solutions obtained by the tested procedure had objective function values twice as good as values obtained by standard approaches (e.g., reducing the best objective function values of other methods from 85 to 40 on the average. Total solution time for the tested procedure ranged from ten to twenty seconds on the CDC 6600.
---
paper_title: Optimization Software Class Libraries

paper_content:

Many decision problems in business and engineering may be formulated as optimization problems. Optimization problems in practice are diverse, often complex and evolve over time, so one requires both ready-to-use optimization software packages and optimization software libraries, which provide more or less adaptable building blocks for application-specific software systems.
---
paper_title: ParadisEO: A Framework for the Reusable Design of Parallel and Distributed Metaheuristics

paper_content:

In this paper, we present the ParadisEO white-box object-oriented framework dedicated to the reusable design of parallel and distributed metaheuristics (PDM). ParadisEO provides a broad range of features including evolutionary algorithms (EA), local searches (LS), the most common parallel and distributed models and hybridization mechanisms, etc. This high content and utility encourages its use at European level. ParadisEO is based on a clear conceptual separation of the solution methods from the problems they are intended to solve. This separation confers to the user a maximum code and design reuse. Furthermore, the fine-grained nature of the classes provided by the framework allow a higher flexibility compared to other frameworks. ParadisEO is of the rare frameworks that provide the most common parallel and distributed models. Their implementation is portable on distributed-memory machines as well as on shared-memory multiprocessors, as it uses standard libraries such as MPI, PVM and PThreads. The models can be exploited in a transparent way, one has just to instantiate their associated provided classes. Their experimentation on the radio network design real-world application demonstrate their efficiency.
---
paper_title: Optimization by simulated annealing

paper_content:

There is a deep and useful connection between statistical mechanics (the behavior of systems with many degrees of freedom in thermal equilibrium at a finite temperature) and multivariate or combinatorial optimization (finding the minimum of a given function depending on many parameters). A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems. This connection to statistical mechanics exposes new information and provides an unfamiliar perspective on traditional optimization problems and methods.
---
paper_title: Simple Explanation of the No-Free-Lunch Theorem and Its Implications

paper_content:

The no-free-lunch theorem of optimization (NFLT) is an impossibility theorem telling us that a general-purpose, universal optimization strategy is impossible. The only way one strategy can outperform another is if it is specialized to the structure of the specific problem under consideration. Since optimization is a central human activity, an appreciation of the NFLT and its consequences is essential. In this paper, we present a framework for conceptualizing optimization that leads to a simple but rigorous explanation of the NFLT and its implications.
---
paper_title: No free lunch theorems for optimization

paper_content:

A framework is developed to explore the connection between effective optimization algorithms and the problems they are solving. A number of "no free lunch" (NFL) theorems are presented which establish that for any algorithm, any elevated performance over one class of problems is offset by performance over another class. These theorems result in a geometric interpretation of what it means for an algorithm to be well suited to an optimization problem. Applications of the NFL theorems to information-theoretic aspects of optimization and benchmark measures of performance are also presented. Other issues addressed include time-varying optimization problems and a priori "head-to-head" minimax distinctions between optimization algorithms, distinctions that result despite the NFL theorems' enforcing of a type of uniformity over all algorithms.
---
paper_title: Approximating the Nondominated Front Using the Pareto Archived Evolution Strategy

paper_content:

We introduce a simple evolution scheme for multiobjective optimization problems, called the Pareto Archived Evolution Strategy (PAES). We argue that PAES may represent the simplest possible nontrivial algorithm capable of generating diverse solutions in the Pareto optimal set. The algorithm, in its simplest form, is a (1 + 1) evolution strategy employing local search but using a reference archive of previously found solutions in order to identify the approximate dominance ranking of the current and candidate solution vectors. (1 + 1)-PAES is intended to be a baseline approach against which more involved methods may be compared. It may also serve well in some real-world applications when local search seems superior to or competitive with population-based methods. We introduce (1 + lambda) and (mu + lambda) variants of PAES as extensions to the basic algorithm. Six variants of PAES are compared to variants of the Niched Pareto Genetic Algorithm and the Nondominated Sorting Genetic Algorithm over a diverse suite of six test functions. Results are analyzed and presented using techniques that reduce the attainment surfaces generated from several optimization runs into a set of univariate distributions. This allows standard statistical analysis to be carried out for comparative purposes. Our results provide strong evidence that PAES performs consistently well on a range of multiobjective optimization tasks.
---
paper_title: Optimization Software Class Libraries

paper_content:

Many decision problems in business and engineering may be formulated as optimization problems. Optimization problems in practice are diverse, often complex and evolve over time, so one requires both ready-to-use optimization software packages and optimization software libraries, which provide more or less adaptable building blocks for application-specific software systems.
---
paper_title: Hybrid Metaheuristics: An Introduction

paper_content:

A modular piston having a high tensile strength piston and rod connection produced without lubrication, weld splatter or other contaminants. The method produces an optimized joint from strength, concentricity and cleanliness standpoints. The parts are centered and connected in the same operation. With this connection an elastomeric bumper and bumper containment plate are retained in position for a complete assembly.
---
paper_title: The CHC Adaptive Search Algorithm: How to Have Safe Search When Engaging in Nontraditional Genetic Recombination

paper_content:

Abstract This paper describes and analyzes CHC, a nontraditional genetic algorithm which combines a conservative selection strategy that always preserves the best individuals found so far with a radical (highly disruptive) recombination operator that produces offspring that are maximally different from both parents. The traditional reasons for preferring a recombination operator with a low probability of disrupting schemata may not hold when such a conservative selection strategy is used. On the contrary, certain highly disruptive crossover operators provide more effective search. Empirical evidence is provided to support these claims.
---
paper_title: A connectionist machine for genetic hillclimbing

paper_content:

1. Introduction.- 1.1. Satisfying hidden strong constraints.- 1.2. Function optimization.- 1.2.1. The methodology of heuristic search.- 1.2.2. The shape of function spaces.- 1.3. High-dimensional binary vector spaces.- 1.3.1. Graph partitioning.- 1.4. Dissertation overview.- 1.5. Summary.- 2. The model.- 2.1. Design goal: Learning while searching.- 2.1.1. Knowledge representation.- 2.1.2. Point-based search strategies.- 2.1.3. Population-based search strategies.- 2.1.4. Combination rules.- 2.1.5. Election rules.- 2.1.6. Summary: Learning while searching.- 2.2. Design goal: Sustained exploration.- 2.2.1. Searching broadly.- 2.2.2. Convergence and divergence.- 2.2.3. Mode transitions.- 2.2.4. Resource allocation via taxation.- 2.2.5. Summary: Sustained exploration.- 2.3. Connectionist computation.- 2.3.1. Units and links.- 2.3.2. A three-state stochastic unit.- 2.3.3. Receptive fields.- 2.4. Stochastic iterated genetic hillclimbing.- 2.4.1. Knowledge representation in SIGH.- 2.4.2. The SIGH control algorithm.- 2.4.3. Formal definition.- 2.5. Summary.- 3. Empirical demonstrations.- 3.1. Methodology.- 3.1.1. Notation.- 3.1.2. Parameter tuning.- 3.1.3. Non-termination.- 3.2. Seven algorithms.- 3.2.1. Iterated hillclimbing-steepest ascent (IHC-SA).- 3.2.2. Iterated hillclimbing-next ascent (IHC-NA).- 3.2.3. Stochastic hillclimbing (SHC).- 3.2.4. Iterated simulated annealing (ISA).- 3.2.5. Iterated genetic search-Uniform combination (IGS-U).- 3.2.6. Iterated genetic search-Ordered combination (IGS-O).- 3.2.7. Stochastic iterated genetic hillclimbing (SIGH).- 3.3. Six functions.- 3.3.1. A linear space-"One Max".- 3.3.2. A local maximum-"Two Max".- 3.3.3. A large local maximum-"Trap".- 3.3.4. Fine-grained local maxima-"Porcupine".- 3.3.5. Flat areas-"Plateaus".- 3.3.6. A combination space-"Mix".- 4. Analytic properties.- 4.1. Problem definition.- 4.2. Energy functions.- 4.3. Basic properties of the learning algorithm.- 4.3.1. Motivating the approach.- 4.3.2. Defining reinforcement signals.- 4.3.3. Defining similarity measures.- 4.3.4. The equilibrium distribution.- 4.4. Convergence.- 4.5. Divergence.- 5. Graph partitioning.- 5.1. Methodology.- 5.1.1. Problems.- 5.1.2. Algorithms.- 5.1.3. Data collection.- 5.1.4. Parameter tuning.- 5.2. Adding a linear component.- 5.3. Experiments on random graphs.- 5.4. Experiments on multilevel graphs.- 6. Related work.- 6.1. The problem space formulation.- 6.2. Search and learning.- 6.2.1. Learning while searching.- 6.2.2. Symbolic learning.- 6.2.3. Hillclimbing.- 6.2.4. Stochastic hillclimbing and simulated annealing.- 6.2.5. Genetic algorithms.- 6.3. Connectionist modelling.- 6.3.1. Competitive learning.- 6.3.2. Back propagation.- 6.3.3. Boltzmann machines.- 6.3.4. Stochastic iterated genetic hillclimbing.- 6.3.5. Harmony theory.- 6.3.6. Reinforcement models.- 7. Limitations and variations.- 7.1. Current limitations.- 7.1.1. The problem.- 7.1.2. The SIGH model.- 7.2. Possible variations.- 7.2.1. Exchanging parameters.- 7.2.2. Beyond symmetric connections.- 7.2.3. Simultaneous optimization.- 7.2.4. Widening the bottleneck.- 7.2.5. Temporal credit assignment.- 7.2.6. Learning a function.- 8. Discussion and conclusions.- 8.1. Stability and change.- 8.2. Architectural goals.- 8.2.1 High potential parallelism.- 8.2.2 Highly incremental.- 8.2.3 "Generalized Hebbian" learning.- 8.2.4 Unsupervised learning.- 8.2.5 "Closed loop" interactions.- 8.2.6 Emergent properties.- 8.3. Discussion.- 8.3.1 The processor/memory distinction.- 8.3.2 Physical computation systems.- 8.3.3 Between mind and brain.- 8.4. Conclusions.- 8.4.1. Recapitulation.- 8.4.2. Contributions.- References.
---
paper_title: Metaheuristics for Hard Optimization: Methods and Case Studies

paper_content:

Metaheuristics for Hard Optimization comprises of three parts. The first part is devoted to the detailed presentation of the four most widely known metaheuristics: - the simulated annealing method; - the tabu search; - the genetic and evolutionary algorithms; - the ant colony algorithms. Each one of these metaheuristics is actually a family of methods, of which we try to discuss the essential elements. Some common features clearly appear in most metaheuristics, such as the use of diversification, to force the exploration of regions of the search space, rarely visited until now, and the use of intensification, to go thoroughly into some promising regions. Another common feature is the use of memory to archive the best encountered solutions. One common drawback for most metaheuristics still is the delicate tuning of numerous parameters; theoretical results available by now are not sufficient to really help in practice the user facing a new hard optimization problem. In the second part, we present some other metaheuristics, less widespread or emergent: some variants of simulated annealing; noising method; distributed search; Alienor method; particle swarm optimization; estimation of distribution methods; GRASP method; cross-entropy method; artificial immune systems; differential evolution. Then we describe some extensions of metaheuristics for continuous optimization, multimodal optimization, multiobjective optimization and contrained evolutionary optimization. We present some of the existing techniques and some ways of research. The last chapter is devoted to the problem of the choice of a metaheuristic; we describe an unifying method called "Adaptive Memory Programming", which tends to attenuate the difficulty of this choice. The delicate subject of a rigorous statistical comparison between stochastic iterative methods is also discussed. The last part of the book concentrates on three case studies: - the optimization of the 3G mobile networks (UMTS) using the genetic algorithms. After a brief presentation of the operation of UMTS networks and of the quantities involved in the analysis of their performances, the chapter discusses the optimization problem for planning the UMTS network; an efficient method using a genetic algorithm is presented and illustrated through one example of a realistic network; - the application of genetic algorithms to the problems of management of the air traffic. One details two problems of air traffic management for which a genetic algorithm based solution has been proposed: the first application deals with the en route conflict resolution problem; the second one discusses the traffic management in an airport platform; - constrained programming and ant colony algorithms applied to vehicle routing problems. It is shown that constraint programming provides a modelling procedure, making it possible to represent the problems in an expressive and concise way; the use of ant colony algorithms allows to obtain heuristics which can be simultaneously robust and generic in nature. One appendix of the book is devoted to the modeling of simulated annealing through the Markov chain formalism. Another appendix gives a complete implementation in C++ language for robust tabu search method
---
paper_title: Applying Adaptive Algorithms to Epistatic Domains

paper_content:

John Holland has shown that when adaptive algorithms are used to search certain kinds of extremely large problem spaces, they will converge on a "good" solution fairly quickly. Such problem spaces are characterized by a low degree of epistasis. A host of classical search problems, however, are epistatic in nature. The present paper describes some new techniques for applying adaptive algorithms to epistatic domains, while retaining some of the strength of Holland's convergence proof. These techniques are described for two-dimensional bin-packing problems, and summarized for graph coloring problems. What makes these problems amenable to an adaptive approach is a two-stage evaluation procedure. Encodings of solutions are mutated and reproduced as they are in non-epistatic domains, but their evaluation is carried out after a decoding process. Using the techniques described, convergence is promoted in two ways: one of the natural mutation operators is a weaker version of Holland's crossover, and domain knowledge may be built into decoding processes so that the size of the search space is radically cut down.
---
paper_title: Representations for Genetic and Evolutionary Algorithms

paper_content:

From the Publisher: ::: In the field of genetic and evolutionary algorithms (GEAs), much theory and empirical study has been heaped upon operators and test problems, but problem representation has often been taken as given. This monograph breaks with this tradition and studies a number of critical elements of a theory of representations for GEAs and applies them to the empirical study of various important idealized test functions and problems of commercial import. The book considers basic concepts of representations, such as redundancy, scaling and locality and describes how GEAs'performance is influenced. Using the developed theory representations can be analyzed and designed in a theory-guided manner. The theoretical concepts are used as examples for efficiently solving integer optimization problems and network design problems. The results show that proper representations are crucial for GEAs'success.
---
paper_title: Hyperheuristics: A Tool for Rapid Prototyping in Scheduling and Optimisation

paper_content:

The term hyperheuristic was introduced by the authors as a high-level heuristic that adaptively controls several low-level knowledgepoor heuristics so that while using only cheap, easy-to-implement low-level heuristics, we may achieve solution quality approaching that of an expensive knowledge-rich approach. For certain classes of problems, this allows us to rapidly produce effective solutions, in a fraction of the time needed for other approaches, and using a level of expertise common among non-academic IT professionals. Hyperheuristics have been successfully applied by the authors to a real-world problem of personnel scheduling. In this paper, the authors report another successful application of hyperheuristics to a rather different real-world problem of personnel scheduling occuring at a UK academic institution. Not only did the hyperheuristics produce results of a quality much superior to that of a manual solution but also these results were produced within a period of only three weeks due to the savings resulting from using the existing hyperheuristic software framework.
---
paper_title: An Adaptive Crossover Distribution Mechanism for Genetic Algorithms

paper_content:

Genetic Algorithms (GAs) emulate the natural evolution process and maintain a population of potential solutions to a given problem. Through the population, GAs implicitly maintain the statistics about the search space. This implicit statistics can be used explicitly to enhance GA's performance. Inspired by this idea, a statistics-based adaptive non-uniform crossover (SANUX) has been proposed. SANUX uses the statistics information of the alleles in each locus to adaptively calculate the swapping probability of that locus for crossover operation. A simple triangular function has been used to calculate the swapping probability. In this paper two new functions, the trapezoid and exponential functions, are proposed for SANUX instead of the triangular function. Experiment results show that both functions further improve the performance of SANUX.
---
paper_title: A Taxonomy of Hybrid Metaheuristics

paper_content:

Hybrid metaheuristics have received considerable interest these recent years in the field of combinatorial optimization. A wide variety of hybrid approaches have been proposed in the literature. In this paper, a taxonomy of hybrid metaheuristics is presented in an attempt to provide a common terminology and classification mechanisms. The taxonomy, while presented in terms of metaheuristics, is also applicable to most types of heuristics and exact optimization algorithms. ::: ::: As an illustration of the usefulness of the taxonomy an annoted bibliography is given which classifies a large number of hybrid approaches according to the taxonomy.
---
paper_title: Hyperheuristics: Recent Developments

paper_content:

Given their economic importance, there is continuing research interest in providing better and better solutions to real-world scheduling problems. The models for such problems are increasingly complex and exhaustive search for optimal solutions is usually impractical. Moreover, difficulty in accurately modelling the problems means that mathematically “optimal” solutions may not actually be the best possible solutions in practice. Therefore heuristic methods are often used, which do not guarantee optimal or even near optimal solutions. The main goal of heuristics is to produce solutions of acceptable quality in reasonable time. The problem owners often prefer simple, easy to implement heuristic approaches which do not require significant amount of resources for their development and implementation [12]. However, such individual heuristics do not always perform well for the variety of problem instances which may be encountered in practice. There is a wide range of modern heuristics known from the literature which are specifically designed and tuned to solve certain classes of optimisation problems. These methods are based on the partial search of the solution space and often referred as metaheuristics.
---
paper_title: Strongly Typed Genetic Programming

paper_content:

Genetic programming is a powerful method for automatically generating computer programs via the process of natural selection (Koza, 1992). However, in its standard form, there is no way to restrict the programs it generates to those where the functions operate on appropriate data types. In the case when the programs manipulate multiple data types and contain functions designed to operate on particular data types, this can lead to unnecessarily large search times and/or unnecessarily poor generalization performance. Strongly typed genetic programming (STGP) is an enhanced version of genetic programming that enforces data-type constraints and whose use of generic functions and generic data types makes it more powerful than other approaches to type-constraint enforcement. After describing its operation, we illustrate its use on problems in two domains, matrix/vector manipulation and list manipulation, which require its generality. The examples are (1) the multidimensional least-squares regression problem, (2) the multidimensional Kalman filter, (3) the list manipulation function NTH, and (4) the list manipulation function MAPCAR.
---
paper_title: Local Search in Combinatorial Optimization

paper_content:

From the Publisher: ::: In the past three decades local search has grown from a simple heuristic idea into a mature field of research in combinatorial optimization. Local search is still the method of choice for NP-hard problems as it provides a robust approach for obtaining high-quality solutions to problems of a realistic size in a reasonable time. This area of discrete mathematics is of great practical use and is attracting ever increasing attention. The contributions to this book cover local search and its variants from both a theoretical and practical point of view, each with a chapter written by leading authorities on that particular aspect. This book is an important reference volume and an invaluable source of inspiration for advanced students and researchers in discrete mathematics, computer science, operations research, industrial engineering and management science.
---
paper_title: The Island Model Genetic Algorithm: On Separability, Population Size and Convergence

paper_content:

Parallel Genetic Algorithms have often been reported to yield better performance than Genetic Algorithms which use a single large panmictic population. In the case of the Island Model genetic algorithm, it has been informally argued that having multiple subpopulations helps to preserve genetic diversity, since each island can potentially follow a different search trajectory through the search space. It is also possible that since linearly separable problems are often used to test Genetic Algorithms, that Island Models may simply be particularly well suited to exploiting the separable nature of the test problems. We explore this possibility by using the infinite population models of simple genetic algorithms to study how Island Models can track multiple search trajectories. We also introduce a simple model for better understanding when Island Model genetic algorithms may have an advantage when processing some test problems. We provide empirical results for both linearly separable and nonseparable parameter optimization functions.
---
paper_title: ParadisEO: A Framework for the Reusable Design of Parallel and Distributed Metaheuristics

paper_content:

In this paper, we present the ParadisEO white-box object-oriented framework dedicated to the reusable design of parallel and distributed metaheuristics (PDM). ParadisEO provides a broad range of features including evolutionary algorithms (EA), local searches (LS), the most common parallel and distributed models and hybridization mechanisms, etc. This high content and utility encourages its use at European level. ParadisEO is based on a clear conceptual separation of the solution methods from the problems they are intended to solve. This separation confers to the user a maximum code and design reuse. Furthermore, the fine-grained nature of the classes provided by the framework allow a higher flexibility compared to other frameworks. ParadisEO is of the rare frameworks that provide the most common parallel and distributed models. Their implementation is portable on distributed-memory machines as well as on shared-memory multiprocessors, as it uses standard libraries such as MPI, PVM and PThreads. The models can be exploited in a transparent way, one has just to instantiate their associated provided classes. Their experimentation on the radio network design real-world application demonstrate their efficiency.
---
paper_title: Forma Analysis and Random Respectful Recombination

paper_content:

Intrinsic parallelism is shown to have application beyond schemata and o-schemata. More general objects called formae are introduced and general operators which manipulate these are introduced and discussed. These include random, respectful recombination. The extended formalism is applied to various common representations and standard operators are analysed in the light of the formalism.
---
paper_title: Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images*

paper_content:

We make an analogy between images and statistical mechanics systems. Pixel gray levels and the presence and orientation of edges are viewed as states of atoms or molecules in a lattice-like physical system. The assignment of an energy function in the physical system determines its Gibbs distribution. Because of the Gibbs distribution, Markov random field (MRF) equivalence, this assignment also determines an MRF image model. The energy function is a more convenient and natural mechanism for embodying picture attributes than are the local characteristics of the MRF. For a range of degradation mechanisms, including blurring, non-linear deformations, and multiplicative or additive noise, the posterior distribution is an MRF with a structure akin to the image model. By the analogy, the posterior distribution defines another (imaginary) physical system. Gradual temperature reduction in the physical system isolates low-energy states (‘annealing’), or what is the same thing, the most probable states under the Gib...
---
paper_title: Constant thermodynamic speed for minimizing entropy production in thermodynamic processes and simulated annealing

paper_content:

For an arbitrary finite-time thermodynamic or information-based process we derive a lower bound on cumulative entropy production, as well as the associated optimal operating strategy for minimizing entropy production. The optimal path corresponds to a fixed rate of entropy production in the system, provided the rate of change is calculated in terms of the natural dimensionless time scale of the system. The constant thermodynamic speed algorithm for simulated annealing is derived from first principles and shown to be the leading term in a general expansion which represents the optimal solution. The results are valid for uniform systems (no spatial gradients) in which the involved intensive thermodynamic quantities are uniquely defined. The method and conclusions are easily extended to other objective functions, such as minimal loss of availability, and to assorted thermodynamic control variables.
---
paper_title: Skewed VNS enclosing second order algorithm for the degree constrained minimum spanning tree problem

paper_content:

We develop ideas to enhance the performance of the variable neighborhood search (VNS) by guiding the search in the shaking phase, and by employing the Skewed strategy. For this purpose, Second Order algorithms and Skewed functions expressing structural differences are embedded in an efficient VNS proposed in the literature for the degree constrained minimum spanning tree problem. Given an undirected graph with weights associated with its edges, the degree constrained minimum spanning tree problem consists in finding a minimum spanning tree of the given graph, subject to constraints on node degrees. Computational experiments are conducted on the largest and hardest benchmark instances found in the literature to date. We report results showing that the VNS with the proposed strategies improved the best known solutions for all the hardest benchmark instances. Moreover, these new best solutions significantly reduced the gaps with respect to tight lower bounds reported in the literature.
---
paper_title: Optimization by simulated annealing

paper_content:

There is a deep and useful connection between statistical mechanics (the behavior of systems with many degrees of freedom in thermal equilibrium at a finite temperature) and multivariate or combinatorial optimization (finding the minimum of a given function depending on many parameters). A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems. This connection to statistical mechanics exposes new information and provides an unfamiliar perspective on traditional optimization problems and methods.
---
paper_title: Variable Neighborhood Decomposition Search

paper_content:

The recent Variable Neighborhood Search (VNS) metaheuristic combines local search with systematic changes of neighborhood in the descent and escape from local optimum phases. When solving large instances of various problems, its efficiency may be enhanced through decomposition. The resulting two level VNS, called Variable Neighborhood Decomposition Search (VNDS), is presented and illustrated on the p-median problem. Results on 1400, 3038 and 5934 node instances from the TSP library show VNDS improves notably upon VNS in less computing time, and gives much better results than Fast Interchange (FI), in the same time that FI takes for a single descent. Moreover, Reduced VNS (RVNS), which does not use a descent phase, gives results similar to those of FI in much less computing time.
---
paper_title: Particle swarm optimization

paper_content:

A concept for the optimization of nonlinear functions using particle swarm methodology is introduced. The evolution of several paradigms is outlined, and an implementation of one of the paradigms is discussed. Benchmark testing of the paradigm is described, and applications, including nonlinear function optimization and neural network training, are proposed. The relationships between particle swarm optimization and both artificial life and genetic algorithms are described.
---
paper_title: Nonlinear inertia weight variation for dynamic adaptation in particle swarm optimization

paper_content:

The particle swarm optimization (PSO) is a relatively new generation of combinatorial metaheuristic algorithms which is based on a metaphor of social interaction, namely bird flocking or fish schooling. Although the algorithm has shown some important advances by providing high speed of convergence in specific problems it has also been reported that the algorithm has a tendency to get stuck in a near optimal solution and may find it difficult to improve solution accuracy by fine tuning. The present paper proposes a new variation of PSO model where we propose a new method of introducing nonlinear variation of inertia weight along with a particle's old velocity to improve the speed of convergence as well as fine tune the search in the multidimensional space. The paper also presents a new method of determining and setting a complete set of free parameters for any given problem, saving the user from a tedious trial and error based approach to determine them for each specific problem. The performance of the proposed PSO model, along with the fixed set of free parameters, is amply demonstrated by applying it for several benchmark problems and comparing it with several competing popular PSO and non-PSO combinatorial metaheuristic algorithms.
---
paper_title: Recent approaches to global optimization problems through Particle Swarm Optimization

paper_content:

This paper presents an overview of our most recent results concerning the Particle Swarm Optimization (PSO) method. Techniques for the alleviation of local minima, and for detecting multiple minimizers are described. Moreover, results on the ability of the PSO in tackling Multiobjective, Minimax, Integer Programming and e1 errors-in-variables problems, as well as problems in noisy and continuously changing environments, are reported. Finally, a Composite PSO, in which the heuristic parameters of PSO are controlled by a Differential Evolution algorithm during the optimization, is described, and results for many well-known and widely used test functions are given.
---
paper_title: Evaluation of repulsive particle swarm method for phase equilibrium and phase stability problems

paper_content:

Phase equilibrium and stability problems are of crucial importance in simulation, design and optimization of several separation processes. Recently, these problems have been solved using minimization of Gibbs free energy, using global optimization techniques. In this paper, repulsive particle swarm (RPS), a recent global optimization technique is explored for the solution of phase stability and phase equilibrium.
---
paper_title: Population structure and particle swarm performance

paper_content:

The effects of various population topologies on the particle swarm algorithm were systematically investigated. Random graphs were generated to specifications, and their performance on several criteria was compared. What makes a good population structure? We discovered that previous assumptions may not have been correct.
---
paper_title: Particle swarm optimiser with neighbourhood operator

paper_content:

In recent years population based methods such as genetic algorithms, evolutionary programming, evolution strategies and genetic programming have been increasingly employed to solve a variety of optimisation problems. Recently, another novel population based optimisation algorithm - namely the particle swarm optimisation (PSO) algorithm, was introduced by R. Eberhart and J. Kennedy (1995). Although the PSO algorithm possesses some attractive properties, its solution quality has been somewhat inferior to other evolutionary optimisation algorithms (P. Angeline, 1998). We propose a number of techniques to improve the standard PSO algorithm. Similar techniques have been employed in the context of self organising maps and neural-gas networks (T. Kohonen, 1990; T.M. Martinez et al., 1994).
---
paper_title: Comparison of linear and classical velocity update rules in particle swarm optimization: notes on diversity

paper_content:

In this study, we investigate the significance of diversity in the particle swarm optimization (PSO) algorithm. To do so, we study two different implementations of the PSO, being the so-called linear and classical PSO formulations. While the behaviour of these two implementations is markedly different, they only differ in the formulation of the velocity update rule. In fact, the differences are merely due to subtle differences in the introduction of randomness into the algorithm. ::: ::: In this paper, we show that in algorithms employing the linear PSO velocity update rule, particle trajectories collapse to line searches in n-dimensional space. The classical formulation does not suffer this drawback. Instead, directional diverse stochastic search trajectories are retained, which in turn helps to alleviate premature convergence. The performance of the classical implementation is therefore superior for all test problems considered, due to the presence of adequate diversity. Copyright © 2006 John Wiley & Sons, Ltd.
---
paper_title: Pareto archived simulated annealing for permutation flow shop scheduling with multiple objectives

paper_content:

In this paper, a metaheuristic procedure based on simulated annealing (SA) is proposed to find Pareto-optimal or non-dominated solution set for the permutation flow shop scheduling problems (FSPs) with the consideration of regular performance measures of minimizing the makespan and the total flow time of jobs. A new perturbation mechanism called "segment-random insertion (SRI)" scheme is used to generate the neighbourhood of a given sequence. The performance of the proposed algorithm is evaluated by solving benchmark FSP instances provided by (B. Taillard, 1993). The results obtained are evaluated in terms of the number of non-dominated schedules generated by the algorithm and the proximity of the obtained non-dominated front to the Pareto front. The results and simple quality measures suggested in this paper can be used to evaluate the quality of the non-dominated fronts obtained by different algorithms
---
paper_title: Metaheuristics for Hard Optimization: Methods and Case Studies

paper_content:

Metaheuristics for Hard Optimization comprises of three parts. The first part is devoted to the detailed presentation of the four most widely known metaheuristics: - the simulated annealing method; - the tabu search; - the genetic and evolutionary algorithms; - the ant colony algorithms. Each one of these metaheuristics is actually a family of methods, of which we try to discuss the essential elements. Some common features clearly appear in most metaheuristics, such as the use of diversification, to force the exploration of regions of the search space, rarely visited until now, and the use of intensification, to go thoroughly into some promising regions. Another common feature is the use of memory to archive the best encountered solutions. One common drawback for most metaheuristics still is the delicate tuning of numerous parameters; theoretical results available by now are not sufficient to really help in practice the user facing a new hard optimization problem. In the second part, we present some other metaheuristics, less widespread or emergent: some variants of simulated annealing; noising method; distributed search; Alienor method; particle swarm optimization; estimation of distribution methods; GRASP method; cross-entropy method; artificial immune systems; differential evolution. Then we describe some extensions of metaheuristics for continuous optimization, multimodal optimization, multiobjective optimization and contrained evolutionary optimization. We present some of the existing techniques and some ways of research. The last chapter is devoted to the problem of the choice of a metaheuristic; we describe an unifying method called "Adaptive Memory Programming", which tends to attenuate the difficulty of this choice. The delicate subject of a rigorous statistical comparison between stochastic iterative methods is also discussed. The last part of the book concentrates on three case studies: - the optimization of the 3G mobile networks (UMTS) using the genetic algorithms. After a brief presentation of the operation of UMTS networks and of the quantities involved in the analysis of their performances, the chapter discusses the optimization problem for planning the UMTS network; an efficient method using a genetic algorithm is presented and illustrated through one example of a realistic network; - the application of genetic algorithms to the problems of management of the air traffic. One details two problems of air traffic management for which a genetic algorithm based solution has been proposed: the first application deals with the en route conflict resolution problem; the second one discusses the traffic management in an airport platform; - constrained programming and ant colony algorithms applied to vehicle routing problems. It is shown that constraint programming provides a modelling procedure, making it possible to represent the problems in an expressive and concise way; the use of ant colony algorithms allows to obtain heuristics which can be simultaneously robust and generic in nature. One appendix of the book is devoted to the modeling of simulated annealing through the Markov chain formalism. Another appendix gives a complete implementation in C++ language for robust tabu search method
---
paper_title: Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem

paper_content:

This paper introduces the ant colony system (ACS), a distributed algorithm that is applied to the traveling salesman problem (TSP). In the ACS, a set of cooperating agents called ants cooperate to find good solutions to TSPs. Ants cooperate using an indirect form of communication mediated by a pheromone they deposit on the edges of the TSP graph while building solutions. We study the ACS by running experiments to understand its operation. The results show that the ACS outperforms other nature-inspired algorithms such as simulated annealing and evolutionary computation, and we conclude comparing ACS-3-opt, a version of the ACS augmented with a local search procedure, to some of the best performing algorithms for symmetric and asymmetric TSPs.
---
paper_title: On how Pachycondyla apicalis ants suggest a new search algorithm

paper_content:

Abstract In this paper we present a new optimization algorithm based on a model of the foraging behavior of a population of primitive ants (Pachycondyla apicalis). These ants are characterized by a relatively simple but efficient strategy for prey search in which individuals hunt alone and try to cover a given area around their nest. The ant colony search behavior consists of a set of parallel local searches on hunting sites with a sensitivity to successful sites. Also, their nest is periodically moved. Accordingly, the proposed algorithm performs parallel random searches in the neighborhood of points called hunting sites. Hunting sites are created in the neighborhood of a point called nest. At constant intervals of time the nest is moved, which corresponds to a restart operator which re-initializes the parallel searches. We have applied this algorithm, called API, to numerical optimization problems with encouraging results.
---
paper_title: MOSA method: a tool for solving multiobjective combinatorial optimization problems

paper_content:

The success of modern heuristics (Simulated Annealing (S.A.), Tabu Search, Genetic Algorithms, …) in solving classical combinatorial optimization problems has drawn the attention of the research community in multicriteria methods. ::: ::: ::: ::: In fact, for large-scale problems, the simultaneous difficulties of -hard complexity and of multiobjective framework make most Multiobjective Combinatorial Optimization (MOCO) problems intractable for exact methods. ::: ::: ::: ::: This paper develops the so-called MOSA (Multiobjective Simulated Annealing) method to approximate the set of efficient solutions of a MOCO problem. Different options for the implementation are illustrated and extensive experiments prove the efficiency of the approach. Its results are compared to exact methods on bi-objective knapsack problems. Copyright © 1999 John Wiley & Sons, Ltd.
---
paper_title: Heuristics for Integer Programming Using Surrogate Constraints

paper_content:

This paper proposes a class of surrogate constraint heuristics for obtaining approximate, near optimal solutions to integer programming problems. These heuristics are based on a simple framework that illuminates the character of several earlier heuristic proposals and provides a variety of new alternatives. The paper also proposes additional heuristics that can be used either to supplement the surrogate constraint procedures or to provide independent solution strategies. Preliminary computational results are reported for applying one of these alternatives to a class of nonlinear generalized set covering problems involving approximately 100 constraints and 300–500 integer variables. The solutions obtained by the tested procedure had objective function values twice as good as values obtained by standard approaches (e.g., reducing the best objective function values of other methods from 85 to 40 on the average. Total solution time for the tested procedure ranged from ten to twenty seconds on the CDC 6600.
---
paper_title: Particle swarm optimization method in multiobjective problems

paper_content:

This paper constitutes a first study of the Particle Swarm Optimization (PSO) method in Multiobjective Optimization (MO) problems. The ability of PSO to detect Pareto Optimal points and capture the shape of the Pareto Front is studied through experiments on well-known non-trivial test functions. The Weighted Aggregation technique with fixed or adaptive weights is considered. Furthermore, critical aspects of the VEGA approach for Multiobjective Optimization using Genetic Algorithms are adapted to the PSO framework in order to develop a multi-swarm PSO that can cope effectively with MO problems. Conclusions are derived and ideas for further research are proposed.
---
paper_title: MAX-MIN Ant System and local search for the traveling salesman problem

paper_content:

Ant System is a general purpose algorithm inspired by the study of the behavior of ant colonies. It is based on a cooperative search paradigm that is applicable to the solution of combinatorial optimization problems. We introduce MAX-MIN Ant System, an improved version of basic Ant System, and report our results for its application to symmetric and asymmetric instances of the well known traveling salesman problem. We show how MAX-MIN Ant System can be significantly improved, extending it with local search heuristics. Our results clearly show that MAX-MIN Ant System has the property of effectively guiding the local search heuristics towards promising regions of the search space by generating good initial tours.
---
paper_title: A niched Pareto genetic algorithm for multiobjective optimization

paper_content:

Many, if not most, optimization problems have multiple objectives. Historically, multiple objectives have been combined ad hoc to form a scalar objective function, usually through a linear combination (weighted sum) of the multiple attributes, or by turning objectives into constraints. The genetic algorithm (GA), however, is readily modified to deal with multiple objectives by incorporating the concept of Pareto domination in its selection operator, and applying a niching pressure to spread its population out along the Pareto optimal tradeoff surface. We introduce the Niched Pareto GA as an algorithm for finding the Pareto optimal set. We demonstrate its ability to find and maintain a diverse "Pareto optimal population" on two artificial problems and an open problem in hydrosystems. >
---
paper_title: Using metaheuristic algorithms remotely via ROS

paper_content:

Jose Garcia-Nieto Dpto. Lenguajes y Ciencias de la Computacion E.T.S. Ingenieria Informatica University of Malaga, Spain jnieto@lcc.uma.es Enrique Alba Dpto. Lenguajes y Ciencias de la Computacion E.T.S. Ingenieria Informatica University of Malaga, Spain eat@lcc.uma.es Francisco Chicano Dpto. Lenguajes y Ciencias de la Computacion E.T.S. Ingenieria Informatica University of Malaga, Spain chicano@lcc.uma.es
---
paper_title: Using UML-F to Enhance Framework Development: a Case Study in the Local Search Heuristics Domain

paper_content:

Abstract Currently frameworks are most commonly represented through design diagrams written in standard object-oriented analysis and design languages. However, these design notations do not provide elements for identifying framework variation points and how their instantiation should be performed. Therefore, in order to create framework instances, users have to rely on extra documentation that is not always available. This paper shows the benefits of an extension to UML that explicitly represents all the information required for framework development and instantiation. The approach is illustrated through a large real-world framework for local search heuristics for combinatorial optimization problems.
---

Title: Metaheuristic optimization frameworks: a survey and benchmarking

Section 1: Introduction and motivation
Description 1: Introduce heuristic methods, the emergence of metaheuristics, and the importance of Metaheuristic Optimization Frameworks (MOFs).

Section 2: Metaheuristic optimization frameworks
Description 2: Define what a Metaheuristic Optimization Framework is and outline the advantages and disadvantages of using such tools.

Section 3: Why are MOFs valuable?
Description 3: Discuss the benefits and value of using MOFs, including efficiency and flexibility in solving optimization problems.

Section 4: Drawbacks: all that glitters are not gold
Description 4: Discuss the limitations and potential challenges associated with using MOFs.

Section 5: Review method
Description 5: Explain the methodology used to review and compare the MOFs, including research questions, information sources, and filtering criteria.

Section 6: Research questions
Description 6: List the main research questions guiding the study.

Section 7: Inclusion and exclusion criteria
Description 7: Define the criteria used to include or exclude certain MOFs from the study.

Section 8: Comparison criteria
Description 8: Describe the criteria used for comparing different MOFs, including specific areas of interest and associated features.

Section 9: Metaheuristic techniques (C1)
Description 9: Detail the assessment of supported metaheuristics, including different techniques and their variants.

Section 10: Adapting to a problem and its structure (C2)
Description 10: Evaluate how MOFs support the adaptation of metaheuristics to specific problems through solution representation, objective function specification, and underlying heuristics.

Section 11: Advanced characteristics (C3)
Description 11: Assess advanced features of MOFs such as hybrid techniques, hyper-heuristics, and distributed computing capabilities.

Section 12: Global optimization process support (C4)
Description 12: Evaluate MOF support for the overall optimization process, including batch execution, experimental design, and statistical analysis.

Section 13: Design, implementation, and licensing (C5)
Description 13: Assess the technical aspects of MOFs including implementation languages, licensing models, and adherence to software engineering best practices.

Section 14: Documentation and support (C6)
Description 14: Evaluate the quality of documentation, technical support, and user community responsiveness for each MOF.

Section 15: Discussion and challenges
Description 15: Discuss the results of the study, identify challenges, and suggest potential areas for improvement in current MOFs.

Section 16: Conclusions
Description 16: Summarize the findings of the study and outline future research directions and potential enhancements for MOFs.

Section 17: Appendix: Data tables
Description 17: Provide detailed tables and additional data supporting the study's findings.