Research On Hybrid Ant Colony Algorithm For Some Combinatorial Optimization Problems

Ant colony algorithm is a swarm intelligence optimization algorithm that simulates the foraging behavior of ants.This algorithm has the characteristics of positive feedback and self-organization,and can effectively solve combinatorial optimization problems.But there are also some shortcomings,such as the algorithm is prone to stagnation,trapped in local optimum,etc.Based on the above,this paper combines the ant colony algorithm with other intelligent algorithms,and applies it to the problem of traveling salesman and vehicle routing.The main research work of the paper is as follows:(1)Combining ant colony algorithm and particle swarm algorithm to solve the traveling salesman problem.By converting the path obtained by particle swarm into the initial pheromone distribution of ant colony,the optimal path is obtained.In the hybrid algorithm,the pheromone volatilization factor of ant colony is adaptively adjusted.The crossover and mutation operations are introduced to the particle swarm.The experimental results show that the proposed algorithm is effective.(2)Ant colony algorithm combined with 2-opt algorithm to solve the spherical traveling salesman problem.On the basis of the ant colony algorithm,the ant colony system is added to update the pheromone,the state transition probability,and the 2-opt optimization is performed on the obtained path.Experimental results show that the performance of this algorithm in solving spherical tsp problems is better than other intelligent algorithms.(3)Ant colony algorithm and k-means algorithm are mixed to solve the vehicle routing problem with capacity.Firstly,the k-means algorithm is used for clustering to meet capacity constraints.Then the ant colony algorithm is used to obtain the optimal path of each cluster.In the hybrid algorithm,the initial value is determined for the k-means algorithm,and the elite strategy is added on the basis of the ant colony algorithm to update the pheromone.Experimental results show that the algorithm has better optimization ability.(4)Ant colony algorithm,thrift algorithm and local search operator are mixed to solve the vehicle routing problem with time window.First,the initial solution of the algorithm is constructed by the parsimony method,and then the pheromone of the algorithm is updated.Finally,the obtained path is optimized by performing 2-opt and -exchange operators.The experimental results show that the performance of the algorithm is better.