Find the shortest path from the ant nest to food based on the concentration of pheromone

Shorter paths have higher pheromone concentrations

When the artificial ant colony chooses a path, it consciously searches for the shortest path according to certain algorithmic rules. rather than blindly

m ants move between adjacent nodes of the graph, determined by the transition probability parameter Use the information stored in the current node to calculate the probability of reaching the node in the next step

Same point

difference

Parallelism

self-organization

robustness

Positive feedback

Time t=0 and the number of cycles Nc = 0, set the maximum number of cycles G, place m ants on n elements (cities), and let the initial information amount τij of each edge (i, j) on the directed graph ( t) = c, where c represents a constant, and the initial time Δτij (0) = 0.

Standard update method

Ant-cycle

Ant-quality

The corresponding pheromone modification formula is

Unlike the ant system, only one ant is updated with pheromones

The value range of the pheromone trajectory amount on each solution element is limited to

Initialize the pheromone to

Before modifying the pheromone path, the ants are ranked according to the length of their travel (shorter first), The amount of pheromone released by an ant must be multiplied by the ant's ranking.

Find the optimal solution after each cycle and retain

Adaptively change the value of p

Reflects the strength of the random factors in the path search of the ant colony, The larger the value, the greater the possibility that the ants will choose the path they have traveled before, and the randomness of the search will be weakened; when the value of the heuristic factor α is too small, it is easy for the ant colony's search to get stuck in the local area prematurely. optimal Generally [1,4]

It reflects the strength of the a priori and deterministic factors of the ant colony in the process of searching for the optimal path. The larger the value, the greater the possibility that the ant will choose the local shortest path at a certain local point. Although the convergence speed of the algorithm is accelerated at this time, the randomness of the ant colony's search for the optimal path is weakened, and the search is prone to falling into a local optimal solution at this time. Generally [3,5]

The choice of size will directly affect the convergence speed and global search performance of the entire ant colony algorithm. If ρ is too small, it means that the possibility of previously searched paths being selected again is too high, which will affect the random performance and global search capabilities of the algorithm; When ρ is too large, it means that the pheromone on the path volatilizes relatively more. Although the random search performance and global search capability of the algorithm can be improved, too many useless search operations will inevitably reduce the convergence speed of the algorithm. Generally a number between 0 and 1

The path traveled by m ants in a cycle is represented as a subset of the problem solution set When the number of ants increases, the changes in pheromones on a large number of previously searched solutions (paths) will tend to average, and the role of positive information feedback will not be obvious. Generally 10~50

No special consideration, you can choose any

Generally 100~500