The Research Of Convex-Guided Ant Colony Algorithm On Path Optimization Problem

As a classic problem in combinatorial optimization problems,Traveling Salesman Problem(TSP)which belongs to NP-hard problems has become a research hotspot.With the advantages of distributed computing,organization,positive feedback,robustness and easily being combined with other algorithms,Ant Colony Algorithm(ACA)is widely used to solve combinatorial optimization problems.However,ACA also has some shortcomings,such as easily sinking into the state of stagnation or poor quality of results while solving problems.Based on the above reasons,on the basis of reading related literature and books,this thesis chooses the shortcomings of ACA as breakthroughs,and combine these together with some existing optimization and related graph theory models which were used to solve the path planning TSP problem,and finally proposes an ant colony algorithm of partially optimal programming guided by dynamic convex hull to solve the TSP problem.In addition,on the basis of the above improved algorithm,this thesis makes a further improvement in quicken the convergence speed,and proposes a S-ACADCG algorithm based on the reconstructed Sigmoid function.The main researches and improvements of this thesis include:(1)In term of the selection range of ants' urban nodes,according to the effects of ant traversing,we control ants to choose the selection range of urban nodes dynamically in order to solve the problem of large selection range in the initial period.This strategy will greatly reduce the search space,save the search time,and also help the algorithm to follow and control the direction of ant traverse.(2)In the aspect of urban node selection strategy,aiming at the weakness of ACA,such as falling into local optimum or low quality of results,the delaying drift factor and convex hull are introduced into ACA.The delaying drift factor will increase diversities of traversal solutions in the early stage and lead the direction of ants with help of convex hull which was built by ants between two neighboring urban nodes.In other words,ants will first choose nodes which were not visited in the area of intersection of nearest existing convex hull to avoid jumping out of nearby nodes,so that we can improve the quality of results because ants won't trace back to nodes they missed and non-optimal paths will be decreased.(3)In term of pheromone updating,algorithm leads the following generation of ants partial optimal programming in searching paths and reduces the probability of selecting non-optimal paths through the direction which gained by convex hull that built by paths ants have visited,which also means algorithm uses update-formula to decrease pheromone in non-optimal paths or paths which bring non-optimal paths by means of existing convex hull and the angle of convex hull.Furthermore,in order to having further control of ACA,according to classifications,algorithm choose to update global pheromone by two unsynchronized ways which combine together with local and global path information of ants for higher accuracy.(4)In the pheromone control strategy,in order to reduce the number of iterations of ACA,the sigmoid function is reconstructed according to iterative characteristics of the algorithm in different period and the traditional Sigmoid function,then the reconstructed Sigmoid function works with original pheromone upper-lower limit control formula to control pheromone in different degrees in all three stages of the algorithm,which not only inhibits the stagnation of the algorithm due to the large gap between the pheromone concentration on the edge and the edge,but also improves the convergence speed of the algorithm.