Mapping the global structure of TSP fitness landscapes

The global structure of combinatorial landscapes is not fully understood, yet it is known to impact the performance of heuristic search methods. We use a so-called local optima network model to characterise and visualise the global structure of travelling salesperson fitness landscapes of different classes, including random and structured real-world instances of realistic size. Our study brings rigour to the characterisation of so-called funnels, and proposes an intensive and effective sampling procedure for extracting the networks. We propose enhanced visualisation techniques, including 3D plots and the incorporation of colour, sizes and widths, to reflect relevant aspects of the search process. This brings an almost tangible new perspective to the landscape and funnel metaphors. Our results reveal a much richer global structure than the suggestion of a ‘big-valley’ structure. Most landscapes of the tested instances have multiple valleys or funnels; and the number, disposition and interaction of these funnels seem to relate to search difficulty on the studied landscapes. We also find that the structured TSP instances feature high levels of neutrality, an observation not previously reported in the literature. We then propose ways of analysing and visualising these neutral landscapes.     

The case for strategic oscillation

We study a “hard” optimization problem for metaheuristic search, where a natural neighborhood (that consists of moves for flipping the values of zero-one variables) confronts two local optima, separated by a maximum possible number of moves in the feasible space. Once a descent method reaches the first local optimum, all sequences of feasible moves to reach the second, which is the global optimum, must ultimately pass through solutions that are progressively worse until reaching the worst solution of all, which is adjacent to the global optimum.     

Balancing global and local search in parallel efficient global optimization algorithms

Most parallel efficient global optimization (EGO) algorithms focus only on the parallel architectures for producing multiple updating points, but give few attention to the balance between the global search (i.e., sampling in different areas of the search space) and local search (i.e., sampling more intensely in one promising area of the search space) of the updating points. In this study, a novel approach is proposed to apply this idea to further accelerate the search of parallel EGO algorithms. In each cycle of the proposed algorithm, all local maxima of expected improvement (EI) function are identified by a multi-modal optimization algorithm. Then the local EI maxima with value greater than a threshold are selected and candidates are sampled around these selected EI maxima. The results of numerical experiments show that, although the proposed parallel EGO algorithm needs more evaluations to find the optimum compared to the standard EGO algorithm, it is able to reduce the optimization cycles. Moreover, the proposed parallel EGO algorithm gains better results in terms of both number of cycles and evaluations compared to a state-of-the-art parallel EGO algorithm over six test problems.     

A Comparison of Global Optimization Methods for the Design of a High-speed Civil Transport

The conceptual design of aircraft often entails a large number of nonlinear constraints that result in a nonconvex feasible design space and multiple local optima. The design of the high-speed civil transport (HSCT) is used as an example of a highly complex conceptual design with 26 design variables and 68 constraints. This paper compares three global optimization techniques on the HSCT problem and two test problems containing thousands of local optima and noise: multistart local optimizations using either sequential quadratic programming (SQP) as implemented in the design optimization tools (DOT) program or Snyman's dynamic search method, and a modified form of Jones' DIRECT global optimization algorithm. SQP is a local optimizer, while Snyman's algorithm is capable of moving through shallow local minima. The modified DIRECT algorithm is a global search method based on Lipschitzian optimization that locates small promising regions of design space and then uses a local optimizer to converge to the optimum. DOT and the dynamic search algorithms proved to be superior for finding a single optimum masked by noise of trigonometric form. The modified DIRECT algorithm was found to be better for locating the global optimum of functions with many widely separated true local optima.     

A stopping rule for optimization using randomized search procedures

In many nonconvex programming problems, it is possible to locate local optima, but the global optimum may be difficult to determine. In such cases, a search procedure is often used, with random starting solutions, to find alternate local optima. This search can be terminated by a stopping rule, based upon Bayesian revised probability distributions, which determines the optimal number of iterations. The application of this rule to a resource allocation problem in project scheduling is illustrated.This work was supported in part by grants from the National Science Foundation and the Rochester Gas and Electric Corporation to the Massachusetts Institute of Technology.     

Investigation of the Fitness Landscapes in Graph Bipartitioning: An Empirical Study

An empirical study is performed on the local-optimum space in graph bipartitioning. We examine some statistical features of the fitness landscape and the local properties of the landscape. They include the distributions of local optima, their cost-distance correlations, their attraction powers, the properties around the central area of local optima, etc. The study reveals some new notable results about the properties of the fitness landscape. For example, the central area yielded good quality in local-optimum space, the local-optimum space had the self-similar structure of global convexity, local optima showed clusters in more than one place, etc. We also provide a simple experiment on whether it is worth to exploit the area around the Euclidean center of the problem space.     

Enhanced speciation in particle swarm optimization for multi-modal problems

In this paper, we present a novel multi-modal optimization algorithm for finding multiple local optima in objective function surfaces. We build from Species-based particle swarm optimization (SPSO) by using deterministic sampling to generate new particles during the optimization process, by implementing proximity-based speciation coupled with speciation of isolated particles, and by including “turbulence regions” around already found solutions to prevent unnecessary function evaluations. Instead of using error threshold values, the new algorithm uses the particle’s experience, geometric mean, and “exclusion factor” to detect local optima and stop the algorithm. The performance of each extension is assessed with leave-it-out tests, and the results are discussed. We use the new algorithm called Isolated-Speciation-based particle swarm optimization (ISPSO) and a benchmark algorithm called Niche particle swarm optimization (NichePSO) to solve a six-dimensional rainfall characterization problem for 192 rain gages across the United States. We show why it is important to find multiple local optima for solving this real-world complex problem by discussing its high multi-modality. Solutions found by both algorithms are compared, and we conclude that ISPSO is more reliable than NichePSO at finding optima with a significantly lower objective function value.     

Local models—an approach to distributed multi-objective optimization

When solving real-world optimization problems, evolutionary algorithms often require a large number of fitness evaluations in order to converge to the global optima. Attempts have been made to find techniques to reduce the number of fitness function evaluations. We propose a novel framework in the context of multi-objective optimization where fitness evaluations are distributed by creating a limited number of adaptive spheres spanning the search space. These spheres move towards the global Pareto front as components of a swarm optimization system. We call this process localization. The contribution of the paper is a general framework for distributed evolutionary multi-objective optimization, in which the individuals in each sphere can be controlled by any existing evolutionary multi-objective optimization algorithm in the literature.     

Local search for the minimum label spanning tree problem with bounded color classes

In the Minimum Label Spanning Tree problem, the input consists of an edge-colored undirected graph, and the goal is to find a spanning tree with the minimum number of different colors. We investigate the special case where every color appears at most r times in the input graph. This special case is polynomially solvable for r=2, and NP- and APX-complete for any fixed r?3.We analyze local search algorithms that are allowed to switch up to k of the colors used in a feasible solution. We show that for k=2 any local optimum yields an (r+1)/2-approximation of the global optimum, and that this bound is tight. For every k?3, there exist instances for which some local optima are a factor of r/2 away from the global optimum.     

Study of multiscale global optimization based on parameter space partition

Inverse problems in geophysics are usually described as data misfit minimization problems, which are difficult to solve because of various mathematical features, such as multi-parameters, nonlinearity and ill-posedness. Local optimization based on function gradient can not guarantee to find out globally optimal solutions, unless a starting point is sufficiently close to the solution. Some global optimization methods based on stochastic searching mechanisms converge in the limit to a globally optimal solution with probability 1. However, finding the global optimum of a complex function is still a great challenge and practically impossible for some problems so far. This work develops a multiscale deterministic global optimization method which divides definition space into sub-domains. Each of these sub-domains contains the same local optimal solution. Local optimization methods and attraction field searching algorithms are combined to determine the attraction basin near the local solution at different function smoothness scales. With Multiscale Parameter Space Partition method, all attraction fields are to be determined after finite steps of parameter space partition, which can prevent redundant searching near the known local solutions. Numerical examples demonstrate the efficiency, global searching ability and stability of this method.     

Parallelizing simulated annealing algorithms based on high-performance computer

We implemented five conversions of simulated annealing (SA) algorithm from sequential-to-parallel forms on high-performance computers and applied them to a set of standard function optimization problems in order to test their performances. According to the experimental results, we eventually found that the traditional approach to parallelizing simulated annealing, namely, parallelizing moves in sequential SA, difficultly handled very difficult problem instances. Divide-and-conquer decomposition strategy used in a search space sometimes might find the global optimum function value, but it frequently resulted in great time cost if the random search space was considerably expanded. The most effective way we found in identifying the global optimum solution is to introduce genetic algorithm (GA) and build a highly hybrid GA+SA algorithm. In this approach, GA has been applied to each cooling temperature stage. Additionally, the performance analyses of the best algorithm among the five implemented algorithms have been done on the IBM Beowulf PCs Cluster and some comparisons have been made with some recent global optimization algorithms in terms of the number of functional evaluations needed to obtain a global minimum, success rate and solution quality.     

Landscape analysis and efficient metaheuristics for solving the n-queens problem

The n-queens problem is a classical combinatorial optimization problem which has been proved to be NP-hard. The goal is to place n non-attacking queens on an n×n chessboard. In this paper, two single-solution-based (Local Search (LS) and Tuned Simulated Annealing (SA)) and two population-based metaheuristics (two versions of Scatter Search (SS)) are presented for solving the problem. Since parameters of heuristic and metaheuristic algorithms have great influence on their performance, a TOPSIS-Taguchi based parameter tuning method is proposed, which not only considers the number of fitness function evaluations, but also aims to minimize the runtime of the presented metaheuristics. The performance of the suggested approaches was investigated through computational analyses, which showed that the Local Search method outperformed the other two algorithms in terms of average runtimes and average number of fitness function evaluations. The LS was also compared to the Cooperative PSO (CPSO) and SA algorithms, which are currently the best algorithms in the literature for finding the first solution to the n-queens problem, and the results showed that the average fitness function evaluation of the LS is approximately 21 and 8 times less than that of SA and CPSO, respectively. Also, a fitness analysis of landscape for the n-queens problem was conducted which indicated that the distribution of local optima is uniformly random and scattered over the search space. The landscape is rugged and there is no significant correlation between fitness and distance of solutions, and so a local search heuristic can search a rugged plain landscape effectively and find a solution quickly. As a result, it was statistically and analytically proved that single-solution-based metaheuristics outperform population-based metaheuristics in finding the first solution of the n-queens problem.     

Path relinking for the vehicle routing problem

This paper describes a tabu search heuristic with path relinking for the vehicle routing problem. Tabu search is a local search method that explores the solution space more thoroughly than other local search based methods by overcoming local optima. Path relinking is a method to integrate intensification and diversification in the search. It explores paths that connect previously found elite solutions. Computational results show that tabu search with path relinking is superior to pure tabu search on the vehicle routing problem.     

Attraction probabilities in variable neighborhood search

Empirical evidence demonstrates that when the same local search operator is used, variable neighborhood search consistently outperforms random multistart local search on all types of combinatorial and global optimization problems tested. In this paper we suggest that this superiority in performance may be explained by the distribution of the attraction basins around a current solution as a function of the distance from the solution. We illustrate with a well-known instance of the multisource Weber problem that the “attraction probabilities” for finding better solutions can be orders of magnitude larger in neighborhoods that are close to the current solution. The paper also discusses the global convergence properties of both general methods in the context of attraction probabilities.     

Local Search for Vehicle Routing and Scheduling Problems: Review and Conceptual Integration

Local search and local search-based metaheuristics are currently the only available methods for obtaining good solutions to large vehicle routing and scheduling problems. In this paper we provide a review of both classical and modern local search neighborhoods for this class of problems. The intention of this paper is not only to give an overview but to classify and analyze the structure of different neighborhoods. The analysis is based on a formal representation of VRSP solutions given by a unifying giant-tour model. We describe neighborhoods implicitly by a set of transformations called moves and show how moves can be decomposed further into partial moves. The search method has to compose these partial moves into a complete move in an efficient way. The goal is to find a local best neighbor and to reach a local optimum as quickly as possible. This can be achieved by search methods, which do not scan all neighbor solutions explicitly. Our analysis shows how the properties of the partial moves and the constraints of the VRSP influences the choice of an appropriate search technique.     

Finding Robust Solutions Using Local Search

This paper investigates how a local search metaheuristic for continuous optimisation can be adapted so that it finds broad peaks, corresponding to robust solutions. This is relevant in problems in which uncertain or noisy data is present. When using a genetic or evolutionary algorithm, it is standard practice to perturb solutions once before evaluating them, using noise from a given distribution. This approach however, is not valid when using population-less techniques like local search and other heuristics that use local search. For those algorithms to find robust solutions, each solution needs to be perturbed and evaluated several times, and these evaluations need to be combined into a measure of robustness. In this paper, we examine how many of these evaluations are needed to reliably find a robust solution. We also examine the effect of the parameters of the noise distribution. Using a simple tabu search procedure, the proposed approach is tested on several functions found in the literature. This revised version was published online in August 2006 with corrections to the Cover Date.     

An algorithm for finding the global maximum of a multimodal,multivariate function

This algorithm for global optimization uses an arbitrary starting point, requires no derivatives, uses comparatively few function evaluations and is not side-tracked by nearby relative optima. The algorithm builds a gradually closer piecewise-differentiable approximation to the objective function. The computer program exhibits a (theoretically expected) strong tendency to cluster around relative optima close to the global. Results of testing with several standard functions are given.     

Global optima results for the Kauffman NK model

The Kauffman NK model has been used in theoretical biology, physics and business organizations to model complex systems with interacting components. Recent NK model results have focused on local optima. This paper analyzes global optima of the NK model. The resulting global optimization problem is transformed into a stochastic network model that is closely related to two well-studied problems in operations research. This leads to applicable strategies for explicit computation of bounds on the global optima particularly with K either small or close to N. A general lower bound, which is sharp for K = 0, is obtained for the expected value of the global optimum of the NK model. A detailed analysis is provided for the expectation and variance of the global optimum when K = N−1. The lower and upper bounds on the expectation obtained for this case show that there is a wide gap between the values of the local and the global optima. They also indicate that the complexity catastrophe that occurs with the local optima does not arise for the global optima.     

The effect of multiple optima on the simple GA run-time complexity

Genetic algorithms are stochastic search algorithms that have been applied to optimization problems. In this paper we analyze the run-time complexity of a genetic algorithm when we are interested in one of a set of distinguished solutions. One such case occurs when multiple optima exist. We define the worst case scenario and derive a probabilistic worst case bound on the number of iterations required to find one of these multiple solutions of interest.     

Analytical solutions to the optimization of a quadratic cost function subject to linear and quadratic equality constraints

In the area of broad-band antenna array signal processing, the global minimum of a quadratic equality constrained quadratic cost minimization problem is often required. The problem posed is usually characterized by a large optimization space (around 50–90 tuples), a large number of linear equality constraints, and a few quadratic equality constraints each having very low rank quadratic constraint matrices. Two main difficulties arise in this class of problem. Firstly, the feasibility region is nonconvex and multiple local minima abound. This makes conventional numerical search techniques unattractive as they are unable to locate the global optimum consistently (unless a finite search area is specified). Secondly, the large optimization space makes the use of decision-method algorithms for the theory of the reals unattractive. This is because these algorithms involve the solution of the roots of univariate polynomials of order to the square of the optimization space. In this paper we present a new algorithm which exploits the structure of the constraints to reduce the optimization space to a more manageable size. The new algorithm relies on linear-algebra concepts, basic optimization theory, and a multivariate polynomial root-solving tool often used by decision-method algorithms.This research was supported by the Australian Research Council and the Corporative Research Centre for Broadband Telecommunications and Networking.