56028300
The Influence of Problem Specific Neighborhood Structures in Metaheuristics Performance
Metaheuristics (MH) aptitude to move past local optimums makes them an attractive technique to approach complex computational problems, such as the Travelling Salesman Problem (TSP), but there is lack of information on the parameterization procedure and the appropriate parameters to improve MHs’ performance. In this paper the parameterization procedure of Simulated Annealing (SA) and Discrete Artificial Bee Colony (DABC) is addressed, with a focus on the Neighborhood Structure (NS). Numerous NS have been proposed for specific problems, which seem to indicate that the NS is a special parameter, whose optimization is independent of other parameters. The performance of eight NS was examined with SA and DABC under two optimization constraints, regarding computational time variation, to determine if there is one appropriate NS for the TSP problem, independent of the rest of the parameters of the optimization procedure. The computational study carried out for comparing the evaluation of the NS, including a statistical analysis, demonstrated a nonproportional increase in the performance of DABC with some NS. For SA the improvement of the solutions appeared to be more uniform with an almost nonexistent variance in improvement.
58018372
Scheduling: Theory, Algorithms, and Systems
This book on scheduling covers theoretical models as well as scheduling problems in the real world. Author Michael Pinedo also includes a CD that contains slide-shows from industry and movies dealing with implementations of scheduling systems. The book consists of three parts. The first part focuses on deterministic scheduling with the associated combinatorial problems. The second part covers probabilistic scheduling models. In this part it is assumed that processing times and other problem data are not known in advance. The third part deals with scheduling in practice. It covers heuristics that are popular with practitioners and discusses system design and development issues. Each chapter contains a series of computational and theoretical exercises. This book is of interest to theoreticians and practitioners alike. Graduate students in operations management, operations research, industrial engineering and computer science will find the book to be an accessible and invaluable resource. Scheduling will serve as an essential reference for professionals working on scheduling problems in manufacturing and computing environments. Michael Pinedo is the Julius Schlesinger Professor of Operations Management at New York University.
55376065
Telefacturing Based Distributed Manufacturing Environment for Optimal Manufacturing Service by Enhancing the Interoperability in the Hubs
Recent happenings are surrounding the manufacturing sector leading to intense progress towards the development of effective distributed collaborative manufacturing environments. This evolving collaborative manufacturing not only focuses on digitalisation of this environment but also necessitates service-dependent manufacturing system that offers an uninterrupted approach to a number of diverse, complicated, dynamic manufacturing operations management systems at a common work place (hub). This research presents a novel telefacturing based distributed manufacturing environment for recommending the manufacturing services based on the user preferences. The first step in this direction is to deploy the most advanced tools and techniques, that is, Ontology-based Protege 5.0 software for transforming the huge stored knowledge/information into XML schema of Ontology Language (OWL) documents and Integration of Process Planning and Scheduling (IPPS) for multijobs in a collaborative manufacturing system. Thereafter, we also investigate the possibilities of allocation of skilled workers to the best feasible operations sequence. In this context, a mathematical model is formulated for the considered objectives, that is, minimization of makespan and total training cost of the workers. With an evolutionary algorithm and developed heuristic algorithm, the performance of the proposed manufacturing system has been improved. Finally, to manifest the capability of the proposed approach, an illustrative example from the real-time manufacturing industry is validated for optimal service recommendation.
7998645
Fast parallel simulated annealing for traveling salesman problem on SIMD machines with linear interconnections
In this paper, we present a fast parallel simulated annealing algorithm for solving traveling salesman problem(TSP) on SIMD machines with linear interconnections among processing elements. Simulated annealing is a generally applicable algorithm for solving combinatorial optimization problems by generating a sequence of moves at decending values of a control parameter. In our algorithm for TSP, the move operation can be executed in proportional to the time taken to broadcast a bit in one processing element (PE) to all the other PE's. Therefore, if a control unit has the broadcasting capability as is often the case with the SIMD machine, the move operation can be done in constant time and the whole simulated annealing algorithm has the time complexity only proportional to the number of the moves.
123646893
A Method for Solving Traveling-Salesman Problems
The traveling-salesman problem is a generalized form of the simple problem to find the smallest closed loop that connects a number of points in a plane. Efforts in the past to find an efficient method for solving it have met with only partial success. The present paper describes a method of solution that has the following properties ( a ) It is applicable to both symmetric and asymmetric problems with random elements ( b ) It does not use subjective decisions, so that it can be completely mechanized ( c ) It is appreciably faster than any other method proposed ( d ) It can be terminated at any point where the solution obtained so far is deemed sufficiently accurate.
27646815
A memetic neural network for the Euclidean traveling salesman problem
We study the hybridization of the self-organizing map (SOM) in an evolutionary algorithm to solve the Euclidean traveling salesman problem (TSP). The evolutionary dynamics consist of interleaving the SOM execution with a mapping operator, a fitness evaluation and a selection operator. SOM and mapping operators have a similar structure based on closest point findings and simple moves performed in the plane. We evaluate the approach on standard TSP test problems and show that it performs better, with respect to solution quality and/or computation time, than other neural network approaches given previously in the literature. Experiments are conducted on 91 publicly available TSP instances with up to 85900 cities.
8243011
Ant colonies for the travelling salesman problem.
We describe an artificial ant colony capable of solving the travelling salesman problem (TSP). Ants of the artificial colony are able to generate successively shorter feasible tours by using information accumulated in the form of a pheromone trail deposited on the edges of the TSP graph. Computer simulations demonstrate that the artificial ant colony is capable of generating good solutions to both symmetric and asymmetric instances of the TSP. The method is an example, like simulated annealing, neural networks and evolutionary computation, of the successful use of a natural metaphor to design an optimization algorithm.
122686821
Computer solutions of the traveling salesman problem
Two algorithms for solving the (symmetric distance) traveling salesman problem have been programmed for a high-speed digital computer. The first produces guaranteed optimal solution for problems involving no more than 13 cities; the time required (IBM 7094 II) varies from 60 milliseconds for a 9-city problem to 1.75 seconds for a 13-city problem. The second algorithm produces precisely characterized, locally optimal solutions for large problems (up to 145 cities) in an extremely short time and is based on a general heuristic approach believed to be of general applicability to various optimization problems. The average time required to obtain a locally optimal solution is under 30n3 microseconds where n is the number of cities involved. Repeated runs on a problem from random initial tours result in a high probability of finding the optimal solution among the locally optimal solutions obtained. For large problems where many locally optimal solutions have to be obtained in order to be reasonably assured of having the optimal solution, an efficient reduction scheme is incorporated in the program to reduce the total computation time by a substantial amount.
1014678
Particle swarm optimization-based algorithms for TSP and generalized TSP
A novel particle swarm optimization (PSO)-based algorithm for the traveling salesman problem (TSP) is presented. An uncertain searching strategy and a crossover eliminated technique are used to accelerate the convergence speed. Compared with the existing algorithms for solving TSP using swarm intelligence, it has been shown that the size of the solved problems could be increased by using the proposed algorithm. Another PSO-based algorithm is proposed and applied to solve the generalized traveling salesman problem by employing the generalized chromosome. Two local search techniques are used to speed up the convergence. Numerical results show the effectiveness of the proposed algorithms.
119097777
Optimized annealing of traveling salesman problem from the nth-nearest-neighbor distribution
We report a new statistical general property in traveling salesman problem, that the nth-nearest-neighbor distribution of optimal tours verifies with very high accuracy an exponential decay as a function of the order of neighbor n. Defining the energy function as deviation λ from this exponential decay, which is different to the tour length d in normal annealing processes, we propose a distinct highly optimized annealing scheme which is performed in λ-space and d-space by turns. The simulation results of some standard traveling salesman problems in TSPLIB95 are presented. It is shown that our annealing recipe is superior to the canonical simulated annealing.
122313212
An Algorithm for the Traveling Salesman Problem
A “branch and bound” algorithm is presented for solving the traveling salesman problem. The set of all tours feasible solutions is broken up into increasingly small subsets by a procedure called branching. For each subset a lower bound on the length of the tours therein is calculated. Eventually, a subset is found that contains a single tour whose length is less than or equal to some lower bound for every tour. The motivation of the branching and the calculation of the lower bounds are based on ideas frequently used in solving assignment problems. Computationally, the algorithm extends the size of problem that can reasonably be solved without using methods special to the particular problem.
16922218
Tabu Search: A Tutorial
Tabu search is a “higher level” heuristic procedure for solving optimization problems, designed to guide other methods (or their component processes) to escape the trap of local optimality. Tabu search has obtained optimal and near optimal solutions to a wide variety of classical and practical problems in applications ranging from scheduling to telecommunications and from character recognition to neural networks. It uses flexible structures memory (to permit search information to be exploited more thoroughly than by rigid memory systems or memoryless systems), conditions for strategically constraining and freeing the search process (embodied in tabu restrictions and aspiration criteria), and memory functions of varying time spans for intensifying and diversifying the search (reinforcing attributes historically found good and driving the search into new regions). Tabu search can be integrated with branch-and-bound and cutting plane procedures, and it has the ability to start with a simple implementation th...
41236005
Honey bees mating optimization algorithm for the Euclidean traveling salesman problem
This paper introduces a new hybrid algorithmic nature inspired approach based on Honey Bees Mating Optimization for successfully solving the Euclidean Traveling Salesman Problem. The proposed algorithm for the solution of the Traveling Salesman Problem, the Honey Bees Mating Optimization (HBMOTSP), combines a Honey Bees Mating Optimization (HBMO) algorithm, the Multiple Phase Neighborhood Search-Greedy Randomized Adaptive Search Procedure (MPNS-GRASP) algorithm and the Expanding Neighborhood Search Strategy. Besides these two procedures, the proposed algorithm has, also, two additional main innovative features compared to other Honey Bees Mating Optimization algorithms concerning the crossover operator and the workers. The main contribution of this paper is that it shows that the HBMO can be used in hybrid synthesis with other metaheuristics for the solution of the TSP with remarkable results both to quality and computational efficiency. The proposed algorithm was tested on a set of 74 benchmark instances from the TSPLIB and in all but eleven instances the best known solution has been found. For the rest instances the quality of the produced solution deviates less than 0.1% from the optimum.
206401003
Memetic Algorithm based on Improved Inver-over operator and Lin-Kernighan local search for the Euclidean traveling salesman problem
In this study, an Improved Inver-over operator is proposed to solve the Euclidean traveling salesman problem (TSP) problem. The Improved Inver-over operator is tested on 14 different TSP examples selected from TSPLIB. The application of the Improved Inver-over operator gives much more effective results regarding to the best and average error values than the Basic Inver-over operator. Then an effective Memetic Algorithm based on Improved Inver-over operator and Lin-Kernighan local search is implemented. To speed up the convergence capability of the presented algorithm, a restart technique is employed. We evaluate the proposed algorithm based on standard TSP test problems and show that the proposed algorithm performs better than other Memetic Algorithm in terms of solution quality and computational effort.
12503625
An Improved Adaptive Multi-Start Approach to Finding Near-Optimal Solutions to the Euclidean TSP
We present an "adaptive multi-start" genetic algorithm for the Euclidean traveling salesman problem that uses a population of tours locally optimized by the Lin-Kernighan algorithm. An all-parent cross-breeding technique, chosen to exploit the structure of the search space, generates better locally optimized tours. Our work generalizes and improves upon the approach of Boese et al. [2]. 
 
Experiments show the algorithm is a vast improvement over simple "multi-start," i.e., repeatedly applying Lin-Kernighan to many random initial tours. Both for random and several standard TSPLIB [5] instances, it is able to find nearly optimal (or optimal) tours for problems of several thousand cities in a few minutes on a Pentium Pro workstation. We find these results are competitive both in time and tour length with one of the most successful TSP algorithms, Iterated Lin-Kernighan.
27359285
A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem
Eight distinct (and in some cases little known) formulations of the Travelling Salesman Problem as an Integer Programme are given. Apart from the standard formulation all the formulations are ‘compact’ in the sense that the number of constraints and variables is a polynomial function of the number of cities in the problem. Comparisons of the formulations are made by projecting out variables in order to produce polytopes in the same space. It is then possible to compare the strengths of the Linear Programming relaxations. These results are illustrated by computational results on a small problem
14538946
The traveling salesman problem: An overview of exact and approximate algorithms
In this paper, some of the main known algorithms for the traveling salesman problem are surveyed. The paper is organized as follows: 1) definition; 2) applications; 3) complexity analysis; 4) exact algorithms; 5) heuristic algorithms; 6) conclusion.
17792012
Traveling Salesman Problem: an Overview of Applications, Formulations, and Solution Approaches
1.1 Origin The traveling salesman problem (TSP) were studied in the 18th century by a mathematician from Ireland named Sir William Rowam Hamilton and by the British mathematician named Thomas Penyngton Kirkman. Detailed discussion about the work of Hamilton & Kirkman can be seen from the book titled Graph Theory (Biggs et al. 1976). It is believed that the general form of the TSP have been first studied by Kalr Menger in Vienna and Harvard. The problem was later promoted by Hassler, Whitney & Merrill at Princeton. A detailed dscription about the connection between Menger & Whitney, and the development of the TSP can be found in (Schrijver, 1960).
11051236
Evaluation of Simulated Annealing to solve fuzzy optimization problems
Simulated Annealing (SA) is a reasonable algorithm for solving optimization problems, through the selection of the best solution among a finite number of possible solutions. It is a particularly attractive technique to solve fuzzy optimization problems, because it allows finding near-optimal solutions, which, in a fuzzy environment, is usually good enough and without a large computational effort. We present a representative set of problems for testing the SA algorithm suitability and performance. The SA performance is measured in terms of the objective function values, considering several trade-offs on constraints satisfaction levels, and computational time to achieve a solution. Furthermore, we discuss the parameters that control the SA algorithm to show how easily they can be manipulated. The set of fuzzy optimization problems tested were formulated following the complete fuzzification method proposed by Ribeiro and Moura-Pires (1999). The results obtained show the flexibility and adaptability of the SA algorithm to solve fuzzy optimization problems.
46165993
Meta-heuristics in cellular manufacturing: A state-of-the-art review
Article history: Received 1 April 2010 Received in revised form 22 July 2010 Accepted 30 July 2010 Available online 1 Auguest 2010 Meta-heuristic approaches are general algorithmic framework, often nature-inspired and designed to solve NP-complete optimization problems in cellular manufacturing systems and has been a growing research area for the past two decades. This paper discusses various metaheuristic techniques such as evolutionary approach, Ant colony optimization, simulated annealing, Tabu search and other recent approaches, and their applications to the vicinity of group technology/cell formation (GT/CF) problem in cellular manufacturing. The nobility of this paper is to incorporate various prevailing issues, open problems of meta-heuristic approaches, its usage, comparison, hybridization and its scope of future research in the aforesaid area. © 2010 Growing Science Ltd. All rights reserved.
2869783
Tuning Meta-Heuristics Using Multi-agent Learning in a Scheduling System
In complexity theory, scheduling problem is considered as a NP-complete combinatorial optimization problem. Since Multi-Agent Systems manage complex, dynamic and unpredictable environments, in this work they are used to model a scheduling system subject to perturbations. Meta-heuristics proved to be very useful in the resolution of NP-complete problems. However, these techniques require extensive parameter tuning, which is a very hard and time-consuming task to perform. Based on Multi-Agent Learning concepts, this article propose a Case-based Reasoning module in order to solve the parameter-tuning problem in a Multi-Agent Scheduling System. A computational study is performed in order to evaluate the proposed CBR module performance.
54652387
Improving Genetic Algorithm with Fine-Tuned Crossover and Scaled Architecture
Genetic Algorithm (GA) is a metaheuristic used in solving combinatorial optimization problems. Inspired by evolutionary biology, GA uses selection, crossover, and mutation operators to efficiently traverse the solution search space. This paper proposes nature inspired fine-tuning to the crossover operator using the untapped idea of Mitochondrial DNA (mtDNA). mtDNA is a small subset of the overall DNA. It differentiates itself by inheriting entirely from the female, while the rest of the DNA is inherited equally from both parents. This unique characteristic of mtDNA can be an effective mechanism to identify members with similar genes and restrict crossover between them. It can reduce the rate of dilution of diversity and result in delayed convergence. In addition, we scale the well-known Island Model, where instances of GA are run independently and population members exchanged periodically, to a Continental Model. In this model, multiple web services are executed with each web service running an island model. We applied the concept of mtDNA in solving Traveling Salesman Problem and to train Neural Network for function approximation. Our implementation tests show that leveraging these new concepts of mtDNA and Continental Model results in relative improvement of the optimization quality of GA.
126142392
Fuzzy Soft Compact Topological Spaces
In this paper, we have studied compactness in fuzzy soft topological spaces which is a generalization of the corresponding concept by R. Lowen in the case of fuzzy topological spaces. Several basic desirable results have been established. In particular, we have proved the counterparts of Alexander’s subbase lemma and Tychonoff theorem for fuzzy soft topological spaces.
73554912
Inner Product over Fuzzy Matrices
The purpose of this study was to introduce the inner product over fuzzy matrices. By virtue of this definition, -norm is defined and the parallelogram law is proved. Again the relative fuzzy norm with respect to the inner product over fuzzy matrices is defined. Moreover Cauchy Schwarz inequality, Pythagoras, and Fundamental Minimum Principle are established. Some equivalent conditions are also proved.
73571930
On Complex Intuitionistic Fuzzy Soft Sets with Distance Measures and Entropies
We introduce the concept of complex 
intuitionistic fuzzy soft sets which is parametric in nature. However, the theory 
of complex fuzzy sets and complex intuitionistic fuzzy sets are independent of the 
parametrization tools. Some real life problems, for example, multicriteria decision making 
problems, involve the parametrization tools. In order to get their new entropies, 
some important properties and operations on the complex intuitionistic fuzzy soft 
sets have also been discussed. On the basis of some well-known distance measures, 
some new distance measures for the complex intuitionistic fuzzy soft sets have 
also been obtained. Further, we have established correspondence between the 
proposed entropies and the distance measures of complex intuitionistic fuzzy soft 
sets.
205939
Optimization by Simulated Annealing
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.
122729427
Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm
We present a Monte Carlo algorithm to find approximate solutions of the traveling salesman problem. The algorithm generates randomly the permutations of the stations of the traveling salesman trip, with probability depending on the length of the corresponding route. Reasoning by analogy with statistical thermodynamics, we use the probability given by the Boltzmann-Gibbs distribution. Surprisingly enough, using this simple algorithm, one can get very close to the optimal solution of the problem or even find the true optimum. We demonstrate this on several examples.We conjecture that the analogy with thermodynamics can offer a new insight into optimization problems and can suggest efficient algorithms for solving them.
19007114
A combinatorial Artificial Bee Colony algorithm for traveling salesman problem
Traveling Salesman Problem is an important optimization issue of many fields such as transportation, logistics and semiconductor industries and it is about finding a Hamiltonian path with minimum cost. To solve this problem, many researchers have proposed different approaches including metaheuristic methods. Artificial Bee Colony algorithm is a well known swarm based optimization technique. In this paper we propose a new Artificial Bee Colony algorithm called Combinatorial ABC for Traveling Salesman Problem. Simulation results show that this Artificial Bee Colony algorithm can be used for combinatorial optimization problems.
32981791
An artificial bee colony algorithm with a modified choice function for the Traveling Salesman Problem
The Artificial Bee Colony (ABC) algorithm is a swarm intelligence approach which has initially been proposed to solve optimization of mathematical test functions with a unique neighbourhood search mechanism. However, this neighbourhood search mechanism could not be directly applied to combinatorial discrete optimization problems. The employed and onlooker bees need to be equipped with problem-specific perturbative heuristics in order to tackle combinatorial discrete optimization problems. However, there is a large variety of available problem-specific heuristics. In this paper, a hyper-heuristic method, namely a Modified Choice Function (MCF), is applied such that it can regulate the selection of the neighbourhood search heuristics adopted by the employed and onlooker bees automatically. The proposed MCF-based ABC model is implemented using the Hyper-heuristic Flexible Framework (HyFlex). To demonstrate the effectiveness of the proposed model, ten Traveling Salesman Problem (TSP) instances available in HyFlex have been evaluated. The empirical results show that the proposed model is able to statistically outperform four out of five ABC variants throughout the optimization process.
41003860
A hybrid artificial bee colony algorithm for the job-shop scheduling problem with no-wait constraint
This paper studies a hybrid artificial bee colony (ABC) algorithm for finding high quality solutions of the job-shop scheduling problem with no-wait constraint (JSPNW) with the objective of minimizing makespan among all the jobs. JSPNW is an extension of well-known job-shop scheduling problem subject to the constraint that no waiting time is allowed between operations for a given job. ABC algorithm is a swarm intelligence technique based on intelligent foraging behavior of honey bee swarm. The proposed hybrid approach effectively coordinates the various components of ABC algorithm such as solution initialization, selection and determination of a neighboring solution with the local search in such a way that it leads to high quality solutions for the JSPNW. The proposed approach is compared with the two best approaches in the literature on a set of benchmark instances. Computational results show the superiority of the proposed approach over these two best approaches.
44256865
Solving the Manufacturing Cell Design Problem Using the Artificial Bee Colony Algorithm
The manufacturing cell design problem (MCDP) proposes to divide an industrial production plant into a number of manufacturing cells. The main objective is to identify an organization of machines and parts in a set of manufacturing cells to allow the transport of parts to be minimized. In this research, the metaheuristic algorithm called Artificial Bee Colony (ABC) is implemented to solve the MCDP. The ABC algorithm is inspired by the ability of bees to get food, the way they look for it and exploit it. We performed two types of experiments using two and three cells, giving a total of 90 problems that have been used to solve the MCDP using ABC. In the results experiments, good results are obtained solving the 90 proposed problems and reaching the 90 global optimum values. Finally, the results are contrasted with two classical metaheuristics and two modern metaheuristics.
19368830
Evaluation of the Simulated Annealing and the Discrete Artificial Bee Colony in the Weight Tardiness Problem with Taguchi Experiments Parameterization
Meta-Heuristics (MH) are the most used optimization techniques to approach Complex Combinatorial Problems (COPs). Their ability to move beyond the local optimums make them an especially attractive choice to solve complex computational problems, such as most scheduling problems. However, the knowledge of what Meta-Heuristics perform better in certain problems is based on experiments. Classic MH, as the Simulated Annealing (SA) has been deeply studied, but newer MH, as the Discrete Artificial Bee Colony (DABC) still need to be examined in more detail. In this paper DABC has been compared with SA in 30 academic benchmark instances of the weighted tardiness problem (1||Σw j T j ). Both MH parameters were fine-tuned with Taguchi Experiments. In the computational study DABC performed better and the subsequent statistical study demonstrated that DABC is more prone to find near-optimum solutions. On the other hand SA appeared to be more efficient.
8902300
Fine-Tuning of Algorithms Using Fractional Experimental Designs and Local Search
Researchers and practitioners frequently spend more time fine-tuning algorithms than designing and implementing them. This is particularly true when developing heuristics and metaheuristics, where the right choice of values for search parameters has a considerable effect on the performance of the procedure. When testing metaheuristics, performance typically is measured considering both the quality of the solutions obtained and the time needed to find them. In this paper, we describe the development of CALIBRA, a procedure that attempts to find the best values for up to five search parameters associated with a procedure under study. Because CALIBRA uses Taguchis fractional factorial experimental designs coupled with a local search procedure, the best values found are not guaranteed to be optimal. We test CALIBRA on six existing heuristic-based procedures. These experiments show that CALIBRA is able to find parameter values that either match or improve the performance of the procedures resulting from using the parameter values suggested by their developers. The latest version of CALIBRA can be downloaded for free from the website that appears in the online supplement of this paper at http://or.pubs.informs.org/Pages.collect.html.
1863673
An experimental investigation of model-based parameter optimisation: SPO and beyond
This work experimentally investigates model-based approaches for optimising the performance of parameterised randomised algorithms. We restrict our attention to procedures based on Gaussian process models, the most widely-studied family of models for this problem. We evaluated two approaches from the literature, and found that sequential parameter optimisation (SPO) [4] offered the most robust performance. We then investigated key design decisions within the SPO paradigm, characterising the performance consequences of each. Based on these findings, we propose a new version of SPO, dubbed SPO+, which extends SPO with a novel intensification procedure and log-transformed response values. Finally, in a domain for which performance results for other (model-free) parameter optimisation approaches are available, we demonstrate that SPO+ achieves state-of-the-art performance.
24233108
Study on the impact of the NS in the performance of meta-heuristics in the TSP
Meta-heuristics have been applied for a long time to the Travelling Salesman Problem (TSP) but information is still lacking in the determination of the parameters with the best performance. This paper examines the impact of the Simulated Annealing (SA) and Discrete Artificial Bee Colony (DABC) parameters in the TSP. One special consideration of this paper is how the Neighborhood Structure (NS) interact with the other parameters and impacts the performance of the meta-heuristics. NS performance has been the topic of much research, with NS proposed for the best-known problems, which seem to imply that the NS influences the performance of meta-heuristics, more that other parameters. Moreover, a comparative analysis of distinct meta-heuristics is carried out to demonstrate a non-proportional increase in the performance of the NS.
15295975
A systematic procedure for setting parameters in simulated annealing algorithms
Abstract Scope and Purpose—Simulated annealing (SA) algorithms have been successfully applied to various difficult combinatorial optimization problems. To apply an SA algorithm to a specific problem, one must design the algorithm by determining methods to represent solutions, to generate neighborhood solutions and to reduce temperature, etc., and then selecting values of parameters used in the algorithm. Since the performance of an SA algorithm generally depends on values of the parameters, it is important to select the most appropriate parameter values. In previous research, parameter values are often selected using experimental designs such as full factorial designs, which require excessive computation time and efforts and frequent human decisions during the design process. In this paper, we suggest a systematic procedure to find appropriate values for parameters quickly without much human intervention by using a nonlinear optimization method. Values of parameters used in simulated annealing (SA) algorithms must be carefully selected since parameter values may have a significant influence on the performance of the algorithm. However, it is not easy to find good parameter values because values of a wide range have to be considered for each parameter and some parameters may be correlated with each other. In this paper, we suggest a procedure which gives good parameter values quickly without much human intervention by using the simplex method for nonlinear programming. To show the performance of the procedure, computational tests are done on a graph partitioning problem, a permutation flowshop scheduling problem and a short-term production scheduling problem. We select values for parameters needed in SA algorithms for the problems using the suggested procedure. The SA algorithms designed with this procedure are compared with existing SA algorithms in which parameter values were selected after extensive experiments.
20356624
SIMULATED ANNEALING METHODS WITH GENERAL ACCEPTANCE PROBABILITIES
Heuristic solution methods for combinatorial optimization problems are often based on local neighborhood searches. These tend to get trapped in a local optimum and the final result is often heavily dependent on the starting solution. Simulated annealing methods attempt to avoid these problems by randomizing the procedure so as to allow for occasional changes that worsen the solution. In this paper we provide probabilistic analyses of different designs of these methods.
58713415
Simulated annealing: A tool for operational research
Abstract This paper describes the Simulated Annealing algorithm and the physical analogy on which it is based. Some significant theoretical results are presented before describing how the algorithm may be implemented and some of the choices facing the user of this method. An overview is given of the experience of experiments with SA and some suggestions are made for ways to improve the performance of the algorithm by modifying the ‘pure’ SA approach.
9420816
Temperature measurement and equilibrium dynamics of simulated annealing placements
One way to alleviate the heavy computation required by simulated annealing placement algorithms is to replace a significant fraction of the higher or middle temperatures with a faster heuristic, and then follow it with simulated annealing. A crucial issue in this approach is the determination of the starting temperature for the simulated annealing phase-a temperature should be chosen that causes an appropriate amount of optimization to be done, but makes good use of the structure provided by the heuristic. A method for measuring the temperature of an existing placement is presented. The approach is based on the measurement of the probability distribution of the change in cost function, P( Delta C), and makes the assumption that the placement is in simulated annealing equilibrium at some temperature. The temperature of placements produced by both a simulated annealing and a min-cut placement algorithm are measured, and good agreement with known temperatures is obtained. The P( Delta C) distribution is also used to give an interesting view of the equilibrium dynamics of simulated annealing. >
40670166
Parameter Tuning for the Artificial Bee Colony Algorithm
While solving a problem by an optimization algorithm, adjusting algorithm parameters have significant importance on the performance of the algorithm. A fine tuning of control parameters is required for most of the algorithms to obtain desired solutions. In this study, performance of the Artificial Bee Colony (ABC) algorithm, which simulates the foraging behaviour of a honey bee swarm, was investigated by analyzing the effect of control parameters.
22447736
Parameter tuning of artificial bee colony algorithm for Gaussian noise elimination on digital images
In this paper, the control parameters of the artificial bee colony algorithm were examined to determine for the best performance of the noise elimination problem on gray level digital images. In order to eliminate a noise, a two dimensional finite impulse response digital filter was designed and the artificial bee colony algorithm was used to adjust its coefficient matrix. For the best selected control parameters, the designed two dimensional finite impulse response digital filter was used to eliminate the Gaussian noise on the gray level digital images at different noise densities and the performance of the designed filter was compared in terms of the noise tolerance.
41525209
The Analysis of Peculiar Control Parameters of Artificial Bee Colony Algorithm on the Numerical Optimization Problems
Artificial bee colony (ABC) algorithm is one of the popular swarm intelligence algorithms. ABC has been developed by being inspired foraging and waggle dance behaviors of real bee colonies in 2005. Since its invention in 2005, many ABC models have been proposed in order to solve different optimization problems. In all the models proposed, there are only one scout bee and a constant limit value used as control parameters for the bee population. In this study, the performance of ABC algorithm on the numeric optimization problems was analyzed by using different number of scout bees and limit values. Experimental results show that the results obtained by using more than one scout bee and different limit values, are better than the results of basic ABC. Therefore, the control parameters of the basic ABC should be tuned according to given class of optimization problems. In this paper, we propose reasonable value ranges of control parameters for the basic ABC in order to obtain better results on the numeric optimization problems.
10769394
A hybrid discrete artificial bee colony algorithm for permutation flowshop scheduling problem
To minimize the makespan in permutation flowshop scheduling problems, a hybrid discrete artificial bee colony (HDABC) algorithm is presented. In the HDABC, each solution to the problem is called a food source and represented by a discrete job permutation. First, the initial population with certain quality and diversity is generated from Greedy Randomized Adaptive Search Procedure (GRASP) based on Nawaz-Enscore-Ham (NEH) heuristics. Second, the discrete operators and algorithm, such as insert, swap, path relinking and GRASP are applied to generate new solution for the employed bees, onlookers and scouts. Moreover, local search is applied to the best one. The presented algorithm is tested on scheduling problem benchmarks. Experimental results show its efficiency.
1946785
A survey of very large-scale neighborhood search techniques
Many optimization problems of practical interest are computationally intractable. Therefore, a practical approach for solving such problems is to employ heuristic (approximation) algorithms that can find nearly optimal solutions within a reasonable amount of computation time. An improvement algorithm is a heuristic algorithm that generally starts with a feasible solution and iteratively tries to obtain a better solution. Neighborhood search algorithms (alternatively called local search algorithms) are a wide class of improvement algorithms where at each iteration an improving solution is found by searching the "neighborhood" of the current solution. A critical issue in the design of a neighborhood search algorithm is the choice of the neighborhood structure, that is, the manner in which the neighborhood is defined. As a rule of thumb, the larger the neighborhood, the better is the quality of the locally optimal solutions, and the greater is the accuracy of the final solution that is obtained. At the same time, the larger the neighborhood, the longer it takes to search the neighborhood at each iteration. For this reason, a larger neighborhood does not necessarily produce a more effective heuristic unless one can search the larger neighborhood in a very efficient manner. This paper concentrates on neighborhood search algorithms where the size of the neighborhood is "very large" with respect to the size of the input data and in which the neighborhood is searched in an efficient manner. We survey three broad classes of very large-scale neighborhood search (VLSN) algorithms: (1) variable-depth methods in which large neighborhoods are searched heuristically, (2) large neighborhoods in which the neighborhoods are searched using network flow techniques or dynamic programming, and (3) large neighborhoods induced by restrictions of the original problem that are solvable in polynomial time.
207225504
TSPLIB - A Traveling Salesman Problem Library
This paper contains the description of a traveling salesman problem library (TSPLIB) which is meant to provide researchers with a broad set of test problems from various sources and with various properties. For every problem a short description is given along with known lower and upper bounds. Several references to computational tests on some of the problems are given. INFORMS Journal on Computing , ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.
14077460
Comparison of Metaheuristics
Metaheuristics are truly diverse in nature—under the overarching theme of performing operations to escape local optima, algorithms as different as ant colony optimization, tabu search, harmony search, and genetic algorithms have emerged. Due to the unique functionality of each type of metaheuristic, comparison of metaheuristics is in many ways more difficult than other algorithmic comparisons. In this chapter, we discuss techniques for meaningful comparison of metaheuristics. We discuss how to create and classify instances in a new testbed and how to make sure other researchers have access to the problems for future metaheuristic comparisons. Further, we discuss the disadvantages of large parameter sets and how to measure complicating parameter interactions in a metaheuristic’s parameter space. Last, we discuss how to compare metaheuristics in terms of both solution quality and runtime.