Shulou(Shulou.com)06/01 Report--

This article will explain in detail the example analysis of the ant colony algorithm in big data. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.

The basic idea of the ant colony algorithm applied to solve the optimization problem is that the feasible solution of the optimization problem is expressed by the ant walking path, and all the paths of the whole ant colony constitute the solution space of the optimization problem. The ants with shorter paths released more pheromones. With the passage of time, the concentration of pheromones accumulated on the shorter paths gradually increased, and the number of ants who chose this path became more and more. Finally, the whole ant will concentrate on the best path under the action of positive feedback, which corresponds to the optimal solution of the problem to be optimized.

Because the core idea of ant colony algorithm is "pheromone", there are two key steps to solve TSP problem by ant colony algorithm.

Step 1: calculate the probability of choosing to transfer to the next city based on the concentration of pheromones

Step 2: update pheromone concentration

First, set some basic parameters: let the number of the whole ant colony be m, the number of cities n, and the distance between city I and city j be dij,t when the concentration of pheromone on the path of connection between city I and city j is

. At the initial moment, the concentration of pheromone on the connecting path of each city is the same (because the ants have not yet started to walk).

.

Step 1: as we mentioned earlier, ants can sense the concentration of pheromones on a certain path and choose to follow that path according to the concentration of pheromones. The idea mentioned by the editor earlier is similar to that of "roulette", but there is a slight difference.

This formula shows the probability of ant k moving from city I to city j at t time, where, for the collection of cities to be visited by ant k, there are (nMul 1) elements at the beginning, that is, including other cities except ant k, with the passage of time, the elements in it continue to decrease until it is empty, which means that all cities have been visited. The greater the value of the pheromone importance factor, the greater the role of the pheromone concentration in the transfer; the greater the importance influence factor, the greater the role in the transfer, that is, the ant will transfer to the city with the shortest distance with greater probability.

Step 2 detailed explanation: after calculating the transfer probability, the ant must move to the next city, and the pheromone concentration on different paths must change, because the ant has just passed this route. As mentioned earlier, while ants release pheromones, the pheromones on the connection paths of each city are gradually disappearing, and the parameter () indicates the degree of volatilization of pheromones. So when all ants complete a cycle (meaning that all ants have found their own path, these ants will update the pheromone concentration on each connection path and then carry out a new round of "finding the best path activity". This is actually an iterative process), and the pheromone concentration on the connection path between cities needs to be updated in real time.

The pheromone concentration update formula is given below.

Among them, it represents the pheromone concentration released by the k ant on the connection path between city I and city j, and the sum of the pheromone concentration released by all ants on the connection path between city I and city j.

Where Q is a constant, which represents the total amount of pheromones released by the ant cycle, and Lk is the length of the path of the k-th ant.

To sum up, the flow chart of ant colony algorithm for solving TSP problem is as follows.

This is the end of the article on "example Analysis of Ant Colony algorithm in big data". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, please share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.