A Staged Continuous Tabu Search Algorithm for the Global Optimization and its Applications to the Design of Fiber Bragg Gratings

A novel staged continuous Tabu search (SCTS) algorithm is proposed for solving global optimization problems of multi-minima functions with multi-variables. The proposed method comprises three stages that are based on the continuous Tabu search (CTS) algorithm with different neighbor-search strategies, with each devoting to one task. The method searches for the global optimum thoroughly and efficiently over the space of solutions compared to a single process of CTS. The effectiveness of the proposed SCTS algorithm is evaluated using a set of benchmark multimodal functions whose global and local minima are known. The numerical test results obtained indicate that the proposed method is more efficient than an improved genetic algorithm published previously. The method is also applied to the optimization of fiber grating design for optical communication systems. Compared with two other well-known algorithms, namely, genetic algorithm (GA) and simulated annealing (SA), the proposed method performs better in the optimization of the fiber grating design.     

Speeding up continuous GRASP

Continuous GRASP (C-GRASP) is a stochastic local search metaheuristic for finding cost-efficient solutions to continuous global optimization problems subject to box constraints (Hirsch et al., 2007). Like a greedy randomized adaptive search procedure (GRASP), a C-GRASP is a multi-start procedure where a starting solution for local improvement is constructed in a greedy randomized fashion. In this paper, we describe several improvements that speed up the original C-GRASP and make it more robust. We compare the new C-GRASP with the original version as well as with other algorithms from the recent literature on a set of benchmark multimodal test functions whose global minima are known. Hart’s sequential stopping rule (1998) is implemented and C-GRASP is shown to converge on all test problems.     

A Hybrid Genetic Algorithm for Nonconvex Function Minimization

In this paper, we consider the problem of minimizing a function in severalvariables which could be multimodal and may possess discontinuities. A newalgorithm for the problem based on the genetic technique is developed. Thealgorithm is hybrid in nature in the sense that it utilizes the genetictechnique to generate search directions, which are used in an optimizationscheme and is thus different from any other methods in the literature.The algorithm has been tested on the Rosenbrock valley functions in 2 and 4dimensions, and multimodal functions in 2 and 4 dimensions, which are of ahigh degree of difficulty. The results are compared with the Adaptive RandomSearch, and Simulated Annealing algorithms. The performance of the algorithmis also compared to recent global algorithms in terms of the number offunctional evaluations needed to obtain a global minimum and results show thatthe proposed algorithm is better than these algorithms on a set of standardtest problems. It seems that the proposed algorithm is efficient and robust.     

A novel metaheuristics approach for continuous global optimization

This paper proposes a novel metaheuristics approach to find the global optimum of continuous global optimization problems with box constraints. This approach combines the characteristics of modern metaheuristics such as scatter search (SS), genetic algorithms (GAs), and tabu search (TS) and named as hybrid scatter genetic tabu (HSGT) search. The development of the HSGT search, parameter settings, experimentation, and efficiency of the HSGT search are discussed. The HSGT has been tested against a simulated annealing algorithm, a GA under the name GENOCOP, and a modified version of a hybrid scatter genetic (HSG) search by using 19 well known test functions. Applications to Neural Network training are also examined. From the computational results, the HSGT search proved to be quite effective in identifying the global optimum solution which makes the HSGT search a promising approach to solve the general nonlinear optimization problem.     

A niche hybrid genetic algorithm for global optimization of continuous multimodal functions

A niche hybrid genetic algorithm (NHGA) is proposed in this paper to solve continuous multimodal optimization problems more efficiently, accurately and reliably. It provides a new architecture of hybrid algorithms, which organically merges the niche techniques and Nelder–Mead's simplex method into GAs. In the new architecture, the simplex search is first performed in the potential niches, which likely contain a global optimum, to locate the promising zones within search space, quickly and reliably. Then another simplex search is used to quickly discover the global optimum in the located promising zones. The proposed method not only makes the exploration capabilities of GAs stronger through niche techniques, but also has more powerful exploitation capabilities by using simplex search. So it effectively alleviates premature convergence and improves weak exploitation capacities of GAs. A set of benchmark functions is used to demonstrate the validity of NHGA and the role of every component of NHGA. Numerical experiments show that the NHGA may, efficiently and reliably, obtain a more accurate global optimum for the complex and high-dimension multimodal optimization problems. It also demonstrates that the new hybrid architecture is potential and can be used to generate more potential hybrid algorithms.     

The challenge of optimizing expensive black boxes: a scatter search/rough set theory approach

There is renewed interest in the development of effective and efficient methods for optimizing models of which the optimizer has no structural knowledge. This is what in the literature is referred to as optimization of black boxes. In particular, we address the challenge of optimizing expensive black boxes, that is, those that require a significant computational effort to be evaluated. We describe the use of rough set theory within a scatter search framework, with the goal of identifying high-quality solutions with a limited number of objective function evaluations. The rough set strategies that we developed take advantage of the information provided by the best and diverse solutions found during the search, in order to define areas of the solution space that are promising for search intensification. We test our procedure on a set of 92 nonlinear multimodal functions of varied complexity and size and compare the results with a state-of-the-art procedure based on particle swarm optimization.     

Integrating particle swarm optimization with genetic algorithms for solving nonlinear optimization problems

Heuristic optimization provides a robust and efficient approach for solving complex real-world problems. The aim of this paper is to introduce a hybrid approach combining two heuristic optimization techniques, particle swarm optimization (PSO) and genetic algorithms (GA). Our approach integrates the merits of both GA and PSO and it has two characteristic features. Firstly, the algorithm is initialized by a set of random particles which travel through the search space. During this travel an evolution of these particles is performed by integrating PSO and GA. Secondly, to restrict velocity of the particles and control it, we introduce a modified constriction factor. Finally, the results of various experimental studies using a suite of multimodal test functions taken from the literature have demonstrated the superiority of the proposed approach to finding the global optimal solution.     

Global optimization based on novel heuristics,low-discrepancy sequences and genetic algorithms

In this paper a new heuristic hybrid technique for bound-constrained global optimization is proposed. We developed iterative algorithm called GLP_τS that uses genetic algorithms, LP_τ low-discrepancy sequences of points and heuristic rules to find regions of attraction when searching a global minimum of an objective function. Subsequently Nelder–Mead Simplex local search technique is used to refine the solution. The combination of the three techniques (Genetic algorithms, LP_τO Low-discrepancy search and Simplex search) provides a powerful hybrid heuristic optimization method which is tested on a number of benchmark multimodal functions with 10–150 dimensions, and the method properties – applicability, convergence, consistency and stability are discussed in detail.     

A Continuous Genetic Algorithm Designed for the Global Optimization of Multimodal Functions

Genetic algorithms are stochastic search approaches based on randomized operators, such as selection, crossover and mutation, inspired by the natural reproduction and evolution of the living creatures. However, few published works deal with their application to the global optimization of functions depending on continuous variables.A new algorithm called Continuous Genetic Algorithm (CGA) is proposed for the global optimization of multiminima functions. In order to cover a wide domain of possible solutions, our algorithm first takes care over the choice of the initial population. Then it locates the most promising area of the solution space, and continues the search through an intensification inside this area. The selection, the crossover and the mutation are performed by using the decimal code. The efficiency of CGA is tested in detail through a set of benchmark multimodal functions, of which global and local minima are known. CGA is compared to Tabu Search and Simulated Annealing, as alternative algorithms.     

A hybrid single and dual population search procedure for the job shop scheduling problem

This paper presents a genetic algorithm and a scatter search procedure to solve the well-known job shop scheduling problem. In contrast to the single population search performed by the genetic algorithm, the scatter search algorithm splits the population of solutions in a diverse and high-quality set to exchange information between individuals in a controlled way. The extension from a single to a dual population, by taking problem specific characteristics into account, can be seen as a stimulator to add diversity in the search process. This has a positive influence on the important balance between intensification and diversification. Computational experiments verify the benefit of this diversity on the effectiveness of the meta-heuristic search process. Various algorithmic parameters from literature are embedded in both procedures and a detailed comparison is made. A set of standard instances is used to compare the different approaches and the best obtained results are benchmarked against heuristic solutions found in literature.     

A new genetic algorithm for global optimization of multimodal continuous functions

In this paper a new genetic algorithm is developed to find the near global optimal solution of multimodal nonlinear optimization problems. The algorithm defined makes use of a real encoded crossover and mutation operator. The performance of GA is tested on a set of twenty-seven nonlinear global optimization test problems of variable difficulty level. Results are compared with some well established popular GAs existing in the literature. It is observed that the algorithm defined performs significantly better than the existing ones.     

Principles of scatter search

Scatter search is an evolutionary method that has been successfully applied to hard optimization problems. The fundamental concepts and principles of the method were first proposed in the 1970s, based on formulations dating back to the 1960s for combining decision rules and problem constraints. In contrast to other evolutionary methods like genetic algorithms, scatter search is founded on the premise that systematic designs and methods for creating new solutions afford significant benefits beyond those derived from recourse to randomization. It uses strategies for search diversification and intensification that have proved effective in a variety of optimization problems.This paper provides the main principles and ideas of scatter search and its generalized form path relinking. We first describe a basic design to give the reader the tools to create relatively simple implementations. More advanced designs derive from the fact that scatter search and path relinking are also intimately related to the tabu search (TS) metaheuristic, and gain additional advantage by making use of TS adaptive memory and associated memory-exploiting mechanisms capable of being tailored to particular contexts. These and other advanced processes described in the paper facilitate the creation of sophisticated implementations for hard problems that often arise in practical settings. Due to their flexibility and proven effectiveness, scatter search and path relinking can be successfully adapted to tackle optimization problems spanning a wide range of applications and a diverse collection of structures, as shown in the papers of this volume.     

New Interval Analysis Support Functions Using Gradient Information in a Global Minimization Algorithm

The performance of interval analysis branch-and-bound global optimization algorithms strongly depends on the efficiency of selection, bounding, elimination, division, and termination rules used in their implementation. All the information obtained during the search process has to be taken into account in order to increase algorithm efficiency, mainly when this information can be obtained and elaborated without additional cost (in comparison with traditional approaches). In this paper a new way to calculate interval analysis support functions for multiextremal univariate functions is presented. The new support functions are based on obtaining the same kind of information used in interval analysis global optimization algorithms. The new support functions enable us to develop more powerful bounding, selection, and rejection criteria and, as a consequence, to significantly accelerate the search. Numerical comparisons made on a wide set of multiextremal test functions have shown that on average the new algorithm works almost two times faster than a traditional interval analysis global optimization method.     

Scatter search for chemical and bio-process optimization

Scatter search is a population-based method that has recently been shown to yield promising outcomes for solving combinatorial and nonlinear optimization problems. Based on formulations originally proposed in 1960s for combining decision rules and problem constraints such as the surrogate constraint method, scatter search uses strategies for combining solution vectors that have proved effective in a variety of problem settings. In this paper, we develop a general purpose heuristic for a class of nonlinear optimization problems. The procedure is based on the scatter search methodology and treats the objective function evaluation as a black box, making the search algorithm context-independent. Most optimization problems in the chemical and bio-chemical industries are highly nonlinear in either the objective function or the constraints. Moreover, they usually present differential-algebraic systems of constraints. In this type of problem, the evaluation of a solution or even the feasibility test of a set of values for the decision variables is a time-consuming operation. In this context, the solution method is limited to a reduced number of solution examinations. We have implemented a scatter search procedure in Matlab (Mathworks, 2004) for this special class of difficult optimization problems. Our development goes beyond a simple exercise of applying scatter search to this class of problems, but presents innovative mechanisms to obtain a good balance between intensification and diversification in a short-term search horizon. Computational comparisons with other recent methods over a set of benchmark problems favor the proposed procedure.     

Parallel Simulated Annealing Algorithms in Global Optimization

Global optimization involves the difficult task of the identification of global extremities of mathematical functions. Such problems are often encountered in practice in various fields, e.g., molecular biology, physics, industrial chemistry. In this work, we develop five different parallel Simulated Annealing (SA) algorithms and compare them on an extensive test bed used previously for the assessment of various solution approaches in global optimization. The parallel SA algorithms consist of various categories: the asynchronous approach where no information is exchanged among parallel runs and the synchronous approaches where solutions are exchanged using genetic operators, or where solutions are transmitted only occasionally, or where highly coupled synchronization is achieved at every iteration. One of these approaches, which occasionally applies partial information exchanges (controlled in terms of solution quality), provides particularly notable results for functions with vast search spaces of up to 400 dimensions. Previous attempts with other approaches, such as sequential SA, adaptive partitioning algorithms and clustering algorithms, to identify the global optima of these functions have failed without exception.     

Hidden Genes Genetic Optimization for Variable-Size Design Space Problems

This paper introduces the biologically inspired concept of hidden genes genetic algorithms; they search for optimal solutions to global optimization problems of multimodal objective functions with a variable number of design variables. A fixed chromosome length is assumed for all solutions in the population. Each chromosome is divided into effective and ineffective segments. The effective segment includes the design variables for that solution. The ineffective segment includes only hidden genes. Hidden genes are excluded in objective function evaluations. The effect of the hidden genes on the convergence of the genetic algorithm is studied. Two test cases are presented.     

On the limitations of classical benchmark functions for evaluating robustness of evolutionary algorithms

Although evolutionary algorithms (EAs) have some operators which let them explore the whole search domain, still they get trapped in local minima when multimodality of the objective function is increased. To improve the performance of EAs, many optimization techniques or operators have been introduced in recent years. However, it seems that these modified versions exploit some special properties of the classical multimodal benchmark functions, some of which have been noted in previous research and solutions to eliminate them have been proposed.In this article, we show that quite symmetric behavior of the available multimodal test functions is another example of these special properties which can be exploited by some EAs such as covariance matrix adaptation evolution strategy (CMA-ES). This method, based on its invariance properties and good optimization results for available unimodal and multimodal benchmark functions, is considered as a robust and efficient method. However, as far as black box optimization problems are considered, no special trend in the behavior of the objective function can be assumed; consequently this symmetry limits the generalization of optimization results from available multimodal benchmark functions to real world problems. To improve the performance of CMA-ES, the Elite search sub-algorithm is introduced and implemented in the basic algorithm. Importance and effect of this modification is illustrated experimentally by dissolving some test problems in the end.     

Global Optimization by Monotonic Transformation

This paper addresses the problem of global optimization by means of a monotonic transformation. With an observation on global optimality of functions under such a transformation, we show that a simple and effective algorithm can be derived to search within possible regions containing the global optima. Numerical experiments are performed to compare this algorithm with one that does not incorporate transformed information using several benchmark problems. These results are also compared to best known global search algorithms in the literature. In addition, the algorithm is shown to be useful for several neural network learning problems, which possess much larger parameter spaces.     

Gbest-guided artificial bee colony algorithm for numerical function optimization

Artificial bee colony (ABC) algorithm invented recently by Karaboga is a biological-inspired optimization algorithm, which has been shown to be competitive with some conventional biological-inspired algorithms, such as genetic algorithm (GA), differential evolution (DE) and particle swarm optimization (PSO). However, there is still an insufficiency in ABC algorithm regarding its solution search equation, which is good at exploration but poor at exploitation. Inspired by PSO, we propose an improved ABC algorithm called gbest-guided ABC (GABC) algorithm by incorporating the information of global best (gbest) solution into the solution search equation to improve the exploitation. The experimental results tested on a set of numerical benchmark functions show that GABC algorithm can outperform ABC algorithm in most of the experiments.     

Scatter Search and Genetic Algorithms for MAX-SAT Problems

In this paper, both scatter search (SS) and genetic algorithms (GAs) are studied for the NP-Hard optimization variant of the satisfiability problem, namely MAX-SAT. First, we investigate a new selection strategy based on both fitness and diversity to choose individuals to participate in the reproduction phase of a genetic algorithm. The resulting algorithm is enhanced in two ways leading to two genetic algorithm variants: the first one uses a uniform crossover. The second one uses a specific crossover operator (to MAX-SAT). The crossover operator is combined with an improved stochastic local search (SLS). The crossover operator is used to identify promising regions while the stochastic local search performs an intensified search of solutions around these regions. Secondly, we propose a scatter search variant for MAX-SAT. Both the SS and the GAs implementations share the solution selection strategy, the improved SLS method and the combination operator. Experiments on several instances from MAX-SAT libraries are performed to show and compare the effectiveness of our approaches. The computational experiments show that both (SS) and (GAs) with a stochastic local search (SLS) improvement technique outperform a classical genetic algorithm (without SLS). The two metaheuristics are able of balancing search diversification and intensification which leads to good results. In general, the specific genetic algorithm with a (SLS) improvement technique and a specific combination method provides competitive results and finds solutions of a higher quality than a scatter search.