Improved Ant Colony Algorithms To The Shortest Path Problem In Dynamic Networks

The shortest path problem is very important in the network optimization. In the study of the static network optimization, it is assumed that the weight of the arc in the network is static. In the common circumstances, the algorithm of static network can deal with the problem well, but in reality, the assumption of static network is not suitable, for the weight is usually dependent on time. The study of algorithm of dynamic network, adding the time variable to the network model, breaks the limit of static network. So the model is more flexible and veracious. In this paper, improved ant colony algorithms will be discussed to solve the shortest path problem in the dynamic network.In initialization phase of the generalized ant algorithms, a same value is given to pheromone trail, so the pheromone has not played the role of guidance in the early stage of the computation. This mean that, in the initialization phase, the heuristic value should be treated as a more important factor for the agents to find the solutions. As computation goes on, pheromone trail becomes more and more important to direct agents in finding good solutions. Thus a non-linearity parameter is applied to weight more importance of the heuristic values than pheromone trail in the first iterations. In this way, the relative weigh between the heuristic and pheromone can be adjusted with the development of the algorithm, which improves the convergence speed of the algorithm.In the paper, an algorithm based on pheromone table is also described on the short paths problem of dynamic networks. By using the combination of the ant algorithm and Q-learning algorithm, the new algorithm can increase the convergence speed. The algorithm also reduces the solution instability and route oscillation through the technology of adaptive expectation. This form of improvement can improve the effectiveness of swarm-based algorithm, reinforce the learning ability of the ants, avoid partial optimization solution and strengthen the generalization.