Dissertation > Excellent graduate degree dissertation topics show

The Research on GA-based Improved Particle Swarm Optimization and Its Application in TSP

Author: LiuHuang
Tutor: ZengChunNian
School: Wuhan University of Technology
Course: Applied Computer Technology
Keywords: particle swarm optimization genetic algorithm convergence global best traveling salesman problem
CLC: TP301.6
Type: Master's thesis
Year: 2010
Downloads: 214
Quote: 4
Read: Download Dissertation

Abstract


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.

Related Dissertations

  1. Development of the Platform for Compressor Optimization Design and Aerodynamic Optimization Design in the Transonic Compressor,TH45
  2. Research on Feature Extraction and Classification of Tongue Shape and Tooth-Marked Tongue in TCM Tongue Diagnosis,TP391.41
  3. The Application of Fuzzy Comprehensive Evaluation Based on Genetic Algorithm in Vocational Evaluation of Classroom Teaching,G712
  4. The Semilocal Convergence Properties of Super-Halley Method and Newton Method under Weak Conditions,O241.7
  5. Dilemma and Way Out of TV Media in Media Convergence Abstract,G206
  6. Fans Cultural Effects in Television Broadcasting,G223
  7. Research on Fuzzy C-Mean Clustering Algorithm Based on Particle Swarm Optimization and Shuffled Frog Leaping Algorithm,TP18
  8. Research on Clustering Algorithm Based on Genetic Algorithm and Rough Set Theory,TP18
  9. Feasibility Study on the Convergence of Community Education and Distance Education,G77
  10. The Discussed on the Zeros and Except Values of Complex Differences Functions,O174.5
  11. Research on Intrusion Detection Based on Feature Selection,TP393.08
  12. Research on the Improvements and Applications of Particle Swarm Optimization,TP18
  13. Convergence analysis of the regional energy consumption intensity,F206;F124
  14. Study on the Relationship between Industrial Structure Upgrading and Convergence Tendency of Financial Services Industry in the Central Region of China,F832.2
  15. Spectral Method for Solving Two Types of Delay Differential Equations,O241.8
  16. Research on Convergence of Regional Economic Growth Across Three Provinces in Northeast China,F127
  17. The Study of Newspaper-Reading-Program on TV Survival State in the Background of Media Convergence,G222
  18. Compulsory Phase of the Basic Concepts of High School Chemistry Teaching and Study of the Convergence of Compulsory Education,G633.8
  19. Research on Limit-Factors in IC Design-Tool Application,TN402
  20. The Research of Inter-Domain Route Flap Damping Algorithm,TP393.02
  21. Research on the TV Spectacle Under the Context of Media Convergence: Take the TV Program "You Are the One" for Example,G206

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > General issues > Theories, methods > Algorithm Theory
© 2012 www.DissertationTopic.Net  Mobile