Application Research Of PSO For Combinatorial Optimization Problems

Particle Swarm Optimization was firstly proposed by Dr.Kennedy and Dr.Eberhart in 1995, and it is an optimization algorithm base on swarm intelligence. It is an evolutionary computation technique inspired by the research of birds looking for food. In biological population, individual influences each other and affects each other; also individual influences and affects the population. These influence and affection are realized as the mechanism of information share. PSO simulates this social behavior and forces the population evolving by sharing the experience. PSO's concept is simple and easy to implement, so it has developed fast. Currently it is used for Multi-objective Optimization, Pattern Recognition, Signal Processing, Decision Support, System Control, Pattern Classification, Fuzzy System Control, Neural Network Training.Combinatorial Optimization Problem, is a kind of mathematical programming, which finds the optimal subset according to find an objective among the subsets ,which satisfy the conditions, of the given finite set, also called Combinatorial Programming Problem. TSP(Traveling Salesman Problem) and FSP(Flow Shop Scheduling Problem) are two famous combinatorial optimization problems.The Traveling Salesman Problem can be described as follows: one traveling salesman wants to visit N cities, the restriction is every city must be visited once and only once, and finally go back to the starting city. The object is to find a minimal length tour.The Flow Shop Scheduling Problem can be described as follows: there are N jobs, and every job has m subjobs. These subjobs are processed on the m machines. The object is to find a scheduling that has the minimal process time. The arrange of the jobs need to satisfy the restrictions: every subjob must be processed on every machine once and only once, every machine can process one workpiece at any time, and the orders of processing every subjobs are the same.In natural science, economics and engineering science etc., many optimization problems need to be considered for multi-objectives which are conflict. This kind of problem is called multi-objective optimization problem. Because the objectives of multi-objective optimization problem are conflict, this kind of problems do not have the single solution to make every objective optimal. The optimal solution is a solution set.This paper based on basic particle swarm optimization algorithm, through researching some improved particle swarm optimization algorithms and combinatorial optimization problem, propose some improved particle swarm optimization algorithms for combinatorial optimization problem. Many experimentations have been done on TSP and FSP. The results show the validity of the algorithms.The first chapter of this paper mainly introduce the algorithm of particle swarm optimization. Describing the inspiration of particle swarm optimization, algorithm procedure and the choice of parameters. Finally researching the development of some discrete particle swarm optimization algorithm.The second chapter mainly introduce the combinatorial optimization problem. Describing two typical combinatorial optimization problems, TSP and FSP detailedly. This paper will take the two problems for instance to introduce how to use the improved discrete particle swarm optimization algorithm to solve combinatorial optimization problems.An improved discrete particle swarm optimization algorithm based on permutation is proposed in the third chapter. Particle is denoted a arrange of N cities in the problem of TSP. So the renovate formula for particle's position and velocity in criterion particle swarm optimization has to be improved. Redefine the operators of the formula. In order to overcome the problem of premature convergence, a novel depressor is proposed to increase the diversity of the swarm and a diversity measure to control the swarm is also introduced which can be used to switch between the attractor and depressor. In order to improve the convergence speed of the algorithm, a novel strategy of dynamic inertia weight is proposed. At the different phases of the algorithm, inertia weight self-adapt changes along with the times of iteration. The proposed algorithm has been applied to a set of benchmark problems and compared with the existing algorithms for solving TSP using swarm intelligence. The results show that it can prevent premature convergence to a high degree, but still keeps a rapid convergence.In the fourth chapter, two hybrid PSO algorithm are proposed to solve the flow shop scheduling problem with the objective of minimizing makespan. It combines the particle swarm optimization algorithm with crossover and mutation operators together effectively. An objective function of flow shop scheduling problem, makespan, has been introduced, a novel method is proposed to compute it. In the first part of this chapter, swarm activity is imported to the algorithm, through mutate the particle's personal best position whose energy is lesser, increase new information into the swarm, lead the particles to search the other space, prevent premature convergence of the algorithm. A random greedy neighbor search strategy is proposed. The particle energy of the algorithm is redefined. We use particle similarity and particle energy to control the search ability of particles. The threshold of particle similarity dynamically changes with iterations and the particle energy depends on the swarm evolving degree and the particle's evolving speed. We use 6 different mutation strategy on different scale problems of FSP for many experimentation, then have a compare and analysis.In the fifth chapter, we mainly propose a particle swarm optimization algorithm used to solve multi-objective flow shop scheduling problem. A method to select particle's personal best position and global best position is proposed. We apply it on the problem of FSP with two objectives. The results show that the algorithm could find the nearly exact Pareto optimal set which have good distributing.