Font Size: a A A

Application Research Of Improved Discrete Particle Swarm Optimization Algorithm In Traveling Salesman Problem

Posted on:2018-09-07Degree:MasterType:Thesis
Country:ChinaCandidate:B Y ChengFull Text:PDF
GTID:2348330512459201Subject:Applied Mathematics
Abstract/Summary:PDF Full Text Request
Particle Swarm Optimization(PSO) is a kind of population-based evolutionary algorithm,and has been practically proved to be an effective global optimization algorithm. Because of its easy implementation, few parameters to be adjusted and fast convergence rate, PSO has gained wide applications in areas such as function optimization, data mining and power system. Traveling Salesman Problem(TSP) is one of the most famous classical combinatorial optimization problems in Operations Research, and it has been proved to be an NP complete problem. TSP synthesizes a large class of combinatorial optimization problems with different characteristics, and exists in various forms in transportation, printed circuit board design, data string clustering and other fields.In this dissertation, through analysis and investigation of PSO and TSP, three improved PSO algorithm were proposed: the improved local-search-based chaotic discrete particle swarm optimization(ILCDPSO) algorithm, the particle swarm optimization algorithm based on self-adaptive excellence coefficients(SECPSO), and the self-adaptive particle swarm optimization algorithm based on Cauchy distribution and 3-opt(SCLPSO). All these algorithms are tested on some typical instances in TSPLIB and their performances are compared with several other improved algorithms. The main work is summarized as follows:(1) In view of the drawbacks of the standard discrete Particle Swarm Optimization(PSO)algorithm such as slow convergence speed and easily trapping into local optima, an improved local-search-based chaotic discrete particle swarm optimization algorithm, called ILCDPSO,was proposed. In this algorithm, each edge is assigned an appropriate excellence coefficient based on the principle of roulette selection. This helps to improve the selection probability of short edges, and thus improves the optimization ability and convergence speed of the algorithm. In order to improve the exploration ability of the algorithm, a local search strategy is employed. Moreover, a chaotic sequence is integrated into the iteration formula to enhance the randomness and diversity of particles and hence to increase the global searching ability of the proposed algorithm. The research results indicate that ILCDPSO performs better than other algorithms in terms of convergence speed, global optimization ability and stability.(2) In order to utilize the heuristic information in the problem domain, a particle swarm optimization algorithm based on self-adaptive excellence coefficients(SECPSO) was proposed to improve the ILCDPSO. The SECPSO modifies the static excellence coefficients,so that these coefficients can be adjusted self-adaptively and dynamically according to the process of searching for the solutions. Furthermore, a 3-opt search mechanism is added to improve the accuracy of the solutions and the convergence rate of the algorithm. The experiments results indicate that the proposed SECPSO algorithm performs better in terms of global search ability and convergence rate.(3) In order to further improve the accuracy and stability of SECPSO, a self-adaptive particle swarm optimization algorithm based on Cauchy distribution and 3-opt, called SCLPSO, was proposed through modification of the inertia weight by Cauchy distribution.Due to the introduction of Cauchy distribution, the SCLPSO may have wider search area atearly stage and higher overall stability. The experimental results show that the convergence ratio of SCLPSO is remarkably increased, and the algorithm can rapidly converge to the best known solution and has higher accuracy, hence the comprehensive performance of the algorithm is largely enhanced.
Keywords/Search Tags:particle swarm optimization, travel salesman problem, 3-opt, self-adaptive excellence coefficients, chaotic sequence, Cauchy distribution
PDF Full Text Request
Related items