The Research On GA-based Improved Particle Swarm Optimization And Its Application In TSP

With the development of technology, optimization problems in the practical application present some characteristics such as nonlinear, large-scale, difficult modeling, complication and so on, and traditional methods have been difficult to resolve these problems, so this forces us to find intelligent, efficient optimization methods. Particle Swarm Optimization (PSO) is a swarm intelligence optimization algorithm, which is from the simulation and modeling of birds'group behaviors such as flying and foraging. PSO theory is very simple. At first, PSO randomly initializes a group of particles (random solutions), than in the iteration process updates particle state by particle best and global best, and lastly searches out the global optimal solution in the solution space. PSO receives widespread attention of many scholars, and has been applied to many practical engineering.This thesis has carried on the detailed analysis and the research to PSO. Through introducing the thought of GA, this thesis has made the improvement to PSO to improve the optimization speed and optimization precision of PSO, and applies the improved PSO algorithm to the practical problems. The main research works of this thesis are as follows:According to the lack of sound mathematical theory of PSO, this thesis has carried on the analysis to particle movement trajectories of PSO, and has obtained that the change process of particle speed vector and position vector is non-homogeneous second-order difference equations. This thesis has proved the convergence of the standard PSO, and has calculated the convergence conditions of PSO. Meanwhile, this thesis has carried on the analysis to the time complexity of PSO algorithm, and the magnitude of its time complexity is O(mnD).According to the disadvantages that standard PSO exists such as slow convergence speed, lower convergence precision, and easily falling into local best, a GA-based improved PSO (GPSO) is proposed through introducing the selection, crossover and variation operation of GA. In the iteration process, GPSO algorithm retained the excellent characteristics of particles through the selection, crossover and variation operation, and also increased the population diversity, then particle can jump out the local best to avoid "precocious" phenomenon and converge to global best. The experimental results demonstrate that GPSO is better than standard PSO both in the convergence speed and convergence precision, and makes the good optimization effect.In order to apply the GA-based GPSO to solve the Traveling Salesman Problem, this thesis proposes a GPSO algorithm model for solving TSP. This thesis carries on the test experiment to the GPSO with testing examples of TSP, and compares the GPSO to the ACO algorithm. The experimental results demonstrate that GPSO algorithm has obvious optimization effect in solving TSP. Relative to the ACO algorithm, GPSO algorithm is better than the ACO algorithm whether in the search speed, search precision, or in the algorithm running time.