Research On The Application Of Swarm Intelligence Algorithms For Uncertain Traveling Salesman Problem

The main contents of this dissertation include the definition ofuncertain TSP problem model and using swam intelligence basedalgorithms to solve this problem.The uncertain TSP problem is based on theuncertain programming theory. The evaluation standard is also proposed inthis thesis. Algorithms which used in this dissertation include Ant ColonyAlgorithm and Particle Swarm Optimization.Sometimes, people can get certain information, but in most cases, it isuncertain. Uncertain theoryand optimization have not onlyacademic value,but also have broad application foreground. The uncertain models include:expectation model, chance constrained model and related chanceconstrained model. In this thesis, chance constrained model is mainlydiscussed.In this thesis, uncertain TSP problem model is proposed firstly. Thismodel makes the distance of each path dynamic. For practice, this modelconsiders the uncertain situation of the traffic movement, so it is moreflexible and has more practical value than the classic TSP model. Thismodel can be used to guide vehicles to select routes.UncertainTSPproblemisdefinedasfollow:For an undirected and weighted graph G = (V , E), V = (1,2,..., n)isthe collection of nodes, and E is the collection of edges. The weight ofany two node i,j is defined as follow:assuming the static distance isd_i,j' (d_i,j'>0, d_i,j'=+∞,i,j∈V)and the real distance is d_i,j. d_i,j obeys thed_i,j' relative randomly distribution. The object function of uncertain TSP isformally defined as:Based on the definition of uncertain TSP problem and in order toevaluating the result effectively, path deviation and the degree of pathdeviation are defined. The circumstance which the uncertain informationdepends on is implemented through triangular distributionIn order to solve the problem of lacking evaluation standard foruncertain problems now, in this paper, the evaluation method in term ofconfidence interval and the robust of algorithm is proposed in this paper.Swarm intelligent algorithms are origin from simulating some natural species'evolutionary process or the behavior of searching food. The swarm of swarmintelligence is defined as a group of principal parts which can communicate with eachother directly or indirectly (through changing the local environment). This group ofprincipal parts can work together to solve distributed problems. The so called swarmintelligence is that the unintelligent principal parts can show intelligent characteristicthrough cooperating with each other. The swarm intelligence gives a base for solvingcomplex distributed problems when there is neither center control nor global models.The ant colony algorithm proposed by J.Kennedy and PSO proposed by M.Dorigo isthe classic practice of the swarm intelligent algorithm.Particle Swarm Optimization is proposed several years before anddeveloping quickly. It is proposed by Kennedy and Eberhart in the year of1995. It is an iterative algorithm. Currently, the research of PSO algorithmfocuses on the continuous PSO, which uses continuous values to describethe states of particles and the rules of the particle's movement.There is littleresearch for discrete PSO. In this thesis, a novel advanced discrete PSOalgorithm is proposedto solve the uncertain TSP problem.Each particle hasintelligence in this algorithm, which make the particle learn from both thelocal optimal results and global optimal result. This method can acceleratethespeed of convergence and avoidtrappinglocal optimal result.Results ofexperiment show that this algorithm performs well for the uncertain TSPproblem. At the emulation experiment, results show that the discrete PSOwith the learning mechanism can converge more swift than the classicdiscretePSO.Ant colony algorithm is a novel simulating evolutionary algorithm. Itis proposed by an Italy scholar: Dorigo and based on the research of thecongregate behavior of real ant colony. Ant colony algorithm and a varietyof improved ant colonyalgorithms have been applied on manyareas. Usingthe classic ant colony algorithm to solve the combinational optimizationproblem has the disadvantages of low converge speed, and easy to betrapped into the local optimization and so on. In order to improve thealgorithm's searching speed and the ability of global searching, this paperusing a novel method: use a hybrid approach based on ant algorithm tosolve uncertain TSP problem. 3-opt method is used to do local optimizingfor the result and to renew the global pheromone. The result of experimentshows that: this algorithm has good performance for the uncertain TSPproblem.Anotherexperiment forthis algorithm istheemulationexperiment.For the feature of the ant colony algorithm itself, this experiment comparesthepathdeviationdegree got bythealgorithm withinfluencefact totheonewithout influence factor. Results show that the path which is select by thealgorithm with influence factor has low deviation degree. Results ofuncertain TSP experiment show that this algorithm have good performancefortheuncertainTSPproblem.At last,results of these twoalgorithms'emulationexperiments arealsocompared. Experimental results show that: each method has its ownadvantages. For the confidence area, the advanced PSO gets the result ofeffective confidence degree: 73.3% and the ant colony algorithm get theresultof76.7%.ItshowsthatantcolonyalgorithmisalittlebetterthanPSO.For the robust of algorithms, both of them have well robust, but advancedPSOisalittlebetter.The last part of this paper gives some discussions. It also gives somehope for the future work. For example: the advanced research of morecomplex uncertain combination problem: the problem of vehicle selectingtherouts.