Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Simulated Annealing <s> Abstract Recently there has been some interest in the use of Simulated Annealing to obtain ‘good’ solutions to a number of combinatorial problems. This paper reports on the use of this method applied to the Quadratic Assignment Problem (i.e. the assignment of inter-communicating objects to locations to minimize the total cost of communication between them). The result is a much-improved annealing scheme for this problem which performs well on a range of examples, finding improved solutions for several of the largest problems available in the literature and requiring only modest amounts of computational effort. <s> BIB001 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Simulated Annealing <s> We describe an approximation algorithm for the problem of finding the minimum makespan in a job shop. The algorithm is based on simulated annealing, a generalization of the well known iterative improvement approach to combinatorial optimization problems. The generalization involves the acceptance of cost-increasing transitions with a nonzero probability to avoid getting stuck in local minima. We prove that our algorithm asymptotically converges in probability to a globally minimal solution, despite the fact that the Markov chains generated by the algorithm are generally not irreducible. Computational experiments show that our algorithm can find shorter makespans than two recent approximation approaches that are more tailored to the job shop scheduling problem. This is, however, at the cost of large running times. <s> BIB002 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Simulated Annealing <s> The quadratic assignment problem (QAP) is one of the well-known combinatorial optimization problems and is known for its various applications. In this paper, we propose a modified simulated annealing algorithm for the QAP - M-SA-QAP. The novelty of the proposed algorithm is an advanced formula of calculation of the initial and final temperatures, as well as an original cooling schedule with oscillation, i.e., periodical decreasing and increasing of the temperature. In addition, in order to improve the results obtained, the simulated annealing algorithm is combined with a tabu search approach based algorithm. We tested our algorithm on a number of instances from the library of the QAP instances - QAPLIB. The results obtained from the experiments show that the proposed algorithm appears to be superior to earlier versions of the simulated annealing for the QAP. The power of M-SA-QAP is also corroborated by the fact that the new best known solution was found for the one of the largest QAP instances - THO150. <s> BIB003 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Simulated Annealing <s> Evolutionary algorithms adopt a natural-selection analogy, exploiting concepts such as population, combination, mutation, and selection to explore a diverse space of possible solutions to combinatorial optimization problems while, at the same time, retaining desirable properties from known solutions. This paper describes an evolutionary approach to improving solutions to mixed integer programming (MIP) models. We propose coarse-grained approaches to mutating and combining MIP solutions, both built within a large-neighborhood search framework. These techniques are then integrated within a MIP branch-and-bound framework. The resulting solution-polishing heuristic often finds significantly better feasible solutions to very difficult MIP models than do available alternatives. In contrast to most evolutionary algorithms, our polishing heuristic is domain-independent, requiring no structural information about the underlying combinatorial problem, above and beyond the information contained in the original MIP formulation. <s> BIB004 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Simulated Annealing <s> We present an efficient metaheuristic based on Simulated Annealing for solving the p-Median problem. These ideas are tested on the well known OR-Lib set of problems with excellent results. <s> BIB005 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Simulated Annealing <s> We study the circular packing problem (CPP) which consists of packing a set of circles of known radii into a larger containing circle without overlapping. The objective is to determine the smallest radius of the containing circle and the coordinates of the center of every packed circle. To solve CPP, we propose a heuristic simulated annealing (HSA) algorithm that incorporates heuristic neighborhood search mechanism and the gradient descent method into the simulated annealing procedure. The special neighborhood search mechanism can avoid the disadvantage of blind search in the simulated annealing algorithm and the gradient descent method can speed up searching the global optimal configuration. The computational results, on a set of instances taken from the literature, show the effectiveness of the proposed algorithm. <s> BIB006
Simulated annealing [64] was first proposed by Kirkpatrick et al. in 1983 . It is a randomized local search algorithm that had an explicit strategy to escape from local minima. The algorithm is analogous to the physical annealing process. Modification to the current solution results in an increasing solution cost that can be accepted with some probability. Iteratively, modification to the current solution is done by randomly selecting a move from the neighborhood. If it is an improving solution, then it is automatically accepted as a new current solution otherwise, it will be accepted (according to the Boltzmann distribution) with certain probability using a control parameter called the Temperature. When the temperature is high and the cost increase is low then the move may accepted with certain probability. According to predefined cooling schedule, the temperature is increasing turned down. When the temperature is adequately low, then method stops at a local optimum by allowing only improving moves. David T. BIB001 proposed an improved simulated annealing for solving quadratic assignment problem. The experiment shows that it is a much improved annealing scheme for this problem, finding better solutions with less amount of computational effort BIB001 . Laarhoven et al. (1992) proposed simulated annealing for solving the job shop scheduling problem. The proposed approach involves the acceptance of cost increasing transitions with a non zero probability to avoid being trapped in local minima BIB002 . Alfonsas (2003) proposed a modified simulated annealing for solving quadratic assignment problem. The proposed approach contains an advanced formula for the computation of initial and final temperature and also cooling schedule with oscillation. In order to improve the performance simulated annealing is merged with a tabu search algorithm BIB003 . Huajin jang et al (2006) proposed a simulated annealing for solving traveling salesman problem. In this a new Columnar Competitive Model (CCM) is introduced with the winnertakes-all (WTA) learning rule for solving the combinatorial optimization problem BIB004 . A.Al-khedhairi (2008) proposed simulated annealing for solving p-median problem. The purpose is to find the optimal (or near optimal) solution of the P-median problem BIB005 . In (2009) Jingfa liu et al. proposed a heuristic simulated annealing algorithm to solve the circular packing problem. The proposed Heuristic Simulated Annealing (HSA) algorithm includes a heuristic neighborhood search mechanism and the gradient descent method into the simulated annealing method. The neighborhood search mechanism can avoid the shortcomings of blind search in the simulated annealing and the gradient descent method can stimulate searching the global optimal configuration BIB006 . Xu Hao (2010) proposed a heuristic algorithm for solving traveling salesman problem. The approach involves the crossover and mutation operator to achieve a balance between speed and accuracy. Experiment shows that algorithm is better than the traditional method  .