Font Size: a A A

Improved Particle Swarm Optimization And Ant Colony Optimization For Traveling Salesman Problem

Posted on:2010-04-16Degree:MasterType:Thesis
Country:ChinaCandidate:C GuFull Text:PDF
GTID:2178360275458186Subject:Operational Research and Cybernetics
Abstract/Summary:PDF Full Text Request
Ant colony optimization and particle swarm optimization algorithm is a distinguished group of swarm intelligence algorithm.Because of the efficiency of the algorithm,and easy to realize,they have attracted many scholars.Currently,the two algorithm have been successfully applied to many function optimization and engineering technology,the good results have been achieved.On the other hand,the algorithm in many fields is still in the initial stage,the algorithm itself exists some shortcomings.Traveling salesman problem is one of the oldest and has been widely studied combinatorial optimization problem.So far,there have many different methods put forward for solving the traveling salesman problem.Due to many drawbacks of uncertainty algorithm, more and more metaheuristic algorithm was concerned in this field.Currently,ant colony optimization algorithm and particle swarm optimization algorithm have been applied to the traveling salesman problem solving,the good results are obtained.However,Compared with some special heuristic methods for solving TSP,the proposed algorithm still have certain disparity in the solution's quality.Therefore,how to make the modified algorithm have better performance is important.On the basis of previous work,Ant colony optimization algorithms,particle swarm optimization algorithm and its application in the traveling salesman problem is studied in this paper.Main job is as follows:1.For ant colony algorithm easily fall into the local optimal,this paper proposed a dynamic adaptive ant colony algorithm based on the arrangement.First,in order to avoid algorithm stagnation at the late,the Minimum of the pheromone was set for a Non-zero constant value,according to the solution's quality,select several of the best ants release pheromone,to enhance the ants ability to explore the optimal solution at the late, Secondly,adopt a more intelligent pseudorandom proportional,so that ants can dynamically adjusting the balance coefficient between exploring and developing in the search process,overcome the disadvantages of premature convergence and stagnation phenomenon,and improve the search ability of the algorithm.Finally,in order to verify the effectiveness and feasibility of the proposed method,the examples in standard library TSPLIB have been tested and the numerical results are given. 2.To overcome the disadvantages of premature convergence and stagnation phenomenon of the standard particle swarm optimization algorithm,this paper proposes an improved particle swarm optimization algorithm for the traveling salesman problem.Firstly.in the process of selecting an initial population,the modified greedy strategy is used to directly obtain a population of high-performance initial solutions to improve the search efficiency of the algorithm.Secondly,through introducing sub-optimal attractor,the particles in the search process can make full use of the population information to improve their own performance,so as to effectively inhibit stagnation in the process of convergence,and improve the search ability of the algorithm.Finally,in order to verify the effectiveness and feasibility of the proposed method,the examples in standard library TSPLIB have been tested and the numerical results are given.
Keywords/Search Tags:Ant Colony Optimization, Partical Swarm Optimization, Greedy Strategy, Traveling Salesman Problem, Combinatorial Optimization
PDF Full Text Request
Related items