Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Particle Swarm Optimization <s> A concept for the optimization of nonlinear functions using particle swarm methodology is introduced. The evolution of several paradigms is outlined, and an implementation of one of the paradigms is discussed. Benchmark testing of the paradigm is described, and applications, including nonlinear function optimization and neural network training, are proposed. The relationships between particle swarm optimization and both artificial life and genetic algorithms are described. <s> BIB001 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Particle Swarm Optimization <s> In This work we present a particle swarm optimization algorithm to solve the single machine total weighted tardiness problem. A heuristic rule, the smallest position value (SPV) rule, is developed to enable the continuous particle swarm optimization algorithm to be applied to all classes of sequencing problems, which are NP-hard in the literature. A simple but very efficient local search method is embedded in the particle swarm optimization algorithm. The computational results show that the particle swarm algorithm is able to find the optimal and best-known solutions on all instances of widely used benchmarks from the OR library. <s> BIB002 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Particle Swarm Optimization <s> Capacitated vehicle routing problem (CVRP) is an NP-hard problem. For large-scale problems, it is quite difficult to achieve an optimal solution with traditional optimization methods due to the high computational complexity. A new hybrid approximation algorithm is developed in this work to solve the problem. In the hybrid algorithm, discrete particle swarm optimization (DPSO) combines global search and local search to search for the optimal results and simulated annealing (SA) uses certain probability to avoid being trapped in a local optimum. The computational study showed that the proposed algorithm is a feasible and effective approach for capacitated vehicle routing problem, especially for large scale problems. <s> BIB003 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Particle Swarm Optimization <s> In this paper, we proposed a modified version of binary particle swarm optimization algorithm (MBPSO) to solve combinatorial optimization problems. All particles are initialized as random binary vectors, and the Smallest Position Value (SPV) rule is used to construct a mapping from binary space to the permutation space. We also propose new formula to update the particles' velocities and positions. The algorithm is then applied to the permutation flow shop problem (PFSP). To avoid the stagnation, local search and perturbation are employed to improve the performance. Performance of the proposed algorithm is evaluated using the benchmarks of flow shop scheduling problems given by Taillard, (1993). Experimental results show that the algorithm with local search and perturbation is more effective. <s> BIB004 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Particle Swarm Optimization <s> A discrete version of particle swarm optimization (DPSO) is employed to solve uncapacitated facility location (UFL) problem which is one of the most widely studied in combinatorial optimization. In addition, a hybrid version with a local search is defined to get more efficient results. The results are compared with a continuous particle swarm optimization (CPSO) algorithm and two other metaheuristics studies, namely, genetic algorithm (GA) and evolutionary simulated annealing (ESA). To make a reasonable comparison, we applied to same benchmark suites that are collected from OR-library. In conclusion, the results showed that DPSO algorithm is slightly better than CPSO algorithm and competitive with GA and ESA. <s> BIB005 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Particle Swarm Optimization <s> Particle Swarm Optimization is a population-based method inspired by the social behaviour of individuals inside swarms in nature. Solutions of the problem are modelled as members of the swarm which fly in the solution space. The improvement of the swarm is obtained from the continuous movement of the particles that constitute the swarm submitted to the effect of inertia and the attraction of the members who lead the swarm. This work focuses on a recent Discrete Particle Swarm Optimization for combinatorial optimization, called Jumping Particle Swarm Optimization. Its effectiveness is illustrated on the minimum labelling Steiner tree problem: given an undirected labelled connected graph, the aim is to find a spanning tree covering a given subset of nodes, whose edges have the smallest number of distinct labels. <s> BIB006 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Particle Swarm Optimization <s> Particle Swarm Optimization (PSO) belongs to a class of algorithms inspired by natural social intelligent behaviors, called Swarm Intelligence (SI). PSO has been successfully applied to solve continuous optimization problems, however, its potential in discrete problems has not been sufficiently explored. Recent works have proposed hybridization of PSO using local search and Path relinking algorithms with promising results. This paper aims to present a hybrid PSO algorithm that uses local search and Path relinking too, but differently to the previous approaches, this works maintains the main PSO concept for the update of the velocity of the particle. The paper describes the proposed algorithm and a set of experiments with the Traveling Salesman Problem (TSP). The results are compared to other Particle Swarm Optimization algorithms presented previously for the same problem. The results are encouraging and reinforce the idea that PSO algorithms can also provide good results when dealing with discrete problems. <s> BIB007 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Particle Swarm Optimization <s> Multidimensional knapsack problem (MKP) is very important and NP-hard. A strategy of mimetic profit/weight ratio (P/W-Rt) is proposed and accordingly, a fast particle swarm optimization algorithm is proposed. The most important merit of this strategy is that it can effectively solve MKP with arbitrary number of constraints under similar computing costs as one dimensional KP. Experiments illustrate the robust performance, efficiency, and computing costs independence with instance scale. <s> BIB008 </s> Survey of Metaheuristic Algorithms for Combinatorial Optimization <s> Particle Swarm Optimization <s> Particle Swarm Optimization (PSO) is a metaheuristic inspired on the emerging social behavior found in nature. PSO has shown good results in some recent works of discrete optimization, even though it was originally designed for continuous optimization problems. This paper models the problem of allocating a set of cabs to some customers as a combinatorial problem whose optimization goal is to minimize the distance traveled by the fleet. This problem can be categorized as a Task Assignment Problem, being optimized in this paper by two versions of the discrete PSO: the first approach that is based on a binary codification and the second one which uses permutations to encode the solution. The obtained results show that the second approach (permutation encoding) is superior than the first one (binary encoding) in terms of quality of the solutions and computational time, and it is capable of achieving the known optimal values whenever they are available. <s> BIB009
Particle Swarm Optimization (PSO) was proposed by Eberhart and Kennedy in 1995. PSO BIB001 is a computational optimization technique which is inspired by the social behavior of bird flocking. PSO is a searching technique utilizes a group of particles that move through the search space to find the global minimum. In PSO, a group of particles is initialized randomly. Each particle represents a possible solution and then iteratively finds the optimal solution. There are basically two extremes called as local and global extreme. Fitness value is calculated. If it is better than it is set as new local best. Now choose the particle with the best fitness value of all particles as the global best. Finally each particle velocity and particle position is calculated and updated. Ayed Salman et al. (2002) proposed PSO to solve task assignment problem. In this new task assignment algorithm is presented which is based on the principle of PSO. The effectiveness of the proposed PSO based algorithm is demonstrated by comparing it with another population based heuristic known as genetic algorithm. Experiment shows that PSO based algorithm is a viable approach for traveling salesman problem  . Kang-Ping Wang et al. (2003) proposed PSO to solve traveling salesman problem. In this paper, the author proposed the concept of swap operator and swaps sequence and redefined some operators on the basis of them. Experiment shows that result achieved are quite better  . Tasgetiren et al.  proposed PSO to solve the single machine total weighted tardiness problem. This paper embedded an efficient local search method and a heuristic rule known as Smallest Position Value (SPV) to the continuous PSO for solving sequencing problem BIB002 . Chen et al. (2006) proposed a hybrid PSO algorithm to solve the capacitated vehicle routing problem. In this, discrete PSO is used which merges the global search and local search to achieve an optimal solution and also simulated annealing is used to avoid being trapped in local minimum BIB003 . BIB004 proposed a modified version of binary PSO that uses Smallest Position Value (SPV) heuristic rule to solve permutation flow shop problem. Also, local search and perturbation is used to improve the convergence speed of the algorithm BIB004 . Guner and Sevkli (2008) proposed a discrete PSO for solving the uncapacitated facility location problem. Here a local search is used to provide more efficient result BIB005 . BIB006 proposed discrete PSO for solving the minimum labeling steiner tree problem. In this paper a discrete PSO called Jumping Particle Swarm Optimization (JPSO) is introduced. JPSO is compared with another algorithm and found that JPSO outperformed all other algorithm achieving high quality solutions in fewer amounts of computational efforts BIB006 . BIB007 proposed a hybrid PSO algorithm to solve the traveling salesman problem. The hybrid approach uses the concept of local search and path relinking BIB007 . BIB009 proposed to solve the task assignment problem. In these two versions are used, one is based on binary codification and other uses permutation to encode the solution. The experiment shows that the permutation encoding is better than the binary encoding BIB009 . Kunpeng Kang (2012) proposed a fast PSO algorithm for solving large scale multidimensional knapsack problem (MKP). In this paper, a strategy of mimetic Profit/Weight ratio (P/W-Rt) is introduced which can effectively solve MKP with arbitrary number of constraints under same computational cost as one dimensional knapsack problem. Experiment shows the efficient and robust performance of the proposed algorithm. Another advantage of the proposed algorithm is that it is quite flexible to the size of the MKP instance BIB008 .